文档介绍：第 3 章数据结构
数据结构的基本概念
本节的学习目标:掌握数据结构基本概念;理解逻辑结构、存储结构和数据运算三方面的概
念及相互之间的关系;了解算法描述方法。
本节的知识要点:数据结构的概念;线性数据结构和非线性数据结构之间的区别;时间复杂
度和空间复杂度的度量方法;
一、本节要点
(一)基本概念和术语
(Data)是信息的载体。它能够被计算机识别、存储和加工处理,是计算机程
序加工的"原料"。随着计算机应用领域的扩大,数据的范畴包括:整数、实数、字符串、图
像和声音等。
(Data Element)是数据的基本单位。数据元素也称元素、结点、顶点、
记录。一个数据元素可以由若干个数据项(也可称为字段、域、属性)组成。数据项是具有
独立含义的最小标识单位。
(Data Structure)指的是数据之间的相互关系,即数据的组织形式。数据
结构一般包括以下三方面内容:
①数据元素之间的逻辑关系,也称数据的逻辑结构(Logical Structure);
数据的逻辑结构是从逻辑关系上描述数据,与数据的存储无关,是独立于计算机的。
数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
②数据元素及其关系在计算机存储器内的表示,称为数据的存储结构(Storage
Structure);
数据的存储结构是逻辑结构用计算机语言的实现(亦称为映象),它依赖于计算机语
言。对机器语言而言,存储结构是具体的。一般,只在高级语言的层次上讨论存储结构。
③数据的运算,即对数据施加的操作。
数据的运算定义在数据的逻辑结构上,每种逻辑结构都有一个运算的集合。最常用的检
索、插入、删除、更新、排序等运算实际上只是在抽象的数据上所施加的一系列抽象的操作。
所谓抽象的操作,是指我们只知道这些操作是"做什么",而无须考虑"如何做"。只有
确定了存储结构之后,才考虑如何具体实现这些运算。
在不产生混淆的前提下,常将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大
类:
(1)线性结构
线性结构的逻辑特征是:若结构是非空集,则有且仅有一个开始结点和一个终端结点,
并且所有结点都最多只有一个直接前趋和一个直接后继。
线性表是一个典型的线性结构。栈、队列、串等都是线性结构。
(2)非线性结构
非线性结构的逻辑特征是:一个结点可能有多个直接前趋和直接后继。数组、广义表、
28
树和图等数据结构都是非线性结构。
(二)算法分析
在解决实际问题时,除了设计一个基本算法外,还需要考虑现有的算法是否已经很完善
了,还有没有更好的算法,称为算法分析。算法分析的内容很多,这里仅考虑算法的复杂度,
通常以算法执行时在时间和空间资源方面的消耗多寡作为评价算法优劣的标准,称为时间复
杂度和空间复杂度。
时间复杂度是估计算法执行所需要的时间,也就是算法中每一个语句的执行次数乘以每
一次执行所需的时间的总和。但是由于语句的执行时间与所采用的机器与编泽程序的功能强
弱有关,所以单从执行时间上来判断容易掩盖算法本身的优劣,为此人们通常用语句的执行
次数来估什,使它成为与硬、软件无关的量度。
例
①…② for(i=1;i<=n;i++) ③for(i=1;i<=n;i++)
x=x+1; x=x+1; for(j=1;j<=n;j++)
… x=x+1;
在例 1 中有 3个程序段,每个程序段中都有语句 x=x+l,它在 3 个程序段中执行的次
数分别为①l 次,②n 次、③n2 次。算法中语句的重复次数称为该语句的频度,记作 f(n),
它是 n 的函数。某一算法的时间复杂度 T(n)是以该算法中频度最大语句的频度 f(n)作
为该算法的时间复杂度,记作 T(n)=O(f(n)),也就是该算法执行次数的数量阶。在例
1 中 3 个程序段的时间复杂度分别为①O(l)、②O(n)、③O(n2)。
由上例可知,时间复杂度虽不能精确地确定一个算法的执行时间,但可以看到随着问
题的规模 n 的增大,算法所耗用时间的增长趋势。
空间复杂度是算法对空间占用的量度,类似于时间复杂度。一般在考虑空间复杂度时,
只估算算法所需增添的辅助空间,而对问题中原始数据所占的空间,由于与算法无关,不予
考虑。
二、课后部分习题答案
3-1 什么是算法?
解答:算法是在有限步骤内求解某一问题所使用的一组定义明确的规则。通俗点说,就是计
算机解题的过程。在这个过程中,无论是形成解题思路还是编写程序,