数据结构线性表及其基本算法学习教案.pptx

《数据结构线性表及其基本算法学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构线性表及其基本算法学习教案.pptx（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)线性表及其基本算线性表及其基本算法法第一页，共49页。n n教学教学(jio xu)(jio xu)目标目标n n线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。造出较复杂的运算。n n掌握顺序表的含义及特点，顺序表上的插入、删除操作是及其平均时间掌握顺序表的含义及特点，顺序表上的插入、删除操作是及其平均时间性能分析，解决简单应用问题。性能分析，解决简单应用问题。n n掌握链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循掌握链表如何表示线性表中元

2、素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。关算法。利用链表设计算法解决简单应用问题。n n领会顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得领会顺序表和链表的比较，以及如何选择其一

3、作为其存储结构才能取得较优的时空性能。较优的时空性能。第1页/共50页第二页，共49页。n n教学重点与难点n n本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析；n n难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用(yngyng)问题。n n教学方法n n课堂讲授n n提问互动n n实验第2页/共50页第三页，共49页。n n定义:n n线性表（linear list）n n （a1，a2，an）n n 其中:n nn：数据元素的个数或线性表的长度；n nai：是一个抽象的符号(fho)，它的数据类型设定为ElemType，表示某一种具体的已知数据类型（

4、1in）。2.1 线性表的类型定义线性表的类型定义第3页/共50页第四页，共49页。n n非空线性表的特征(tzhng)（P18）n n 有且仅有一个开始结点(表头结点 head)a1，它没有直接前驱，只有一个直接后继;n n 有且仅有一个终端结点(表尾结点tail)an，它没有直接后继，只有一个直接前驱;n n 其它结点都有一个直接前驱和直接后继；n n 元素之间为一对一的线性关系。第4页/共50页第五页，共49页。线性表的抽象数据类型定义线性表的抽象数据类型定义(dngy)（P18）ADT ListADT List 数据对象数据对象(duxing)(duxing)：D=ai|aiD=ai|

