第3章线性表-2.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第,页,*,第,3,章 线性表,3.2,线性表的顺序存储,3.2.1,顺序存储,最常用的方法是顺序存储。顺序存储结构是把线性表的各个数据元素依次存储在一组连续的内存存储单元中。,第,页,由于线性表的所有数据元素属于同一类型，因此每个元素在存储器中占用的空间大小相同，假设向量的第一个元素存放的地址为,LOC(a,1,),，,每个元素占用的空间大小为,L,个字节，则元素,a,i,的存放地址为：,LOC(a,i,),LOC(a,1,),L*(i,1),第,页,线性表的这种机内表示称做线性表的顺序存储结构。,该种数据结构中数据的逻辑关系是以元素在计算机内存储器的存储位置相邻来表示的。,A1,A2,A3,Ai,an,存储地址 数据元素 位序 数组下标 位序,Loc(a1),Loc(a1)+L,Loc(a1)+2*L,Loc(a1)+(i-1)*L,Loc(a1)+(n-1)*L,1,2,3,.,.,i,.,n,0,1,3,.,.,i-1,.,n-1,A1,A2,A3,Ai,an,1,2,3,.,.,i,.,n,第,页,只要确定了存储线性表的起始位置，线性表中任一数据元素都可随机存取，所以线性表的顺序存储结构是一种随机存取结构。,在高级语言环境中常用一维数组来表示向量。为更好体现信息隐蔽原则以及数据抽象原则，在这里把数组,Elem,和线性表的长度,Length,封装在一个结构体中。,第,页,3.2.2,顺序结构线性表的运算,存储结构如下：,#define,list_maxsize,100,typedef,struct,int,datalist_maxsize,；,/*,数组*,/,int,length,；,/*,表长*,/,SqList,；,/*,结构体类型名*,/,第,页,1.,顺序表的初始化,算法,3-2,顺序表的初始化,void,InitList(SqList,*L),L.length,=0;,2.,求顺序表的表长,算法,3-3,求顺序表的表长,int,ListLength,（,SqList,*L),reture,L.length,;,第,页,3.,取顺序表第,i,个结点,算法,3-4,求顺序表的第,i,个结点。,datatype,GetElem,（,SqList,*L,，,int,i),if(i,L.length,),Error(“position,error!”);,retrun,L.datai-1;,第,页,4.,顺序表的结点查询,算法,3-5,顺序表的结点查询,int,Search,（,SqList,*L,，,int,x,，,int,n),for(i=0;i=,q;-p,),*(p+1)=p;/*,后移元素*,/,第,页,*,q=e;/*,插入*,/,+,L.length,/*,线性表长度加,1*/,return OK,；,该算法的平均时间复杂度为：,T(n,)=,O(n,),第,页,1,3,2,5,3,3,4,7,5,9,6,12,7,23,8,14,9,1,3,2,5,3,3,4,7,5,9,6,10,7,12,8,23,9,14,序号 数据元素 序号 数据元素,(a),插入前,n=8 (b),插入后,n=9,插入,10,i=6,1,2,3,移动顺序,第,页,6.,删除,要删除线性表中的第,i,个元素,a,i,，,操作和插入操作类似。,把元素,a,i+1,，,，,a,n,分别向前移动一个位置。对于长度为,n,的线性表,(a,0,，,，,a,i-1,，,a,i,，,，,a,n-1,),，,变成长度为,n-1,的线性表,(a,0,，,，,a,i-1,，,a,i+1,，,，,a,n-2,),。,在程序中最后还要将线性表长度减,1,。删除算法如下。,第,页,算法,3-7,void,delete_Sq(Sqlist,*,L,int,i,，,int,&e),if(i,L.length+1)return ERROR;,p=,/*,被删除元素的前一个的地址*,/,e=*p;/*,被删除的元素存入变量,e,中*,/,q=,for(+p;p,next=NULL;,头结点 表结点,首元素,尾元素,第,页,一个结点的存储结构定义为,typedef,int,datatype,；,typedef,struct,Lnode,datatype,data;/*,数据域*,/,struct,Lnode,*next;/*,指针域*,/,LinkList,第,页,假设,h,，,p,，,q,为指针变量，可用下列语句来说明：,LinkList,*h,*p,*q;,变量,h,，,p,，,q,被定义为指针类型之后，一个指针变量占用个字节，准备存放地址值。此时每个指针变量的内容并未确定，并没有指向任何实际结点，即,h,变量中没有任何某实际结点所占空间的首地址值。,第,页,若将,h,置为空，需用语句：,h=NULL;,若让,h,指向一个新分配的结点，则用如下语句：,h=(,Lnode,*),malloc(sizeof(Lnode,);,该语句的作用是动态分配一个结点所需的若干个字节，将首地址存入指针变量,h,之中,该结点也称,h,结点。,第,页,结点,h,的数据域用,h-data,来表示，它的指针域用,h-next,来表示，下列为结点各个子域赋值的语句：,p-data=12;,p-next=NULL;,第,页,通过指针赋值语句：,p=h,，,可以使指针变量,p,获得一个已经存在的结点的地址。这表明,h,，,p,之中存放的是同一个结点的首地址。也称指针,h,，,p,指向同一个结点。,如图,2.1(b),所示。,(a),指针变量,h,；,(b)h,所指的结点,h,(a),12,p,h,(b),第,页,如果要把结点所占用的存储空间归还给系统，则用函数,free(h,),来释放参数指定的结点占用的地址空间。,如用函数,free(h,),或,free(p),来实现释放参数指定的结点,h,和,p,指出结点所占用的地址空间。,指针变量所指向的结点则根据数据元素的结构不同占用存储单元数不同，一般一个结点占用多个地址单元。,第,页,语句 执行前 执行后,q=p,p,p,q,q=p-next,p,p,q,指针变量的主要操作,指针变量的主要操作示意图,第,页,语句 执行前 执行后,p-next=q,p,p,q,q,P-next=q-next,p,q,p,q,指针变量的主要操作示意图,第,页,建立一个带头结点的单链表,算法,3-8,带头结点的单链表初始化,Initlist(LinkList,*L),L=(,LinkList,*),malloc(sizeof(Lnode,);,L-next=NULL;,第,页,法,3-9,建立带头结点的单链表,(,头插入）,Create_L(LinkList,*,L,int,n),LinkList,*,p;int,i;,Initlist(L,);,for(i,=,n;i,0;i-),p=(,LinkList,*),malloc(sizeof(Lnode,);,scanf(&p,-data);,p-next=L-next;,L-next=p;,第,页,an,an-1,a1,L,a1,L,初始（,Initlist,(),）,插入第一个,p,语句：,p-next=L-next,语句：,L-next=p,a1,L,结果：,第,页,a2,插入第二个,p,语句：,p-next=L-next,语句：,L-next=p,a2,L,结果：,a1,L,a1,第,页,3.3.2,线性链表的运算,1.,单链表的查找操作,(1),可以按位置查找某元素；,(2),也可以按值查找位置；,第,页,(1),按位置查找某元素；,算法,3-10,在带头结点的单链表中查找第,i,元素。,若存在，则返回其值；,否则返回“不存在！”,第,页,VisitElem_L(LinkList,*,L,int,i,datatype,&e),LinkList,*,p,int,j;,p=L-,next;j,=0;,while(p,!=,NULL)&(j,next;+j;,if(p,=,NULL)|j,i)return ERROR;,e=p-data;,return OK;,第,页,(2),按值查找某元素位置；,算法,3-11,在带头结点的单链表中查找其值,=,给定的值的元素的位置。,若存在，则返回其位置；,否则返回,NULL,第,页,Lnode,*,Locate(LinkList,*,head,datatype,key),Lnode,*p=head-next;,while(p&(p,-data!=key),p=p-next;,if(p,=NULL)return ERROR;,return p;,第,页,2.,单链表的插入操作,在单链表中插入一个结点有如下三种情况：,(1),将结点插入在链表的第一个结点位置；,(2),将结点插入在链表任意两个结点之间；,(3),将结点插入在链表的第一个结点位置。,第,页,插入第一个结点之前，操作示意图：,x,s,h,a,b,h,a,b,x,s,语句：,s-next=h-,next;h,-next=s;,注：两个语句的顺序不可互换！,第,页,插入在两个结点中间操作示意图：,a,b,x,s,a,b,x,s,语句：,s-next=p-,next;p,-next=s;,注：两个语句的顺序不可互换！,p,第,页,插入在最后操作示意图,a,b,x,s,a,b,x,s,NULL,NULL,p,语句：,s-next=p-,next;p,-next=s;,注：两个语句的顺序不可互换！,第,页,在单链表中插入一个结点有如下三种方法：,(1),根据指针将结点插入在链表中；,(2),根据值将结点插入在链表中。,(3),根据位序号将结点插入在链表中；,第,页,(1),根据指针将结点插入在链表中,根据指针将结点插入在链表中，又可以分为两种方法：,a.,在指针指出结点的后边进行插入；,b.,已指针指出结点的前边进行插入。,第,页,a.,在指针指出结点的后边进行插入,指针,p,指出某一结点，新结点,s,插入在,p,指出结点之后。,head,x,s,p,第,页,操作较为简单，不用查找便可直接插入。相关操作的语句组如下：,s=(,Lnode,*),malloc(sizeof(Lnode,);,s-data=x;,s-next=p-next;,p-next=s;,第,页,b.,在,P,指针所指向的结点前插入一个结点其数据元素值,=,，操作示意图：,head,x,s,q,p,第,页,先设一指针,q,从头结点开始向后移动进行查找，直到,q,指向,p,的前趋结点为止。,然后在,q,指针所指结点之后，,p,指针所指结点之前进行插入。,在已知结点的前边进行插入，操作较为复杂，需先查找然后插入。,第,页,有关操作的语句组如下：,q=head;,while(q,-next!=p)q=q-next;,/*,通过循环查找,p,的前驱结点*,/,s=(,Lnode,*),malloc,(,sizeof(Lnode,);,s-data=x;,s-next=p;,q-next=s;,第,页,(2),在线性表中值为,x,的元素前插入一个值为,y,的数据元素。如果值为,x,的结点不存在，则将,y,插在表尾。如图,2.6,所示。,head,a,i,x,y,s,a,n,q,p,第,页,算法思想：,这里已知条件应该是链表的头指针,h,和,x,、,y,。,先设一指针,p,从头结点,h,的下一个结点开始向后查找值为,x,的结点，同时还需用另一个指针,q,从头结点开始紧跟在指针,p,后面。,第,页,当指针,p,到位时,(p,指向值为,x,的结点,),，,q,正好指向它的前趋结点，然后在,q,与,p,结点之间插入。也即在,q,所指向的结点之后进行插入。,具体算法如下,:,第,页,void,Insert(Lnode,*,head,dataty,x,dataty,y),s=(,Lnode,*),malloc,(,sizeof(Lnode,);,s-data=y;,q=head;,p=q-next;,while(p!=NULL)&(p-data!=x),q=p,；,p=p-next;,s-next=p;q-next=s;,第,页,(3),在链表的第,i,个元素结点处插入,算法思想：,与前一插入算法比较，已知条件除了头指针,head,和即将插入的,y,之外，另一个已知条件不再是某个结点的值域而是结点的序号,i,。,第,页,这样一来不仅需先设一指针,p,从头结点开始，而且同时设置一个记数变量,k,从零开始，,p,每向前移动一次，,k,便加,1,，循环到,k,等于,i-1,为止。,当指针,p,到位时,(p,指向序号为,i-1,的结点,),，正好指向,i,号结点的前趋结点，然后在,p,所指向的结点之后进行插入。本题目实质上就是在第,i-1,个元素结点后插入。,第,页,算法,3-12,在第,i,结点前插入,Insert_Li(LinkList,*,L,int,i,datatype,e),LinkList,*p,*s;,int,j;,s=(,LinkList,*),malloc(sizeof(Lnode,);,s-data=e;,s-next=NULL;,p=L;,j=0;,第,页,while(p,!=,NULL&j,next;,+j;,if(!p|j,i-1)return ERROR;,s-next=p-next;,p-next=s;,return OK;,第,页,算法,3-13,在第,i,结点后插入,Insert_Li(LinkList,*,L,int,i,datatype,e),LinkList,*p,*s;,int,j;,s=(,LinkList,*),malloc(sizeof(Lnode,);,s-data=e;,s-next=NULL;,p=L;,j=0;,第,页,while(p,!=,NULL&j,next;,+j;,if(!p|j,i)return ERROR;,s-next=p-next;,p-next=s;,return OK;,第,页,