第三课-第二章-线性表-课件

第三课第二章线性表ppt课件线性结构的特点：在数据元素的非空有限集中：①存在唯一一个“第一个”的数据元素②存在唯一一个“最后一个”的数据元素③除第一个外集合中的每个数据元素只有一个元素均只有一个前驱④除最后一个外集合中的每个数据元素只有一个元素均只有一个后继。

2023/7/292唐山师范学院数学与信息科学系数据结构线性表的长度：线性表中数据元素的个数n(n≥0)，称为线性表的长度。n=0时线性表为空表。在非空线性表中，每个数据元素都有确定的位置，a1是第一个数据元素；an是第n个数据元素，ai是第i个数据元素，i称为数据元素ai在线性表中的位序。2023/7/295唐山师范学院数学与信息科学系数据结构抽象类型线性表的定义：ADTList{

数据对象：D={ai|ai∈Elemset,(i=1,2,…,n),n≥0}

数据关系：R1={<ai-1,ai>|ai-1,ai∈D,(i=2,…，n)}

基本操作：initlist(&L);destroy(&L);clearlist(&L),listlength(L),listEmpty(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())……

}ADTlist2023/7/296唐山师范学院数学与信息科学系数据结构1、initlist(&L)操作结果：构造一个空的线性表2、destorylist(&L)初始条件：线性表已经存在，操作结果：销毁线性表L3、clearlist(&L)初始条件：线性表已经存在，操作结果：将L重置为空4、listEmpty(L)初始条件：线性表已经存在，操作结果：若L为空表，则返回TRUE，否则返回FALSE.5、listlength(L)初始条件：线性表已经存在，操作结果：返回L中数据元素的个数2023/7/297唐山师范学院数学与信息科学系数据结构6、getelem(L,i,&e)初始条件：线性表已经存在，1≤i≤listlength(L)操作结果：用e返回L中第i个元素的值7、locateElem(L,e,compare())初始条件：线性表已经存在，compare()是数据元素判定函数操作结果：返回L中第1与e满足关系compare()的数据元素的序位。若这样的数据元素不存在，则返回值这为08、priorElem(L,cur_e,&pre_e)初始条件：线性表已经存在操作结果：若cur_e是L的数据元素，且不是第一个，则用pre_e返回它的前驱元素。否则操作失败，pre_e无意义。9、nextElem(L,cur_e,&next_e)初始条件：线性表已经存在操作结果：若cur_e是L的数据元素，且不是最后一个，则用next_e返回它的后继元素。否则操作失败，next_e无意义。2023/7/298唐山师范学院数学与信息科学系数据结构10、listinsert(&L,i,e)初始条件：线性表已经存在,1≤i≤listlength(L)+1操作结果：在L中第i个元素插入新的数据元素e,L的长度加1。11、listDelete(&L,i,&e)初始条件：线性表已经存在,1≤i≤listlength(L)操作结果：删除L中第i个元前，并用e返回其值,L的长度减1。12、listtraverse(L,visit())初始条件：线性表已经存在,操作结果：依次对L中的每个元素调用visit(),一旦visit()失败,则操作失败2023/7/299唐山师范学院数学与信息科学系数据结构举例：线性表的合并例2-1线性表La,Lb的合并La=La∪LbVoidUnion(list&La,listLb){//将所有在Lb中但不在L

a中的元素元素插入到La中La_len=listlength(La);Lb_len=listlength(Lb);For(i=1;i<=Lb_len,i++){Getlist(Lb,i,e);If(!locatelist(La,eequal))listinsert(&La,++La_len,e);}}

算法的时间复杂度O（Lb_lenXLa_len）

2023/7/2910唐山师范学院数学与信息科学系数据结构例2-2将两个按值非递减有序排列的线性表LA和LB合并为一个仍按值非递减有序排列的新线性表LC。(P21算法2.2)

LA=(3,5,8,11)LB=(2,6,8,9,11,15,20)LC=(2,3,5,6,8,8,9,11,11,15,20)2023/7/2911唐山师范学院数学与信息科学系数据结构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); 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++,bi);ListInsert(Lc,++k,bj);}}//MergeList算法的时间复杂度O（La_len+Lb_len）2023/7/2912唐山师范学院数学与信息科学系数据结构2.2线性表的顺序表示

