第二章-线性表

第二章线性表2.1线性表的类型定义2.2线性表的顺序表示和实现2.3线性表的链式表示和实现

2.3.1线性链表

2.3.2循环链表

2.3.3双向链表2.4一元多项式的表示及相加第二章线性表重点：理解线性表的逻辑结构特性熟练掌握线性表的顺序存储结构的描述方法，以及在该存储结构下的基本操作熟练掌握线性表的链式存储结构的描述方法，灵活使用单链表、双链表、循环链表，学会在相应存储结构下实现其各种基本算法及相关的时间性能分析一元多项式的表示和相加第二章线性表难点：能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其应用场合使用本章所学的基本知识设计有效算法，解决与线性表相关的应用问题第二章线性表线性结构的特点：在数据元素的非空有限集中，1）存在唯一的一个被称为“第一个”的数据元素2）存在唯一的一个被称为“最后一个”的数据元素3）除第一个之外，集合中的每个数据元素均只有一个前驱4）除最后一个之外，集合中的每个数据元素均只有一个后继1.线性表：定义：简称为表，是零个或多个元素的有穷序列，通常可以表示成(a1,a2,…,an)(n

0)表的长度：表中所含元素的个数

n空表：长度为零的表表项：表中的元素ai位序：数据元素ai在线性表中的位置2.1线性表的类型定义1.线性表：线性表中的数据元素在不同的情况下可以有不同的具体含义，它可以是一个数、一个符号，也可是其它更复杂的信息例1.26个字母(A,B,…,Z)

例2.班级人数(33,32,35,30)例3.学生情况登记表：数据元素为记录，有若干个数据项组成（如姓名，学号，性别，年龄…)P182.1线性表的类型定义2.线性表的特点：线性表中的数据元素是各种各样的，但同一线性表中的元素必定具有相同特性，即属于同一数据对象，比如数据元素都是整数。相邻数据元素之间存在序偶关系

(a1,a2,…,ai-1,ai,ai+1,…,an)ai-1是ai的直接前驱元素，ai+1是ai的直接后继元素相当灵活，长度可以增长或缩短。即可对线性表中的元素进行访问，还可进行插入和删除等。2.1线性表的类型定义3.线性表的基本运算在线性表中插入一个元素；在线性表中删除某个元素；在线性表中查找某个特定元素；在线性表中查找某个元素的后继元素；在线性表中查找某个元素的前驱元素；创建空线性表；判别一个线性表是否为空表。……由基本运算可以构成其它较为复杂的运算2.1线性表的类型定义4.抽象数据类型线性表的定义P19ADTList{

数据对象：D={ai|aiElemSet,i=1,2,…,n,n

0}

数据关系：R1={<ai-1,ai>|

ai-1,

aiD,i=1,2,…,n}

基本操作：

InitList(&L)

操作结果：构造一个空的线性表L

DestroyList(&L)

初始条件：线性表L已存在操作结果：销毁线性表

…2.1线性表的类型定义4.抽象数据类型线性表的定义（P19）

…ClearList(&L)

初始条件：线性表L已存在操作结果：将线性表L重置为空表

ListEmpty(L)

初始条件：线性表L已存在操作结果：若L为空表，则返回TRUE，否则返回FALSE

ListLength(L)

初始条件：线性表L已存在操作结果：返回L中数据元素个数

2.1线性表的类型定义4.抽象数据类型线性表的定义（P19）

GetElem(L,i,&e)

初始条件：线性表L已存在，1≤i≤LengthList(L)

操作结果：用e返回L中第i个元素的值

LocateElem(L,e,compare())

初始条件：线性表L已存在，compare()是元素判定函数操作结果：返回L中第1个与e满足关系compare()的元素的位序。若这样的元素不存在，则返回值为0

PriorElem(L,cur_e,&pre_e)

初始条件：线性表L已存在操作结果：若cur_e是L的元素，但不是第一个，则

用pre_e返回它的前驱，否则操作失败，pre_e无定义2.1线性表的类型定义4.抽象数据类型线性表的定义（P19）

NextElem(L,cur_e,&next_e)

初始条件：线性表L已存在操作结果：若cur_e是L的元素，但不是最后一个，则用next_e返回它的后继，否则操作失败，next_e无定义

ListTraverse(L,visit())

初始条件：线性表L已存在操作结果：依次对L的每个元素调用函数visit()。一旦visit()失败，则操作失败2.1线性表的类型定义4.抽象数据类型线性表的定义（P19）

ListInsert(&L,i,e)

初始条件：线性表L已存在，1≤i≤LengthList(L)+1

操作结果：在L的第i个元素之前插入新的元素e，L

的长度增1

ListDelete(&L,i,&e)

初始条件：线性表L已存在且非空，

1≤i≤LengthList(L)

操作结果：删除L的第i个元素，并用e返回其值，L

的长度减1}ADTList2.1线性表的类型定义算法2-1

