数据结构-线性表课件

数据结构第二章线性表

在本课程介绍的几种数据结构中，线性表是最常简单的，也是最常用的数据结构，线性表在实际应用大量使用，并不是一个陌生的概念。

基本内容

1线性表的概念；

2线性表两类存储结构和它们的类型定义；

3在这些存储结构下，线性表的基本操作的算法；学习要点：

1了解线性表逻辑结构的特征;

2重点掌握线性表的顺序存储结构和链式存储结构，它们如何表达线性表中数据元素之间的结构关系；如何用C语言描述它们的类型定义；3掌握在顺序存储结构下，线性表的基本操作的算法；

4掌握在链式存储结构下，线性表的基本操作的算法；

5能够从时间复杂度的角度，比较线性表两类存储结构的不同特点及适用场合；

第二章线性表

2.1线性表的概念说明：设A=(a1,a2,...,ai-1,ai,ai+1,…,an)是一线性表1）线性表的数据元素可以是各种各样的，但同一线性表中的元素须是同一类型的；2）在表中ai-1领先于ai，ai领先于ai+1，称ai-1是ai的直接前趋，ai+1是ai的直接后继；3）在线性表中，除第一个元素和最后一个元素之外，其他元素都有且仅有一个直接前趋，有且仅有一个直接后继，具有这种结构特征的数据结构称为线性结构。线性表是一种线性数据结构；4）线性表中元素的个数n称为线性表的长度，n=0时称为空表；5）ai是线性表的第i个元素，称i为数据元素ai的序号，每一个元素在线性表中的位置，仅取决于它的序号；2.1线性表的概念设L=（a1,a2,...ai-1,ai,ai+1,…,an）是一线性表1初始化操作InitList(&L)功能：建立空的线性表L；2销毁操作DetroyList(&L)功能：回收为线性表L动态分配的存储空间；3置空操作ClearList(&L)功能：L中已存在，重新将其置成空表；4判空操作ListEmpty(L)功能：判断线性表L是否为空表，若为空表返回TRUE，否则返回FALSE；5求表长操作

ListLength(L)功能：返回线性表L的表长；二、线性表的基本操作6取元素操作：GetElem(L,i,&e)功能：将线性表L中第i个元素赋值给

e；7查找操作LocateElem(L,e,compare())功能：在线性表L中查找与元素e满足compare()的第1个元素，返回该元素在表中的序号（或位置），若表中不存在这样的元素，则返回0；8插入操作ListInsert(&L,i,e)功能：在线性表L的第i个元素之前插入一个新元素e;9删除操作

ListDelete(&L,i,&e)功能：删除线性表L的第i个元素，并用e返回；10遍历操作

ListTraverse(&L,visit())功能：依次对线性表L的每一个元素调用函数visit()。若visit()失败，则返回ERROR，否则返回OK；说明1上面列出的操作，只是线性表的一些常用的基本操作；2不同的应用，基本操作可能是不同的；

例如：上面列出的删除操作Delete(&L,i,&e),功能是在线性表L中删除第i个元素，并用e返回其值。在电话号码查询系统中，一旦某用户撤掉某部电话，则需在系统的电话号码簿中删除该用户对应的数据，因此电话号码查询系统，需要提供这样的功能，在电话号码簿中删除与给定元素e值相同的数据元素；3线性表的复杂操作可通过基本操作实现；

这有点类似于数中的情形，例如整数的基本操作是+,-,,/。如果要求某班同学的平均年龄则可利用+/实现，全班同学的平均年龄=(age1+age2+age3+…)/全班同学的人数

例如，我们要在设计一个电话号码询系统，显然这个系统至少要具备下列功能：

·

查询某人的电话号码；

·在电话号码薄中，插入一新用户姓名及电话号码；

·在电话号码薄中，删除已撤销的用户姓名及电话号码；

由上我们知道，电话号码薄可用线性表表示，上面列出的功能实际上就是对线性表的查找、插入、删除操作，为了在计算机上实现上述功能，我们应该做什么呢？

显然，首先需要将电话号码薄上的信息存储到计算机中，然后才可能对这些信息进行加工处理，实现上述功能。

2.2

线性表的顺序存储和实现

一、线性表的顺序存储结构——顺序表1.线性表的顺序存储结构2.顺序表的类型定义二、顺序表的基本操作算法三、利用基本操作实现线性表的其他操作线性表的顺序存储结构，就是用一组连续的内存单元依次存放线性表的数据元素。用顺序表存储线性表时，数据元素之间的逻辑关系，是通过数据元素的存储顺序反映出来的a1a2ai-1aiai+1an线性表(a1,a2a3,...an)的顺序存储结构用顺序存储结构存储的线性表:称为顺序表2.2线性表的顺序存储和实现一、线性表的顺序存储结构:顺序表1.线性表的顺序存储结构2.2线性表的顺序存储和实现说明：

