二章线表.PPT

《二章线表.PPT》由会员分享，可在线阅读，更多相关《二章线表.PPT（60页珍藏版）》请在三一办公上搜索。

1、第二章 线性表,2.1 线性表的类型定义2.2 线性表的顺序表示和实现2.3 线性表的链式表示和实现 2.3.1 线性链表 2.3.2 循环链表 2.3.3 双向链表2.4 线性表的应用：一元多项式的表示及相加,线性结构是：一个数据元素的有序集。线性结构的基本特征：在数据元素的非空有限集合中，1、存在唯一的一个被称做“第一个”的数据元素 2、存在唯一的一个被称做“最后一个”的数据元素 3、除第一个之外，集合中的每个数据元素均只有一个前驱 4、除最后一个之外，集合中每个数据元素均只有一个后继例1：26个英文字母组成的字母表（A，B，C，Z）,例2：学生健康情况登记表如下：,（(王小林、79063

2、1、男、18、健康)，(陈 红、790632、女、20、一般)，),线性表(Linear List)：由n(n0)个数据元素(结点)a1，a2，an组成的有限序列。其中数据元素的个数n定义为表的长度。当n=0时称为空表，常常将非空的线性表(n0)记作：(a1，a2，an)这里的数据元素ai(1in)只是一个抽象的符号，其具体含义在不同的情况下可以不同。,2.1 线性表的类型定义,线性表的逻辑特征：在非空的线性表中，有且仅有一个开始结点a1，它没有直接前趋，而仅有一个直接后继a2；有且仅有一个终端结点an，它没有直接后继，而仅有一个直接前趋an-1；其余的内部结点ai(2in-1)都有且仅有一个

3、直接前趋a i-1和一个直接后继ai+1。结论：线性表是一种典型的线性结构。数据的运算是定义在逻辑结构上的，而运算的具体实现则是在存储结构上进行的。,线性表的抽象数据类型的定义：ADT List 数据对象:D=ai|aiElemSet,i=1,2,n,n0 数据关系:R1=|ai-1,ai D,i=2,n 基本操作:InitList(&L)操作结果：构造一个空的线性表L。DestroyList(&L)初始条件：线性表L已存在。操作结果：销毁线性表L。ListInsert(&L,i,e)初始条件：线性表L已存在,1iListLength(L)+1.操作结果：在L中第i个位置之前插入新的数据元素e

