数据结构第二章线性表.ppt

《数据结构第二章线性表.ppt》由会员分享，可在线阅读，更多相关《数据结构第二章线性表.ppt（24页珍藏版）》请在三一办公上搜索。

1、1,数据结构 第二章 线性表,重庆一中 葛静,2,数据元素之间满足线性关系的表称为线性表，是一种最基本、最简单的数据结构类型。本章讨论线性表的逻辑和存储结构、相关算法的实现以及线性表应用举例。2.1线性表的定义及基本操作2.1.1 定义：线性表(Linear List)是若干数据元素的一个线性序列，记为：L=(a1,ai-1aiai+1an)其中：L为表名，ai(1in)为数据元素；n为表长，n0 时，L为非空表，否则为空表。2.1.2 线性表的逻辑结构和特征 线性表L可用二元组形式描述：L=(D,R)数据元素集合:D=ai|aidatatype,i=1,2,n,n0关系集合:R=|ai,ai

2、+1D,1in-1表长n=0时，L为空表；关系符在这里称为有序对，表示任意相邻的两个元素之间的一种先后次序关系，称ai是ai+1的直接前驱,ai+1是ai的直接后继，当表长n1时，关系集R为空集。,3,例2-1 线性表的例子,L1=(A,B,Z)元素为字符；L2=(6,7,105)元素为整数；学生记录表：线性表的特征：对非空表,a1是表头,无前驱；an是表尾,无后继；其它的每个元素ai有且仅有一个直接前驱(ai-1)和一个直接后继(ai+1)。2.1.3 线性表的抽象数据类型表示 设线性表 L=(a1,a2,an)，对 L的抽象数据类型表示：,a1a2.a32,4,线性表的抽象数据类型表示,A

3、DT List 数据元素集：D=ai|aidatatype,i=1,2,n,n0数据关系集：R=|ai,ai+1D,1in-1 基本操作集：P(置表空、求表长、插入、删除、查找一个元素等),5,2.2.1 顺序表,若将线性表L=(a0,a1,an-1)中的各元素依次存储于计算机一片连续的存储空间，如图2.2所示。这种机内表示为线性表的顺序存储结构(顺序表)。地址：b:占d个单元 b+d:设Loc(ai)为ai的地址，Loc(a1)=b，则：Loc(a2)=b+1*d b+（i-1）*d:.Loc(ai)=b+（i-1）*d b+（n-1)*d:图2.2顺序表的特点：(1)逻辑上相邻的元素 ai

4、,ai+1，存储位置也是相邻的；(2)对ai的存取为随机存取或按地址存取。(3)存储密度高。存储密度D=(数据结构中元素所占存储空间)/(整个数据结构所占空间)。顺序表的不足：对表的插入和删除等运算的时间复杂度较差。,6,线性表的顺序存储,Type list=record vec:array1.m0 of elemtype;len:integer;End;Var L:list;1、setnull(L)L.len:=0;操作结果：构造一个空的线性表L。2、length(L)return(L.Len);初始条件：线性表L存在。操作结果：返回L中的元素个数。3、向线性表的第i个元素插入一个元素步骤：

5、（1）检查存储空间是否已经满，若满，则“溢出”。（2）检查i是否超范围1=i=n+1,若是，则“超出范围”（3）将线性表中第i个元素和后面所有元素均后移一位。（4）将新元素写在第i个位置上。（5）线性表长度加1.,7,线性表的抽象数据类型表示,3、向线性表的第i个元素插入一个元素的算法描述Insert(L,i,x);Begin if L.len=m0 then writeln(overflow);if(iL.len+1)then writeln(out of range);for j:=L.len downto i do L.vecj+1:=L.vecj;L.veci=x;L.len:=L.l

6、en+1;End;算法复杂度分析：算法第1、2步根据情况可省略。时间复杂度主要取决于第3步，即for循环的次数，也就是向后移动的元素个数。当i=n+1时，最好情况,元素不移动,当i=1时，最坏情况，移动n次。假定在线性表的任何位置上插入元素的概率相同，为pi=1/(n+1),1=i=n+1,则元素平均移动的次数为：Pi(n+n-1+n-2+0)=pi(n(n+1)/2)=n/2故最坏和平均O(n),8,线性表的抽象数据类型表示,4、删除线性表的第i个元素算法步骤：（1）检查1n)then writeln(out of range);x:=L.vexi;for j:=i+1 to L.len d

7、o L.vecj-1:=L.vecj;L.len:=L.len-1;End;时间复杂度分析：最坏，i=n时，不移动元素，i=1时，移动n-1个元素。删除任意元素等概率情况下1/n，1/n(0+1+2+n-1)=1/n(n(n-1)/2)=(n-1)/2故最坏和平均O(n),9,线性表的抽象数据类型表示,5、删除给定值等于x的第一个元素。算法步骤：（1）从线性表的起始元素开始，根X 比较，直到X等于某个元素值（查找成功），或者查完所有元素仍找不到（查找失败）。（2）若查找失败，则“没有找到”错误处理。（3）删除其值等于x的元素。（4）线性表长度减1；算法描述：Delete(L,x);Begin

8、i:=1;while(ix)do inc(i);if in then writeln(not find)else for j:=i+1 to L.len do L.vecj-1:=L.vecj;dec(L.len);End;O(n),10,线性表的操作,以上运算是对线性表L施加的一些基本运算，对线性表L的运算还有：合并、拆分、复制、排序等等。例2-2 设线性表La=(a1a2,am),Lb=(b1b2,bn)，求LaLb=La，如图2.1所示。算法思路：依次取Lb中的bi(i=1,2,n)，若bi不在La中，则将其插入。算法描述：procedure Union(La,Lb:list);begi