在顺序存储结构下，线性表元素之间的逻辑关系，可通过元素的存储顺序反映（表示）出来，所以只需存储数据元素的信息；假没线性表中每个数据元素占用k个存储单元，那么，在顺序存储结构中，线性表的第i个元素的存储位置与第1个元素的存储位置的关系是：Loc(ai)=Loc(a1)+(i–1)k

这里Loc(ai)是第i个元素的存储位置,Loc(a1)是第1个元素的存储位置，也称为线性表的基址；2.2线性表的顺序存储和实现怎样在计算机上实现线性表的顺序存储结构？？2、顺序表的类型定义

以上用自然语言描述了线性表的顺序存储结构，怎样将这种存储方式在计算机上实现？为此，我们用C语言对这种存储方式进行描述，我们知道C语言一维数组的机内表示也是顺序结构，因此，可借用C语言的一维数组实现线性表的顺序存储。2.2线性表的顺序存储和实现顺序表图示a1a2ai-1aiai+1anL.lengthL.listsizeL.elemnLIST_INIT_SIZE存放线性表元素的一维数组设A=（a1,a2,a3,...an）是一线性表，L是SqList类型的结构变量，用于存放线性表A，则L在内存中的状态如图所示：2.2线性表的顺序存储和实现

二、顺序表的基本操作算法回顾本书算法中常用到的两个C函数。

1)

Malloc(intsize)

功能：系统内存分配size个的存储单元，并返回该空间的基址。

使用方法：

...

intm=100,float*p;

p=(float*)malloc(m*sizeof(float));

执行语句p=(float*)malloc(m*sizeof(float))，计算机将按float类型变量所占空间的大小(一般为32bit)分配m*sizeof(float)个的存储单元,并将其基址赋值给指针变量p;

01299p

p=(float*)malloc(m*sizeof(float))图示2.2线性表的顺序存储和实现如何在顺序表上实现线性表的基本操作？如何建空表？如何求表长？如何插入？删除？？

设线性表用顺序表L存储，下面我们介绍用顺序表存储线性表时，各种基本操作的算法。当线性表用顺序表存储时，对线性表各种基本操作实际上就是对存储在内存中的顺序表进行操作。2.2线性表的顺序存储和实现1）初始化操作InitList_Sq(SqList&L)

参数：L是存放线性表的结构变量（称L为顺序表）,因为插入操作对顺序表L进行了修改,所以用了引用参数&L;功能：建立空的顺序表L主要步骤：调用malloc()为顺序表分配一预定大小(LIST_INIT_SIZE）的空间,并将其基址赋值给L.elem;

初始化操作演示2.2线性表的顺序存储和实现

顺序表初始化01LIST_INIT_SIZE-1L.lengthL.listsizeL.elem0LIST_INIT_SIZE

再演示一次2.2线性表的顺序存储和实现

销毁操作图示2销毁操作

DetroyList(SqList&L)

功能：回收为顺序表动态分配的存储空间

主要步骤：调用free()回收为顺序表动态分配的存储空间2.2线性表的顺序存储和实现

销毁顺序表L.lengthL.listsizeL.elem01LIST_INIT_SIZE-1a1a2ai-1aiai+1an

nLIST_INIT_SIZE00=null

再演示一次2.2线性表的顺序存储和实现销毁操作算法：

StatusDetroyList_Sq(SqList&L){

If(!L.elem)returnERROR;//若表L不存在

free(L.elem);//若表L已存在，回收动态分配的存储空间

L.elem=null;

L.length=0;

L.Listsize=0;

returnOK;

}//DetroyList_Sq2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现L.lengthL.listsizeL.elem0199a1a2ai-1aiai+1an

n

990置空操作图示置空再演示一次取元素操作图示6取元素操作

GetElem_Sq(SqListL,inti,ElemType&e)

功能：将顺序表中第i个元素赋值给e

算法：

StatusGetElem_Sq(SqList&L,inti,ElemType&e){

if((i<1)||(i>L.length-1))returnERROR;//i非法

e=L.elem[i-1];//将顺序表中第i个元素赋值给e

returnOK;

}//GetElem_Sq

由于C语言的一维数组下标从0开始,故线性表的第一个元素放在L.elem[0]，第i个素放L.elem[i-1]中，最后一个元素放在L.elem[L.length-1]中。2.2线性表的顺序存储和实现

为初学者易于理解插入算法主要步骤，这里简化了书上的插入算法2.4，对插入算法中表空间已满的情况，只简单的返回出错（ERROR），在2.2的最后部分给出完整的插入算法。当然，应用中对各种情况的如何处理，要根据实际问题的需要来决定。注意2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现

插入操作图示插入操作主要步骤：1）i是否合法，若合法转2），否则算法结束，并返回ERROR；

2）L是否已满，若未满转3），否则算法结束，并返回ERROR；3）将顺序表ai及之后的所有元素后移一个位置；

4)将新元素写入空出的位置；

