数据结构线性表及其基本算法.pptx

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

1、教学目标线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。掌握顺序表的含义及特点，顺序表上的插入、删除操作是及其平均时间性能分析，解决简单应用问题。掌握链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。领会顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。第1页/共50页教学重点与难点本章的重点是掌握顺序表和

2、单链表上实现的各种基本算法及相关的时间性能分析；难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。教学方法课堂讲授提问互动实验第2页/共50页定义:线性表（linear list）（a1，a2，an）其中:n：数据元素的个数或线性表的长度；ai：是一个抽象的符号，它的数据类型设定为ElemType，表示某一种具体的已知数据类型（1in）。2.1 线性表的类型定义第3页/共50页非空线性表的特征（P18）有且仅有一个开始结点(表头结点 head)a1，它没有直接前驱，只有一个直接后继;有且仅有一个终端结点(表尾结点tail)an，它没有直接后继，只有一个直接前驱;其它结点都有一

3、个直接前驱和直接后继；元素之间为一对一的线性关系。第4页/共50页线性表的抽象数据类型定义（P18）ADT List 数据对象：D=ai|aiElemSet;1in,n0;数据关系：R=|ai,ai+1D,i=1,2,n-1 基本操作：InitList(&L)ListLength(L)GetElem(L,i,&e)PriorElem(L,cur_e,&pre_e)NextElem(L,cur_e,&next_e)LocateElem(L,e,compare()ListInsert(&L,i,e)ListDelete(&L,i,&e)ADT List第5页/共50页算法2.1（线性表的首尾合并）

4、void union(List&La,List Lb)La_len=ListLength(La);Lb_len=ListLength(Lb);for(i=1;i=Lb_len;i+)GetElem(Lb,i,e);if (!LocateElem(La,e,equal)ListInsert(La,+La_len,e);/union 算法分析：设LocateElem的执行时间与表长成正比，即：算法的时间复杂度为：O(ListLength(La)*ListLength(Lb)第6页/共50页算法2.2（有序线性表的合并）void MergeList(List La,List Lb,List&Lc)I

5、nitList(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);/Mer

6、geList第7页/共50页2.2 线性表的顺序存储结构一、特点1.用一组地址连续的存储单元依次存放线性表中的元素；2.以元素在机内的“物理位置相邻”来表示数据之间的逻辑关系:LOC(ai+1)LOC(ai)L3.是一种随机存取的存储结构;LOC(ai)LOC(a1)(i1)*L4.插入删除时需移动大量元素;a1a2aiai+1anLOC(a a1 1)LOC(a ai i)LOC(a ai+1i+1)第8页/共50页2.2 线性表的顺序存储结构二、描述方式#define LIST_INIT_SIZE 100#define LISTINCREMENT 10typedef structElemT

7、ype*elem;int length;int listsize;SqList第9页/共50页2.2 线性表的顺序存储结构三、基本操作的算法描述 初始化顺序表 （算法 2.3）插入元素 （算法 2.4）删除元素 （算法 2.5）元素的查找（算法 2.6）顺序表的合并 （算法 2.7）第10页/共50页算法2.3（初始化顺序表）Status InitList_Sq(SqList&L)L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType)if(!L.elem)exit（OVERFLOW）;L.length=0;L.listsize=LIST

8、_INIT_SIZE;return OK;/InitList_Sq第11页/共50页算法2.4：顺序表中插入一个元素Status ListInsert_Sq(SqList&L,int i,ElemType e)if(iL.length+1)return ERROR;if(L.length=L.listsize)newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);if(!newbase)exit(OVERFLOW);L.elem=newbase;L.listsize+=LISTINCREMET

9、;q=&(L.elemi-1);for(p=&(L.elemL.length-1);p=q;-p)*(p+1)=*p;*q=e;+L.length;return OK;/ListInsert_Sq for(j=L.length-1;j=i-1;j-)L.elemj+1=L.elemj第12页/共50页a1a2aiai+1anL.elem01i-1i下标a1a2aian-1ane第13页/共50页插入算法的时间复杂度分析插入算法花费的时间，主要在于循环中元素的向后移动上面，而元素的移动次数与插入的位置i有关：(设L.length=n)当i=1时，全部元素都得移动，需n次移动，当i=n+1时，不需

10、移动元素，一般地：在i位置插入时移动次数ci为n-i+1，假设在每个位置插入的概率为pi（不妨设为等概率），则平均移动元素的次数为：故时间复杂度为O(n)。第14页/共50页 算法2.5 顺序表中删除元素Status ListDelete_Sq(Sqlist&L,int i,ElemType&e)if(iL.length)return ERROR;p=&(L.elemi-1);e=*p;q=L.elem+L.length-1;for(+p;p=q;+p)*(p-1)=*p;-L.length;return OK;/ListDelete_Sq e=L.elemi-1;For(j=i;j=L.le

11、ngth-1;j+)L.elemj-1=L.elemj；第15页/共50页删除算法的时间复杂度分析删除算法花费的时间，主要在于循环中元素的前移上，而元素的移动次数与删除的位置i有关：(设L.length=n)当i=1时，其后的全部元素都得移动，需n-1次移动，当i=n时，不需移动元素，一般地：在i位置删除元素时的移动次数ci为n-i假设在每个位置删除的概率为pi（不妨设为等概率），则平均移动元素的次数为：故时间复杂度为O(n)。第16页/共50页算法2.6 顺序表中元素的查找int LocateElem_Sq(Sqlist L,ElemType e,status(*compare)(ElemT

12、ype,ElemType)i=1;p=L.elem;while(iL.length&!(*compare)(*p+,e)+i;if(i=L.length)return i;else return 0;/ListDelete_Sq注 ：设L.length=n，则T(n)=O(n)第17页/共50页算法2.6-1 顺序表中元素的查找int LocateElem_Sq(Sqlist L,ElemType e)i=0;while(iL.length&L.elemi!=e)+i;if(iL.length)return i+1;else return 0;/ListDelete_Sq注注 ：设设L.len

13、gth=n，则则T(n)=O(n)第18页/共50页 算法2.7 顺序表的合并Status MergeList_Sq(Sqlist La,Sqlist Lb,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(!pc)return OVERFLOW;pa_last=pa+La.length-1;pb_last=pb+Lb.length-1;while(pa=pa_last)&(p

14、b=pb_last)if(*pa=*pb)*pc+=*pa+;else*pc+=*pb+;while(pa=pa_last)*pc+=*pa+;while(pbnext;j=1;while(p&jnext;j+;if(!p|ji)return ERROR;e=p-data;return OK;注意：注意：n循环控制条件及异常处理循环控制条件及异常处理n算法的时间复杂度：算法的时间复杂度：O(n)第26页/共50页算法2.9（插入元素）Status ListInsert_L(LinkList&L,int i,ElemType e)p=L;j=0;while(p&jnext;j+;if(!p|ji

15、-1)return ERROR;s=(LinkList)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;return OK;xsbap2.3.1 线性链表（单链表）bap算法的时间复杂度为算法的时间复杂度为0(n)。第27页/共50页2.3.1 线性链表（单链表）算法2.10（删除元素）Status ListDelete_L(LinkList&L,int i,ElemType&e)p=L;j=0;while(p-next&jnext;j+;if(!(p-next)|ji-1)return ERROR;q=p-next;p-next=q-

16、next;e=q-data;free(q);return OK;第28页/共50页2.3.1 线性链表（单链表）算法2.11-1（头插法建立单链表）void CreateListe_L_1(LinkList&L,int n)L=(LinkList)malloc(sizeof(LNode);L-next=NULL;for(i=1;idata);p-next=L-next;L-next=p;第29页/共50页2.3.1 线性链表（单链表）算法2.11-2（尾插法建立单链表）void CreateListe_L_2(LinkList&L,int n)L=(LinkList)malloc(sizeof

17、(LNode);L-next=NULL;q=L;for(i=1;idata);q-next=p;q=p;q-next=NULL;第30页/共50页2.3.1 线性链表（单链表）算法2.12（有序链表的合并）void MergeListe_L(LinkList&La,LinkList&Lb,LinkList&Lc)pa=La-next;pb=Lb-next;Lc=pc=La;while(pa&pb)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;/while pc-next=pa?pa:pb;

18、free(Lb);第31页/共50页2.3.2 单循环链表L an a1a2n 循环链表的操作与单链表的操作类似，差别如下：循环链表的操作与单链表的操作类似，差别如下：链表的判空条件：链表的判空条件：L-next=L最后一个结点的判定条件最后一个结点的判定条件:p-next=L可以设立尾指针可以设立尾指针单循环链表示意图单循环链表示意图第32页/共50页2.3.3 双向链表概念引入结点结构与定义priordatanexttypedef struct DuLNode ElemType data;struct DuLNode*prior;struct DuLNode*next;DuLNode,*D

19、uLinkListn双向链表示意图双向链表示意图L a2 a3 a1 an L a2 a3 a1 an第33页/共50页算法2.18（双向循环链表中插入元素）Status ListInsett_DuL(DuLinkList&L,int i,ElemType e)p=L-next;j=1;while(p!=L&jnext;j+;if(p=L|ji)return ERROR;if(!(s=(DuLinkList)malloc(sizeof(DuLNode)return ERROR;s-data=e;s-prior=p-prior;p-prior-next=s;s-next=p;p-prior=s;

20、return OK;/ListInsert_Dul第34页/共50页算法2.19（双向循环链表中删除元素）Status ListDelete_DuL(DuLinkList&L,int i,ElemType e)p=L-next;j=1;while(p!=L&jnext;j+;if(p=L|ji)return ERROR;e=p-data;p-prior-next=p-next;p-next-prior=p-prior;free(p);return OK;/ListDelete第35页/共50页具体要求具体要求顺序表顺序表链表链表基于空间基于空间适于线性表长适于线性表长度变化不大，度变化不大，易

21、于事先确定易于事先确定其大小时采用。其大小时采用。适于当线性表长度变化大，难以估计适于当线性表长度变化大，难以估计其存储规模时采用。其存储规模时采用。基于时间基于时间由于顺序表是由于顺序表是一种随机存储一种随机存储结构，当线性结构，当线性表的操作主要表的操作主要是查找时，宜是查找时，宜采用。采用。链表中对任何位置进行插入和删除都链表中对任何位置进行插入和删除都只需修改指针，所以这类操作为主的只需修改指针，所以这类操作为主的线性表宜采用链表做存储结构。若插线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。则宜采用尾指针

22、表示的单循环链表。线性表的两种存储结构的比较第36页/共50页2.4 线性表的应用举例高级语言中的数组；计算机的文件系统；计算机的目录系统；电话号码查询系统（可采用顺序表或单链表结构）；各种事务处理（各种表格均采用顺序表和线性链表结构）一元多项式的表示和相加第37页/共50页例：一元多项式的表示和相加情况一：Pn(x)=p0+p1x+p2x2+pnxnQn(x)=q0+q1x+q2x2+qnxmRn(x)=(p0+q0)+(p1+q1)x+(p2+q2)x2+(pn+qn)xn+qn+1xn+1+qmxm可以表示为：P=（p0，p1，p2，pn）Q=（q0，q1，q2，qm）R=(p0+q0，

23、(p1+q1)，(p2+q2)，(pn+qn)，qn+1，qm）)存储结构选择及运算实现 第38页/共50页情况二：Pn(x)=p1xe1+p2xe2+pnxenQn(x)=q1xt1+q2xt2+qmxtm可以表示为：P=（(p1，e1)，(p2，e2)，(pn，en)）Q=（(q1，t1)，(q2，t2)，(qm，tm)）存储结构选择及运算实现typedef struct pnode real coef;int exp;struct pnode *next;*polyn第39页/共50页一元多项式的相加Ployn polynadd(poly pa,poly pb)pnode*at,*bt,

24、*ct,*q;ct=pc=pa;at=pa-next;bt=pb-next;while(at&bt)if(at-expexp)ct=at;at=at-next;else if(at-exp=bt-exp)x=at-coef+bt-coef);if(x)at-coef=x;ct=at;else ct=at-next;free(at);at=ct-next;q=bt;bt=bt-next;free(q);else q=bt-next;bt-next=at;ct-next=bt;ct=ct-next;bt=q;/*while*/if(bt)ct-next=bt;free(bt);return pa;

25、第40页/共50页本章小结了解线性表的定义和线性结构的特点。理解两类存储结构（顺序和链式存储结构）的描述方法，以及单链表、循环链表、双向链表的特点；掌握线性表在顺序存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析；会用单链表编写查找、插入、删除、合并等的有关算，并学会何时选用何种链表的方法；学会从时间和空间复杂角度比较线性表的不同特点极其使用场合。第41页/共50页习题一、填空题(1)链表中逻辑上相邻的元素的物理位置_相连。(2)在单链表中除首结点外，任意结点的存储位置都由_结点中的指针指示。(3)在单链表中，设置头结点的作用是在插入或删除首结点时不必对_进行处理。(4)线性表的

26、存储结构有顺序存储和_存储两种。(5)线性表的元素长度为4，在顺序存储结构下LOC(ai)2000，则LOC(ai+1)_。(6)线性表的元素长度为L，在顺序存储结构下Loc(ai)Loc(a1)+_。第42页/共50页(7)已带表头结点的单链表L，指针p指向L链表中的一个结点，指针q是指向L链表外的一个结点，则：在指针p所指结点后插入q所指结点的语句序列是_；在指针p所指结点前插入q所指结点的语句序列是_；将q所指结点插入在链表首结点的语句序列是_；将q所指结点插入在链表尾结点的语句序列是_。第43页/共50页(8)已知带表头结点的单链表L，指针p指向L链表中的一个结点(非首结点非尾结点)，

27、则：删除指针p所指结点的直接后继结点的语句是_；删除指针p所指结点的直接前驱结点的语句序列是_；删除指针p所指结点的语句序列是_；删除首结点的语句序列是_；删除尾结点的语句序列是_。第44页/共50页(9)已知指针p指向双向链表中的一个结点(非首结点，非尾结点)，则：将结点s插入在指针p所指结点的直接后继位置的语句是_；将结点s插入在指针p所指结点的直接前驱位置的语句是_；删除指针p所指结点的直接后继结点的语句序列是_；删除指针p所指结点的直接前驱结点的语句序列是_；删除指针p所指结点的语句序列是_。第45页/共50页(10)在下图所示的链表中，若在指针p所指的结点之后插入数据字段相继为a和b

28、的两个结点，则可用下列两个语句实现该操作，它们依次是_和_。第46页/共50页 习题二、单选题(1)下列说法正确的是：A.线性表的逻辑顺序和存储顺序总是一致的B.线性表的链式存储结构中，内存中可用的存储单元可以是连续的，也可以不连续C.线性表的顺序存储结构优于链式存储结构D.每种数据结构都具有插入、删除和查找三种基本操作。(2)线性表中哪些元素只有一个直接前驱和一个直接后继A.首元素B.尾元素C.中间的元素D.所有的元素第47页/共50页(3)指针p指向循环单链表的首结点的条件是：A.p=LB.p-next=LC.L-next=pD.p-next=NULL(3)指针p指向双向循环链表的尾结点的条件是：A.p=LB.p=NULLC.p-prior=LD.p-next=NULL第48页/共50页习题三、算法题第49页/共50页