数据结构-基于C语言的描述第2版课件 第2章 线性表

DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO

线性结构基本特征：在数据元素非空有限集合中：有且只有一个“第一个元素”；有且只有一个“最后一个元素”；除第一个元素外，其他元素都有唯一的直接前驱；除最后一个元素之外，其他元素都有唯一的直接后继。第2章主要内容线性表第章2《数据结构–基于C语言的描述》（第2版）-清华大学出版社DATASTRUCTUREDATASTRUCTUREDataStructureBYPENGBO第2章主要内容2.1

线性表的类型定义2.2

线性表顺序表示及操作实现2.3

线性表链式表示及操作实现2.4

线性表两种存储表示的比较线性表第章2《数据结构–基于C语言的描述》（第2版）-清华大学出版社2.1线性表的类型定义

线性表是最简单、最基本及最常用的一种线性结构。它的主要基本操作是插入操作、删除操作和查找操作等。

●

英文字母表(A,B,…,X,Y,Z)是一个线性表，每个字母是一个元素。

●

扑克牌点数(2,3,…,10,J,Q,K,A)是一个线性表，每个点数是一个元素。

2.1线性表的类型定义2.1.1线性表的定义

●

学生成绩表是一个线性表，每个学生对应行信息是一个元素，由姓名、学号、性别、成绩共四个数据项组成。

学号姓名性别成绩001孙一男95002钱二女85003常三女90004吴四男88……………………DataStructureBYPENGBO2.1线性表的类型定义2.1.1线性表的定义

线性表是n(n≥0)个具有相同属性元素的有限序列，即表中的元素属于同一个数据对象，且相邻的元素之间存在着“序偶”关系。

●

元素个数n称为线性表的长度（n=0时称为空表）；

●将非空线性表(n>0)记为：(a1,a2,…,ai,…,an)；

●

元素ai(1≤i≤n)只是个抽象符号，具体含义在不同情况下不同。DataStructureBYPENGBOADTList{Data：D={ai|ai

ElemSet,i=1,2,…,n,n≥0}（具有相同类型的元素集合）

Relation：R={<ai-1,ai>|ai-1,ai

D,i=2,…,n}（相邻元素具有前驱和后继的关系）2.1线性表的类型定义2.1.2线性表的抽象数据类型

Operation： InitList(&L)初始条件：无操作结果：构造一个空线性表L。…………ListInsert(&L,i,e)初始条件：线性表L已经存在，且1≤i≤ListLength(L)+1。操作结果：在L中第i个位置之前插入新的元素e。

ListDelete(&L,i,&e)初始条件：线性表L已经存在，且1≤i≤ListLength(L)。操作结果：删除L的第i个元素，并用e返回其值，且令L的长度减1。

…………}ADTList

对于不同的实际应用，ADT中基本操作的接口可能不同。例如：ListDelete(&L,i)又如：ListDelete(&L,&e)

在ADT这一层次上研究问题可以避开技术细节，面向应用，深入讨论问题。

2.2线性表的顺序表示及操作实现

线性表有两种存储表示方法：一种是顺序存储表示，另一种是链式存储表示；而顺序存储表示又是计算机中最简单、最常用的一种存储方式。2.2线性表的顺序表示及操作实现2.2.1顺序表的定义

把线性表中元素按其逻辑次序依次存放在一组地址连续存储单元里，采用这种存储结构的线性表称为顺序表。a1a2aian内存状态12in2.2线性表的顺序表示及操作实现2.2.1顺序表的定义●顺序表中数据元素的存储地址

不失一般性，设线性表中所有元素具有相同的属性，因此占用的存储空间也相同。假设线性表中每个元素占用d个存储单元，第1个元素的起始地址为LOC(a1)，则：

第2个元素的起始地址为：

LOC(a2)=LOC(a1)+d

……

第i个元素的起始地址为：

LOC(ai)=LOC(a1)+(i-1)

d （i=1,2,3,…,n）因此，线性表中第n个元素an

的起始地址为：

LOC(an)=LOC(a1)+(n-1)

d （1≤i≤n）

定位公式顺序表是一种随机存取结构

2.2线性表的顺序表示及操作实现2.2.1顺序表的定义●顺序表中数据元素的存储地址顺序表示意图12in空闲LOC(a1)LOC(a1)+dLOC(a1)+(i-1)dLOC(a1)+(n-1)d顺序表最大空间a1a2aian存储地址内存状态元素在线性表中位序2.2线性表的顺序表示及操作实现2.2.1顺序表的定义●顺序表的类型定义#defineLIST_INIT_SIZE 100 //线性表存储空间的初始分配量#defineLIST_INCREMENT 10 //线性表存储空间的分配增补量typedefstruct{ElemType *elem; //线性表存储空间基地址int length; //线性表当前长度int listsize; //当前分配的存储容量（以ElemType为单位）}SqList;

