教学课件-软件技术基础(鲍有文)

1.1数据结构的主要内容

1.2基本概念和术语

1.3算法

1.4本章小结

自测习题1.1数据结构的主要内容

【例1-1】某学校课程表管理。表1-1中的课程表就是一个数据结构。课程表管理的主要功能包括：查找、浏览、插入、修改和删除。如果把表1-1中的一行看成一个记录，则在此表中，结点和结点之间的关系是一种最简单的线性关系。

【例1-2】家谱问题。图1-1所示为我国唐王朝初期的家谱，它像一棵倒立的树，清楚地描述了唐王朝家庭人员的继承关系。图1-1唐王朝初期的家谱

【例1-3】最短路径问题。如图1-2所示，有8个城市，以0~7为其编号，带箭头的线表示城市之间的连接关系，线上的数字表示两个城市之间的距离。问题是如何确定一个城市与其他城市的最短距离。由上面三个例子可见，描述这类非数值计算问题的数学模型不再是数学方程，而是诸如表、树和图之类的数据结构。因此，简单地说，数据结构是一门研究非数值计算的程序设计问题中相关问题的学科，具体包括数据之间的逻辑关系和对数据的操作，同时还研究如何将具有逻辑关系的数据按一定的存储方式存放到计算机中。图1-2城市之间的距离和连接关系1.2基本概念和术语1.2.1数据、数据元素及数据项数据(Data)是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并能够被计算机程序处理的符号的总称。数据是计算机程序加工的“原料”。例如，一个利用数值分析方法解代数方程的程序，其处理对象是整数和实数；编译程序或文字处理程序的处理对象是字符串。因此，对计算机科学而言，数据的含义极为广泛，如图像、声音等都可以通过编码而归于数据的范畴。数据元素(DataElement)是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。数据元素又称为元素、结点或记录。数据项(DataItem)是数据的不可分割的、含有独立意义的最小单位。数据项也被称为字段或域。以学生成绩表为例，如表1-2所示，整张表是数据，每一行记录称为数据元素，每一个字段称为数据项。

1.2.2数据结构数据结构(DataStructure)是相互之间存在一种或多种特定关系的数据元素的集合。这是对数据结构的一种简单解释。从1.1节中的三个例子可以看到，在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系。根据数据元素之间关系的不同特性，通常有下列四类基本结构。

(1)集合：结构中的数据元素之间除了“同属于一个集合”的关系外，别无其他关系。

(2)线性结构：结构中的数据元素之间存在一个对一个的关系。

(3)树形结构：结构中的数据元素之间存在一个对多个的关系。

(4)图状结构或网状结构：结构中的数据元素之间存在多个对多个的关系。图1-3为上述四类基本结构的关系图。由于“集合”是数据元素之间关系极为松散的一种结构，因此在本书中不对其进行讨论。图1-3四类基本结构上述数据结构的定义只是对操作对象的一种数学描述，换句话说，是将操作对象抽象出来的数学模型。结构定义中的“关系”描述的是数据元素之间的逻辑关系，因此又称为数据的逻辑结构(DataLogicalStructure)。然而，讨论数据结构是为了在计算机中实现对它的操作，因此还需研究如何在计算机中表示它。

数据结构在计算机中的表示(又称映像)称为数据的物理结构(DataPhysicalStructure)，又称存储结构。存储结构包括数据元素的表示和关系的表示。在计算机中，表示信息的最小单位是二进制数的一位，称为位(Bit)。在计算机中，可以用一个由若干位组合起来形成的一个位串表示一个数据元素(如用一个字长的位串表示一个整数，用8位二进制数表示一个字符等)，通常称这个位串为元素(Element)或结点(Node)。当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串称为数据域(DataField)。因此，元素或结点可看成是数据元素在计算机中的映像。数据元素之间的关系在计算机中有两种不同的表示方法：顺序存储映像和非顺序存储映像，由此可得到两种主要的存储结构：顺序存储结构和链式存储结构。顺序存储的特点是：在内存中开辟一组连续的存储单元，借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系。例如，有一个数组A，含有n个元素，这n个数据元素的存储如图1-4所示。链式存储结构的特点是：借助指示元素存储地址的指针Pointer)表示数据元素之间的逻辑关系，数据元素的存储并不一定是连续的。例如，有两个数据元素，一个为“王家”，另一个为“李家”，二者的存储并不连续。为了能由数据元素“李家”找到数据元素“王家”，还需要存储数据元素“王家”的地址0023，这样两个数据元素之间的邻接关系就能表示了，如图1-5所示。数据的逻辑结构和物理结构是密切相关的两个方面，以后读者会看到，任何一个算法的设计都取决于选定的数据(逻辑)结构，而算法的实现则依赖于所采用的存储结构。图1-4顺序存储示例图图1-5链式存储示例图数据类型(DataType)是和数据结构密切相关的一个概念，它最早出现在高级程序语言中，用以刻画(程序)操作对象的特性。在用高级程序语言编写的程序中，每个变量、常量或表达式都有一个它所属的确定的数据类型。这些类型明显或隐含地规定了在程序执行期间变量或表达式所有可能取值的范围，以及在这些值上允许进行的操作。因此数据类型是一个值的集合和定义在这个取值范围上的一组操作的总称。例如，C语言中的整型变量，其取值范围为某个区间上的整数(区间大小依赖于不同的机器)，定义在其上的操作为：加、减、乘、除和取模等算术运算。

