1、2022-9-121（C语言版语言版）2022-9-1222022-9-123第第1 1章章 绪论绪论2022-9-1241.1 什么是数据结构什么是数据结构2022-9-125 2022-9-126返回返回返回返回登录号登录号书号书号书名书名作者作者出版社出版社定价定价1ISBN 7-302-02368-9/TP1185 数据结构数据结构严蔚敏严蔚敏 清华大学清华大学222ISBN 7-302-00860-4/TP312 C 程序设计程序设计谭浩强谭浩强 清华大学清华大学17.33ISBN 7-5053-9279-4 /TP311 数据结构数据结构徐孝凯徐孝凯 电子工业电子工业294ISBN
2、 7-5053-8168-7/TP4757 计算机系统原理计算机系统原理张基温张基温 电子工业电子工业255ISBN 7-5609-2351-8/TP316 操作系统原理操作系统原理庞丽萍庞丽萍 华中科技大学华中科技大学22.86ISBN 7-304-01404-0/TP68 数据库基础与应用数据库基础与应用王王 利利 中央电大中央电大23.37ISBN 7-5084-1648-1/TP706 网页制作实例教程网页制作实例教程齐建玲齐建玲 中国水利水电中国水利水电20表表 1-1 图书目录表图书目录表2022-9-127 binrootlibuseretcmathdszhaojiang sha
3、oliqueuetree graphstacksw2022-9-128课程编号 课程名称 先修课程 C1 计算机导论 无 C2 数据结构 C3 汇编语言 C4 C 程序设计 C5 计算机图形学 C6 接口技术 C7 数据库原理 C8 编译原理 C9 操作系统C1，C4C2C1C1C2，C3，C4C3C2，C9C4C1C3C6C5C2C4C9C8C7C12022-9-129 通过以上几例可以认为：数据结构就是研究数据的逻辑结构通过以上几例可以认为：数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，并对这种结构定义相应的运和物理结构以及它们之间相互关系，并对这种结构定义相应的运算，而且
4、确保经过这些运算后所得到的新结构仍然是原来的结构算，而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。类型。2022-9-12101 1数据数据(Data)Data)数据数据(Data)：是对信息的一种符号表示。在计算机科学中是指所是对信息的一种符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。包括有能输入到计算机中并被计算机程序处理的符号的总称。包括等。等。数据元素数据元素(Data Element)：是数据的基本单位，在计算机程序中是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据
5、项组成。数据项是数据的不可分一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。割的最小单位。2022-9-1211 数据对象数据对象(Data Object)：是性质相同的数据元素的集合。是数据是性质相同的数据元素的集合。是数据的一个子集。的一个子集。数据结构数据结构(Data Structure)：是相互之间存在一种或多种特定关系是相互之间存在一种或多种特定关系的数据元素的集合。的数据元素的集合。2022-9-12122022-9-1213 数据结构主要指逻辑结构和物理结构。数据结构主要指逻辑结构和物理结构。数据之间的相互关系称为逻辑结构。通常分为数据之间的相互关系称为逻辑
6、结构。通常分为 类基本结构：类基本结构：结构中的数据元素除了同属于一种类型外，别无其它关系。结构中的数据元素除了同属于一种类型外，别无其它关系。结构中的数据元素之间存在一对一的关系。结构中的数据元素之间存在一对一的关系。结构中的数据元素之间存在一对多的关系。结构中的数据元素之间存在一对多的关系。结构中的数据元素之间存在多对多的关系。结构中的数据元素之间存在多对多的关系。2022-9-12142022-9-1215 2022-9-1216 数据对象可以是有限的，也可以是无限的。数据对象可以是有限的，也可以是无限的。数据结构不同于数据类型，也不同于数据对象，它不仅要描述数据类型的数据数据结构不同于
7、数据类型，也不同于数据对象，它不仅要描述数据类型的数据对象，而且要描述数据对象各元素之间的相互关系。对象，而且要描述数据对象各元素之间的相互关系。2022-9-12172022-9-12182022-9-12192022-9-12202022-9-12212022-9-1222 1.2 算法描述算法描述 2022-9-12232022-9-1224 2022-9-12252022-9-12262022-9-1227 1.3 算法分析与评价算法分析与评价 2022-9-12282022-9-12292022-9-12301数据结构研究的是数据的表示和数据之间的关系。从逻辑上数据结构研究的是数据的
8、表示和数据之间的关系。从逻辑上讲，数据有集合、线性、树和图四种结构。从存储结构上讲，讲，数据有集合、线性、树和图四种结构。从存储结构上讲，数据有顺序结构、链接结构、索引结构和散列结构四种。理论数据有顺序结构、链接结构、索引结构和散列结构四种。理论上，任一种数据逻辑结构都可以用任一种存储结构来实现。上，任一种数据逻辑结构都可以用任一种存储结构来实现。2在集合结构中，数据处于无序的、各自独立的状态；在线性在集合结构中，数据处于无序的、各自独立的状态；在线性结构中，数据之间是结构中，数据之间是1对对1的关系；在树结构中，数据之间是的关系；在树结构中，数据之间是1对对多的关系；在图结构中，数据之间是多
9、对多的关系。多的关系；在图结构中，数据之间是多对多的关系。3就存储结构而言，一个数组占有一片连续的存储空间，每个就存储结构而言，一个数组占有一片连续的存储空间，每个元素的物理存储单元是按下标位置从元素的物理存储单元是按下标位置从0开始连续编号的，相邻元开始连续编号的，相邻元素之间其存储位置也相邻。对于任一种数据的逻辑结构，若能素之间其存储位置也相邻。对于任一种数据的逻辑结构，若能够把元素之间的逻辑关系对应地转换为数组下标位置之间的物够把元素之间的逻辑关系对应地转换为数组下标位置之间的物理关系，则就能够利用数组来实现其顺序存储结构。理关系，则就能够利用数组来实现其顺序存储结构。2022-9-12
10、314抽象数据类型是数据和对数据进行各种操作的集合体。这抽象数据类型是数据和对数据进行各种操作的集合体。这里所说的数据是广义的，是带有结构的数据，它可以具有任何里所说的数据是广义的，是带有结构的数据，它可以具有任何逻辑结构和存储结构。逻辑结构和存储结构。5算法的评价指标主要为正确性、健壮性、可读性和有效性算法的评价指标主要为正确性、健壮性、可读性和有效性四个方面。有效性又包括时间复杂度四个方面。有效性又包括时间复杂度(性性)和空间复杂度和空间复杂度(性性)两个两个方面。一个算法的时间和空间复杂度越好，就越节省时间和空方面。一个算法的时间和空间复杂度越好，就越节省时间和空间，则表明该算法越有效。
11、间，则表明该算法越有效。6算法的时间复杂度和空间复杂度通常用数量级的形式表示算法的时间复杂度和空间复杂度通常用数量级的形式表示出来。数量级的形式可分为常量级，对数级、线性级、平方级、出来。数量级的形式可分为常量级，对数级、线性级、平方级、立方级等多个级别。当数据处理量较大时，处于前面级别的算立方级等多个级别。当数据处理量较大时，处于前面级别的算法比处于后面级别的算法更有效。法比处于后面级别的算法更有效。2022-9-12322022-9-1233 线性表 2022-9-1234 常常将非空的线性表常常将非空的线性表(n0)记作：记作：(a1，a2，an)这里的数据元素这里的数据元素 ai(1i
12、n)只是一个抽象的符号，其具体含只是一个抽象的符号，其具体含义在不同的情况下可以不同。义在不同的情况下可以不同。2022-9-1235例例1、26个英文字母组成的字母表个英文字母组成的字母表 （A，B，C、Z）例例2、从、从1978年到年到1983年各种型号的计算机拥有量的变化情况。年各种型号的计算机拥有量的变化情况。（6，17，28，50，92，188）例例3、2022-9-1236从以上例子可看出线性表的逻辑特征是：从以上例子可看出线性表的逻辑特征是：在非空的线性表，有且仅有一个开始结点在非空的线性表，有且仅有一个开始结点a1，它没有直接它没有直接前趋，而仅有一个直接后继前趋，而仅有一个直
13、接后继a2；有且仅有一个终端结点有且仅有一个终端结点an，它没有直接后继，而仅有一个它没有直接后继，而仅有一个直接前趋直接前趋a n-1；其余的内部结点其余的内部结点ai(2in-1)都有且仅有一个直接前趋都有且仅有一个直接前趋a i-1和和一个直接后继一个直接后继a i+1。线性表是一种典型的线性结构。线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。是在存储结构上进行的。2022-9-12372 线性表的基本运算 2022-9-1238。2022-9-1239 1.线性表的顺序存储结构 20
14、22-9-12402022-9-12412022-9-12422022-9-1243 这样，一个线性表的顺序存储结构需要两个分量。为体现数组这样，一个线性表的顺序存储结构需要两个分量。为体现数组data和和length之间的内在联系，通常将它们定义在一个结构类型中。之间的内在联系，通常将它们定义在一个结构类型中。此处的元素类型用此处的元素类型用ElemType来表示。来表示。综上所述，综上所述，在在C C语言中，可用下述类型定义来描述顺序表：语言中，可用下述类型定义来描述顺序表：#define MaxLen 100 /线性表的容量线性表的容量 typedef int ElemType /在实际
15、应用中，将在实际应用中，将ElemType定义成实际类型定义成实际类型 typedef struct ElemType dataMaxLen;/定义存储表中元素的数组定义存储表中元素的数组 int length;/线性表的实际长度线性表的实际长度 sqList;sqList L;/定义表结构的变量定义表结构的变量2022-9-1244 本节将讨论采用顺序存储结构之后，如何实现线性表的基本运本节将讨论采用顺序存储结构之后，如何实现线性表的基本运算，并讨论各算法时间复杂度。算，并讨论各算法时间复杂度。1初始化顺序表初始化顺序表initlist(L)的实现的实现 顺序表的初始化即构造一个空表，顺序表
16、顺序表的初始化即构造一个空表，顺序表L是否为空取决于其是否为空取决于其元素个数是否为元素个数是否为0，因此，只要将表，因此，只要将表L中的表长度置为中的表长度置为0，就可以实，就可以实现建空表的功能。现建空表的功能。void initlist(sqList*L)L-length=0;2求线性表长度求线性表长度Getlen(L)的实现的实现 求线性表的长度算法如下：求线性表的长度算法如下：int Getlen(sqList*L)return L-length;该算法的时间复杂度为该算法的时间复杂度为O(1)2022-9-12453按序号取元素按序号取元素Getelem(L,i)的实现的实现 按前
17、面的约定，序号为按前面的约定，序号为i的元素存储在数组下标为的元素存储在数组下标为i-1的数组的数组元素中，所以可直接从该数组元素中取得值。元素中，所以可直接从该数组元素中取得值。i的有效值应大的有效值应大于等于于等于1和小于等于线性表的实际长度。和小于等于线性表的实际长度。ElemType Getelem(sqLlist*L,int i)if(iL-length)printf(“error”);exit(1);return L-datai-1;4查找运算查找运算locate(L,x)的实现的实现要 确定值为确定值为x的元素在的元素在L表中的位置，需要依次比较各元素。当表中的位置，需要依次比较
18、各元素。当查询到第一个满足条件的数据元素时，返回其序号，否则返回查询到第一个满足条件的数据元素时，返回其序号，否则返回0，表示查找失败。，表示查找失败。2022-9-1246查找操作的具体实现算法如下：查找操作的具体实现算法如下：int Locate(sqList*L,ElemType x)int i;i=0;while(ilength&L-datai!=x)i+;if(ilength)return i;else return 0;5顺序表的插入算法顺序表的插入算法inselem(L,i,x)的实现的实现 顺序表的插入是指在表的第顺序表的插入是指在表的第 i个位置上插入一个值为个位置上插入一个
19、值为 x的的新元素，插入后使原表长为新元素，插入后使原表长为 n的表：的表：(a1，a2，ai-1，ai，ai+1，an)，成为表长为成为表长为 n+1n+1的表：的表：由算法可知，对于表长为由算法可知，对于表长为n的顺序表，在查找过程中，数据的顺序表，在查找过程中，数据元素比较次数最少为元素比较次数最少为1，最多为，最多为 n，元素比较次数的平均值为元素比较次数的平均值为(n+1)/2，时间复杂度为时间复杂度为 O(n)。2022-9-1247 (a1，a2，ai-1，x，ai，ai+1，an),i 的取值范围为的取值范围为1iin+1。下图表示一个顺序表中的数组在进行插入运算前下图表示一个
20、顺序表中的数组在进行插入运算前后，数据元素在数组中的下标变化。后，数据元素在数组中的下标变化。0 a0 1 a1 2 a2 i-1 ai-1 i ai i+1 ai+1 i+2 ai+2 num anum 0 a0 1 a1 2 a2 i-1 ai-1 i x i+1 ai i+2ai+1 numanum 插入插入x插入前插入前插入后插入后2022-9-1248void Inselem(sqList*L,int i,Elemtype x)if(iL-length+1)printf(“Error!”);/插入位置出错插入位置出错 exit(1);if(L-length=MaxLen)printf
21、(“overflow!”);/表已满表已满 exit(1);for(j=L-length;j=i;j-)L-dataj+1=L-dataj;/数据元素后移数据元素后移 L-datai=x;/插入插入x L-length+;/表长度加表长度加1 2022-9-1249 )1(11inpEniiin11112)1(11)1(Eniniiinninninp假设表中任何位置插入概率是均等的假设表中任何位置插入概率是均等的,即即Pi=1/(n+1),则：则：该算法的时间主要花费在移动数据元素上，移动个数取决于插该算法的时间主要花费在移动数据元素上，移动个数取决于插入位置入位置 i和表的长度和表的长度n。
22、所以可以用数据元素的移动操作来估计算法所以可以用数据元素的移动操作来估计算法的时间复杂度。在第的时间复杂度。在第 i个位置上插入个位置上插入 x，共需要移动共需要移动 n-i+1个元素，个元素，i 的取值范围为的取值范围为：1i n+1，即有即有 n+1个位置可以插入。个位置可以插入。当当i=n+1时，不需要移动结点；当时，不需要移动结点；当i=1时需要移动时需要移动n个结点个结点。由此。由此可以看出，算法在最好的情况下时间复杂性为可以看出，算法在最好的情况下时间复杂性为O(1)，最坏的时间复最坏的时间复杂性是杂性是O(n)。由于插入的位置是随机的，因此，需要分析执行该算法移动数由于插入的位置
23、是随机的，因此，需要分析执行该算法移动数据元素的平均值。设在第据元素的平均值。设在第i个位置上作插入的概率为个位置上作插入的概率为Pi，则平均移动则平均移动数据元素的次数：数据元素的次数：2022-9-1250 由此可以看出，在线性表上做插入操作需要移动表中一由此可以看出，在线性表上做插入操作需要移动表中一半的数据元素，当半的数据元素，当n较大时，算法的效率是比较低的，所以较大时，算法的效率是比较低的，所以在线性表上进行插入操作的时间复杂度为在线性表上进行插入操作的时间复杂度为(n)。顺序表的删除运算是指将表中第顺序表的删除运算是指将表中第 i 个元素从线性表中去掉，个元素从线性表中去掉，原表
24、长为原表长为 n 的线性表的线性表(a1，a2，ai-1，ai，ai+1，an)。进行删除以后的线性表表长变为进行删除以后的线性表表长变为 n-1的表的表(a1，a2，ai-1，ai+1，an)，i 的取值范围为：的取值范围为：1in。图图2-5表示一个顺序表的数组在进行删除运算前后，其数表示一个顺序表的数组在进行删除运算前后，其数据元素在数组中的下标变化。据元素在数组中的下标变化。2022-9-1251图图2-5 线性表中的删除运算示意图线性表中的删除运算示意图a1a2ai-1ana1a2.ai-1aiai+1.an.MaxLen-1012in-1n删除aiMaxLen-1012.i-1i+
25、1 i+2n-1下标数据元素下标数据元素删除前删除后ai+1i-1i+1an-1.2022-9-1252 在线性表上完成上述运算通过以下两个操作来实现：在线性表上完成上述运算通过以下两个操作来实现：(1)(1)线性表中第线性表中第i个至第个至第n个元素（共个元素（共n-i+1个元素）依次向前移个元素）依次向前移动一个位置。将所删除的元素动一个位置。将所删除的元素ai覆盖掉，从而保证逻辑上相邻覆盖掉，从而保证逻辑上相邻的元素物理位置也相邻。的元素物理位置也相邻。(2)(2)修改线性表长度，使其减修改线性表长度，使其减1。线性表的删除算法如下：线性表的删除算法如下：void Delelem(sqL
26、ist*L,int i)/删除线性表中第删除线性表中第i个位置上的元素个位置上的元素 if(iL-length)/检查空表及删除位置的合法性检查空表及删除位置的合法性 printf(不存在第不存在第i个元素个元素);exit(0);for(j=i;jlength-1;j+)L-dataj-1=L-dataj;/向前移动元素向前移动元素 L-length-;2022-9-1253 niideinp1)(E11121)(1)(Eniniideninninp 删除算法的时间性能分析：删除算法的时间性能分析：与插入运算相同，删除运算的时间也主要消耗在移动表中数与插入运算相同，删除运算的时间也主要消耗在
27、移动表中数据元素上，删除第据元素上，删除第i个元素时，其后面的元素个元素时，其后面的元素 ai+1an 都要向前移都要向前移动一个位置，共移动了动一个位置，共移动了 n-i 个元素，所以在等概率的情况下，在个元素，所以在等概率的情况下，在线性表中删除数据元素所需移动数据元素的期望值，即平均移动线性表中删除数据元素所需移动数据元素的期望值，即平均移动数据元素的次数为：数据元素的次数为：由此可以看出，在线性表上删除数据元素时大约需要移动表中一由此可以看出，在线性表上删除数据元素时大约需要移动表中一半的元素，显然该算法的时间复杂度为半的元素，显然该算法的时间复杂度为(n)。通常情况下，我们认为在线性
28、表中任何位置删除元素是等概通常情况下，我们认为在线性表中任何位置删除元素是等概率的，即率的，即pi=1/n，则：则：2022-9-1254【例例2-1】利用线性表的基本运算，编写在线性表利用线性表的基本运算，编写在线性表A A中删除线性表中删除线性表B B中出现的元素的算法。中出现的元素的算法。【解】【解】本题的算法思路是：依次检查线性表本题的算法思路是：依次检查线性表B B中的每个元素，看中的每个元素，看它是否在线性表它是否在线性表A A中。若在线性表中。若在线性表A A中，则将其从中，则将其从A A中删除。本中删除。本题的算法如下：题的算法如下：void delete(sqList*A,s
29、qList*B)int i,k;ElemType x;for(i=1;i0)Delelem(A,k);/若在线性表若在线性表A中找到了，将其删除中找到了，将其删除 2022-9-1255【例例2-2】利用线性表的基本运算，编写将线性表利用线性表的基本运算，编写将线性表A A和和B B中公共元素生成中公共元素生成线性表线性表C C的算法。的算法。【解】本题的算法思路是：先初始化线性表【解】本题的算法思路是：先初始化线性表C，然后依次检查线性表然后依次检查线性表A中中的每个元素，看它是否在线性表的每个元素，看它是否在线性表B中；若在线性表中；若在线性表B中，则将其插入中，则将其插入到线性表到线性表
30、C中。本题的算法如下：中。本题的算法如下：void commelem(sqList*A,sqList*B,sqList*C)int i,k,j=1;ElemType x;Initlist(C);for(i=1;iO)Inselem(C,j,x);j+;/若在线性表若在线性表B B中找到了，将其插入到中找到了，将其插入到C C中中 2022-9-1256【例【例2-3】将顺序表】将顺序表(a1，a2，a3，an)重新排列为以重新排列为以a1为界的两部分：为界的两部分：a1前面的值均比前面的值均比a1小，小，a1后面的值都比后面的值都比a1大（这里假设数据元素的类型大（这里假设数据元素的类型具有可
31、比性，可设为整型）具有可比性，可设为整型）。【解】基本思路：从第二个元素开始到最后一个元素，逐一向后扫描，【解】基本思路：从第二个元素开始到最后一个元素，逐一向后扫描，当数据元素当数据元素ai比比a1大时，表明它已经在大时，表明它已经在a1的后面，不必改变它与的后面，不必改变它与a1之间之间的位置，继续比较下一个；当数据元素的位置，继续比较下一个；当数据元素ai比比a1小时，表明它应该在小时，表明它应该在a1的的前面，此时将它前面的元素依次向下移动一个位置，然后将它置入最前面，此时将它前面的元素依次向下移动一个位置，然后将它置入最上方。算法如下：上方。算法如下：typedef int Elem
32、Type;void part(sqList*L)int i,j;ElemType x,y;x=L-data0;/将基准元素将基准元素a1置入置入x中中 for(i=1;ilength;i+)if(L-dataidatai;for(j=i-1;j=0;j-)/移动移动 L-dataj+1=L-dataj;L-data0=y;2022-9-1257即最坏情况下移动数据的时间复杂性能为即最坏情况下移动数据的时间复杂性能为O(n2)。2)3()1()21(22nniinini 本算法中，有两重循环，外循环执行本算法中，有两重循环，外循环执行n-1次，内循环中元素次，内循环中元素的移动次数与当前数据的大
33、小有关，的移动次数与当前数据的大小有关，当第当第i个元素小于个元素小于a1时，要时，要移动它上面的移动它上面的i-1个元素，再加上前面结点的保存及置入，所以个元素，再加上前面结点的保存及置入，所以移动移动i-1+2次，在最坏情况下，次，在最坏情况下，a1后面的结点都小于后面的结点都小于a1，故总的故总的移动次数为：移动次数为：2022-9-1258 线性表的顺序存储结构中任意数据元素的存储地址可由公式直线性表的顺序存储结构中任意数据元素的存储地址可由公式直接导出，因此顺序存储结构的线性表是可以随机存取其中的任意接导出，因此顺序存储结构的线性表是可以随机存取其中的任意元素。元素。但是，顺序存储结
34、构也有一些不方便之处，主要表现在：但是，顺序存储结构也有一些不方便之处，主要表现在：（1）数据元素最大个数需预先确定，使得高级程序设计语言编译）数据元素最大个数需预先确定，使得高级程序设计语言编译系统需预先分配相应的存储空间；系统需预先分配相应的存储空间；（2）插入与删除运算的效率很低。为了保持线性表中的数据元素）插入与删除运算的效率很低。为了保持线性表中的数据元素顺序，在插入操作和删除操作时需移动大量数据。对于插入和删顺序，在插入操作和删除操作时需移动大量数据。对于插入和删除操作频繁的线性表、将导致系统的运行速度难以提高。除操作频繁的线性表、将导致系统的运行速度难以提高。（3）存储空间不便于
35、扩充。当一个线性表分配顺序存储空间后，）存储空间不便于扩充。当一个线性表分配顺序存储空间后，若线性表的存储空间已满，但还需要插入新的元素，则会发生若线性表的存储空间已满，但还需要插入新的元素，则会发生“上溢上溢”错误。错误。2022-9-1259 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，故可以随机存取表中的任一结点；但在点间的逻辑关系，故可以随机存取表中的任一结点；但在插入和删插入和删除操作时需移动大量的结点。除操作时需移动大量的结点。为避免大量结点的移动，介绍线性表的另一种存储方式为避免大量结点的移动，介绍线
36、性表的另一种存储方式:链式链式存储结构，简称链表存储结构，简称链表(Linked List)Linked List)。线性表的链式存储结构就是用一组任意的存储单元（可以是不线性表的链式存储结构就是用一组任意的存储单元（可以是不连续的）存储线性表的数据元素。对线性表中的每一个数据元素，连续的）存储线性表的数据元素。对线性表中的每一个数据元素，都需用两部分来存储：一部分用于存放数据元素值，称为数据域；都需用两部分来存储：一部分用于存放数据元素值，称为数据域；另一部分用于存放直接前驱或直接后继结点的地址（指针），称为另一部分用于存放直接前驱或直接后继结点的地址（指针），称为指针域，称这种存储单元为结
37、点。指针域，称这种存储单元为结点。链式存储方式可用于表示线性结构，也可用于表示非线性结构。链式存储方式可用于表示线性结构，也可用于表示非线性结构。2022-9-12602.3.1链表的存储结构 链式存储结构是利用任意的存储单元来存放线性表中的元素，链式存储结构是利用任意的存储单元来存放线性表中的元素，存储数据的单元在内存中可以连续，也可以零散分布。存储数据的单元在内存中可以连续，也可以零散分布。由于线性表中各元素间存在着线性关系，每一个元素有一个直接由于线性表中各元素间存在着线性关系，每一个元素有一个直接前驱和一个直接后继。为了表示元素间的这种线性关系，在这种前驱和一个直接后继。为了表示元素间
38、的这种线性关系，在这种结构中不仅要存储线性表中的元素，还要存储表示元素之间逻辑结构中不仅要存储线性表中的元素，还要存储表示元素之间逻辑关系的信息。所以用链式存储结构表示线性表中的一个元素时至关系的信息。所以用链式存储结构表示线性表中的一个元素时至少需要两部分信息，除了存储每一个数据元素值以外，还需存储少需要两部分信息，除了存储每一个数据元素值以外，还需存储其后继或前驱元素所在内存的地址。两部分信息一起构成链表中其后继或前驱元素所在内存的地址。两部分信息一起构成链表中的一个结点。结点的结构如下所示。的一个结点。结点的结构如下所示。datanext数据域指针域2022-9-1261C语言采用结构数
39、据类型描述结点如下：语言采用结构数据类型描述结点如下：typedef struct LNodeElemType data;/结点值结点值 struct LNode*next;/存储下一个结点的地址存储下一个结点的地址LNode,*LinkList;LNode*head;在此结构中，用数据域在此结构中，用数据域data存储线性表中数据元素存储线性表中数据元素。指针域。指针域next，它给出下一个结点的存储地址。结点的指针域将所有结点它给出下一个结点的存储地址。结点的指针域将所有结点按线性表的逻辑次序链接成一个整体，形成一个链表。由于链表按线性表的逻辑次序链接成一个整体，形成一个链表。由于链表中第
40、一个结点没有直接前驱，所以必须设置一个头指针中第一个结点没有直接前驱，所以必须设置一个头指针head存储存储第一个结点的地址。最后一个结点没有直接后继，其指针域应为第一个结点的地址。最后一个结点没有直接后继，其指针域应为空指针，空指针，C语言用语言用NULL或或0来表示，在图中表示为来表示，在图中表示为“”。假设有一个线性表为（假设有一个线性表为（A,B,C,D,E），），存储空间具有存储空间具有10个存储结个存储结点，该线性表在存储空间中的存储情况如图点，该线性表在存储空间中的存储情况如图2-7(a)所示。所示。2022-9-1262图图 2-7 链表结构示意图链表结构示意图4head头指针
41、12345678910datanextA7B2C9D1E0(a)线性链表的物理状态头指针headABCDE47291(b)线性表的逻辑状态2022-9-1263 从图中可见，每个结点的存储地址存放在直接前驱的指针域中。从图中可见，每个结点的存储地址存放在直接前驱的指针域中。所以要访问链表中数据元素所以要访问链表中数据元素C，必须由头指针必须由头指针head得到第一个结点得到第一个结点（数据（数据A）的地址，由该结点的指针域得到第二个结点（数据的地址，由该结点的指针域得到第二个结点（数据B）的地址，再由其指针域得到存储数据的地址，再由其指针域得到存储数据C的结点地址，访问该结点的的结点地址，访问
42、该结点的数据域就可以处理数据数据域就可以处理数据C了。链表这种顺着指针链依次访问数据元了。链表这种顺着指针链依次访问数据元素的特点，表明链表是一种素的特点，表明链表是一种顺序存储结构顺序存储结构，只能顺序操作链表中元，只能顺序操作链表中元素。不能像顺序表（数组）那样可以按下标素。不能像顺序表（数组）那样可以按下标随机随机存取。存取。为了提高顺序操作的速度，使操作更加灵活方便，对链表中为了提高顺序操作的速度，使操作更加灵活方便，对链表中的指针采用了不同的设置，构成了不同的链表。如只设置一个指向的指针采用了不同的设置，构成了不同的链表。如只设置一个指向后继结点地址的指针域是单链表；将其首尾相接构成
43、一个环状结构，后继结点地址的指针域是单链表；将其首尾相接构成一个环状结构，称为循环链表；增加一个指向前驱的指针就构成双向链表。称为循环链表；增加一个指向前驱的指针就构成双向链表。在链表存储结构中，不要求存储空间的连续性，数据元素之间在链表存储结构中，不要求存储空间的连续性，数据元素之间的逻辑关系由指针来确定。由于链式存储的灵活性，这种存储方式的逻辑关系由指针来确定。由于链式存储的灵活性，这种存储方式既可用于表示线性结构，也可以用来表示非线性结构。既可用于表示线性结构，也可以用来表示非线性结构。2022-9-12642.3.2 单向链表单向链表 在图在图2-7所示的链表中，每个结点只有一个指向后
44、继的指针。也就是说访问数据所示的链表中，每个结点只有一个指向后继的指针。也就是说访问数据元素只能由链表头依次到链表尾，而不能做逆向访问。称这种链表为单向链表或线元素只能由链表头依次到链表尾，而不能做逆向访问。称这种链表为单向链表或线性链表。这是一种最简单的链表。性链表。这是一种最简单的链表。单链表分为带头结点和不带头结点两种类型。单链表分为带头结点和不带头结点两种类型。对于空链表，头结点的指针域为空。图对于空链表，头结点的指针域为空。图2-8是带头结点的链表示方式：是带头结点的链表示方式：图图2-8（a）为带头结点的空链为带头结点的空链 (b)为带头结点的单链表为带头结点的单链表headhea
45、da1a2a3(a)空链表（b)非 空链表2022-9-1265 由于链表是一种动态管理的存储结构，每个结点需动态产生。由于链表是一种动态管理的存储结构，每个结点需动态产生。1初始化链表初始化链表initlist(L)的实现的实现 建立一个空的带头结点的单链表。所谓空链表就是指表长建立一个空的带头结点的单链表。所谓空链表就是指表长为为0的表。在这种情况下，链表中没有元素结点。但应有的表。在这种情况下，链表中没有元素结点。但应有一个头结点，其指针域为空。一个头结点，其指针域为空。void initlist(LinkList void initlist(LinkList*L)L)*L=(LNode
46、 L=(LNode*)malloc(sizeof(LNode);)malloc(sizeof(LNode);(*L)-next=NULL;L)-next=NULL;在函数调用时，指针在函数调用时，指针L指向的内容发生了变化，为使得调用函数中头指针变量指向的内容发生了变化，为使得调用函数中头指针变量head获得头结点地址，需传递头指针变量的地址给获得头结点地址，需传递头指针变量的地址给initlist()函数，而函数中定义二函数，而函数中定义二级指针变量级指针变量L接受该地址值，从而返回改变后的值。接受该地址值，从而返回改变后的值。2022-9-12662求线性表长度求线性表长度Getlen(L
47、)的实现的实现 设计思路：设置一个初值为设计思路：设置一个初值为0的计数器变量和一个跟踪链的计数器变量和一个跟踪链表结点的指针表结点的指针p。初始时初始时p指向链表中的第一个结点，然后指向链表中的第一个结点，然后顺着顺着next域依次指向每个结点，每指向一个结点计数器变域依次指向每个结点，每指向一个结点计数器变量加量加1。当。当p为为0时，结束该过程。其时间复杂度为时，结束该过程。其时间复杂度为O(n)。int Getlen(LinkList L)int Getlen(LinkList L)int num=0;int num=0;LNode LNode*p;p;p=L-next;p=L-nex
48、t;while(p!=NULL)while(p!=NULL)num+;num+;p=p-next;p=p-next;return(num);return(num);2022-9-12673按序号取元素按序号取元素Getelem(L,i)的实现的实现根据前面的讨论，对单链表中的结点只能顺序存取，即访问根据前面的讨论，对单链表中的结点只能顺序存取，即访问前一个结点后才能接着访问后一个结点。所以要访问单前一个结点后才能接着访问后一个结点。所以要访问单链表中第链表中第i个元素值，必须从头指针开始遍历链表，依次个元素值，必须从头指针开始遍历链表，依次访问每个结点，直到访问到第访问每个结点，直到访问到第i
49、个结点为止。同顺序表一个结点为止。同顺序表一样，也需注意存取的位置是否有效。样，也需注意存取的位置是否有效。LNode LNode*Getelem(LinkList L,int i)Getelem(LinkList L,int i)LNode LNode*p;int pos=1;p;int pos=1;p=L-next;p=L-next;if(iGetlen(L)exit(1);if(iGetlen(L)exit(1);while(posi)while(posnext;p=p-next;pos+;pos+;return p;return p;2022-9-12684查找运算查找运算locate
50、(L,x)的实现的实现 设计思路：设置一个跟踪链表结点的指针设计思路：设置一个跟踪链表结点的指针p，初始时初始时p指指向链表中的第一个结点，然后顺着向链表中的第一个结点，然后顺着next域依次指向每个域依次指向每个结点，每指向一个结点就判断其值是否等于结点，每指向一个结点就判断其值是否等于x，若是则返若是则返回该结点地址。否则继续往后搜索，直到回该结点地址。否则继续往后搜索，直到p为为0，表示链，表示链表中无此元素，返回表中无此元素，返回NULL。其时间复杂度为其时间复杂度为O(n)。LNode LNode*Locate(LinkList L,int x)Locate(LinkList L,i