1.顺序表：

用一组地址连续的存储单元依次存储线性的数据元素。线性表的每个元素占用l个存储单元，并以所占的第一个单元的存储地址作为数据元素的存储位置。则线性表中的第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：LOC(ai+1)=LOC(ai)+l

线性表中第i个数据元素ai的存储位置为：

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

2023/7/2913唐山师范学院数学与信息科学系数据结构线性表的顺序表示（图示）存储地址内存状态位序ba11b+la22………………b+(i-1)laii………………b+(n-1)lann2023/7/2914唐山师范学院数学与信息科学系数据结构顺序表的特点：1）以元素在计算机内“物理位置相邻”来表示线性表中数据元素之间的逻辑关系；2）只要确定了存储线性表中的起始位置，线性表中的任何一个数据元素都可以随即存取。因此线性表中的顺序存储结构是一种随机存取的存储结构。2023/7/2915唐山师范学院数学与信息科学系数据结构2、

通常用数组来描述数据结构中的顺序存储结构。

//――――线性表的动态分配顺序存储结构―――――

#define LIST_INIT_SIZE100//线性表存储空间初始分配量

#define LISTINCREMENT10//线性表存储空间的分配增量typedefstruct{ElemType *elem;//存储空间基址intlength;//当前长度intlistsize//当前分配的存储容量}Sqlist

2023/7/2916唐山师范学院数学与信息科学系数据结构1）

构造一个空的线性表（P23算法2.3） 线性表的初始化操作就是为顺序表分配一个预定义大小的数组空间，并将线性表的当前长度设为“0”，listsize指示顺序表当前分配的存储空间大小，一旦因插入元素而空间不足时，可再为顺序表增加一大小为LISTINCREMENT个数据元素的空间。StatusInitList_sq(SqList&L){

//构造一个空的线性表LL.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(Elemtype)); if(!L.elem)exit(OVERFLOW);

//存储分配失败

L.length=0; //空表长度为0

L.listsize=LIST_INIT_SIZE; //初始存储容量

return ok;}//InitList_Sq2023/7/2917唐山师范学院数学与信息科学系数据结构2）StatusDestoryList(sqlist&L)

//销毁线性表L{free(L.elem);L.length=0;L.listsize=0;returnOK;}3)StatusClearList(sqlist&L)

//清空线性表L{L.length=0;returnOK;}2023/7/2918唐山师范学院数学与信息科学系数据结构（4）StatusListEmpty(sqlistL)//判断线性表L是否为空{if(L.length==0)returnTRUE;elsereturnERROR;}（5）intListLength(sqlistL)

//返回线性表L的长度{returnL.length;}(6)StatusGetElem(sqlistL,inti,elemtype&e)//用e返回线性表L中第i个数据元素的值{if(I<1||i>L.length)returnerror;elsee=L.elem[i-1];returnOK;}2023/7/2919唐山师范学院数学与信息科学系数据结构(7)intLocateElem_Sq(SqlistL,ElemTypee,Status(*compare)(ElemType,ElemTYpe)){ //在线性顺序表L中查找第1个值与e满足compare()的元素的位序 //若找到，则返回其在L中的位序，否则返回0i=1; //i的初值为第一个元素的位序

p=L.elem //p的初值为第一个元素的存储位置while(i<=L.length&&!(*compare)(*p++,e))++i;if(i<L.length)returni;elsereturn0;}//LocateElem_Sq2023/7/2920唐山师范学院数学与信息科学系数据结构(8)StatusPriorElem(sqlistL,ElemTypecur_e,ElemType&pre_e)

//用pre_e返回线性表L中cur_e的前驱{inti=2;ElemType*p=L.elem+1while(i<=l.length&&*p!=cur_e){i++;p++}if(i>L.length)returnINFEASIBLE;elsepre_e=*--p;returnOK;}2023/7/2921唐山师范学院数学与信息科学系数据结构(9)StatusNextElem(sqlistL,ElemTypecur_e,ElemType&Next_e)

