第2章线性表(修改)

1、 本章要点本章要点 线性表的逻辑结构线性表的逻辑结构 线性表的顺序存储线性表的顺序存储 线性表的链式存储线性表的链式存储 顺序表和链表的比较顺序表和链表的比较 本章难点本章难点 顺序存储结构、链式存储结构及基本运算的实现顺序存储结构、链式存储结构及基本运算的实现 2.1 线性表的逻辑结构线性表的逻辑结构 2.1.1 线性表的类型定义线性表的类型定义线性表是一种线性结构，线性结构的数据元素之间是一种线性表是一种线性结构，线性结构的数据元素之间是一种线性关系，线性关系的特点如下：线性关系，线性关系的特点如下： 在一个线性表中的数据元素的类型是相同的，数据元素一在一个线性表中的数据元素的类型是相同的

2、，数据元素一个接一个的排列。个接一个的排列。 存在一个唯一的被称作存在一个唯一的被称作“第一个第一个”的数据元素。的数据元素。 存在唯一的一个被称作存在唯一的一个被称作“最后一个最后一个”的数据元素。的数据元素。 除第一个之外，每个数据元素均只有一个前驱；除最后一除第一个之外，每个数据元素均只有一个前驱；除最后一个之外，每个数据元素均只有一个后继。个之外，每个数据元素均只有一个后继。一个线性表是一个线性表是n (n0)个同类型数据元素个同类型数据元素a1 , a2 , a3 , ，an的有限序列。记作：的有限序列。记作： （a1 , a2 , a3 , , an ）从定义可以看出，线性表强调两

3、个特性：从定义可以看出，线性表强调两个特性：（1）任何数据元素）任何数据元素ai (i=1 , ，n) 必须是同类型的数据，例如，必须是同类型的数据，例如，如果是记录，则必须是含有相同数据项的记录；如果是整数，如果是记录，则必须是含有相同数据项的记录；如果是整数，则必须都是整数，不能将不同性质的数据列在一个线性表内。则必须都是整数，不能将不同性质的数据列在一个线性表内。（2）另一个是数据元素的有序性，数据元素在表中的位置决定）另一个是数据元素的有序性，数据元素在表中的位置决定了它的序号。按照这个次序，元素了它的序号。按照这个次序，元素ai-1 称为称为 ai 的直接前趋，的直接前趋，ai 称为

4、称为ai-1 的直接后继（的直接后继（i=1,2,3,，n）。）。 a1 是表中第一个元素，是表中第一个元素，它没有前趋；它没有前趋；an 是表中最后一个元素，它没有后继。是表中最后一个元素，它没有后继。表中数据元素的个数表中数据元素的个数n称为线性表的长度。长度为称为线性表的长度。长度为0的线性表称的线性表称为为空表空表。称。称 i 为为ai在线性表中的在线性表中的位序位序。 2.1.1 线性表的类型定义线性表的类型定义 【例1】英文字母表（A，B，Z）是线性表，表中每个字母是一个数据元素（结点）【例2】一副扑克牌的点数（2，3，10，J，Q，K，A）也是一个线性表，其中数据元素是每张牌的点

5、数【例3】学生成绩表中，每个学生及其成绩是一个数据元素，其中数据元素由学号、姓名、各科成绩及平均成绩等数据项组成。将数据元素称为记录，含有大量记录的线性表成为文件。举例其抽象数据类型的定义如下：其抽象数据类型的定义如下：ADT List 数据对象：数据对象：Data ai | ai ElemSet, i=1,2,.,n, n0 数据关系：数据关系：R1 |ai-1,aiData, i=2,.,n 线性表中的数据元素可以是各种各样的，只要是属于同一线性表中的数据元素可以是各种各样的，只要是属于同一个集合即可。个集合即可。 2.1.1 线性表的类型定义线性表的类型定义数据结构的运算是定义在逻辑结构

6、层次上的，而运算的具数据结构的运算是定义在逻辑结构层次上的，而运算的具体实现是建立在存储结构上的，每一种操作的具体实现只有在体实现是建立在存储结构上的，每一种操作的具体实现只有在确定了线性表的存储结构之后才能完成。确定了线性表的存储结构之后才能完成。对于线性表，常用的运算有如下几种：对于线性表，常用的运算有如下几种：(1) 置空表（结构初始化）置空表（结构初始化） init_seqlist(L)；操作结果：构造一个空的线性表操作结果：构造一个空的线性表L。求线性表的长度。求线性表的长度。list_length(L);初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：返回操作结果：返回

