《数据结构与算法》第二章线性表

第二章线性表2.1

线性表的类型定义2.2线性表的顺序表示和实现2·3线性表的链式表示和实现2.4一元多项式的表示及相加逻辑结构存储结构操作建立。。。线性表广义表串树二叉树图数组堆栈和队列顺序存储链式存储索引散列清除。。。插入数据元素删除数据元素修改数据元素排序查找(检索)2.1线性表的类型定义一、线性表的逻辑结构二、线性表的ADT例2-1利用线性表运算实现A=A

B例2-2利用线性表运算把两个有序的序列合并成一个有序序列2.2线性表的顺序表示和实现2·3线性表的链式表示和实现一、线性表的逻辑结构1.线性表的定义2.线性结构的特点

3.线性表的长度4.位序5.空表如：(A,B,C,D,………,Z)(85,67,78,65,……,92)((‘m’,87),(‘f’,65),……(‘m’,92))

1.定义:含有大量记录的线性表又称为文件线性表是由有限个元素构成的有序序列可记作：〔a1,a2,……,an〕2.特点:(1)表中每个元素都有它自己的位置除第一个元素外，每个元素都有唯一的前驱除最后一个元素外，每个元素都有唯一的后继i是ai在线性表中的位序(索引)(2)表中元素具有相同特性(数据类型),

属于同一数据对象有序性均匀性二、线性表的ADTADTList{数据对象:D={ai∣ai∈ElemSet,i=1,2,3，…,n,n≥0}数据关系:R={<ai-1,ai>∣ai-1、ai∈D,i=2,3,…,n}根本操作:InitList(&L);操作结果:构造一个空的线性表L.DestroyList(&L);

初始条件:线性表L已经存在.

操作结果:销毁线性表L.1003张三女9887671002李四男9992741021王五男787677ClearList(&L);

初始条件:线性表L已经存在.

操作结果:将L重置为空表.1003张三女9887671002李四男9992741021王五男7876771008万一女756776

ListEmpty(L);初始条件:线性表L已经存在.操作结果:假设L为空表,那么返回TRUE,否那么返回FALSE.1003张三女9887671002李四男9992741021王五男787677TRUEFALSEListLength(L);

初始条件:线性表L已经存在.

操作结果:返回L中数据元素个数.GetElem(L,i,&e);

初始条件:线性表L已经存在,1≤i≤ListLength(L).

操作结果:用e存放L中第i个数据元素的值.1003张三女9887671002李四男9992741021王五男7876771008万一女756776ListLength(L)为4GetElem(L,3,e);e为王五的数据LocateElem(L,e,compare());初始条件:线性表L已经存在,compare()是数据元素判定函数.操作结果:返回L中第1个与e满足关系compare()的数据元素的位序.假设这样的数据元素不存在,那么返回值为0.1003张三女9887671002李四男9992741021王五男7876771008万一女756776假设e为王五，那么LocateElem(L,e,equal)返回3假设e为马六，那么LocateElem(L,e,equal)返回0PriorElem(L,cur_e,&pre_e);初始条件:线性表L已经存在.操作结果:假设cur_e是L的数据元素,且不是第一个,那么用pre_e存放它的前驱,否那么操作失败,pre_e无定义.1003张三女9887671002李四男9992741021王五男7876771008万一女756776假设cur_e为李四，PriorElem(L,cur_e,pre_e);pre_e为张三假设cur_e为张三，PriorElem(L,cur_e,pre_e);pre_e值无意义NextElem(L,cur_e,&next_e);初始条件:线性表L已经存在.操作结果:假设cur_e是L的数据元素,且不是最后一个,那么用next_e存放它的后继,否那么操作失败,next_e无定义.1003张三女9887671002李四男9992741021王五男7876771008万一女756776假设cur_e为李四，NextElem(L,cur_e,next_e);next_e为王五假设cur_e为万一，NextElem(L,cur_e,next_e);next_e值无意义ListInsert(&L,i,e);初始条件:线性表L已经存在,1≤i≤ListLength(L)+1.操作结果:在L中第i个位置之前插入新的数据元素e,L的长度加1.1003张三女9887671002李四男9992741021王五男7876771008万一女756776ListInsert(L,3,e);e为马六的数据1033马六男8080801021王五男7876771008万一女756776ListDelete(&L,i,&e);初始条件:线性表L已经存在且非空,1≤i≤ListLength(L).操作结果:删除L的第i个数据元素,并用e存放其值,L的长度减1.1003张三女9887671002李四男9992741021王五男7876771008万一女756776ListDelete(L,3,e);1008万一女756776ListTraverse(L,visit());初始条件:线性表L已经存在.操作结果:依次对L的每个数据元素调用函数visit().一旦visit()失败,那么操作失败.}ADTListInitList(&L);DestroyList(&L);ClearList(&L);ListLength(L);GetElem(L,i,&e);LocateElem(L,e,compare());PriorElem(L,cur_e,&pre_e);NextElem(L,cur_e,&next_e);ListInsert(&L,i,e);ListDelete(&L,i,&e);ListTraverse(L,visit());例2-1用线性表LA和LB分别表示集合A和B，利用线性表运算实现A=A