5、aiElemSet;1in,n0;ElemSet;1in,n0;数据关系：数据关系：R=|R=|ai,ai+1ai,ai+1D,i=1,2,n-1D,i=1,2,n-1 基本操作：基本操作：InitList(&L)InitList(&L)ListLength(L)ListLength(L)GetElem(L,i,&e)GetElem(L,i,&e)PriorElem(L,cur_e,&pre_e)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)NextElem(L,cur_e,&next_e)LocateElem(L,e,compare()L

6、ocateElem(L,e,compare()ListInsert(&L,i,e)ListInsert(&L,i,e)ListDelete(&L,i,&e)ListDelete(&L,i,&e)ADT ListADT List第5页/共50页第六页，共49页。算法算法(sun f)2.1（线性表的首尾（线性表的首尾合并）合并）void union(List&La,List Lb)void union(List&La,List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);La_len=ListLength(La);Lb_len=ListLengt

7、h(Lb);for(i=1;i=Lb_len;i+)for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);GetElem(Lb,i,e);if (!LocateElem(La,e,equal)if (!LocateElem(La,e,equal)ListInsert(La,+La_len,e);ListInsert(La,+La_len,e);/union /union 算法分析：算法分析：设设LocateElemLocateElem的执行的执行(zhxng)(zhxng)时间与表长成正比，时间与表长成正比，即：算法的时间复杂度为：即：算法的时间复杂度为：O(ListLeng

8、th(La)*ListLength(Lb)O(ListLength(La)*ListLength(Lb)第6页/共50页第七页，共49页。算法算法(sun f)2.2（有（有序线性表的合并）序线性表的合并）void MergeList(List La,List Lb,List&Lc)void MergeList(List La,List Lb,List&Lc)InitList(Lc);i=j=1;k=0;InitList(Lc);i=j=1;k=0;La_Len=ListLength(La);Lb_Len=ListLength(Lb);La_Len=ListLength(La);Lb_Len=

9、ListLength(Lb);while(i=La_Len)&(j=Lb_Len)while(i=La_Len)&(j=Lb_Len)GetElem(La,i,ai);GetElem(La,i,ai);GetElem(Lb,j,bj);GetElem(Lb,j,bj);if(ai=bj)ListInsert(Lc,+k,ai);+i;if(ai=bj)ListInsert(Lc,+k,ai);+i;else ListInsert(Lc,+k,bj);+j;else ListInsert(Lc,+k,bj);+j;while(i=La_len)while(i=La_len)GetElem(La,

10、i+;ai);ListInsert(Lc,+k,ai);GetElem(La,i+;ai);ListInsert(Lc,+k,ai);while(j=Lb_len)while(j=Lb_len)GetElem(Lb,j+;bj);ListInsert(Lc,+k,bj);GetElem(Lb,j+;bj);ListInsert(Lc,+k,bj);/MergeList/MergeList第7页/共50页第八页，共49页。2.2 线性表的顺序存储结构线性表的顺序存储结构(jigu)n n一、特点n n用一组地址连续的存储单元依次存放线性表中的元素；n n以元素在机内的“物理位置相邻”来表示数据之

11、间的逻辑关系:n n LOC(ai+1)LOC(ai)Ln n是一种随机存取的存储结构(jigu);n n LOC(ai)LOC(a1)(i1)*Ln n插入删除时需移动大量元素;a1a2aiai+1anLOC(a a11)LOC(a aii)LOC(a ai+1i+1)第8页/共50页第九页，共49页。2.2 线性表的顺序存储结构线性表的顺序存储结构(jigu)n n二、描述(mio sh)方式n n#define LIST_INIT_SIZE 100n n#define LISTINCREMENT 10n ntypedef structn nElemType*elem;n n int le

12、ngth;n n int listsize;n n SqList第9页/共50页第十页，共49页。2.2 线性表的顺序存储结构线性表的顺序存储结构(jigu)n n三、基本操作的算法描述 n n初始化顺序(shnx)表 （算法 2.3）n n插入元素 （算法 2.4）n n 删除元素 （算法 2.5）n n 元素的查找（算法 2.6）n n 顺序(shnx)表的合并 （算法 2.7）第10页/共50页第十一页，共49页。n n算法(sun f)2.3（初始化顺序表）n nStatus InitList_Sq(SqList&L)n nL.elem=(ElemType*)malloc(LIST_I

13、NIT_SIZE*sizeof(ElemType)n nif(!L.elem)exit（OVERFLOW）;n nL.length=0;n nL.listsize=LIST_INIT_SIZE;n nreturn OK;n n/InitList_Sq第11页/共50页第十二页，共49页。算法算法算法算法(sun f(sun f)2.4)2.4：顺序表中插入一个元素：顺序表中插入一个元素：顺序表中插入一个元素：顺序表中插入一个元素Status ListInsert_Sq(SqList&L,int i,ElemType e)Status ListInsert_Sq(SqList&L,int i,E

14、lemType e)if(iL.length+1)return ERROR;if(iL.length+1)return ERROR;if(L.length=L.listsize)if(L.length=L.listsize)newbase=(ElemType*)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);if(!n

15、ewbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMET;L.elem=newbase;L.listsize+=LISTINCREMET;q=&(L.elemi-1);q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;*q=e;+L.length;+L.length;return OK;return OK;/ListInsert_Sq /ListInsert_Sq fo

16、r(j=L.length-1;j=i-1;j-)L.elemj+1=L.elemj第12页/共50页第十三页，共49页。a1a2aiai+1anL.elem01i-1i下标下标a1a2aian-1ane第13页/共50页第十四页，共49页。插入插入插入插入(ch r)(ch r)算法的时间复杂度分析算法的时间复杂度分析算法的时间复杂度分析算法的时间复杂度分析n n插入算法花费的时间，主要在于循环中元素插入算法花费的时间，主要在于循环中元素(yun s)(yun s)的向后移动上的向后移动上面，而元素面，而元素(yun s)(yun s)的移动次数与插入的位置的移动次数与插入的位置i i有关：有

17、关：(设设L.length=n)L.length=n)n n当当i=1i=1时，全部元素时，全部元素(yun s)(yun s)都得移动，需都得移动，需n n次移动，次移动，n n当当i=n+1i=n+1时，不需移动元素时，不需移动元素(yun s)(yun s)，n n一般地：在一般地：在i i位置插入时移动次数位置插入时移动次数ci ci为为n-i+1n-i+1，n n假设在每个位置插入的概率为假设在每个位置插入的概率为pi pi（不妨设为等概率）（不妨设为等概率），则平均移，则平均移动元素动元素(yun s)(yun s)的次数为：的次数为：故时间故时间(shjin)复杂度为复杂度为O(

18、n)。第14页/共50页第十五页，共49页。算法算法算法算法(sun f(sun f)2.5 )2.5 顺序表中删除元素顺序表中删除元素顺序表中删除元素顺序表中删除元素Status ListDelete_Sq(Sqlist&L,int i,ElemType&e)Status ListDelete_Sq(Sqlist&L,int i,ElemType&e)if(iL.length)return ERROR;if(iL.length)return ERROR;p=&(L.elemi-1);p=&(L.elemi-1);e=*p;e=*p;q=L.elem+L.length-1;q=L.elem+L

19、.length-1;for(+p;p=q;+p)*(p-1)=*p;for(+p;p=q;+p)*(p-1)=*p;-L.length;-L.length;return OK;return OK;/ListDelete_Sq/ListDelete_Sq e=L.elemi-1;For(j=i;j=L.length-1;j+)L.elemj-1=L.elemj；第15页/共50页第十六页，共49页。删除删除删除删除(shnch)(shnch)算法的时间复杂度分析算法的时间复杂度分析算法的时间复杂度分析算法的时间复杂度分析n n删除算法花费的时间，主要在于循环中元素的前移上，而元素删除算法花费的时

20、间，主要在于循环中元素的前移上，而元素的移动次数与删除的位置的移动次数与删除的位置i i有关：有关：(设设L.length=n)L.length=n)n n当当i=1i=1时，其后的全部元素都得移动，需时，其后的全部元素都得移动，需n-1n-1次移动，次移动，n n当当i=ni=n时，不需移动元素，时，不需移动元素，n n一般地：在一般地：在i i位置删除元素时的移动次数位置删除元素时的移动次数ci ci为为n-in-in n假设假设(ji(ji sh)sh)在每个位置删除的概率为在每个位置删除的概率为pi pi（不妨设为等概率）（不妨设为等概率），则平均移动元素的次数为：，则平均移动元素的次

21、数为：故时间故时间(shjin)复杂度为复杂度为O(n)。第16页/共50页第十七页，共49页。算法算法算法算法2.6 2.6 顺序顺序顺序顺序(shnx)(shnx)表中元素的查找表中元素的查找表中元素的查找表中元素的查找int LocateElem_Sq(Sqlist L,ElemType e,int LocateElem_Sq(Sqlist L,ElemType e,status(*compare)(ElemType,ElemType)status(*compare)(ElemType,ElemType)i=1;i=1;p=L.elem;p=L.elem;while(iL.length&

22、!(*compare)(*p+,e)+i;while(iL.length&!(*compare)(*p+,e)+i;if(i=L.length)return i;if(i=L.length)return i;else return 0;else return 0;/ListDelete_Sq /ListDelete_Sq注注 ：设设L.length=nL.length=n，则则T(n)=O(n)T(n)=O(n)第17页/共50页第十八页，共49页。算法算法算法算法2.6-1 2.6-1 顺序表中元素顺序表中元素顺序表中元素顺序表中元素(yun s)(yun s)的查找的查找的查找的查找int

23、 LocateElem_Sq(Sqlist L,ElemType e)int LocateElem_Sq(Sqlist L,ElemType e)i=0;i=0;while(iL.length&L.elemi!=e)+i;while(iL.length&L.elemi!=e)+i;if(iL.length)return i+1;if(iL.length)return i+1;else return 0;else return 0;/ListDelete_Sq /ListDelete_Sq注注 ：设设L.length=n，则则T(n)=O(n)第18页/共50页第十九页，共49页。算法算法算法算

24、法2.7 2.7 顺序顺序顺序顺序(shnx)(shnx)表的合并表的合并表的合并表的合并Status MergeList_Sq(Sqlist La,Sqlist Lb,Sqlist&Lc)Status MergeList_Sq(Sqlist La,Sqlist Lb,Sqlist&Lc)pa=La.elem;pb=Lb.elem;pa=La.elem;pb=Lb.elem;Lc.ListSize=Lc.length=La.length+Lb.length;Lc.ListSize=Lc.length=La.length+Lb.length;pc=Lc.elem=(ElemType*)pc=Lc

25、.elem=(ElemType*)malloc(Lc.ListSize*sizeof(ElemType);malloc(Lc.ListSize*sizeof(ElemType);if(!pc)return OVERFLOW;if(!pc)return OVERFLOW;pa_last=pa+La.length-1;pa_last=pa+La.length-1;pb_last=pb+Lb.length-1;pb_last=pb+Lb.length-1;while(pa=pa_last)&(pb=pb_last)while(pa=pa_last)&(pb=pb_last)if(*pa=*pb)*p

26、c+=*pa+;if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;else*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;while(pa=pa_last)*pc+=*pa+;while(pb=pb_last)*pc+=*pb+;while(pbnext;p=L-next;j=1;j=1;while(p&ji)while(p&jnext;p=p-next;j+;j+;if(!p|ji)return ERROR;if(!p|ji)return ERROR;e=p-data;e=p-data;return OK;return OK;注意：注意：循环控制

27、条件及异常处理循环控制条件及异常处理算法算法(sun f)的时间复杂的时间复杂度：度：O(n)第26页/共50页第二十七页，共49页。算法算法2.92.9（插入（插入(ch r)(ch r)元素）元素）Status ListInsert_L(LinkList&L,int i,ElemType e)Status ListInsert_L(LinkList&L,int i,ElemType e)p=L;p=L;j=0;j=0;while(p&ji-1)while(p&jnext;p=p-next;j+;j+;if(!p|ji-1)return ERROR;if(!p|ji-1)return ERR

28、OR;s=(LinkList)malloc(sizeof(LNode);s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;s-data=e;s-next=p-next;p-next=s;return OK;return OK;xsbap2.3.1 线性链表（单链表）线性链表（单链表）bap算法算法(sun f)的时间复杂度为的时间复杂度为0(n)。第27页/共50页第二十八页，共49页。2.3.1 线性链表（单链表）线性链表（单链表）算法算法(sun f(sun f)2.10)2.10（删除元素）（删除元素）Sta

29、tus ListDelete_L(LinkList&L,int i,ElemType&e)Status ListDelete_L(LinkList&L,int i,ElemType&e)p=L;p=L;j=0;j=0;while(p-next&jnext&jnext;p=p-next;j+;j+;if(!(p-next)|ji-1)return ERROR;if(!(p-next)|ji-1)return ERROR;q=p-next;p-next=q-next;e=q-data;q=p-next;p-next=q-next;e=q-data;free(q);free(q);return OK

30、;return OK;第28页/共50页第二十九页，共49页。2.3.1 线性链表（单链表）线性链表（单链表）算法算法(sun f(sun f)2.11-1)2.11-1（头插法建立单链表）（头插法建立单链表）void CreateListe_L_1(LinkList&L,int n)void CreateListe_L_1(LinkList&L,int n)L=(LinkList)malloc(sizeof(LNode);L=(LinkList)malloc(sizeof(LNode);L-next=NULL;L-next=NULL;for(i=1;i=n;i+)for(i=1;idata)

31、;scanf(&p-data);p-next=L-next;p-next=L-next;L-next=p;L-next=p;第29页/共50页第三十页，共49页。2.3.1 线性链表（单链表）线性链表（单链表）算法算法(sun f(sun f)2.11-2)2.11-2（尾插法建立单链表）（尾插法建立单链表）void CreateListe_L_2(LinkList&L,int n)void CreateListe_L_2(LinkList&L,int n)L=(LinkList)malloc(sizeof(LNode);L=(LinkList)malloc(sizeof(LNode);L-n

32、ext=NULL;L-next=NULL;q=L;q=L;for(i=1;i=n;i+)for(i=1;idata);scanf(&p-data);q-next=p;q-next=p;q=p;q=p;q-next=NULL;q-next=NULL;第30页/共50页第三十一页，共49页。2.3.1 线性链表（单链表）线性链表（单链表）算法算法(sun f(sun f)2.12)2.12（有序链表的合并）（有序链表的合并）void MergeListe_L(LinkList&La,LinkList&Lb,LinkList void MergeListe_L(LinkList&La,LinkLis

33、t&Lb,LinkList&Lc)&Lc)pa=La-next;pb=Lb-next;pa=La-next;pb=Lb-next;Lc=pc=La;Lc=pc=La;while(pa&pb)while(pa&pb)if(pa-datadata)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;pc-next=pa;pc=pa;pa=pa-next;else else pc-next=pb;pc=pb;pb=pb-next;pc-next=pb;pc=pb;pb=pb-next;/while /while pc-next=pa?pa:pb;pc-next=pa

34、?pa:pb;free(Lb);free(Lb);第31页/共50页第三十二页，共49页。2.3.2 单循环链表单循环链表L an a1a2n 循环链表的操作与单链表的操作类似，差别如下：循环链表的操作与单链表的操作类似，差别如下：n链表的判空条件：链表的判空条件：L-next=Ln最后一个结点最后一个结点(ji din)的判定条件的判定条件:p-next=Ln可以设立尾指针可以设立尾指针单循环链表示意图单循环链表示意图第32页/共50页第三十三页，共49页。2.3.3 双向链表双向链表n n概念概念(ginin)(ginin)引入引入n n结点结构与定义结点结构与定义priordatanex

35、ttypedef struct DuLNode ElemType data;struct DuLNode*prior;struct DuLNode*next;DuLNode,*DuLinkListn双向链表示意图双向链表示意图L a2 a3 a1 an L a2 a3 a1 an第33页/共50页第三十四页，共49页。算法算法算法算法(sun f(sun f)2.18)2.18（双向循环链表中插入元素）（双向循环链表中插入元素）（双向循环链表中插入元素）（双向循环链表中插入元素）Status ListInsett_DuL(DuLinkList&L,int i,ElemType e)Status

36、 ListInsett_DuL(DuLinkList&L,int i,ElemType e)p=L-next;j=1;p=L-next;j=1;while(p!=L&ji)while(p!=L&jnext;p=p-next;j+;j+;if(p=L|ji)return ERROR;if(p=L|ji)return ERROR;if(!(s=(DuLinkList)malloc(sizeof(DuLNode)if(!(s=(DuLinkList)malloc(sizeof(DuLNode)return ERROR;return ERROR;s-data=e;s-data=e;s-prior=p-

37、prior;p-prior-next=s;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;s-next=p;p-prior=s;return OK;return OK;/ListInsert_Dul/ListInsert_Dul第34页/共50页第三十五页，共49页。算法算法算法算法2.192.19（双向循环链表中删除（双向循环链表中删除（双向循环链表中删除（双向循环链表中删除(shnch)(shnch)元素）元素）元素）元素）Status ListDelete_DuL(DuLinkList&L,int i,ElemType e)Status

38、 ListDelete_DuL(DuLinkList&L,int i,ElemType e)p=L-next;j=1;p=L-next;j=1;while(p!=L&ji)while(p!=L&jnext;p=p-next;j+;j+;if(p=L|ji)return ERROR;if(p=L|ji)return ERROR;e=p-data;e=p-data;p-prior-next=p-next;p-prior-next=p-next;p-next-prior=p-prior;p-next-prior=p-prior;free(p);free(p);return OK;return OK;

39、/ListDelete/ListDelete第35页/共50页第三十六页，共49页。具体要求具体要求顺序表顺序表链表链表基于空间基于空间适于线性表长适于线性表长度变化不大，度变化不大，易于事先确定易于事先确定其大小时采用。其大小时采用。适于当线性表长度变化大，难以估计适于当线性表长度变化大，难以估计其存储规模时采用。其存储规模时采用。基于时间基于时间由于顺序表是由于顺序表是一种随机存储一种随机存储结构，当线性结构，当线性表的操作主要表的操作主要是查找时，宜是查找时，宜采用。采用。链表中对任何位置进行插入和删除都链表中对任何位置进行插入和删除都只需修改指针，所以这类操作为主的只需修改指针，所以这

40、类操作为主的线性表宜采用链表做存储结构。若插线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。则宜采用尾指针表示的单循环链表。线性表的两种存储结构线性表的两种存储结构(jigu)的比较的比较第36页/共50页第三十七页，共49页。2.4 线性表的应用线性表的应用(yngyng)举例举例n n高级语言中的数组；高级语言中的数组；n n计算机的文件系统；计算机的文件系统；n n计算机的目录系统；计算机的目录系统；n n电话号码查询电话号码查询(chxn)(chxn)系统（可采用顺序表或单链表结构）；系统（可采用顺序表或单

41、链表结构）；n n各种事务处理（各种表格均采用顺序表和线性链表结构）各种事务处理（各种表格均采用顺序表和线性链表结构）n n一元多项式的表示和相加一元多项式的表示和相加第37页/共50页第三十八页，共49页。例：一元例：一元例：一元例：一元(y yun)(y yun)多项式的表示和相加多项式的表示和相加多项式的表示和相加多项式的表示和相加n n情况情况(qngkung)(qngkung)一：一：n nPn(x)=p0+p1x+p2x2+pnxnPn(x)=p0+p1x+p2x2+pnxnn nQn(x)=q0+q1x+q2x2+qnxmQn(x)=q0+q1x+q2x2+qnxmn nRn(x

42、)=(p0+q0)+(p1+q1)x+(p2+q2)x2+Rn(x)=(p0+q0)+(p1+q1)x+(p2+q2)x2+(pn+qn)xn+qn+1xn+1+qmxm+(pn+qn)xn+qn+1xn+1+qmxmn n可以表示为：可以表示为：n nP=P=（p0p0，p1p1，p2p2，pnpn）n nQ=Q=（q0q0，q1q1，q2q2，qmqm）n nR=(p0+q0R=(p0+q0，(p1+q1)(p1+q1)，(p2+q2)(p2+q2)，(pn+qn)(pn+qn)，qn+1qn+1，qmqm）)n n存储结构选择及运算实现存储结构选择及运算实现 第38页/共50页第三十九页

43、，共49页。n n情况二：情况二：n nPn(x)=p1xe1+p2xe2+pnxenPn(x)=p1xe1+p2xe2+pnxenn nQn(x)=q1xt1+q2xt2+qmxtmQn(x)=q1xt1+q2xt2+qmxtmn n可以可以(ky(ky)表示为：表示为：n nP=P=（(p1(p1，e1)e1)，(p2(p2，e2)e2)，(pn(pn，en)en)）n nQ=Q=（(q1(q1，t1)t1)，(q2(q2，t2)t2)，(qm(qm，tm)tm)）n n存储结构选择及运算实现存储结构选择及运算实现n ntypedef struct pnodetypedef struct

44、pnoden n real coef;real coef;n n int exp;int exp;n n struct pnode *next;struct pnode *next;n n*polyn*polyn第39页/共50页第四十页，共49页。一元一元一元一元(y yun)(y yun)多项式的相加多项式的相加多项式的相加多项式的相加Ployn polynadd(poly pa,poly pb)Ployn polynadd(poly pa,poly pb)pnode*at,*bt,*ct,*q;pnode*at,*bt,*ct,*q;ct=pc=pa;at=pa-next;bt=pb-n

45、ext;ct=pc=pa;at=pa-next;bt=pb-next;while(at&bt)while(at&bt)if(at-expexp)if(at-expexp)ct=at;at=at-next;ct=at;at=at-next;else if(at-exp=bt-exp)else if(at-exp=bt-exp)x=at-coef+bt-coef);x=at-coef+bt-coef);if(x)at-coef=x;ct=at;if(x)at-coef=x;ct=at;else ct=at-next;free(at);else ct=at-next;free(at);at=ct-n

46、ext;q=bt;bt=bt-next;free(q);at=ct-next;q=bt;bt=bt-next;free(q);else q=bt-next;bt-next=at;ct-next=bt;else q=bt-next;bt-next=at;ct-next=bt;ct=ct-next;bt=q;ct=ct-next;bt=q;/*while*/*while*/if(bt)ct-next=bt;if(bt)ct-next=bt;free(bt);free(bt);return pa;return pa;第40页/共50页第四十一页，共49页。本章本章(bn zhn)小结小结n n了解线

47、性表的定义和线性结构的特点。n n理解两类存储结构（顺序和链式存储结构）的描述方法，以及单链表、循环链表、双向链表的特点；n n掌握线性表在顺序存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析；n n会用单链表编写查找、插入、删除、合并等的有关算，并学会何时选用何种链表的方法；n n学会从时间和空间复杂角度比较线性表的不同特点极其(jq)使用场合。第41页/共50页第四十二页，共49页。习题习题(xt)n n一、填空题一、填空题n n(1)(1)链表中逻辑上相邻的元素的物理位置链表中逻辑上相邻的元素的物理位置_相连。相连。n n(2)(2)在单链表中除首结点外，任意结点的存储位置

48、都由在单链表中除首结点外，任意结点的存储位置都由_结结点中的指针指示。点中的指针指示。n n(3)(3)在单链表中，设置头结点的作用在单链表中，设置头结点的作用(zuyng)(zuyng)是在插入或删除首结点是在插入或删除首结点时不必对时不必对_进行处理。进行处理。n n(4)(4)线性表的存储结构有顺序存储和线性表的存储结构有顺序存储和_存储两种。存储两种。n n(5)(5)线性表的元素长度为线性表的元素长度为4 4，在顺序存储结构下，在顺序存储结构下LOC(ai)LOC(ai)20002000，则，则LOC(ai+1)LOC(ai+1)_ _。n n(6)(6)线性表的元素长度为线性表的元

49、素长度为L L，在顺序存储结构下，在顺序存储结构下Loc(ai)Loc(ai)Loc(a1)+_Loc(a1)+_。第42页/共50页第四十三页，共49页。n n(7)已带表头结点的单链表L，指针(zhzhn)p指向L链表中的一个结点，指针(zhzhn)q是指向L链表外的一个结点，则：n n 在指针(zhzhn)p所指结点后插入q所指结点的语句序列是_；n n 在指针(zhzhn)p所指结点前插入q所指结点的语句序列是_；n n 将q所指结点插入在链表首结点的语句序列是_；n n 将q所指结点插入在链表尾结点的语句序列是_。第43页/共50页第四十四页，共49页。n n(8)(8)已知带表头结

50、点的单链表已知带表头结点的单链表L L，指针，指针p p指向指向L L链表中的一个结点链表中的一个结点(非首结点非尾结点非首结点非尾结点)，则：，则：n n 删除指针删除指针p p所指结点的直接后继结点的语句所指结点的直接后继结点的语句(y(y j)j)是是_；n n 删除指针删除指针p p所指结点的直接前驱结点的语句所指结点的直接前驱结点的语句(y(y j)j)序列是序列是_；n n 删除指针删除指针p p所指结点的语句所指结点的语句(y(y j)j)序列是序列是_；n n 删除首结点的语句删除首结点的语句(y(y j)j)序列是序列是_；n n 删除尾结点的语句删除尾结点的语句(y(y j