软件技术基础11章为第2数据结构概述

2.1基本概念和术语2.2算法的描述和分析习题2本节将对数据结构的一些基本概念和术语加以定义和解释。

数据(data)是描述客观事物的数字、字符以及所有能输入到计算机中并被计算机程序处理的符号的集合。例如，一个代数方程的求解程序中所用的数据是整数和实数；一个编译程序或文本编辑程序中所使用的数据是字符串。随着计算机应用领域的扩大，数据的含义更为广泛，如图像、声音等都可以通过编码而属于数据的范畴。

数据元素(DataElement)是数据的基本单位。有些情况下，数据元素也称为元素、结点、顶点、记录。有时，一个数据元素可以由若干个数据项(DataItem)组成，数据项是具有独立含义的、不可再分割的最小标识单位。2.1基本概念和术语数据结构(DataStructure)是数据之间的相互关系，即数据的组织形式。一般来说，数据结构所研究的主要内容包括以下三个方面：

①数据的逻辑结构——数据元素之间的逻辑关系；

②数据的存储结构——数据结构在计算机中的存储方法；

③数据的运算——对数据施加的操作。数据的逻辑结构是从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。因此，数据的逻辑结构可以看做是从具体问题抽象出来的数学模型。数据的存储结构是逻辑结构用计算机语言的实现(亦称为映像)，它是依赖于计算机语言的，对机器语言而言，存储结构是具体的，但我们只在高级语言的层次上来讨论存储结构。数据的运算是定义在数据的逻辑结构上的，每种逻辑结构都有一组基本运算，例如，对数据进行查找、插入、删除、排序等运算。这些基本运算实际上是在抽象的数据上所进行的一系列抽象的操作，我们只需要知道这些操作“做什么”，而不需要考虑“如何做”。只有确定了数据的存储结构之后，我们才能够具体实现这些基本运算。在设计一般的算法时，通常我们可以调用有关的基本运算来实现。在本书的数据结构部分所讨论的算法，均以类C语言来描述。数据类型(DataType)是和数据结构密切相关的一个概念，它最早出现在高级语言中，用以描述程序操作对象的特性。在用高级语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。定义某种数据类型，就确定了一个值域以及对该类型数据可以进行的操作。例如，C语言中的“整数类型”，其值域为某个区间上的整数(区间大小依赖于不同的机器)，对整型数据可以进行加、减、乘、除和取模等操作。

按“值”是否可分解，可将数据类型划分为两类：原子类型，其值不可分解，如C语言中的基本类型(整型、实型、字符型等)、指针类型；结构类型，其值可分解为若干个成分，如数组、结构体等类型的数据还可以进一步分解。为了加深对数据结构的感性认识，下面举例说明有关数据结构的概念。

【例2.1】学生成绩表。我们把学生成绩表称为一个数据结构，表中的每一行是一个数据元素，又称为一个结点或记录，它由学号、姓名、性别、各科成绩及平均成绩等数据项组成。该表中数据元素之间的逻辑关系是：对于表中任意一个结点，与它相邻且在它前面的结点(称为直接前趋结点)最多只有一个；与表中任意一个结点相邻且在其后的结点(称为直接后继结点)最多只有一个。表中只有第一个结点没有直接前趋结点，故称为开始结点；只有最后一个结点没有直接后继结点，故称为终端结点。例如，表中学生“马二”所在结点的直接前趋结点和直接后继结点分别是学生“丁一”和“张三”所在的结点。结点之间的关系构成了这张学生成绩表的逻辑结构。该表的存储结构则是用计算机语言表示结点之间的这种关系，可以顺序邻接地存储在一段连续的存储单元中，或者用指针将这些结点链接在一起。

在不会产生混淆的前提下，通常我们将数据的逻辑结构简称为数据结构。数据的逻辑结构有两大类：线性结构和非线性结构。

线性结构的逻辑特征：若数据结构是非空集，则第一个结点没有直接前趋结点，最后一个结点没有直接后继结点，其余结点都有一个直接前趋结点和一个直接后继结点。线性表、栈、队列、串等都是线性结构。

非线性结构的逻辑特征：一个结点可能有多个直接前趋结点和直接后继结点。树、图等属于非线性结构。数据的存储结构可以用以下四种基本的存储方法得到：

(1)顺序存储方法。借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，结点间的逻辑关系由存储单元的邻接关系来体现，由此得到的存储表示称为顺序存储结构(SequentialStorageStructure)。通常，顺序存储结构是借助于程序语言的数组(又称为向量)来描述的。

该方法主要应用于线性的数据结构，非线性的数据结构也可以通过某种线性化的方法来实现顺序存储。

(2)链接存储方法。借助指示元素存储地址的指针表示数据元素之间的逻辑关系，即逻辑上相邻的结点在物理位置上不一定相邻，由此得到的存储表示称为链式存储结构(LinkedStorageStructure)，通常要借助于程序语言的指针类型来描述它。

(3)索引存储方法。在存储结点的同时，还应建立附加的索引表。索引表中的每一项称为索引项，其一般形式为：(关键字，地址)。关键字是能够唯一标识一个结点的那些数据项。若每个结点在索引表中都有一个索引项，则该索引表称为稠密索引(DenseIndex)；若一组结点在索引表中对应一个索引项，则该索引表称为稀疏索引(SparseIndex)。稠密索引中的索引项的地址指示结点所在的存储位置，而稀疏索引中的索引项的地址则指示一组结点的起始存储位置。

(4)散列存储方法。该方法的基本思想是根据结点的关键字直接计算出该结点的存储地址。

上述四种基本存储方法既可以单独使用，也可以组合起来对数据结构进行存储。同一种逻辑结构采用不同的存储方法，可以得到不同的存储结构。至于选择何种存储结构来表示相应的逻辑结构，应当考虑算法运算的方便及时间和空间要求。2.2.1算法的概念