按照数据元素所取值的不同特性，高级程序语言中的数据类型可分为两类：一类是非结构的原子类型，原子类型的值是不可分解的，如C语言中的基本类型(整型、实型、字符型和枚举类型)、指针类型和空类型；另一类是结构类型，结构类型的值是由若干成分按某种结构组成的，因此是可以分解的，并且它的成分可以是非结构的，也可以是结构的，例如数组的值由若干分量组成，每个分量可以是整数，也可以是数组等。在某种意义上，如果把数据结构看成是“一组具有相同结构的值”，则结构类型就可以看成由一种数据结构和定义在其上的一组操作组成。引入“数据类型”概念的目的，从硬件的角度来看，是作为解释计算机内存中信息含义的一种手段，而对使用数据类型的用户来说，则实现了信息的隐蔽，即将一切用户不必了解的细节都封装在数据类型中。例如，用户在使用“整数”类型时，既不需要了解“整数”在计算机内部是如何表示的，也不需要知道其操作是如何实现的。从上面的分析可以得到数据结构的概念。数据结构指的是数据之间的相互关系，即数据的组织形式，主要包括以下三方面的内容：

(1)数据元素之间的逻辑关系，也称为数据的逻辑结构。

(2)数据元素及其关系在计算机存储器内的表示，称为数据的存储结构(StorageStructure)。

(3)数据的运算，即对数据施加的操作。这也是数据结构的主要研究内容，即非数值应用问题中数据之间的逻辑关系，同时数据结构还研究如何将具有逻辑关系的数据按一定的存储结构存放在计算机内，并确定对数据施加的操作及实现方式。1.3算法1.3.1算法的概念及特性

【例1-4】

main()

{

printf(″请稍等…您将知道世界的末日…″)；

while(1)

{}

}

【例1-5】

getsum(intnum)

{

inti，sum=0；

for(i=1；i<=num；i++)

sum+=i；

}仔细分析例1-4的程序可以看到，while循环语句的判断条件永远为“真”，结果是循环没有结束的时候，执行的时候将陷入死循环。分析例1-5可以知道，函数虽然进行了累加运算，但是没有任何输出，无输出的算法没有任何意义。那么什么是算法呢？一个算法应该满足哪些特性呢？

算法(Algorithm)是对特定问题求解步骤的一种描述，它是指令的有限序列，每一条指令表示一个或多个操作。此外，一个算法还具有下列五个重要特性：

(1)有穷性：一个算法必须总是(对任何合法的输入值)在执行有穷步之后结束，且每一步都可在有穷的时间内完成。

(2)确定性：算法中每一条指令必须有确切的含义，读者理解时不会产生二义性，并且在任何条件下，算法只有唯一的一条执行路径，即对于相同的输入只能得出相同的输出。

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

(4)输入：一个算法有零个或多个输入，这些输入取自于某个特定对象的集合。

(5)输出：一个算法有一个或多个输出，这些输出是同输入有着某些特定关系的量。

1.正确性(Correctness)算法应当满足具体问题的需求。通常一个大型问题的需求要以特定的规格说明方式给出，而一个实习问题或练习题往往就不那么严格，目前多数采用自然语言来描述需求，至少应当包括对于输入、输出和加工处理等的明确的无歧义性描述。

算法是否正确，通常要将其转化为程序，通过上机来检验。“正确”一词的含义通常有很大差别，大体可分为以下四个层次：程序不含语法错误；程序对于几组输入数据能够得出满足规格说明要求的结果；程序对于精心选择的典型、苛刻的几组输入数据能够得出满足规格说明要求的结果；程序对于一切合法的输入数据都能产生满足规格说明要求的结果。显然，达到第四层意义下的正确是极为困难的，所有不同输入数据的数量大得惊人，逐一验证的方法是不现实的。对于大型软件需要进行专业测试，而在一般情况下，通常以第三层意义的正确性作为衡量一个程序是否合格的标准。

2.可读性(Readability)算法主要是为了人们进行阅读与交流，其次才是机器执行。可读性好有助于人们对算法的理解；晦涩难懂的程序易于隐藏较多错误，难以调试和修改。

3.健壮性(Robustness)

当输入数据非法时，算法也能适当地做出反应或进行处理，而不会产生莫明其妙的输出结果并中止程序的执行，以便在更高的抽象层次上进行处理。

4.效率与低存储量需求

通俗地说，效率指的是算法的执行时间。对于同一个问题如果有多个算法可以解决，则执行时间短的算法效率高。存储量需求是指算法执行过程中所需要的最大存储空间。效率与低存储量需求这两者都与问题的规模有关。例如，求100个人的平均分与求1000个人的平均分所花的执行时间或运行空间显然有一定的差别。

1.3.2算法的描述方法算法的描述方法很多，根据描述语言的不同，可以分为框图算法描述、非形式算法描述、类C语言算法描述、C语言编写的程序或函数。本书采用的是类C语言算法描述方法，类C语言不拘泥于C语言的细节，又容易转换成C或者C＋＋程序，这使得数据结构和算法的描述及讨论变得简明清晰。本书采用的类C语言精选了C语言的一个核心子集，同时作了若干扩充修改，从而增强了语言的描述功能，以下对其作简要说明。表1-3所示为类C语言的常用语法。