//用next_e返回线性表L中cur_e的后继元素{inti=1;ElemType*p=L.elemwhile(i<l.length&&*p!=cur_e){i++;p++}if(i>=L.length)returnINFEASIBLE;elseNext_e=*++p;returnOK;}2023/7/2922唐山师范学院数学与信息科学系数据结构(10)顺序表的插入操作（P24算法2.4）在第i(1≤i≤n)个元素之前插入一个元素时，需将第n至第i（共n-i+1）元素向后移动一个位置。StatusListInsert_sq(SqList&L,inti,ElemTypee){//在顺序线性表Ｌ中第i个位置之间插入新的元素e,//i的合法值为1≤i≤ListLength_Sq(L)+1if(i<1||i>L.Length+1)returnERROR;//i值不合法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; //增加存储容量 }q=&(L.elem[i-1]) //q为插入位置for(p=&(L.elem[L.length-1]);p>=q;--p)*(p+1)=*p;//插入位置及之后的元素右移*q=e; //插入e++L.length; //表长增加1returnOK;}//ListInsert_Sq2023/7/2923唐山师范学院数学与信息科学系数据结构(11)顺序表的删除操作（P24算法2.5）删除第i(1≤i≤n)个元素，需将第i+1至第n（共n-i）元素向前移动一个位置。StatusListDelete_sq(SqList&L,inti,ElemType&e){//在顺序线性表Ｌ中删除第i个元素并用e返回其值//i的合法值为1≤i≤ListLength_Sq(L)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_Sq

2023/7/2924唐山师范学院数学与信息科学系数据结构插入一个元素的平均时间复杂度：O(n)N个长度的线性表，在第i个元素之前插入元素，需要移动（n-i+1）个

删除一个元素的平均时间复杂度：O(n)