4、。ListDelete(&L,i,e)初始条件：线性表L已存在且非空,1iListLength(L)+1.操作结果：删除L的第i元素，并用e返回其值，L长度减1。,例2-1 利用两个线性表LA和LB分别表示两个集合A和B（即线性表中的数据元素即为集合中的成员），现要求一个新的集合A=AB。,void union(List if(!LocateElem(La，e，equal)ListInsert(la，+La_len，e),扩展1:利用两个线性表LA和LB分别表示两个集合A和B，现要求一个新的集合A=AB。,void JiHeJiao(List,例2-2 已知线性表LA和线性表LB中的数据元素按

5、值非递减有序排列，现要求将LA和LB归并为一个新的线性表LC，且LC中的元素仍按值非递减有序排列。此问题的算法如下：void MergeList(List La，List Lb，List while(i=La_len)&(j=Lb_len),GetElem(La，i，ai);getElem(Lb，j，bj);if(ai=bj)ListInsert(Lc，+k，ai);+i;else ListInsert(Lc，+k，bj);+j;while(i=La_len)GetElem(La，i+，ai);ListInsert(Lc，+k，ai);while(j=Lb_len)GetElem(Lb，j+，

6、bj);ListInsert(Lc，+k，bj);,2.2 线性表的顺序表示和实现2.2.1 顺序存储的线性表(Sequential Lists)把线性表的结点按逻辑顺序依次存放在一组地址连续的存储单元里。用这种方法存储的线性表简称顺序表。线性表的起始地址称作线性表的基地址。假设线性表的每个元素需占用L个存储单元，则线性表中第i+1个数据元素的存储位置LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满足下列关系：,LOC(ai+1)=LOC(ai)+L线性表的第i个数据元素ai的存储位置为：LOC(ai)=LOC(a1)+(i-1)*L,例：有一线性表为：(a1,a2,ai,an

7、)由于C语言中的一维数组也是采用顺序存储表示，故可以用数组类型来描述顺序表。,b,b+L,b+(i-1)L,b+(n-1)L,b+nL,a0,a1,ai-1,an-1,线性表的顺序存储的c语言描述：#define List_Init_Size 100 typedef LISTINCREMENT 10;typedef struct ElemType*elem;int length;int listsize;Sqlist;,2.2.2 顺序表上实现的基本操作线性表的初始化操作InitList(/InitList_Sq,问题规模是表的长度，设它的值为n。该算法的时间主要花费在循环的结点后移语句上，移

8、动结点的次数是n-i+1。依赖于表的长度与插入位置。当i=n+1时，结点后移语句将不进行；这是最好情况，其时间复杂度O（1）；当i=1时，需移动表中所有结点，即n次。这是最坏情况，其时间复杂度为O（n）。,插入算法ListInsert(&L,i,e)的实现。分析算法的复杂度：,王一,赵二,李四,张三,a0,a1,a2,a3,a4,王五,例：有一线性表为：(王一，赵二，张三，李四，王五)现要变为：(王一，赵二，李四，王五),王一,赵二,李四,a0,a1,a2,a3,a4,王五,例：有一线性表为：(王一，赵二，张三，李四，王五)现要变为：(王一，赵二，李四，王五),王一,赵二,李四,a0,a1,a

9、2,a3,a4,王五,例：有一线性表为：(王一，赵二，张三，李四，王五)现要变为：(王一，赵二，李四，王五),删除算法ListInsert(&L,i,&e)的实现。该算法的时间分析与插入算法相似，结点的移动次数也是由表长n和位置i决定。若i=n，无需移动结点；若i=1，则前移语句将循环执行n-1次。两种情况下算法的时间复杂度分别为O(1)和O(n)。删除算法的平均性能分析：在长度为n的线性表中删除一个结点，令Edl(n)表示所需移动结点的平均次数，pi表示删除表中第i个结点的概率。删除表中第i个结点的移动次数为n-i，故 Edl(n)=(n-i)pi,在等概率的假设下，p1=p2=p3=pn=

10、1/n由此可得：Edl(n)=(n-i)/n=(n-1)/2 即在顺序表上做删除运算，平均要移动表中约一半的结点，平均时间复杂度也是O(n)。小结：1、在顺序表上插入、删除一个结点，需要移动大量元素。2、具有随机访问的特点。,2.3 线性表的链式表示和实现 线性表的顺序表示的特点是用物理位置上的邻接关系来表示结点间的逻辑关系，这一特点使我们可以随机存取表中的任一结点，但它也使得插入和删除操作会移动大量的结点.为避免大量结点的移动，介绍线性表的另一种存储方式，链式存储结构，简称为链表。,2.3.1 线性链表 链表是指用一组任意的存储单元来依次存放线性表的结点，这组存储单元即可以是连续的，也可以是

11、不连续的，甚至是零散分布在内存中的任意位置上的。因此，链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息，这个信息称为指针或链。这两部分组成了链表中的结点结构：,其中：data域是数据域，用来存放结点的值。next是指针域（亦称链域），用来存放结点的直接后继的地址（或位置）。由于上述链表的每一个结只有一个链域，故将这种链表称为单链表。开始结点无前趋，应设头指针head指向开始结点。终端结点无后继，终端结点的指针域为空，即NULL（图示中也可用表示)。,例1、线性表:(bat，cat，eat，fat，ha

12、t，jat，lat，mat),单链表示意图,110,130,135,160,165,170,200,205,头指针head,head,bat,cat,eat,mat,单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名。,例如：若头指针名是head，则把链表称为表head,用C语言描述的单链表如下：,typedef struct LNode ElemType data;struct LNode*next;LNode,*LinkList;,假设p为指向结点的指针变量，则它通过标准函数生成的，即 p=(LNode*)malloc(sizeof(LNode);函数malloc分配了一个类型为L

13、Node的结点变量的空间，并将其首地址放入指针变量p中。一旦p所指的结点不再需要了，又可通过标准函数 free(p)释放所指的结点空间。,注意：三个概念：头结点的概念 头指针 首元结点,单链表的基本操作：一、查找运算 在单链表中，即使知道被访问结点的序号i，也不能象顺序表中那样直接按序号i访问结点，而只能从单链表的头指针出发，顺链域next逐个结点往下搜索，直到搜索到第i个结点为止。因此，链表不是随机存取结构。设单链表的长度为n，要查找表中第i个结点，仅当1=i=n时，i的值是合法的。,算法的平均时间复杂度：,a,b,步骤1：生成一个数据域为x的结点。,p,x,s,data,next,在线性表

14、的两个数据元素a和b之间插入一个数据元素x，已知p为其单链表存储结构中指向结点a的指针。,二、单链表的插入,用C语句描述为：s=(LNode*)malloc(sizeof(LNode);s-data=x;,a,b,步骤2：将数据元素x插在a和b元素之间。,p,data,next,a,b,p,x,s,data,next,用C语言描述为：s-next=p-next;p-next=s;,a,b,p,data,next,即：p-next=s;s-next=p-next;,s,注意语句的顺序，如改为以下顺序，什么情况会发生？,b结点的地址？,在带头结点单链表L中第i个位置之前插入元素e：,ai-1,ai

15、,p,j=0,a1,L,在带头结点单链表L中第i个位置之前插入元素e：,ai-1,ai,j=1,a1,p,L,在带头结点单链表L中第i个位置之前插入元素e：,p,j=,ai-1,ai,a1,L,在带头结点单链表L中第i个位置之前插入元素e：,j=i-1,ai-1,ai,a1,p,L,ai-1,ai,a1,p,e,s,L,关键语句：s=(LNode*)malloc(sizeof(LNode);s-data=e;s-next=p-next;p-next=s;,插入算法：Status ListInsert(LinkList,删除元素b：,a,b,p,c,data,next,b,三、单链表的删除,a,

16、b,p,c,data,next,b,删除元素b：,三、单链表的删除,a,b,p,c,data,next,b,用C语言语句描述为：p-next=p-next-next;,删除元素b：,三、单链表的删除,删除元素b并释放之：,a,b,p,c,data,next,b,步骤1：将b的地址记录下来 即：q=p-next;,q,a,b,p,c,data,next,b,删除元素b并释放之：,步骤2：让p-next指向b后第一个结点即：p-next=q-next;,q,a,b,p,c,data,next,b,删除元素b并释放之：,q,步骤3：释放b结点即：free(q),删除结点的算法：Status List

17、Delete(LinkList,小结,3、链式存储的优点：插入删除效率高,4、链式存储的缺点：访问某个数据效率低,1、在单链表上插入、删除一个结点，必须知道其前驱结点。,2、单链表不具有按序号随机访问的特点，只能从头指针开始一个个顺序进行。,2.3.2 循环链表循环链表：是一种头尾相接的链表。其特点是无需增加存储量，仅对表的链接方式稍作改变，即可使得表处理更加方便灵活。单循环链表：在单链表中，将终端结点的指针域NULL改为指向第一个结点，就得到了单链形式的循环链表，并简称为单循环链表。循环链表中也可设置一个头结点。这样，空循环链表仅有一个自成循环的头结点表示。如下图所示：,a1,an,.,he

18、ad,非空表,空表,在用头指针表示的单链表中，找开始结点a1的时间是O(1)，然而要找到终端结点an，则需从头指针开始遍历整个链表，其时间是O(n)。在很多实际问题中，表的操作常常是在表的首尾位置上进行，此时头指针表示的单循环链表就显得不够方便.如果改用尾指针rear来表示单循环链表，则查找开始结点a1和终端结点an都很方便，它们的存储位置分别是(rearnext)next和rear，显然，查找时间都是O(1)。因此，实际中多采用尾指针表示单循环链表。由于循环链表中没有NULL指针，故涉及遍历操作时，其终止条件就不再像非循环链表那样判断p或pnext是否为空，而是判断它们是否等于某一指定指针。

19、,2.3.3 双向链表 双向链表:在单链表的每个结点里再增加一个指向其直接前趋的指针域prior。这样形成的链表中有两个方向不同的链，故称为双向链表。形式描述为：typedef struct DulNode ElemType data;数据域 struct DulNode*prior;指向前驱元素的指针 struct DulNode*next;指向后继元素的指针 DulNode,*DuLinkList;,设指针p指向某一结点，则有：(pprior)next=p=(pnext)prior 即结点*p的存储位置既存放在其前趋结点*(pprior)的直接后继指针域中，也存放 在它的后继结点*(pne

20、xt)的直接前趋指针域中。,a1,an,.,head,非空表,空表,双向链表,a,b,x,p,q,在p所指结点前插入值为x的结点，应怎样修改指针？,q=(DulNode*)malloc(sizeof(DulNode);qdata=x;qprior=pprior;qnext=p;ppriornext=q;pprior=q;,a,b,p,c,双向链表中删除结点p，应怎样修改指针？,ppriornext=pnext;pnextprior=pprior;free(p);,注意：与单链表的插入和删除操作不同的是，在双链表中插入和删除必须同时修改两个方向上的指针。上述两个算法的时间复杂度均为O(1)。,2

21、.4 一元多项式的表示及相加,因此一元多项式：Pm(x)=p1xe1+p2xe2+.+pmxem可用线性表：(p1,e1),(p2,e2),(pm,em)表示,一元多项式：Pm(x)=p1xe1+p2xe2+.+pmxem可用系数线性表P表示:p=(p1,p2,pm)但对 S(x)=1+3 x 1000+2 x 2000 这样的多项式浪费空间系数线性表(1,0,0,3,0,0,2)可用非零系数指数线性表:(1,0),(3,1000),(2,2000),例：求两多项式的和多项式A(x)=7+3 x+9 x 8+5 x 17B(x)=8 x+22 x 7 9 x 8C(x)=A(x)+B(x)=7

22、+11x+22 x 7+5 x 17,A=(7,0),(3,1),(9,8),(5,17)B=(8,1),(22,7),(-9,8)C=(7,0),(11,1),(22,7),(5,17),结点：,一元多项式的链式存储结构,抽象数据类型PolynomialADT Polynomial 数据对象:D=ai|aiTermSet,i=1,2,m,m0 TermSet中的每个元素包含一个表示系数的实数和 表示指数的整数 数据关系:R1=|ai-1,ai D,且ai-1中的指数 值 ai 中的指数 值，i=2,n 基本操作:CreatPolyn(&p,m)DestroyPolyn(&p)PrintPolyn(p)PolynLength(p)AddPoly(&Pa,&pb)SubtractPolyn(&Pa,&Pb)MultiplyPolyn(&Pa,&Pb)ADT Polynomial,例：S(x)=1+3 x 1000+2 x 2000 的单链表存储示意图,pa,和多项式链表：,AddPolyn算法(类似于两个有序表的归并，仅有一些细微差别。）,设多项式A(x)，B(x)分别用带表头结点的单链表pa，pb表示，和多项式仍用带表头结点的单链表pa表示。,设p,q分别指向A,B中某一结点，p,q初值是第一结点,运算规则：,算法示意：,最后：,