Bvoidunion(List&La,ListLb){La_len=ListLength(La);//计算A的长度Lb_len=ListLength(Lb);//计算B的长度

for(i=1;i<=Lb_len;i++){GetElem(Lb,i,e);//取B中一个元素if(!LocateElem(La,e,equal))//检查A中有无？ListInsert(La,++La_len,e);//没有就插在表尾}}//union例2-2线性表LA和LB分别表示两个非递减序的有序序列，利用线性表运算把LA和LB合并成一个有序序列LCvoidMergeList(ListLa,ListLb,List&Lc){InitList(Lc);i=j=1;k=0;La_len=ListLength(La);Lb_len=ListLength(Lb);

while((i<=La_len)&&(j<=Lb_len)){GetElem(La,i,ai);GetElem(Lb,j,bj);if(ai<=bj){ListInsert(Lc,++k,ai);++i;}else{ListInsert(Lc,++k,bj);++j;}}

while(i<=La_len){GetElem(La,i++,ai);ListInsert(Lc,++k,ai);}while(j<=Lb_len){GetElem(Lb,j++,bj);ListInsert(Lc,++k,bj);}}//MergeList线性表的物理结构a1a2……an

∧

a1a3a2abdfh42576398010110线性表的物理结构静态链表2.2线性表的顺序表示和实现线性表的顺序表示是指:

用一组地址连续的存储单元

依次存储线性表中的数据元素即：逻辑相邻，物理也相邻，以物理相邻表示元素之间的逻辑相邻a1a2……an一、顺序表示设ai的物理存储位置为LOC(ai)，需要的存储单元长度为hLOC(ai)=LOC(ai-1)+hLOC(ai)=LOC(a1)+(i-1)*h

每个元素的存储位置与线性表的起始位置相差一个常数,该常数与数据元素的位序成正比因此，可以随机存取，且任一元素的存取时间相同.//–––––线性表的动态分配顺序存储结构–––––#defineLIST_INIT_SIZE100//线性表存储空间的初始分配#defineLISTINCREMENT10//线性表存储空间的分配增量typedefstruct{

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

intlength;//当前长度

intlistsize;//当前分配的存储容量}SqList;3597...L.elemSqListL;L.length=4;L.listsize=100;typedefintElemType;typedefstruct{ElemType*elem;intlength;intlistsize;}SqList;StatusInitList_Sq(SqList&L){//构造一个空的线性表L.L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW);//存储分配失败

L.length=0;//空表长度为0L.listsize=LIST_INIT_SIZE;//初始存储容量

returnOK;}//InitList_Sq二、线性表的动态分配实现01234567……98991.初始化：L.elem2.插入元素StatusListInsert_Sq(SqList&L,inti,ElemTypee){q=&(L.elem[i-1]); //q为插入位置if(L.length>=1)for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;*q=e;//插入e++L.length;returnOK;//表长增1}//ListInsert_SqL.elemi-1qpen-1if(i<1‖i>L.length+1)returnERROR;if(L.length>=L.listsize) {newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType));if(!newbase)exit(OVERFLOW);//存储分配失败

L.elem=newbase;//新基址

L.listsize+=LISTINCREMENT;//增加存储容量

}

算法执行时间主要花在移动元素上设pi表示在第i个元素之前插入新元素的概率在第i个元素之前插入新元素需移动n-i+1个元素平均移动次数为：T(n)=O(n)3.删除元素StatusListDelete_Sq(SqList&L,inti,ElemType&e)

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

//i的合法值为1≤i≤ListLength_Sq(L)if((i<1)‖(i>L.length))returnERROR;

