【教学课件】第二章线性表.ppt

《【教学课件】第二章线性表.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第二章线性表.ppt（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第二章 线性表n n学习要点学习要点 n n了解线性表的逻辑结构是数据元素之间存在了解线性表的逻辑结构是数据元素之间存在着线性关系，在计算机中表示这种关系的两着线性关系，在计算机中表示这种关系的两种不同的存储结构是顺序存储结构和链式存种不同的存储结构是顺序存储结构和链式存储结构。储结构。n n熟熟练练掌掌握握线线性性表表的的两两种种存存储储结结构构，即即顺顺序序存存储结构和链式存储结构。储结构和链式存储结构。n n熟熟练练掌掌握握线线性性表表的的两两种种存存储储结结构构的的基基本本算算法法:查找、插入、删除等。查找、插入、删除等。2.1线性表的基本概念n n线性表的定义线性表是线性表是线性表是

2、线性表是nn个类型相同数据元素的有限序列，个类型相同数据元素的有限序列，个类型相同数据元素的有限序列，个类型相同数据元素的有限序列，Linear-list=(D,R)Linear-list=(D,R)其中：其中：其中：其中：D=aD=ai i|a|ai i datatype,i=0,1,n-1datatype,i=0,1,n-1R=aR=|a|ai i,a,ai+1i+1D,1in-1D,1in-1或记作（或记作（或记作（或记作（a a0 0,a,a1 1,a,a2 2,a,an-1n-1）。）。）。）。姓名 电话号码蔡颖63214444陈红63217777刘建平 63216666王小林 63

3、218888张力63215555.例1、数学中的数列（11，13，15，17，19，21）例2、英文字母表（A,B,C,D,EZ）。例3、某单位的电话号码簿。说明：说明：说明：说明：设设设设A=A=（a a0 0,a,a1 1,.,a,.,ai-1i-1,a,ai i,a,ai+1i+1,a,an-1n-1）是一线）是一线）是一线）是一线性表性表性表性表1)1)不同线性表中数据元素的类型可以是各种各样的，但同一线不同线性表中数据元素的类型可以是各种各样的，但同一线不同线性表中数据元素的类型可以是各种各样的，但同一线不同线性表中数据元素的类型可以是各种各样的，但同一线性表中的元素必须是性表中的元

4、素必须是性表中的元素必须是性表中的元素必须是同一类型同一类型同一类型同一类型的；的；的；的；2)2)在表中在表中在表中在表中a ai-1i-1 领先于领先于领先于领先于a ai i，a ai i 领先于领先于领先于领先于a ai+1i+1，称，称，称，称a ai-1i-1 是是是是a ai i 的直接前驱，的直接前驱，的直接前驱，的直接前驱，a ai+1i+1 是是是是a ai i 的直接后继；的直接后继；的直接后继；的直接后继；3)3)在线性表中，除第一个元素和最后一个元素之外，其他元素在线性表中，除第一个元素和最后一个元素之外，其他元素在线性表中，除第一个元素和最后一个元素之外，其他元素在

5、线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前驱，有且仅有一个直接后继，这是都有且仅有一个直接前驱，有且仅有一个直接后继，这是都有且仅有一个直接前驱，有且仅有一个直接后继，这是都有且仅有一个直接前驱，有且仅有一个直接后继，这是所有所有所有所有线性结构线性结构线性结构线性结构的共同特征。线性表是一种线性数据结构；的共同特征。线性表是一种线性数据结构；的共同特征。线性表是一种线性数据结构；的共同特征。线性表是一种线性数据结构；4)4)线性表中元素的个数线性表中元素的个数线性表中元素的个数线性表中元素的个数nn称为称为称为称为线性表的长度线性表的长度线性表的长度线性表的长度，

