数据结构第二章线性表课件

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

2、特征 线性表L可用二元组形式描述： L= (D,R)数据元素集合: D=ai | aidatatype ,i=1,2, n ,n0关系集合: R= | ai , ai+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是表尾是表尾

3、,无后继；其它的每个元无后继；其它的每个元素素ai有且仅有一个直接前驱有且仅有一个直接前驱(ai-1)和一个直接后继和一个直接后继(ai+1)。2.1.3 线性表的抽象数据类型表示线性表的抽象数据类型表示 设线性表 L=(a1,a2, ,an)，对 L的抽象数据类型表示： 学 号 姓 名性 别 年 龄班 级 -J99001丁兰女19计99-J99002王林男20计99-J99032马红女18计99-a1a2.a32数据结构第二章线性表4线性表的抽象数据类型表示ADT List 数据元素集：D=ai|aidatatype,i=1,2, n,n0数据关系集：R=|ai,ai+1D,1in-1 基本

4、操作集：P(置表空、求表长、插入、删除、查找一个元素等) 数据结构第二章线性表52.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, ai+1，存储位置也是相邻的；(2)对ai的存取为随机存取或按地址存取。(3

5、)存储密度高。存储密度D=(数据结构中元素所占存储空间)/(整个数据结构所占空间)。顺序表的不足顺序表的不足：对表的插入和删除等运算的时间复杂度较差。 a1 a2 aian数据结构第二章线性表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个元素插入一个元素步骤： （1）检查存储空间是

6、否已经满，若满，则“溢出”。 （2）检查i是否超范围1=i=n+1,若是，则“超出范围” （3）将线性表中第i个元素和后面所有元素均后移一位。 （4）将新元素写在第i个位置上。 （5）线性表长度加1. a1 ai an数据结构第二章线性表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.ve

7、ci=x; L.len:=L.len+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）检查1=i=n,若不是，则“超出范围” （2）若删除的元素有用，则把第i个元

8、素赋值给变参带回。 （3）把第i个元素后面所有的元素前移一位。 （4）线性表长度减1。算法描述：Delete(L,i,x);Begin if(in) then writeln(out of range); x:=L.vexi; for j:=i+1 to L.len do 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、删除

9、给定值等于x的第一个元素。算法步骤： （1）从线性表的起始元素开始，根X 比较，直到X等于某个元素值（查找成功），或者查完所有元素仍找不到（查找失败）。 （2）若查找失败，则“没有找到”错误处理。 （3）删除其值等于x的元素。 （4）线性表长度减1；算法描述：Delete(L,x);Begin i:=1; while (i=n)and(L.vecix) 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线性表的操

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);begin var i,x:integer; k:boolean; for i:=1 to Lb.len do begin x:=Lb.veci; k:=locateLa,x;判断x是否在La中，自定

11、义函数 if not k then insert(La,x); end;类似可写出求LaLb , LaLb等运算的算法。 1 3 5 7La 5 7 9 11 Lb数据结构第二章线性表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 to L.len-1 do for j:=i+1 to L.len do if L.veci=L.ve

12、cj 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)要求系统提供一片较大的连续存储空间。下面讨论线性表的链式存储结构，即链表。是第二章的重点。2.3.1单链表单链表将线性表L=(a1,a2,an)中各元素分布在存储器的不同存储块，称为节点，通过地址或指针建立它们之间的联系，所得到的存

13、储结构为链表结构。表中元素ai的节点形式如图2.4所示。 图图2.4其中，data域存放数据元素ai，而next域是一个指针，指向ai的直接后继ai+1所在的节点。于是，线性表L=( a1,a2,an)的结构如图2.5所示: data next a1 a2 an L .数据结构第二章线性表13单链表例例2-4 设线性表L=(赵，钱，孙，李，周，吴，郑，王)，各元素在存储器中的分布如图2.6所示。 地址地址dataNext100李李142106钱钱112112孙孙100118王王NULL124吴吴136130赵赵106136郑郑118142周周124 图图2.6带头节点的单链表：带头节点的单链表