5）表长+1；用鼠标单击图中的绿字StatusListInsert_Sq(SqList&L,inti,ElemTypee){

//在顺序表L中第i个位置之前插入新的元素e,

//i的合法值为1≤i≤L.length+1,当i=L.length+1时//e插在表尾

if(i<1||i>L.length+1)returnERROR;//i值不合法

if(L.length>=L.listsize)returnERROR;//顺序表已满

for(j=L.length-1;j>=i-1;--j)L.elem[j+1]=L.elem[j];

//插入位置及之后的元素后移一个位置

L.elem[i-1]=e;//插入e

++L.length;//表长增1

returnOK;

}//ListInsert_Sq算法2.4a插入操作算法为初学者易于理解插入算法，这里通过下标引用L.elem中的元素。2.2线性表的顺序存储和实现2.2线性表的顺序存储和实现StatusListInsert_Sq(SqList&L,intI,ElemTypee){

//在顺序表L中第i个位置之前插入新的元素e,

//i的合法值为1≤i≤L.length+1

if(i<1||i>L.length+1)returnERROR;//i值不合法

if(L.length>=L.listsize)returnERROR;//顺序表已满

q=&(L.elem[i-1]);//q为插入位置

for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;

//插入位置及之后的元素后移一个位置

*q=e;//插入e

++L.length;//表长加1

returnOK;

}//ListInsert_Sq算法2.4b算法2.4b与算法2.4a唯一的不同是通过指针p引用L.elem中的元素。2.2线性表的顺序存储和实现

插入位置移动元素个数

1

n

2

n-1

in-i+1

n1

n+10

算法时间复杂度分析

下面分析插入算法的时间复杂度。顺序表的插入算法2.4a或2.4b中，基本操作是移动元素，算法时间复杂度取决于移动元素的个数，即算法时间复杂度取决于算法中循环体执行次数。移动元素的个数不仅与表长有关，而且与插入位置有关。2.2线性表的顺序存储和实现由此可见

·在顺序表中插入一个元素，平均要移动表的一半元素。

·表长为n的顺序表，插入算法的时间复杂度为On）假设在线性表的任何位置插入元素的概率相同，即pi=1/(n+1),则

若用pi表示在顺序表的第i个元素之前插入元素的概率，在长度为n的顺序表中插入一个元素，所需移动元素个数数学期望值为：2.2线性表的顺序存储和实现9.删除操作:ListDelete_sq(SqList&L,inti,ElemType&e)

·功能：删除顺序表L的第i个元素，并用e返回

·删除操作图示

删除操作主要步骤：

1）i不合法或表空，算法结束，并返回ERROR；否则转2）

2）将ai赋值给e;

3）将顺序表中ai后面的元素依次向前移动一个位置;

4）表长-12.2线性表的顺序存储和实现

删除操作图示用鼠标单击图中的绿字2.2线性表的顺序存储和实现

删除操作算法StatusListDelete_Sq(SqList&L,inti,ElemType&e){

//在顺序表L中删除第i个元素，并用e返回其值

//i的合法值为1≤i≤L.length，//表空L.length=0则i>L.lengthif((i<1)||(i>L.length))returnERROR;//i值不合法或表空

e=L.elem[i-1];//被删除元素的值赋给e

for(j=i;j<=L.length-1;++j)L.elem[j-1]=L.elem[j]//被删除元素之后的元素前移

--L.length;//表长减1

returnOK;

}//ListDelete_Sq

算法2.5a为初学者易于理解插入算法，这里通过下标引用L.elem中的元素。2.2线性表的顺序存储和实现StatusListDelete_Sq(SqList&L,intI,ElemType&e){

//在顺序线性表L中删除第.i个元素，并用e返回其值

//i的合法值为1≤i≤L.length//表空L.length=0则i>L.length

if((i<1)||(i>L.Length))returnERROR;//i值不合法或表空

p=&(L.elem[i-1]);//p为被删除元素的位置

e=*p;//被删除元素的值赋给e

q=L.elem[L.length-1];//表尾元素的位置

for(++p;p<=q;++p)*(p-1)=*p;//被删除元素之后的元素前移

--L.length;//表长减1

returnOK;

}//ListDelete_Sq算法2.5b删除操作算法算法2.5b与算法2.5a唯一的不同是通过指针p引用L.elem中的元素。第二章习题习题三1P162.102编写算法：1）判空操作statusListEmpty_Sq(SqListL)2）求表长操作intListLength_Sq(SqListL)习题取自:数据结构题集C语言版严尉敏等编第二章习题