假设利用两个线性表LA和LB分别表示两个集合A和B（即：线性表中的数据元素即为集合中的成员），现要求一个新的集合A＝A∪B。上述问题等价于：要求对线性表作如下操作：扩大线性表LA，将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。

分下列三步进行：

1）从线性表LB中依次取得每个数据元素;

2）依值在线性表LA中进行查访;

3）若不存在，则插入之。2.1线性表的类型定义算法2.1：用C语言描述如下算法：voidunion(List&La,ListLb){

//将所有在线性表Lb中但不在La中的数据元素插入到La中

La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度

for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e

if(!LocateElem(La,e,equal))

ListInsert(La,++La_len,e);

//La中不存在和e相同的数据元素，则插入之

}}//union2.1线性表的类型定义例2-2

已知一个非空集合B，试构造集合A，要求集合A中只包含集合B中所有值不相同的数据元素。

解法一：同上，分别以线性表LA和LB表示集合A和B，则首先初始化线性表LA为空表，之后的操作和例2-1完全相同。

解法二：仍以线性表表示集合。只是求解之前先对线性表LB中的数据元素进行排序，即线性表LB中的数据元素依其值从小到大有序排列，则值相同的数据元素必相邻。则上述操作中的第二步就不需要进行从头至尾的查询。2.1线性表的类型定义算法2.2：用C语言描述得如下算法（针对解法一）voidpurge(List&La,ListLb){

InitList（La）；//初始化La为空表

La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度

for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取Lb中第i个数据元素赋给e

if(ListEmpty(La)||!LocateElem(La,e,equal))

ListInsert(La,++La_len,e);//La中不存在和e相同的数据元素，则插入之

}//for}//purge思考题：请针对例子2-2C语言描述，写出解法二对应算法。2.1线性表的类型定义例2-3

P20例子2-2。归并两个“其数据元素按值非递减有序排列的”线性表LA和LB，求得线性表LC也具有同样特性。算法2.3：C语言描述如下：voidMergeList(ListLa,ListLb,List&Lc){//已知线性表La和Lb中的元素按值非递减排列。归并La和Lb得到新的线性表Lc，Lc的元素也按值非递减排列。

InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);//求线性表的长度

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

GetElem(La,i,ai);GetElem(Lb,j,bj);2.1线性表的类型定义

if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}//将较小的元素优先插入Lc

while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}//La的剩余元素插入Lc

while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}//Lb的剩余元素插入Lc}//merge_list算法结果演示：思考题：为什么上述两个while循环体只会执行其中的一个？2.1线性表的类型定义●

算法时间复杂度分析:

假设:

GetElem和ListInsert这两个操作的执行时间和表长无关，LocateElem的执行时间和表长成正比，则算法2.1的时间复杂度为

O(ListLength(LA)×ListLength(LB))；

例2-2(解法一)的时间复杂度为

O(ListLength2(LB))；算法2.2的时间复杂度为