1.3.3算法的性能分析前面已经提到，好的算法要求高效率和低存储量。目前，随着计算机硬件的迅速发展，计算机的存储空间越来越大，所花的费用越来越低，讨论算法空间复杂度的必要性不大，因此，本书主要讨论算法的时间特性。时间特性通过算法执行时间进行描述，算法执行时间需依据该算法编制的程序在计算机上运行时所消耗的时间来度量。显然，同一个算法用不同的语言实现，或者用不同的编译程序进行编译，或者在不同的计算机上运行时，执行时间均不相同。这表明使用绝对的执行时间衡量算法的效率是不合适的。撇开这些与计算机硬件、软件有关的因素，可以认为一个特定算法执行时间的大小只依赖于问题的规模(通常用整数n表示)，或者说，它是问题规模的函数。一个算法是由控制结构(顺序、分支和循环)和基本操作构成的，算法时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题来说是基本操作的操作，以该基本操作重复执行的次数作为算法的时间量度，记做Ο(n)=Ο(f(n))其中，f(n)为基本操作重复执行的次数，是问题规模n的非递减函数，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同；Ο(n)称做算法的渐近时间复杂度，简称时间复杂度。例如，求4×4矩阵元素和，“加法”运算是矩阵元素求和问题的基本操作。整个算法的执行时间与该基本操作(加法)重复执行的次数成正比，记做Ο(4)=Ο(f(4))其中，f(4)＝4×4＝16。算法描述如下：

intsum(intnum［4］［4］)

{

inti，j，r=0；

for(i=0；i<4；i++) for(j=0；j<4；j++) r+=num［i］［j］；/*基本操作*/

returnr；

}显然，被称做问题的基本操作重复执行次数和算法的执行时间是成正比的。在多数情况下，重复执行是最深层循环内的语句中的基本操作，其执行次数和包含它的语句的频度相同(语句的频度指的是该语句重复执行的次数)。例如，程序段1:

for(i=1；i<=n；++i)

++x；程序段2：

for(j=1；j<=n；++j)

for(k=1；k<=n；++k)

++x；程序段1的语句频度为n，时间复杂度为Ο(n)；程序段2的语句频度为n2，时间复杂度为Ο(n2)。常见函数的增长率如图1-6所示。对于算法来说，随着问题规模的增加，其时间复杂度变化或增加得越缓慢，则性能越好。图1-6常见函数的增长率1.4本章小结

本章首先从实例出发介绍了数据结构研究的主要内容，然后介绍了有关的基本概念和术语，最后介绍了算法的概念、特性、描述方法及性能分析。在深入学习数据结构之前，首先了解数据结构的意义、研究内容以及一些相关概念，对于深入了解后面章节的内容会有很大的帮助。自测习题

1-1解释下列术语:数据数据项数据逻辑结构数据存储结构算法

1-2数据结构是一门研究什么内容的学科？

1-3根据数据元素之间的逻辑关系，一般分为哪几类基本的数据结构？

1-4算法有哪几个特性？

1-5有下列运行时间函数：

(1)T1(n)=1000；(2)T2(n)=n2+1000n；

(3)T3(n)=3n3+100n2+n+1。试分别写出相应的用Ο表示的时间复杂度。

1-6试给出下面两个算法的时间复杂度。

(1)fori＝1tondo

x＝x+1；

(2)fori＝1tondo

forj＝1tondo x＝x+1；2.1线性结构

2.2树和二叉树

2.3本章小结

自测习题2.1线性结构2.1.1线性表及逻辑结构

线性表(Linear_List)是最常用且最简单的一种数据结构。简言之，一个线性表是n个数据元素的有限序列。每个数据元素的具体含义在不同的情况下各不相同，它可以是一个数或一个符号，也可以是一页书，甚至其他更复杂的信息。例如，26个英文字母的字母表：(A，B，C，…，Z)是一个线性表，表中的数据元素是单个字母字符。又如，目前全国重点大学的校名可以用线性表的形式给出：

(“清华大学”，“北京大学”，“北京交通大学”，“上海复旦大学”，…)表中的数据元素是字符串。在较复杂的线性表中，一个数据元素可以由若干个数据项(Item)组成。在这种情况下，常把数据元素称为记录(Record)，含有大量记录的线性表又称文件(File)。例如，某公司人员登记表如表2-1所示，表中每个员工的情况为一个记录，它由姓名、性别、年龄、工作证号、部门五个数据项组成。综上可见，线性表中的数据元素可以是各种各样的，但同一线性表中的数据元素必定具有相同的特性，即属于同一数据对象，相邻数据元素之间存在着序邻接关系。若将线性表记为(a1，…，ai-1

，ai，ai+1，…，an)则表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素。当i＝1，2，…，n-1时，ai有且仅有一个直接后继，当i＝2，3，…，n时，ai有且仅有一个直接前驱。由此可以总结出线性结构的特点是：在数据元素的非空有限集中，

(1)存在唯一的一个被称做“第一个”的数据元素；

(2)存在唯一的一个被称做“最后一个”的数据元素；

(3)除第一个之外，集合中的每个数据元素均只有一个前驱；

(4)除最后一个之外，集合中每个数据元素均只有一个后继。线性表中元素的个数n(n≥0)定义为线性表的长度，n＝0时称为空表。在非空表中的每个数据元素都有一个确定的位置，如a1是第一个数据元素，an是最后一个数据元素，ai是第i个数据元素，称i为数据元素ai在线性表中的位序。线性表是一个相当灵活的数据结构，它的长度可根据需要增长或缩短，即对线性表的数据元素不仅可以进行访问，还可进行插入和删除等。对线性表进行的操作有以下几种：

(1)初始化：创建一个空的线性表。

(2)计数：求线性表的长度。

(3)读取：读取线性表的第i个元素。

(4)删除：删除线性表的第i个元素。

(5)归并：把两个或更多的线性表按一定的要求合并成一个新表。

(6)插入：在第i个位置插入新的数据元素。

(7)查找：确定在线性表中是否存在数据元素x。2.1.2线性表的顺序存储结构