实验一（学时：4）电话号码查询系统功能：1建立电话号码簿（用顺序存储结构存储电话号码簿）2在电话号码簿中插入一元素（输入插入位置i,插入元素）3在电话号码簿中删除一元素（输入删除元素位置i）4显示电话号码簿

电话号码簿

姓名电话号码蔡颖63214444陈红63217777刘建平63216666王小林63218888张力63215555...2.2线性表的顺序存储和实现

例：将两个有序线性表归并成一个有序线性表；

设线性表A、B分别用La、Lb的两个顺序表存储，两顺序表中元素按非递减顺序排列，编写算法：将La、Lb归并得到顺序表Lc,Lc中的元素也按值非递减顺序排列。实现上述功能的算法有很多，我们采用第三种。

1）将Lb并入La;

2）将La并入Lb;

3）将La,Lb并入Lc;(顺序表Lc中的空间是新分配的存储空间）基本思想：同时对La.elem,Lb.elem进行扫描，在扫描过程中按两表当前元素的大小，依次将其插入到Lc的表尾；三、利用基本操作实现线性表的其他操作

Lc.elemLc.lengthLc.listsize2.2线性表的顺序存储和实现

顺序表的归并图示（算法2.7a)0199La.elem358La.length3100La.listsize0199Lb.elem2689Lb.length4100Lb.listsize01992356889100建空表Lc0La,Lb归并72.2线性表的顺序存储和实现voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){

//已知顺序表La和Lb中的数据元素按值非递减排列。

//归并La和Lb得到新的顺序表Lc,Lc的数据元素也按值非递减排列。

InitList_Sq(Lc)；

i=j=1;k=0;

La_len=Listength_Sq(La);Lb_len=ListLength_Sq(Lb);

while((.i<=La_len)&&(j<=Lb_len)){//La和Lb均非空

GetElem_Sq(La,i,ai);GetElem_Sq(Lb,j,bj);

if(ai<=bj){ListInsert_Sq(Lc,++k,ai);++.i;}

else{ListInsert_Sq(Lc,++k,bj);++j;}

}

while(i<=La_len){

GetElem_Sq(La,.i++,ai);ListInsert_Sq(Lc,++k,ai);

}

while(j<=Lb_len){

GetElem_Sq(Lb,.j++,bj);ListInsert_Sq(Lc,++k,bj);

}

}//MergeList_Sq算法2.7a用线性表的基本操作实现线性表的其它操作Lc.elemLc.lengthLc.listsize2.2线性表的顺序存储和实现

顺序表的归并图示（算法2.7a)0199La.elem358La.length3100La.listsize0199Lb.elem2689Lb.length4100Lb.listsize01992356889100建空表Lc0La,Lb归并72.2线性表的顺序存储和实现voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){

//已知顺序表La和Lb的元素按值非递减排列

//归并La和Lb得到新的顺序表Lc,Lc的元素也按值非递减排列

pa=La.elem;pb=Lb.elem;

Lc.listsize=Lc.length=La.length+Lb.length;

pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType));

if(!Lc.elem)exit(OVERFLOW);//存储分配失败

pa_last=La.elem+La.length-1;

pb_last=Lb.elem+Lb.length-1;

while(pa<=pa_last&&pb<=pb_last){//归并

if(*pa<=*pb)*pc++=*pa++;

else*pc++=*pb++;

}

while(pa<=pa_last)*pc++=*pa++;//插入La的剩余元素

while(pb<=pb_last)*pc++=*pb++;//插入Lb的剩余元素

}//MergeList_Sq算法2.7b两线性表归并操作也可不调用基本操作：而是通过直接对顺序表进行操作实现。直接对顺序表进行操作实现顺序表的的其它操作Lc.elemLc.lengthLc.listsize2.2线性表的顺序存储和实现顺序表的归并图示（算法2.7b)

0199La.elem358La.length3100La.listsize0199Lb.elem2689Lb.length4100Lb.listsize

017

2356889077建空表LcLa,Lb归并2.2线性表的顺序存储和实现

顺序表是线性表最简单的一种存储结构

小结顺序表的特点：1通过元素的存储顺序反映线性表中数据元素之间的逻辑关系；2可随机存取顺序表的元素；3顺序表的插入删除操作要通过移动元素实现；2.3线性表的链式存储和实现

