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

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,数据结构,线性表,数据结构线性表及其基本算法,教学目标,线性表的逻辑结构特征；线性表上定义的基本运算，并利用基本运算构造出较复杂的运算。,掌握顺序表的含义及特点，顺序表上的插入、删除操作是及其平均时间性能分析，解决简单应用问题。,掌握链表如何表示线性表中元素之间的逻辑关系；单链表、双链表、循环链表链接方式上的区别；单链表上实现的建表、查找、插入和删除等基本算法及其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义和相关算法。利用链表设计算法解决简单应用问题。,领会顺序表和链表的比较，以及如何选择其一作为其存储结构才能取得较优的时空性能。,教学重点与难点,本章的重点是掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析；,难点是使用本章所学的基本知识设计有效算法解决与线性表相关的应用问题。,教学方法,课堂讲授,提问互动,实验,定义,:,线性表（,linear list,）,（,a,1,，,a,2,，,，,a,n,）,其中,:,n,：数据元素的个数或线性表的长度；,a,i,：,是一个抽象的符号，它的数据类型设定为,ElemType,，表示某一种具体的已知数据类型（,1in,）,。,2.1,线性表的类型定义,非空线性表的特征（,P,18,）,有且仅有一个开始结点,(,表头结点,head)a,1,，它没有直接前驱，只有一个直接后继,;,有且仅有一个终端结点,(,表尾结点,tail)a,n,，它没有直接后继，只有一个直接前驱,;,其它结点都有一个直接前驱和直接后继；,元素之间为一对一的线性关系。,线性表的抽象数据类型定义（,P,18,）,ADT List,数据对象：,D=a,i,|a,i,ElemSet;1in,n0;,数据关系：,R=|a,i,a,i+1,D,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,算法（线性表的首尾合并）,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),算法（有序线性表的合并）,void MergeList(List La,List Lb,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=L.listsize),newbase=(ElemType*)realloc(L.elem,(L.listsize+LISTINCREMENT)*sizeof(ElemType);,if(!newbase)exit(OVERFLOW);,L.elem=newbase;L.listsize+=LISTINCREMET;,q=,for(p=,*q=e;,+L.length;,return OK;,/ListInsert_Sq,for(j=L.length-1;j=i-1;j-),L.elemj+1=L.elemj,a,1,a,2,a,i,a,i+1,a,n,0,1,i-1,i,下标,a,1,a,2,a,i,a,n-1,a,n,e,插入算法的时间复杂度分析,插入算法花费的时间，主要在于循环中元素的向后移动上面，而元素的移动次数与插入的位置,i,有关：,(,设,L.length=n,),当,i=1,时，全部元素都得移动，需,n,次移动，,当,i=n+1,时，不需移动元素，,一般地：在,i,位置插入时移动次数,c,i,为,n-i+1,，,假设在每个位置插入的概率为,p,i,（不妨设为等概率），则平均移动元素的次数为：,故时间复杂度为,O(n),。,算法,2.5,顺序表中删除元素,Status ListDelete_Sq(Sqlist&L,int i,ElemType&e),if(iL.length)return ERROR;,p=,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.length-1;j+),L.elemj-1=L.elemj,；,删除算法的时间复杂度分析,删除算法花费的时间，主要在于循环中元素的前移上，而元素的移动次数与删除的位置,i,有关：,(,设,L.length=n,),当,i=1,时，其后的全部元素都得移动，需,n-1,次移动，,当,i=n,时，不需移动元素，,一般地：在,i,位置删除元素时的移动次数,c,i,为,n-i,假设在每个位置删除的概率为,p,i,（不妨设为等概率），则平均移动元素的次数为：,故时间复杂度为,O(n),。,算法,2.6,顺序表中元素的查找,int LocateElem_Sq(Sqlist L,ElemType e,status(*compare)(ElemType,ElemType),i=1;,p=L.elem;,while(iL.length,if(i=L.length)return i;,else return 0;,/ListDelete_Sq,注,：,设,L.length=n,，,则,T(n)=O(n),算法,2.6-1,顺序表中元素的查找,int LocateElem_Sq(Sqlist L,ElemType e),i=0;,while(iL.length,if(iL.length)return i+1;,else return 0;,/ListDelete_Sq,注,：,设,L.length=n,，,则,T(n)=O(n),算法,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)&(pb=pb_last),if(*pa=*pb)*pc+=*pa+;,else*pc+=*pb+;,while(pa=pa_last)*pc+=*pa+;,while(pb=pb_last)*pc+=*pb+;,顺序存储结构的优缺点,优点,逻辑相邻，物理相邻,可随机存取任一元素,存储空间使用紧凑,缺点,插入、删除操作需要移动大量的元素；,预先分配空间需按最大空间分配，空间利用不充分。,DuLNode,*DuLinkList,(10)在下图所示的链表中，若在指针p所指的结点之后插入数据字段相继为a和b的两个结点，则可用下列两个语句实现该操作，它们依次是_和_。,if (!LocateElem(La,e,equal),ADT List,1 线性链表（单链表）,length-1;j+),for(i=1;iexp=bt-exp),算法（有序链表的合并）,return OK;,Pn(x)=p1xe1+p2xe2+pnxen,else return 0;,/InitList_Sq,160,H,2.3,线性表的链式存储结构,先看一个例子：,线性表,(,a,1,a,2,a,3,a,4,a,5,a,6,a,7,a,8,),指针域,200,190,150,210,260,110,NULL,240,头指针,存储地址,数据域,110,a,5,150,a,2,160,a,1,190,a,3,200,a,6,210,a,4,240,a,8,260,a,7,示意图：,a,n,a,1,a,2,a,3,H,H,NULL,L,a,n,a,1,a,2,L,2.3,线性表的链式存储结构,线性表的链式存贮结构及特点,用一组任意的存储单元存放线性表中的各元素,;,数据之间的逻辑关系由结点中的指针指示,;,是一种非随机存取,(,顺序存取,),的存储结构,;,插入删除时无需移动大量元素。,常用的链表有：,单链表,循环链表,双向链表,多重链表,2.3.1,线性链表（单链表）,在定义的链表中，若只含有一个指针域来存放下一个元素地址，称这样的链表为单链表或线性链表。,结点结构与定义：,data,next,线性链表示意图,a,1,a,2,a,3,H,typedef struct LNode,ElemType data;,struct LNode*next;,LNode,*LinkList;,a,n,a,1,a,2,L,2.3.1,线性链表（单链表）,单链表的基本算法：,读取元素 （算法）,插入新结点（算法）,删除结点 （算法）,链表的创建（算法）,有序链表的合并（算法）,2.3.1,线性链表（单链表）,算法（取元素）,Status GetElem_L(LinkList L,int i,ElemType&e),p=L-next;,j=1;,while(p&jnext;,j+;,if(!p|ji)return ERROR;,e=p-data;,return OK;,注意：,循环控制条件及异常处理,算法的时间复杂度：,O(n),算法（插入元素）,Status ListInsert_L(LinkList&L,int i,ElemType e),p=L;,j=0;,while(p&jnext;,j+;,if(!p|ji-1)return ERROR;,s=(LinkList)malloc(sizeof(LNode);,s-data=e;s-next=p-next;p-next=s;,return OK;,x,s,b,a,p,2.3.1,线性链表（单链表）,b,a,p,算法的时间复杂度为,0(n),。,2.3.1,线性链表（单链表）,算法（删除元素）,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-next;e=q-data;,free(q);,return OK;,2.3.1,线性链表（单链表）,算法（头插法建立单链表）,void CreateListe_L_1(LinkList&L,int n),L=(LinkList)malloc(sizeof(LNode);,L-next=NULL;,for(i=1;inext=L-next;,L-next=p;,2.3.1,线性链表（单链表）,算法（尾插法建立单链表）,void CreateListe_L_2(LinkList&L,int n),L=(LinkList)malloc(sizeof(LNode);,L-next=NULL;,q=L;,for(i=1;inext=p;,q=p;,q-next=NULL;,2.3.1,线性链表（单链表）,算法（有序链表的合并）,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;,free(Lb);,2.3.2,单循环链表,L,a,n,a,1,a,2,循环链表的操作与单链表的操作类似，差别如下：,链表的判空条件：,L-next=L,最后一个结点的判定条件,:,p-next=L,可以设立尾指针,单循环链表示意图,2.3.3,双向链表,概念引入,结点结构与定义,prior,data,next,typedef struct DuLNode,ElemType data;,struct DuLNode*prior;,struct DuLNode*next;,DuLNode,*DuLinkList,双向链表示意图,L,a,2,a,3,a,1,a,n,L,a,2,a,3,a,1,a,n,算法（双向循环链表中插入元素）,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;,return OK;,/ListInsert_Dul,算法（双向循环链表中删除元素）,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,typedef struct DuLNode,int LocateElem_Sq(Sqlist L,ElemType e,if(inext;pb=Lb-next;,P=（(p1，e1)，(p2，e2)，(pn，en)）,p=p-next;,2 线性表的顺序存储结构,if (!LocateElem(La,e,equal),插入删除时需移动大量元素;,删除算法花费的时间，主要在于循环中元素的前移上，而元素的移动次数与删除的位置i有关：(设L.,设LocateElem的执行时间与表长成正比，,length)return i;,struct DuLNode*prior;,具体要求,顺序表,链表,基于空间,适于线性表长度变化不大，易于事先确定其大小时采用。,适于当线性表长度变化大，难以估计其存储规模时采用。,基于时间,由于顺序表是一种随机存储结构，当线性表的操作主要是查找时，宜采用。,链表中对任何位置进行插入和删除都只需修改指针，所以这类操作为主的线性表宜采用链表做存储结构。若插入和删除主要发生在表的首尾两端，则宜采用尾指针表示的单循环链表。,线性表的两种存储结构的比较,2.4,线性表的应用举例,高级语言中的数组；,计算机的文件系统；,计算机的目录系统；,号码查询系统（可采用顺序表或单链表结构）；,各种事务处理（各种表格均采用顺序表和线性链表结构）,一元多项式的表示和相加,例：一元多项式的表示和相加,情况一：,P,n,(x)=p,0,+p,1,x+p,2,x,2,+p,n,x,n,Q,n,(x)=q,0,+q,1,x+q,2,x,2,+q,n,x,m,R,n,(x)=(p,0,+,q,0,)+(p,1,+,q,1,),x+(p,2,+,q,2,),x,2,+(p,n,+,q,n,)x,n,+q,n+1,x,n+1,+q,m,x,m,可以表示为,：,P=,（,p,0,，,p,1,，,p,2,，,，,p,n,）,Q=,（,q,0,，,q,1,，,q,2,，,，,q,m,）,R=(p,0,+,q,0,，,(p,1,+,q,1,),，,(p,2,+,q,2,),，,，,(p,n,+,q,n,),，,q,n+1,，,，,q,m,）,),存储结构选择及运算实现,情况二：,P,n,(x)=p,1,x,e,1,+p,2,x,e,2,+p,n,x,e,n,Q,n,(x)=q,1,x,t,1,+q,2,x,t,2,+q,m,x,t,m,可以表示为：,P=,（,(,p,1,，,e,1,),，,(,p,2,，,e,2,),，,，,(,p,n,，,e,n,),）,Q=,（,(,q,1,，,t,1,),，,(,q,2,，,t,2,),，,，,(,q,m,，,t,m,),）,存储结构选择及运算实现,typedef struct pnode,real coef;,int exp;,struct pnode *next;,*polyn,一元多项式的相加,Ployn polynadd(poly pa,poly pb),pnode*at,*bt,*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;,本章小结,了解线性表的定义和线性结构的特点。,理解两类存储结构（顺序和链式存储结构）的描述方法，以及单链表、循环链表、双向链表的特点；,掌握线性表在顺序存储结构中实现基本运算（查找、插入、删除、合并等）的算法及分析；,会用单链表编写查找、插入、删除、合并等的有关算，并学会何时选用何种链表的方法；,学会从时间和空间复杂角度比较线性表的不同特点极其使用场合。,习题,一、填空题,(1),链表中逻辑上相邻的元素的物理位置,_,相连。,(2),在单链表中除首结点外，任意结点的存储位置都由,_,结点中的指针指示。,(3),在单链表中，设置头结点的作用是在插入或删除首结点时不必对,_,进行处理。,(4),线性表的存储结构有顺序存储和,_,存储两种。,(5),线性表的元素长度为,4,，在顺序存储结构下,LOC(,a,i,),2000,，则,LOC(a,i+1,),_,。,(6),线性表的元素长度为,L,，在顺序存储结构下,Loc(a,i,),Loc(a,1,)+_,。,(,7),已带表头结点的单链表,L,，指针,p,指向,L,链表中的一个结点，指针,q,是指向,L,链表外的一个结点，则：,在指针,p,所指结点后插入,q,所指结点的语句序列是,_,；,在指针,p,所指结点前插入,q,所指结点的语句序列是,_,；,将,q,所指结点插入在链表首结点的语句序列是,_,；,将,q,所指结点插入在链表尾结点的语句序列是,_,。,(,8),已知带表头结点的单链表,L,，指针,p,指向,L,链表中的一个结点,(,非首结点非尾结点,),，则：,删除指针,p,所指结点的直接后继结点的语句是,_,；,删除指针,p,所指结点的直接前驱结点的语句序列是,_,；,删除指针,p,所指结点的语句序列是,_,；,删除首结点的语句序列是,_,；,删除尾结点的语句序列是,_,。,(,9),已知指针,p,指向双向链表中的一个结点,(,非首结点，非尾结点,),，则：,将结点,s,插入在指针,p,所指结点的直接后继位置的语句是,_,；,将结点,s,插入在指针,p,所指结点的直接前驱位置的语句是,_,；,删除指针,p,所指结点的直接后继结点的语句序列是,_,；,删除指针,p,所指结点的直接前驱结点的语句序列是,_,；,删除指针,p,所指结点的语句序列是,_,。,L=(LinkList)malloc(sizeof(LNode);,j+;,j+;,length)return i+1;,p=p-next;,else q=bt-next;bt-next=at;ct-next=bt;,for(i=1;inext=L,C.L-next=p,D.p-next=NULL,(3),指针,p,指向双向循环链表的尾结点的条件是：,A.p=L,B.p=NULL,C.p-prior=L,D.p-next=NULL,习题,三、算法题,