14、： a1 an L L赵赵钱钱孙孙吴吴郑郑王王周周李李数据结构第二章线性表14单链表节点描述：type link=node; node=record data:elemtype; next:link; end; 若说明var A:node; p:link; 则结构变量A为所描述的节点，而指针变量p为指向此类型节点的指针（或p的值为节点的地址），如图2.8所示: 设p指向链表中节点ai，如图2.9所示:获取ai，写作：p.data；而取ai+1,写作：p.next.data。 另外，若指针p的值为NULL，则它不指向任何节点, 此时取p.data或p.next是错误的。 data next P

15、A： aiai+1 P数据结构第二章线性表152.3.2单链表的基本操作可调用pascal中new(p)函数向编译系统申请节点的存储空间，若说明：Var var p:link; new(p); 则获得了一个类型为node的节点，且该节点的地址已存入指针变量P中：1建立单链表建立单链表算法思路算法思路：依次读入L=(a1,.,an)中每一ai(设为整型)，若i=n，则将ai形成一节点，链入表尾，最后返回链表的头节点指针H。算法描述算法描述：procedure create; var p,q,h:link; I,j:integer; begin i:=1;readln(x);new(p);p.da

16、ta:=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; data next P 数据结构第二章线性表16设L=(2，4，8)，则建表过程如下：设表长为n，显然此算法的时间复杂度为T(n)=O(n)。从此算法可以看到，链表的结构是动态形成的，即算法运行前，表结构是不存在的，而通过算法的运行，得到一个如图所示的单链表。2链表查找链表查找 在单链表中查找即实现GetElem(L,k)。算法思路算法思路：从表

17、头第一个结点起，依次使每个结点的关键字同给定的的值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; 建立单链表H248数据结构第二章线性表173前插前插 即实现ListInsert(L, i, e)。讨论将x插入表中节点ai之前的情况。算法思路算法思路：调用算法Get

18、Elem(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)，但插入时未引起元素的移动，这一点优于顺序结构的插入。Ha1ai anai-1Pe q数据结构第二章线性表18单链表删除4删除删除 即实现ListDel(L,i)。图图2.15 算法思路算法思路：同插入法，先调用函数GetElem(H,i-1),找到节点ai的前驱，然后如图2.15所示，

19、将节点ai删除之。算法描述算法描述：p.next:=q.next; dispose(q)同插入法，此算法的T(n)=O(n)。Ha0ai ai-1Pai+1q数据结构第二章线性表19线性表的存储结构n顺序存储结构顺序存储结构 用数组类型： list: array 1.max of elemtp ;n动态链式存储结构动态链式存储结构 用指针类型： point = p_list ; p_list = record data : elemtp ; next: point ; end;n静态链式存储结构静态链式存储结构type statinode=record data:elemtype; next:

20、integer; end; var a:array1.maxof statinode;abcdeacaebd54013bcde数据结构第二章线性表20比较一下方案逻辑结构物理结构特点无序数组无序线性表数组差无序链表链表插入快有序数组有序线性表数组查找快有序链表链表比较平衡数据结构第二章线性表21线性表的典型实例线性表的典型实例n约瑟夫问题约瑟夫问题nM个人围成一圈，从第一个人开始报数，数到个人围成一圈，从第一个人开始报数，数到N的人的人出圈；再由下一个人开始报数，数到出圈；再由下一个人开始报数，数到N(N1)的人出的人出圈；圈；.。输出依次出圈的人的编号。输出依次出圈的人的编号。M的值预先的值预先选定，选定，N由键盘输入。由键盘输入。n分析：要解决这道问题，首先需要构造一个环表，构分析：要解决这道问题，首先需要构造一个环表，构造环的方法很简单，只要存储每个人的下一个即可，造环的方法很简单，只要存储每个人的下一个即可，当然，最后一个人的下一个就是第一个人，这样就构当然，最后一个人的下一个就是第一个人，这样就构成了一个环，构造环以后，就可进行删除操作，直到成了一个环，构造环以后，就可进行删除操作，直到环剩下一个人为止。环剩下一个人为止。数据结构第二章线性表22约瑟夫问题(采用链表)write(m & n:); readln(m,n);