N个长度的线性表，删除第i个元素，需要移动（n-i）个2023/7/2925唐山师范学院数学与信息科学系数据结构有序顺序表的合并voidMergeList_Sq(SqlistLa,SqlistLb,Sqlist&Lc){pa=La.elem;pb=Lb.elem;Lc.length=Lc.listsize=La.length+Lb.length;pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemType))if(!Lc.elem)exit(OVERFLOW);pa_last=La.elem+La.llength-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++;while(pb<=Pb_last)*pc++=*pb++;}2023/7/2926唐山师范学院数学与信息科学系数据结构练习题：1.设顺序表a中的数据元素递增有序。试写一算法，将X插入到顺序表中适当的位置上，以保持该表有序。2.试写一算法，实现顺序表的就地逆置，即利用原表的存储空间将线性表（a1,a2,a3,……,an)逆置为（an,an-1,……,a1).3.试写一算法，实现从顺序存储结构的线性表L中删除第i个元素起k个元素。DeLeteK(SqList&L,inti,intk)2023/7/2927唐山师范学院数学与信息科学系数据结构习题答案:1.statusinsertorderList(sqlist&L,Elemtypex){if(L.length==L.listsize)return(OVERFLOW);else{I=L.length-1;while(I>=0&&x<L.elem[I])I--;for(j=L.length-1;j>=I+1;j--)L.elem[j+1]=L.elem[j];L.elem[I]=x;L.length++;returnOK;}}2023/7/2928唐山师范学院数学与信息科学系数据结构2.statusreverse(sqlist&L){for(i=0;i<L.lengh/2;i++)L.elem[I]<->L.elem[L.length-1-i];returnOK;}statusreverse(sqlist&L){for(i=0,j=L.length-;i<j;i++,j--)L.elem[i]<->L.elem[j];returnOK;}statusreverse(sqlist&L){for(p=L.elem,q=L.elem+L.length-1;p<q;p++,q--)*p<->*q;returnOK;}2023/7/2929唐山师范学院数学与信息科学系数据结构3.StatusDeleteK(sqlist&L,inti,intk){if(i<1||k<0||i+k>L.length)returnINFEASIBLE;Else{for(count=1;count<k;count++){for(j=a.length;j>=I+1;j--)L.elem[j-1]=L.elem[j];L.length--;}}2023/7/2930唐山师范学院数学与信息科学系数据结构StatusDeleteK(sqlist&L,inti,intk){if(i>0&&i<L.length-1)&&(k>=0&&k<=L.length-i)returnINFEASIBLE;Else{p=&L.elem[i-1];q=&L.elem[i-1+k];{for(;q<=&L.elem[L.length-1];q++,p++)*p=*q;L.length=L.length-k;}}2023/7/2931唐山师范学院数学与信息科学系数据结构2.3线性表的链式表示教学目标：掌握线性表的链式表示及实现方法（链表的插入、删除），重点是是插入和删除算法。教学内容：2.3线性表的链式表示一、线性链表顺序表示的优点：是随机存取表中的任意元素顺序表示的弱点：在插入和删除时需要移动大量的元素链式存取没有顺序表示的弱点，但也失去了顺序表示的优点

2023/7/2932唐山师范学院数学与信息科学系数据结构链式表示可以用任意的一组单元存储线性表中的数据元素例如：线性表（zhao,qian,sun,li,zhou,wu,zheng,wang）头指针H31

存储地址数据域指针域1li437qian1313sun119wangNULL25wu3731zhao737zheng1943zhou25整个链表的存取必须从头指针开始链表逻辑状态zhaoqiansunlizhouwuzhengwangNULL2023/7/2933唐山师范学院数学与信息科学系数据结构链表的相关名称：结点：为了表示每个数据元素ai与其直接后继数据元素ai+1之间的逻辑关系，对数据元素ai来说，除了存储其本身的信息外，还需要存储一个指示其直接后继的信息，这两部分组成数据元素ai的存储映像，称为结点。数据域：存储数据元素的域称为数据域指针域：存储其后继存储位置的域称为指针域指针或链：指针域存储的信息称做指针或链链表：n个结点链成一个链表，即为线性表的链式存储结构单链表：链表中的每个结点只有一个指针域，称为单链表头指针：指示链表中第一个结点的存储位置。头结点:有时候,我们在单链表的第一个结点之前附设一个结点,称之为头结点2023/7/2934唐山师范学院数学与信息科学系数据结构//――――线性表的单链表存储结构―――――

typedefstructLnode{ElemType data; structLnode *next;}Lnode,*LinkList;2023/7/2935唐山师范学院数学与信息科学系数据结构1)初始化

statusInitList(LinkList&L)

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

if(!L)return(OVERFLOW);

L->next=NULL;

returnOK;

}2)销毁链表statusDestoryList(Linklist&L){LinkListq;while(L){q=L->next;free(L);L=q;}returnOK;}2023/7/2936唐山师范学院数学与信息科学系数据结构(3)CLearList(LinkList&L)

{LinkListp,q;

p=L->next;

while(p)

{q=p->next;

free(p);

p=q;}

L->next=NULL;

returnOK;}(4)statusListEmpty(LinklistL){if(l->next)returnFALSE;elsereturnTRUE;}2023/7/2937唐山师范学院数学与信息科学系数据结构(5)intListLength(LinkListL)

{inti=0;

LinkListp;

p=L->next;

while(p){i++,p=p->next;}

returni

}2023/7/2938唐山师范学院数学与信息科学系数据结构(6)返回线性表第i个数据元素的值（(P29算法2.8)）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_L2023/7/2939唐山师范学院数学与信息科学系数据结构(7)intLocateElem(LinklistL,ElemTypeestatus(*compare)(ElemType,ElemType)){inti=0;LinkListp=L->next;while(p){i++;if(compare(p->data,e)retruni;p=p->next;}retrun0;}2023/7/2940唐山师范学院数学与信息科学系数据结构(8)statusPriorElem(LinkListL,ElemTypecur_e,ElemType&pre_e){LinkListq,p;p=L->next;while(p->next){q=p->next;if(q->data==cur_e){pre_e=p->data;returnOK;}p=q;}retrunINFEASIBLE;}2023/7/2941唐山师范学院数学与信息科学系数据结构(9)statusNextElem(LinkListL,ElemTypecur_e,ElemType&Next_e){LinkListq,p;p=L->next;while(p->next){if(p->data==cur_e){Next_e=p->next->data;returnOK;}p=p->next;}retrunINFEASIBLE;}2023/7/2942唐山师范学院数学与信息科学系数据结构(10)

线性表第i个位置之前插入元素e（(P30算法2.9)）

StatusListInsert_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或大于表长+1s=(LinkList)malloc(sizeof(Lnode)); //生成新结点s->data=e;s->next=p->next; //插入L中p->next=s;returnok;}//ListInsert_L

2023/7/2943唐山师范学院数学与信息科学系数据结构(11)在带头结点的线性表L中删除第i个元素（(P30算法2.10)）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_L

2023/7/2944唐山师范学院数学与信息科学系数据结构(12)StatusListTraverse(LinkListL,void(*vi)(ElemType)){Linklistp;p=L->next;while(p){vi(p->data);p=p->next;}returnOK;}2023/7/2945唐山师范学院数学与信息科学系数据结构归并两个有序单链表的算法如下voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){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;}else(pc->next=pb;pc=pb;pb=pb->next;)}pc->next=pa?pa:pb;free(Lb);}2023/7/2946唐山师范学院数学与信息科学系数据结构