O(ListLength(LB))；

可见，不同的算法策略所得不同算法的时间复杂度不同。算法2.3的时间复杂度为

O(ListLength(LA)＋ListLength(LB))2.1线性表的类型定义线性表的顺序表示：

以元素在计算机内存中的“物理位置相邻”来表示线性表中数据元素之间的逻辑关系，如下所示：

Locate(ai+1)=Locate(ai)+sizeof(DataType) Locate(ai)=Locate(a0)+sizeof(DataType)*i称第一个数据元素的存储地址为线性表的起始地址，称作线性表的基地址。只要确定了基地址，线性表中任意数据元素都可以随机存取。因此线性表的顺序存储结构为一种随机存取的存储结构。2.2线性表的顺序表示和实现逻辑地址数据元素存储地址数据元素0k0Loc(k0)k01k1Loc(k0)+ck1…………ikiLoc(k0)+i*cki……n-1kn-1Loc(k0)+(n-1)*ckn-1●线性表的顺序存储结构示意图2.2线性表的顺序表示和实现2.2线性表的顺序表示和实现线性表顺序存储（顺序表）结构定义：在C语言中可以用一维数组表示。

constLIST_INIT_SIZE=100;//表初始空间分配量

constLISTINCREMENT=10;//空间分配增量

typedefstruct{ElemType*elem;//存储空间基址

intlength;//顺序表的当前长度

intlistsize;//顺序表当前存储容量

}SqList;2.2线性表的顺序表示和实现●根据顺序表的存储特点，顺序表的基本操作：1、构造空表：

StatusInitList_Sq(SqList&L)

{//构造空表L

L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);L.length=0;//表当前长度

L.listsize=LIST_INIT_SIZE;//表容量

L.incrementsize=LISTINCREMENT;returnOK;}//InitList_Sq2.2线性表的顺序表示和实现2.

intinsert_sq(SqListpalist,DataTypex,intp)

在palist所指顺序表中下标为p的位置上插入一个值为x的元素，并返回插入成功与否的标志。此运算在0≤p≤n时有意义3.

intdelete_sq(SqListpalist,intp)

在palist所指顺序表中删除下标为p的元素，并返回删除成功与否的标志。此运算在0≤p＜n时有意义2.2线性表的顺序表示和实现3.

intfirst_sq(SqListpalist)

求palist所指顺序表中第一个元素的下标。当palist为空表时返回一个特殊的下标值-14.intlocate_sq(SqListpalist,DataTypex)

在palist所指顺序表中寻找值为x的元素的下标，若palist中不存在值为x的元素，则返回一个特殊的下标值-12.2线性表的顺序表示和实现5.DataTyperetrieve_sq(SqListpalist,intp)

在palist所指顺序表中，寻找下标为p(0≤p＜n)的元素，并将该元素的值作为函数值返回，若palist中无下标为ｐ的元素，则返回一个特殊的值6.intnext_sq(SqListpalist,intp)

求palist所指顺序表中下标为p的元素的后继元素下标，当不存在下标为p的元素或虽有该元素但无后继时，返回一个特殊的下标值-12.2线性表的顺序表示和实现7.intprevious_sq(SqListpalist,intp)

求palist所指顺序表中下标为p的元素的前驱元素下标，当不存在下标为p的元素，或虽有该元素但无前驱时，本函数返回一个特殊的下标值-18.voidcreateNullList_sq(SqListpalist)

置palist所指顺序表为空表9.intisNullList_sq(SqListpalist)

判别palist所指顺序表是否为空表。若为空则返回1,否则返回02.2线性表的顺序表示和实现●

顺序表的插入和删除操作及算法描述：

1）线性表的插入操作示意图。P23图2.3

..\数据结构C语言版.pdf。插入算法C语言描述如下：