6、n=0n=0时称空表；时称空表；时称空表；时称空表；5)a5)ai i是线性表的第是线性表的第是线性表的第是线性表的第i+1i+1个元素，称个元素，称个元素，称个元素，称i+1i+1为数据元素为数据元素为数据元素为数据元素a ai i 的序号，每的序号，每的序号，每的序号，每一个元素在线性表中的位置，仅取决于它的序号；一个元素在线性表中的位置，仅取决于它的序号；一个元素在线性表中的位置，仅取决于它的序号；一个元素在线性表中的位置，仅取决于它的序号；线性表的其他表示方式线性表的其他表示方式线性表的其他表示方式线性表的其他表示方式二元组表示二元组表示二元组表示二元组表示L=D,SL=，其中，其中，

7、其中，其中D=aD=a0 0,a,a1,1,a a2,2,.a.an-1n-1 S=RR=aS=RR=,a图示表示图示表示图示表示图示表示a ai i+1a a0a ai-i-1a a1 1a ai ia an-n-1顶点：表示一个数据元素顶点：表示一个数据元素边：表示是数据间的顺序结构关系边：表示是数据间的顺序结构关系n n线性表的基本操作n n初始化操作初始化操作初始化操作初始化操作：InitiateInitiate（L L）设定一个空的线性表设定一个空的线性表设定一个空的线性表设定一个空的线性表LL；n n求长度函数求长度函数求长度函数求长度函数：LengthLength（L L）求线性

8、表求线性表求线性表求线性表L L中数据元素的个数中数据元素的个数中数据元素的个数中数据元素的个数；n n查找函数查找函数查找函数查找函数：GetGet（L L,i i）取得线性表取得线性表取得线性表取得线性表L L的第的第的第的第i i个数据元素个数据元素个数据元素个数据元素；n n定位函数定位函数定位函数定位函数：LocateLocate（L L,x x）求数据元素求数据元素求数据元素求数据元素x x在线性表在线性表在线性表在线性表L L中的位置中的位置中的位置中的位置；n n插入操作插入操作插入操作插入操作：InsertInsert（L L,i i,x x）在线性表中第在线性表中第在线性表

9、中第在线性表中第i i个位置插入一个数据元素个位置插入一个数据元素个位置插入一个数据元素个位置插入一个数据元素;n n删除操作删除操作删除操作删除操作：DeleteDelete（L L,i i）在线性表中第在线性表中第在线性表中第在线性表中第i i（0in-10in-1）个结点；）个结点；）个结点；）个结点；为了存储线性表，至少要保存两类信息：为了存储线性表，至少要保存两类信息：1）线性表中的数据元素；）线性表中的数据元素；2）线性表中数据元素的顺序关系；）线性表中数据元素的顺序关系；如何在计算机中存储线性表？如何在计算机中实现线性表的基本操作？2.22.2线性表的顺序存储结构线性表的顺序存储

10、结构 一、线性表的顺序存储结构顺序表线性表的顺序存储结构，就是用一组线性表的顺序存储结构，就是用一组连连续的续的内存单元内存单元依次依次存放线性表的数据元素。存放线性表的数据元素。a a0 0a a1 1a ai-1i-1a ai ia ai+1i+1a an-1n-1线性表（线性表（a0,a1,a2.an-1）的顺序存储结构的顺序存储结构用顺序存储结构存储的线用顺序存储结构存储的线性表性表称为顺序表称为顺序表说明：n n在顺序存储结构下，线性表元素在顺序存储结构下，线性表元素在顺序存储结构下，线性表元素在顺序存储结构下，线性表元素之间的逻辑关系，通过元素的存之间的逻辑关系，通过元素的存之间的

11、逻辑关系，通过元素的存之间的逻辑关系，通过元素的存储顺序反映（表示）出来，即逻储顺序反映（表示）出来，即逻储顺序反映（表示）出来，即逻储顺序反映（表示）出来，即逻辑关系相邻，物理位置也相邻；辑关系相邻，物理位置也相邻；辑关系相邻，物理位置也相邻；辑关系相邻，物理位置也相邻；n n 假设线性表中每个数据元素占用假设线性表中每个数据元素占用假设线性表中每个数据元素占用假设线性表中每个数据元素占用dd个存储单元，那么，在顺序存储个存储单元，那么，在顺序存储个存储单元，那么，在顺序存储个存储单元，那么，在顺序存储结构中，线性表的第结构中，线性表的第结构中，线性表的第结构中，线性表的第i i个元素的存个