练习：1.已知L是无表头结点的单链表，且P不是首结点，也不是尾结点，从下列提供的答案中选择合适的语句序列。a.在p结点后插入S结点的语句序列是：b.在p结点前插入S结点的语句序列是：c.在表首插入S结点的语句序列是：d.在表尾插入S结点的语句序列是：(1)p->next=s;(2)p->next=p->next->next;(3)p->next=s->next;(4)s->next=p->next;(5)s->next=L;(6)s->next=NULL;(7)q=p;(8)while(p->next!=q)p=p->next;(9)while(p->next=NULL)p=p->next;(10)p=q;(11)p=L(12)L=s;(13)L=p2023/7/2947唐山师范学院数学与信息科学系数据结构2.已知L是带头结点的非空单链表,且P结点既不是首元结点,也不是尾元结点,试从下列提供的答案中选择合适的语句序列a.删除P结点的直接后继结点的语句序列是:

b.删除P结点的直接前驱结点的语句序列是:c.删除P结点的语句序列是:d.删除首元结点的语句序列是:e.删除尾元结点的语句序列是:(1)p=p->next;(2)p->next=p;(3)p->next=p->next->next;(4)p=p->next->next;(5)while(p!=NULL)p=p->next;(6)while(q->next!=NULL){p=q,q=q->next;}(7)while(p->next!=q)p=p->next;(8)while(p->next->next!=q)p=p->next;(9)while(p->next->next!=NULL)p=p->next;(10)q=p;(11)q=p->next;(12)p=L;(13)L=L->next;(14)free(q);

2023/7/2948唐山师范学院数学与信息科学系数据结构3.试写一算法，对单链表（有头结点）就地逆置4.试写一算法，在无头结点的动态单链表上实现线性表的insert(L,i.b)。5.已知线性表中的元素是非递减的有序表，并以单链表作为存储结构。试写一高效算法，删除表中所有值相同的多余元素，同时释放被删除的结点空间。2023/7/2949唐山师范学院数学与信息科学系数据结构