StatusListInsert_Sq(SqList&L,inti,ElemTypee){//在顺序表L中第i个位置之前插入新元素e

if(i<1||i>L.length+1)returnERROR;//非法的位置

if(L.length>=L.listsize){//当前空间已满

newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));

2.2线性表的顺序表示和实现if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize=L.listsize+INCREMENT;}

q=&(L.elem[i-1]);//定位位置i，对应数组下标为i-1

for(p=&(L.elem[L.length-1]),p>=q;--p){*(p+1)=*p;}//插入位置及之后的元素后移一个单元*q=e;//e插入位置iL.length++;//表长增1

returnOK;

}//ListInsert_Sq2.2线性表的顺序表示和实现2）线性表的删除操作示意图。P23图2.4

..\数据结构C语言版.pdf。删除算法C语言描述如下：StatusListDelete_Sq(SqList&L,intI,ElemType&e){//删除L中第i个元素，后面的元素前移

if(i<1||i>L.length)returnERROR;//i值不合法p=&(L.elem[i-1]);//p为被删除元素的位置e=*p;//被删除元素的值赋给eq=L.elem+L.length-1;//表尾元素的位置for(++p;p<=q;++p){*(p-1)=*p;}

//被删除元素之后元素左移--L.length;//表长减1returnOK;

}//ListDelete_Sq2.2线性表的顺序表示和实现插入元素时的时间效率：

设pi是在第i个元素之前插入一个元素的概率，则在长度为n的线性表中插入一个元素时所需移动元素的次数的期望值（平均次数）为：设则有2.2线性表的顺序表示和实现删除元素时的时间效率：

设qi是删除第i个元素的概率，则在长度为n的线性表中删除一个元素时所需移动元素的次数的期望值（平均次数）为：设则有2.2线性表的顺序表示和实现算法2.7：两个顺序表的合并P26voidMergeList_Sq(SqListla,SqListlb,SqList&lc){//已知顺序表La和Lb的元素按值非递减排列。与P21算法2.2类似

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

ElemType*pa,*pb,*pc,*pa_last,*pb_last; pa=la.elem;pb=lb.elem; lc.listsize=la.length+lb.length; pc=lc.elem=(ElemType*)malloc(sizeof(ElemType)*lc.listsize); if(!lc.elem)exit(OVERFLOW); pa_last=pa+la.length-1; pb_last=pb+lb.length-1;2.2线性表的顺序表示和实现

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的剩余元素

}//EndofMergeList_Sq()算法结果演示：..\数据结构-光盘\DS-Algo-VC2.2线性表的顺序表示和实现例：设计一个算法，用尽可能少的辅助空间将顺序表中前m个元素和后n个元素进行整体互换。即将线性表(a1,a2,…,am,b1,b2,…,bn)改变成

(b1,b2,…,bn,a1,a2,…,am)

分析1：取一临时空间，将b1放入临时空间，a1-am全部后移一个位置，如此b2,直到bn。

特点：牺牲时间节省空间。

分析2：另外申请空间m+n个元素单元，将b,a分别写入。时间复杂度将为O（n+m）。2.2线性表的顺序表示和实现算法一实现：voidexchange1(SqList&L,intm,intn){//线性表分成两个部分后，两部分倒置

for(i=1;i<=n;i++){w=L.Elem[i+m];//临时空间w

for(j=m;j>=1;j--)

L.Elem[i+j]=L.Elem[i+j-1];L.Elem[i]=w;//依次转移w，

}

}//exchange12.3线性表的链式表示及实现顺序表的缺陷：插入/删除耗费大量时间。因此，引入线性链表：用一组任意单元表示数据元素和数据元素之间的关系（这些单元可以是连续的，也可以是不连续的）。其结点由两部分信息组成：

（1）数据域：存储数据元素信息；（2）指针域：存储直接后继的存储位置（地址）。●链表头指针指示链表中的第一个结点的存储位置，整个链表的存取必须从头指针开始。最后一个结点没有直接后继，其指针域为“空”（NULL）。2.3线性表的链式表示及实现2.3.1单链表：