12、元素的存个元素的存个元素的存储位置与第储位置与第储位置与第储位置与第1 1个元素的存储位置的个元素的存储位置的个元素的存储位置的个元素的存储位置的关系是：关系是：关系是：关系是：Loc(aLoc(ai-1i-1)=Loc(a)=Loc(a0 0)+(i1)+(i1)*d dd d个单元个单元Loc(a0)Loc(ai-1)a a0 0a a1 1a ai-1i-1a ai ia ai+1i+1a an-1n-1怎样在计算机上实现怎样在计算机上实现线性表的顺序存储结构？线性表的顺序存储结构？因为高级语言中的一维数组是采用顺序结构储存的，因此我们使用一维数组来表示线性表，数组的类型由线性表中的数据

13、元素的性质决定。顺序表的类型定义顺序表的类型定义#defineMaxnum200/*分配的顺序表总长度分配的顺序表总长度*/elementtypeelementMaxnum；/*定义元素类型数组定义元素类型数组*/intn；/*当前顺序表存储数据的个数当前顺序表存储数据的个数*/为了把线性表的表元素和当前长度整合作为该线性表的特性，为了把线性表的表元素和当前长度整合作为该线性表的特性，我们定义一个结构体如下：我们定义一个结构体如下：structsqlistelementtypeelementMaxnum;/*顺序表数组顺序表数组*/intn;/*当前线性表长度当前线性表长度*/;typedef

14、structsqlist*ptsqlist；设设A=（a0,a1,a2,.an-1）是一线性表，）是一线性表，L是是sqlist类型的结构变量，用于存放线性表类型的结构变量，用于存放线性表A，则，则L在内在内存中的状态如图所示：存中的状态如图所示：1 12 2i-1i-1i ii+1i+1n nL.elementiL.elementiL.nL.nn n存放线性表元素存放线性表元素的一维数组的一维数组顺序表通过顺序表通过顺序表通过顺序表通过元素的存储顺序元素的存储顺序元素的存储顺序元素的存储顺序反映线性表元素间的逻辑关系反映线性表元素间的逻辑关系反映线性表元素间的逻辑关系反映线性表元素间的逻辑关

15、系a a0 0a a1 1a ai-1i-1a ai ia ai+1i+1a an-1n-1二、顺序表的基本操作算法1.1.1.1.创建并初始化顺序表创建并初始化顺序表创建并初始化顺序表创建并初始化顺序表 2.2.2.2.在顺序表中查找下标为在顺序表中查找下标为在顺序表中查找下标为在顺序表中查找下标为i i i i的元素（的元素（的元素（的元素（0in-10in-10in-10in-1）并返回该）并返回该）并返回该）并返回该元素元素元素元素 3.3.3.3.顺序表的判空操作顺序表的判空操作顺序表的判空操作顺序表的判空操作 intEmpty(ptsqlistlist)iflist-n=0retu

16、rn(1);return(0);ptsqlistInitiate(void)ptsqlistlist;list=(ptsqlist)malloc(sizeof(structsqlist)if!listprintf(overflow!n);return(null);elselist-n=0;return(list);elementtypeGet(ptsqlistlist,inti)if(i=list-n)printf(notexistn);return(null);return(list-elementi);4.4.插入插入插入插入insert(L,i,x)insert(L,i,x)功能：功能：

17、功能：功能：在顺序表在顺序表在顺序表在顺序表L L L L中第中第中第中第i i i i个位置后插入一元素插入个位置后插入一元素插入个位置后插入一元素插入个位置后插入一元素插入一一一一个新个新个新个新元素元素元素元素x,x,x,x,插入前线性表为插入前线性表为插入前线性表为插入前线性表为 (a(a(a(a0 0 0 0,a,a,a,a1 1 1 1,a,a,a,a2 2 2 2,a,a,a,ai-1i-1i-1i-1,a,a,a,ai i i i,a,a,a,an-1 n-1 n-1 n-1)插入后插入后插入后插入后,线性表长度为线性表长度为线性表长度为线性表长度为n+1,n+1,n+1,n+

18、1,线性表为线性表为线性表为线性表为 (a(a(a(a0 0 0 0,a,a,a,a1 1 1 1,a,a,a,a2 2 2 2,a,a,a,ai-1i-1i-1i-1,x,a,x,a,x,a,x,ai i i i,a,a,a,an-1 n-1 n-1 n-1)插入前插入前n=7插入后插入后n=8插入操作示意图：插入操作示意图：insert(p,3,11)121234343 31111272716161471474444a a0 0a a1 1a a2 2a a3 3a a4 4a a5 5a a6 6a a7 71111121234343 3272716161471474444a a0 0a

19、 a1 1a a2 2a a3 3a a4 4a a5 5a a6 6a a7 7插入操作算法intInsert(ptsqlistlist,inti,elementtypex)intj;if(i=list-n)/*位置不合理位置不合理*/printf(“notexit!n”);return(0);if(list-n=Maxnum)/*空间已满空间已满*/printf(“outofspace!n”);return(0);for(j=list-n-1;j=i;j-)/*向后移动元素向后移动元素*/list-elementj+1=list-elementj;list-elementi=x;/*插入元

20、素插入元素*/list-n+;/*长度加长度加1*/return(1);演示5.5.删除删除删除删除delete(L,i)delete(L,i)功能：功能：功能：功能：删除顺序表删除顺序表删除顺序表删除顺序表L L L L中下标为中下标为中下标为中下标为i i i i（0in-10in-10in-10in-1）的数据元）的数据元）的数据元）的数据元素素素素,删除前线性表为删除前线性表为删除前线性表为删除前线性表为 (a(a(a(a0 0 0 0，a a a a1 1 1 1，a a a an-1n-1n-1n-1)删除后删除后删除后删除后,线性表长度为线性表长度为线性表长度为线性表长度为n-1

21、,n-1,n-1,n-1,线性表为线性表为线性表为线性表为 (a(a(a(a0 0 0 0，a a a a1 1 1 1，a a a ai-1i-1i-1i-1，a a a ai+1i+1i+1i+1，a a a an-1n-1n-1n-1)删除前删除前n=8删除后删除后n=7删除操作示意图：删除操作示意图：Delete(p,3)1111121234343 3272716161471474444121234343 31111272716161471474444a a0 0a a1 1a a2 2a a3 3a a4 4a a5 5a a6 6a a7 7a a0 0a a1 1a a2 2a

22、a3 3a a4 4a a5 5a a6 6a a7 7删除操作算法intDelete(ptsqlistlist,inti)intj;if(i=list-n)/*位置不合理位置不合理*/printf(“notexist!n”);return(0);for(j=i;jn-1;j+)/*向前移动元素向前移动元素*/list-elementj=list-elementj+1;list-n-;/*长度减长度减1*/return(1);演示6.6.顺序表的反转操作顺序表的反转操作顺序表的反转操作顺序表的反转操作viodfanzhuanlist(ptsqlistlist)elementtypemid;in

23、ta,z;a=0;z=list-n-1;for(;aelementa;list-elementa=list-elementz;list-elementz=mid;a a0 0a a1 1a ai-1i-1a ai ia ai+1i+1a an-1n-1mid怎样分析插入和删除算法怎样分析插入和删除算法的的T（n）呢？）呢？在下标为在下标为i的位置的位置(第第i+1个位置个位置)前插入前插入元素下标元素下标移动元素个数移动元素个数0n1n-1in-in-11n0三、算法时间复杂度分析在顺序表中插入元素，时间主要耗费在移动元素在顺序表中插入元素，时间主要耗费在移动元素上，而移动的个数取决于插入的位

24、置以及表的长度。上，而移动的个数取决于插入的位置以及表的长度。1 12 2i-1i-1i ii+1i+1n na a0 0a a1 1a ai-1i-1a ai ia ai+1i+1a an-1n-1假设在线性表的任何位置插入元素的概率相同，即假设在线性表的任何位置插入元素的概率相同，即pi=1/(n+1)则有：则有：假设假设pi是在第是在第i个元素之前插入元素的概率，在长度为个元素之前插入元素的概率，在长度为n的顺的顺序表中插入一个元素，所需移动元素个数数学期望值为：序表中插入一个元素，所需移动元素个数数学期望值为：假设在线性表的任何位置删除元素的概率相同，即假设在线性表的任何位置删除元素的

25、概率相同，即pd=1/n则有：则有：删除下标为删除下标为i的元素（第的元素（第i+1个）需移动个）需移动n-i-1个元素，设在相个元素，设在相应位置删除元素的概率是应位置删除元素的概率是pd，则删除的平均移动次数是：，则删除的平均移动次数是：在顺序表中插入或删除元素的在顺序表中插入或删除元素的时间时间复杂度时间时间复杂度为为O(n)O(n)相关例题例1 利用顺序表设计一算法，用以清除表利用顺序表设计一算法，用以清除表L中的多余的重复结中的多余的重复结点。如表点。如表L（21，3，5，3，21，3，90，5）运算后变为）运算后变为L（21，3，5，90）算法思想应该算法思想应该是怎样的呢？是怎样

26、的呢？相关代码：voidPurge(ptsqlistlist)voidPurge(ptsqlistlist)inti,j,k;inti,j,k;i=0;i=0;while(in)while(in)j=i+1;j=i+1;while(jn)while(jn)if(list-elementi=list-elementj)if(list-elementi=list-elementj)for(k=j+1;kn;k+)for(k=j+1;kn;k+)list-elementk-1=list-elementk;list-elementk-1=list-elementk;list-n=list-n-1;li

27、st-n=list-n-1;elsej=j+1;elsej=j+1;i=i+1;i=i+1;作业：设计相关算法，完成线性表的其它操作：作业：设计相关算法，完成线性表的其它操作：Locate(p,x);Union(p,q).Locate(p,x);Union(p,q).小结顺序表的特点：1通过元素的存储顺序反映线性表中数据元素之间的逻辑关系；2可随机存取顺序表的元素；3顺序表的插入、删除操作要通过移动元素实现；线性表的链式存储结构是用一组线性表的链式存储结构是用一组任意任意的存的存储单元存储线性表的数据元素。为了表示线性储单元存储线性表的数据元素。为了表示线性表中元素的先后关系，每个结点除了需要

28、存储表中元素的先后关系，每个结点除了需要存储自身的信息外，还需存储一个指示其直接后继自身的信息外，还需存储一个指示其直接后继的信息（直接后继的存储位置）。的信息（直接后继的存储位置）。a ai i+1a a1a ai-i-1a a2 2a ai ia an n2.32.3线性表的链式存储结构线性表的链式存储结构 101010121014101610181020102210241026用线性链表存储线性表时，用线性链表存储线性表时，数据元素之间的关系是通过数据元素之间的关系是通过保存直接后继元素的存储位保存直接后继元素的存储位置来实现的置来实现的2.3.1 线性链表一，线性链表的概念a4 4a3

29、 3a1 1a2 2NULL101010241014a1 1a4 4a2 2结点结点数据域数据域数据域数据域指针域指针域指针域指针域n n线性链表有关术语n n结点：结点：结点：结点：数据元素及直接后继的存储位置（地址）组数据元素及直接后继的存储位置（地址）组数据元素及直接后继的存储位置（地址）组数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；成一个数据元素的存储结构，称为一个结点；成一个数据元素的存储结构，称为一个结点；成一个数据元素的存储结构，称为一个结点；n n结点的数据域结点的数据域结点的数据域结点的数据域：结点中用于保存数据元素的部分结点中用于保存数据元

30、素的部分结点中用于保存数据元素的部分结点中用于保存数据元素的部分;n n结点的指针域结点的指针域结点的指针域结点的指针域：结点中用于保存数据元素直接后继结点中用于保存数据元素直接后继结点中用于保存数据元素直接后继结点中用于保存数据元素直接后继存储地址的部分存储地址的部分存储地址的部分存储地址的部分;存储数据元素存储数据元素存储直接后继存储直接后继结点的地址结点的地址怎样在计算机上实现线性链表？结点变量图示LNode：结构类型名；：结构类型名；LNode类型结构变量有两个域：类型结构变量有两个域：data：用于存放线性表的数据元素，用于存放线性表的数据元素，next：用于存放元素直接后继结点的地

31、址；用于存放元素直接后继结点的地址；该类型结构变量用于表示线性链表中的一个结点；该类型结构变量用于表示线性链表中的一个结点；data next LNode类型类型结构变量结构变量p pp是是LNode类类型的指针变量型的指针变量线性链表的结点类型定义及指向结点的指针类型定义线性链表的结点类型定义及指向结点的指针类型定义typedefstructNodeEtypedata;structNode*next;LNode,*LinkList;数据域数据域数据域数据域指针域指针域指针域指针域顺序顺序顺序顺序建立单链表建立单链表建立单链表建立单链表（尾插法）（尾插法）（尾插法）（尾插法）Hpa aqHpa

32、 aqHpa aqb bqHb bc cpqqa a Lnode*Screat_List(void)charch;LinkListH,p,q;H=NULL;q=H;scanf(ch);while(ch!=n)p=(LinkList)malloc(sizeof(LNode);p-data=ch;if(H=NULL)H=p;elseq-next=p;q=p;scanf(ch);p-next=NULL;returnH;headhead是头指针是头指针头结点头结点空指针空指针headn n头指针：头指针：头指针：头指针：用于存放线性链表中第一个结点的存储地址用于存放线性链表中第一个结点的存储地址用于存

33、放线性链表中第一个结点的存储地址用于存放线性链表中第一个结点的存储地址;n n空指针：空指针：空指针：空指针：不指向任何结点，线性链表最后一个结点的不指向任何结点，线性链表最后一个结点的不指向任何结点，线性链表最后一个结点的不指向任何结点，线性链表最后一个结点的指针通常是空指针指针通常是空指针指针通常是空指针指针通常是空指针;n n头结点：头结点：头结点：头结点：线性链表的第一元素结点前面的一个附加结线性链表的第一元素结点前面的一个附加结线性链表的第一元素结点前面的一个附加结线性链表的第一元素结点前面的一个附加结点，称为头结点；点，称为头结点；点，称为头结点；点，称为头结点；n n带头结点的线

34、性链表：带头结点的线性链表：带头结点的线性链表：带头结点的线性链表：第一元素结点前面增加一个附第一元素结点前面增加一个附第一元素结点前面增加一个附第一元素结点前面增加一个附加头结点的线性链表称为加头结点的线性链表称为加头结点的线性链表称为加头结点的线性链表称为 带头结点的线性链表；带头结点的线性链表；带头结点的线性链表；带头结点的线性链表；an na1 1a2 2非空表非空表空表空表二，线性链表基本操作的算法如何在线性链表上实现线性表的基本操作？如何建表?查找?如何插入?删除?约定用带头结点的线性链表存储线性表headan na1 1a2 21.1.建立单链表建立单链表建立单链表建立单链表（前

35、插法）（前插法）（前插法）（前插法）LpX XLp-next=L-next;L-next=p;Lan na1 1pX Xp-next=L-next;L-next=p;1.1.建立单链表建立单链表建立单链表建立单链表（前插法）（前插法）（前插法）（前插法）LinkListCreateList(intn)LinkListL,p;inti;L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for(i=n;i0;-i)p=(LinkList)malloc(sizeof(LNode);scanf(%d,&p-data);p-next=L-next;L-next=p

36、;return(L);2.2.按序号查找按序号查找按序号查找按序号查找Lan na1 1LNode*Get_List_Node(LinkListhead,inti)/*在单链表中查找第i个结点,返回其指针,若失败返回空*/LNode*p;intj;p=head;j=0;while(p-next!=NULL)&jnext;j+;if(j=i)returnp;elsereturnNULL;3.3.按值查找按值查找按值查找按值查找Lan na1 1LNode*Locate_List_Node(LinkListhead,Etypex)/*在单链表中查找值为x的结点,返回其指针,查找失败返回空*/LNo

37、de*p;p=head-next;while(p!=NULL)&(p-data!=x)p=p-next;/*后移查找指针*/if(p!=NULL)returnp;returnNULL;4.4.插入操作插入操作插入操作插入操作 intListInsert(LinkListL,inti,Etypee)intListInsert(LinkListL,inti,Etypee)功能：功能：在线性链表的第在线性链表的第i个结点之前插入一个新结点；个结点之前插入一个新结点；插入操作主要步骤：插入操作主要步骤：1）查找链表）查找链表L的第的第i-1个结点；个结点；2）为新元素建立结点；）为新元素建立结点；3）

38、修改第）修改第i-1个元素结点的指针和新元素结点指个元素结点的指针和新元素结点指针完成插入；针完成插入；注意注意 的顺序！的顺序！headan nai-1i-1ai ia1 1headan nai-1i-1ai ia1 1插入前插入前插入后插入后xs-next=p-next;p-next=s;intListInsert(LinkListL,inti,Etypee)LinkListp;p=Get_List_Node(L,i-1);if(p=NULL)returnERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next

39、=s;returnOK;4.4.插入操作插入操作插入操作插入操作 5.5.删除操作删除操作删除操作删除操作 intListDelete(LinkListL,inti,Etypee)intListDelete(LinkListL,inti,Etypee)功能：功能：删除线性链表的第删除线性链表的第i个结点；个结点；删除操作主要步骤：删除操作主要步骤：1）查找链表的第）查找链表的第i-1个元素结点个元素结点,使指针使指针p指向它指向它,将将指针指针q指向第指向第i个结点；个结点；2）修改第）修改第i-1个元素结点指针，使其指向第个元素结点指针，使其指向第i个元素个元素结点的后继；结点的后继；3）回

40、收）回收q指针所指的第指针所指的第i个结点空间；个结点空间；ai+1i+1headan nai-1i-1ai ia1 1删除前删除前删除后删除后ai+1i+1headan nai-1i-1ai ia1 1p pq qp pq q插入操作图示：插入操作图示：p-next=q-next;p-next=p-next-next;free(q);intListDelete(LinkListL,inti,Etypee)LinkListp,q;intj;ElemTypee;p=Get_List_Node(L,i-1);if(p=NULL|p-next=NULL)returnERROR;q=p-next;p-

41、next=q-next;e=q-data;free(q);returnOK;5.5.删除操作删除操作删除操作删除操作 演示三、线性链表的其他操作的实现例1 将两个递增有序线性链表归并成一个递增有序表。将两个递增有序线性链表归并成一个递增有序表。设线性表设线性表A、B分别用头指针为分别用头指针为La、Lb的两个带头结点的两个带头结点的线性链表存储的线性链表存储,归并后的递增有序表头指针为归并后的递增有序表头指针为Lc,将两表将两表数据较小的结点依次取出插入到新表。数据较小的结点依次取出插入到新表。演示利用基本操作利用基本操作直接对链表进行操作直接对链表进行操作LinkListMergeList(

42、LinkListLa,LinkListLb)LinkListLc,pa,pb,pc;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;elsepc-next=pb;pc=pb;pb=pb-next;pc-next=pa?pa:pb;free(Lb);return(Lc);例2 某仓库中有一批电视机，按价格从低到高构成一单链表某仓库中有一批电视机，按价格从低到高构成一单链表存于计算机中。链表的每个结点指出同样价格的若干台，现存于计算机中。链表的每个结点指出同样价格的若

43、干台，现又到新又到新m台价格为台价格为h的电视机入库。请写出链表增加电视的算的电视机入库。请写出链表增加电视的算法。法。Cost number next Cost number nexttypedefstructLNODEfloatcost;intnumber;structLNODE*next;LNode,*LinkList;LinkListTVSets(LinkLists,intm,floath)LinkListp,q,t;q=s;p=s-next;while(p!=NULL&p-costnext;if(p!=NULL&p-cost=h)p-number=p-number+m;elset=(

44、LinkList)malloc(sizeof(LNode);t-cost=h;t-number=m;q-next=t;t-next=p;return(s);线性链表是线性表的一种链式存储结构线性链表小结线性链表小结线性链表的特点1通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；2插入删除操作通过修改结点的指针实现；3不能随机存取元素；(a)(a)非空表非空表 （b b）空表）空表2.3.2 2.3.2 单向循环链表单向循环链表n n循环链表的概念 循环链表是线性表的另一种链式存储结构，它的特点循环链表是线性表的另一种链式存储结构，它的特点循环链表是线性表的另一种链式存储结构，它的特

45、点循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的头结是将线性链表的最后一个结点的指针指向链表的头结是将线性链表的最后一个结点的指针指向链表的头结是将线性链表的最后一个结点的指针指向链表的头结点点点点n n循环链表图示headheadheadheada1ana2(c)(c)给出尾指针的循环链表给出尾指针的循环链表n n说明n n对循环链表，有时不给出头指针，而是给出尾指针对循环链表，有时不给出头指针，而是给出尾指针对循环链表，有时不给出头指针，而是给出尾指针对循环链表，有时不给出头指针，而是给出尾指针n n循环链表与线性链表操作的主要差别是算法中循环循环

46、链表与线性链表操作的主要差别是算法中循环循环链表与线性链表操作的主要差别是算法中循环循环链表与线性链表操作的主要差别是算法中循环结束的条件不是结束的条件不是结束的条件不是结束的条件不是p p p p或或或或p-nextp-nextp-nextp-next是否为是否为是否为是否为NULL,NULL,NULL,NULL,而是它们而是它们而是它们而是它们是否等于某一特定指针（头指针是否等于某一特定指针（头指针是否等于某一特定指针（头指针是否等于某一特定指针（头指针/尾指针）；尾指针）；尾指针）；尾指针）；n n在解决某些实际问题时，循环链表要比线性链表方在解决某些实际问题时，循环链表要比线性链表方在

47、解决某些实际问题时，循环链表要比线性链表方在解决某些实际问题时，循环链表要比线性链表方便些。如将一个链表链在另一个链表的后面；便些。如将一个链表链在另一个链表的后面；便些。如将一个链表链在另一个链表的后面；便些。如将一个链表链在另一个链表的后面；rearreara1ana2p=a-next;q=b-next;a-next=q-next;b-next=p;free(q);p pa aa1ana2q qb bb1bnb2p pa aa1ana2q qb bb1bnb2存储数据元素存储数据元素存储后继结点存储后继结点 的地址的地址存储前趋结点存储前趋结点 的地址的地址2.3.3 2.3.3 双向链表

48、双向链表n n双向链表的概念 双向链表中，每个结点有两个指针域，一个指向直接双向链表中，每个结点有两个指针域，一个指向直接双向链表中，每个结点有两个指针域，一个指向直接双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。后继元素结点，另一个指向直接前趋元素结点。后继元素结点，另一个指向直接前趋元素结点。后继元素结点，另一个指向直接前趋元素结点。datadatapriorpriornextnext结点结点(a)(a)结点图示结点图示(b)(b)空的双向循环链表空的双向循环链表 head-prior=head-next（c c）非空的双向循环链表）非空的双向循环

49、链表typedef struct DulNodeElemTypedata;struct DulNode*prior;struct DulNode*next;dlNode,*DullinkList；headheadabheadheadn n双向链表图示p pabxsn n双向链表的基本操作算法插入插入 S-prior=p-prior;p-prior-next=S;S-next=p;p-prior=S;删除删除p-prior-next=p-next;p-next-prior=p-prior;p pacbp-priorp-next插入操作算法插入操作算法intdList_Insert(DlinkLi

50、stH,inti,Etypee)dLNode*p=H-next;intj=0;dop=p-next;j+;while(p!=H-next&ji)return0;if(!(s=(dLNode*)malloc(sizeof(dLNode)return0;s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;return1;p pabes删除操作算法删除操作算法intdList_Delete(DLinkListH,inti,Etype*e)dLNode*p=H-next;intj=0;dop=p-next;j+;while(p!=H-n