statusDelete_Equal(Listlist&L){p=L->next;q=p->next;while(p->next){if(p->data!=q->data){p=p->next;q=p->next;}else{while(q->data==p->data){s=q->next;free(q);q=s;}p->next=q;p=q;q=p->next;}}}2023/7/2950唐山师范学院数学与信息科学系数据结构1.a.(4),(1)b.(7),(11),(8),(4),(1)c.(5),(12)d.(11),(9),(1),(6)2.a.(11),(3),(4)b.(10),(12),(8),(11),(3),(14)c.(10),(12),(7),(3),(14)d.(12),(11),(3),(14)e.(12),(9),(11),(3),(14)3.Statusreverse(linklist&L){p=L->next;L->next=NULL;While(p){q=p->next;p->next=L->next;L->next=p;p=q;}returnOK;}2023/7/2951唐山师范学院数学与信息科学系数据结构4.Statusinsert(linklist&L,inti,elemtypee){p=L;s=(linklist)malloc(sizeof(lnode));s->data=e;if(i==1){s->next=L;L=s;}else{while(--i>1)p=p->next;s->next=p;p->next=s;}returnOK;}2023/7/2952唐山师范学院数学与信息科学系数据结构静态链表#DefineMAXSIZE1000Typedefstruct{ElemTypedata;intcur;}component,SlinkList[MAXSUZE];011zhao22qian33Sun44Li55Zhou66Wu77Zheng88wang0910011zhao22qian33Sun44Li95Zhou66Wu87Zheng88wang09shi5102023/7/2953唐山师范学院数学与信息科学系数据结构在静态链表中实现定位函数LlocateElemIntLocateElem_SL(SLinkLists,ElemTypee){i=S[0].cur;While(I&&s[i].data!=e)I=s[i].cur;Returni;}2023/7/2954唐山师范学院数学与信息科学系数据结构将整个数组空间初始化成一个链表VoidinitSpace_SL(Slinklist&space){for(i=0;i<MAXSIZE-1;++i)space[i].cur=i+1;Space[MAXSIZE-1].cur=0;}从备用空间取得一个结点Voidmalloc_SL(Slinklist&space){I=space[0].cur;If(space[0].cur)space[0].cur=space[I].cur;Returni}将空闲结点链接到备用表中Voidfree_SL(Slinklist&space,intk){space[k].cur=space[o].cur;space[0].cur=k;}2023/7/2955唐山师范学院数学与信息科学系数据结构voiddifference(SLinkListspace,int*S)/*算法2.17*/{/*依次输入集合A和B的元素，在一维数组space中建立表示集合(A-B)∪(B-A)*//*的静态链表，S为其头指针。假设备用空间足够大，space[0].cur为备用空间的头指针*/

intr,p,m,n,i,j,k;ElemTypeb;InitSpace(space);/*初始化备用空间*/*S=Malloc(space);/*生成S的头结点*/

r=*S;/*r指向S的当前最后结点*/

printf("请输入集合A和B的元素个数m,n:");scanf("%d,%d%*c",&m,&n);/*%*c吃掉回车符*/

printf("请输入集合A的元素（共%d个）:",m);for(j=1;j<=m;j++)/*建立集合A的链表*/{

i=Malloc(space);/*分配结点*/

scanf("%c",&space[i].data);/*输入A的元素值*/

space[r].cur=i;/*插入到表尾*/

r=i;}scanf("%*c");/*%*c吃掉回车符*/

space[r].cur=0;/*尾结点的指针为空*/

printf("请输入集合B的元素（共%d个）:",n);2023/7/2956唐山师范学院数学与信息科学系数据结构

for(j=1;j<=n;j++){/*依次输入B的元素,若不在当前表中,则插入,否则删除*/

scanf("%c",&b);p=*S;k=space[*S].cur;/*k指向集合A中的第一个结点*/

while(k!=space[r].cur&&space[k].data!=b){/*在当前表中查找*/

p=k;k=space[k].cur;}if(k==space[r].cur){/*当前表中不存在该元素，插入在r所指结点之后，且r的位置不变*/

i=Malloc(space);space[i].data=b;space[i].cur=space[r].cur;space[r].cur=i;}else/*该元素已在表中，删除之*/{

space[p].cur=space[k].cur;Free(space,k);if(r==k)r=p;/*若删除的是尾元素，则需修改尾指针*/}}}2023/7/2957唐山师范学院数学与信息科学系数据结构二、循环链表和双向链表1、循环链表的定义：另一种形式的链式存储结构，特点是最后一个结点的指针域指向头结点，整个链表形成一个环，从表中任一结点出发均可找到表中其它结点。循环条件是它们是否指向头指针。

HH链表为空的条件:H->next=H;2023/7/2958唐山师范学院数学与信息科学系数据结构2、双向链表的定义：在双向链表的结点域中有两个指针域，其一是指向其直接后继，另一是指向其直接前趋。//――――线性表的双向链表存储结构―――――

typedefstructDuLNode{ElemType data; structDuLnode *prior; structDuLnode *next;}DuLnode,*DuLinkList;priordatanextABCL2023/7/2959唐山师范学院数学与信息科学系数据结构在带头结点的双链循环线性表L中第i个位置之前插入元素e（(P36算法2.18)）

