数据结构-ppt课件-链表部分.ppt

回顾上次课内容回顾上次课内容n数据结构的相关概念n数据的存储结构逻辑结构存储结构集合集合线性结构线性结构树形结构树形结构图状结构或网图状结构或网状结构状结构顺序存储结构顺序存储结构链接存储结构链接存储结构n算法分析方法第二章第二章 线性表线性表主要内容：l 线性表的类型定义线性表的类型定义l 线性表的顺序表示和实现线性表的顺序表示和实现l 线性表的链式表示和实现线性表的链式表示和实现l 线性表的应用举例线性表的应用举例 线性结构的特点线性结构的特点线性结构的特点线性结构的特点存在惟一的一个开始结点，称做存在惟一的一个开始结点，称做“第一个第一个”的数据元素的数据元素存在惟一的一个终端结点，称做存在惟一的一个终端结点，称做“最后一个最后一个”的数据元素的数据元素除第一个外，每个数据元素只有一个前驱除第一个外，每个数据元素只有一个前驱除最后一个外，每个数据元素只有一个后继除最后一个外，每个数据元素只有一个后继1.1.描述描述描述描述:线性表是由线性表是由n(n=0)个数据元素个数据元素(结点结点)a1,a2,.,ai,.,an组成的有限序列。其中，数据元素组成的有限序列。其中，数据元素的个数的个数n定义为表长。当定义为表长。当n=0时称为空表，非空的线性表时称为空表，非空的线性表(n0)记为：记为：(a1,a2,.,ai,.,an)一、逻辑结构一、逻辑结构一、逻辑结构一、逻辑结构注意注意注意注意:1.数据元素数据元素ai是一个抽象的符号是一个抽象的符号2.ai可取各种数据类型可取各种数据类型3.同一线性表中的元素必定具有相同的特性，属于同一数同一线性表中的元素必定具有相同的特性，属于同一数据对象据对象4.相邻数据元素之间存在序偶关系相邻数据元素之间存在序偶关系5.i是数据元素是数据元素ai在线性表中的位序在线性表中的位序(1i n)2.2.2.2.逻辑特征逻辑特征逻辑特征逻辑特征：仅有一个开始结点和一个终端结点，并且所有结：仅有一个开始结点和一个终端结点，并且所有结点都最多只有一个前驱和一个后继点都最多只有一个前驱和一个后继线性表是一个线性结构线性表是一个线性结构线性表是一个线性结构线性表是一个线性结构2.1 线性表的类型定义线性表的类型定义二、抽象数据类型线性表的定义二、抽象数据类型线性表的定义ADTList数据对象：数据对象：D=aiaiElemset,i=1,2,n,n0数据关系：数据关系：R1=ai-1,aiD,i=2,n基本操作：基本操作：构造、销毁、置空、判空、获取元素、插入、删除、构造、销毁、置空、判空、获取元素、插入、删除、定位等。定位等。ADTListna1是第一个元素，有且仅有一个直接后继元素是第一个元素，有且仅有一个直接后继元素a2；nan是最后一个元素，有且仅有一个直接前趋元素是最后一个元素，有且仅有一个直接前趋元素an-1；n其余其余ai(1in)有且仅有一个直接前趋有且仅有一个直接前趋ai-1，有且仅有一，有且仅有一个直接后继个直接后继ai+11顺序表示（存储）顺序表示（存储）：指在内存中用地址连续的一块存储空间顺序存放线性表的各元素，用这种存储形式存储的线性表称其为顺序顺序表表。线性表顺序存储结构示意图线性表顺序存储结构示意图2.2 线性表的顺序表示和实现线性表的顺序表示和实现n数据元素存储位置表示数据元素存储位置表示设设 a的存储地址为的存储地址为Loc(a)，每个数据元素占每个数据元素占l l个存储地址，则第个存储地址，则第i个数据元素的地址为：个数据元素的地址为：Loc(ai)=Loc(a)+(i-1)*l l，1inn逻辑上相邻的逻辑上相邻的ai和和ai+1以相邻的存储位置。以相邻的存储位置。n确定起始位置后，顺序表中任一数据元素都可确定起始位置后，顺序表中任一数据元素都可随机存取。随机存取。n顺序表是一种随机存取的存储结构。顺序表是一种随机存取的存储结构。n 高级语言中一般用数组来描述顺序存储。高级语言中一般用数组来描述顺序存储。#include#define MAXSIZE 100typedef int ElemType;typedef structElemType aMAXSIZE;int length;Sqlist;因为线性表长度可变，且所需最大空间随问题不同因为线性表长度可变，且所需最大空间随问题不同而不同，所以用动态分配的一维数组而不同，所以用动态分配的一维数组(P22)。为使得。为使得算法简明扼要，暂使用静态数组。算法简明扼要，暂使用静态数组。线性表的建立、输出算法线性表的建立、输出算法初始化初始化void initlist(Sqlist*L)L-length=0;建立顺序表建立顺序表void creat_sqlist(Sqlist&L)int i,n;coutn;L.length=n;for(i=0;iL.ai;void initlist(Sqlist&L)L.length=0;Sqlist Sl;initlist(&Sl);Sqlist Sl;initlist(Sl);输出顺序表输出顺序表void outputl(Sqlist L)int i;coutList length L.lengthendl;for(i=0;iL.length;i+)coutL.ai ;if(i+1)%10=0)coutendl;coutendl;(a1,ai-1,ai,an)改变为(a1,ai-1,e,ai,an)a1a2ai-1aiana1a2ai-1aiean表的长度加11.插入：在线性表第插入：在线性表第i（1i n+1）个位置上插入元）个位置上插入元素素e线性表主要操作的实现线性表主要操作的实现注意：注意：C语言中的数组下标从语言中的数组下标从“0”开始，因此，若开始，因此，若L是是Sqlist类型的顺序表，则表中第类型的顺序表，则表中第i个元素是个元素是L.ai-1。void insert_sq(Sqlist&L,int i,ElemType e)int j;if(L.length=MAXSIZE)coutERROR!endl;elseif(iL.length+1)coutERROR!i-1;j-)L.aj=L.aj-1;L.ai-1=e;L.length+;这里的问题规模是表的长度，设它的值为这里的问题规模是表的长度，设它的值为n。该算。该算法的时间主要花费在循环的元素后移语句上，所需移法的时间主要花费在循环的元素后移语句上，所需移动元素的次数不仅依赖于表的长度，而且还与插入位动元素的次数不仅依赖于表的长度，而且还与插入位置有关。置有关。i位置位置 移动次数移动次数 1n 2 n-1 i n-i+1 n 1 n+10插入操作时间复杂度分析插入操作时间复杂度分析n最好情况下：T(n)=O(1)n最坏情况下：T(n)=O(n)n平均时间复杂度：长度为n的顺序表中，插入一个结点，令E(n)表示移动结点的期望值(移动平均次数)，在表中第i个位置插入一个结点移动的次数为n-i+1.其中pi表示在表中第i位置插入结点的概率。Pi1/(n+1)计算得 E(n)=n/2，所以平均时间复杂度为O(n)(a1,ai-1,ai,ai+1,an)改变为(a1,ai-1,ai+1,an)（1 i n）ai+1 an表的长度减1a1a2ai-1aiai+1ana1a2ai-12.2.删除：在线性表中删除第删除：在线性表中删除第i i个元素，使个元素，使ElemType delete_sq(Sqlist&L,int i)int x,j;if(L.length=0)coutERROR!endl;return(-1);else if(iL.length)coutERROR!“endl;return(-1);else x=L.ai-1;for(j=i;j0)，否则返回，否则返回-1，表示未找到。，表示未找到。int locate_sq(Sqlist L,ElemType e)int i;i=0;while(i=L.length-1&L.ai!=e)i+;if(i=L.length-1)return(i+1);return(-1);4.合并：两表分别非递减有序合并：两表分别非递减有序(递增或等值递增或等值)，合并，合并后仍然非递减有序。后仍然非递减有序。void merge_list(Sqlist a,Sqlist b,Sqlist&c)int i,j,k;i=j=k=0;c.length=a.length+b.length;while(i=a.length-1&j=b.length-1)if(a.ai=b.aj)c.ak=a.ai;i+;k+;else c.ak=b.aj;j+;k+;while(i=a.length-1)c.ak=a.ai;i+;k+;while(jdata 表示数据域表示数据域p-next 表示指针域表示指针域线性表的单链表线性表的单链表线性表的单链表线性表的单链表函数函数mallocfree(p);访问结点访问结点指针赋值的操作指针赋值的操作指针赋值的操作指针赋值的操作P=(LNode*)malloc(sizeof(LNode);产生一个产生一个Lnode类型结点，把首地址送给类型结点，把首地址送给P变量变量系统回收系统回收P所指向的结点（若干字节），所指向的结点（若干字节），P中无中无所指向所指向Lnode*p,s;p-data=20;p-next=null;(s.data=20;s.next=null;用的少用的少)指针指向结点指针指向结点p=qq p指针指向后继指针指向后继p=q-next指针移动指针移动p=p-nextqppp指针赋值的操作指针赋值的操作指针赋值的操作指针赋值的操作pqp-next=qp-next=q-nextpq1.创建链表创建链表单链表的基本运算单链表的基本运算void creat_list()ElemType x;LNode*ptr,*p;p=head;coutx;while(x!=999)ptr=new LNode;ptr-data=x;ptr-next=NULL;p-next=ptr;p=ptr;coutx;调用语句：head=new LNode;head-next=NULL;creat_list();定义定义head为全局变量为全局变量void create(LNode*L)int i,n;LNode*s,*p;p=L;coutn;for(i=1;i=n;i+)s=new LNode;couts-data;p-next=s;p=s;p-next=NULL;调用语句：head=new LNode;head-next=NULL;create(head);定义定义head为局部变量为局部变量LNode*Creat_L(int n)int i;LNode*L,*p;L=new LNode;L-next=NULL;for(i=n;i=1;i-)p=new LNode;coutp-data;p-next=L-next;L-next=p;return(L);调用语句：head=Creat_L(5);定义定义head为全局变量为全局变量2.输出链表输出链表void out_list()LNode*q;q=head-next;if(q=NULL)coutEmpty list!n;elsewhile(q!=NULL)coutdatanext;coutnext;j=1;while(p&jnext;j+;if(!p|ji)return(-1);else return(p-data);调用语句：coutGetElem is GetElem(head,4)endl;语句频度：语句频度：in，n次次平均为平均为n数量级，故数量级，故T(n)=O(n)4.在带头结点的单链表在带头结点的单链表L中第中第i结点之前插入元素结点之前插入元素evoid Insert_L(LNode*L,int i,ElemType e)LNode*p,*s;int j;p=L;j=1;while(p!=NULL&jnext;j+;if(p=NULL|ji)coutERROR!data=e;s-next=p-next;p-next=s;5.删除带头结点的单链表删除带头结点的单链表L中第中第i个结点，其数据元素由函个结点，其数据元素由函数名返回数名返回ElemType delete_list(LNode*L,int i)LNode*p,*q;int j;ElemType e;p=L;j=0;while(p-next!=NULL&jnext;j+;if(p-next=NULL|ji-1)coutERROR!next;e=q-data;p-next=q-next;delete(q);return(e);void listdelete_L(LNode*L,ElemType x)LNode*p,*q;p=L;while(p-next&p-next-data!=x)/找找x的前的前驱驱p=p-next;if(!p-next)coutNot find elementnext;p-next=q-next;delete(q);/删除删除x结点结点6.在带头结点的单链表在带头结点的单链表L中，查找值中，查找值x的元素，删除之。的元素，删除之。（假设（假设L中元素不重复）中元素不重复）7.链表合并链表合并La,Lb有序递增，合并为有序递增，合并为Lc，仍非递减有序，仍非递减有序LNode*merge_list(LNode*La,LNode*Lb)LNode*Lc,*pa,*pb,*pc;Lc=La;pc=La;/以以La链为基础链为基础pa=La-next;pb=Lb-next;while(pa!=NULL&pb!=NULL)if(pa-datadata)pc-next=pa;pc=pa;pa=pa-next;else pc-next=pb;pc=pb;pb=pb-next;if(pa!=NULL)pc-next=pa;else pc-next=pb;delete(Lb);return(Lc);T(n)=O(m+n)链式存储结构小结链式存储结构小结链式存储结构小结链式存储结构小结：（1）a1,ai+1地址可不连续；地址可不连续；（2）不能直接存取，需先移动指针到）不能直接存取，需先移动指针到ai；（3）插入、删除时，不需大量移动元素。）插入、删除时，不需大量移动元素。以上是动态链表的基本操作，另外还有静态链表，课下以上是动态链表的基本操作，另外还有静态链表，课下以上是动态链表的基本操作，另外还有静态链表，课下以上是动态链表的基本操作，另外还有静态链表，课下自己了解，适用于自己了解，适用于自己了解，适用于自己了解，适用于BASICBASIC语言。语言。语言。语言。n最后一个结点的指针域的指针又指回第一个结最后一个结点的指针域的指针又指回第一个结点的链表点的链表和单链表的差别仅在于，和单链表的差别仅在于，判别判别链表中最后一个结链表中最后一个结点的点的条件条件不再是不再是“后继是否为空后继是否为空”，而是，而是“后后继是否为头结点继是否为头结点”。a1a2anH(a)H(b)单循环链表循环链表循环链表循环链表循环链表p=Anext;Anext=Bnextnext;Bnext=p;A=B;操作和线性链表基本一致，有时在循环链表中设立尾指针操作和线性链表基本一致，有时在循环链表中设立尾指针可使操作简化。见下图可使操作简化。见下图ABAB/-/-线性表的双向链表存储结构线性表的双向链表存储结构 -typedef struct DuLNode ElemType data;/数据域 struct DuLNode*prior;/指向前驱的指针域 struct DuLNode*next;/指向后继的指针域 DuLNode,*DuLinkList;双向链表双向链表a1a2anheadhead双向链表双向链表双向链表双向链表ai-1aies-prior=p-prior;psai-1ai插入插入p-prior-next=s;s-next=p;p-prior=s;ai-1删除删除aiai+1p-prior-next=p-next;p-next-prior=p-prior;free(p);pai-1n 本章介绍了线性表的逻辑结构及它的两种存储结构：顺序表和链表。顺序存储有三个优点：(1)方法简单，各种高级语言中都有数组，容易实现。(2)不用为表示结点间的逻辑关系而增加额外的存储开销。(3)顺序表具有按元素序号随机访问的特点。顺序表和链表的比较顺序表和链表的比较顺序表和链表的比较顺序表和链表的比较但它也有两个缺点：在顺序表中做插入删除操作时，平均移动大约表中一半的元素，因此对n较大的顺序表效率低。需要预先分配足够大的存储空间，估计过大，可能会导致顺序表后部大量闲置；预先分配过小，又会造成溢出。链表的优缺点恰好与顺序表相反。n 基于存储的考虑基于存储的考虑 对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事对线性表的长度或存储规模难以估计时，不宜采用顺序表；链表不用事先估计存储规模，但链表的存储密度较低。先估计存储规模，但链表的存储密度较低。n 基于运算的考虑基于运算的考虑 如果经常做的运算是按序号访问数据元素，顺序表优于链表；如果经常做的运算是按序号访问数据元素，顺序表优于链表；在顺序表中做插入、删除操作时平均移动表中一半的元素，在链表中作在顺序表中做插入、删除操作时平均移动表中一半的元素，在链表中作插入、删除操作，虽然也要找插入位置，但操作主要是比较操作，从这个角插入、删除操作，虽然也要找插入位置，但操作主要是比较操作，从这个角度考虑后者优于前者。度考虑后者优于前者。n 基于环境的考虑基于环境的考虑 顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指顺序表容易实现，任何高级语言中都有数组类型，链表的操作是基于指针的，相对来讲前者简单些，也是用户考虑的一个因素。针的，相对来讲前者简单些，也是用户考虑的一个因素。n 总总之之，两两种种存存储储结结构构各各有有长长短短，选选择择那那一一种种由由实实际际问问题题中中的的主主要要因因素素决决定定。通通常常“较较稳稳定定”的的线线性性表表选选择择顺顺序序存存储储，而而频频繁繁做做插插入入删删除除的的即即动动态态性性较较强强的的线线性性表表宜宜选择链式存储。选择链式存储。在实际中怎样选取存储结构呢？在实际中怎样选取存储结构呢？在实际中怎样选取存储结构呢？在实际中怎样选取存储结构呢？通常有以下几点考虑：通常有以下几点考虑：通常有以下几点考虑：通常有以下几点考虑：在计算机中，可以用一个线性表来表示在计算机中，可以用一个线性表来表示:P=(p0,p1,，pn)一、一元多项式的表示一、一元多项式的表示但是对于形如但是对于形如S(x)=1+3x100002x20000的多项式，上述表示方法是否合适？的多项式，上述表示方法是否合适？2.4 线性表的应用线性表的应用_一元多项式相加一元多项式相加一般情况下的一元稀疏多项式一元稀疏多项式可写成Pn(x)=p1xe1+p2xe2+pmxem其中：其中：pi是指数为ei的项的非零系数，0e1e2exp=q-exp则将两结点中的系数相加，则将两结点中的系数相加，当和不为零时修改当和不为零时修改p结点中的系数域，将结点中的系数域，将p所指结点加入所指结点加入C;p、q后移。后移。2、若、若p-expexp则将则将p所指结点加入所指结点加入C。p后移。后移。3、若、若p-expq-exp则则q所指结点加入所指结点加入C。q后移。后移。typedefstructpolyfloatcoef;/系数系数intexp;/指数指数structpoly*next;poly;结点的数据元素类型定义为:元多项式的实现元多项式的实现元多项式的实现元多项式的实现poly*add_poly(poly*La,poly*Lb)poly*Lc,*pa,*pb,*pc,*s1,*s2;int x;Lc=La;pc=La;/以以La链为基础链为基础pa=La-next;pb=Lb-next;delete(Lb);while(pa&pb)if(pa-expexp)pc-next=pa;pc=pa;pa=pa-next;else if(pa-exppb-exp)pc-next=pb;pc=pb;pb=pb-next;else x=pa-coef+pb-coef;if(x=0)s1=pa;s2=pb;pc-next=pa-next;pa=pa-next;pb=pb-next;delete(s1);delete(s2);else s2=pb;pc-next=pa;pa-coef=x;pc=pa;pa=pa-next;pb=pb-next;delete(s2);本章小结本章小结1.1.了了解解线线性性表表的的逻逻辑辑结结构构特特性性是是数数据据元元素素之之间间存存在在着着线线性性关关系系，在在计计算算机机中中表表示示这这种种关关系系的的两两类类不不同同的的存存储储结结构构是是顺顺序序存存储储结结构构和和链链式式存存储储结结构构。用用前前者者表表示示的的线线性性表表简简称称为为顺顺序序表表，用后者表示的线性表简称为链表。用后者表示的线性表简称为链表。2.2.熟练掌握这两类存储结构的描述方法，以及熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。线性表的各种基本操作的实现。思考题P29 算法 2.8，若L不是带头结点的单链表，要如何调整程序？想一想，增加头结点的目的是什么？实验：实验：有一个单链表的第一个结点指针为有一个单链表的第一个结点指针为head,编写一个函编写一个函数将该单链表逆置数将该单链表逆置,即最后一个结点变成第一个结点即最后一个结点变成第一个结点,原来倒数第二个结点变成第二个结点。在逆置中不原来倒数第二个结点变成第二个结点。在逆置中不能建立新的单链表能建立新的单链表调试好后，老师检查，计入实验成绩。上机后写实调试好后，老师检查，计入实验成绩。上机后写实验报告。验报告。编程环境：编程环境：VC6.0+