数据结构ppt课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 线性表,线性结构,特点,：在数据元素的非空有限集中,存在,唯一,的一个被称作“,第一个,”的数据元素,存在,唯一,的一个被称作“,最后一个,”的数据元素,除第一个外，集合中的每个数据元素均,只有一个前驱,除最后一个外，集合中的每个数据元素均,只有一个后继,2.1,线性表的逻辑结构,定义：一个线性表是,n,个数据元素的有限序列,例 英文字母表,（,A,B,C,.Z),是一个线性表,例,数据元素,例 一副扑克的点数,（,2,，,3,，,4,，,，,J,，,Q,，,K,，,A,）,从以上例子可看出线性表的逻辑特征是：,在非空的线性表，有且仅有一个开始结点,a,1,，,它没有直接前趋，而仅有一个直接后继,a,2,；,有且仅有一个终端结点,a,n,，,它没有直接后继，而仅有一个直接前趋,a,n-1,；,其余的内部结点,a,i,(2in-1),都有且仅有一个直接前趋,a,i-1,和一个直接后继,a,i+1,。,线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。,特征：,元素个数,n,表长度，,n=0,空表,1,i=0 ,数据关系：,Rl,= ai-1,，,ai,| ai-1,，,ai,D,，,i=1,2,n ,基本操作：,InitList(&L,),DestroyList(&L,),ClearList(&L,),ListEmpty(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,(),ADT List,算法,2.1,利用两个线性表,LA,和,LB,分别表示两个集合,A,和,B,，,现要求一个新的集合,A=AB,。,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-en,，,e) ,算法的时间复杂度：,O,（,ListLength(LA,) ,ListLength(LB,),）,算法,2.2,巳知线性表,LA,和线性表,LB,中的数据元素按值非递减有序排列，现要求将,LA,和,LB,归并为一个新的线性表,LC,，且,LC,中的元素仍按值非递减有序排列。,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,;,elselistinsert(lc,，,+k,，,bj);+j,;,while(I=la-,len,),getelem(la,，,I+,，,ai);listinsert(lc,，,+k,，,ai,); ,while(j=,ListSize,) ,printf(“overflow,”); exit(overflow); ,for (j=l.length-1;j=I-1;j-) l.dataj+1=l.dataj; l.dataI-1=x;,l.length,+;,内存,a,1,a,2,a,i,a,i+1,a,n,0,1,i-1,V,数组下标,n-1,i,n,1,2,i,元素序号,i+1,n,n+1,内存,a,1,a,2,a,i,a,i+1,a,n,0,1,i-1,V,数组下标,n-1,i,n,1,2,i,元素序号,i+1,n,n+1,a,n-1,x,分析算法的复杂度,这里的问题规模是表的长度，设它的值为。该算法的时间主要化费在循环的结点后移语句上，该语句的执行次数（即移动结点的次数）是。由此可看出，所需移动结点的次数不仅依赖于表的长度，而且还与插入位置有关。,当,i=n+1,时，由于循环变量的终值大于初值，结点后移语句将不进行；这是,最好,情况，其时间复杂度,O,（,1,）；,当,i=1,时，结点后移语句将循环执行,n,次，需移动表中所有结点，这是,最坏,情况，其时间复杂度为,O,（,n,）。,算法时间复杂度,T(n),设,Pi,是在第,i,个元素之前插入一个元素的概率，则在长度为,n,的线性表中插入一个元素时，所需移动的元素次数的平均次数为：,也就是说，在顺序表上做插入运算，平均要移动表上一半结点。当表长,n,较大时，算法的效率相当低。虽然,Eis(n,),中,n,的的系数较小，但就数量级而言，它仍然是线性阶的。因此算法的平均时间复杂度为,O(n),。,动态,删除,定义：线性表的删除是指将第,i,（,1,i,n,）,个元素删除，使长度为,n,的线性表,变成,长度为,n-1,的线性表,需将第,i+1,至第,n,共,（,n-i),个元素前移,算法,Void,deleteList,(,Sqlist,*L,，,int,i) ,int,j;,if (il.length),printf(“Position,error”);,return ERROR ,for (j=i;jdata,表示,p,指向结点的数据域,(*p).link,p-link,表示,p,指向结点的指针域,线性链表,定义：结点中只含一个指针域的链表叫,，也叫单链表,typedef,listnode,*,linklist,;,listnode,*p;,linklist,head;,注意区分,指针变量,和,结点变量,这两个不同的概念。,P,为动态变量，它是通过标准函数生成的，即,p=(,listnode,*),malloc(sizeof(listnode,);,函数,malloc,分配了一个类型为,listnode,的结点变量的空间，并将其首地址放入指针变量,p,中。一旦,p,所指的结点变量不再需要了，又可通过标准函数,free ( p ),释放所指的结点变量空间。,指针变量,P,（其值为结点地址）和结点变量*,P,之间的关系。,一、建立单链表,假设线性表中结点的数据类型是字符，我们逐个输入这些字符型的结点，并以换行符,n,为输入结束标记。动态地建立单链表的常用方法有如下两种：,1,、头插法建表,该方法从一个空表开始，重复读入数据，生成新结点，将读入数据存放到新结点的数据域中，然后将新结点插入到当前链表的表头上，直到读入结束标志为止。,a,2,.,h,头结点,a,n-1,0,a,n,linklist,createlistf,(void) char,ch,;,linklist,head;,listnode,*p; head=null;,ch,=,getchar,( );,while (,ch,!=n) p=(,listnode,*),malloc(sizeof(listnode,); pdata=,ch,; pnext=head; head=p;,ch,=,getchar,( ); ,return (head); ,2,、尾插法建表,头插法建立链表虽然算法简单，但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致，可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上，为此必须增加一个尾指针,r,，,使其始终指向当前链表的尾结点。,linklist,creater,( ) ,char,ch,;,linklist,head;,listnode,*p,，*,r; /(,， *,head;),head=NULL; r=NULL;,while(ch,=,getchar,( )!=n),p=(,listnode,*),malloc(sizeof(listnode,);,pdata=,ch,;,if(head,= =NULL) head=p;,else rnext=p;,r=p; ,if (r!=NULL) rnext=NULL;,return(head);,说明：,第一个生成的结点是开始结点，将开始结点插入到空表中，是在当前链表的第一个位置上插入，该位置上的插入操作和链表中其它位置上的插入操作处理是不一样的，原因是开始结点的位置是存放在头指针（指针变量）中，而其余结点的位置是在其前趋结点的指针域中。,算法中的,第一个,if,语句,就是用来对第一个位置上的插入操作做特殊处理。算法中的,第二个,if,语句,的作用是为了分别处理空表和非空表两种不同的情况，若读入的第一个字符就是结束标志符，则链表,head,是空表，尾指针,r,亦为空，结点*,r,不存在；否则链表,head,非空，最后一个尾结点*,r,是终端结点，应将其指针域置空。,如果我们在链表的开始结点之前附加一个结点，并称它为,头结点,，那么会带来以下两个优点：,a,、,由于开始结点的位置被存放在头结点的指针域中，所以在链表的第一个位置上的操作就和在表的其它位置上的操作一致，无需进行特殊处理；,b,、,无论链表是否为空，其头指针是指向头结点在的非空指针（空表中头结点的指针域为空），因此空表和非空表的处理也就统一了。,h,a,1,a,2,头结点,a,n,.,h,空表,头结点：,在单链表第一个结点前附设一个结点叫,头结点指针域为空表示线性表为空,linklist,createlistr1( ),char,ch,;,linklist,head=(,linklist)malloc(sizeof(listnode,);,listnode,*p,，*,r,；,r=head;,while(ch,=,getchar,( )!=n,p=(,listnode,*),malloc(sizeof(listnode,);,pdata=,ch,;,rnext=p;,r=p; ,rnext=NULL;,return(head);,上述算法里动态申请新结点空间时未加错误处理，可作下列处理：,p=(,listnode,*),malloc(sizeof(listnode,),if(p=NULL),error(No space for node can be obtained);,return ERROR;,以上算法的时间复杂度均为,O(n),二、查找运算,1,、按序号查找,在链表中，即使知道被访问结点的序号,i,，,也不能象顺序表中那样直接按序号,i,访问结点，而只能从链表的头指针出发，顺链域,next,逐个结点往下搜索，直到搜索到第,i,个结点为止。因此，链表不是随机存取结构。,设单链表的长度为,n,，,要查找表中第,i,个结点，仅当,1in,时，,i,的值是合法的。但有时需要找头结点的位置，故我们将头结点看做是第,0,个结点，其算法如下：,Listnode,*,getnode(linklist,head,，,int,i) ,int,j;,listnode,* p;,p=head;j=0;,while(pnext & jnext;,j+; ,if (i=j),return p;,else,return NULL;,2,、,按值查找,按值查找是在链表中，查找是否有结点值等于给定值,key,的结点，若有的话，则返回首次找到的其值为,key,的结点的存储位置；否则返回,NULL,。,查找过程从开始结点出发，顺着链表逐个将结点的值和给定值,key,作比较。其算法如下：,Listnode,*,locatenode(linklist,head,，,int,key) ,listnode,* p=headnext;,while( p & pdata!=key),p=pnext;,return p;,该算法的执行时间亦与输入实例中的的取值,key,有关，其平均时间复杂度的分析类似于按序号查找，也为,O(n),。,p,a,b,x,s,三、插入运算,插入运算是将值为,x,的新结点插入到表的第,i,个结点的位置上，即插入到,a,i-1,与,a,i,之间。因此，我们必须首先找到,a,i-1,的存储位置,p,，,然后生成一个数据域为,x,的新结点*,p,，,并令结点*,p,的指针域指向新结点，新结点的指针域指向结点,a,i,。,从而实现三个结点,a,i-1,，,x,和,a,i,之间的逻辑关系的变化，插入过程如：,s-next=p-next;,p-next=s;,具体算法如下：,void,insertnode(linklist,head,，,datetype,x,，,int,i),listnode,* p,，*,q;,p=,getnode(head,，,i-1);,if(p=NULL),error(position error);,q=(,listnode,*),malloc(sizeof(listnode,);,qdata=x;,qnext=pnext;,pnext=q;,设链表的长度为,n,，,合法的插入位置是,1in+1,。,注意当,i=1,时，,getnode,找到的是头结点，当,i=n+1,时，,getnode,找到的是结点,an,。,因此，用,i-1,做实参调用,getnode,时可完成插入位置的合法性检查。算法的时间主要耗费在查找操作,getnode,上，,故时间复杂度亦为,O(n),。,p,a,b,c,四、删除运算,删除运算是将表的第,i,个结点删去。因为在单链表中结点,a,i,的存储地址是在其直接前趋结点,a,i-1,的指针域,next,中，所以我们必须首先找到,a,i-1,的存储位置,p,。,然后令,pnext,指向,a,i,的直接后继结点，即把,a,i,从链上摘下。最后释放结点,a,i,的空间，将其归还给“存储池”。此过程为：,p-link=p-link-link;,具体算法如下：,void,deletelist(linklist,head,，,int,i),listnode,* p,， *,r;,p=,getnode(head,，,i-1);,if(p= =NULL |,pnext= =NULL),return ERROR;,r=pnext;,pnext=rnext;,free( r ) ;,设单链表的长度为,n,，,则删去第,i,个结点仅当,1in,时是合法的。注意，当,i=n+1,时，虽然被删结点不存在，但其前趋结点却存在，它是终端结点。因此被删结点的直接前趋*,p,存在并不意味着被删结点就一定存在，仅当*,p,存在（即,p!=NULL,）,且*,p,不是终端结点 （即,pnext!=NULL,）,时，才能确定被删结点存在。,显然此算法的时间复杂度也是,O(n),。,单链表特点,它是一种,动态结构,，整个存储空间为多个链表共用,不需预先分配,空间,指针占用,额外,存储空间,不能随机存取,，查找速度慢,静态单,链表,循环链表,(circular linked list),循环链表是表中最后一个结点的指针指向头结点，使链表构成环状,特点：从表中任一结点出发均可找到表中其他结点，提高查找效率,操作与单链表基本一致,循环条件不同,单链表,p,或,p-link=NULL,循环链表,p,或,p-link=H,h,h,空,表,双向链表（,double linked list,）,在循环链表中，访问结点的特点：,访问后继结点，只需要向后走一步，而访问前驱结点，就需要转一圈。,结论：,循环链表并不适用于经常访问前驱结点的情况。,解决方法：,在需要频繁地同时访问前驱和后继结点的时候，使用双向链表。,双向链表：,就是每个结点有两个指针域。一个指向后继结点，另一个指向前驱结点。,结点定义,typedef,struct,node,datatype,element;,struct,node *prior,*next;,JD;,prior,element,next,L,空双向循环链表：,非空双向循环链表：,L,A,B,b,c,a,p,p-prior-next= p= p-next-,proir,;,b,c,a,P,void,del_dulist(JD,*p),p-prior-next=p-next;,p-next-prior=p-prior;,free(p);,删除,算法描述,算法评价：,T(n,)=O(1),p-prior-next=p-next;,p-next-prior=p-prior;,void,ins_dulist(JD,*,p,int,x), JD *s;,s=(JD*),malloc(sizeof(JD,);,s-element=x;,s-prior=p-prior;,p-prior-next=s;,s-next=p;,p-prior=s;,算法描述,算法评价：,T(n)=O(1),x,S,b,a,P,插入,2.4,线性表的应用举例,一元多项式的表示及相加,一元多项式的表示：,可用线性表,P,表示,但对,S(x),这样的多项式浪费空间,一般,其中,用数据域含两个数据项的线性表表示,其存储结构可以用顺序存储结构，也可以用单链表,单链表的结点定义,coef,exp,next,-1,A,7 0,3 1,9 8,5 17 ,-1,B,8 1,22 7,-9 8 ,-1,C,7 0,11 1,22 7,5 17 ,一元多项式相加,typedef,struct,node,int,coef,exp,;,struct,node *next;,JD;,设,p,q,分别指向,A,B,中某一结点，,p,q,初值是第一结点,比较,p-exp,与,q-exp,p-exp exp : p,结点是结果多项式中的一,项，,p,后移,q,不动,p-exp q-exp : q,结点是结果多项式中的一项，,将,q,插在,p,之前,q,后移,p,不动,p-exp = q-exp :,系数相加,0,：从,A,表中删去,p,释放,p,q,，,p,q,后移,0,：修改,p,系数域,释放,q,，,p,q,后移,直到,p,或,q,为,NULL,若,q=NULL,，,结束,若,p=NULL,，,将,B,中剩余部分连到,A,上即可,运算规则,q,-1,pa,7 0,3 1,9 8,5 17 ,-1,pb,8 1,22 7,-9 8 ,p,pre,q,-1,pa,7 0,11,1,9 8,5 17 ,-1,pb,8 1,22 7,-9 8 ,p,pre,-1,pa,7 0,11,1,22 7,5 17 ,算法描述,void add_poly(JD *pa,JD *,pb,), JD *p,*q,*u,*pre;,int,x;,p = pa-next;,q =,pb,-next;,pre = pa;,while( p ! = NULL ) & ( q ! = NULL ), if ( p-exp exp ), pre = p; p = p-next; ,else if ( p-exp = q-exp ), x = p-,coef,+ q-,coef,;,if ( x ! = 0 ) p-,coef,= x; pre = p; ,else pre-next = p-next;,free(p); ,p = pre-next;,u=q;,q=q-next;,free(u);,else, u=q-next;,q-next=p;,pre-next=q;,pre=q; q=u;,if ( q ! = NULL),pre-next=q;,free(pb,);,线性表的应用举例,约瑟夫,（,Joseph,）,问题,编号为,1,，,2,，,，,n,的,n,个人按顺时针方向围坐在一张圆桌旁，每个人手中持有一个密码（正整数）。首先输入一个正整数作为报数上限值,m,，,然后，从第一个人开始按顺时针方向自,1,开始顺序报数，报到,m,的人离开桌旁，并将他手中的密码作为新的,m,值，从顺时针方向的下一个就坐在桌旁的人人开始重新从,1,报数，如此下去，直至所有人全部离开桌旁为止。,假设有,7,个人，编号从,1,到,7,，他们手中的密码分别是,3,，,1,，,7,，,2,，,4,，,8,，,4,，最初的,m=2,，,通过报数，这,7,个人离开桌旁的顺序应该是：,2,，,3,，,5,，,4,，,7,，,6,，,1,。,数据结构的分析：,这个问题的主角是,n,个人，每个人需要描述的信息有：编号、密码和是否在桌旁的状态。假设有,7,个人，他们的信息可以表示成下面的形式。,算法描述：,让,n,个人围坐在一张圆桌旁；,for (i=1;i=n;i+),从,1,开始报数，报到,m,停止；,报到,m,的人离开桌子；,# define LIST_MAX_LENGTH 7,# define n LIST_MAX_LENGTH,typedef,int,EntryType,;,/,将,EntryType,定义为,int,类型,void,Joseph(int,code ,int,n),顺序存储结构：,最终的算法实现,/,通过一维数组,code,带入,n,个人手中的密码，,n,是开始就坐在桌旁的人数,SQ_LIST people;,int,temp,m; /m,是报数的上限值,scanf(“%d”,&m,); /,输入最初的,m,if (,InitList(&people,)=ERROR) exit ERROR;,for (i=1;i=n;i+),if (ListInsert(,position=0; /,记录当前报数人的编号,count=0; /,记录当前所报的数目,for (i=1;i0) count+;,while (count!=m);,printf(“%d”,position,);,/,输出当前离开桌旁人的编号,GetElem(people,position,&m,);,people. tempposition-1 = -people.tempposition-1;,/,将密码变为负值,链式存储结构：,使用一个不带头结点的循环单链表结构。结点结构为：,图,2-10,No code next,用,C,语言定义,typedef,struct,/,循环链表中每个结点的数据域部分的类型,int,No; /,编号,int,code; /,密码,INFO;,typedef,INFO,EntryType,;,算法,void,Joseph(int,code,int,n) ,LINK_LIST people;,NODE *position,*pre;,/position,指向当前报数的结点,if (,InitList(&people,)=ERROR) exit ERROR;,/,初始化链表,people,for (i=1;inext!=people.head),position=,NextElem(people,position,);,scanf(“%d”,&m,); /,输入最初的,m,for (i=1;iitem.No); /,离开桌子处理,m=position-item.code;,pre=,PriorElem(people,position,);,pre-next=position-next;,free(position);,position= pre;,printf(“%d”,position,-item.No); /,处理最后一个人,free(position);,重点：,线性表的顺序存储；,线性表的链式存储；,顺序表的插入、删除,单链表的插入、删除,难点：,双向链表的系列操作,线性表的应用。,