数据与结构算法中对线性表的理解.ppt

线性表顺序表 链表顺序表与链表的比较,第二章 线性表,线性表(Linear List),线性表的定义和特点 定义 n（0）个数据元素的有限序列，记作（a1,a2,an）ai 是表中数据元素，n 是表长,n=0时为空表 遍历 逐项访问：从前向后 从后向前,线性表的特点,除第一个元素外，其他每一个元素有且仅有一个直接前驱除最后一个元素外，其他每一个元素有且仅有一个直接后继,a1,a2,a3,a4,a5,线性表的初始化 Init_List(L)求线性表的长度 Length_List(L)取表元 Get_List(L,i)按值查找 Locate_List(L,x)插入操作 Insert_List(L,i,x)删除操作 Delete_List(L,i),线性表的基本操作,顺序表(Sequential List),顺序表的定义和特点 定义 将线性表中的元素相继存放在一个连续的存储空间中。可利用一维数组描述存储结构 特点 逻辑顺序与物理顺序一致 访问 顺序存取,随机存取,25 34 57 16 48 09,0 1 2 3 4 5,data,顺序表的连续存储方式,35 27 49 18 60 54 77 83 41 02,1 2 3 4 5 6 7 8 9 10,l l l l l l l l l l,Loc(ai)=Loc(a1)+(i1)*l 1in,a,顺序表(SeqList)的定义,#define Maxsize 100/最大允许长度typedef int datetype;typedef struct datatype dataMaxsize;/存储数组 int last;/当前元素个数 SeqList;SeqList*L;(或SeqList L;),顺序表基本运算的实现,顺序表的初始化 SeqList*inti_Seqlist()SeqList*L;L=(SeqList*)malloc(sizeof(SeqList);Llast=-1;return L;,求表的长度 int Length(SeqList*L)return Llast+1;取表元：在表中提取第 i 个元素的值 datatype GetData(SeqList*L,int i)if(i=1,按值查找：在顺序表中查找结点值等于给定值 x 的结点,动画演示,i=Llast,按值查找动画演示,25 34 57 16 48 09,0 1 2 3 4 5,data,查找 16,i,0 1 2 3 4 5,查找成功，返回i的值,查找 50,25 34 57 16 48 09,0 1 2 3 4 5,data,i,0 1 2 3 4 5,查找失败，返回1,查找成功的平均比较次数 若查找概率相等，则：查找不成功，数据比较 n 次,O(n),25 34 57 16 48 09 63,0 1 2 3 4 5 6 7,data,25 34 57,0 1 2 3 4 5 6 7,data,50,i=4,例:在第个位置(i=4)插入一个值为50的新元素,插入运算：在顺序表的第 i(1i n+1)个位置插入一个值为 x 的新元素,63,09,48,16,i与Llast的关系？,int Insert(SeqList*L,datatype x,int i)/在表中第 i 个位置插入新元素 x if(i)return 0;if(Llast=Maxsize-1)return-1;/参数不合理或表已满，插入不成功 for(j=Llast;j=;j-)Ldataj+1=Ldataj;=x;Llast+;return 1;/插入成功,Llast+2,i-1,Ldatai-1,算法分析：,在顺序表上做插入操作需要移动表中一半的元素,时间复杂度为(n),16,25 34 57 16 48 09 63,0 1 2 3 4 5 6 7,data,25 34 57,0 1 2 3 4 5 6 7,data,i=4,例:将表中第个位置(i=4)上的元素删除,删除运算：将顺序表中的第 i(1i n)个元素从表中删除,63,09,48,i与Llast的关系？,int Delete(SeqList*L,datatype x)/删除表中第 i 个位置上的元素 if(i Llast+1)return 0;for(;j=Llast;j+)Ldataj-1=Ldataj;Llast-；return 1;/删除成功,j=i,算法分析：,在顺序表上做删除操作大约需要移动表中一半的元素,时间复杂度为(n),例题,顺序表应用举例,例1将顺序(a1,a2,.,an)表重新排列为以a1为界的两部分，a1前面的值均比a1小，a1后面的值都比a1大,i=,x,25,30,20,60,10,35,15,y,25,if(L-dataix)i+;,if(L-dataix),顺序表应用举例,例1将顺序表重新排列为以a1为界的两部分，a1前面的值均比a1小，a1后面的值都比a1大 算法思想：依次取原链表中的每个结点，将其做为第一个结点插入到新链表中。,算法实现见书P29,顺序表溢出的处理,顺序表的问题在于：如果其空间大小已经分配，一旦空间占满，再加入新元素将产生溢出。已知顺序表的大小为 ListSize,其定义和分配如下：datatype*elem=new datatypeListSize;现已产生溢出，处理溢出的方法为：,const int NewSize=100;datatype*newArray=new datatypeNewSize;if(newArray=NULL)cout“存储分配错!n”);exit(1);int n=NewSize;datatype*srcptr=elem;datatype*destptr=newArray;while(n-)*destptr+=*srcptr+;delete elem;elem=newArray;,链表（Linked List）,链表是线性表的链接存储表示单链表静态链表 循环链表双向链表,单链表,每个结点由数据域(data)和指针域(next)构成 线性表（a1,a2,an）通过每个结点的指针域指向下一个结点，形成单链表：结点可以连续存储也可以不连续存储，使得结点的逻辑顺序与物理顺序可以不一致,单链表的存储映像,free,(a)可利用的存储空间,free,head,(b)经过一段运行后的单链表结构,单链表的定义,typedef char datatype;typedef struct node/单链表结点 datatype data;struct node*next;LNode;typedef LNode*LinkList;LinkList head;/链表头指针,空链表的表示：头指针的值为NULL,head,s,x,思考：s-next=？如何利用next指针在空 表的基础上建立一非空的单链表？,申请结点空间：LNode*s;s=(LNode)malloc(sizeof(LNode);s-data=x;,LinkList head=NULL;,前插法 建立单链表,从一个空表开始，重复读入数据：用malloc函数生成新结点读入的数据存放到新结点的data域中将该新结点插入到链表的最前端直到读入的数据等于结束符flag为止。,动画演示,s,25,head,flag值为-1,x=25,s,s,x=45,x=18,45,18,x=-1,2条重要的指针赋值语句：,s-next=head;,head=s;,前插法 建立单链表的动画演示,LinkList CreateListL()int x;ListNode head=NULL;LNode*s;scanf(“%d”,s-next=head;,head=s;,后插法 建立单链表,从一个空表开始，重复读入数据：用malloc函数生成新结点读入的数据存放到新结点的data域中将该新结点插入到链表的最后端直到读入的数据等于结束符flag为止。,动画演示,关键：引入尾指针r,总是指向表中尾结点,head,s,x=25,s,s,x=45,x=18,25,45,18,x=-1,r,flag值为-1,后插法 建立单链表的动画演示,对于空表与非空表，后插结点的操作是否一致？,思考：,后插法 建立单链表的两种情况：,x,s,head,x,s,r,r,NULL,r-next=s;,head=s;,空 表：,非空表：,if(head=NULL)else,r=s;,r=s;,LinkList CreateListR()LinkList head=NULL;LNode*s,*r=NULL;int x;scanf(“%d”,r=s;,r!=NULL,前插法与后插法比较前插法：不用辅助存储变量，简单；空表与非空表的操作一致后插法：需要辅助存储变量；空表与非空表的操作不一致为使空表与非空表的操作一致，可在链表的头部加入“头结点”,带头结点的单链表,头结点位于表的最前端，本身不带数据,仅标志表头，可用malloc语句申请头结点空间设置头结点的目的：统一空表与非空表的操作，简化链表操作,空表 非空表,an,a1,head,head,x,s,r-next=s;,head,x,s,r-next=s;,空表 非空表,r=s;,r=s;,例：带头结点的单链表的后插法建立,结论：带头结点的单链表同样也会简化其它的链表操作（如：插入、删除）,head,p,a0,a1,a2,j=0,head,p,a0,a1,a2,j=1,head,p,a0,a1,a2,j=2,head,p,a0,a1,a2,j=3,计算带头结点的单链表长度,int Length(LinkList head)LNode*p=head;/指针 p 指示头结点 int j=0;while(p-next!=NULL)/逐个结点检测 p=p-next;j+;return j;,计算带头结点的单链表长度,head,0,p,j=0,思考：空表是否适用该算法？,int Length2(LinkList head)int j;LNode*p=head;/指针 p 指示头结点 if(p-next=NULL)return 0;j=1;while(p-next!=NULL)/逐个结点检测 p=p-next;j+;return j;,p,j=1,计算不带头结点的单链表长度,以后的算法如不加说明都是带头结点的,LNode*Find(LinkList head,datatype x)/在链表中从头查找数据域的值为x的结点 LNode*p=head-next;/检测指针 p 指示第 1 号结点 while(p!=NULL,在单链表中按值查找,head,p,a1,a2,a3,LNode*Locate(LinkList head,int i)/返回表中第 i 个元素的地址 LNode*p=head;int j=0;/置于表头 while(p-next!=NULL/返回第 i 个结点地址或NULL,在单链表中按序号查找（定位）,head,p,a1,a2,a3,j=0,(插入前)(插入后),后插结点：在*p之后插入*s s-next=p-next;p-next=s；,s,p,s,p,单链表中的插入与删除,前插结点：在*p之前插入*s,head,p,a0,a1,a2,qhead;while(q-next!=p)q=q-next;s-next=q-next；q-next=s;,int Insert(LinkList head,int x,int i)/在链表第 i(=0)个位置处插入新元素 x LNode*p=head，*s;p=Locate(head,i-1);/找第 i-1个结点 if(p=NULL)printf(“无效的插入位置!n”);return 0;else s=(Lnode*)malloc(sizeof(Lnode);/创建新结点 s-data=x;s-next=p-next;p-next=s;return 1;,O(n),删除删除结点删除运算,ai-1,ai-1,ai,ai,ai+1,ai+1,q,p,删除前,删除后,q-nest=p-next;free(p);,int Delete(LinkList head,int i)/在链表中删除第 i 个结点 LNode*p=head,*s;p=Locate(head,i-1);/找第 i-1个结点 if(p=NULL)printf(“第i1个结点不存在!n”);return-1;else if(p-next=NULL)printf(“第i个结点不存在”);return 0;else s=p-next;p-next=s-next;free(s);/删除s return 1;,O(n),head,a0,a1,a2,【练习1】单链表清空,void makeEmpty(LinkList head)/删去链表中除表头结点外的所有其他结点 LNode*q;while()q=head-next;/将表头结点后第 1 个结点从链中摘下/释放它,head-next!=NULL,head-next=q-next;,free(q);,【练习2】写出函数体 单链表求和函数 typedef int datatype;int sum(LinkList head)LNode*p=head-next;int sum=0;while(p!=NULL)sum+=p-data;/累加 p=p-next;return sum;,循环链表(Circular List),循环链表：使单链表最后一个结点的 next 指针不为 NULL，而是指向了表的最前端。为简化操作，往往在循环链表中加入表头结点。特点：只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。,循环链表的示例带表头结点的循环链表,a1,a2,a3,an,head,an,head,a2,a1,head,(空表),(非空表),循环链表的定义,typedef char datatype;typedef struct cnode/链表结点 datatype data;/结点数据域 struct cnode*next;/结点链域 CircListNode;typedef CircListNode*CircLinkList;/循环链表头指针CircLinkList head;/循环链表头指针,查找成功,查找不成功,循环链表的查找,head,head,31,31,48,48,15,15,57,57,查找15,查找25,p,p,p,p,p,p,p,p,循环链表的查找算法,CircListNode*Find(CircLinkList head,datatype x)/在链表中从头搜索其数据值为x的结点 CircListNode*p=head-next;/检测指针 p 指示第 0 号结点 while()p=p-next;if(p-data=x)return p;,p!=head&p-data!=x,带尾指针的循环链表,rear,31,48,15,57,22,如果插入与删除仅在链表的两端发生，可采用带表尾指针的循环链表结构。在表尾插入，时间复杂性 O(1)在表尾删除，时间复杂性 O(n)在表头插入，相当于在表尾插入 在表头删除，时间复杂性 O(1),两个用尾指针标识的循环链表的连接,R1,a1,a3,a4,b2,b3,b4,b1,a2,R2,p=R1-next;R1-next=R2-next-next;free(R2-next);R2-next=p;,双向链表,双向链表是指在前驱和后继方向都能遍历的线性链表。双向链表每个结点结构：通常采用带表头结点的循环链表形式。,前驱方向 后继方向,结点指向p=p-prior-next=p-next-prior;,非空表 空表,p-prior,p-next,p,prior,next,head,head,双向循环链表的定义,typedef struct dnode datatype data;/数据 struct dnode*prior,*next;/指针 DblNode;typedef DblNode*DblList;/双向链表,建立空的双向循环链表,void CreateDblList(DblList/表头结点的链指针指向自己,计算双向循环链表的长度,int Length(DblList head)/计算带表头结点的双向循环链表的长度 DblNode*p=head-rlink;int count=0;while(p!=head)p=p-rlink;count+;return count;,查找成功,查找不成功,双向循环链表的查找,head,head,31,31,48,48,15,15,57,57,查找15,查找25,ListNode*Find(DblList head,datatype x)/在双向循环链表中搜索含 x 的结点,若找到,/则返回该结点的地址,否则返回表头地址。DblNode*p=head-rlink;while(p!=head/也可以在 llink(前驱)方向查找,程序类似。,DblNode*Locate(DblList head,int i)if(i rlink;int j=0;while(p!=head/也可以在 llink(前驱)方向查找,程序类似。,定位：查找第 i 个结点在链中的位置,在双向链表的插入结点,31,48,15,p,q-next=p-next;q-prior=p;q-next-prior=q;p-next=q;,例：在*p 后插入值为25的新结点,思考：若顺序如下，则语句应改为什么？,31,48,15,p,q-prior=p-prior;p-prior-next=q;q-next=p;p-prior=q;,双向循环链表的插入(空表),在结点*p 后插入25,p,q-rlink=p-rlink;(=head)p-rlink=q;q-llink=p;q-rlink-llink=q;(head-llink=q),int Insert(DblList head,int i,datatype x)DblNode*p=Locate(head,i-1);/指针定位于插入位置 if(p=head,删除48,在双向链表中结点的删除结点,head,head,31,48,15,p,31,15,p-prior-next=p-next;p-next-prior=p-prior;,删除31,双向循环链表的删除,head,head,31,p,p-rlink-llink=p-llink;p-llink-rlink=p-rlink;,int Remove(DblList head,int i)DblNode*p=Locate(head,i);/指针定位于删除结点位置 if(p=head)return 0;p-rlink-llink=p-llink;p-llink-rlink=p-rlink;/将被删结点*p 从链上摘下 delete p;/删去 return 1;,静态链表结构,SL=,AV=,AV=,AV=,SL=,SL=,SL=,(10,15,20,30,50,67,78,81),静态链表定义,const int MaxSize=100;typedef int datatype;typedef struct node datatype data;int next;SNode;SNode sdMaxSize;int SL,AV;,data,next,3456789,AV=,SL=,void InitList(SNode sd)sd0.next=-1;AV=1;for(i=1;i MaxSize-1;i+)sdi.next=i+1;sdMaxSize-1.next=-1;,静态链表的初始化,data,next,3456789,SL=,AV=,在静态链表中查找具有给定值的结点,int Find(SNode sd,datatype x)int p=sd0.next;/指针 p 指向链表第 1 个结点 while(p!=-1)if(sdp.data!=x)p=sdp.next;else break;return p;,data,next,3456789,AV=,SL=,在静态链表的表尾追加一个新结点,int Append(SNode sd,datatype x)if(AV=-1)return 0;/追加失败 int q=AV;/分配结点下标为q AV=sdAV.next;sdq.data=x;sdq.next=NULL;int p=0;/查找表尾 while(sdp.next!=-1)p=sdp.next;sdp.next=q;/追加 return 1;,在静态链表中查找第 i 个结点,int Locate(SNode sd,int i)if(i 0)return-1;if(i=0)return 0 int j=1,p=sd0.next;while(p!=-1,data,3456789,AV=,SL=,例：查找第3 个结点,j=1,p=,j=2,p=,j=3,p=,在静态链表第 i 个结点处插入一个新结点,int Insert(SNode sd,int i,datatype x)int p=Locate(sd,i-1);if(p=-1)return 0;int q=AV;AV=sdAV.next;sdq.data=x;sdq.next=sdp.next;sdp.next=q;return 1;第 4 个结点处插入一个新结点,data,next,3456789,AV=,SL=,q=,p=,x,6,2,2,在静态链表中释放第 i 个结点,int Remove(SNode sd,int i)int p=Locate(sd,i-1);if(p=-1)return 0;/找不到结点 int q=sdp.next;/第 i 号结点 sdp.next=sdq.next;sdq.next=AV;AV=q;/释将释放的结点插入到空表的最前面 return 1;,单链表应用举例,例1：单链表倒置 算法思想：依次取原链表中的每个结点，将其做为第一个结点插入到新链表中。,a1,a2,a3,h,0,算法实现见书P29,例2：删除单链表H中的重复结点。思想：P指向第一个结点，从它的后继结点开始到表的结束，找与其值相同的结点并删除之，P指向下一个结点，依此类推，直到p指向最后一个结点时算法结束。,10,15,10,head,15,例3：将两个递增有序的单链表A、B归并成一个递减有序的单链表，要求用A、B中的原结点，不能重新申请结点。思想：依次将A、B中较小结点摘下，插入到C表的头部。,1,3,A,2,4,6,B,C,一元多项式(Polynomial),n 阶多项式 Pn(x)有 n+1 项。系数 c0,c1,c2,cn 指数 0,1,2,n。按升幂排列,ADT Polynomial Polynomial();/构造函数 int operator!();/判是否零多项式 float Coef(int e);int LeadExp();/返回最大指数 Polynomial Add(Polynomial poly);Polynomial Mult(Polynomial poly);float Eval(float x);/求值,多项式(Polynomial)的抽象数据类型,多项式的存储表示,第一种：(静态数组表示)int degree;float coef maxDegree+1;Pn(x)可以表示为：pl.degree=n pl.coefi=ci,0 i n,0 1 2 degree maxDgree,c0,c1,c2,cn,coef,第二种：(动态数组表示)int degree;float*coef;动态分配 degree=sz;coef=new floatdegree+1;以上两种存储表示适用于指数连续排列的多项式。但对于指数不全的多项式如 P101(x)=3+5x50-14x101,不经济。,在多项式的链表表示中每个结点三个数据成员：优点是：多项式的项数可以动态地增长，不存在存储溢出问题。插入、删除方便，不移动元素。,第三种：多项式的链表表示,coef exp next,elem Term,typedef struct node/多项式结点定义 float coef;/系数 int exp;/指数 struct node*next;/链指针 Term;typedef Term*Polynomial;/多项式的定义,多项式(polynomial)链表定义,多项式链表的相加,AH=1-3x6+7x12BH=-x4+3x6-9x10+8x14,AH,BH,CH,1 0,1 0,-1 4,-1 4,-3 6,3 6,-9 10,-9 10,7 12,7 12,8 14,8 14,两个多项式的相加算法,扫描两个多项式，若都未检测完：若当前被检测项指数相等，系数相加。若未变成 0，则将结果加到结果多项式。若当前被检测项指数不等，将指数小者加到结果多项式。若一个多项式已检测完，将另一个多项式剩余部分复制到结果多项式。,AH,BH,CH,1 0,1 0,-1 4,-1 4,-3 6,3 6,-9 10,7 12,7 12,8 14,8 14,pa,p,pc,-9 10,pb,1 0,1 0,-1 4,-1 4,-3 6,3 6,-9 10,7 12,7 12,8 14,8 14,pa,pb,pc,-9 10,AH,CH,1 0,1 0,-1 4,-1 4,-3 6,3 6,-9 10,7 12,7 12,8 14,8 14,pa,pb,pc,-9 10,AH,CH,1 0,1 0,-1 4,-1 4,-3 6,3 6,-9 10,7 12,7 12,8 14,8 14,pa,p,pc,-9 10,pb,0,AH,CH,1 0,1 0,-1 4,-1 4,0 6,-9 10,7 12,7 12,8 14,8 14,pa,p,pc,-9 10,pb,AH,CH,1 0,1 0,-1 4,-1 4,-9 10,7 12,7 12,8 14,8 14,pa,pc,-9 10,pb,AH,CH,1 0,1 0,-1 4,-1 4,-9 10,7 12,7 12,8 14,8 14,pa,pc,-9 10,pb,AH,CH,1 0,1 0,-1 4,-1 4,-9 10,7 12,7 12,8 14,8 14,pa=,pc,-9 10,pb,AH,CH,1 0,1 0,-1 4,-1 4,-9 10,7 12,7 12,8 14,8 14,pa=,pc,-9 10,pb,AH,CH,Polynomial/删去bh的表头结点,while(pa!=NULL/相加为零,该项不要,else/相加不为零,加入ch链 pc-next=pa;pc=pa;pa=pa-next;break;case:/pa-exp pb-exp pc-next=pb;pc=pb;pb=pb-next;break;case exp exp pc-next=pa;pc=pa;pa=pa-next;,if(pa!=NULL)pc-next=pa;else pc-next=pb;/剩余部分链入ch链 return ah;,顺序表与链表的比较,基于空间的比较存储分配的方式顺序表的存储空间可以是静态分配的，也可以是动态分配的。链表的存储空间是动态分配的存储密度=结点数据本身所占的存储量/结点结构所占的存储总量顺序表的存储密度=1链表的存储密度 1,基于时间的比较存取方式顺序表可以随机存取，也可以顺序存取链表是顺序存取的插入/删除时移动元素个数顺序表平均需要移动近一半元素链表不需要移动元素，只需要修改指针若插入/删除仅发生在表的两端，宜采用带尾指针的循环链表,