StatusListInsert_DuL(DuLinkList&L,inti,Elemtypee){//在带头结点的双链循环线性表L第i个位置之前插入元素e//i的合法值为1≤i≤表长+1if(!(p=GetElemP_Dul(L,i)))//在L中确定第i个元素的位置指针p return ERROR; //p=NULL，第i个元素不存在if(!(s=(DuLinkList)malloc(sizeof(DuLnode)))); //生成新结点s->data=e;s->prior=p->prior; p->prior->next=s;s->next=p; p->prior=s;returnok;}//ListInsert_DuL

2023/7/2960唐山师范学院数学与信息科学系数据结构在带头结点的双链循环线性表L中删除第i个元素(P37算法2.19)

StatusListDelete_DuL(DuLinkList&L,inti,Elemtype&e){//删除带头结点的双链循环线性表L第i个元素，i的合法值为1≤i≤表长//i的合法值为1≤i≤表长+1if(!(p=GetElemP_Dul(L,i))) //在L中确定第i个元素的位置指针p return ERROR; //p=NULL，第i个元素不存在e=p->data;p->prior->next=p->next;p->next->prior=p->prior;free(p);returnok;}//ListDelete_DuL

2023/7/2961唐山师范学院数学与信息科学系数据结构2.4一元多项式的表示及相加一个一元多项式Pn(x)=p0+p1x+p2x2+p3x3+……+pnxnP=(p0,p1,p2……pn)qm(x)=q0+q1x+q2x2+q3x3+……+pmxmq=(q0,q1,q2……qm)设m<nRn(x)=pn(x)+qm(x)R=(p0+q0,p1+q1,p2+q2,……,pm+qm,pm+1,…..,pn)S(x)=1+3x10000+2x200002023/7/2962唐山师范学院数学与信息科学系数据结构采用链表存储表示如：A17(x)=7+3x+9x8+5x17B8(x)=8x+22x7-9x8-1703198517A-181227-98B2023/7/2963唐山师范学院数学与信息科学系数据结构

voidCreatPolyn(polynomial&P,intm)/*算法2.22*/{/*输入m项的系数和指数，建立表示一元多项式的有序链表P*/Positionq,s;terme;inti;InitList(P);printf("请依次输入%d个系数，指数：\n",m);for(i=1;i<=m;++i){/*依次输入m个非零项（可按任意顺序）*/

scanf("%f,%d",&e.coef,&e.expn);if(!LocateElemP(P,e,q,cmp))/*当前链表中不存在该指数项,cmp是实参*/

if(MakeNode(s,e))/*生成结点并插入链表*/

InsFirst(P,q,s);}}2023/7/2964唐山师范学院数学与信息科学系数据结构

voidPrintPolyn(polynomialP){/*打印输出一元多项式P*/Linkq;q=P.head->next;/*q指向第一个结点*/

printf("系数指数\n");while(q){printf("%f%d\n",q->data.coef,q->data.expn);q=q->next;}}2023/7/2965唐山师范学院数学与信息科学系数据结构voidAddPolyn(polynomial*Pa,polynomial*Pb)/*算法2.23*/{/*多项式加法:Pa=Pa+Pb,并销毁一元多项式Pb*/Positionha,hb,qa,qb;terma,b;ha=GetHead(*Pa);hb=GetHead(*Pb);/*ha和hb分别指向Pa和Pb的头结点*/

qa=NextPos(ha);qb=NextPos(hb);/*qa和qb分别指向Pa和Pb中当前结点（现为第一个结点）*/

while(!ListEmpty(*Pa)&&!ListEmpty(*Pb)&&qa){/*Pa和Pb均非空且ha没指向尾结点(qa!=0)*/a=GetCurElem(qa);b=GetCurElem(qb);/*a和b为两表中当前比较元素*/

switch(cmp(a,b)){case-1:ha=qa;/*多项式Pa中当前结点的指数值小*/

qa=NextPos(ha);/*ha和qa均向后移一个结点*/

break;

2023/7/2966唐山师范学院数学与信息科学系数据结构case0:qa->data.coef+=qb->data.coef;/*两者的指数值相等,修改Pa