//i值不合法}//ListDelete_sqL.elemi-1pqen-1

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;设删除第i个元素的概率为Pi那么平均移动元素的次数为：T(n)=O(n)intLocateElem_Sq(SqListL,ElemTypee,Status(*compare)(ElemType,ElemType)){//在顺序线性表L中查找第1个值与e满足compare()的元素的位序//假设找到,那么返回其在L中的位序,否那么返回0i=1;//i的初值为第1个元素的位序p=L.elem;//p的初值为第1个元素的存储位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<=L.length)returni;elsereturn0;}//LocateElem_Sqvoidunion_Sq(SqList&La,SqListLb){//将所有在线性表Lb中但不在La中的数据元素插入到La中La_len=ListLength_Sq(La);Lb_len=ListLength_Sq(Lb);//求线性表的长度for(i=1;i<=Lb_len;i++){GetElem_Sq(Lb,i,e);//取Lb中第i个数据元素赋给eif(!LocateElem_Sq(La,e,equal))ListInsert_Sq(La,++La_len,e);//La中不存在和e相同的数据元素,那么插入之}}//union4·合并两个集合5·合并有序序列顺序线性表La和Lb的元素按值非递减排列归并La和Lb得到新的顺序线性表Lc,Lc的元素也按值非递减排列voidMergeList_Sq(SqListLa,SqListLb,SqList&Lc){InitList_Sq(Lc);i=j=1;k=0;La_len=ListLength_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++,a);ListInsert_Sq(Lc,++k,a);}while(j<=Lb_len){GetElem_Sq(Lb,j++,b);ListInsert_Sq(Lc,++k,b);}}//MergeLest_SqvoidMergeList_Sq(SqListLa,SqListLb,SqList&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++;eles*pc++=*pb++;

}while(pa<=pa_last)*pc++=*pa++;

//插入La的剩余元素

while(pb<=pb_last)*pc++=*pb++;

//插入Lb的剩余元素}//MergeLest_Sq2·3线性表的链式表示和实现一、线性链表

静态链表二、循环链表三、双向链表∧∧∧∧数据域指针域

1.存储映象

用一组任意的存储单元存储线性表中的数据元素既需要表示数据元素,又需要表示相邻元素的逻辑关系。链表中只有一个指针域的链表称为线性链表或单链表一、线性链表2.线性链表的特点：

★整个链表的存取必须从头指针开始★最后一个结点的指针域为空NULL

★用指针表示数据元素之间的逻辑关系链表是非随机存取的存储结构

★可附设头指针

★一种动态结构，表可以扩充∧∧3.线性链表的运算⑴存储结构typedefstructLNode{ElemTypedata;

structLNode*next;}LNode,*LinkList;LNodedatanextLinkListStatusInitList_L(LinkList&L){//建立一个空的链表，L为带头结点的单链表的头指针.

L=(LinkList)malloc(sizeof(LNode));//生成头结点

if(!L)returnERROR;L->next=NULL;returnOK;}//InitList_L∧⑵获取第i个元素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_LStatusListInsert_L(LinkList&L,inti,ElemTypee){//在带头结点的单线性链表L中第i个位置之前插入元素ep=L;j=0;while(p&&j<i-1){p=p->next;++j;}

//寻找第i-1个结点

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;}//ListInsert_L⑶插入元素⑷删除元素StatusListDelete_L(LinkList&L,inti,ElemType&e){//在带头结点的单链线性表L中,删除第i个元素,并由e返回其值

p=L;j=0;

while(p->next&&j<i-1){p=p->next;++j;}//寻找第i个元素,并令p指向其前驱

if(!(p->next)‖j>i-1)returnERROR;//删除位置不合理

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

e=q->data;free(q);returnOK;}//ListDelete_LvoidCreateList_L(LinkList&L,intn){//逆位序输入n个元素的值,建立带表头结点的单链线性表L.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⑸逆位序输入元素的值，建立线性链表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;L->next=p;}}//CreateList_L⑹把两个有序链表合并成一个有序链表voidMergeList_L(LinkListLa,LinkListLb,LinkList&Lc){InitList_L(Lc);i=j=1;k=0;La_len=ListLength_L(La);Lb_len=ListLength_L(Lb);while((i<=La_len)&&(j<=Lb_len))//La和Lb均为空