1.顺序存储结构的概念及特点

一个线性表可以采用多种不同的存储方式存储到计算机中，其中，最简单的方法就是顺序存储。线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元素。假设线性表的每个元素需要占用d个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置，则线性表中第i＋1个数据元素的存储位置LOC(ai＋1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai＋1)＝LOC(ai)＋d一般来说，线性表的第i个数据元素ai的存储位置为LOC(ai)＝LOC(a1)＋(i-1)×d式中，LOC(a1)是线性表的第一个数据元素a1的存储位置，通常称做线性表的起始位置或基地址。假设一个线性表含有n个元素，分别为a0，a1，…，ai，…，an-1，当采用顺序存储的时候，数据元素的逻辑地址、数据元素以及存储地址的关系如图2-1所示。图2-1顺序存储示意图线性表的这种计算机内表示称做线性表的顺序存储结构或顺序映像(SequentialMapping)，相应地，称这种存储结构的线性表为顺序表。顺序表的特点是：表中相邻的元素ai和ai+1被赋以相邻的存储位置LOC(ai)和LOC(ai+1)，即以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系。由此，只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取的存储结构。

2.顺序存储结构的数据类型定义高级程序设计语言中有一种数据类型为数组类型，系统开辟了一片连续的存储单元对其进行存储，此外，数组也具有随机存取的特性，因此，通常都用数组来描述数据结构中的顺序存储结构。在此，由于线性表的长度可变，且所需最大存储空间随问题的不同而不同，因此在类C语言中描述如下:

#defineMAXSIZE100

/*表的最大长度*/

#defineDataTypeint

/*数据元素(结点)类型*/

typedefstruct

{

DataTypedata［MAXSIZE］；

/*数组Data下标为0，1，…，MAXSIZE-1*/

intlast；/*last为表长*/

}SeqList；/*SeqList即为顺序表的类型*/

3.基本操作在顺序表上的实现在这种存储结构中，容易实现线性表的某些操作，如随机存取第i个数据元素等。要特别注意的是，C语言中数组的下标从“0”开始，因此，若L是SeqList类型的顺序表，则表中第j个数据元素是L.data［j-1］。下面重点讨论线性表的基本操作在顺序表上的实现方法。

1)顺序表的初始化执行顺序表的初始化函数，结果返回一个空的顺序表。

SeqListInti_Sequenlist(SeqLista)

{

a.last=0；

returna；/*通过返回值，带回结果*/

}

2)顺序表上元素的插入插入操作是指在长度为n的线性表中第i(1≤i≤n)个元素之前插入一个元素x，使长度为n的线性表变为长度为n＋1的线性表。算法的思路是：因为要使插入元素后的线性表仍具有线性表的结构特征，所以必须将元素ai，…，an逐一向后移动一个位置，然后将x放置到第i个位置，表长加1。这里移动的顺序十分重要，从逻辑上考虑，只能按an，…，ai的顺序进行移位操作，先将an向后移一位，再将an-1移到an原来的位置上，以此类推，直到ai移到ai+1的位置。例如，图2-2表示一个线性表在进行插入操作前后其数据元素在存储空间中的位置变化。为了在线性表的第2个和第3个元素之间插入一个值为38的数据元素，需将第3个至第6个数据元素依次往后移动一个位置，并且表长变为7。图2-2线性表在进行插入操作前后其数据元素在存储空间中的位置变化顺序表的第i个位置插入数据元素的算法如下:

intinsert(SeqListL，DataTypex，inti)

{

intk；

/*判断位置是否合法*/

if(i<1||i>(L.last+1)||L.last>=MAXSIZE)

{

printf(″error″)；

return0；

}

else

{

for(k=L.last；k>=i；k)

L.data［k］=L.data［k-1］；

L.data［i-1］=x；

L.last=L.last+1；

return(1)；/*成功返回1*/

}

}一般情况下，在第i(1≤i≤n)个元素之前插入一个元素时，需将第n个至第i个(共n－i＋1个)元素向后移动一个位置。由以上算法可见，当在顺序存储结构的线性表中某个位置上插入一个数据元素时，其时间主要耗费在移动元素上(换句话说，移动元素的操作为预估算法时间复杂度的基本操作)，而移动元素的个数则取决于插入元素的位置。假设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素次数的期望值(平均次数)为一般地，可以假定在线性表的任何位置上插入元素都是等概率的，即

则

由上式可见，在顺序存储结构的线性表中插入一个数据元素，约平均移动表中的一半元素。若表长为n，则算法的时间复杂度为O(n)。对后面的各种算法，不再详细分析和推导算法的时间复杂度，只给出推导的结果。

3)顺序表上元素的删除在顺序表上实现删除操作也必须移动元素才能使删除后的线性表仍具有线性结构的特征。这里移动顺序也是十分重要的，从逻辑上考虑，只能按ai+1，…，an的顺序进行移位操作，先将ai+1向前移一位，覆盖掉被删除的元素，再将ai+2移到ai+1原来的位置上，以此类推，直到an移到an-1的位置上，并将表长减1。例如，图2-3所示为一个线性表在进行删除操作前后其数据元素在存储空间中的位置变化。为了在线性表中删除第3个数据元素，需将第4个至第7个数据元素依次往前移动一个位置，且表长变为6。图2-3线性表在进行删除操作前后其数据元素在存储空间中的位置变化顺序表的第i个位置删除数据元素的算法如下:

intDelete(SeqListL，inti)