算法是对特定问题求解步骤的描述，是指令的有限序列。算法必须满足以下性质：

(1)输入性：0至多个输入，这些输入取自于某个特定的对象的集合。

(2)输出性：1至多个输出，这些输出是同输入有着某种特定关系的量。

(3)有穷性：对于合法的输入值，算法在执行有穷步之后结束。

(4)确定性： 对于相同的输入执行相同的路径，即对于相同的输入只能得出相同的输出。

2.2算法的描述和分析

(5)可行性：用于描述算法的操作都是足够基本的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。

需要说明的是，算法与程序是有区别的。例如操作系统，只要系统不遭破坏，它就永远不会停止，即使没有作业要处理，仍处于一个等待循环中，等待新作业的进入。因此，操作系统程序不是一个算法。求解同一计算问题时可能有许多不同的算法，在算法正确的前提下，以下三个方面可以作为算法性能的评价标准：

①算法的时间特性，执行算法所需的计算时间；

②算法的空间特性，执行算法所需的辅助存储空间；

③算法应当易于理解，易于编码，易于调试等。当然，我们希望选用一个所占存储空间小、运行时间短、其它性能也好的算法。然而，上述要求常常相互抵触，要节约算法的执行时间往往要以牺牲更多的空间为代价，而为了节省空间可能要耗费更多的计算时间。算法的时间特性和空间特性都与问题的规模有关，因此我们只能根据具体情况而有所侧重。本书主要讨论算法的时间特性，偶尔也讨论空间特性。2.2.2算法的时间特性

一个算法所需的计算时间，应当是该算法中每条语句的执行时间之和，而每条语句的执行时间是该语句的执行次数(称为频度)与该语句执行一次所需时间的乘积。但是，当算法转换为程序之后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量，这是很难确定的。我们假设每条语句执行一次所需的时间均是单位时间，一个算法的计算时间就是该算法中所有语句的频度之和。于是，我们就可以独立于机器的软、硬件系统来分析算法的时间特性。

【例2.2】求两个n阶方阵的乘积C＝A×B，其算法如下：

#definen自然数

voidMATRIXMLT(intA[n][n],intB[n][n],intC[n][n])

{inti,j,k;

(1)for(i=0;i<n;i++) n+1

(2)for(j=0；j<n;j++){ n(n+1)

(3)C[i][j]=0; n2

(4)for(k=0;k<n;k++) n2(n+1)

(5)C[i][j]=C[i][j]+A[i][k]*B[k][j]; n3

}

}其中，右边列出的是各语句的频度。语句(1)的循环控制变量i取值从0到n，语句执行了n+1次，故它的频度是n+1，但它的循环体只执行了n次。语句(2)作为语句(1)的循环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得，语句(3)、(4)和(5)的频度分别是n2、n2(n+1)和n3。该算法中所有语句的频度之和为：

T(n)=2n3+3n2+2n+1

算法的语句频度之和T(n)是矩阵阶数n的函数，n是算法求解方阵乘积问题的规模。

一般情况下，算法中基本操作重复执行的时间是问题规模n的某个函数f(n)，算法的渐进时间复杂度(简称为时间复杂度(TimeComplexity))，记做

T(n) = O(f(n))(2-1)

它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，f(n)一般是算法中频度最大的语句频度。例如，算法MATRIXMLT的时间复杂度是T(n)=O(n3)，这里的f(n)=n3是该算法中语句(5)的频度。由此可见，当有循环嵌套时，算法的时间复杂度是由最内层语句的频度f(n)决定的。

下面再举几例，说明如何求算法的时间复杂度。

【例2.3】

交换a和b的值。

temp=a;

a=b;

b=temp;

以上三条单个语句的频度为1，该算法的执行时间是一个与问题规模n无关的常数，时间复杂度记做T(n)=O(1)。事实上，只要算法的执行时间不随着问题规模的增加而增长，即使算法中有上千条语句，其时间复杂度也只是O(1)。

【例2.4】

判断n是否为素数。

voidprime(intn)

{inti=2;

while((n%i)!=0&&i<sqrt(n))

i++;

if(i>=sqrt(n))printf("%d是素数",n);

elseprintf("%d不是素数",n);

}

设语句i++；的频度为f(n)，由i<sqrt(n)可知f(n)<sqrt(n)，时间复杂度应考虑最坏的情况，所以

【例2.5】

变量计数。

i=1；1

while(i<=n)i=i*2;f(n)

由于2f(n)≤n，即f(n)≤lbn，取最大值f(n)=lbn，T(n)=O(f(n))=O(lbn)。

将常见的时间复杂度按数量级递增排列，则依次为：常量阶O(1)、对数阶O(lbn)、线性阶O(n)、线性对数阶O(nlbn)、平方阶O(n2)、立方阶O(n3)、…、k次方阶O(nk)、指数阶O(2n)。显然，时间复杂度为指数阶的算法效率极低，当n值稍大时就无法应用。

2.2.3算法的空间特性

类似于算法的时间复杂度，算法的空间复杂度(SpaceComplexity)可以作为算法所需辅助存储空间的度量，记做

S(n) = O(f(n))(2-2)

它也是问题规模n的函数。若额外空间相对于输入数据量来说是常量，则称此算法为原地工作。如果所占空间量依赖于特定的输入，则除了特别指明外，均应按最坏情况来分析。

一、名词解释

数据，数据元素，逻辑结构，存储结构，线性结构，非线性结构，顺序存储结构，链式存储结构，索引存储结构，散列存储结构，算法，时间复杂度

二、填空题

1．从某种意义上说，数据、数据元