顺序表是用一维数组实现的线性表，数组下标看作元素在内存的相对地址，因此顺序表最大特点是逻辑上相邻的元素在物理位置上也相邻。特点

（1）分配线性表存储空间，如果分配失败，则给出错误信息；（2）设置线性表当前长度为0。

（3）设置线性表的当前存储容量为顺序表的最大容量。初始化顺序表操作结束2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●初始化操作设计L.elemLIST_INIT_SIZE内存L.length=0L.listsize=LIST_INIT_SIZE2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●初始化操作算法2-1voidInitList_Sq(SqList&L){//构造一个最大容量为LIST_INIT_SIZE的顺序表LL.elem=newElemType[LIST_INIT_SIZE];if(!L.elem)Error("Overflow!"); //存储分配失败L.length=0;L.listsize=LIST_INIT_SIZE;}//InitList_SqvoidError(char*s){//出错信息处理函数，用于处理异常情况

cout<<s<<endl;exit(1);}//Error

使算法正常转到用户界面的环境，而不至于转到操作系统的意外状态。

一般情况下，一个没有循环的算法，时间复杂度O(1)。（1）释放顺序表所占用的存储空间；（2）设置顺序表当前长度为0；（3）设置线性表存储容量为0。销毁顺序表操作结束内存a1a2a3an2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●销毁操作设计L.elemList_SizeL.length=0L.listsize=02.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●销毁操作voidDestroyList_Sq(SqList&L){//释放顺序表L中元素所占用的存储空间delete[]L.elem;L.length=0;L.listsize=0;}//DestroyList_Sq算法2-2时间复杂度O(1)。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●清空操作设计重新设置线性表为空表，即令表的长度为0，但不释放掉该表所占用的存储空间。算法2-3voidClearList_Sq(SqList&L){//重置顺序表L为空表L.length=0;}//ClearList_Sq时间复杂度O(1)。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●求表长操作设计直接返回顺序表中的长度域值。算法2-4intListLength_Sq(SqListL){//返回顺序表L的长度returnL.length;}//ListLength_Sq时间复杂度O(1)。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●取值操作设计（1）判断取元素值操作所要求的相关参数是否合理，如果不合理，则给出错误信息；（2）返回线性表中待取元素值。算法2-5voidGetElem_Sq(SqListL,inti,ElemType&e){//用e返回顺序表L中第i个元素值（1≤i≤L.length）//若参数不合理则给出相应信息并退出运行

if((i<1)||(i>L.Length)) //取元素值的参数不合理Error("PositionError!");e=L.elem[i-1];}//GetElem_Sq时间复杂度O(1)。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●定位操作设计（1）从顺序表的第一个元素起，依次和给定元素值进行比较，如果存在与其值相等的元素，则返回第1个相等元素的位序；（2）如果查遍整个顺序表都没有找到与其值相等的元素，则返回为0。intLocateElem_Sq(SqListL,ElemTypee){//查找并返回顺序表L中第1个与e相等的元素位序；若未找到则返回0i=1; //指示位序，初值为1p=L.elem //指向L第i个元素，初始指向首个元素while((i<=L.length)&&(*p++!=e))i++;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sq算法2-62.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●定位操作分析

①问题规模：线性表的“当前长度”（设值为n）；②基本操作：指示位置的变量加1（i++）；③时间分析：当i=1时，变量i加1操作的次数为0；当i=n时，变量i加1操作的次数为n-1；查找成功时的平均执行次数为(n-1)/2，查找不成功时的执行次数为n，因此时间复杂度为O(n)。

（1）检查用户插入参数是否合理，如果不合理，则给出错误信息并退出运行；

（2）判断当前存储空间是否已满：

方法1，如果已满，则停止系统运行并退出程序；

方法2，如果已满，则需要系统增加空间；

（3）将顺序表中原来第n个至第i个元素依次往后移动一个元素的位置；

（4）把新元素e插入在顺序表的第i个位置上；（5）修正顺序表长度。插入元素到顺序表结束2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●插入操作设计a1ai-1aiai+1an-1内存位置位序1i-1ii+1n-1空闲插入位置annanan-1an-2ai插入元素ee空闲n+1voidListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序表L中第i个位置前插入元素e；若插入位置不合理则给出相应信息并退出运行//i的合理值为1≤i≤L.length+1if((i<1)||(i>L.length+1))Error("PositionError!");2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●插入操作算法2-7if(L.length>=L.listsize)

Increment(L);voidIncrement(SqList&L){//为顺序表L扩充LIST_INCREMENT个数据元素的空间newlist=newElemType[L.listsize+LIST_INCREMENT];

//增加LIST_INCREMENT个存储分配if(!newlist)Error("Overflow!"); //存储分配失败for(i=0;i<L,length;i++)newlist[i]=L.elem[i]; //腾挪原空间中的数据到newlist中delete[]L.elem; //释放元素所占的原空间L.elemL.elem=newlist; //移交空间首地址L.listsize+=LIST_INCREMENT; //修改扩充后顺序表的最大空间}//Incrementq=&(L.elem[i-1]);for(p=&(L.elem[L.length–1]);p>=q;--p)*(p+1)=*p;*q=e;++L.length;}//ListInsert_Sq若当前存储空间已满，则增加空间。令指针q指向插入位置，依次后移元素在第i个位置中插入e，修正表长

①问题规模：线性表的“当前长度”（设值为n）；②基本操作：依次后移元素；③时间分析：

如果当前存储空间已满，则需要腾挪原空间中的数据到新空间newlist中，移动次数为n。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●插入操作a1ai-1aiai+1an-1内存位置位序1i-1ii+1n-1ann插入位置n+1e如果当前存储空间不满，最好情况分析分析

①问题规模：线性表的“当前长度”（设值为n）；②基本操作：依次后移元素；③时间分析：

如果当前存储空间已满，则需要腾挪原空间中的数据到新空间newlist中，移动次数为n。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●插入操作如果当前存储空间不满，a1ai-1aiai+1an-1内存位置位序i-1ii+1n-1ann插入位置a1ai-1aiai+1an-1an1n+1e最坏情况a1ai-1aiai+1an-1an分析2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●插入操作假设在表中任何合法位置(1≤i≤n+1)上插入元素概率均等，则有p1=p2=…=pn+1=1/(n+1)。后移元素的平均次数：综合考虑，该算法时间复杂度为O(n)。

①问题规模：线性表的“当前长度”（设值为n）；②基本操作：依次后移元素；③时间分析：

如果当前存储空间已满，则需要腾挪原空间中的数据到新空间newlist中，移动次数为n。如果当前存储空间不满，

（1）检查用户删除参数是否合理，如果不合理，则给出错误信息并退出运行；（2）将待删除元素的值赋给变量；

（3）将顺序表中原来第i+1个至第n个元素依次向前移一个元素位置；（4）修正顺序表的长度。删除顺序表中元素结束2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●删除操作设计a1ai-1aiai+1an-1内存位置位序1i-1ii+1n-1空闲要删除的元素ai+1ai+2annan空闲已删除元素aie=L.elem[i-1]2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●删除操作算法2-8依次前移元素将待删除元素的值赋给e，p指向待删除元素，q指向最后一个元素。voidListDelete_Sq(SqList&L,inti,ElemType&e){//删除顺序表L中第i个元素并用e返回其值；若删除位置不合理则给出信息并退出运行//i的合理值为1≤i≤L.lengthif((i<1)||(i>L.length))Error("PositionError!"); e=L.elem[i-1];p=&(L.elem[i-1]);q=L.elem+L.length–1;for(++p;p<=q;++p)*(p-1)=*p;--L.length;}//ListDelete_Sq修正表长2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●删除操作

①问题规模：线性表的“当前长度”（设值为n）；②基本操作：依次前移元素；③时间分析：a1ai-1aiai+1an-1内存位置位序1i-1ii+1n-1an删除位置n最好情况分析2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●删除操作分析

①问题规模：线性表的“当前长度”（设值为n）；②基本操作：依次前移元素；③时间分析：a1ai-1aiai+1an-1内存位置位序i-1ii+1n-1ann删除位置1a2aiai+1ai+2an最坏情况2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●删除操作分析

①问题规模：线性表的“当前长度”（设值为n）；②基本操作：依次前移元素；

不失一般性，假设在顺序表中任何合法位置(1≤i≤n)上删除元素概率均等，则有q1=q2=…=qn+1=1/n。因此，前移数据元素的平均次数：综合考虑，该算法时间复杂度为O(n)。③时间分析：2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●输出所有数据元素操作设计当顺序表L非空时，依次输出L中的所有元素。算法2-9voidTraverseList_Sq(SqListL){//依次输出顺序表L中的每个元素if(L.length!=0){i=1; //指示位序，初值为1p=L.elem //指向L第i个元素，初始指向首元素while(i<=L.length){ //依次输出L中的元素cout<<*p++;i++;}}}//TraverseList_Sq2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现●输出所有数据元素操作分析

①问题规模：线性表的“当前长度”（设值为n）；②基本操作：依次输出表中每个元素、位序增1；③时间分析：基本操作与问题规模成正比，时间复杂度为O(n)。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-1

将两个有序顺序表A和B合并为一个新有序顺序表C。设计（1）设有序顺序表C表长，即C.listsize=C.length=A.length+B.length。（2）设A.elem、B.elem、C.elem下标分别为i、j、k，且初始值均为0。（3）当i≤A.length且j≤B.length时，进行A和B合并：

若A.elem[i]≤B.elem[j]，则令C.elem[k]=A.elem[i]，并令i和k加1；

若A.elem[i]>B.elem[j]，则令C.elem[k]=B.elem[i]，并令j和k加1。（4）如果A有剩余元素，则将其插入到C；如果B有剩余元素，则将其插入到C。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-1

将两个有序顺序表A和B合并为一个新有序顺序表C。算法2-10voidMerge_Sq(SqListA,SqListB,SqList&C){//将两个有序顺序表A和B合成一个有序顺序表CC.length=A.length+B.length; //设C的表长C.elem=newElemType[C.length] //为C动态分配存储空间if(!C.elem)Error("Overflow!"); //存储分配失败

i=0;j=0;k=0;

while((i<A.length)&&(j<B.length)) //合并A和Bif(A.elem[i]<=B.elem[j]){C.elem[k]=A.elem[i];i++;k++;}else{C.elem[k]=B.elem[j];j++;k++;}2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-1

将两个有序顺序表A和B合并为一个新有序顺序表C。算法2-10while(i<A.length){ //插入A的剩余段C.elem[k]=A.elem[i];i++;k++;}while(j<B.length){ //插入B的剩余段C.elem[k]=B.elem[j];j++;k++;}}//Merge_Sq2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-1

将两个有序顺序表A和B合并为一个新有序顺序表C。分析①问题规模：表A“当前长度”（设值为n）与表B“当前长度”（设值为m）之和；②基本操作：元素赋值、下标修改；③时间分析：执行时间主要花费在三个while循环基本操作上，执行的总次数为n+m，因此算法的时间复杂度为O(n+m)。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-2

插入元素e到递增顺序表L中且保证插入后表有序性不变。设计（1）如果顺序表L已满，则给出相应信息并退出运行；（2）从顺序表L的最后一个元素开始，依次向前寻找第一个小于或等于e的元素位置；在寻找过程中，由于大于e的元素都放在e之后，因此可以边寻找边后移元素，当找到第一个小于或等于e的元素时，该位置空出，将e插入该位置即可；（3）修正顺序表L的长度。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-2

插入元素e到递增顺序表L中且保证插入后表有序性不变。算法2-11voidIns_IncreaseList(Sqlist&L,ElemTypee){//插入e到递增顺序表L中，且保证插入后L的有序性不变//若L满则给出相应信息并退出运行if(L.length>=L.listsize)Error("LinearListOverflow!"); //L已满，给出相应信息for(i=L.length;(i>0)&&(L.elem[i-1]>e);i--)L.elem[i]=L.elem[i-1]; //比较并后移元素L.elem[i]=e; //插入e到L中L.length++; //修正L的长度，令其增1}//Ins_IncreaseList2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-2

插入元素e到递增顺序表L中且保证插入后表有序性不变。分析①问题规模：表L的“当前长度”（设值为n）；②基本操作：元素后移；③时间分析：基本操作的平均执行次数为n/2（分析参见算法2-7），因此算法的时间复杂度为O(n)。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-3

逆置顺序表L，且只在原表存储空间外增加一个附加空间。设计（1）设置m为顺序表L长度的一半，即m=

L.length/2

；（2）依次将L.elem[0]与L.elem[n-1]交换，L.elem[1]与L.elem[n-2]交换，……，L.elem[k]与L.elem[n-k-1]交换，直至完成顺序表中所有元素逆置。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-3

逆置顺序表L，且只在原表存储空间外增加一个附加空间。算法2-12voidInvert_Sq(SqList&L){//逆置顺序表Ln=L.length;m=n/2;for(i=0;i<m;i++){ //交换L.elem[i]与L.elem[n-i-1]temp=L.elem[i];L.elm[i]=L.elem[n-i-1];L.elem[n-i-1]=temp;}}//Invert_Sq2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-3

逆置顺序表L，且只在原表存储空间外增加一个附加空间。分析①问题规模：待逆置表L的“当前长度”（设值为n）；②基本操作：数据元素交换；③时间分析：执行时间主要花费在for循环的基本操作上，元素交换的次数为n/2，因此算法的时间复杂度为O(n)。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-4

调整顺序表L：使其左边所有元素均小于0，右边所有元素均大于或等于0。设计

（1）分配临时存储空间temp；

（2）将顺序表L中的所有元素依次和0比较：小于0的元素从temp[0]开始依次向右存放，大于或等于0的元素从temp[n-1]开始依次向左存放；

（3）将整理好的temp赋值到顺序表L，并销毁temp。2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-4

调整顺序表L：使其左边所有元素均小于0，右边所有元素均大于或等于0。算法2-13voidAdjust_Sq(SqList&L){//调整顺序表L：使其左边的所有元素均小于0，右边的所有元素均大于或等于0n=L.length;temp=newElemType[n];//分配临时存储空间tempif(!temp)Error(“Overflow!”);x=0;y=n-1;

for(i=0;i<n;i++) //将L中的元素依次和0比较if(L.elem[i]<0) //若<0，则元素从temp[0]开始向右存放

{temp[x]=L.elem[i];x++;}else //若≥0，则元素从temp[n-1]开始向左存放

{temp[y]=L.elem[i];y--;}

for(i=0;i<n;i++)L.elem[i]=temp[i];//将整理好的temp腾挪到L中delete[]temp;

//销毁临时存储空间temp}//Adjust_Sq2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现2.2线性表的顺序表示及操作实现2.2.2顺序表的操作实现例2-4

调整顺序表L：使其左边所有元素均小于0，右边所有元素均大于或等于0。分析①问题规模：待调整表L的“当前长度”（设值为n）；②基本操作：元素赋值；③时间分析：执行时间主要花费在两个for循环的基本操作上，元素赋值的次数均为n，因此算法的时间复杂度为O(n)。2.3线性表的链式表示及操作实现

在顺序表中插入或删除一个元素，需要对插入或删除点后面的全部元素逐个进行移动，操作不便，特别是当元素信息量较多时，移动元素的时间开销相当可观。线性表链式存储结构可以克服顺序表的不足。

2.3线性表的链式表示及操作实现2.3.1单链表的定义

线性表中的一个元素由数据域和指针域（指向其后继）组成，称为结点。datanext数据域指针域单链表的结点结构

存储线性表中一个元素的元素信息。

存储直接后继元素的内存地址。通过每个结点的指针保存线性表元素逻辑关系，采用这种存储结构的线性表称为链表。每个结点只有一个指针域的链表称为单链表。单链表是一种顺序存取结构

2.3线性表的链式表示及操作实现2.3.1单链表的定义

例如：线性表(5,8,9,21,4,19,15,17)的单链表如下。

整个链表的存取必须从头指针Head开始进行，头指针指示链表中第一个结点的存储地址。

由于最后一个元素没有后继元素，所以最后一个结点中的“指针”为空，是一个特殊值“NULL”（在图上用“∧”表示），称为“空指针”。∧Head589214191517∧单链表的逻辑状态5172.3线性表的链式表示及操作实现2.3.1单链表的定义●单链表的头结点和头指针非空表空表空表的头结点指针域为“空”

在单链表第一个结点之前附加一个同结构的结点，称为头结点。指向头结点的指针称为头指针。typedefstruct{ElemType data; //数据域structLNode *next; //指针域}LNode;typedefLNode*LinkList;2.3线性表的链式表示及操作实现2.3.1单链表的定义●单链表的类型定义LinkList和LNode*是不同名字的同一个指针类型。LinkList类型的指针变量表示是单链表的头指针，LNode*类型的指针变量表示是指向某一结点的指针。

在单链表中，结点之间的逻辑关系由结点中指针指示，逻辑上相邻的两个结点物理位置不要求相邻，因此单链表不是随机存取结构。

特点LinkListLNode*（1）生成一个新结点作为头结点；（2）设置头结点的指针域为空。初始化单链表操作结束2.3线性表的链式表示及操作实现2.3.2单链表的操作实现设计●初始化操作L∧2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●初始化操作voidInitList_L(LinkList&L){//构造一个空单链表LL=newLNode;L->next=NULL;}//InitList_L时间复杂度O(1)。算法2-14

从头结点开始依次释放单链表每一个结点所占用的存储空间。

销毁单链表操作结束2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●销毁操作设计La1aian∧a2pppppL空while(L){p=L;L=L->next;deletep;}L空2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●销毁操作voidDestroyList_L(LinkList&L){//释放单链表L所占用的存储空间while(L){p=L;L=L->next;deletep;}}//DestroyList_L算法2-15分析①问题规模：线性表“当前长度”，即单链表结点个数（设值为n）；②基本操作：指针后移、释放结点存储空间；③时间分析：执行时间主要花费在while循环的基本操作上，执行次数为n+1，因此算法的时间复杂度为O(n)。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●销毁操作2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●清空操作设计

（1）从单链表第一个结点开始依次释放表中每个结点所占用的存储空间；

（2）令头结点指针域为空。voidClearList_L(LinkList&L){//清空单链表L，释放所有结点空间，保留头结点p=L->next;while(p){q=p;p=p->next;deleteq;}L->next=NULL;}//ClearList_L算法2-162.3线性表的链式表示及操作实现2.3.2单链表的操作实现●清空操作分析①问题规模：线性表“当前长度”，即单链表结点个数（设值为n）；②基本操作：指针后移、释放结点存储空间；③时间分析：执行时间主要花费在while循环的基本操作上，执行次数为n，因此算法的时间复杂度为O(n)。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●求表长操作设计

（1）设置一个指针，初始时指向单链表的头结点；（2）设置一个计数器，初始时为0；

（3）通过指针顺链表向后扫描：如果指针不空，则令计数器加1，且令指针指向其后继结点，如此循环直至指针为“空”止。intListLength_L(LinkListL){//顺单链表L向后扫描，依次访问结点，计数得到L的长度，并返回其值p=L; //设置指针，初始指向L的头结点length=0; //设置计数器length初始为0while(p->next) //顺表向后扫描，计算表长

{length++;p=p->next;}returnlength;}//ListLength_L算法2-172.3线性表的链式表示及操作实现2.3.2单链表的操作实现●求表长操作分析①问题规模：线性表“当前长度”，即单链表结点个数（设值为n）；②基本操作：计数器加1、指针后移；③时间分析：执行时间主要花费在while循环中的基本操作上，执行次数为n，因此算法的时间复杂度为O(n)。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●取值操作设计

（1）设置一个指针，初始时指向单链表的第一个结点；

（2）设置一个计数器，初始时为1；

（3）通过指针顺链表向后扫描，判断取元素值操作所要求的相关参数是否合理，如果不合理，则给出错误信息；

（4）取结点数据域中的值并返回。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●取值操作voidGetElem_L(LinkListL,inti,ElemType&e){//用e返回单链表L中第i个结点的数据域值；若i值不合理，则给出相应信息并退出运行//i的合理值为1≤i≤表长p=L->next; //设置指针，初始时指向L的第一个结点j=1; //设置计数器，初始时为1while(p&&(j<i)){ //顺链向后扫描p=p->next;++j;}if(!p||(j>i))Error("PositionError!");elsee=p->data; }//GetElem_L算法2-182.3线性表的链式表示及操作实现2.3.2单链表的操作实现●取值操作分析①问题规模：线性表“当前长度”，即单链表结点个数（设值为n）；②基本操作：指针后移、计数器加1；③时间分析：执行时间主要花费在while循环的基本操作上。当取结点值的参数i合理时，其平均执行次数为(n-1)/2；当取结点值的参数i大于L的长度时，其执行次数为n。因此算法的时间复杂度为O(n)。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●定位操作设计

（1）设置一个指针，初始时指向单链表的第一个结点；

（2）从第一个结点起，通过指针顺链表向后扫描，依次将结点数据域值和给定元素值相比较：

如果存在与其值相等的结点，则返回第一个相等的结点指针；

如果整个单链表都不存在这样一个结点，则返回空指针“NULL”。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●定位操作LNode*LocateElem_L(LinkListL,ElemTypee){//查找单链表L中第一个数据域值和e相等的结点//若存在则返回其指针；若不存在则返回NULLp=L->next; //设置指针，初始时指向L第一个结点while(p&&(p->data!=e)) //顺链向后扫描p=p->next;returnp;}//LocateElem_L算法2-192.3线性表的链式表示及操作实现2.3.2单链表的操作实现●定位操作分析①问题规模：线性表“当前长度”，即单链表结点个数（设值为n）；②基本操作：指针后移；③时间分析：执行时间主要花费在while循环中的基本操作上。当存在与给定元素值相等的结点时，其平均执行次数为(n-1)/2；当不存在与给定元素值相等的结点时，其执行次数为n。因此算法的时间复杂度为O(n)。

（1）通过指针顺链向后扫描寻找第i-1个结点，检查插入参数i是否合理，若否则给出错误信息并退出运行；

（2）生成一个数据域值为e的结点；

（3）将该结点插入第i-1和i个结点间。

2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●插入操作设计La1aian∧ai-1pse在单链表中插入结点操作结束s->next=p->nextp->next=sp=L;j=0;while(p&&(j<i-1)){p=p->next;++j;}1≤i≤表长+12.3线性表的链式表示及操作实现2.3.2单链表的操作实现●插入操作else{s=newLNodes->data=e;s->next=p->next;p->next=s;}}//LinkInsert_L在L中顺链向后扫描寻找第i-1个结点voidListInsert_L(LinkList&L,inti,ElemTypee){//在单链表L中第i个位置前插入值为e的结点；若插入位置不合理则给出信息并退出运行//i的合理值为1≤i≤表长+1p=L;j=0;while(p&&(j<i-1)){p=p->next;++j;}if(!p||(j>i-1))Error("PositionError!");若插入位置合理则完成插入若插入位置不合理则给出信息并退出运行算法2-202.3线性表的链式表示及操作实现2.3.2单链表的操作实现●插入操作分析最好：i=1，指针后移次数为0最坏：i=n+1，指针后移次数为n①问题规模：线性表“当前长度”，即单链表结点个数（设值为n）；②基本操作：指针后移等；③时间分析：执行时间主要花费在while循环中的基本操作上。插入成功时的平均执行次数为n/2，插入不成功时的执行次数为n。等概率情况下平均执行次数为=n/2。因此算法的时间复杂度为O(n)。

（1）通过指针顺链向后扫描寻找第i-1个结点，检查删除参数i是否合理，若否则给出错误信息并退出运行；（2）设置一个指针指向被删除结点，为删除后释放结点做准备；

（4）删除第i个结点；

（5）释放第i个结点空间。

在单链表中删除结点操作结束p=L;j=0;while((p->next)&&(j<i-1)){p=p->next;++j;}p->next=q->next2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●删除操作设计La1ai+1an∧ai-1aipq（3）取出第i个结点值；

e=q->data1≤i≤表长voidListDelete_L(LinkList&L,inti,ElemType&e){//删除单链表L第i个结点，用e返回其数据域值；若删除位置不合理则给出信息并退出运行//i的合理值为1≤i≤表长p=L;j=0;while((p->next)&&(j<i-1)){p=p->next;++j;}q=p->next;e=q->data;p->next=q->next;deleteq;}//LinkDelete_L2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●删除操作若删除位置不合理则给出信息并退出运行在L中顺链向后扫描寻找第i-1个结点if(!(p->next)||(j>i-1))Error("PositionError!");若删除位置合理则完成删除并释放结点空间算法2-212.3线性表的链式表示及操作实现2.3.2单链表的操作实现●删除操作分析最好：i=1，指针后移次数为0最坏：i=n，指针后移次数为n-1

①问题规模：线性表“当前长度”，即单链表结点个数（设值为n）；②基本操作：指针后移等；③时间分析：执行时间主要花费在while循环中的基本操作上。删除成功时的平均执行次数为(n-1)/2，删除不成功时的执行次数为n。等概率情况下平均执行次数为

=n/2。因此算法的时间复杂度为O(n)。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●输出所有数据元素操作设计当单链表非空时，从第一个结点开始，顺链表向后扫描，依次输出表中每个结点数据域的值。算法2-22voidTraverseList_L(LinkListL){//依次输出单链表L中每个结点数据域的值p=L->next;while(p){cout<<p->data;p=p->next;}}//TraverseList_L2.3线性表的链式表示及操作实现2.3.2单链表的操作实现●输出所有数据元素操作分析①问题规模：线性表“当前长度”，即单链表结点个数（设值为n）；②基本操作：依次输出表中每个元素、指针后移；③时间分析：基本操作与问题规模成正比，因此时间复杂度为O(n)。（1）初始化一个空单链表；

（2）生成一个结点，按照逆序读入数据，并将其存入结点数据域；（3）将该结点插入到单链表中；

（4）依次建立各元素结点，并逐个插入到单链表中；逆序创建单链表完成2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-5

逆序创建单链表。设计L∧pan∧pan-1pan-2pa1p->next=L->next;L->next=p;2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-5

逆序创建单链表。voidCreateList_L(LinkList&L,intn){//按照逆序输入n个元素的值，从表尾到表头逆向建立单链表LInitList_L(L); //建立一个空链表Lfor(i=n;i>0;--i){p=newLNode; //生成一个新结点cin>>p->data; //读入数据到新结点数据域p->next=L->next; //插入新结点到L中L->next=p; //头结点指针指向新结点}}//CreateList_L算法2-232.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-5

逆序创建单链表。分析①问题规模：待输入的元素个数n；②基本操作：建立结点并插入到单链表中；③时间分析：执行时间主要花费在for循环的基本操作上，执行次数为n，因此算法的时间复杂度为O(n)。思考：如何正序创建单链表2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-6

将两个有序单链表La和Lb合并为一个有序单链表Lc且Lc和La共用一个表头。设计

（1）设置初始状态。当La和Lb非空时，指针pa和pb分别指向La和Lb中第一个结点；Lc和La共用一个表头，故指针pc指向La头结点。

（2）将La和Lb合并为Lc，有两种情况：如果pa->data≤pb->data，则将pa所指向的结点链接到pc所指向的结点之后，同时修改pc和pa；如果pa->data＞pb->data，则将pb所指向的结点链接到pc所指向的结点之后，同时修改pc和pb。

（3）插入剩余段：如果一个单链表的元素已经合并完，则将另一个单链表的剩余元素段链接在pc所指结点之后；

（4）释放单链表Lb的头结点。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-6

将两个有序单链表La和Lb合并为一个有序单链表Lc且Lc和La共用一个表头。voidMerge_L(LinkListLa,LinkListLb,LinkList&Lc){//将两个有序单链表La和Lb合成一个有序单链表Lc，且Lc和La共用一个表头pa=La->next;pb=Lb->next;Lc=pc=La; //Lc和La共用一个表头算法2-24

while(pa&&pb)if(pa->data<=pb->data) //如果pa->data≤pb->data

{

pc->next=pa;pc=pa;pa=pa->next;}else //如果pa->data>pb->data

{pc->next=pb;pc=pb;pb=pb->next;}

pc->next=pa?pa:pb; //插入剩余段deleteLb; //释放Lb头结点的存储空间}//Merge_L2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-6

将两个有序单链表La和Lb合并为一个有序单链表Lc且Lc和La共用一个表头。分析①问题规模：待合并的两个有序单链表的“长度和”（设La表长为n，Lb表长为m）；②基本操作：修改指针；③时间分析：执行时间主要花费在while循环的基本操作上，执行次数最多为n+m，因此算法的时间复杂度为O(n+m)。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-7

一元多项式的表示及相加。

一元多项式按其升幂表示为：A(x)=a0+a1x+a2x2+……+anxn，它由n+1个系数唯一确定。可以用一个线性表(a0,a1,a2,…,an)表示，每一项的指数i隐含在其系数ai的序号里。

有

A(x)=a0+a1x+a2x2+……+anxn和B(x)=b0+b1x+b2x2+……+bmxm，一元多项式求和即为求A(x)=A(x)+B(x)，实质上是一个合并同类项的过程。

在实际应用中，只存储非零系数元素，每一个非零系数项可以由系数和指数唯一表示。例如，S(x)=5+10x30+90x100可以用线性表((5,0),(10,30),(90,100))来表示。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-7

一元多项式的表示及相加。

（1）一元多项式的存储表示：

采用链式存储结构，则每一个非零项对应单链表中的一个结点，且单链表应该按照指数递增有序排列。//修改2.3.1中定义的单链表类型定义：typedefstructLNode{float coef; //系数int expn; //指数structLnode*next; //指向下一个元素项的指针}LNode; typedefLNodePolynomial;设计

（2）一元多项式的相加操作：

两个单链表头指针分别为Pa和Pb。要求进行多项式加法：Pa=Pa+Pb，利用两个多项式结点构成“和多项式”，且“和多项式”与Pa共用一个头结点。

设指针p指向单链表Pa的第一个结点，指针q指向单链表Pb的第一个结点。两个多项式求和实质上是对p结点的指数域和q结点的指数域进行比较，有下面三种情况：2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-7

一元多项式的表示及相加。设计2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-7

一元多项式的表示及相加。设计

①如果p->expn<q->expn，则p结点应该为“和多项式”中的一个结点，将指针p后移。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-7

一元多项式的表示及相加。设计

②如果p->expn>q->expn，则q结点应该为“和多项式”中的一个结点，将q结点插入到单链表A中p结点之前，再将指针q后移。2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现2.3线性表的链式表示及操作实现2.3.2单链表的操作实现例2-7

一元多项式的表示及相加。设计

③如果p->expn=q->expn，则p与q所指结点为同类项，将q结点系数加到p结点系数上：

若相加结果不为0，则指针p后移，删除q结点；

若相加结果为0，则表明“和多项式”中无此项，删除p和q结点，并将指针p和q分别