线性表的链式存储结构是用一组任意的存储单元存储线性表的各个数据元素。为了表示线性表中元素的先后关系，每个元素除了需要存储自身的信息外还需保存直接前趋元素或直接后继元素的存储位置。下面介绍线性表的三种链式存结构先从最简单的开始：

用顺序表存储线性表时，线性表的插入删除操作要移动大量的元素，平均的来看要移动线性表中一半的元素，因此对于应用经常要进行进行插入，删除操作的线性表，一般不使用顺序表存储，下面我们来看线性表的另一种存储结构:链式存储结构。2.3线性表的链式存储和实现2.3.1线性链表

一线性链表的概念

二线性链表的基本操作算法

三静态链表四线性链表的其它操作2.3.2循环链表

2.3.3双向链表

一双向链表的概念

二双向链表的基本操作算法一线性链表的概念

1线性链表2.3.1线性链表a4a3a1a2

0101010241014101010121014101610181020102210241026用一组任意的存储单元存储线性表中的数据元素，对每个数据元素除了保存自身信息外，还保存了直接后继元素的存储位置。

用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的2.3.1线性链表线性链表图示ai-1aia2a1ai+1nan

用线性链表存储线性表时，数据元素之间的关系是通过保存直接后继元素的存储位置来表示的2线性链表图示一般来说，我们并不需要写出直接后继的实际地址，为直观起见，通常用如下所示的图表示链表，其中，箭头表示相应单元中保存的是它所指向结点的存储地址。结点：数据元素及直接后继的存储位置（地址）组成一个数据元素的存储结构，称为一个结点；结点的数据域：结点中用于保存数据元素的部分;结点的指针域：结点中用于保存数据元素直接后继存储地址的部分;3线性链表有关术语2.3.1线性链表存储数据元素存储后继结点存储地址结点数据域指针域2.3.1线性链表头指针：用于存放线性链表中第一个结点的存储地址;

空指针：不指向任何结点，线性链表最后一个结点的指针通常是指针;

头结点：线性链表的第一元素结点前面的一个附加结点，称为头结点；

带头结点的线性链表：第一元素结点前面增加一个附加结点的线性链表称为带头结点的线性链表；带头结点的线性链表图示

L是头指针ai-1aia2a1ai+1nan头结点空指针L2.3.1线性链表ai-1aia2a1ai+1nan线性链表的每个结点中只有一个指针域故也称为单链表2.3.1线性链表怎样在计算机上实现线性链表？？上面用自然语言描述线性表的一种链式存储结构——线性链表，怎样在计算机上实现线性链表？显然，可以用C语言的结构表示线性链表的结点，可以用指针存放直接后继的存储地址。

2.3.1线性链表结点变量图示typedefstructLNode{

ElemTypedata;

StructLNode*next;

}LNode,*LinkList;·LNode：结构类型名；

LNode类型结构变量有两个域：

data：用于存放线性表的数据元素，

next：用于存放元素直接后继结点的地址；

·该类型结构变量用于表示线性链表中的一个结点；

·LinkList：指针类型名；

·LinkList类型指针变量用于存放LNode类型结构变量的地址；

数据域指针域

datanext

Lnode类型结构变量LLinkList类型指针变量L4线性链表的结点类型定义及指向结点的指针类型定义2.3.1线性链表设L是LinkList类型变量，L用来保存线性链表中第一个结点的地址，则L为线性链表的头指针。ai-1aia2a1ai+1nanL以L为头指针的线性链表称为线性链表L二线性链表基本操作的算法

假设线性表用带头结点的线性链表L的存储。下面讨论在这种存储方式下，线性表各种基本操作的算法。当线性表用线性链表存储时，对线性表各种基本操作实际上就是对存储在内存中的线性链表进行操作。2.3.1线性链表如何在线性链表L上实现线性表的基本操作？如何建空表？如何插入？删除？？2.3.1线性链表初始化操作演示L∧算法：

StatusInitList_L(LinkList&L){

L=(LinkList)malloc(sizeof(Lnode));

If(!L)exit(OVERFLOW);

L->next=null;

ReturnOK;

}//InitList_L

1）初始化操作InitList_L(LinkList&L)

功能：建空线性链表L

参数：L为线性链表的头指针主要步骤：调用malloc()分配一结点的空间,并将其地址赋值给L；2.3.1线性链表2取元素操作GetElem_L(LinkListL,inti,ElemType&e)

·功能：将线性链表中第i个元素赋值给e取元素操作主要步骤：1）查找链表的第i个元素结点；