数据域指针域存储地址数据域指针域

1 Li 437 Qian 1313 Sun 1 19 Wang NULL25 Wu 3731 Zhao 737 Zheng1943 Zhou 2531头指针H2.3线性表的链式表示及实现单链表：单链表的逻辑结构LiZhaoQianSunZhouWuZhengWang^H2.3线性表的链式表示及实现单链表：一般附加一个头结点，其数据域不存储信息，指针域存储指向第一个结点的指针。

a1an^a2...头指针H头结点H^非空表空表单链表结构：注意头指针，头结点等概念的不同含义。

2.3线性表的链式表示及实现2.3线性表的链式表示及实现为什么要加头结点？

头结点是链表的开始结点之前的一个附加结点。

使用头结点的好处在于：（1）由于开始结点(第一个数据节点)位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无须进行特殊处理。（2）无论链表是否为空，其头指针是指向结点的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。线性链表的定义typedefintElemType;/*定义元素类型为整型，也可定义为其他类型*/structLNode; /*单链表结点类型*/typedefstructLNode*PNode;/*结点指针类型*/=======================================structLNode /*单链表结点存储结构*/{

ElemTypedata；//数据域

structLNode *next;//指针域}Lnode,*LinkList;2.3线性表的链式表示及实现单链表基本操作：

1、StatusInitList_L(LinkList&L){

//建立头结点，其Next为空。初始化为空表

L=(LinkList)malloc(sizeof(LNode));L->next=NULL;returnOK;}2.3线性表的链式表示及实现2、VoidCreateList_L(LinkList&L,intn){/*创建一个带头结点的链表*/

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;//P指针域赋值

L->next=p;

}

}//CreateList_L

算法结果演示：..\数据结构-光盘\DSDemoW2.3线性表的链式表示及实现3、算法2.8单链表的元素读取（非随机存取）StatusGetElem_L(LinkList&L,inti,ElemType&e){//L为带//带头结点的单链表的头指针。当第i个元素存在时，其值赋给e并返回//OK，否则返回ERROR

LinkListp;//链表指针变量pp=L->next;intj=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_L2.3线性表的链式表示及实现单链表结点插入和删除P29图2.8、2.9..\数据结构C语言版.pdf2.3线性表的链式表示及实现abpabpcs->next=p->next;

注：顺序不能反单链表插入结点

p->next=p->next->next;

单链表删除结点abxsp2.p->next=s;●单链表结点插入算法描述：

StatusListInsert_L(LinkList&L,inti,ElemTypee){//算法2.9

//在带头结点的单链线性表L的第i个元素之前插入元素e

LinkListp,s;p=L;//p指向L头结点

intj=0;while(p&&j<i-1){//寻找第i-1个结点

p=p->next;++j;}if(!p||j>i-1)returnERROR;//插入位置合法性检查，

i小于1或者大于表长？

s=(LinkList)malloc(sizeof(LNode));//生成新结点

s->data=e;s->next=p->next;//插入L中

p->next=s;returnOK;}//LinstInsert_L算法结果演示：..\数据结构-光盘\DSDemoW2.3线性表的链式表示及实现●单链表结点删除算法描述：StatusListDelete_L(LinkList&L,inti,ElemType&e){//算法//2.10。在带头结点的单链线性表L中，删除第i个元素，并由e返回其值

LinkListp,q;p=L;intj=0;while(p->next&&j<i-1){//寻找第i个结点

p=p->next;++j;}if(!(p->next)||j>i-1)returnERROR;//删除位置合法性检查，是否合理？

q=p->next;//预删除的结点ip->next=q->next;//删除并释放结点

e=q->data;free(q);returnOK;}//ListDelete_L算法结果演示：..\数据结构-光盘\DSDemoW2.3线性表的链式表示及实现●单链表查找算法描述：算法2.12LNode*LocateElem_L(LinkListL,ElemTypee){//在L中找到第一个值和e相同的结点，返回其