{

intj；

if((i<1)||(i>L.last)||(L.last==0))

{

printf(″Error!″)；

return0；

}

else

{

for(j=i；j<L.last；j++)//第j+1个元素前移

L.data［j-1］=L.data［j］；

L.last；

return1；

}

}线性表的删除操作是使长度为n的线性表(a1，…，ai-1，ai，ai+1，…，an)变成长度为n-1的线性表(a1，…，ai-1，ai+1，…，an)。数据元素ai-1、ai和ai+1之间的逻辑关系发生了变化，为了在存储结构上反映这个变化，同样需要移动元素。一般情况下，删除第i(1≤i≤n)个元素时需将第i+1个至第n个(共n-i个)元素依次向前移动一个位置。当在顺序存储结构的线性表中某个位置上删除一个数据元素时，其时间主要耗费在移动元素上(换句话说，移动元素的操作为预估算法时间复杂度的基本操作)，而移动元素的个数则取决于删除元素的位置。在顺序存储结构的线性表中删除一个数据元素，平均约移动表中的一半元素。若表长为n，则算法的时间复杂度为O(n)。

4)顺序表上元素的查找在顺序表上查找某个元素时，对线性表上的元素只有访问，没有变动，所以无移动元素的操作。基本操作是判断表中的元素是否和给定的元素值x相等。顺序表上元素的查找算法如下：

intLocate(SeqLista，DataTypex)

{

/*在顺序表a中查找值为x的元素，返回其位置*/

intk=1；

while(k<=a.last&&a.data［k-1］!=x)

k++；

if(k<=a.last)

returnk；

else

return0；//找不到元素

}顺序表上元素的查找算法的时间复杂度为O(n)。线性表还可进行一些更复杂的操作，如将两个或两个以上的线性表合并成一个线性表，把一个线性表拆开成两个或两个以上的线性表，重新复制一个线性表等等。有些操作将在应用举例部分给出例题。

4.应用举例

【例2-1】假设利用两个线性表la和lb分别表示两个集合a和b(线性表中的数据元素即为集合中的成员)，现要求一个新的集合a＝a∪b。算法分析：题目要求对线性表进行如下操作：扩大线性表la，将存在于线性表lb中而不存在于线性表la中的数据元素插入到线性表la中。只需从线性表lb中依次取得每个数据元素，并按值在线性表la中进行查找，若不存在，则将其插入。上述操作过程可用下列算法来描述。

voidunite_seqlist(SeqLista，SeqListb)

{

inti，j，k；

for(i=1；i<=b.last；i++)

{

k=1；

while(k<=a.last&&a.data［k-1］!=b.data［i-1］)

k++；

if(k>a.last)//找不到元素

if(a.last<MAXSIZE)/*判断线性表是否满*/

{

a.data［a.last］=x；

a.last=a.last+1；

}

else

{

printf(″overflow!″)；

break；

}

}

}

【例2-2】已知线性表la和lb中的数据元素按值非递减有序排列，现要求将la和lb归并为一个新的线性表lc，且lc中的数据元素仍按值非递减有序排列。例如，设

la=(3，5，8，13)lb=(6，9，11，15，20)lc＝(3，5，6，8，9，11，13，15，20)算法分析：由题目要求可知，lc中的数据元素或是la中的数据元素，或是lb中的数据元素，只要先设lc为空表，然后将la或lb中的元素逐个插入到lc中即可。为使lc中元素按值非递减有序排列，可设两个指针i和j分别指向la和lb中的某个元素，若设i当前所指的元素为a，j当前所指的元素为b，则当前应插入到lc中的元素c为上述操作过程可用下列算法来描述。

voidmerge_seqlist(SeqListla，SeqListlb，SeqListlc)

{

inti，j，k；

i=j=k=1；

while(i<=la.last&&j<=lb.last)if(la.data［i-1］<=lb.data［j-1］){lc.data［k-1］=la.data［i-1］；

k++；

i++；

}

else{lc.data［k-1］=lb.data［j-1］；

k++；

j++；

}

while(i<=la.last){lc.data［k-1］=la.data［i-1］；

k++；

i++；

}

while(i<=lb.last){

lc.data［k-1］=lb.data［j-1］；

k++；

j++；

}

lc.last=k-1；

}2.1.3线性表的链式存储结构

1.链表的概念及类型定义

从2.1.2节的讨论中可知，线性表的顺序存储结构的特点是：逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中任一个元素，它的存储位置可用一个简单、直观的公式来表示。然而，从另一方面来看，这个特点也造成了这种存储结构的弱点：在进行插入或删除操作时，需要移动大量元素。本节将讨论线性表的另一种表示方法——链式存储结构，由于这种结构不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的缺点，但同时也失去了顺序表可随机存取的优点。线性表的链式存储结构的特点是：可用一组任意的存储单元来存储线性表的数据元素(这组存储单元可以是连续的，也可以是不连续的)。因此，为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息之外，还需存储一个指示其直接后继的信息(即直接后继的存储位置)。这两部分信息组成数据元素ai的存储映像，称为结点(Node)。结点包括两个域：存储数据元素信息的域称为数据域;存储直接后继存储位置的域称为指针域。指针域中存储的信息称做指针或链。n个结点连接成一个链表，即为线性表(a1，a2，…，an)的链式存储结构。又由于此链表的每个结点中只包含一个指针域，因此又称线性链表或单链表(本书后面内容中出现的“链表”指的就是单链表)。

