c语言数据结构第二章课件清华出版社.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 线性表,复习：,1,、抽象数据类型的定义由哪几部分组成？,2,、按数据元素之间的逻辑关系不同，数据结构有哪几类？,本章学习内容,线性表,顺序表,链表,2.1,线性表,线性表是一种最简单的线性结构。,什么是线性结构？,简单地说，,线性结构是一个数据元素的有序（次序）集合。它有,四个基本特征,：,1,集合中必存在唯一的一个,第一元素,；,2,集合中必存在唯一的一个,最后元素,；,3,除最后元素之外，其它数据元素均有唯一的,后继,；,4,除第一元素之外，其它数据元素均有唯一的,前驱,。,2.1.1,抽象数据类型线性表的定义,通常可以下列,“,n,个数据元素的序列,”,表示,线性表,(,Linear_List,),(a,1,a,2,.,a,i,.,a,n,),序列中数据元素的个数,n,定义为线性表的表长；,n=0,时的线性表被称为空表。称,i,为 在线性表中的位序。,线性表中的数据元素可以是各种各样的，只要是属于同一个集合即可。例如，,26,个小写英文字母是一个线性表,(,a,b,z),同一花色的,13,张扑克牌,(2,3,4,5,6,7,8,9,10,J,Q,K,A),可以构成一个线性表。,其抽象数据类型的定义如下：,ADT List,数据对象：,D,a,i,|,a,i,ElemSet,i=1,2,.,n,n0,数据关系：,R1,|ai-1,ai,D,i=2,.,n,序偶,表示,ai-1,是,ai,的直接前驱，反之，,ai,是,ai-1,的直接后继。,基本操作：,（共四大类）,结构初始化,InitList,(,&,L),操作结果：构造一个空的线性表,L,。任何数据结构在被使用之前都必须进行,“,初始化,”,，它类似于编程中使用的变量都必须先有定义。,销毁结构,DestroyList,(,&,L),初始条件：线性表,L,已存在。操作结果：销毁线性表,L,。,任何数据结构不再使用时都必须进行,结构销毁,，其实质为,释放,它所占有的存储空间。,引用型操作,ListEmpty,(L),/,判定线性表是否为空表。,初始条件：线性表,L,已存在。操作结果：若,L,为空表，则返回,TRUE,，否则返回,FALSE,。,ListLength,(L),/,求得线性表的长度，即线性表中所含数据元素的个数。,初始条件：线性表,L,已存在。操作结果：返回,L,中元素个数。,PriorElem,(L,cur_e,&,pre_e,),初始条件：线性表,L,已存在。操作结果：若,cur_e,是,L,中的数据元素，则用,pre_e,返回它的前驱，否则操作失败，,pre_e,无定义。若,cur_e,是线性表,L,中第一个数据元素，则它的前驱,pre_e,为,“,空元素,”,。,NextElem,(L,cur_e,&,next_e,),初始条件：线性表,L,已存在。操作结果：若,cur_e,是,L,中的数据元素，则用,next_e,返回它的后继，否则操作失败，,next_e,无定义。若,cur_e,是线性表,L,中最后一个数据元素，则它的后继,next_e,为,“,空元素,”,。,GetElem,(L,i,&,e),初始条件：线性表,L,已存在，,1iLengthList(L),。操作结果：用,e,返回,L,中第,i,个元素的值。此操作的结果是求得线性表,L,中和位序,i,相对应的数据元素，因此，只有当,i,的值在线性表的长度范围内才有意义。,LocateElem,(L,e,compare(),初始条件：线性表,L,已存在，,compare(),是元素判定函数。操作结果：返回,L,中第,1,个与,e,满足关系,compare(),的元素的位序。若这样的元素不存在，则返回值为,0,。,ListTraverse(L,visit(),初始条件：线性表,L,已存在，,visit(),为元素的访问函数。操作结果：依次对,L,的每个元素调用函数,visit(),。一旦,visit(),失败，则操作失败。,以上,7,个操作的结果都没有改变线性表中的数据元素和数据元素之间的关系，因此它们都是,“,引用型,”,的操作。,加工型操作,ClearList,(&L),初始条件：线性表,L,已存在。操作结果：将,L,重置为空表。,值得注意,的是，在进行了,DestroyList(L,),操作之后，线性表,L,不再存在，即不能在以后的程序中再引用它，而在对线性表,L,进行,ClearList(L,),操作之后，仅是删除表中所有元素，在以后的程序中仍可对它进行某些,“,合法,”,操作，如判空、插入等。,PutElem,(&L,i,&e),初始条件：线性表,L,已存在，,1iLengthList(L),。操作结果：,L,中第,i,个元素赋值同,e,的值。,和,GetElem,操作相同，,i,的值必须在线性表的长度范围内。,ListInsert,(&L,i,e),初始条件：线性表,L,已存在，,1iLengthList(L)+1,。操作结果：在,L,的第,i,个元素之前插入新的元素,e,，,L,的长度增,1,。,可在线性表中任意一个元素之前插入一个新的数据元素，,i=1,意为在第一个元素之前插入一个新的数据元素，,i=LengthList(L)+1,则为在最后一个元素之后插入一个新的数据元素。换句话说，操作结果是使新插入的数据元素成为插入之后的线性表中第,i,个数据元素，显然，插入位置,i,的合法值应为,1iLengthList(L)+1,。,ListDelete,(&L,i,&e),初始条件：线性表,L,已存在且非空，,1iLengthList(L),。操作结果：删除,L,的第,i,个元素，并用,e,返回其值，,L,的长度减,1,。,ADT List,例,2-1,已知集合,A,和,B,，求两个集合的并集，使,A,AB,，且,B,不再单独存在。,从集合的观点看，此问题求解的方法很简单，只要对集合,B,中的所有元素一个一个地检查，看看在集合,A,中是否存在相同元素，若不存在，则将该元素插入到集合,A,，否则舍弃之。要在计算机中求解，首先要确定,如何表示集合,。集合可以有多种表示方法，对上述集合求并的问题可以用线性表表示集合。现假设以线性表,LA,和,LB,分别表示集合,A,和,B,，即构造两个线性表,LA,和,LB,，它们的数据元素分别为集合,A,和,B,中的成员。由此，上述集合求并的问题便可演绎为：要求对线性表作如下操作：扩大线性表,LA,，将,存在于线性表,LB,中,而,不存在于线性表,LA,中,的数据元素,插入到线性表,LA,中,去。具体操作步骤为：,1,从线性表,LB,中取出一个数据元素；,2,依值在线性表,LA,中进行查询；,3,若不存在，则将它插入到,LA,中。重复上述三步直至,LB,为空表止。,那么，其中的每一步能否利用上述线性表类型中定义的基本操作来完成呢？,上述的每一步恰好对应线性表的一个基本操作：,1.,ListDelete,(LB,1,e);,2.,LocateElem,(LA,e,equal();,3.,ListInsert,(LA,n+1,e),算法,2.1,void,union(List,&LA,List&LB),/,将所有在线性表,LB,中但不在,LA,中的数据元素插入到,LA,中,/,算法执行之后，线性表,LB,不再存在。,La_len,=,ListLength(LA,);,/,求得线性表,LA,的长度,while(!,ListEmpty(LB,)/,依次处理,LB,中元素直至,LB,为空表止,ListDelete(LB,1,e);,/,从,LB,中删除第,1,个数据元素并赋给,e,if(!,LocateElem(LA,e,equal,(),ListInsert(LA,+La_len,e,);,/,当,LA,中不存在和,e,值相同的数据元素时进行插入,/while,DestroyList(LB,);,/,销毁线性表,LB,/union,2.2,线性表的顺序存储表示和实现,2.2.1,顺序表,顺序表,是线性表的顺序存储表示的简称，它指的是，,用一组,地址连续,的存储单元,依次存放,线性表中的数据元素,，即以,存储位置相邻,表示,位序相继的两个数据元素之间的前驱和后继的关系,(,有序对,),，并以表中第一个元素的存储位置作为线性表的起始地址，称作,线性表的基地址,。如下图所示。,假设每个数据元素占据的存储量是一个常量,C,，则后继元素的存储地址和其前驱元素相隔一个常量，即：,LOC(ai,)=LOC(ai-1)+,C,一个数据元素所占存储量。,由此，所有数据元素的存储位置均可由第一个数据元素的存储位置得到,LOC(ai,)=LOC(a1)+(i-1)C,基地址,用,C,语言描述的,顺序表类型,如下所示：,/,存储结构,#define,MAXLISTSIZE 80 /,预设的存储空间最大容量,typedef,struct,ElemType,*,elem,;,/,存储空间基址,int,length;,/,当前长度,int,listsize,;,/,允许的最大存储容量,(,以,sizeof,(ElemType,),为单位,),SqList,;,/,俗称,顺序表,注意：,由于线性表的长度是可变的，因此对顺序表的定义除了需要一个存储元素的一维数组空间以外，还需要两个数据成员：其中一个指示顺序表中已有的元素个数，另一个指示该顺序表允许存放的数据元素个数的最大值，如下图所示。,ElemType,为元素类型。,/,基本操作接口,(,函数声明,),void,InitList,(,SqList,&,L,int,maxsize,);,/,构造一个最大存储容量为,maxsize,的空的顺序表,L,。,maxsize,由用户设定，其默认值为系统设定值,MAXLISTSIZE,。,void,DestroyList,(,SqList,&,L),/,销毁顺序表,L,。,bool,ListEmpty,(,SqList,L),/,若顺序表,L,为空表，则返回,TRUE,，否则返回,FALSE,。,int,ListLength,(,SqList,L),/,返回顺序表,L,中元素个数。,int,PriorElem,(,SqList,L,ElemType,cur_e,),/,若,cur_e,是顺序表,L,的元素，则返回其前驱的位序,/,(,设第一个元素的前驱的位序为,0),，否则返回,-1,。,int,NextElem,(,SqList,L,ElemType,cur_e,),/,若,cur_e,是顺序表,L,的元素，则返回其后继的位序,/(,设最后一个元素的后继的位序为,L,的表长,+1),，否则返回,-1,。,bool,GetElem,(,SqList,L,int,pos,ElemType,&,e),/,若,1posLengthList(L),，则用,e,带回顺序表,L,中第,pos,个元素,/,的值且返回函数值为,TRUE,，否则返回函数值为,FALSE,。,int,LocateElem,(,SqList,L,ElemType,e,bool,(*,compare)(ElemType,ElemType,),/,返回顺序表,L,中,第,1,个,与,e,满足,关系,compare(),的数据元素的位序。,/,若这样的元素不存在，则返回值为,0,。,compare(),为数据元素的判定函数。,void,ListTraverse,(,SqList,L,void,(*,visit)(ElemType,),/,依次,对顺序表,L,的每个元素调用函数,visit(),。,/,一旦,visit(),失败，则操作失败。,void,ClearList,(,SqList,&,L),/,将顺序表,L,重置为空表。,bool,PutElem,(,SqList,L,int,pos,ElemType,&,e),/,若,1posLengthList(L),，则对顺序表,L,中第,pos,个元素,/,赋值同,e,的值且返回函数值为,TRUE,，否则返回函数值为,FALSE,。,bool,ListInsert,(,SqList,&,L,int,pos,ElemType,e),/,若存储空间未满且,1posLengthList(L)+1,，则在顺序表,L,的,/,第,pos,个元素之前插入新的元素,e,，,L,的长度增,1,，且返回函数值为,TRUE,，,/,否则不改变顺序表且返回函数值为,FALSE,。,bool,ListDelete,(,SqList,&,L,int,pos,ElemType,&,e),/,若,1posLengthList(L),，则删除顺序表,L,的第,pos,个元素,e,，,/,L,的长度增,1,，且返回函数值为,TRUE,，否则不改变顺序表且返回函数值为,FALSE,。,2.2.2,顺序表中基本操作的实现,从顺序表的存储结构定义容易看出，由于顺序表的,长度,是个,显值,，且由于第,i,个元素恰好存储在数组的第,i,个分量,(,数组下标为,i-1),中，因此其,求长,、,判空,以及,存取第,i,个数据元素,等操作都很容易实现。下面重点讨论顺序表类型定义中五个操作的实现。一、初始化操作二、元素定位操作三、插入元素操作四、删除元素操作五、销毁结构操作,一、初始化操作,对顺序表而言，,“,初始化,”,的实质是为它分配一个,“,足够应用,”,的元素存储空间，由用户根据它对线性表的使用要求定义一个最大存储容量,maxsize,，并约定当用户没有提出特殊需求,(,maxsize,=0),时，按予设的最大存储量,MAXLISTSIZE,进行分配。由于顺序存储结构需,“,一次性,”,地分配一个存储空间，为便于调用环境按实际需要有效利用存储空间，故在顺序表的初始化函数中增设一个,“,最大存储容量,”,的参数。,算法,2.2,void,InitList(SqList,&,L,int,maxsize,),/,构造一个空的线性表,L,if,(,maxsize,=0),maxsize,=MAXLISTSIZE;,L.elem,=,(*,ElemType)malloc(sizeof(ElemType,)*,maxsize,);,if,(,!,L.elem,),exit,(1);,/,存储分配失败,L.length,=0;,/,顺序表的初始长度为,0,L.listsize,=,maxsize,;,/,该顺序表可以存储元素的最大容量,/,InitList,此算法的时间复杂度为,O,(1),。,二、元素定位操作,在顺序表中,查询,是否存在一个和给定值满足判定条件的元素的最简单的办法是，依次取出结构中的每个元素和给定值进行比较。,算法,2.3,int,LocateElem(SqList,L,ElemType,e,void,(*,compare)(ElemType,ElemType,),/,在顺序表,L,中查找第,1,个值与,e,满足判定条件,compare(),的元素，,/,若找到，则返回其在,L,中的位序，否则返回,0,。,i=1;,/i,的初值为第,1,元素的位序,p=,L.elem,;,/p,的初值为第,1,元素的存储位置,while,(i=,L.length,&!,(*compare)(*,p+,e,),+i;,/,依次进行判定,if,(i=,L.length,),return,i;,/,找到满足判定条件的数据元素为第,i,个元素,else,return,0;,/,该线性表中不存在满足判定的数据元素,/,LocateElem,此算法的时间复杂度为：,O,(,ListLength(L,),三、插入元素操作,首先分析，,“,插入元素,”,使线性表的逻辑结构发生什么变化？假设在线性表的第,i,个元素之前插入一个元素,e,，使得线性表,(a1,ai-1,ai,an),改变为,(a1,ai-1,e,ai,an),即：,(1),改变了表中元素之间的关系，使,改变为,和,(2),表长增,1,由于顺序表是以,存储位置相邻,表示,元素之间的前驱和后继关系,，则必须,移动元素,来体现,元素之间发生的,变化,”,。,算法,2.4,bool,ListInsert(SqList,&,L,int,pos,ElemType,e),/,若存储空间不满且,1posListlength(L)+1,，则在顺序表,L,的,/,第,pos,个元素之前插入新的元素,e,且返回,TRUE,，否则返回,FALSE,if,(pos L.length+1),return FALSE,;/,插入位置不合法,if,(,L.length,=,L.listsize,),return FALSE,;,/,当前存储空间已满，无法插入,for,(j=L.length-1;j=pos-1;-j),L.elemj+1=,L.elemj,;/,插入位置及之后的元素右移,L.elempos-1=e;,/,插入,e,+,L.length,;,/,表长增,1,return,TRUE,;,/,ListInsert,此算法的时间复杂度为：,O,(,ListLength(L,),四、删除元素操作,同样首先分析，,“,删除元素,”,使线性表的逻辑结构发生什么变化？假设删除线性表中第,i,个元素，使得线性表,(a1,ai-1,ai,ai+1,),改变为,(a1,ai-1,ai+1,),即：,(1),改变了表中元素之间的关系，使,和,改变为,(2),表长减,1,对顺序表而言，需要改变从第,i+1,个元素起到第,n,个元素的存储位置，即进行,从第,i+1,到第,n,个元素往前移动一个,位置,。,算法,2.5,bool,ListDelete(SqList,&,L,int,pos,ElemType,&,e),/,若,1posListlength(L),，则以,e,带回从顺序表,L,中删除的,/,第,pos,个元素且返回,TRUE,，否则返回,FALSE,if,(pos,L.length,),return FALSE,;,/,删除位置不合法,for,(j=pos;j,L.length,;+j),L.elemj-1=,L.elemj,;,/,被删除元素之后的元素左移,-,L.length,;,/,表长减,1,return TRUE,;,/,ListDelete,此算法的时间复杂度为：,O,(,ListLength(L,),五、销毁结构操作,和,“,初始化,”,操作分配空间相对应，销毁结构的实质是释放它所占的全部空间，以便使存储空间得到充分的利用。,算法,2.6,void,DestroyList,(,SqList,&,L),/,释放顺序表,L,所占存储空间,free(,L.elem,);,L.listsize,=0;,L.length,=0;,/,DestroyList_Sq,此算法的时间复杂度为：,O,(1),2.2.3,顺序表其它算法举例,例,2-2,试编写算法,比较,两个顺序表的大小。算法的基本思想为：若,A=B=,空表，则,A=B,；若,A=,空表，而,B,空表，或者两者均不为空表，且,A,的首元小于,B,的首元，则,AB,。若,aj,=,bj,，则,j,增,1,，之后继续比较后继元素；否则即可得出比较结果。显然，,j,的初值应为,0,，循环的条件是,j,不超出其中任何一个表的范围,。若在循环内不能得出比较结果，则循环结束时有三种可能出现的情况需要区分。,算法,2.7,int,compare(,SqList,A,SqList,B),/,若,AB,，则返回,1,j=0;,while,(j,A.length,&,j,B.length,),if,(,A.elemj,B.elemj,),return,(1);,else,j+;,if,(,A.length,=,B.length,),return,(0);,else if,(,A.length,data,表示,p,所指结点中的数据域，,p-next,表示,p,所指结点中的指针域，若非空，则指向其,“,后继,”,结点。,p-data,即为,(*,p).data,，类似地，,p-next,即为,(*,p).next,。,注意：,只有在,p“,有值,”,且,“,值不为空,”,的情况下，,p-data,和,p-next,才有意义。指针型变量只能作同类型的指针赋值与比较操作。并且，指针型变量的,“,值,”,除了由同类型的指针变量赋值得到外，都必须用,C,语言中的动态分配函数得到。例如，,p=,malloc(sizesofe(LNode,),或,p=,new,LNode,;,表示在运行时刻系统动态生成了一个,LNode,类型的结点，并令指针,p“,指向,”,该结点。反之，当指针,p,所指结点不再使用，可用,free(p),或,delete p;,释放此结点空间。,2.3.2,单链表中基本操作的实现,线性表的五个基本操作在链式存储结构中的实现。,一、初始化操作,根据上一节的约定，初始化建一个空的链表即为建立一个只有头结点的链表。,算法,2.8,void,InitList,(,SLink,&,L),/,创建一个带头结点的空链表,L,为指向头结点的指针,L=,new,LNode,;,if,(!L),exit,(1);,/,存储空间分配失败,L-next=,NULL,;,/,nitList,算法的时间复杂度为,O,(1),。,二、销毁结构操作,算法,2.9,void,DestroyList,(,SLink,&,L),/,销毁以,L,为头指针的单链表，释放链表中所有结点空间,while,(L),p=L;,L=L-next;,delete,p;,/while,L=,NULL,;,/,DestroyList,算法的时间复杂度为,O,(,Listlength(L,),。,三、存取元素操作,单链表是一种,“,顺序存取,”,的结构，即：为取第,i,元素，首先必须先找到第,i-1,个元素。因此不论,i,值为多少，都必须从头结点开始起,“,点数,”,，直数到第,i,个为止。头结点可看成是第,0,个结点。可见算法中应设一个指针变量,p,和一个整数变量,j,，并使,p,和,j,同步变化，始终保持指针,p,指向第,j,的结点的状态。,算法,2.10,bool,GetElem,(,SLink,L,int,pos,ElemType,&,e),/,若,1posLengthList(L),，则用,e,带回指针,L,指向头结点的单链表,/,中第,pos,个元素的值且返回函数值为,TRUE,否则返回函数值为,FALSE,p=L-next;j=1;,/,变量初始化，,p,指向第一个结点,while,(p,&,jnext;+j;,/while,if,(!p|jpos),return FALSE;,/,链表中不存在第,pos,个结点,e=p-data;,/,取到第,pos,个元素,return TRUE;,/,GetElem,算法的时间复杂度为,O,(,ListLength(L,),。,四、插入元素操作,前面已经分析过，在线性表中,插入,一个元素时，使元素之间的关系,改变为,和,。当用指针指示后继元素时，实现这种关系的改变就很容易了，只要修改相应指针即可。因为新的元素插入在线性表的第,i,个元素之前，使得,ai,不再是,ai-1,的后继，而是新的元素,e,的后继，因此需要修改元素,e,和元素,ai-1,所在结点的指针。由此，算法的基本思想就是，首先找到第,i-1,个结点，然后修改相应指针。,算法,2.11,bool,ListInsert,(,SLink,&,L,int,pos,ElemType,e),/,若,1posLengthList(L)+1,，则在指针,L,指向头结点的单链表,/,的第,pos,个元素之前插入新的元素,e,，且返回函数值为,TRUE,/,否则不进行插入且返回函数值为,FALSE,p=L;j=0;,while,(p,&,jnext;+j;,/while,if,(!p|j,pos-1),return FALSE;,/,参数不合法，,pos,小于,1,或者大于表长,+1,s=,new,LNode,;,if(!s)exit(1);,/,存储空间分配失败,s-data=e;,/,创建新元素的结点,s-next=p-next;p-next=s;/,修改指针,return TRUE;,/,ListInsert,算法时间复杂度为,O,(,ListLength(L,),。,五、删除元素操作,和插入类似，由于删除元素,ai,改变了元素之间的关系，使,ai+1,不再是,ai,的后继，而是,ai-1,的后继，因此需要修改,ai-1,元素所在结点的指针。因此在单链表中删除元素操作的算法基本思想和插入相同，也是：首先找到第,i-1,个结点，然后修改相应指针。,算法,2.12,bool,ListDelete,(,SLink,&,L,int,pos,ElemType,&,e),/,若,1posLengthList(L),，则删除指针,L,指向头结点的单链表,/,中第,pos,个元素并以,e,带回其值，返回函数值为,TRUE,，,/,否则不进行删除操作且返回函数值为,FALSE,p=L;j=0;,while,(p-next,&,j next;+j;,if,(,!,(p-next)|j i-1),return FALSE;,/,删除位置不合理,q=p-next;p-next=q-next;,/,修改指针,e=q-data;,delete,(q,);,/,释放结点空间,return TRUE;,/,ListDelete_L,2.3.3,单链表举例,例,2-3,逆序创建链表假设线性表,(a1,a2,，,an),的数据元素存储在一维数组,An,中，则从数组的最后一个分量起，依次生成结点，并逐个插入到一个初始为,“,空,”,的链表中。,线性表,(,b,b,c,d,e,),的逆序创建的过程。,算法,2.13,void,CreateList_L(SLink,&,L,int,n,ElemType,A),/,已知数组,A,中存有线性表的,n,个数据元素，,/,逆序建立带头结点的单链表。,L=,new,LNode,;,if(!L)exit(1);,/,存储空间分配失败,L-next=NULL;,/,先建立一个带头结点的空的单链表,for,(i=n;i 0;-i),p=,new,LNode,;,if(!p)exit(1);,/,存储空间分配失败,p-data=Ai-1;,/,赋元素值,p-next=L-next;L-next=p;/,插入在头结点之后,/for,/,CreateList_L,链式存储结构的优势在于：,(1),能有效利用存储空间；因为它是动态存储分配的结构，不需要预先为线性表分配足够大的空间，而是向系统,“,随用随取,”,，并且在删除元素时可同时释放空间。,(2),用,“,指针,”,指示数据元素之间的后继关系，便于进行,“,插入,”,、,“,删除,”,等操作；插入或删除时只需要修改指针，而不需要进行大量元素的移动。,而其劣势则是不能随机存取数据元素。同时，它还丢失了一些顺序表有的长处，如线性表的,表长,和数据元素在线性表中的,位序,，在上述的单链表中都看不见了。又如，不便于在表尾插入元素，需遍历整个表才能找到插入的位置。表长和位序是线性表中两个重要属性，在本节设置的单链表中表长是一个隐含值，必须从前到后遍历整个表才能得到。为了更突出链表的优势，需改进单链表结构的定义。除了保留指向头结点的指针外，还应增设,尾指针,和,表长,两个属性。,2.3.4,循环链表,循环链表,(Circular Linked List),是线性表的另一种形式的链式存储表示。它的特点是表中最后一个结点的指针域指向头结点，整个链表成为一个由链指针相链接的环，并且将头指针设成指向最后一个结点。空的循环链表由只含一个自成循环的头结点表示。,循环链表的操作和单链表基本一致，差别仅在于，判别链表中最后一个结点的条件不再是,后继是否为空,，而是,后继是否为头结点,。,2.3.5,双向链表,顾名思义，,双向链表,(Double Linked List),的特点是其结点结构中含有两个指针域，其一指向数据元素的,直接后继,，另一指向数据元素的,直接前驱,，用,C,语言描述如下：,typedef,struct,DuLNode,ElemType,data;,struct,DuLNode,*prior;,struct,DuLNode,*next;,DuLNode,*,DuLink,;,很明显，在双向链表中不仅能直接找到结点的前驱，也能即刻找到结点的后继。,假设指针,p,指向双向链表中某个结点，则,p-prior-next=p,p-next-prior=p,与单链表类似，双向链表也是由指向头结点的头指针唯一确定，若将头尾结点链接起来则构成双向循环链表。空的双向循环链表则由只含一个自成双环的头结点表示。,算法,2.14,void,ListInsert_DuL(DuLink,&,L,DuLNode,*p,DuLNode,*s),/,在带头结点的双向循环链表,L,中结点*,p,之后插入结点*,s,s-next=p-next;p-next=s;,s-next-prior=s;s-prior=p;,/,ListInsert_DuL,2.3.6,静态链表,结构体数组,P31,小结,这一章我们向大家介绍了线性表的抽象数据类型的定义以及它的两种存储结构的实现。线性表是,n(n0),个数据元素的序列，通常写成,(a1,a2,an),因此线性表中除了第一个和最后一个元素之外都只有一个前驱和一个后继。线性表中每个元素都有自己确定的位置，即,“,位序,”,，因此线性表也可以看成是由,n,个,(,i,ai,),构成的集合。,n=0,时的线性表称为,“,空表,”,，它是线性表的一种特殊状态，因此在写线性表的操作算法时一定要考虑你的算法对空表的情况是否也正确。顺序表是线性表的顺序存储结构的一种别称。它的特点是以,“,存储位置相邻,”,表示两个元素之间的前驱后继关系。因此，顺序表的优点是可以随机存取表中任意一个元素，其缺点是每作一次插入或删除操作时，必须移动表中大量元素。常应用于主要是为查询而很少作插入和删除操作，表长变化不大的线性表。链表是线性表的链式存储结构的别称。它的特点是以,指针,指示后继元素，因此线性表的元素可以存储在存储器中任意一组存储单元中。它的优点是便于进行插入和删除操作，但不能进行随机存取，每个元素的存储位置都存放在其前驱元素的指针域中，为取得表中任意一个数据元素都必须从第一个数据元素起查询。由于它是一种动态分配的结构，结点的存储空间可以随用随取，并在删除结点时随时释放，以便系统资源更有效地被利用。这对编制大型软件非常重要，作为一个程序员在编制程序时必须养成这种习惯。,