//地址，若不存在，返回空值。

if(!L)returnNULL;p=L;

while(p&&p->data!=e)p=p->next;returnp;}算法结果演示：..\数据结构-光盘\DS-Algo-VC该算法时间复杂度：O(n)2.3线性表的链式表示及实现算法2.13：将两个有序链表归并为一个新的有序链表。分析：有两个非递减有序链表La,Lb.现归并La,Lb得到Lc。其条件Lc非递减有序，即当前节点，大于前者，小于后者。VoidMergeList_L(LinkList&Lc,LinkListLa,LinkListLb){

//已知两个非递减单链表为La,Lb

//归并单链表La,Lb,形成新的有序链表Lc

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

Lc=pc=La;//用La的头结点作为Lc的头结点2.3线性表的链式表示及实现

while(pa&&pb){//La,Lb非空

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的头结点，为啥不释放La？}//MergeList_L算法结果演示：..\数据结构-光盘\DSDemoW时间复杂度分析：O(n)

2.3线性表的链式表示及实现单链表与顺序表的比较：单链表的存储密度比顺序表低，它多占用了存储空间。但在许多情况下，链式的分配比顺序分配有效，顺序表必须分配足够大的连续的存储空间，而链表可以利用零星的存储单元在单链表里进行插入、删除运算比在顺序表里容易得多对于顺序表，可随机访问任一个元素，而在单链表中，需要顺着链逐个进行查找，因此单链表适合于在成批地、顺序地处理线性表中的元素时采用。（单链表不是随机存取）2.3线性表的链式表示及实现2.3.2循环链表最后一个结点的指针域的指针又指回第一个结点操作与线性链表基本一致循环条件：p->next==p->head表空条件：p->head->next==p->head2.3线性表的链式表示及实现HH空循环链表非空循环链表2.3.3双向链表可以在单链表的每一个结点里再增加一个指向其前趋和后继的指针域。这样链表中有两条不同方向的链。优点：既可以找前驱，也可以找后继。2.3线性表的链式表示及实现H

^^H^^空双向链表非空双向链表双向链表存储结构：

typedefstructDuLNode{

ElemTypedata;

structDuLNode*prior;

structDuLNode*next;

}DuLNode,*DuLinkList;2.3线性表的链式表示及实现双向循环链表2.3线性表的链式表示及实现H

H空双向循环链表非空双向循环链表2.3线性表的链式表示及实现双向(循环)链表的插入和删除删除双向链表的结点1.p->prior->next=p->next;2.p->next->prior=p->prior;往双向链表中插入结点s->prior=p->prior;p->prior->next=s;//先左s->next=p;p->prior=s;//后右顺序不可颠倒ABCpABCsp①②③④①②③④双向循环链表的插入算法：StatusListInsert_Dul(DuLinkList&L,inti,ElemTypee){//在带头结点的双向循环链表第i个位置插入元素e

if(!(p=GetElemP_Dul(L,i)))returnERROR；//表的长度未达i，定位is=(DuLinkList)malloc(sizeof(ElemType));//生成结点

if(!s)exit(OVERFLOW)//空间不够，溢出

s->data=e;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;returnOK;//更改指针域，插入结点e

}//ListInsert_Dul2.3线性表的链式表示及实现双向循环链表的删除算法：StatusListDelete_Dul(DuLinkList&L,inti,ElemType&e){//在带头结点的双向循环链表中删除第i个位置元素，并将结果存入e

if(!(p=GetElemP_Dul(L,i)))returnERROR；//表的长度未达i，定位i

e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);//更改指针域，释放第i个结点

returnOK;

}//ListDelete_Dul2.3线性表的链式表示及实现线性链表与顺序表的比较：线性链表