例如，图2-4所示为线性表(A，B，C，D，E，F，G)的线性链表存储结构，整个链表的存取必须从头指针开始进行，头指针指示链表中第一个结点(即第一个数据元素的存储映像)的存储位置。同时，由于最后一个数据元素没有直接后继，因此线性链表中最后一个结点的指针为“空”(NULL)。用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针来指示的。换句话说，指针为数据元素之间的逻辑关系的映像，逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，因此，这种存储结构为非顺序映像或链式映像。图2-4线性链表存储结构通常把链表画成用箭头相连接的结点的序列，结点之间的箭头表示链域中的指针。图2-4所示的线性链表可画成如图2-5所示的形式，这是因为在使用链表时，关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。图2-5线性链表举例由此可见，单链表可由头指针唯一确定，在C语言中可用“结构指针”来描述。下面就是线性表的单链表存储结构的结点类型定义：

typedefstructnode//结点类型定义

{

DataTypedata；

structnode*next；

}LinkList；假设L是LinkList型变量，则L为单链表的头指针，它指向表中的第一个结点。若L为“空”(L＝NULL)，则它所表示的线性表为“空”表，其长度n为“零”。有时在单链表的第一个结点之前附设一个结点，称为头结点。头结点的数据域可以不存储任何信息，也可存储如线性表的长度等附加信息。头结点的指针域存储指向第一个结点的指针(即第一个元素结点的存储位置)。如图2-6(a)所示，单链表的头指针指向头结点。若线性表为空表，则头结点的指针域为“空”，如图2-6(b)所示。图2-6带头结点的单链表在线性表的顺序存储结构中，由于逻辑上相邻的两个元素在物理位置上紧邻，因此每个元素的存储位置都可从线性表的起始位置计算得到。在单链表中，任何两个元素的存储位置之间都没有固定的联系。然而，每个元素的存储位置都包含在其直接前驱结点的信息之中。

2.基本操作在单链表上的实现假设p是指向线性表中第i个数据元素(结点ai)的指针，则p->next是指向第i＋1个数据元素(结点ai+1)的指针。换句话说，若p->data＝ai，则p->next->data＝ai+l。由此可知，在单链表中，取得第i个数据元素必须从头指针出发寻找，因此，单链表是非随机存取的存储结构。

1)单链表初始化操作算法思想：建立一个单链表，首先要生成一个结点，空链表就是只包含头结点的链表，如图2-7所示。图2-7单链表初始化操作示意图单链表初始化操作的算法如下:

voidInitList(LinkList*head)

{

LinkList*t；

t=(LinkList*)malloc(sizeof(LinkList))；

head=t；

t->next=NULL；

}

2)建立单链表操作设线性表中结点的数据类型为字符，依次输入这些字符，并以“$”作为输入结束的标志。动态地建立单链表有两种常用方法：尾插入法和头插入法。下面详细讲解这两种方法的算法实现。

(1)尾插入法建表。算法思路：从一个空表开始，反复读入数据，生成新结点，将读入的数据存放到新结点的数据域，然后将新结点插到当前链表的表尾上，直到读入结束标志符为止。图2-8描述了插入一个新结点的过程。图2-8带头结点的尾插入法建表过程示意图分析尾插入法建表的过程：一般情况下，插入一个元素对应的指针操作是

last->next＝t；

last＝t；但若单链表为空链表，则在插入第一个元素的时候，对应的指针操作是

head＝t；

last＝t；由此可见，当单链表为空链表而又插入第一个元素时，情况比较特殊。为了使链表上的操作简单、一致，可以采用带头结点的单链表。下面为带头结点的尾插入法建表算法。voidCreateList1(LinkList*head)

{LinkList*last，*t；

charch；

t=(LinkList*)malloc(sizeof(LinkList))；

head=t；

last=t；//建立表的头结点

t->next=NULL；

while((ch=getchar())!=′$′){t=(LinkList*)malloc(sizeof(LinkList))；

t->data=ch；

last->next=t；

last=t；

t->next=NULL；

}}通过上面的算法可以总结出，带有头结点的单链表通常具有以下优点：①线性表中第一个元素结点的地址被存放到头结点的指针域中，这样表中所有结点的地址均放到前驱结点中，算法对所有元素结点的处理可一致化；②无论链表是否为空，头指针均指向头结点，这给算法的处理带来了方便。指针变量和结点变量是两个容易混淆但又必须搞清楚的概念。head是LinkList类型的指针变量，head中指针域存放的为LinkList类型的某个结点的地址。在建表算法中，每个新结点都是在需要的时候动态生成的，是通过标准函数malloc即malloc(sizeof(LinkList))生成的。当某个变量不再需要的时候，可以通过free()函数释放掉结点所占用的空间。在C语言中，对指针所指向结点的成员进行访问，通常用运算符->。例如，如果某个结点的指针为p，则访问该结点的两个分量的语句为p->data，p->next。

(2)头插入法建表。算法思路：从一个空表开始，反复读入数据，生成新结点，将读入的数据存放到新结点的数据域，然后将新结点插到当前链表的第一个结点位置上，直到读入结束标志符为止图2-9描述了插入一个新结点的过程。图2-9带头结点的头插入法建表过程示意图

voidCreateList2(LinkList*head)

{

LinkList*t；

charch；

t=(LinkList*)malloc(sizeof(LinkList))；

head=t；//建立头结点

t->next=NULL；

while((ch=getchar())!=′$′)

{

t=(LinkList*)malloc(sizeof(LinkList))；

t->data=ch；

t->next=head->next；

head->next=t；

}

}

3)查找操作

(1)按序号查找。算法思路：在链表结构中，只能从链表的头指针出发，顺着指针往下搜索，直至搜索结束。下面是在带头结点的单链表中查找第i个结点的算法：若找到第i个结点(1≤i≤n)，则返回这个结点的指针，否则返回NULL。

