数据结构2线性表.ppt
《数据结构2线性表.ppt》由会员分享,可在线阅读,更多相关《数据结构2线性表.ppt(66页珍藏版)》请在装配图网上搜索。
第二章数组,2.1线性表2.2顺序表2.3单链表2.4线性链表的其他变形2.5单链表的应用:多项式及其运算,2.1线性表,线性表(LinearList):由n(n0)个数据元素(结点)a1,a2,an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表,常常将非空的线性表(n0)记作:(a1,a2,an)()这里的数据元素ai(1in)只是一个抽象的符号,其具体含义在不同的情况下可以不同。,例子,例1、26个英文字母组成的字母表(A,B,C、Z)例2、某校从1978年到1983年各种型号的计算机拥有量的变化情况。(6,17,28,50,92,188),例3、学生健康情况登记表如下:,例4、一副扑克的点数(2,3,4,J,Q,K,A)线性表的逻辑特征是:在非空的线性表,有且仅有一个开始结点a1,它没有直接前趋,而仅有一个直接后继a2;有且仅有一个终端结点an,它没有直接后继,而仅有一个直接前趋an-1;其余的内部结点ai(2in-1)都有且仅有一个直接前趋ai-1和一个直接后继ai+1,线性表的逻辑结构:线性结构数据的运算是定义在逻辑结构上的。运算的具体实现则是在(物理)存储结构上进行的。线性表只能“顺序存取”数组与线性表的异同:数组id与位置的对应。线性表是线性排列的“对象”。,线性表的特点,线性表上实现的基本操作,1.构造2.随机访问:取第i个位置上的元素。3.插入:线性表的插入运算是指在表的第I(1in+1个位置上,插入一个新结点x。4.删除:线性表的删除运算是指将表的第i(1in)结点删除。5.查找:寻找具有特定数据的节点。6.归并、复制、计数、排序。,线性表的实现,顺序表:用顺序方法存储的线性表叫顺序表。,顺序存储:用一组连续的存储空间,依次存储线性表的元素。特点:其逻辑结构与物理结构(顺序结构相同。注意:顺序表是顺序存储,随机存取。实现顺序存储一种最好的方式是用数组。例顺序表a0,a1,a2,an-1,Loc(ai)=loc(a0)+i*c顺序表的抽象数据结构p43,顺序表上实现的基本运算,1.查找例:在顺序表12,15,33,45,67,89,57,78查找57(找到),查找66(找不到)。,程序实现,TempletintSeqlist:Find(type/找到,查找算法的时间复杂度,问题规模:表的长度,设它的值为n。算法的时间:主要化费在循环比较语句上。比较结点的次数依赖于(表的长度,被查找元素位置)。最好情况:a0=x;这时,其时间复杂度O(1);最坏情况:找不到;比较语句将循环执行n次,其时间复杂度O(n),平均复杂度:在长度为n的线性表中第i个位置上找到一个结点,令Efd(n)表示找到结点的期望值(即比较的平均次数),则在第i个位置上找到一个结点的比较次数为i+1。故Efd(n)=pi(i+1)假设在表中任何位置(0in-1)上查找结点的机会是均等的,则p0=p1=p2=pn-1=1/n因此,在等概率插入的情况下,Efd(n)=(i+1)/n=(n+1)/2在顺序表上做查找运算,算法的平均时间复杂度为O(n)。,2.插入例:在顺序表12,15,33,45,67,89,57,78的第三个元素处插入元素44。,44,程序实现,TempletintSeqlist:Insert(type,插入算法的时间复杂度,问题规模:表的长度,设它的值为n。算法的时间:主要化费在循环的结点后移语句上。移动结点的次数(依赖于表的长度,插入位置)。最好情况:i=n;由于循环变量的终值大于初值,结点后移语句将不进行;这是,其时间复杂度O(1);最坏情况:当i=1时,结点后移语句将循环执行n次,其时间复杂度O(n);,平均复杂度:在长度为n的线性表中第i个位置上插入一个结点,令Eis(n)表示移动结点的期望值(即移动的平均次数),则在第i个位置上插入一个结点的移动次数为n-i+1。故Eis(n)=pi(n-i+1)假设在表中任何位置(1in+1)上插入结点的机会是均等的,则p1=p2=p3=pn+1=1/(n+1)因此,在等概率插入的情况下,Eis(n)=(n-i+1)/(n+1)=n/2在顺序表上做插入运算,算法的平均时间复杂度为O(n)。,3.删除:在上例完成后,再删除44,完成后,程序实现,TempletintSeqlist:Remove(type/找不到,不能删除算法的平均复杂度=0(n),顺序表的使用,TempletvoidUnion(SeqList,线性表的链式表示和实现,顺序表的优点:取数方便快速。缺点:删除、插入平均要移o(n)个元素。适应性不强。,链表:是指用一组任意的存储单元来存放线性表的结点,这组存储单元可以是零散分布在内存中的任意位置上的。任意的存储单元如何存放线性表例:(a1,a2,a3,a4)链表中的结点结构:,单链表(SingleLinked):每一个结点只有一个链域,将各节点按顺序联系在一起的链表。链式存储的优点:存储方便。空间使用性好。取用不方便(一定是顺序取用)。链表:非顺序存储,顺序取用例1、线性表:(bat,cat,eat,fat,hat,jat,lat,mat),的单链表示意图如下:,heat,head,bat,cat,eat,mat,单链表是由表头唯一确定,因此单链表可以用头指针的名字来命名。,单链表的类定义,1.复合类定义法:Classlist;TempleteClasslistNodefriendclasslist;private:Type*data;listNode*link;,Templetclasslistprivate:listNode*first,*last;public:/公共线性表操作;,嵌套类Templetclasslistprivate:classlistNodepublic:type*data;listNode*link;listNode*first;*last;public:/公共线性表操作;,对象和对象指针,对象指针:用于存放对象地址的变量声明形式:类名*对象指针名。Point*p;Pointp1;p=通过对象指针引用对象成员:p-x,p-y,单链表的插入与删除,插入(表首、中间、最后),p,S,S-link=p-link;P-link=S;,删除算法(表首、中间、最后),P,S,p-link=s-link;DeleteS;,单链表的实现,不带表头的单链表结构,first,判断空表的条件:first=NULL,last,带表头的单链表结构,first,判断空表的条件:first-link=NULL,last,建立单链表,1、头插法建表该方法从一个空表开始,重复读入数据,生成新结点,将读入数据存放到新结点的数据域中,然后将新结点插入到当前链表的表头上,直到读入结束标志为止。,2、尾插法建表头插法建立链表虽然算法简单,但生成的链表中结点的次序和输入的顺序相反。若希望二者次序一致,可采用尾插法建表。该方法是将新结点插入到当前链表的表尾上,为此必须增加一个尾指针r,使其始终指向当前链表的尾结点。,查找运算,1、按序号查找在链表中,即使知道被访问结点的序号i,也不能象顺序表中那样直接按序号i访问结点,而只能从链表的头指针出发,顺链域link逐个结点往下搜索,直到搜索到第i个结点为止。因此,链表不是随机存取结构。设单链表的长度为n,要查找表中第i个结点,仅当1in时,i的值是合法的。但有时需要找头结点的位置,故我们将头结点看做是第0个结点,其算法如下:,TempletelistNode*list:find(inti)If(i*p=first-link;intj=0;while(p!=NULL,2、按值查找按值查找是在链表中,查找是否有结点值等于给定值key的结点,若有的话,则返回首次找到的其值为key的结点的存储位置;否则返回NULL。查找过程从开始结点出发,顺着链表逐个将结点的值和给定值key作比较。其算法如下:,TempletelistNode*list:find(typevalue)listNode*p=first-link;while(p!=NULL算法的执行时间亦与输入实例中的的取值key有关,其平均时间复杂度的分析类似于按序号查找,也为O(n)。,三、插入运算插入运算是将值为x的新结点插入到表的第i个结点的位置上,即插入到ai-1与ai之间。因此,我们必须首先找到ai-1的存储位置p,然后生成一个数据域为x的新结点*p,并令结点*p的指针域指向新结点,新结点的指针域指向结点ai。从而实现三个结点ai-1,x和ai之间的逻辑关系的变化,插入过程如:,Templeteintlist:insert(typevalue,inti)listNode*p=find(i-1);If(p=NULL)return0;listNode*newNode=GetNode(value,p-link);if(p-link=NULL)last=newNode;p-link=newNode;return1;,算法的时间主要耗费在查找操作find上,故时间复杂度亦为O(n)。四、删除运算删除运算是将表的第i个结点删去。因为在单链表中结点ai的存储地址是在其直接前趋结点aai-1的指针域link中,所以我们必须首先找到ai-1的存储位置p。然后令plink指向ai的直接后继结点,即把ai从链上摘下。最后释放结点ai的空间,将其归还给“存储池”。,设单链表的长度为n,则删去第i个结点仅当1in时是合法的。注意,当i=n+1时,虽然被删结点不存在,但其前趋结点却存在,它是终端结点。因此被删结点的直接前趋*p存在并不意味着被删结点就一定存在,仅当*p存在(即p!=NULL)且*p不是终端结点即plink!=NULL)时,才能确定被删结点存在。显然此算法的时间复杂度也是O(n)。从上面的讨论可以看出,链表上实现插入和删除运算,无须移动结点,仅需修改指针。,单链表的游标,指针的抽象:first;current;last;仿真:模仿人的工作。应用的方便性:在几乎不损失效率的前提下,可以利用游标直接完成多种运算。它是一种利用单链表的基本方式。(求和、求平均、求最大值。)O,静态链表,数组中的每一个元素附加一个链接指针,就形成了一个静态链表。静态链表是利用数组实现的,在运算过程中存储空间大小不变(静态)如何利用空间:分成两个链表1.可利用空间链表2.已用空间链表(实例),循环链表,单循环链表:在单链表中,将终端结点的指针域NULL改为指向表头结点,就得到了单链形式的循环链表,并简单称为单循环链表。为了使空表和非空表的处理一致,循环链表中也可设置一个头结点。这样,空循环链表仅有一个自成循环的头结点表示。如下图所示:,a1,an,.,first,非空表,空表,在用头指针表示的单链表中,找开始结点a1的时间是O(1),然而要找到终端结点an,则需从头指针开始遍历整个链表,其时间是O(n),first,在很多实际问题中,表的操作常常是在表的首尾位置上进行,此时头指针表示的单循环链表就显得不够方便.如果改用尾指针last来表示单循环链表,则查找开始结点a1和终端结点an都很方便,它们的存储位置分别是(lastlink)link和last,显然,查找时间都是O(1)。因此,实际中多采用尾指针表示单循环链表。,判断表尾的条件:P-link=first;判断空表的条件:first-link=first;由于循环链表中没有NULL指针,故涉及遍历操作时,其终止条件就不再像非循环链表那样判断p或plink是否为空,而是判断它们是否等于某一指定指针,如头指什或尾指针等。,例、在链表上实现将两个线性表(a1,a2,a3,an)和(b1,b2,b3,bn)链接成一个线性表的运算。算法:templeteCirclist*Circlist:Merge(CirclistA-last-link=(B-last-link)-link;deleteB-last-link;B-last-link=p;returnA);,first,last,first,last,用循环链表解约瑟夫问题,约瑟夫问题:旅行社用循环余数方法选择旅客,提供免费旅行。例子:n=8,m=3,双链表,问题的提出:双向遍历(删除)双链表的结构1节点的结构,2双链表结构,first,双向链表(Doublelinkedlist):在单链表的每个结点里再增加一个指向其直接前趋的指针域llink。这样就形成的链表中有两个方向不同的链,故称为双向链表。,双链表与单链表的区别,判断表空的条件:first=first-llink=first-rlink=last;判断表尾的条件:p-rlink=first;双链表的对称性:p-llink-rlink=p-rlink-llink=p,和单链表类似,双链表一般也是由头指针唯一确定的,增加头指针也能使双链表上的某些运算变得方便,将头结点和尾结点链接起来也能构成循环链表,并称之为双向链表。,向后插入算法,双向链表的向后操作算法:q-llink=p-lling;q-rlink=p;p-rlink-llink=q;p-rlink=q;,向前插入算法,双向链表的前插操作算法:q-llink=p-lling;q-rlink=p;p-llink-rlink=q;p-llink=q;,删除算法,pllinkrlink=prlink;prlinkllink=pllink;deletep;注意:与单链表的插入和删除操作不同的是,在双链表中插入和删除必须同时修改两个方向上的指针。上述上个算法的时间复杂度均为O(1)。,双向遍历,向后遍历while(p!=first,链表的总结,C+中的继承,Classpolygonpolygon(),move(),isInside(),referencePoint(),vdraw(),referencePoint,ClassRectangle:publicpolygonRectangle(),isInside(),draw(),vertex2,带有虚函数(virtual)的类不能实例化祖先类私有的项目不会继承到子孙类中祖先类受保护的和公共的项目继承到子孙类中,C+中的虚函数,Virtualvoiddraw()虚函数的作用同一类对象的统一行为。,Polygon:draw=0,Rectangle:draw,Square:draw,Triangle:draw,虚函数,虚函数是重载的另一种表现形式,这是一种动态的重载方式。虚函数允许函数调用与函数体之间的联系在运行时才建立,即动态联编。详见例virtual.cpp纯虚函数:是一个在基类中说明的虚函数,它在该基类中没有定义,但要求在它的派生类中定义自已的版本,或重新说明为纯虚函数。格式:virtualtypefunc_name(参数表),- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 线性
装配图网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文