7、L中元素个数。中元素个数。 2.1.2 线性表的基本操作线性表的基本操作定位定位:访问线性表的第访问线性表的第i个元素。个元素。get_node(L,i);初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：返回操作结果：返回L中第中第i个元素的值或地址。个元素的值或地址。查找查找 : 在线性表中查找满足某种条件的数据元素。在线性表中查找满足某种条件的数据元素。location_list(L,x);初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：返回操作结果：返回L中值为给定值中值为给定值x的数据元素。的数据元素。 2.1.2 线性表的基本操作线性表的基本操作插入插入:在线

8、性表的第在线性表的第i个元素之前，插入一个同类型的元素。个元素之前，插入一个同类型的元素。insert_list(L,i,x);初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：在操作结果：在L的第的第i个位置插入一个值为个位置插入一个值为x的新元素。的新元素。删除删除 : 删除线性表中第删除线性表中第i个元素。个元素。delete_list(L,i);初始条件：线性表初始条件：线性表L已存在。已存在。操作结果：在操作结果：在L中删除序号为中删除序号为i的数据元素。的数据元素。清除表清除表: 将已有线性表变为空表，即删除表中所有元素。将已有线性表变为空表，即删除表中所有元素。 2.1

9、.2 线性表的基本操作线性表的基本操作一种数据结构只有在内存中正确表示出来，才能实现其基一种数据结构只有在内存中正确表示出来，才能实现其基本操作。数据结构在内存中的表示通常有两种形式，即本操作。数据结构在内存中的表示通常有两种形式，即顺序存顺序存储储表示和表示和链式存储链式存储表示。线性表的顺序表示又称为表示。线性表的顺序表示又称为顺序表顺序表。 2.2.1顺序表顺序表用一组地址连续的存储单元依次存储线性表的数据元素，用一组地址连续的存储单元依次存储线性表的数据元素，这种存储方式称为线性表的顺序存储结构。它以元素在计算机这种存储方式称为线性表的顺序存储结构。它以元素在计算机内内“物理位置相邻物

10、理位置相邻”来表示线性表中数据元素之间的逻辑关系，来表示线性表中数据元素之间的逻辑关系，即逻辑上相邻的数据元素在物理位置上也是相邻的。即逻辑上相邻的数据元素在物理位置上也是相邻的。 2.2线性表的顺序存储线性表的顺序存储线性表的顺序存储结构具有以下基本特点：线性表的顺序存储结构具有以下基本特点：(1) 存储空间必须是连续的，预分配；存储空间必须是连续的，预分配；(2) 逻辑顺序与物理顺序一致，用物理上的相逻辑顺序与物理顺序一致，用物理上的相邻来表示逻辑上的线性关系。邻来表示逻辑上的线性关系。(3)任意相邻元素之间无空闲空间，且相距为任意相邻元素之间无空闲空间，且相距为L(4)已知基地址，可以计

11、算出任意元素的存储已知基地址，可以计算出任意元素的存储地址地址a1a2ai-1aiai+1anlength-1线性表的顺序存储线性表的顺序存储设设a1的存储地址为的存储地址为Loc(a1)，称为基址，每个数据元素占，称为基址，每个数据元素占d个存储单元，则第个存储单元，则第i个数据元素的地址为：个数据元素的地址为：Loc(ai)Loc(a1)+(i-1)*di n已知顺序表的首地址和每个元素所占地址单元的个数，已知顺序表的首地址和每个元素所占地址单元的个数，就可求出第就可求出第i个数据元素的地址。个数据元素的地址。 2.2.1 顺序表顺序表所以称顺序表为一种所以称顺序表为一种随机存取随机存取的

12、结构的结构知识点回顾:用typedef定义类型可以用可以用typedef声明新的类型名来代替已有的类型名。声明新的类型名来代替已有的类型名。例例1：typedef int COUNT; COUNT I,j;例例2：typedef struct int month; int day; int year; DATE; 新类型名新类型名DATE DATE birthday; DATE *p;说明：对于上结构体，说明：对于上结构体，typedef 后跟一个无命名的结构体类后跟一个无命名的结构体类型型例3：typedef struct Node elemtype data; struct Node *n

13、ext; ListNode,*LinkList;Typedef与#define区别如：Typedef int COUNT;和#define COUNT int 二者不同#define是在预编译时处理的，只能做简单的字符串替换。而typedef是在编译时处理的，它可以像定义变量的方法那样声明一个类型。如：COUNT I ,j;顺序表的虚拟实现：顺序表的虚拟实现：在高级语言中，数组是采用顺序存储的，所以我们可以用数组在高级语言中，数组是采用顺序存储的，所以我们可以用数组类型来说明顺序表的存储方式。类型来说明顺序表的存储方式。即顺序表类型定义即顺序表类型定义 2.2.1 顺序表顺序表#define