{GetElem_L(La,i,ai);GetElem_L(Lb,j,bj);if(ai<=bj){ListInsert_L(Lc,++k,ai);++i;}else{ListInsert_L(Lc,++k,bj);++j;}}while(i<=La_len){GetElem_L(La,i++,a);ListInsert_L(Lc,++k,a);}while(j<=Lb_len){GetElem_L(Lb,j++,b);ListInsert_L(Lc,++k,b);}}//MergeLest_LvoidMergeList_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静态链表特点:1.在静态空间里实现动态数据结构2.两个链表:数据链表和空闲空间链表3.没有现成的空间管理函数下标01234567891011abdfhabdfh42576398010110234567891.静态链表用一维数组存储链表//–––––线性表的静态单链表存储结构–––––//#defineMAXSIZE1000

//链表的最大长度typedefstruct{ElemTypedata;intcur;}component,SlinkList[MAXSIZE];2·运算：

1 2 3456 78 910110下标01234567891011123456789⑴初始化voidInitSpace_SL(SlinkList&space){//将一维数组space中各分量链成一个备用链表,//space[0].cur为头指针，"0"表示空指针

for(i=0;i<MAXSIZE-1;++i)space[i].cur=i+1;space[MAXSIZE-1].cur=0;}//InitSpace_SL123456789

⑵申请建立一个结点intMalloc_SL(SlinkList&space){//假设备用空间链表非空,那么返回分配的结点下标,否那么返回0i=space[0].cur;if(space[0].cur)space[0].cur=space[i].cur;returni;}//Malloc_SL⑶回收一个结点voidFree_SL(SlinkList&space,intk)

⑶回收一个结点voidFree_SL(SlinkList&space,intk)

//将下标为k的空闲结点收回到备用链表{space[k].cur=space[0].cur;space[0].cur=k;}//Free_SL⑷查找第一个值为e的元素intLocateElem_SL(SlinkListS,ElemTypee){//在静态链表线性表S中查找第1个值为e的元素.//假设找到,那么返回它在S中的位序,否那么返回0.i=S[0].cur;//i指示表中第一个结点while(i&&S[i].data!=e)i=S[i].cur;//在表中顺链查找returni;}//LocateElem_SLA={a,d,h,f,m,c},B={h,t,u,c}123456789⑸完成集合运算〔A-B〕〔B-A〕0123456789101112345678910110123456789adhfmcr0123456789101182345670910110adhfmc123567u9adtfmcr0123456789101172350689410110adtfmu二、循环链表

1·特点：表中最后一个结点的指针域指向头结点从表的任一结点出发均可访问表中其他结点2·操作3·仅设尾指针的循环链表存储结构typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;

StatusListInsert_L(LinkList&L,inti,ElemTypee){//在带头结点的循环链表L中第i个位置之前插入元素e

p=L;j=0;while(p->next!=L&&j<i-1){p=p->next;++j;}

//寻找第i-1个结点

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

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

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

p->next=s;returnOK;}//ListInsert_L三、双向链表1．双向链表的结点结构//–––––线性表的双向链表存储结构–––––typedefstructDuLNode{ElemTypedata;structDuLNode*prior;

structDuLNode*next;}DuLNode,*DuLinkList;2·特点〔1〕设d为DuLinkList型变量d->next->prior=d;d->prior->next=d;〔2〕插入与删除不太方便a1a3a2表（a1,a2,a3）空表Status

ListInsert_DuL(DuLinkList&L,inti,ElemTypee){

//在带头结点的双链循环线表L中第i个位置之前插入元素e,//i的合法值为1≤i≤表长+1.

p=L->next;j=1;while(p->next!=L&&j<i){p=p->next;j++;}

if(j<i||j>i)

returnERROR;

//第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;}//ListInsert_DuLStatusListDelete_DuL(DuLinkList&L,inti,ElemType&e){//删除带头结点的双链循环线性链表L的第i个元素,i的合法值为1≤i≤表长

if(!(p=GetElemP_DuL(L,i)))returnERROR;

e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);returnOK;}//ListDelete_DuL改进线性链表的结构：1.增加表长设置2.增加表尾指针3.设置当前位置指针的操作五、对带头结点的单向链表的重新定义typedefstructLNode //结点类型{ElemTypedata; structLNode*next;}*Link,*Position;typedefstruct//链表类型{Linkhead,tail;

//分别指向线性链表中的头结点和最后一个结点

