1、数据结构 第一章绪论 第二章线性表 第三章数组和广义表 第四章栈和队列 第五章串 第六章树 第七章图 第八章查找 第九章排序第一章 绪论本章学习要求：了解数据结构的研究内容。理解掌握数据结构的基本概念和术语。了解数据元素间的结构关系。理解掌握算法及算法的描述1.1 数据结构的发展数据结构的发展1.1.1数据结构的发展简史最早对这一发展作出杰出贡献的是D.E.Kunth教授和C.A.R.Hoare(霍尔)。D.E.Kunth的计算机程序设计技巧和霍尔的数据结构札记对数据结构这门学科的发展作出了重要贡献。随着计算机科学的飞速发展，到20世纪80年代初期，数据结构的基础研究日臻成熟，已经成为一门完整
2、的学科。1.1.2数据结构的研究内容 用计算机解决一个具体的问题时，大致需要经过以下几个步聚：（1）分析问题，确定数据模型。（2）设计相应的算法。（3）编写程序，运行并调试程序直至得到正确的结果。例例1.1 学生成绩表学号姓名高数数据结构8201001李红89908201002杜刚958782010040刘珊8786一 个 数 据元素数据项例例1.2组织示意图 学院教务处学生处总务处图书馆电教中心团委财务科后勤中心例例1.3七桥问题Euler在1736年访问俄罗斯的哥尼斯堡时，他发现当地的居民正从事一项非常有趣的消遣活动。哥尼斯堡城中有一条名叫勒格尔的河流横经其中，在河上建有七座桥如图所示：A
3、DBC这项有趣的消遣活动是在星期六作一次走过所有七座桥的散步，每座桥只能经过一次而且起点与终点必须是同一地点。设四块陆地分别为A、B、C、D，Euler把每一块陆地考虑成一个点，连接两块陆地的桥以线表示，便得到如下的图形：ADCB1327645后来推论出此种走法是不可能的。他的论点是这样的，除了起点以外，每一次当一个人由一座桥进入一块陆地（或点）时，他（或她）同时也由另一座桥离开此点。即每个点如果有进去的边就必须有出来的边，因此每一个陆地与其他陆地连接的桥数必为偶数。七桥所成的图形中，没有一点含有偶数条数，因此上述的任务是不可能实现的。1.2 数据结构的基本概念和术语 数据数据（data）：是
4、指在计算机科学中能够被计算机输入、存储、处理和输出的一切信息，是计算机处理的信息的某种特定的符号表示形式。包括数字、英文、汉字、以及表示图形、声音、光和电的符号等。数据项数据项(Data Item)：是数据的最小单位，有时也称为域（field），即数据表中的字段。数据项是具有独立含义的不可分割的最小标识单位。1.2 数据结构的基本概念和术语 数据元素数据元素(Data Element)：是数据的基本单位，在计算机信息处理中通常作为一个整体来考虑。一个数据元素可以由若干个数据项组成，数据元素也称为元素、结点、顶点、记录。数据对象(Data Object)：具有性质相同的数据元素的集合，是数据的一
5、个子集。如整数数据对象是集合N=0,1,2,。1.2 数据结构的基本概念和术语 数据类型：数据类型：是一个值的集合和定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合：值的集合和操作集合。其中值的集合定义了该类型数据元素的取值，操作集合定义了该类型数据允许参加的运算，例如C语言中的int类型，取值范围是-3276832767，主要的运算为加、减、乘、除、取模、乘方等。数据结构数据结构(Data Structure)：带结构的数据元素的集合，描述了一组数据元素及元素间的相互关系。数据元素间的关系包括三个方面：数据的逻辑结构、存储结构和操作集合。1.2 数据结构的基本概念和术语 数据类型
6、：数据类型：是一个值的集合和定义在这个值集合上的一组操作的总称。数据类型中定义了两个集合：值的集合和操作集合。其中值的集合定义了该类型数据元素的取值，操作集合定义了该类型数据允许参加的运算，例如C语言中的int类型，取值范围是-3276832767，主要的运算为加、减、乘、除、取模、乘方等。数据结构数据结构(Data Structure)：带结构的数据元素的集合，描述了一组数据元素及元素间的相互关系。数据元素间的关系包括三个方面：数据的逻辑结构、存储结构和操作集合。1.3 数据的逻辑结构 逻辑结构（逻辑结构（logical structure）：）：是指数据元素之间的逻辑关系，是用户使用需要建
7、立起来的数据组织形式，是独立于计算机的。根据数据元素之间的不同关系，有以下四种基本逻辑结构：（1）线性结构：结构中的数据元素之间是一对一的关系。在线性结构中，有且仅有一个开始结点和一个终端结点，除了开始结点和终端结点，其余结点都有且仅有一个直接前趋和一个直接后继。1.3 数据的逻辑结构（2）树状结构或层次结构：数据元素之间存在着一对多的关系。比如部门之间的隶属关系、人类社会的父子关系、上下级关系等。在树形结构中，除根结点之外，每个结点都有唯一直接前趋，所有的结点都可以有0个或多个直接后继。1.3 数据的逻辑结构（3）图形结构或网状结构：结构中的数据元素之间存在着多对多的关系。在图状结构中，每个
8、结点都可以有多个直接前趋和多个直接后继。（4）集合结构：数据元素间除了同属于一个集合的关系外，无任何其他关系。1.3 数据的逻辑结构 一个数据结构的逻辑结构G可以用二元组来表示：G=（D，R）其中：D是数据元素的集合；R是D上所有数据元素之间关系的集合（表示各元素的前趋、后继关系）。R中的关系圆括号表示是双向的，尖括号表示是单向的。例例1-4一种数据结构Graph=（D，R）其中：D=A，B，C，D，E R=r r=(A,B),(A,C),(B,C),(B,D),(B,E),(C,E)r中的(A,B)表示顶点A到顶点B之间的边是双向的，上述的结构关系如图1-5所示。ADCBE1.4数据的存储结
9、构 数据的存储结构(storage structure)又称物理结构，是数据的逻辑结构在计算机存储器中的存储形式（或称映象）。（1）顺序存储结构：顺序存储结构：借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系，可用一维数组描述。（2）链式存储结构：链式存储结构：借助指示元素存储地址的指针来表示数据元素之间的逻辑关系。可用指针描述，数据元素不一定存在地址的存储单元，存储处理的灵活性较大。（3）索引存储索引存储：是在原有存储数据结构的基础上，附加建立一个索引表，索引表中的每一项都由关键字和地址组成。采取索引存储的主要作用是为了提高数据的检索速度。（4）散列存储散列存储：是通过构造散列函数来
10、确定数据存储地址或查找地址的。1.5算法和算法的描述算法和算法的描述1.5.1 什么是算法1算法的的概念算法的的概念算法算法是为了解决某类问题而规定的一个有限长的操作序列，是对解题过程的准确而完整的描述。2算法的特性算法的特性一个算法一般具有以下特性：（1）输入：一个算法必须有0个或多个输入。这些输入取自于特定的对象的集合。它们可以使用输入语句由外部提供，也可以使用赋值语句在算法内给定。（2）确定性：算法的每一步都应确切地、无歧义地定义。对于每一种情况，需要执行的动作都应严格地、清晰地规定。（3）有穷性：一个算法无论在什么情况下都应在执行有穷步后结束。1.5算法和算法的描述算法和算法的描述（4
11、）可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（5）输出：一个算法应有一个或多个输出，输出的量是算法计算的结果。3.算法与程序的区别算法与程序的区别（1）算法代表了对问题的求解过程，而程序则是算法在计算机上的实现。算法用特写的程序设计语言来描述，就成了程序。（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。（3）一个算法必须在有穷步之后结束，一个程序不一定满足有穷性。（4）可行性：一个算法是能行的，即算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现的。（5）输出：一个算法应有一个或多个输出，输出的量是算法计算的结果。
12、3.算法与程序的区别算法与程序的区别（1）算法代表了对问题的求解过程，而程序则是算法在计算机上的实现。算法用特写的程序设计语言来描述，就成了程序。（2）程序中的指令必须是机器可执行的，而算法中的指令则无此限制。（3）一个算法必须在有穷步之后结束，一个程序不一定满足有穷性。1.5.2 算法设计的要求通常设计一个“好”的算法应考虑达到如下目标：（1）正确性：在合理的数据输入下，能在有限的运行时间内得到正确的结果。（2）可读性：程序可读性好，有助于人对算法的理解。（3）健壮性：当输入的数据非法时，算法应当恰当地作出反映或进行相应处理，而不是产生莫名奇妙的输出结果。并且，处理出错的方法不应是中断程序的
13、执行，而应是返回一个表示错误或错误性质的值，以便在更高的抽象层次上进行处理。（4）高效性：对同一个问题，执行时间越短，算法的效率越高。（5）低存储量：完成相同的功能，执行算法所占用的存储空间应尽可能的少。1.5.4 算法的描述 算法可以用流程图、自然语言、计算机程序语言或其他语言来描述，但描述必须精确地说明计算过程。在本书中算法是以函数形式描述，描述如下：类型标识符函数名（形式参数表）*算法说明语句序列 1.5.4 算法效率的评价 算法可以用流程图、自然语言、计算机程序语言或其他语言来描述，但描述必须精确地说明计算过程。在本书中算法是以函数形式描述，描述如下：类型标识符函数名（形式参数表）*算
14、法说明语句序列1时间复杂度（时间复杂度（Time Complexity）一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数(n)，算法的时间量度记作：T（n）=O(n)它表示随问题规模n的增大，算法执行时间的增长率和(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。1.5.4 算法效率的评价 算法可以用流程图、自然语言、计算机程序语言或其他语言来描述，但描述必须精确地说明计算过程。在本书中算法是以函数形式描述，描述如下：类型标识符函数名（形式参数表）*算法说明语句序列1时间复杂度（时间复杂度（Time Complexity）一般情况下，算法中基本操作重复执行的次数是问题
15、规模n的某个函数(n)，算法的时间量度记作：T（n）=O(n)它表示随问题规模n的增大，算法执行时间的增长率和(n)的增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。1.5.4 算法效率的评价 算法可以用流程图、自然语言、计算机程序语言或其他语言来描述，但描述必须精确地说明计算过程。在本书中算法是以函数形式描述，描述如下：类型标识符函数名（形式参数表）*算法说明语句序列1时间复杂度（时间复杂度（Time Complexity）一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数(n)，算法的时间量度记作：T（n）=O(n)它表示随问题规模n的增大，算法执行时间的增长率和(n)的
16、增长率相同，称做算法的渐近时间复杂度，简称时间复杂度。1.5.4 算法效率的评价 例1-5在下列的三个程序中(a)x=0 (b)for(i=1;i=n;i+)x=x+1 (c)for(i=1;i=n;i+)for(j=1;j=n;j+)X=X+i*j上述三个语句的频度分别为1，n,n22.空间复杂度空间复杂度（Space ComPlexity）一个程序的空间复杂度是指程序运行从开始到结束所需要的存储空间。包括算法本身所占用的存储空间、输入数据占用的存储空间以及算法在运行过程中的工作单元和实现算法所需辅助空间。第二章 线性表本章学习要求：系统学习线性表的存储结构及其基本操作。理解线性表的逻辑结构
17、 理解掌握线性表的顺序存储结构及操作 理解掌握线性表的链式存储结构及操作2.1线性表逻辑结构 2.1.1 线性表的定义1线性表的定义线性表的定义线性表（Linear List）是具有相同数据类型的数据元素的一个有限序列。通常表示为：（a1，a2，ai，ai+1 an）其中n为线性表的长度，n0；当n=0时表示一个空表。线性表相邻元素之间存在着顺序关系。a1叫表头元素，an叫表尾元素。除第一个和最后一个元素外，每个元素都只有一个前趋和一个直接后继。ai-1称为ai的直接前趋结点，ai+1称为ai的直接后继结点。表中的元素可以是一个数，也可以是由多个数据项组成的复杂信息，但线性表中的元素必须属于同
18、一数据对象。例如英文字母（A，B，.Y，Z）和在绪论中引入的学生成绩表表11。2线性表的二元组表示线性表的二元组表示线性表用二元组表示为：linear_list=(D，R)其中数据对象：D=ai|1in,n 0,aiElemType数据关系：R=r，r=|1in-1，对应的逻辑结构图如图2-1所示：图2-1线性表的逻辑结构图 a1a2aian2.1.2 线性表的基本操作线性表是一种简单灵活的数据结构，我们根据需要可以对线性表中的元素进行访问、插入和删除等操作，常用操作有以下几种：(1)创建线性表：创建线性表：InitList(L)初始条件：表不存在操作结果：构造一个空的线性表L。(2)求线性表
19、的长度：求线性表的长度：ListLength(L)初始条件：线性表L已存在。操作结果：返回L中元素个数。(3)查找线性表中的元素：查找线性表中的元素：GetElem(L,i)初始条件：线性表L已存在，1iLengthList(L)操作结果：用来返回L中第i个元素的值。2.1.2 线性表的基本操作(4)查找线性表中元素的位置查找线性表中元素的位置：LocateElem(L,x)初始条件：线性表L已存在 操作结果：返回L中查找值为x的数据元素，若查找成功，则返回值为x的那个元素在L中首次出现的的序号或地址，否则，在L中未找到值为X的数据元素，则返回值为特定值，表示查找失败。(5)插入操作：插入操作
20、：ListInsert(&L,i,x)初始条件：线性表L已存在，1iLengthList(L)+1操作结果：在L的第i个元素之前插入新的元素x，L的长度增1。(6)删除操作：删除操作：ListDelete(&L,i,&e)初始条件：线性表L已存在且非空，1iLengthList(L)操作结果：删除L的第i个元素，并用e返回其值，L的长度减1。2.2线性表的顺序存储结构线性表的顺序存储结构2.2.1 顺序存储结构线性表的顺序存储线性表的顺序存储是指用一组地址连续的存储单元依次存放线性表的数据元素，这种存储形式的线性表称为顺序表。它的特点是线性表中相邻的元素在内存中的存储位置也是相邻的。由于线性表
21、中的所有数据元素属于同一类型，所以每个元素在存储中所占的空间大小相同。如图2-2所示，如果第一个元素存放的位置为b，每个元素占用的空间大小为L，则顺序表中第i个数据元素ai的存储位置为：LOC（ai）=LOC（a1）+（i-1）*L,其中LOC（a1）是线性表的起始地址或基地址。即LOC（ai）=b+（i-1）*L在程序设计中，一维数组在内存中占用的存储空间就是一组连续的存储区域，因此在高级语言中讨论线性表的顺序存储结构，通常是利用数组来进行描述。由于对线性表需要进行插入和删除等操作，其长度是可变的。因此线性表的顺序结构可定义为：typedef structElemType elemMaxSi
22、ze;/*存储线性表中的元素*/int len;/*线性表的当前表长*/SqList;2.2.2 基本操作的实现 在线性表的顺序存储结构中，ListLength(L)等操作比较简单，在这里我们主要介绍以下几种操作。1插入插入线性表的插入是指在表的第i个位置上插入一个值为x的元素，线性表的逻辑结构由(a1，ai-1，ai，an)改变为(a1，ai-1，x，ai，an)，表长变为n+1。算法思想如下：（1）检查i值是否超出所允许的范围（1in+1），若超出，则进行“超出范围”错误处理；（2）否则，将线性表的第i个元素和它后面的所有元素均向后移动一个位置；（3）将新元素写入到空出的第i个位置上；（4
23、）使线性表的长度增加1。2.2.2 基本操作的实现具体算法：【算法算法2.1】int Insert_Sq(SqList*L,int i,ElemType x)/*在顺序线性表L的第i个元素之前插入新的元素x*/Int i,j;if(i L-len+1)return 0;/*不合理的插入位置*/if(L-len=L-MaxSize-1)return 1;/*表已满*/for(j=L-len;j=i;-j)L-elemj+1=L-elemj;L-elemi=x;+L-len;return 1Insert_Sq2.2.2 基本操作的实现 插入算法的时间性能分析：顺序表上的插入运算，时间主要消耗在数据
24、的移动上，在第i个位置上插入x，从an到ai都要向下移动一个位置，共需要移动n-il个元素，而i的取值范围为：1in+1，即n+1个位置可以插入。设在第i个位置上作插入的概率为pi，则平均移动数据元素的次数：Ein=1n1ii1)i-(np2.2.2 基本操作的实现 如果在表的任何位置插入元素的概率相等，即：pi=，则：Ein=因此在顺序表上做插入操作，平均约移动表中一半的元素，若表长为n，则上述算法的时间复杂度为O(n)。1n1ii1)i-(np11n1n1i1)i-(n2n2.2.2 基本操作的实现2 删除操作删除操作删除操作是指删除线性表中的第i个数据元素，线性表的逻辑结构由(a1，ai
25、-1，ai，ai+1，an)变成长度为n-1的(a1，,ai-1，ai+1，an)。算法思想如下：（1）检查i值是否超出所允许的范围（1in），若超出，则进行“超出范围”错误处理；（2）否则，将线性表的第i个元素后面的所有元素均向前移动一个位置；（3）使线性表的长度减1。具体算法如下：2.2.2 基本操作的实现【算法算法2.2】int Delete_Sq(SqList*L,int i)/*删除线性表中第i个元素*/if(i L-len)return 0;/*不合理的删除位置*/if(L-len=0)return 1;/*空表*/for(j=i;jlen-1;j+)/*被删除元素的后面元素向前移
26、*/L-elemj=L-elemj+1;-L-len;return 1;/*Delete_Sq*/2.2.2 基本操作的实现 删除算法的时间性能分析：与插入运算相同，其时间主要消耗在数据的移动上，删除第i个元素时，其后面的元素ai1到an都要向前移动一个位置，共需要移动n-i个元素，则平均移动数据元素的次数：Edel=n1iii)-(np2.2.2 基本操作的实现 3.按值查找按值查找线性表中的按值查找是指在线性表中查找与给定值x相等的数据元素。算法思想如下：（1）从第一个元素a1起依次和x比较，直至找到一个与x相等的数据元素，则返回它在顺序表中存储下标或序号。（2）如果没有找到，则返回1。2
27、.2.2 基本操作的实现具体算法如下：【算法算法2.3】int LocateElem(SqList*L,ElemType x)int i;for(i=0;ilen;i+)if(L-datai=x)return i;return(0)2.2.2 基本操作的实现上述算法的主要运算是比较，当a1=x时，需比较一次，若an=x时，比较n次成功。因此查找概率相等的情况下，平均比较次数为：:Eloc=所以上述算法的时间复杂度也为O(n)。n121nn1ii2.3线性表的链式存储结构 采用顺序存储方式的线性表，内存的存储密度高，可以节约存储空间，并可以随机地存取结点，但是插入和删除操作时往往需要移动大量的数
28、据元素，并且要预先分配空间，并要按最大空间分配，因此存储空间得不到充分的利用，从而影响了运行效率。线性表的链式存储结构，它能有效地克服顺序存储方式的不足，同时也能有效地实现线性表的扩充。2.3.1 单链表 线性表的链式存储结构是用一组地址任意的存储单元存放线性表中的数据元素。为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的值之外，还必须有一个指示该元素直接后继存储位置的信息，即指出后继元素的存储位置。这两部分信息组成数据元素ai的存储映像，称为结点（node）。每个结点包括两个域：一个域存储数据元素信息，称为数据域；另一个存储直接后继存储
29、位置的域称为指针域。指针域中存储的信息称做指针或链。N个结点链结成一个链表，由于此链表的每一个结点中包含一个指针域，故又称线性链表或单链表。2.3线性表的链式存储结构 单链表中结点的存储结构描述如下：typedefstructLnode ElemTypedata；Struct Lnode*next;Lnode;2.3线性表的链式存储结构 单链表的存储结构如图2-3所示。其中，H是一个指向LNode类型的指针变量，称为头指针。另外图2-3(a)中单链表的第一个结点之前还附设一个结点，称之为头结点，头结点的数据域可以不存储任何信息，也可存储如线性表的长度等附加信息，单链表的头指针指向头结点，头结点
30、的指针域指向第一个结点的指针，由于最后一个结点没有后继结点，它的指针域为空，用“”表示。若线性表为空表，则头结点的指针域为“空”，如图2-3(b)所示。2.3线性表的链式存储结构 (a)非空表 (b)空表 图2-3 线性表的单链表存储结构 H H2.3线性表的链式存储结构 在建立链表或向链表中插入结点时，应先按结点的类型向系统申请一个结点，系统给结点分配指针值，即该结点的首地址。可以通过调用C的动态分配库函数malloc，向系统申请结点。如有说明语句：LNode *p；调用函数malloc的形式为：p（LNode*）ma11oc（sizeof（LNode）,则p指向一个新的结点。结点的数据域用
31、 p-data来表示，指针域用 p-next来表示。使用时要注意区分结点和指向结点指针这两个不同的概念 2.3.2 基本操作的实现1.初始化链表操作初始化链表操作算法思想：初始化单链表，其结构形式如图2-3(b)所示。在初始状态，链表中没有元素结点，只有一个头结点，因此需要动态产生头结点，并将其后继指针置为空。算法如下：【算法2.4】Lnode Init_L()Lnode H;if(H=(LNnode*)malloc(sizeof(LNode)/*头结点*/H-next=NULL;return 1;/*设置后继指针为空*/else return 0;2.3.2 基本操作的实现2.取某序号元素的
32、操作取某序号元素的操作算法思想:在单链表中查找某结点时，需要设置一个指针变量从头结点开始依次数过去，并设置一个变量j，记录所指结点的序号。查找到则返回该指针值,否则返回空指针.具体算法如下:【算法2.5】Status GetElem_L(LNode*H,int i)p=H-next,j=1;while(p&jnext;+j;if(!p|ji)return NULL;return p;/*GetElem_L*/2.3.2 基本操作的实现3.插入操作插入操作在单链表中插入新结点，首先应确定插入的位置，然后只要修改相应结点的指针，而无须移动表中的其他结点。（1）在第i个位置插入一个新结点。算法思想如
33、下：1）从头结点开始向后查找，找到第i-1个结点；若存在继续2，否则结束。2）动态的申请一个新结点,赋给s结点的数据域值。3）将新结点插入。如在第三位置插入一个新结点操作示意图如图所示，具体算法如下：2.3.2 基本操作的实现【算法2.6】Status ListInsert_L1(LNode*H,int i,ElemType x)p=H,j=0;while(p&jnext;+j;if(!p|ji-1)return 0;s=(LNnode*)malloc(sizeof(LNode);s-data=x;s-next=p-next;p-next=s;return 1;/*ListInsert_L*/
34、2.3.2 基本操作的实现在第三个位置插入元素6i=311H238.pj=0p&ji-1为真21H238.pj=1p&ji-1为真31H238.j=2p&jnext;while(p&p-data!=x)/*寻找值为x的结点*/q=p;p=p-next;s=(LNnode*)malloc(sizeof(LNode);s-data=x;s-next=p;q-next=s;/*插入*/*Insert_L*/2.3.2 基本操作的实现4删除操作删除操作从链表中删除一个结点，首先应找到被删结点的前驱结点，然后修改该结点的指针域，并释放被删结点的存储空间。从链表中删除一个不需要的结点时，要把结点归还给系统
35、，用库函数free(p)实现。（1）删除单链表中的第i（i0）个元素。算法思想：设置一个指针p从第一个元素结点开始向后移动，当p移动到第i-1个结点时，另设一个指针q指向p的后继结点。使p的后继指针指向q的后继指针，即可完成删除操作。如删除第二个结点元素，操作如图2-5所示,具体算法如下 2.3.2 基本操作的实现【算法2.8】Status ListDelete_L(LNode*H,int i,ElemType&e)p=H,j=0;while(p&jnext;+j;if(!p-next|ji-1)return0;q=p-next;p-next=q-next;e=q-data;free(q);r
36、eturn 1;/*ListDelete_L2.3.2 基本操作的实现删除第二个结点元素11H238.pj=0p&ji-1为真21H238.pj=1p&jnextp-next=q-nextpfree(q)图2-5删除结点 2.3.2 基本操作的实现(2)删除链表中所有值为x的结点，并返回值为x的结点的个数。算法思想：操作时设指针p从第一个元素结点起逐一查找值为x的结点，并设一个辅助指针q始终指向它的前趋结点，每找到一个结点便进行删除，同时统计被删除结点的个数。具体算法如下：【算法2.9】int Delete_Linkst(LNode*H,ELEMTP X)q=H;count=0;while(q
37、-next)/*遍历整个链表*/p=q-next;if(p-data=x)q-next=p-next;free(p);+count;else q=p;return count;/*delete_Linkst*/2.3.2 基本操作的实现从以上的查找、插入、删除算法可知，这些操作都是从链表的头结点开始，向后查找插入、删除的位置，然后进行插入、删除。所以，如果表长是n，则上述算法的时间复杂度为O(n)。2.3.3 循环链表 循环链表是另一种形式的链式存储结构。在线性表中，每个结点的指针都指向其下一个结点，最后一个结点的指针为“空”，不指向任何地方，只表示链表的结束。若把这种结构修改一下，使其最后一
38、个结点的指针回指向第一个结点，这样就形成了一个环，这种形式的链表就叫做循环链表。如图2-6所示。(a)非空表 (b)空表 图2-6单向循环链表a1H.a2anH2.3.3 循环链表 循环单链表的操作与线性表类似，只是有关表尾、表空的判定条件不同。在采用头指针描述的循环链表中，空表的条件是head-next=head，指针p到达表尾的条件是 p-next=head。因此循环链表的插入、删除、建立、查找等操作只需在线性链表的算法上稍加修改即可。在循环链表结构中从表中任一结点出发均可找到表中的其他结点。如果从表头指针出发，访问链表的最后一个结点，必须扫描表中所有的结点。若把循表的表头指针改用尾指针代
39、替，则从尾指针出发，不仅可以立即访问最后一个结点，而且也可十分方便地找到第一个结点，如图27所示。设rear为循环链表的尾指针，则开始结点a1的存储位置可用 rear-next-next表示 2.3.3 循环链表 在实际应用中，经常采用尾指针描述的循环链表，例如，将两个循环链表首尾相接时合并成一个表，采用设置尾指针的循环链表结构来实现，将十分简单、有效。操作过程如图2-8所示，有关的操作语句如下 p=rb-next;rb-next=ra-next;ra-next=p-next;free(p);ra=rb;a1.a2anrear图2-7 设尾指针的循环链表 2.3.3 循环链表 图2-8循环链表
40、合并示意图2.3.4 双向链表 在单链表中，从任何一个结点通过指针域可找到它的后继结点，但要寻找它的前趋结点，则需从表头出发顺链查找。因此对于那些经常需要既向后查找又向前查找的问题，采用双向链表结构，将会更方便。在双向链表结构中，每一个结点除了数据域外，还包括两个指针域，一个指针指向该结点的后继结点，另一个指针指向它的前趋结点。结点结构如图2-9(a)所示，双向链表也可以是循环表，其结构如图2-10(b)所示。2.3.4 双向链表 a1.anH.NextDataPrior(a)结点结构 （b)非空的双向链表图2-9双向循环链表示意图2.3.4 双向链表 双向链表的结点结构可描述如下：typed
41、ef struct dunode ElemType data;struct dunode *prior,*next;Dunode;双向链表由于可以从两个方向搜索某个结点，这使得链表的某些操作变得比较简单，本节主要介绍以下几种操作：1插入在双向链表的指定结点p之前插入一个新的结点。如图2-10所示，算法思想：（1）生成一个新结点s，将值x赋给s的数据域。（2）将p的前驱结点指针作为s的前驱结点指针。（3）p作为新结点的直接后继。（4）s作为结点的直接前驱的后继。（5）s作为p结点新的直接前驱。2.3.4 双向链表 acpb.2413s图2-10在双向链表中插入一个结点 具体算法如下：【算法2.1
42、0】void ListInsert_Dul(Dunode*p,ElemType x)Dunode*s;s=(Dunode*)malloc(sizeof(Dunode);s-data=x;s-prior=p-prior;s-next=p;p-prior-next=s;p-prior=s;2.3.4 双向链表2删除：在双向链表中删除p结点，如图2-11所示，主要操作步骤如下：p-prior-next=p-next;p-next-prior=p-prior;free(p);图2-11在双向链表中删除一个结点abp.c.122.4 线性表的应用线性表的应用-多项式相加问题多项式相加问题 多项式的相加操
43、作是线性表处理的典型例子。在数学上，一个多项式可写成下列形式：P（x）a0 x0a1x1+anxn 其中ai为xi的非零系数。在多项式相加时，至少有两个或两个以上的多项式同时并存，而且在实现运算的过程中所产生的中间多项式和结果多项式的项数和次数都是难以预料的。因此计算机实现时，可采用单链表来表示。多项式中的每一项为单链表中的一个结点，每个结点包含三个域：系数域、指数域和指针域，其形式如下：coefexpnext结点结构描述为：type struct pnode int coef;/*系数域*/int exp;/*指数域*/struct pnode*next/*指针域*/2.4 线性表的应用线性
44、表的应用-多项式相加问题多项式相加问题 多项式相加的运算规则为：两个多项式中所有指数相同的项，对应系数相加，若和不为零，则构成“和多项式”中的一项，否则，“和多项式”中就去掉这一指数项，所有指数不同的项均复制到“和多项式”中。如对于多项式A(x)=5x5+8x4+4x2-8，B(x)=6x10+4x5-4x2。实现时，可采用另建多项式的方法，也可以把一个多项式归并到另一个多项式中去的方法。这里介绍后一种方法。算法思想：首先设两个指针qa和qb分别从多项式的首项开始扫描。比较qa和qb所指结点指数域的值，可能出现下列三种情况之一：（1）qa-exp大于qb-exp，则qa继续向后扫描。(2)qa
45、-exp等于qb-exp ，则将其系数相加。若相加结果不为零，将结果放入qacoef中，否则同时删除qa和qb所指结点。然后qa、qb继续向后扫描。（3）qa-exp小于qb-exp，则将qb所指结点插入qa所指结点之前，然后qa、qb继续向后扫描。扫描过程一直进行到qa或qb有一个为空为止，然后将有剩余结点的链表接在结果链表上。所得Ha指向的链表即为两个多项式之和。操作过程见图2-13所示。55840-842Ha610452-4Hbpreqaqb95840-842Ha610452-4Hbpreqaqb已删除95840-8Ha610Hb（1）（2）（3）图2-13多项式相加示意图 下面是多项式
46、相加算法：【算法2.11】void polyadd(pnode*Ha,pnode*Hb)/*以Ha和Hb为头指针的单链表分别表示两个多项式，实现Ha=Ha+Hb*/pnode*pre,*qa,*qb,*q;int sum;pre=Ha;/*pre始终指向当肖和多项式的最后一个结点*/qa=Ha-next;qb=Hb-next;while(qa&qb)/*指数相同*/if(qa-exp=qb-exp)sum=qa-coef+qb-coef;if(sum)qa-coef=sum;pre=qa;else/*系数和为零*/pre-next=qa-next;free(qa);qa=pre-next;q=
47、qb;qb=qb-next;free(q);else/*指数不相同*/if(qa-expqb-exp)pre=qa;qa=qa-next;else pre-next=qb;pre=qb;qb=qb-next;pre-next=qa;if(qb)pre-next=qb;/*链接pb中剩余结点*/free(Hb);/*释放Hb头结点*/本章小结 线性表是一种最基本、最常用的数据结构。本章主要介绍了线性表的定义、运算和线性表的两种存储结构顺序表和链表，以及在这两种存化结构上实现的基本运算。顺序表是用数组实现的，链表是用指针实现的。用指针来实现的链表，结点空间是动态分配的，链表又按链接形式的不同，区分
48、为单链表、双链表和循环链表。建议读者熟练掌握在顺序表和链表上实现的各种基本运算及其时间、空间特性。习题2 一 选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为4,则第5个元素的地址是()A.110 B.116 C.100 D.120 2.向一个有128个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。A.64 B.63 C.63.5D.73在循环双链表的p所指接点之前插入s所指接点的操作是 A.p-prior=s;s-next t=p;p-prior t-left=s;s-prior=p-prior;B.p-prior=s;p-prior-next=s;
49、s-next=p;s-prior=p-prior;C.s-next=p;s-prior=p-prior;p-prior=s;p-prior-next=s;D.s-next=p;s-prior=p-prior;p-prior-next=s;p-prior=s;4从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较（）个结点。A.n B.n/2 C.(n-1)/2 D.(n+1)/25线性表是具有n个（）的有限序列（n0）A.表元素 B.字符 C.数据元素 D.数据项6非空的循环单链表head的尾结点（由P指向）满足A.p-next=NULL B.p=NULLC.p-n
50、ext=head D.p=head7在一个单链表中已知q所指的结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行()A.s-next=p-next;p-next=s;B.p-next=s-next;s-next=p;C.q-next=s;s-next=p;D.p-next=s;s-next=q;习题2 8已知一个顺序存储线性表，若第1个结点的地址d，第3个的地址是5d，则第n个结点的地址为()A2*(n-1)+1*d B.2*(n-1)*d C.2*(n-1)-1*d D.(n+1)*d9在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()A.O(1)B.O(n