2)将第i个元素结点中的数据元素赋值给e;ai-1aia2a1ai+1nanLeai取元素元素操作图示2.3.1线性链表·取元素操作算法：StatusGetElem_L(LinkListL,intI,ElemType&e){//L为带头结点的单链表的头指针。//当第i个元素存在时，其值赋给e并返回OK，否则返回ERRORp=L->next;j=1;//初始化，p指向第一个结点，j为计数器

while(p&&j<i){//顺指针向后查找，直到p指向第i个元素或p为空

p=p->next;++j;}if(!p||j>i)returnERROR;//第i个元素不存在

e=p->data;//取第i个元素

returnOK;}//GetElem_L

算法2.83插入操作ListInsert_L(LinkList&L,inti,ElemTypee)

功能：在线性链表L的第i个元素结点之前插入一个新元素结点；插入操作图示：2.3.1线性链表插入前插入后

ai-1aia2a1ai+1nanLai-1aia2a1ai+1naneL2.3.1线性链表插入操作主要步骤：

1）查找链表L的第i-1个元素结点；

2）为新元素建立结点；

3）修改第i-1个元素结点的指针和新元素结点指针完成插入；

插入操作演示用鼠标单击图中的绿字2.3.1线性链表插入操作算法：

StatusListInsert_L(LinkList&L,inti,ElemTypee){//在带头结点的线性链表L中第I元素结点之前插入元素ep=L;j=0while(p&&j<i-1){p=p->next;++j;}//寻找第i-1个元素结点

if(!p||j>.j-1)returnERROR;//i小于1或者大于表长

s=(LinkList)malloc(sizeof(LNode));//分配新结点

s->data=e;s->next=p->next;p->next=s;//插入新结点

returnOK;}//LinstInsert_L

算法2.94删除操作ListDelete_L(LinkList&L,inti,ElemType&e)

功能：在线性链表L中删除第i个元素，并且用e返回其值删除操作图示：

2.3.1线性链表删除前删除后ai-1aia2a1ai+1nanLai-1aia2a1ai+1nanL2.3.1线性链表删除操作主要步骤：1）查找链表的第i-1个元素结点；

2）修改第i-1个元素结点指针，删除第i个元素结点；

3)将第i个元素结点中的数据元素赋值给e;

4）回收被删除结点空间；

删除操作演示用鼠标单击图中的绿字2.3.1线性链表删除操作算法：StatusListDelete_L(LinkList&L,inti,ElemType&e){//在带头结点的单链线性表L中，删除第i个元素，并由e返回其值

p=L;j=0;while(p->next&&j<i-1){//寻找第i个结点，并令p指向其前趋

p=p->next;++j;}if(!p->next)||j>i-1)returnERROR;//表中无第i个结点(i不合法)

q=p->next;p->next=q->next;//删除结点

e=q->data;free(q);//回收（释放）结点空间

returnOK;}//LinstDelete_L算法：2.10第二章习题习题四P132.1,2.2,2.3,2.14,2.172.3.1线性链表

四、线性链表的其他操作例：将两个有序线性链表归并成一个有序表。设线性表A、B分别用头指针为La、Lb的两个带头结点的线性链表存储，且两线性链表中元素按非递减顺序排列，编写算法，将La、Lb归并得到线性链表Lc,Lc中的元素也按值非递减顺序排列。（注意：线性链表Lc中的结点利用原La，Lb的结点）

实现上述功能的算法有很多，我们采用第三种。

1）将Lb并入La;

2）将La并入Lb;

3）将La,Lb并入Lc;基本思想：设两个指针pa,pb分别对La,Lb进行扫描，在扫描过程中按

pa,pb所指结点的大小，将其插入到Lc的表尾。算法演示LaLbpapbpcLc2234331^^2.3.1线性链表线性链表归并操作算法（直接对链表进行操作）voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){

//已知单链线性表La和Lb的元素按值非递减排列

//归并La和Lb得到新的单链线性表Lc,Lc的元素也按值非递减排列。

pa=La->next;pb=Lb->next;

Lc=pc=La;//用La的头结点作为Lc的头结点

while(pa&&pb){

If(pa->data<=pb->data)

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

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

}

pc->next=pa?pa:pb;//插入剩余段

free(Lb);//释放Lb的头结点}//MergeList_L

算法2.12直接对线性链表进行操作实现线性链表的其它操作例2头插法建立单链表算法描述:逆位序输入n个元素的值,建立带头结点的单链表算法演示:如输入二个元素a,b,头插法建立单链表L^ab^pp2.3.1线性链表例2建立线性链表voidCreateList_L(LinkList&1,intn){//逆序输入n个元素的值，建立带表头结点的线性链表

L=（LinkList）malloc(sizeof(LNode));L->next=NULL;//先建立一个带头结点的单链表

for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));//生成新结点

scanf(&p->data);//输入元素值