14、MAXSIZE 100 /表空间的大小可根据实际需要而定，表空间的大小可根据实际需要而定，这里假设为这里假设为100 typedef int ElemType /ElemType的类型可根据实际情况而定，的类型可根据实际情况而定，这里假设为这里假设为int typedef struct Elemtype dataMAXSIZE; /最多有最多有MAXSIZE个数据元素个数据元素 int length; /存放数据元素的实际个数存放数据元素的实际个数 SeqList; /定义了一个新类型：顺序表类型定义了一个新类型：顺序表类型SeqList list; /定义一个变量：顺序表定义一个变量：顺序表

15、list为了能够对顺序表进行整体引用，通常将为了能够对顺序表进行整体引用，通常将data和和length封封装成一个结构体作为顺序表的类型。装成一个结构体作为顺序表的类型。知识点回顾：结构体中成员的表示知识点回顾：结构体中成员的表示表长表长list.length=n；表空标志表空标志list.length=0；表满标志表满标志list.length=MAXSIZE； 即即0=lengthlength； / 等同于等同于(*pslist).length 表空标志表空标志pslist-length=0；表满标志表满标志pslist-length=MAXSIZE；数据元素数据元素pslist-dat

16、a0pslist-datapslist-length-1a1a2ai-1aiai+1an01i-2i-1in-1MAXSIZE-1a1a2ai-1aiai+1anpslist-datapslist-length-1 2.2.1 顺序表顺序表l 注意：注意： 存放线性表结点的向量空间的大小存放线性表结点的向量空间的大小MAXSIZE应应仔细选值，使其既能满足表结点的数目增加的需求，又仔细选值，使其既能满足表结点的数目增加的需求，又不致于预先定义过大而浪费存储空间。不致于预先定义过大而浪费存储空间。 由于由于C语言中向量的下标从语言中向量的下标从0开始，所以若开始，所以若L是是SqList类型的指

17、针变量，则类型的指针变量，则a1和和an分别存储在分别存储在L.pslist0和和L.pslistlength-1中。中。注意问题：注意问题：l 参数：参数：值传递和地址传递的区别值传递和地址传递的区别参数传递的方向参数传递的方向l 边界值的处理：边界值的处理：在第一个元素前插入在第一个元素前插入在最后一个元素后插入在最后一个元素后插入l 当删除或插入元素时，线性表的长度改变当删除或插入元素时，线性表的长度改变l 指定的数据元素的位置是否合法指定的数据元素的位置是否合法 2.2.2 顺序表的基本运算顺序表的基本运算 顺序表的初始化顺序表的初始化初始化即构造一个空表。初始化即构造一个空表。算法分

18、析算法分析将将pslist设为指针参数，动态分配存储空间设为指针参数，动态分配存储空间需考虑问题：需考虑问题：（1）动态分配空间是否成功）动态分配空间是否成功（2）表中）表中length值设为值设为0初始化算法实现：初始化算法实现：SeqList *init_SeqList() SeqList *pSlist; pSlist=(SeqList *) malloc (sizeof(SeqList); if ( pSlist !=NULL) pSlist-length=0; else printf(“Out of space!”); return(pSlist); main() SeqList *

19、pSlist; pSlist=init_Seqlist(); 2.2.2 顺序表的基本运算顺序表的基本运算 2.2.2 顺序表的基本运算顺序表的基本运算j的取值范围： i-1=j=i-1;j-) dataj+1=dataj;i-1n-1自下而上的向下移动自下而上的向下移动j起始位置起始位置需考虑问题：需考虑问题：(1) 分配时由于向量空间大小在声明时确定，当L-length=MAXSIZE时，表空间已满，不可再做插入操作；(2) 当插入位置i的值为ilength+1或i1时为非法位置，不可做正常插入操作；(3) 移动元素时是整体自下而上的顺序； (4) length值增1；插入算法实现：插入算