LinkList*get(inti；LinkList*head)

{

intj；

linklist*p；

j=0；

p=head；

while(j<i)&&(p->next!=NULL))

{

p=p->next；

j++；

}

if(j==i)

returnp；

else

returnNULL；

}

(2)按值查找。算法思路：从链表的头结点出发，顺着指针往下搜索，若搜索到给定的值，则返回第一个找到的结点的指针，否则返回NULL。

算法如下:

LinkList*locate(datatypex，LinkList*head)

{

LinkList*p；

p=head->next；

while(p!=NULL)

if(p->data==x)

returnp；

else

p=p->next；

returnNULL；

}

4)插入操作(在已知结点的后面插入新的结点)算法思想：假设要在线性表的两个数据元素a和b之间插入一个数据元素x，设指针p指向值为a的结点，指针s指向值为x的结点，在值为a的结点后面插入指针s指向值为x的结点时，需要改变两个结点的指针域，从而实现三个元素a、b和x之间逻辑关系的变化。在已知结点的后面插入新的结点时指针的变化情况如图2-10所示。图2-10在已知结点的后面插入新的结点时指针的变化情况算法如下：

voidinsertafter(datatypex，LinkList*p)

{

LinkList*s；

s=malloc(sizeof(LinkList))；

s->data=x；

s->next=p->next；

p->next=s；

}

5)删除操作(删除已知结点的后继结点)算法思想：如图2-11所示，在线性表中删除元素b时，为了在单链表中实现元素a、b和c之间逻辑关系的变化，仅需修改结点a中的指针域。假设p为指向结点a的指针，则修改指针的语句为

p->next＝p->next->next图2-11在单链表中删除结点时指针的变化情况算法如下：

intdeleteafter(LinkList*p)

{

LinkList*t；

intr=1；

if(p->next!=NULL)

{

t=p->next；

p->next=t->next；

free(t)；

}

else

r=0；

returnr；

}由此可见，若已知链表中元素插入或删除的确切位置，则在单链表中插入或删除一个结点时，仅需修改指针而不需要移动元素。容易看出，在已知结点的后面插入新的结点算法和删除已知结点的后继结点算法的时间复杂度均为O(n)。这是因为，在第i-1个结点之后插入一个新结点或删除第i-1个结点，都必须首先找到第i-1个结点，即需修改指针的结点，从算法的实现中已经得知，它的时间复杂度为O(n)。在插入和删除算法中会引用到C语言中的两个标准函数malloc()和free()。执行p＝(LinkList)malloc(sizeof(LinkList))的作用是由系统生成一个LinkList型的结点，同时将该结点的起始位置赋给指针变量p；反之，执行free(q)的作用是由系统回收一个LinkList型的结点，回收后的空间可以备作再次生成结点时使用。因此，与顺序存储结构不同，单链表是一种动态结构。整个可用存储空间可为多个链表共同享用，每个链表占用的空间不能预先分配，而是由系统根据需求即时生成。因此，建立线性表链式存储结构的过程就是一个动态生成链表的过程，即从“空表”的初始状态起，依次建立各元素结点，并逐个插入链表。

3.应用举例

【例2-3】计算链表中结点的个数并打印其值。算法思想：计算链表中结点的个数并打印其值的操作就是通过从链表的头指针出发，顺着指针往下搜索，直到整个链表结束。算法如下：

voidcount(LinkList*head)

{

LinkList*p；

intn=0；

p=head->next；

while(p!=NULL)

{

printf(p->data);

p=p->next；

n=n+1；

}

}

【例2-4】如何将两个有序链表归并为一个有序链表。算法思想：假设头指针为La和Lb的单链表分别为线性表LA和LB的存储结构，现要归并La和Lb，得到单链表Lc。按照有序的顺序表合并的算法思想，需设立三个指针pa、pb和pc，其中pa和pb分别指向La表和Lb表中当前待比较插入的结点，而pc指向Lc表中当前最后一个结点。若pa->data≤pb->data，则将pa所指结点链接到pc所指结点之后，否则将pb所指结点链接到pc所指结点之后。显然，指针的初始状态为：当La和Lb为非空表时，pa和pb分别指向La和Lb表中第一个结点，否则为空；pc指向空表Lc中的头结点。由于链表的长度是隐含的，因此第一个循环执行的条件是pa和pb皆非空，当其中一个为空时，说明有一个表的元素已归并完，这种情况下只要将另一个表的剩余段链接在pc所指结点之后即可。由此可得归并两个单链表的算法如下：

voidMergeList(LinkList*La，linkList*Lb，LinkList*Lc)

{

pa=La->next；

pb=Lb->next；

Lc=pc=La；

while(pa&&pb)

{

if(pa->data<=pb->data)

{

pc->next=pa；

pc=pa；

pa=pa->next；

}

else

{

pc->next=pb；

pc=pb；

pb=pb->next；

}

}

pc->next=(pa!=NULL?)pa：pb；

free(La)；

free(Lb)；

}由此容易看出，单链表下的归并算法和顺序表下的归并算法其时间复杂度相同，但空间复杂度不同。在归并两个链表为一个链表时，不需要另建新表的结点空间，只需将原来两个链表中结点之间的关系解除，重新按元素值非递减的关系将所有结点链接成一个链表即可。

4.线性表的顺序存储结构与链式存储结构的比较

线性表的顺序存储结构和链式存储结构各有优点和缺点，应根据具体的问题选择合适的存储结构。下面是二者在空间性能和时间性能上的比较。