9、n var i,x:integer;k:boolean;for i:=1 to Lb.len do begin x:=Lb.veci;k:=locateLa,x;判断x是否在La中，自定义函数 if not k then insert(La,x);end;类似可写出求LaLb,LaLb等运算的算法。,11,线性表的操作,例2-3 设计清除线性表L=(a1,a2,-,ai,-,an)中重复元素的算法。算法思路：对当前表L中的每个ai（1in-1），依次与aj(i+1jn)比较，若与ai相等，则删除之。算法描述：procedure Purge(var L:list)begin for i:=1 t

10、o L.len-1 do for j:=i+1 to L.len do if L.veci=L.vecj then delete(L,j)；delete函数表示从L中删除第j位上的元素 end;初始：L=（1，3，1，5，3，5，7）i j结果：L=（1，3，5，7）,12,2.3 线性表的链式存储结构,线性表的顺序存储结构有存储密度高及能够随机存取等优点，但存在以下几点不足：(1)插入、删除等运算耗时，且存在元素在存储器中成片移动的现象；(2)要求系统提供一片较大的连续存储空间。下面讨论线性表的链式存储结构，即链表。是第二章的重点。单链表将线性表L=(a1,a2,an)中各元素分布在存储器的

11、不同存储块，称为节点，通过地址或指针建立它们之间的联系，所得到的存储结构为链表结构。表中元素ai的节点形式如图2.4所示。图2.4其中，data域存放数据元素ai，而next域是一个指针，指向ai的直接后继ai+1所在的节点。于是，线性表L=(a1,a2,an)的结构如图2.5所示:,L.,13,单链表,例2-4 设线性表L=(赵，钱，孙，李，周，吴，郑，王)，各元素在存储器中的分布如图2.6所示。,图2.6带头节点的单链表：,L,14,单链表,节点描述：type link=node;node=record data:elemtype;next:link;end;若说明var A:node;p

12、:link;则结构变量A为所描述的节点，而指针变量p为指向此类型节点的指针（或p的值为节点的地址），如图2.8所示:设p指向链表中节点ai，如图2.9所示:获取ai，写作：p.data；而取ai+1,写作：p.next.data。另外，若指针p的值为NULL，则它不指向任何节点,此时取p.data或p.next是错误的。,15,单链表的基本操作,可调用pascal中new(p)函数向编译系统申请节点的存储空间，若说明：Var var p:link;new(p);则获得了一个类型为node的节点，且该节点的地址已存入指针变量P中：1建立单链表算法思路：依次读入L=(a1,.,an)中每一ai(设

13、为整型)，若i=n，则将ai形成一节点，链入表尾，最后返回链表的头节点指针H。算法描述：procedure create;var p,q,h:link;I,j:integer;begin i:=1;readln(x);new(p);p.data:=x;p.next:=nil;q:=p;h:=p;inc(i);while i=n do begin readln(x);new(p);p.data:=x;p.next:=nil;q.next:=p;q:=p;end;end;,16,设L=(2，4，8)，则建表过程如下：设表长为n，显然此算法的时间复杂度为T(n)=O(n)。从此算法可以看到，链表的结

14、构是动态形成的，即算法运行前，表结构是不存在的，而通过算法的运行，得到一个如图所示的单链表。2链表查找 在单链表中查找即实现GetElem(L,k)。算法思路：从表头第一个结点起，依次使每个结点的关键字同给定的的值K进行比较，直到某个结点的关键字等于给定值K(查找成功)，或查找的表尾（查找失败）为止。算法描述：function locate(H,k):boolean;begin p:=h;while pnil do if p.datak then p:=p.next else begin locate:=true;q:=p;break;end;q返回被查找元素的地址 end;,建立单链表,17

15、,3前插 即实现ListInsert(L,i,e)。讨论将x插入表中节点ai之前的情况。算法思路：调用算法GetElem(H,i-1)，获取节点ai-1的指针p(ai 之前驱)，然后申请一个q节点，存入e，并将其插入p节点之后。插入时的指针变化如图2.14所示。,图2.14算法描述：q.next:=p.next;p.next:=q;此算法的时间主要花费在函数Getlist(H,i-1)上，故T(n)=O(n)，但插入时未引起元素的移动，这一点优于顺序结构的插入。,18,单链表删除,4删除 即实现ListDel(L,i)。图2.15 算法思路：同插入法，先调用函数GetElem(H,i-1),找

16、到节点ai的前驱，然后如图2.15所示，将节点ai删除之。算法描述：p.next:=q.next;dispose(q)同插入法，此算法的T(n)=O(n)。,q,19,线性表的存储结构,顺序存储结构 用数组类型：list:array 1.max of elemtp;动态链式存储结构 用指针类型：point=p_list;p_list=record data:elemtp;next:point;end;静态链式存储结构type statinode=record data:elemtype;next:integer;end;var a:array1.maxof statinode;,20,比较一下

17、,21,线性表的典型实例,约瑟夫问题M个人围成一圈，从第一个人开始报数，数到N的人出圈；再由下一个人开始报数，数到N(N1)的人出圈；.。输出依次出圈的人的编号。M的值预先选定，N由键盘输入。分析：要解决这道问题，首先需要构造一个环表，构造环的方法很简单，只要存储每个人的下一个即可，当然，最后一个人的下一个就是第一个人，这样就构成了一个环，构造环以后，就可进行删除操作，直到环剩下一个人为止。,22,约瑟夫问题(采用链表),write(m 显示最后出圈人,23,约瑟夫问题(采用数组),const max=100;var a:array 1.max of integer;i,j,m,n:integer;begin write(m writeln(j)end.,24,作业,书上例题及课后练习,