20、法实现：int insert_list(SeqList *pslist, int i, Elemtype x ) int j; if (pslist-length =MAXSIZE) printf(“表满表满n”); return -1; if (ipslist-length+1) printf(“位置错位置错”)；return (0); 2.2.2 顺序表的基本运算顺序表的基本运算 for (j=pslist-length-1;j=i-1;j-) pslist-dataj+1=pslist-dataj;/*结点向后移结点向后移*/ pslist-datai-1=x;/*插入新元素插入新元素*

21、/ pslist-length+;/*length仍指向最后元素仍指向最后元素*/ return 1; 2.2.2 顺序表的基本运算顺序表的基本运算时间复杂度分析：时间复杂度分析：设在第设在第i个位置插入的概率为个位置插入的概率为Pi平均移动次数平均移动次数Eis(n)= n/2说明做插入操作时，需要移动一半的数据元素，时间复杂说明做插入操作时，需要移动一半的数据元素，时间复杂度为度为O(n)。 2.2.2 顺序表的基本运算顺序表的基本运算niiinP1) 1(niin1) 1(11n11na 2.2.2 顺序表的基本运算顺序表的基本运算in-1自上而下的向上移动自上而下的向上移动j起始位起始

22、位置置j的取值范围： i=j=length-1移动语句：For (j=i;jlength的值为的值为0，条件（，条件（ipslist-length）也包括对表空的检查（符合）也包括对表空的检查（符合ilength ）；(4)移动元素时是整体自上而下的顺序；(5) length值减1； 删除算法实现删除算法实现int delete_list(SeqList *pslist,int i) int j; if (ipslist-length) printf(“不存在第不存在第i个元素个元素n”); return(0);for (j=i;jlength-1;j+) pslist-dataj-1=psl

23、ist-dataj; pslist-length-; return 1; 2.2.2 顺序表的基本运算顺序表的基本运算时间复杂度分析：时间复杂度分析：删除第删除第i个位置的概率为个位置的概率为Pi平均移动次数平均移动次数Ede(n)=说明删除运算时平均需要移动一半的数据元素，时间复杂说明删除运算时平均需要移动一半的数据元素，时间复杂度为度为O(n)。 2.2.2 顺序表的基本运算顺序表的基本运算niinP1) 1(n1n1niin1)(2) 1( n 2.2.2 顺序表的基本运算顺序表的基本运算 顺序表按值查找算法实现顺序表按值查找算法实现int location_seqlist(SeqLis

24、t *pslist,elemtype x) int i; i=0; while (ilength-1 & pslist-datai!=x) i+; if (ipslist-length-1) return 1; else return i; /*返回存储位置返回存储位置*/ 2.2.2 顺序表的基本运算顺序表的基本运算时间复杂度分析：时间复杂度分析：本算法的主要运算是比较，比较次数与本算法的主要运算是比较，比较次数与x的位置有的位置有关，也与表长有关。关，也与表长有关。 2.2.2 顺序表的基本运算顺序表的基本运算找到找到找不到找不到最好情况最好情况1 1次次 O(1)O(1) n+1n+1次

25、次 O(1)O(1)最坏情况最坏情况n n次次O(nO(n) )n+1n+1次次O(nO(n) )平均情况平均情况n/2n/2次次O(nO(n) )n+1n+1次次O(nO(n) ) 2.2.2 顺序表的基本运算顺序表的基本运算 查找操作算法实现查找操作算法实现Elemtype Get_Node(SeqList *pslist,int i) if (i=1 & ilength) return(pslist-datai-1); else printf(“Not exit.n”); return(-1); 求表长算法实现求表长算法实现int list_length(SeqList *pslist)

26、 return(pslist-length); /求求pslist所指向顺序表的长度所指向顺序表的长度 2.2.2 顺序表的基本运算顺序表的基本运算算法算法5和算法和算法6的时间复杂度均为的时间复杂度均为O(1)顺序表的划分。顺序表的划分。将顺序表将顺序表(a1,a2,，an)重新排列为以重新排列为以a1为界的两部分：为界的两部分：a1前前面的值均比面的值均比a1小，小，a1后面的值都比后面的值都比a1大。大。 2.2.3 顺序表的应用顺序表的应用1226811191010118122619划分前划分前划分后划分后算法分析算法分析从第二个元素开始从第二个元素开始 当前数据比当前数据比a1大时，

27、不改变其位置，继续比较下一个。大时，不改变其位置，继续比较下一个。 当前数据比当前数据比a1小时，将其前面的元素依次向后移动一个位小时，将其前面的元素依次向后移动一个位置，然后将其置入对应单元。置，然后将其置入对应单元。 2.2.3 顺序表的应用顺序表的应用12268111910将26和12比较，比12大，不用变化，再比较8和12，比12小，则12、26均向后移动(1) 需要一个变量来存放比较的位置，此算法用i来表示数组下标位置。1=i=length(2) 当需要移动元素时，需要一个变量表示移动的范围，用j表示。0=jdata0; for (i=1; ilength-1;i+) if (L-d

28、ataidatai; for (j=i-1;j=0;j-) L-dataj+1=L-dataj; L-data0=y; 2.2.3 顺序表的应用顺序表的应用顺序表的合并。顺序表的合并。已知顺序表已知顺序表LA和和LB中的数据元素按值非递减有序排列，中的数据元素按值非递减有序排列，现要求将现要求将LA和和LB归并为一个新的顺序表归并为一个新的顺序表LC，且，且LC中的数据中的数据元素仍按值非递减有序排列。元素仍按值非递减有序排列。LA=(1，4，7，10)LB=(2，3，9，12，16)LC=(1，2，3，4，7，9，10，12，16)算法分析算法分析设设LC为空表，依次扫描为空表，依次扫描LA

29、和和LB，比较当前元素，将较，比较当前元素，将较小值的元素赋给小值的元素赋给LC，直到一个线性表扫描完毕，然后将未完，直到一个线性表扫描完毕，然后将未完的顺序表中余下部分赋给的顺序表中余下部分赋给LC即可。即可。 三个顺序表都需要设个变量存当前的位置。三个顺序表都需要设个变量存当前的位置。 void union(SeqList LA, SeqList LB,SeqList *LC) int i,j,k; i=0;j=0;k=0; while (i=LA.length-1 & j=LB.length-1) if (LA.dataidatak+=LA.datai+; else LC-datak+=

30、LB.dataj+; while (idatak+=LA.datai+; while (jdatak+=LB.dataj+; LC-length=LA.length+LB.length; 2.2.3 顺序表的应用顺序表的应用从前面看到，顺序存储结构有特点：从前面看到，顺序存储结构有特点： （1）逻辑顺序与物理顺序一致）逻辑顺序与物理顺序一致 （2）随机存取）随机存取但是，也存在一些缺点：但是，也存在一些缺点： （1）插入、删除等操作要移动元素）插入、删除等操作要移动元素 （2）存储空间是预分配的，不灵活，浪费空间）存储空间是预分配的，不灵活，浪费空间 （3）表的存储空间难扩充）表的存储空间难扩

31、充 2.3线性表的链式存储线性表的链式存储那么，有没有一种灵活的存储方式呢？那么，有没有一种灵活的存储方式呢？回答是肯定的！回答是肯定的！链式存储结构，但是有优点，链式存储结构，但是有优点，同样也存在缺点同样也存在缺点 线性表的链式存储方式：线性表的链式存储方式：（1）是用一组任意的存储单元存储数据元素（这组存储单元）是用一组任意的存储单元存储数据元素（这组存储单元可以是连续的，也可以是不连续的）。可以是连续的，也可以是不连续的）。（2）为了表示线性关系，对数据元素）为了表示线性关系，对数据元素ai来说，除了存储其本来说，除了存储其本身的信息之外，还需要存储直接后继的存储位置（也可以是身的信息

32、之外，还需要存储直接后继的存储位置（也可以是前驱）。前驱）。这两部分信息组成数据元素的这两部分信息组成数据元素的ai的存储映象，称为的存储映象，称为结点结点（Node）。它包括两个域：数据域和指针域。）。它包括两个域：数据域和指针域。n个结点链结成一个链表，即为线性表的链式存储结构。又个结点链结成一个链表，即为线性表的链式存储结构。又由于每个结点中只包含一个指针域，故又称为单链表。由于每个结点中只包含一个指针域，故又称为单链表。 2.3线性表的链式存储线性表的链式存储 2.3.1 线性链表线性链表 线性表的链式存储结构的特点线性表的链式存储结构的特点 存储空间不一定连续存储空间不一定连续 逻辑

33、关系由指针来体现逻辑关系由指针来体现(3) 逻辑上相邻，物理上不一定相邻逻辑上相邻，物理上不一定相邻(4) 非随机存取（顺序存取），即访问任何一个元素非随机存取（顺序存取），即访问任何一个元素的时间不同。如磁带和的时间不同。如磁带和CD注意：注意：链式存储是最常用的存储方式之一，它不仅可用来表示链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。线性表，而且可用来表示各种非线性的数据结构。 2.3.1 线性链表线性链表存储地址存储地址数据域数据域指针指针110E150120D110125A160140C120150FNULL160B140125头指针头指

34、针head链式存储结构链式存储结构例：有线性表例：有线性表h（A,B,C,D,E,F），其对应的链式存储结构），其对应的链式存储结构如图所示。如图所示。 2.3.1 线性链表线性链表datanext 虚拟实现：虚拟实现：利用高级语言中的指针来实现。利用高级语言中的指针来实现。 结点定义如下：结点定义如下：typedef struct Node elemtype data; struct Node *next; ListNode,*LinkList;结点（结点（Node）单链表中每个结点的存储地址是存放在其前趋结点单链表中每个结点的存储地址是存放在其前趋结点next域域中，而起始结点无前趋，故设

35、中，而起始结点无前趋，故设头指针头指针head指向起始结点。指向起始结点。定义头指针变量：定义头指针变量：LinkList head; LinkNode *p; LinkList head;注意：注意： LinkList和和LNode *是不同名字的同一个指针类型（命是不同名字的同一个指针类型（命名的不同是为了概念上更明确）名的不同是为了概念上更明确） LinkList类型的指针变量类型的指针变量head表示它是单链表的头指针表示它是单链表的头指针 LNode *类型的指针变量类型的指针变量p表示它是指向某一结点的指表示它是指向某一结点的指针针 2.3.1 线性链表线性链表ABCDEFhead

36、链表的逻辑结构链表的逻辑结构nextdataPpdatapnextl算法中各个域的表示算法中各个域的表示l如定义一个指针如定义一个指针p：lLinklist p(*p).data(*p).nextHead=NULL不带头结点的空表不带头结点的空表ABCDEhead不带头结点的链表不带头结点的链表 这种链表称为不带头结点的链表，但是首结点无前驱，很多操作需要单独这种链表称为不带头结点的链表，但是首结点无前驱，很多操作需要单独考虑首结点。考虑首结点。 2.3.3线性链表的基本运算线性链表的基本运算 2.3.3线性链表的基本运算线性链表的基本运算头结点的数据域可以不存储任何信息，也可存储如线性表的长

37、度等头结点的数据域可以不存储任何信息，也可存储如线性表的长度等附加信息。指针域存放首元结点的地址附加信息。指针域存放首元结点的地址head带头结点的空表带头结点的空表ABCDEhead附加头结点的链表附加头结点的链表头指针头指针头结点头结点首元结点首元结点Headnext=NULL 头结点是在链表的起始结点之前附加头结点是在链表的起始结点之前附加的一个结点，有两个优点：的一个结点，有两个优点：由于起始结点的位置被存放在头结点的指由于起始结点的位置被存放在头结点的指针域中，故在链表的第一个位置上的操作针域中，故在链表的第一个位置上的操作与表中其他位置上操作一致，无须进行特与表中其他位置上操作一致

38、，无须进行特殊处理。殊处理。无论链表是否为空，其头指针都是指向头无论链表是否为空，其头指针都是指向头结点的非空指针，故此空表和非空表的处结点的非空指针，故此空表和非空表的处理也统一了。理也统一了。 2.3.2 动态内存分配动态内存分配动态内存分配指在程序执行过程中动态地分配或回收存储动态内存分配指在程序执行过程中动态地分配或回收存储空间，在需要时，由系统即时分配。空间，在需要时，由系统即时分配。 malloc()函数函数void *malloc(unsigned int size)在内存的动态存储区中分配一个长度为在内存的动态存储区中分配一个长度为size的连续空间。的连续空间。例例p=(lo

39、ng *) malloc(8)/*开辟长度为开辟长度为8个字节的内存空间，并把起始地址赋给一个指个字节的内存空间，并把起始地址赋给一个指向向long型的指针变量型的指针变量p*/注意注意当函数未能成功分配存储空间（如内存不足）时，返回一当函数未能成功分配存储空间（如内存不足）时，返回一个个NULL指针，即调用该函数时检测返回值是否为指针，即调用该函数时检测返回值是否为NULL并执并执行相应的操作。行相应的操作。 2.3.2 动态内存分配动态内存分配例：动态分配程序例：动态分配程序 #include /*标准输入输出文件标准输入输出文件*/#include /*动态分配文件动态分配文件*/mai

40、n() int count,*array; if (array=(int *) malloc(10*sizeof(int)=NULL) printf(“error!”); exit(1); for (count=0;count10;count+) arraycount=count; for (count=0;countnext=NULL; else printf(“out of space!”); return(pLlist); 2.3.3线性链表的基本运算线性链表的基本运算ABCDEheadp 2.3.3线性链表的基本运算线性链表的基本运算带表头结点的单链表求表长带表头结点的单链表求表长 i

41、nt length_LinkList(LinkList L) Lnode *p; int count; p=L;/*p指向头结点指向头结点*/ count=0; while (p-next !=NULL) p=p-next; count+;/*p所指的是第所指的是第count个结点个结点*/ return count; 此操作遍历了整个链表，时间复杂度：此操作遍历了整个链表，时间复杂度：O(n) 此处注意：此处注意：p-next !=NULL与与p !=NULL不同不同请同学们说出，哪儿不同？请同学们说出，哪儿不同？ 2.3.3线性链表的基本运算线性链表的基本运算3. 查找操作查找操作 链表中

42、按序号查找（查找指定位置的结点）链表中按序号查找（查找指定位置的结点） 按序号查找是线性表的一种常用运算，其功能是按序号查找是线性表的一种常用运算，其功能是对给定的链表查找表中第对给定的链表查找表中第i个结点，并用一个指针变量个结点，并用一个指针变量指向该结点。指向该结点。算法设计算法设计 从链表的第一个元素结点起，判断当前结点是否是从链表的第一个元素结点起，判断当前结点是否是第第i个，若是，则返回该结点的指针；否则继续判断后个，若是，则返回该结点的指针；否则继续判断后一个，直到表结束为止。没有第一个，直到表结束为止。没有第i个结点时返回空。个结点时返回空。 请同学们现在自己编写这个算法请同学

43、们现在自己编写这个算法 l当做遍历操作时候，while条件都要加上while (p-next！=NULL &？)或或while (p-next！=NULL | ？)或或while (p！=NULL &？)或或while (p！=NULL | ？)i的合法位置为n，j的取值范围0-n(1) 若若i1，则while条件中jn+1，则while条件中jnextNULL，此，此时时j=n; (i与与j肯定不相等肯定不相等)(3) 若若1=inext !=NULL & jnext; j+; if (i=j&i!=0) return(p); else return(NULL); 按序号查找链表数据元素算法

44、一按序号查找链表数据元素算法一还有其他的表示方法吗？Int Getelem(linklist l,int I, int *e)P=L-next;J=1;While(p & jnext; +j; If (!p | ji) return -1;E=p-data;Return 1;算法二：算法二： 2.3.3线性链表的基本运算线性链表的基本运算 按值查找操作按值查找操作算法分析算法分析从链表的第一个结点起，判断当前结点值是否等于从链表的第一个结点起，判断当前结点值是否等于x，若是，返回该结，若是，返回该结点的指针；否则继续判断后一个，直到表结束，找不到时返回空。点的指针；否则继续判断后一个，直到表结

45、束，找不到时返回空。 ListNode *Locate_Linklist(LinkList Llist,Elemtype x) ListNode *p; p=Llist-next; /* 设置初值设置初值 */ while (p!=NULL & p-data!=x) p=p-next; /*未达到尾结点，又未找到值等于未达到尾结点，又未找到值等于x的结点时，继续找的结点时，继续找*/ return(p); /* 找到值为找到值为x的结点，返回它的地址的结点，返回它的地址 */ 查找算法的时间复杂度均为查找算法的时间复杂度均为O(n)算法算法 (1) 分配时由于向量空间大小在声明时确定，当分配时

46、由于向量空间大小在声明时确定，当L-length=MAXSIZE时，表空间已满，不可再时，表空间已满，不可再做插入操作；做插入操作；(2) 当插入位置当插入位置i的值为的值为in+1或或i1时为非法位时为非法位置，不可做正常插入操作；置，不可做正常插入操作；(3) 移动元素时是整体自下而上的顺序；移动元素时是整体自下而上的顺序； (4) length值增值增1；4. 插入操作插入操作在顺序表的插入算法中需考虑问题：在顺序表的插入算法中需考虑问题：链表的插入算法与顺序表插入算法相比较：（1）不存在“表满”（2）插入位置合理性判断1=inext=p-next; p-next=s; 2.3.3线性链

47、表的基本运算线性链表的基本运算注意注意两个指针的操作顺序不能交换，否则两个指针的操作顺序不能交换，否则p结点后面的结点将被断开，不能结点后面的结点将被断开，不能实现正确插入。实现正确插入。在第在第i位置之前插入一个值为位置之前插入一个值为x的结点，算法如下：的结点，算法如下：Int insert_LinkList(LinkList head, int i, Elemtype e) P=head; j=0;While(P & jnext;+j;If(!p|ji-1) return -1;S=(linklist )malloc(sizeof(listnode);S-data=e;S-next=p-

48、next;P-next=s;Return 1; 2.3.3线性链表的基本运算线性链表的基本运算5. 链表中删除结点链表中删除结点在顺序表中删除算法需考虑问题：在顺序表中删除算法需考虑问题：(1)如果需如果需ai，应先返回，应先返回ai的值的值(2)检查要删除位置的有效性，检查要删除位置的有效性，1in (3)当表空时不能做删除当表空时不能做删除(4)移动元素时是整体自上而下的顺序移动元素时是整体自上而下的顺序(5) length值减值减1；在链表中删除算法需考虑问题：在链表中删除算法需考虑问题：(1)如果需如果需ai，应先返回，应先返回ai的值的值(2)检查要删除位置的有效性，检查要删除位置的

49、有效性，1in (3)当表空时不能做删除当表空时不能做删除(4)不需要移动元素不需要移动元素(5)不需要设不需要设Length值值(6)删除的结点空间用删除的结点空间用free释放释放设设s指向单链表中某个结点，删除指向单链表中某个结点，删除s，首先要找到，首先要找到s的前驱结的前驱结点点p，指针操作由下：，指针操作由下：p-next=s-next;free(s);a1ai+1anheadai-1aip 2.3.3线性链表的基本运算线性链表的基本运算s删除链表中第删除链表中第i个结点的基本步骤如下：个结点的基本步骤如下： 找到第找到第i-1个结点；若存在，继续进行，否则结束。个结点；若存在，继

50、续进行，否则结束。 若存在第若存在第i个结点，则继续个结点，则继续，否则结束。，否则结束。 删除第删除第i个结点，结束。个结点，结束。 2.3.3线性链表的基本运算线性链表的基本运算删除链表中第删除链表中第i个结点的算法如下：个结点的算法如下：int del_LinkList(LinkList pList,int i) Listnode *p,*q;int j;p=pList;j=0;while(*p).next!=NULL & ji-1) return ERROR;q=(*p).next;(*p).next=(*q).next;free(q);return OK; 2.3.3线性链表的基本运

51、算线性链表的基本运算 2.3.3线性链表的基本运算线性链表的基本运算练习：已知已知L是带表头结点的非空单链表，且是带表头结点的非空单链表，且P结点结点既不是首元结点，也不是尾元结点，试从既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。下列提供的答案中选择合适的语句序列。a.删除删除P结点的直接后继结点的语句序列是结点的直接后继结点的语句序列是b.删除删除P结点的直接前驱结点的语句序列是结点的直接前驱结点的语句序列是_c.删除删除P结点的语句序列是结点的语句序列是_d.删除首元结点的语句序列是删除首元结点的语句序列是_e.删除尾元结点的语句序列是删除尾元结点的语句序列是_

52、(1) P=Pnext;(2) Pnext=P;(3) Pnext=Pnextnext;(4) P=Pnextnext;(5) While(P!=NULL) P=Pnext;(6) While (Qnext!=NULL) P=Q; Q=Qnext；(7) While (Pnext!=Q) P=Pnext;(8) While (Pnextnext!=Q) P=Pnext;(9) While (Pnextnext!=NULL) P=Pnext;(10) Q=P;(11) Q=Pnext;(12) P=L;(13) L=L next;(14) free(Q);由此可知：要删除的结点为Q结点练习：a.

53、删除P结点的直接后继结点的语句序列是 （11）（3）（14）b.删除P结点的直接前驱结点的语句序列是_ (10) (12) (8) (11) (3) (14)c.删除P结点的语句序列是_ (10) (12) (7) (3) (14)d.删除首元结点的语句序列是_ (12) (10) (11) (3) (14)e.删除尾元结点的语句序列是_ (9) (11) (3) (14) 或 (10)/(11) (6) (3) (14)简述下列算法的功能简述下列算法的功能 int A(Linklist L) L为不带头结点的链表为不带头结点的链表 if (L & L next) Q=L; L=L next;

54、 P=L; while (P next) P=P next; P next=Q; Q next=NULL; return(1); 如果如果L的长度不小于的长度不小于2，则将首元结点删掉并插入到表尾。，则将首元结点删掉并插入到表尾。 2.3.3补充补充 2.3.3补充补充354728867935473528473586284735在链表头部插入建立单链表在链表头部插入建立单链表 2.3.3补充补充建立单链表算法建立单链表算法 LinkList Creat_LinkList1() LinkList L; ListNode *p; int a; int flag; L=NULL; scanf(“ %

55、d ”,&a); while (a != flag) p=(Lnode *) malloc (sizeof(Lnode); p-data=a; p-next=L; L=p; scanf(“ %d ”,&a); return L; 2.3.3补充补充 2.3.3补充补充353535353547472847288647288679在链表尾部插入建立单链表在链表尾部插入建立单链表headheadheadheadheadheadrearrearrearrearrearrear 2.3.3补充补充建立单链表算法建立单链表算法 LinkList Creat_LinkList2() LinkList L;

56、ListNode *p,*rear; int a; int flag; L=rear=NULL; scanf(“ %d ”,&a); while (a != flag) p=(Lnode *) malloc (sizeof(Lnode); p-data=a; if (L=NULL) L=p;/*处理第一个结点处理第一个结点*/ else rear-next=p;/*其它结点的处理其它结点的处理*/ rear=p;/*指向新的尾结点指向新的尾结点*/ scanf(“ %d ”,&a); if (rear != NULL) rear-next=NULL; return L; 2.3.3补充补充he

57、ad 2.3.4循环链表及运算循环链表及运算a1a2anheada1a2anhead 2.3.4循环链表及运算循环链表及运算单循环链表的连接单循环链表的连接 LinkList connect(LinkList ra,rb) ListNode *p; p=ra-next; ra-next=rb-next-next; free(rb-next); rb-next=p; return(rb); 2.3.4循环链表及运算循环链表及运算priordatanext 2.3.5双向链表及运算双向链表及运算a1a2anpheadhead 2.3.5双向链表及运算双向链表及运算 2.3.5双向链表及运算双向链表

58、及运算pxs 2.3.5双向链表及运算双向链表及运算（4）放到最后面是最保险的）放到最后面是最保险的请同学们写出当请同学们写出当p指指向第向第i-1个结点时的个结点时的操作操作 2.3.5双向链表及运算双向链表及运算算法：带头结点的双向链表算法：带头结点的双向链表L的第的第i个位置上插入值为个位置上插入值为x的元素。的元素。 int insert_DubList(DulList L,int i,Elemtype x) if(!(p=GetElem_DuL(L,i) return ERROR; if (!(s=(DulList)malloc(sizeof(DulNode) return ERROR; s-data=x; s-prior=p-prior; p-prior-next=s; s-next=p; p-prior=s; return(