优点：空间的合理利用；插入和删除时不需要移动缺点：实现基本操作（如求表长）不如顺序表数据元素的“位序”概念被淡化很多场合下，线性链表是线性表的首选存储结构2.3线性表的链式表示及实现一个带头结点的线性链表类型定义：P37~38..\数据结构C语言版.pdf2.3线性表的链式表示及实现多项式运算的问题，几乎成为表处理的一个经典问题。用单链表结构来表示多项式，研究两个多项式的相加运算一元多项式

Pn(x)=p0+p1x+p2x2++pnxnQm(x)=q0+q1x+q2x2++qmxm在计算机中可以用一个线性表P,Q（顺序存储）来表示：P=(p0,p1,p2,,pn)Q=(q0,q1,q2,,qm)

每一项的指数都隐含在系数pi,qj的序号里2.4一元多项式的表示及相加多项式相加：Rn(x)=Pn(x)+Qm(x)(m<n)在计算机中可以用一个线性表R（顺序存储）来表示：R=(p0+q0,p1+q1,p2+q2,pm+qm,pm+1,,pn)采用顺序结构使的多项式相加的算法非常简洁这种表示方法对于所有项都比较全的时候是很好的，但是如果指数很高并且变化很大时，不合适，顺序表的最大长度难以确定。2.4一元多项式的表示及相加例如：一个稀疏多项式

:

S(x)=1+3x109-5x231+6x354把每一项的系数和指数都存储下来，也就是对于每一项都用两个数据项来存储。即为如下的形式：P=((p1,e1),(p2,e2),(pm,em))可用线性表((1,0),(3,109),(-5,231),(6,354))表示对于这种表示方法，采用链式存储。利用单链表表示多项式时，每个结点设有三个域：系数域coef，指数域exp和链域next。

2.4一元多项式的表示及相加coefexpnext抽象数据类型一元多项式的定义ADTPolynomial{

数据对象：D＝{ai|ai∈TermSet,i=1,2,...,m,m≥0

TermSet中的每个元素包含一个表示系数的实数和表示指数的整数

}

数据关系：R1＝{<ai-1,ai>|ai-1,ai∈D,且ai-1中的指数值＜ai中的指数值，i=2,...,n}

基本操作：

CreatPolyn(&P,m)

操作结果：输入m项的系数和指数，建立一元多项式P。

DestroyPolyn(&P)

初始条件：一元多项式P已存在。2.4一元多项式的表示及相加

操作结果：销毁一元多项式P。

PrintPolyn(&P)

初始条件：一元多项式P已存在。操作结果：打印输出一元多项式P。

AddPolyn(&Pa,&Pb)

初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相加运算，即：Pa=Pa＋Pb，并销毁一元多项式Pb。

SubtractPolyn(&Pa,&Pb)

初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相减运算，即：Pa=Pa－Pb，并销毁一元多项式Pb。2.4一元多项式的表示及相加

MultiplyPolyn(&Pa,&Pb)

初始条件：一元多项式Pa和Pb已存在。操作结果：完成多项式相乘运算，即：Pa=Pa×Pb，并销毁一元多项式Pb。

PolynLength(P)

初始条件：一元多项式P已存在。操作结果：返回一元多项式P中的项数。

}ADTPolynomial2.4一元多项式的表示及相加例AH=1-10x6+2x8+7x14BH=-x4+10x6-3x10+8x14+4x18CH(x)=AH(x)+BH(x)它的单链表表示如图2.4一元多项式的表示及相加多项式的加法运算规则:(1)若指数相等，系数相加，得C(x)的一项（若和为0，此项不存在）；(2)若A(x)当前项指数小于B(x)，复抄A(x)的这一项到C(x)上；(3)若A(x)当前项指数大于B(x)，复抄B(x)的这一项到C(x)上；(4)若一个多项式每项都加到C(x)上了，就把另一多项式的剩余部分复抄到C(x)上。2.4一元多项式的表示及相加C(x)是动态建立的，需要从表头指针所指的结点开始检测，为此我们设两个指针pa和pb分别指向两个多项式中当前被检测的结点；同时还需要记清C(x)建在什么地方，又设指针pc指向C(x)当前的最后一个结点。2.4一元多项式的表示及相加根据运算规则，考虑以下三种情况：（1）exp(pa)>exp(pb)：把pb指的结点复抄到C表的后面。所以调用过程——链接在C(x)上(coef(pb),exp(pb),pc)，并移动指针pb，继续往下检测；（2）exp(pa)=exp(pb)：将它们的系数相加，为此用一个x单元存放coef(pa)+coef(pb)的和。若x≠0，就调用过程——链接在C(x)上(x,exp(pb),pc)，并移动指针pa，pb；（3）exp(pa)<exp(pb)：把pa所指的结点复抄到C表的后面。所以调用过程——链接在C(x)上(coef(pa),exp(pa),pc),并移动指针pa。2.4一元多项式的表示及相加一元多项式抽象数据类型的实现：typedefstruct_ElemType//元素类型{ float coef; /*多项式系数*/