intlen;

//指向线性链表中数据元素的个数}LinkList;StatusMakeNode(Link&p,ElemTypee);//建立由p指向的值为e的结点，并返回OK，假设建立失败，那么返回ERRORStatusInitList(LinkList&L)；

//构造一个空的线性链表L.voidFreeNode(Link&p);//释放p所指向的结点eppp=NULL

∧L.headL.tailL.len=0StatusDestroyList(LinkList&L)；

//销毁线性链表L，L不再存在.StatusClearList(LinkList&L)；

//将线性表L重置为空表，并释放原链表的结点空间.

∧L.headL.head=L.tail=NULLL.len=0L.tail

∧L.headL.tail

∧L.headL.tailStatusInsFirst(Linkh,Links)；//h指向线性链表的一个结点，将s所指结点插入在h结点之后

∧sh

∧shStatusDelFirst(Linkh,Link&q);//h指向线性链表的一个结点//删除链表中h后第一个结点并以q返回

∧h

∧qhStatusAppend(LinkList&L,Links);

//将指针s所指的一串结点链接在线性表L的最后一个结点之后，

//并改变链表L的尾指针指向新的尾结点

∧L.headL.tailS

L.headL.tailS∧StatusRemove(LinkList&L,link&q);

//删除线性链表L中的尾结点并以q返回，

//改变链表L的尾指针指向新的尾结点

∧L.headL.tailq

L.headL.tail∧StatusInBefore(LinkList&L,Link&p,Links);//p指向线性链表L中的一个结点，将s所指结点插入在p所指结点之前//并修改指针p指向新插入的结点

∧sp

∧spStatusInAfter(LinkList&L,Link&p,Links);//p指向线性链表L中的一个结点，将s所指结点插入在p所在结点之后，//并修改指针p指向新插入的结点

∧sp

∧spStatusSetCurElem(Link&p,ElemTypee);//p指向线性链表L中的一个结点，用e更新p所指向结点中数据元素的值∧peElemTypeGetCurElem(Linkp);//p指向线性链表L中的一个结点，返回p所指向结点中数据元素的值StatusListEmpty(LinkListL);//假设线性表L为空表,那么返回TRUE,否那么返回FALSE.intListLength(LinkListL);//返回线性表L中数据元素个数.PositionGetHead(LinkListL);//返回线性表L中头结点的位置PositionGetLast(LinkListL);//返回线性表L中最后一个结点的位置PositionPriorPos(LinkListL,Linkp)；//P指向线性表L中的一个结点，返回p所指向结点的直接前驱的位置//假设无前驱，那么返回NULL。PositionNextPos(LinkListL,Linkp)；//P指向线性表L中的一个结点，返回p所指向结点的直接后继的位置//假设无后继，那么返回NULL。StatusLocatePos(LinkListL,inti,Link&p);//p指向线性链表L中第i个结点的位置并返回OK，i值不合法时返回ERROR。PositionLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));//返回线性表L中第1个与e满足关系compare()判定关系的数据元素的位置.//假设这样的数据元素不存在,那么返回值为NULL.StatusListTraverse(LinkListL,Status(*visit)());//依次对L的每个数据元素调用函数visit().一旦visit()失败,那么操作失败.StatusMakeNode(Link&p,ElemTypee);voidFreeNode(Link&p);StatusInitList(LinkList&L)；StatusDestroyList(LinkList&L)；StatusClearList(LinkList&L)；StatusInsFirst(Linkh,Links)；StatusDelFirst(Linkh,Link&q);StatusAppend(LinkList&L,Links);StatusRemove(LinkList&L,link&q);StatusInBefore(LinkList&L,Link&p,Links);StatusInAfter(LinkList&L,Link&p,Links);StatusSetCurElem(Link&p,ElemTypee);ElemTypeGetCurElem(Linkp);StatusListEmpty(LinkListL);intListLength(LinkListL);PositionGetHead(LinkListL);PositionGetLast(LinkListL);PositionPriorPos(LinkListL,Linkp)；PositionNextPos(LinkListL,Linkp)；StatusLocatePos(LinkListL,inti,Link&p);PositionLocateElem(LinkListL,ElemTypee,Status(*compare)(ElemType,ElemType));StatusListTraverse(LinkListL,Status(*visit)());StatusLinkInsert_L(LinkList&L,inti,ElemTypee)

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

