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

数据结构 第二章 线性表 重庆一中 葛静 1 数据元素之间满足线性关系的表称为线性表，是一种最基本、最简单的 数据结构类型。本章讨论线性表的逻辑和存储结构、相关算法的实现以及线性 表应用举例。 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+1D, 1in-1 表长n=0时，L为空表；关系符在这里称为有序对，表示任意相邻的 两个元素之间的一种先后次序关系，称ai是ai+1的直接前驱, ai+1是ai的直接后继 ，当表长n1时，关系集R为空集。 2 例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的抽象数据类型表示： 学 号 姓 名性 别 年 龄班 级 - J99001丁兰女19计99- J99002王林男20计99- - J99032马红女18计99- a1 a2 a32 3 线性表的抽象数据类型表示 ADT List 数据元素集： D=ai|aidatatype,i=1,2, n,n0 数据关系集：R=|ai,ai+1D,1in-1 基本操作集：P(置表空、求表长、插入、删除、 查找一个元素等) 4 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, ai+1，存储位置也是相邻的；(2) 对ai的存取为随机存取或按地址存取。(3)存储密度高。存储密度D=(数据结构 中元素所占存储空间)/(整个数据结构所占空间)。 顺序表的不足：对表的插入和删除等运算的时间复杂度较差。 a1 a2 ai an 5 线性表的顺序存储 Type list=record vec:array1m0 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）检查存储空间是否已经满，若满，则“溢出”。 （2）检查i是否超范围1L.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.len+1; End; 算法复杂度分析：算法第1、2步根据情况可省略。时间复杂度主要取决于第3步 ，即for循环的次数，也就是向后移动的元素个数。当i=n+1时，最好情况,元 素不移动,当i=1时，最坏情况，移动n次。假定在线性表的任何位置上插入元 素的概率相同，为pi=1/(n+1),1n) 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) 8 线性表的抽象数据类型表示 5、删除给定值等于x的第一个元素。 算法步骤： （1）从线性表的起始元素开始，根X 比较，直到X等于某个元素值（查找 成功），或者查完所有元素仍找不到（查找失败）。 （2）若查找失败，则“没有找到”错误处理。 （3）删除其值等于x的元素。 （4）线性表长度减1； 算法描述： Delete(L,x); Begin 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) 9 线性表的操作 以上运算是对线性表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中，自定义函数 if not k then insert(La,x); end; 类似可写出求LaLb , LaLb等运算的算法。 1 3 5 7 La 5 7 9 11 Lb 10 线性表的操作 例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.vecj then delete(L,j)；delete函数表示从L中删除第j位上 的元素 end; 初始：L=（1，3，1，5，3，5，7） i j 结果：L=（1，3，5，7） 11 2.3 线性表的链式存储结构 线性表的顺序存储结构有存储密度高及能够随机存取等优点，但存在以 下几点不足：(1)插入、删除等运算耗时，且存在元素在存储器中成片移动的 现象；(2)要求系统提供一片较大的连续存储空间。 下面讨论线性表的链式存储结构，即链表。是第二章的重点。 2.3.1单链表 将线性表L=(a1,a2,an)中各元素分布在存储器的不同存储块，称为节 点，通过地址或指针建立它们之间的联系，所得到的存储结构为链表结构。表 中元素ai的节点形式如图2.4所示。 图2.4 其中，data域存放数据元素ai，而next域是一个指针，指向ai的直接后继ai+1所 在的节点。于是，线性表L=( a1,a2,an)的结构如图2.5所示: data next a1 a2 an L . 12 单链表 例2-4 设线性表L=(赵，钱，孙，李，周，吴，郑，王)，各元素在存储器中 的分布如图2.6所示。 地址dataNext 100李142 106钱钱112 112孙孙100 118王NULL 124吴136 130赵赵106 136郑郑118 142周124 图2.6 带头节点的单链表： a1 an L L 赵钱孙 吴郑王 周 李 13 单链表 节点描述：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 A： aiai+1 P 14 2.3.2单链表的基本操作 可调用pascal中new(p)函数向编译系统申请节点的存储空间，若说明： Var var p:link; new(p); 则获得了一个类型为node的节点，且该节点的地址已存入指针 变量P中： 1建立单链表 算法思路：依次读入L=(a1,.,an)中每一ai(设为整型)，若inil do if p.data1)的人出圈 ；。输出依次出圈的人的编号。M的值预先选 定，N由键盘输入。 n分析：要解决这道问题，首先需要构造一个环表，构 造环的方法很简单，只要存储每个人的下一个即可， 当然，最后一个人的下一个就是第一个人，这样就构 成了一个环，构造环以后，就可进行删除操作，直到 环剩下一个人为止。 21 约瑟夫问题(采用链表) write(m readln(m,n); 构造环-循环链表 for i:=1 to m do begin new(q); q.data:=i; p:=q;if i=1 then head:=q else p.next:=q; p:=q; if i=m then p.next:=head; end; 做出圈操作删除链表节点 p:=head; repeat for i:=1 to n-2 do p:=p.next ; 报数 q:=p.next; p.next:=p.next.next; 删除并且重新开始报数 writeln(q.data); 显示出圈人员信息 dispose(q); p:=p.next; 下一次开始报数 until p=p.next ; writeln(p.data); 显示最后出圈人 22 约瑟夫问题(采用数组) const max=100; var a:array 1max of intege