int expn; /*多项式指数*/}ElemType;/*NodeType单个结点类型--存储结构*/typedefstruct_Polyn{

ElemType data; /*数据域*/

struct_Polyn*next; /*指针域*/}Node,*Link; /*Nodetype&NodePointer2.4一元多项式的表示及相加typedefstruct{ Link head,tail; /*用作链表的头节点和尾指针*/

int len; /*可以用来记录链表的长度*/}LinkList,*PLinkList;typedefLinkListpolynomial;/*Initializealinklist–操作*/voidInitPolyn(polynomial&P);/*所用到的函数的原型化声明*//*把两个一元多项式相加*/voidAddPolyn(polynomial&pa,polynomial&pb);/*创建一个一元多项式*/voidCreatePolyn(polynomial&P,intm);2.4一元多项式的表示及相加/*实现两个一元多项式的相乘*/voidMultiplyPolyn(polynomial&pa,polynomial&pb);/*打印该链表的结果*/voidPrintPolyn(polynomialP);/*比较两个节点的指数的大小*/Intcmp(ElemTypea,ElemTypeb);/*删除一个链表*/voidFreeList(polynomialP);/*Multiplyapolynomialwithanelement*/voidMultiItem(polynomialpResultList,polynomialP,LinkItem);/*Multiplytwolinklist*/PLinkListMultiLinkList(polynomialP1,polynomialP2);2.4一元多项式的表示及相加算法2-23多项式的加法:算法思路P41图2-17、18..\数据结构C语言版.pdfvoidAddPolyn(polynomial&Pa,polynomial&Pb){ ha=GetHead(Pa);hb=GetHead(Pb);//头结点位置

qa=NextPos(ha); qb=NextPos(hb)；//开始结点位置

while(!Empty(Pa)&&!Empty(Pb)) { a=GetCurElem(qa);b=GetCurElem(qb); switch(*cmp(a,b)){ case-1:/*第一个链表中当前结点的指数值小*/

ha=qa;qa=NextPos(Pa,qa);break;//同时移动指针

case0: /*指数值相等*/

sum=a.coef+b.coef;

if(sum!=0.0){SetCurElem(qa,sum);ha=qa; }2.4一元多项式的表示及相加 else{ /*若为零，则释放qa所指向的结点空间*/

DelFirst(ha,qa);FreeNode(qa);}

DelFirst(hb,qb);FreeNode(qb);

qb=NextPos(Pb,hb);qa=NextPos(Pa,qa);break;

case1:/*第一个链表中当前结点的指数值大*/

DelFirst(hb,qb);InsFirst(ha,qb);//从Lb中删除qb，将qb插入La

qb=NextPos(Pb,hb);ha=NextPos(Pa,ha);break;

} /*EndofSwitch*/

} /*Endofwhile*/

if(!Empty(Pb))Append(Pa,qb);//链接Pb中剩余结点

FreeNode(hb);