p->next=L->next;L->next=p;//插入到表头/}}//CreateList_L直接对线性链表进行操作实现线性链表的其它操作2.3.1线性链表小结线性链表是线性表的一种链式存储结构

线性链表的特点1通过保存直接后继元素的存储位置来表示数据元素之间的逻辑关系；2插入删除操作通过修改结点的指针实现；3不能随机存取元素；2.3.1线性链表

以上学习了线性表的顺序存储结构——顺序表，链式存储结构——线性链表,以及在这两种存储结构下如何实现线性表的基本操作。需要强调的是：本课程不仅要从概念和方法上了解每一种数据结构的逻辑结构，基本操作，更重要的是要学习如何在计算机上实现，即如何在计算机上存储线性表？如何在计算机上实现线性表的操作，我们已经看到，在不同的存储结构下，线性表的同一操作的算法是不同的。在顺序表存储结构下，线性表的插入删除操作，通过移动元素实现，在线性链表存储结构下，线性表的插入删除操作，通过修改指针实现。我们要很好地理解和掌握以上两种存储结构，及两种存储结构下操作的特点。它们是应用中最常用的两种存储结构，也是后续课程其它存储结构的基础。第二章习题实验二（学时：4）电话号码查询系统功能：1建立电话号码簿（用线性链表存储电话号码簿）2在电话号码簿中插入一元素（输入插入位置i，插入元素）3在电话号码簿中删除一元素（输入删除元素位置i）4显示电话号码簿

电话号码簿姓名电话号码蔡颖63214444陈红63217777刘建平63216666王小林63218888张力63215555...2．3线性表的链式存储和实现

线性链表的缺点之一，是无法从指定的某结点到达该结点的前趋结点，这可能会给某些应用带来一些不便，下面介绍线性表的另外两种链式存储结构——循环链表和双向链表。

1循环链表的概念循环链表是线性表的另一种链式存储结构，它的特点是将线性链表的最后一个结点的指针指向链表的第一个结点2循环链表图示2.3.2循环链表(a)非空表（b）空表HHa1an2.3.2循环链表说明·在解决某些实际问题时循环链表可能要比线性链表方便些。如将一个链表链在另一个链表的后面；·循环链表与线性链表操作的主要差别是算法中循环结束的条件；

·对循环链表，有时不给出头指针，而是给出尾指针，设立尾指针可以很方便的找到线性表的第一个元素和最后一个元素结点，可使某些操作易于实现；例如将两个链表首尾相连的操作；Ta1an给出尾指针的循环链表1双向链表的概念2.3.3双向链表(a)结点图示数据域指针域指针域结点存储数据元素存储后继结点的地址存储前趋结点的地址双向链表中，每个结点有两个指针域，一个指向直接后继元素结点，另一个指向直接前趋元素结点。2.3.3双向链表2双向链表图示L（c）非空的双向循环链表

(b)空的双向循环链表Lab在双向链表中删除结点时指针变化情况在双向链表中插入一个结点时指针的变化情况ai-1px①②③④aiaiai+1p①②ai-12.3.3双向链表3、双向链表的基本操作算法2.3.3双向链表ai-1px①②③④ai1）插入操作算法

StatusListInsert_DuL(DuLinkList&L,inti,ElemTypee){

//在带头结点的双链循环线性表L中第i个位置之前插入元素e，

//i的合法值为1≤i≤表长+1。

if(!p=GetElemP_DuL(L,i)))//在L中确定第i个元素的位置指针p

returnERROR;//p=NULL，即第i个元素不存在

//建新结点、

if(!(s=(DuLinkList)malloc(sizeof(DuLNode))))returnERROR;

s->data=e;

s->prior=p-prior;p->prior->next=s;//完成插入图示中的①②

s->next=p;p->prior=s;//完成插入图示中的③④

returnOK;

}//LinstInsert_DuL

算法2.182.3.3双向链表2）删除操作算法StatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){

//删除带头结点的双链循环线性表L的第i个元素，i的合法值为1≤i≤表长

if(!p=GetElemP_DuL(L,i)))//在L中确定第i个元素的位置指针p

returnERROR;//p=NULL，第i个元素不存在

e=p->data;

p->prior->next=p->next;//完成删除图示中的①

p->next->prior=p->prior;//完成删除图示中的②

free(p);returnOK;

}//LinstDelete_DuL

算法2.19aiai+1p①②ai-12.4一元多项式的表示及相加线性表是最简单常用的数据结构。本节介绍一个线性表的典型应用:一元多项式的运算。

2.4一元多项式的表示及相加它由个系数唯一确定。多项式基本运算有加法减法乘法，为了用计算机实现多项式运算，可用一个由系数构成的线性表来表示一元多项式：