if(!LocatePos(L,i-1,h))returnERROR;

//i值不合法

if(!MakeNode(s,e))returnERROR;

//结点存储分配失败

InsAfter(L,h,s);

//对于从第i个结点开始的链表，第i-1个结点是它的头结点

returnOK;

}//ListInsert_LvoidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc,int(*compare)(ElemType,ElemType)){//单链线性表中的元素按值非递减排列,归并和得到新的单链线性表，元素也按非递减排列if(!InitList(Lc))returnERROR; //存储空间分配失败ha=GetHead(La);hb=GetHead(Lb);//ha和hb分别指向La和Lb的头结点pa=NextPos(La,ha);pb=NextPos(Lb,hb); //pa和pb分别指向La和Lb的当前结点while(pa&&pb)//La和Lb均非空{a=GetCurElem(pa);b=GetCurElem(pb);//a和b为两表中当前比较元素if((*compare)(a,b)<=0) /a<=b{DelFirst(ha,q);Append(Lc,q);pa=NextPos(La,ha);}else{DelFirst(hb,q);Append(Lc,q);pb=NextPos(Lb,hb);}}//whileif(!ListEmpty(La))//pa

Append(Lc,pa);

//链接La中剩余结点

elseAppend(Lc,pb); //链接Lb中剩余结点FreeNode(ha);FreeNode(hb);

//释放La和Lb的头结点returnOk;}//MergeList_L多项式(Polynomial)n阶多项式Pn(x)有n+1项。

系数a0,a1,a2,…,an

指数0,1,2,…,n。按升幂排列2.4一元多项式的表示及相加Pn(x)=1+x2+4x3+2x5+6x6Sn(x)=1+x8+2x60+3x100一、一元多项式的表示((1,0),(0,1),(1,2),(4,3),(0,4),(2,5),(6,6))((1,0),(1,8),(2,60),(3,100))ADTPolynomial{数据对象:D={ai∣ai∈TermSet,i=1,2,…,m,m≥0;TermSet中的每个元素包含一个表示系数的实数和表示指数的整数}数据关系:R={<ai-1,ai>∣ai-1,ai∈D,且ai-1中的指数值<ai中的指数值,i=1,2,…,n}根本操作:CreatePolyn(&P,m)操作结果:输入m项的系数和指数,建立一元多项式P.DestroyPolyn(&P)操作结果:销毁一元多项式P.二、一元多项式的抽象数据类型定义

PrintPolyn(P)

操作结果:打印输出一元多项式P.PolynLength(P)

操作结果:返回一元多项式P中的项数,AddPolyn(&Pa,&Pb)

操作结果:完成多项式相加运算,即:Pa=Pa+Pb,并销毁一元多项式Pb.

SubtractPolyn(&Pa,&Pb)

操作结果:完成多项式相减运算,即:Pa=Pa-Pb,并销毁一元多项式Pb.

MultiplyPolyn(&Pa,&Pb)

操作结果:完成多项式相乘运算,即:Pa=Pa*Pb,并销毁一元多项式Pb.

}ADTPolynomial三、一元多项式抽象数据类型的实现StatusLocateElem(LinkListL,ElemTypee,Position&q,int(*compare)(ElemType,ElemType));//假设有序链表L中存在与e满足判定函数compare()取值为0的元素,//那么q指示L中第一个这样的结点的位置,并返回TRUE;//否那么q指示第一个与e满足判定函数//compare()取值>0的元素的前驱的位置,并返回FALSEStatusOrderInsert(LinkList&L,ElemTypee,int(*compare)(ElemType,ElemType));//按有序判定函数compare()的约定,//将值为e的结点插入到有序链表L的适当位置例2-4抽象数据类型Polynomial的实现.typedefstruct{//项的表示,多项式的项作为LinkList的数据元素

floatcoef;

//系数COEFFICIENT

intexpn;

//指数EXPONENT}term,ElemType;

//两个类型名:term用于本ADT,ElemType为LinkList的数据对象名typedefLinkListpolynomial;

//用带表头结点的有序链表表示多项式//–––––根本操作的函数原型说明–––––//voidCreatePolyn(polynomial&P,intm);//输入m项的系数和指数,建立表示一元多项式的有序链表PvoidDestroyPolyn(polynomial&P);//销毁一元多项式PvoidPrintPolyn(polynomialP);//打印输出一元多项式PintPolynLeng