(1)空间性能上的比较。顺序表的存储空间是静态分配的，链表的存储空间是动态分配的。在预先难以确定长度的情况下，最好使用链表作为存储结构。因为链表中的每个结点除了存储数据外还要存储指针域，所以当线性表的长度变化不大时，采用顺序存储结构比较节省存储空间。

(2)时间性能上的比较。顺序表是一种随机存储结构，而链表中的元素只能按照头指针顺着链表扫描才能取得，因此，若线性表上的操作主要是查找、读取而很少进行插入和删除操作，则采用顺序存储结构为宜。在顺序表中进行插入和删除操作时平均要移动近一半的元素，而在链表中进行插入和删除操作时只需要修改指针即可，因此，在频繁地进行插入和删除操作的情况下，采用链表比较适宜。2.1.4栈和队列

1.栈栈(stack)是限定仅在表尾进行插入或删除操作的线性表。因此，对栈来说，表尾端有其特殊含义，称为栈顶(top)，相应地，表头端称为栈底(bottom)。不含元素的空表称为空栈。假设栈S＝(a1，a2，…，an)，则称an为栈底元素，a1为栈顶元素。栈中元素按a1，a2，…，an的次序进栈，退栈的第一个元素应为栈顶元素。换句话说，栈的元素操作是按后进先出的原则进行的，如图2-12所示。因此，栈又称为后进先出(FirstInLastOut)的线性表(简称FILO)。图2-12栈的示意图栈可以进行以下基本操作。

(1)初始化：将栈初始化为空栈。

(2)判空：若栈为空栈，则函数的返回值为“真”，否则为“假”。

(3)进栈：在栈顶插入一个新的元素。

(4)出栈：删除栈顶元素。

(5)取栈顶元素：得到栈顶元素的值。

1)顺序栈——栈的顺序存储表示和实现顺序栈即采用顺序存储结构的栈，它利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。通常用top＝0表示空栈。由于C语言中数组的下标约定从0开始，因此当以C语言作描述语言时，如此设定会带来很大不便；另一方面，栈在使用过程中所需最大空间的大小很难估计。以下为顺序栈的类型说明。

typedefstruct{DataTypedata［maxsize］；

inttop；

}SeqStack；在C语言中，采用数组来存储栈中的数据元素，栈底定在一端，栈底的位置固定不变；栈顶是变的，top指示栈顶位置。鉴于C语言中数组的下标约定从0开始，为了方便描述顺序栈，可以约定向量中的0单元空闲不用，则top既为栈顶元素的下标又指栈中元素的个数，当top为数组最大值减1时，栈满。按照上面的约定，当栈空的时候，栈顶指针top的位置如图2-13(a)所示；当b入栈的时候，栈顶指针top的位置如图2-13(b)所示；当k元素入栈时，栈里的元素达到最大值，即栈满，如图2-13(c)所示；当一元素入栈时，无法入栈，发生溢出现象，如图2-13(d)所示；当k元素出栈时，栈顶指针top指向e元素，如图2-13(e)所示。图2-13入栈和出栈操作时栈顶指针top的变化下面是顺序栈上实现基本操作时对应的算法。

(1)初始化。算法思想：此操作的作用是将栈初始化为空栈。因为栈顶指针top也可以表示栈中元素的个数，所以可以将top置为0来表示空栈。具体算法如下：

voidIniStack(SeqStack*s)

{s->top=0；

}

(2)判空。算法思想：若栈为空栈，即栈顶指针top为0，则函数的返回值为“真”，否则为“假”。具体算法如下：

intempty(SeqStack*s)

{

if(s->top==0)

return1；

else

return0；

}

(3)进栈。算法思想：在栈顶插入一个新的元素，此时，栈顶指针向上移动1个位置。具体算法如下：

intPush(SeqStack*s，DataTypex)

{

if(s->top==maxsize-1)

{

printf(″overflow″)；

return0；

}

else

{

s->top++；

(s->data)［s->top］=x；

return1；

}

}

(4)出栈。算法思想：删除栈顶元素，通过栈顶指针减1来实现。具体算法如下：

Pop(SeqStack*s)

{DataTypex；

if(empty(s))printf(″underflow″)；

elses->top--；

}

(5)取栈顶元素。算法思想：得到栈顶元素的值。此算法与出栈操作的区别在于栈顶指针没有发生变化，栈中的元素也没有发生变化。具体算法如下：

DataTypeGetTop(SeqStack*s)

{DataTypex，XX=#；//#为特殊值，表示空元素

if(empty(s))

{

printf(″underflow″)；

x=XX；

}

else

x=(s->data)［s->top］；

returnx；

}

2)链栈-栈的链式存储表示和实现若栈中元素的数目变化范围较大或不清楚栈元素的数目，则应该考虑使用链式存储结构。人们将用链式存储结构表示的栈称做“链栈”。由于栈的插入和删除操作只能在一端进行，而对于单链表来说，在首端插入、删除结点要比尾端相对容易一些，因此，将单链表的首端作为栈顶端，即将单链表的头指针作为栈顶指针。由于只能在链表的头部进行操作，因此没有必要附加头结点，通常用一个无头结点的单链表来表示。下面是链栈的数据类型描述。

typedefstructsnode{DataTypedata；

structsnode*next；

}LinkStack；图2-14所示为链栈示意图。通过语句LinkStack*top定义了一个栈顶指针top，top能唯一地确定一个链栈。当top=NULL时，该链栈为空栈，链栈没有栈满的问题。图2-14链栈示意图

(1)初始化。算法思想：此操作的作用是将栈初始化为空栈，只需将栈顶指针top