P=(p0,p1,p2,…pn)

Q=(q0,q1,q2,…qm)不失一般性，设m<n，则两个多项式相加的结果可用线性表R表示： R=(p0+q0,p1+q1,…,pm+qm,pm+1,…,pn)

显然可以对P，Q，R采用顺序结构存储，这样一元多项式相加运算很容易实现。Pn(x)=p0+p1x+p2x2+…+pnxnQm(x)=q0+q1x+q2x2+…+qmxm一、一元多项式的表示多项式的操作是表处理的典型用例。数学上,一元多项式可按升幂写成：

2.4一元多项式的表示及相加以下用非0项（系数，指数）构成的线性表表示一元多项式。用这种方式表示一元多项式时，一元多项式运算经常要对线性表进行插入删除操作，所以采用线性链表存储结构它们。应用中一元多项式往往幂次很高，且有大量项的系数为零。例：S(x)=1+3x10000+2x20000

如果用系数构成的线性表表示该多项式，就要用一长度为20001的线性表表示，可表中只有三个非零项，这显然很浪费内存空间。可采用另一种方式，即用非0项（系数，指数）构成的线性表表示一元多项式，S=((1,0),(3,10000),(2,20000))2.4一元多项式的表示及相加链表中结点指针的类型定义typedefstructLNode{

ElemTypedata;

StructLNode*next;

}*Link,*Position;1）线性链表的类型定义ai-1aia2a1ai+1nanL链表中结点指针二一元多项式的链式存储结构1重新定义线性链表

一元多项式运算，将利用线性链表的基本操作实现。为了实现多项式的加减乘等运算需要重新定义线性链表和基本操作。2.4一元多项式的表示及相加链表的类型定义（链表表头结点的类型定义）

typedefstruct{

Linkhead,tail;

intlen;

}LinkList;表头结点是一结构a1anLheadtaillennL是Linklist类型的结构变量2.4一元多项式的表示及相加a1anLheadtaillenn2）新定义线性链表图示表头结点头结点L是Linklist类型的结构变量2.4一元多项式的表示及相加3）在原线性链表的基础上，增加如下的基本操作：（1）取表头操作PositionGetHead(LinkListL)

功能：L为线性链表的表头结点，该操作返回链表的头结点指针；（2）求后继操作Position

Nextpos(LinkListL,Linkp)

功能：p指向线性链表L的某个结点，返回p所指结点的后继的指针；（3）求前趋操作PositionPrior(LinkListL,Linkp)

功能：p指向线性链表L的某个结点，返回p所指结点的前趋的指针；（4）取当前结点值的操作ElemTypeGetCurElem(Linkp)

功能：p指向线性链表L的某一结点，返回p的所指结点的值；headtaillennL是表头结点头结点a1anL2.4一元多项式的表示及相加a1anLhs插入首结点StatusInsFirst(Linkh,Links)图示（5）为当前结点赋值StatusSetCurElem(Link&p,ElemTypee)功能：p指向线性链表L的某个结点,用e更新p所指结点中数据元素的值（6）插入首结点StatusInsFirst(Linkh,Links)

功能：h指向线性链表L的头结点,在线性链表的第一元素结点之前插入s所指结点；2.4一元多项式的表示及相加（7）删除首结点StatusDelFirst(Linkh,Linkq)

功能：

h指向线性链表L的头结点,删除线性链表的第一元素结点，并用q返回其指针；

（8）连接链表StatusAppend(LinkList&L,Links)

功能：将s所指的链表链接在线性链表L的尾部La1ana2

删除首结点StatusDelFirst(Linkh,Linkq)图示hq2.4一元多项式的表示及相加1）元素的类型定义typedefstruct{

floatcoef;//存储项系数

intexpn;//存储项指数

}ElemType;2）一元多项式链表的类型定义typedefLinkListpolynomail;//用带表头结点的线性链表表示//一元多项式，为类型重命名//是为增加算法的可读性

coefexpn2一元多项式链式存储结构为用线性链表表示一元多项式，给出ElemType的类型定义2.4一元多项式的表示及相加3）一元多项式链式存储结构图示s-110310000220000∧S是表头结点头结点2.4一元多项式的表示及相加例：求两多项式的和多项式

A(x)=7+3x+9x8+5x17B(x)=8x+22x7–9x8三、一元多项式的相加算法设多项式A(x)，B(x)分别用带表头结点的线性链表Pa,Pb表示，和多项式C(x)用带表头结点的线性链表Pc表示（如下图所示,PaPbPc分别是三个表的表头结点）A(x)B(x)相加的和多项式为

C(x)=A(x)+B(x)=7+11x+22

x7+5