当前位置:首页 >> 学科竞赛 >> 第二章线性表

第二章线性表


第二章 线性表

顺序表和链表

1

第一节 线性表的逻辑结构
线性表的概念(Linear List) ? 表是由n(n≥0)个同一类型的元素(结点) a1,a2,…,an组成的有限序列。其中,元素的个 数n定义为表的长度。当n=0时称为空表。当 n≥l时,我们说元素ai位于该表的第i个位置, 或称ai是表

中第i个元素,i=1,2,…,n。
?

2页

?

根据各元素在表中的不同位置可以定义它 们在表中的前后次序。我们称元素ai在元素ai+1 之前或ai是ai+1的前驱(i=1,2,…,n-1)。同时, 我们也称元素ai+1在元素ai之后,或ai+1是ai的后 继。由于表的元素具有线性性质,所以又称为 线性表。

3页

常常将非空的线性表(n>0)记作:(a1,a2,……an) 。这里的数据元素ai(1<=i<=n)只是一个抽象的符号 ,其具体的含义在不同的情况下可以不同。每个数 据元素的具体含义,在不同的情况下各不相同,它 可以是一个数,或一个符号,也可以是一页书,甚 至其它更复杂的信息。例如由每个英文字母组成的 字母表: (A,B,C,……,Z) 是一个线性表,表中的数据元素是单个字母字符。 又如某校从1999年至2004年各种型号计算机的拥有 量的变化情况,可以用线性表的形式给出: (16,27,38,60,102,198) 表中的数据元素是整数。
4页

在稍复杂的线性表中,一个数据元素可以由若干个 数据项组成。在这种情况下,常把数据元素称为记 录,含有大量记录的线性表又称文件。 例如,一个学校的学生健康情况登记表如图2.1 所示,表中每个学生的情况为一个记录,它由姓名 、学号、性别、年龄、班级和健康状况等六个数据 项组成。

5页

线性表的运算 线性表是一个相当灵活的数据结构,它的长度可根据 需要增长或缩短,即对线性表的数据元素不仅可以进行 访问,还可进行插入和删除。对线性表进行的基本操作 有如下几种: 1、置空表SETNULL(L): 运算结果是将线性表L置成空 表 2、求长度LENGTH(L): 结果是线性表L的结点个数 3、取结点GET(L,i): 当1≤i≤LENGHTH(L)时,结果 是表L中的第i个结点。 4、定位LOCATE(L,x): 当线性表中存在一个值为x的 结点时,结果是该点的位置;若表L中存在多个值为x的 结点时,则是首次找到结点的位置。当表L中不存在值 为x的结点时,将给出一个特殊值表示值为x的结点不存 在。 6页

5、插入INSERT(L,x,i):在线性表的第i个位置插入一 个值为x的新结点,使得原编号为i,i+1…n的结点变 为编号为i+1,i+2…n+1的结点。这里1≤i≤n+1,而n是原 表的长度。 6、删除DELETE(L,i): 删除线性表L的第i个结点 ,使得原编号为i+1,i+2…n+1的结点变为编号为 i,i+1…n的结点。这里1≤i≤n,而n是原表L的长度。 对线性表还可进行—些更复杂的运算。如:将两 个或两个以上的线性表合并成—个线性表;把一个 线性表拆成两个或两个以上的线性表;重新复制一 个线性表;对线性表中的数据元素按其某个数据项 递增(或递减)的顺序进行重新排列(由此得到的线性 表称为有序表),等等。 7页

第二节 线性表的顺序存储结构
顺序表的定义 在计算机内,存储线性表的最简单和最自然的方 式,是把表中的数据元素一个接一个地放进一组连 续的存储单元之中,也就是说,把表中相邻的数据 元素存放在内存中邻接的存储单元里 。 假设线性表的每个元素需占用L个存储单元,并以 所占的第一个单元的存储地址做为数据元素的存储 位置。则线性表中第i+1个数据元素的存储位置 LOC(ai+1)和第i个数据元素的存储位置LOC(ai)之间满 足下列关系:
8页

LOC(ai+1)=LOC(ai)+L 一般来说,线性表的第i个元素ai的存储位置为: LOC(ai)=LOC(a1)+(i-1)* L 其中LOC(a1)是线性表的第—个数据元素a1的存 储位置,通常称做线性表的起始位置或基地址。 线性表的这种机内表示称做线性表的顺序存储 结构或顺序映象。用这种方法存储的线性表简称 为顺序表。其特点是:逻辑上相邻的数据元素, 它们的物理次序也是邻接的。

9页

换句话说,以元素在计算机内“物理位置相邻”来 表示线性表各数据元素之间的逻辑关系。每一个数 据元素的存储位置都和线性表的起始位置相差一个 和数据元素在线性表中的位序成正比的常数。由此 ,只要确定了存储线性表的起始位置,线性表中任 一数据元素都可随机存取,所以线性表的顺序存储 结构是一种随机存取的存储结构。

10页

线性表的顺序存储结构示意图
地址 b=LOC(a1) b+ L
b +(i-1)L

内容
a1 a2 …… ai ai+1 ……

元素在表中的位序
L 1

2
i i+1 n

b +(n-1)L

an

空闲区
b +(max-1)L
11页

一个一维数组M,下标的范围是0到9, 每个数组元素用相邻的5个字节存储。存储器 按字节编址,设存储数组元素M[0]的第一个 字节的地址是98,则M[3]的第一个字节的 地址是

113

解:地址计算通式为:
LOC(ai) = LOC(a1) + L *(i-1) 因此:LOC( M[3] ) = 98 + 5 ×(3-0) =113
12页

顺序表的描述:在pascal语言中可用一维数组描述顺 序表。
Const MaxLength=数组的最大长度,即表的最大单元数目; Type List = Record elem: Array [1..MaxLength] of elemtype; last: 0..MaxLength; End;

在上述描述中,线性表的顺序存储结构是一个记录 型的结构,其中数据域elem描述了线性表中的数据 元素占用的数组空间,数组的第i个分量为线性表中 第i个数据元素的存储映象,数据域last指示最后一 个数据元素在数组空间中的位置。此时,数据元素 的存储位置可用数组的下标值(即相对于线性表的起 始位置的值)来表示。 13页

顺序表的运算
?

在这种存储结构中,线性表的某些操作容易 实现。如:线性表的长度即为last域的值,等等。 下面着重讨论线性表的插入和删除两种操作。

14页

1. 插入

? 在顺序表的第i(1<=i<=n+1)个位置上,插入一个新 结点x,使长度为n的顺序表:(a1,…ai-1,ai,…,an)变 成长度为n+1的顺序表:(a1,…ai-1,x,ai,…,an)。

数据元素ai-1和ai之间的逻辑关系发生了变化。在线性 表的顺序存储结构中,由于逻辑上相邻的数据元素在 物理位置上也是相邻的,因此,除非i=n+l,否则必 须移动元素才能反映这个逻辑关系的变化。

15页

例如,图2.3表示一个线性表在进行插入操作的前 、后,其数据元素在向量空间中的位置变化。为了 在线性表的第4和第5个元素之间插入一个值为25的 数据元素,则需将第5个至第8个数据元素在向量空 间中依次往后移动一个位置。

16页

一般情况下,在第i(1<=i<=n)个元素之前插入一个元 素时,需将第n至第i(共n-i+1)个元素向后移动一个 位置。算法如下所示。
procedure sqinsert(var v:list;x,i:integer;); var j:integer; begin if (i<1) or (i>v.last+1) then writeln (‘position does not exist’) else if v.last>=maxlength then writeln (‘list is full’) else begin for j:=v.last downto i do v.elem[j+1]:=v.elem[j]; v.elem[i]:=x; v.last:=v.last+1 end end;

17页

说明: 算法sqinsert将位于i,i+1,…,last 中的元素分别移到 位置i+1,i+2,…,last+1 ,然后将新元素插入位置i。注 意算法中元素后移的顺序,必须从表中最后一个位 置开始后移,直至将位置i处的元素后移为止。如果 新元素的插入位置不合法,则输出错误信息,然后 终止程序。

18页

复杂性: 现在我们来分析算法的时间复杂性。这里问题的 规模是表的长度v.last,设它的值为n。显然该算法 的主要时间花费在for循环的元素后移上,该语句的 执行次数为n-i+1。由此可看出,所需移动元素位置 的次数不仅依赖于表的长度,而且还与插人的位置i 有关。当i=n+1时由于循环变量的终值大于初值,元 素后移语句将不执行,无须移动元素;若i=1,则元 素后移语句将循环执行n次,需移动表中所有元素。 也就是说该算法在最好情况下需要Ο(1)时间,在最 坏情况下需要Ο(n)时间。由于插入可能在表中任何 位置上进行,因此,有必要分析算法的平均性能。
19页

设在长度为n的表中进行插入运算所需的元素移动 次数的平均值为EIN(n)。由于在表中第i个位置上插 入元素需要的移动次数为n-i+1,故

其中,pi表示在表中第i个位置上插入元素的概率。 考虑最简单的情形即假设在表中任何合法位置i (1≤i≤n+l)上插入元素的机会是均等的,则:

从而,在等概率插入的情况下,

也就是说,用数组实现表时,在表中做插入运算,平 均要移动表中一半的元素,因而算法所需的平均时间 仍为Ο(n)。

2. 删除 ? 含义:将表的第i(1<=i<=n)个结点删去,使长 度为n的线性表(a1,…ai-1,ai,…,an) 变成长 度为n-1的线性表(a1,…ai-1,ai+1,…,an)。

数据元素ai-1和ai+1之间的逻辑关系发生变化,为 了在存储结构上反映这个变化,同样需要移动元 素。如图2.4所示,为了删除第4个数据元素.必 须将从第5个至第8个元素都依次往前移动一个位 置。
22页

图2.4 线性表删除前后的状况 (a)删除前n=8 ,(b)删除后n=7。
23页

一般情况下,删除第i(1<=i<=n)个元素时需将第i+1 至第n个(共n-i)元素依次向前移动一个位置,算法 如下所示。 procedure sqdelete(var v:list;i:integer); var j:integer; begin if (i<1) or (i>v.last) then writeln (‘no this element’) else begin for j:=i to v.last-1 do v.elem[j]:=v.elem[j+1]; v.last:=v.last-1 end end;

24页

复杂性 该算法的时间分析与插入算法类似,元素的移 动次数也是由表长n和位置i决定的。若i=n,则由 于循环变量的初值大于终值,前移语句将不执行 ,无须移动元素;若i=1,则前移语句将循环执行 n-1次,需要移动表中除删除元素外的所有元素。 因此,算法在最好情况下需要O(1)时间,而在最 坏情况下需要O(n)时间。

25页

删除运算的平均性能分析与插入运算类似。设在 长度为n的表中删除一个元素所需的平均移动次 数为EDE(N)。由于删除表中第i个位置上的元素需 要的移动次数为n-i,故

其中,pi表示删除表中第i个位置上元素的概率。 在等概率的假设下,

这时

也就是说用数组实现表时,在表中做删除运算, 平均要移动表中约一半的元素,因而删除运算所 需的平均时间为O(n)。

顺序表的优缺点 用数组来实现线性表时,我们利用了数组单元 在物理位置上的邻接关系来表示线性表中元素之 间的逻辑关系。由于这个原因,用数组来实现线 性表有如下的优缺点: 优点是: 1、无须为表示表中元素之间的逻辑关系增加额 外的存储空间; 2、可以方便地随机访问表中任一位置的元素。

28页

缺点是: 1、插入和删除运算不方便,除表尾的位置外, 在表的其他位置上进行插入或删除操作都必须移动 大量元素,其效率较低; 2、由于数组要求占用连续的存储空间,存储分 配只能预先进行静态分配。因此,当表长变化较大 时,难以确定数组的合适的大小。确定大了将造成 浪费,确定小了造成数组空间溢出。

29页

顺序表的应用举例
1. josephus问题 设有n 个人围坐在一个圆桌周围,现从第s个人 开始报数,报到第m的人出列,然后从出列的 下一个人重新开始报数,数到第m的人又出列 ,……,如此重复到所有的人全部出列为止。 P8 P1 P7 P6 P5 P2

P3
P4
30页

问题分析: josephus问题是:对于任意给定的n,s,m,求出 按出列次序得到的n个人员的顺序表 。 对于一序列p1 ,p2 ,...,pn ,我们可以用整数i来代 替pi ,将初始序列看成一个整数序列:1,2,3, ...n,并把它们存储在一个顺序表p中,pi出列即 是将p[i]从顺序表中删除,为节省存储空间 ,不 妨将p[i+1],...,p[n]的值上移一位置,在把p[i]的 值保留在p[n]中,然后对p[1],p[2],...,p[n-1]重 复上述过程。当p中只剩下一个元素没有出列时 ,就把它放在p[1]原处。这时的顺序表p中保存了 出列次序的逆序。
31页

JOSEPHUS问题程序
p[k]:=p[n-k+1]; p[n-k+1]:=w end; for i:=1 to n do {输出} begin write(p[i]:8); if (i mod 6)=0 then end; end. 输入示例: 8 1 4 输出示例: 4 8 5 2 1 3 7 6 writeln

32页

2、对任意给定的一个自然数n(n<=100),将分母小 于等于n的不可约分的真分数按上升的次序排序, 并且在第一个分数前加上0/1, 而在最后一个分数 后加上1/1,这个序列称为n级法雷序列,以Fn表示. 例如,F8为: 0/1,1/8,1/7,1/6,1/5,1/4,2/7,1/3,3/8,2/5,3/7, 1/2,4/7,3/5,5/8,2/3,5/7,3/4,4/5,5/6,6/7,7/8,1/1. 编程求出n级法雷序列,每行输出10个分数.

33页

问题分析:由于程序要求以分数的形式输出法雷 序列,对每个真分数必需分别存放其分子分母, 这就要用两个线性表来实现。开始时线性表中只 有两个元素,分别是0/1和1/1,线性表用两个数组 fp[1..n]和fq[1..n]来表示,fp[1..n]存放分子, fq[1..n]存放分母。所有的真分数用一个两重循环 来产生,每次将当前产生的真分数p/q插入到线性 表中去。

34页

为了保证线性表中在插入新元素后仍然按从小到大 的次序排列,首先要从表中找出第一个不小于p/q 的元素,如果该元素等于p/q,则说明p/q是可约的 真分数,p/q无需插入,否则p/q应插入在表中第一 个大于它的元素的位置。当向线性表中插入新元素 时,插入新元素之前要将从插入位置直到最后的所 有元素都后移一位,然后再插入新元素。删除线性 表中元素时,只要将从删除位置之后的那个元素直 到最后的所有元素都前移一位即可。由于对实数要 避免等或不等的比较,程序中在对两个分数进行比 较时,将它们化成了乘式进行。

35页

end. [运行程序]下划线表示输入 Input n:15 0/1 1/7 3/11 5/12 5/9 7/10 5/6 13/14 1/15 2/13 2/7 3/7 4/7 5/7 11/13 14/15 1/14 1/6 3/10 4/9 7/12 8/11 6/7 1/1 1/13 2/11 4/13 5/11 3/5 1/12 1/5 1/3 6/13 8/13 3/4 7/8 1/11 3/14 5/14 7/15 5/8 1/10 2/9 4/11 1/2 7/11 1/9 1/8 1/4 5/13 7/13 2/3 2/15 4/15 2/5 6/11 9/13 4/5 11/12 9/11 12/13

3/13 3/8 8/15 9/14 7/9

11/15 13/15

10/13 8/9

11/14 10/11

9/10

36页

3、多项式加法。编制一程序实现两个整系数一元 多项式的加法。 例如两个多项式为:2x6+4x3-7x4+1 和 50x2+4x+1 结果:2x6-7x4+4x3+50x2+4x+2 程序要求:键盘输入多项式的各项系数和指数 。每项系数和指数为一组数据(系数和指数之一 可以为零),以‘0 0’结束一个多项式的输入。

37页

上例第一式输入为: 2 6 4 3 -7 4 1 0 0 0 要求结果按降幂排序,同类项要合并,上例输出 结果如下: 2x^6-7x^4+4x^3+50x^2+4x+2 注:指数最大不超过30 分析:我们用数组c1,c2分别存两个多项式系数 ,下标就是指数。例如5x3表示为c1[3]:=5;
38页

参考程序: var co,ex,max1,max2,max_ex,i:integer; c1,c2,c:array[0..30] of integer;{存放数组} begin max1:=0; repeat write('enter eof & exp of 1:'); readln(co ,ex);{co为系数,ex为指数} if max1<ex then max1:=ex;{max1记录第一个多项式指数最高项} if co<>0 then c1[ex]:=co;{下标是指数,内容为系数} until (co=0) and (ex=0); max2:=0; writeln; repeat write('enter eof & exp of 2:');{读入第二个多项式} readln(co ,ex); if max2<ex then max2:=ex;{max1记录第二个多项式指数最高项} if co<>0 then c2[ex]:=co; until (co=0) and (ex=0); if max1<max2 then max_ex:=max2 {max_ex记录指数最高的项} else max_ex:=max1; for i:=0 to max_ex do {两个多项式相加} c[i]:=c1[i]+c2[i]; writeln;

39页

第三节 线性表的链式存储结构
链式存储引入 ? 实现表的另一种方法是用指针将存储表元素 的那些单元依次串联在一起。这种方法避免了 在数组中用连续的单元存储元素的缺点,因而 在执行插入或删除运算时,不再需要移动元素 来腾出空间或填补空缺。然而我们为此付出的 代价是,需要在每个单元中设置指针来表示表 中元素之间的逻辑关系,因而增加了额外的存 储空间的开销。
?

40页

?

用一组任意的存储单元来存放线性表的结点,这组 存储单元可以是连续的,也可以是不连续的,甚至是零 散分布在内存中的任何位置上。因此,链表中结点的逻 辑次序和物理次序不一定相同。为了能正确表示结点间 的逻辑关系,在存储每个结点值的同时,必须存储指示 其后继结点的地址(或位置)信息,这个信息称为指针 或链。 结点结构:

?

Data 数据域

link

指针域 (链域)

41页

例如,如果表是a1,a2,…,an ,那么含有元素ai的那个 单元中的指针应指向含有元素ai+1的单元(i=1,2,…,n1)。含有an的那个单元中的指针是空指针nil。此外 ,通常我们还为每一个表设置一个表头结点head, 其中的指针指向开始元素中所在的单元,但表头单 元head中不含任何元素。设置表头单元的目的是为 了使表运算中的一些边界条件更容易处理。这一点 我们在后面可以看到。

42页

上述这种用指针来表示表的结构通常称为单链接表 ,或简称为单链表或链表。通常我们把链表画成用 箭头相链接的结点的序列,结点之间的箭头表示链 域中的指针。这是因为在使用链表时,关心的只是 它所表示的线性表中数据元素之间的逻辑顺序,而 不是每个数据元素在存储器中的实际位置。单链表 的逻辑结构如图2.6所示。表示空表的单链表只有一 个单元,即表头结点head,其中的指针是空指针nil 。

图2.6 单链表示意图
43页

例 线性表 (ZHAO,QIAN,SUN,LI,ZHOU,WU,ZHENG,WANG)

存储地址
头指针 H 31 1 7 13 19 25 31 37 43

数据域 LI QIAN SUN

指针域 43 13 1

WANG WU ZHAO ZHENG ZHOU

NIL 37 7 19 25

H ZHAO ZHOU QIAN SUN ZHENG

LI
WANG

WU

^ 44页

单链表的描述 由上述可见,单链表可由头指针唯一确定,在 Pascal语言中可用“指针”数据类型来描述。单链 表结构的主要类型可形式地定义为: Type point=^node;{定义指针类型} node=record data:datatype{数据域} link:point; {指针域} end; Var head :point;{定义指针类型变量} 假设head是point型的变量,则head为单链表的头指针 ,它指向表中第一个结点。若head为“空”(head= NIL),则所表示的线性表为“空“表,其长度n为“ 零”。 45页

单链表的运算
建立单链表
1.头插法建表 从一个空表开始,重复读入数据,生成新结 点,将读入数据存放到新结点的数据域中,然后 将新结点插入到当前链表的表头上,直到读入结 建立过程如图2.7所示: 束标志为止。

46页

头插入算法(先进后出)

算法描述:{头插法建立单链表,head为头指针,x为插入的值} var head,s:point; x:real; begin new(head); head^.link:=nil;{head指针初始化} read(x); write(x:6:1); while x>=0 do {建立一个正数单链表} begin new(s); {动态申请一个地址} s^.data:=x; s^.link:=head^.link;{s^.link指向head^.link所指的结点(1)} head^.link:=s;{把head^.link指针指向s结点(2)} read(x); {读入下一个结点} write(x:6:1);

47页

2.尾插法建表(先进先出) 该方法是将新结点插到当前链表的表尾上, 为此必须增加一个尾指针r,使其始终指向当前 链表的尾结点。建立过程如图2.8所示:

48页

尾插法算法(先进先出)

{尾插法建立单链表,head为头指针,x为插入的值,r始终指向尾结点} var head,r,s:point; x:real; begin new(head);{初始化头指针} head^.link:=nil; r:=head; read(x); write(x:6:1); while x>=0 do {建立一个正数的单链表} begin new(s); {动态申请一个指针s} s^.data:=x;

49页

建立单链表的过程就是一个动态生成链表 的过程。即从“空表”的初始状态起,依次 建立各元素结点,并逐个插入链表。所以其 时间复杂度为O(n)。

50页

查找运算
在单链表中进行查找 ,可以查找链表中的第i 个结点(1<=i<=n),可以查找具有特定值的结点。 链表与顺序表不同,链表中结点的地址不能通过 公式计算出来,必须从表头开始顺着链表查找。

51页

1. 按序号查找
1. 按序号查找 在单链表中,取得第i个数据元素必须从头指针出发寻找,因 此,单链表是非随机存取的 存储结构。 procedure lfindi( var head:point;i:integer;var p:point); {head 为链表中的头指针,查找结束时第i个结点的地址在p中,或者 说,p指向第i个结点} var j:integer; begin p:=head^.link;{p指向第一个结点}

复杂度

时间复杂度 为O(n)
52页

2. 按值查找

时间复杂度 按值查找是在链表中,查找是否有结点值等于给定值 x 为O(n) 的结点,若有的话则返回首次找到的其值为x的结点的存储 位置;否则返回NULL。 复杂度
2. 按值查找 按值查找是在链表中,查找是否有结点值等于给定值 x的结 点,若有的话则返回首次找到的其值为x的结点的存储位置。 procedure lfindx(var head:point; x:real;var p:point); {head 为头指针,x为给定值,p指向查找结束时具有x值的结点} begin p:=head^.link; while(p<>nil) and(p^.data<>x) do p:=p^.link; if p=nil then writeln('No this data in the list') else writeln('Data has been found') end;
53页

插入运算
?

?
?

?
?

在单链表中可以实现以下三种插入操作: (1)在某节点a的节点之前(后)插入一个新 节点。 (2)在第i与i+1个节点之间插入一个新节点。 (3)在递增(减)有序表插入一个新节点, 使得生成长度为n+1的表仍是有序的。 这里我们讨论第二种情况的完整算法:

54页

假设我们要在单链表的第i与i+1个节点之间插入一个 数据元素x,假设p为单链表中指向第i个结点的指针 。如图2.9(a)所示。为插入数据元素x,首先要生成一 个数据域为x的结点,然后插入在单链表中,根据插 入运算的逻辑定义,需要修改第i个结点中的指针域 ,令其指向结点x,而结点x中的指针域应指向第i+1 个结点,从而实现三个元素之间逻辑关系的变化。插 入后的单链表如图2.9(b)所示。

55页

假设s为指向结点x的指针,则上述插入算法可以描 述如下:
procedure inslinkst(x:real;i:integer;var head:point); {在以head为头指针的链表的第i结点之前插入数据为x的结点,该链表带 有表头结点} var j:integer; p,s:point; begin new(s); {动态申请指针} s^.data:=x;{生成数据为x的结点} p:=head^.link;{从第一个结点开始} 时间复杂度 j:=1; {p指向表头结点,计数器j赋初值} 为O(n) while (p<>nil) and (j<i-1) do begin p:=p^.link; j:=j+1; end;{查找第i-1个结点,并用指针p指向i-1} 复杂度 if p<> nil then{查找到插入位置} begin s^.link:=p^.link;{用s^.link替换p^.link}

56页

删除运算
删除运算依据不同的需要可以写出多种算法: (1)删除数据为x的结点。 (2)删除第i个结点。 这里我们讨论删除结点数据为x的完整算法: 如图2.10所示若要删除单链表中元素b,在单链表 中实现元素a、b和c之间逻辑关系的变化,仅需修改 结点a的指针域即可。假设p为指向结点a的指针,则 上述插入算法可以描述如下:

57页

算法:

procedure dellinkst(b:real;var head:point); {删除带头结点的单链表中数据为b的结点,head为单 链表的头指针} var p,r:point; begin r:=head^.link; while(r<>nil) and (r^.data<> b) do begin p:=r; {p指向a的直接前驱} r:=r^.link {r指向结点b} end;{查找数据为b的结点} if r<> nil then begin p^.link:=p^.link^.link;{或p^.link: =r^.link也可以实现}

时间复杂度 为O(n)
58页

?

插入和删除运算的时间复杂度均为O(n), 这是因为链式存储结构不是随机存储结构。因 此,虽然在链表中插入或删除元素时不需要移 动元素,但为了找到表中元素,仍需执行时间 复杂度为O(n)的查找运算。

59页

循环链表
?

我们在用指针实现表时,表中最后一个元素 所在单元的指针域(link)为空指针nil。如果将这 个空指针改为指向表头单元的指针就使整个链 表形成一个环。这种首尾相接的链表称为循环 链表。在循环链表中,从任意一个单元出发可 以找到表中其他单元。

60页

?

图2.11所示的是一个单链的循环链表或简称为 单循环链表。

head

a1

an

(a)非空表

(b)空表
61页

在单循环链表上实现表的各种运算的算法 与单链表的情形是类似的。它们仅在循环终止 条件上有所不同:前者是p或p^.link指向表头单 元,即p^.link=head;后者是p或p^.link指向空 (nil),即p^.link=nil ? 循环链表是一种首尾相接的链表。其特点 是无须增加存储量,仅对表的链接方式稍作改 变,即可使得表处理更加方便灵活。
?

62页

循环链表应用举例
?

约瑟夫问题:有n个猴子,按照顺时针方向围成 一圈,选大王。从第1号开始报数1,2,3...,数到m 号时该猴子退出到圈外,如此报数直到圈内只剩 下一个猴子时,则此猴子便是大王.由键盘输入 n,m,打印最后出圈(大王)的猴子序号. n 1 n-1 … … 2

3
4
63页

问题分析:由于猴子坐成一圈,所以可以用循环链表来表 示这n个猴子,则算法的实质就是循环链表的删除操作. ? (1) N 个猴子按序号围坐一圈,即第 1 个猴子后是第 2 个猴子......第N 个猴子后继猴子是第 1 个猴子,形成循 环链表的结构, 所以可采用循环链表表示这 N 个猴子; ? (2) 每一个结点有两个域: 数据域─→猴子的编号, 指 针域─→指向下一个猴子的地址; ? (3) 报数 : 即数猴子个数, 每当数到 M 时, 则该号猴子 走出圈内──→删除该结点, 输出猴子号 ; ? (4) 重复 (3)过程, 直到只有一个猴子为止。
?

64页

第四节 双链表
双链表的定义 ? 在单向链表中,结点的域中只有一个指针域, 该指针域用于指向后继元素的地址,靠一个指 针将线性表连接起来。然而在处理某些问题中, 需要有双向指针将前后的相关结点联系起来, 这种用两个指针域将线性表的结点连接起来的 链表称为双向链表。
?

65页

?

每个结点的两个指针,一个指针指向它的前趋 结点,另一个指针指向它的后继结点。双链表 的结点结构如图2.12所示:

66页

?

这种形式的链表中有两条方向不同的链,故称 之为双向链表,简称为双链表。如图2.13所示:

67页

?

根据定义双链表的单元类型可以描述如下:

type pointer=^nodetype; nodetype=record data:datatype; pre,next:pointer; {pre指向前趋,next指向后继} end; var head,p,q,r:pointer;

68页

?

和单链表类似,双链表一般也是由头指针head 唯一确定的,增加头结点也能使双链表上的某 些运算变得方便,将头结点和尾结点链接起来 也能构成循环链表,并称之为双向循环链表。 双向循环链表:最后一个结点的next指针指向 头结点,且头结点的pre指针指向最后一个结点。 如图2.14:

69页

双链表的运算
?

在双向链表中,有些操作如:比求长度、 查找等操作仅需涉及一个方向的指针,则它们 的算法描述和单链表的操作相同,但在插入、 删除时有很大的不同,在双向链表中需同时修 改两个方向上的指针,下面仅以双向循环链表 为例给出三种基本运算的实现。

70页

1、构造循环双向链表算法
procedure creat_dulist(var head:pointer); begin new(head);head^.next:=head;head^.pre:=head;q:=head;{建立 空链表} read(a); while a>0 do {建立循环双链表} begin new(p); p^.data:=a;q^.next:=p; p^.pre:=q; q:=p; read(a) end; q^.next:=head;head^.pre:=q; {首尾相接} end;

71页

?

2、图2.15给出双向链表的插入过程。

72页

算法如下:
Procedure insert(head:pointer;i,x:integer); {在双向链表的第i个结点之前插入x} Var s,p:pointer;j:integer; Begin New(s); s^.data:=x; p:=head; j:=0; while (p^.next<>head) and (j<i) do begin p:=p^.next; j:=j+1; end; {p指向第i个结点} if i<>j then writeln('no this position!') else begin {将结点S插入到结点P之前} s^.pre:=p^.pre; {将S的前趋指向P的前趋(1)} p^.pre^.next:=s; {将P的本来前趋结点的后继指向S(2)} s^.next:=p; {将S的后继指向P(3)} p^.pre:=s; {将S作为P的新前趋(4)} end; End;

73页

?

3、 图2.16给出双向链表的删除过程。

74页

算法如下:
Procedure delete(head:pointer;i:integer); {删除双向链表的第i个结点} Var p:pointer;j:integer; Begin p:=head; j:=0; while (p^.next<>head) and (j<i) do begin p:=p^.next; j:=j+1; end; {p指向第i个结点} if i<>j then writeln('no this position!') else begin {将结点P删除} p^.pre^.next:=p^.next; {P的前趋结点的后继赋值为P的后继(1)} p^.next^.pre:=p^.pre; {P的后继结点的前趋赋值为P的前趋(2)} dispose(p); end; End;

显然,这三 种算法平均 时间复杂度 为O(n)。

75页

双链表的应用举例 此题实质是双向循环
链表的插入和删除操 ? 模拟一个民航定票系统:该系统中有一张用双 作 重链表表示的乘客表,表中的结点按乘客的姓 名(拼音字母)顺序链接。编一个程序模拟乘 客订票或退票。 ? 设该链表的每个结点如 下图所示:

76页

第五节 顺序表和链表的比较
1.基于空间的考虑

? 顺序表的存储空间是静态分配的,在程序执 行之前必须明确规定它的存储规模。估计过 大将造成空间浪费,估计太小将使空间溢出 机会增多。
? 静态链表中,初始存储池虽然也是静态分配 的,但若同时存在若干个结点类型相同的链 表,则它们可以共享空间,使各链表之间能 够相互调节余缺,减少溢出的机会。
77页

?

动态链表的存储空间是动态分配的,只要 内存空间尚有空闲,就不会产生溢出。当规模难 以估计时,采用动态链表为益。 ? 在链表中的每个结点,除了数据域外,还要 额外设置指针(或游标)域,从存储密度来讲是 不经济的。 存储密度是指结点数据本身所占的存储量和 整个结点结构所占的存储量之比,即 存储密度=(结点数据本身所占的存储) /(结点结构所占的存储总量)
78页

2. 基于时间的考虑

?

顺序表是由向量实现的,它是一种随机 存取结构,对表中任一结点都可在O(1)时间 内直接地存取,而链表中的结点,需从头指 针起顺着链扫描才能取得。因此,若线性表 的操作主是进行查找,很少做插入和删除操 作时,用顺序表为宜。 在链表中的任何位置上进行插入和删除, 都只需修改指针。对于频繁进行插入和删除 的线性表,宜采用链表做为存储结构。
79页

?

3. 基于语言的考虑 对于没有提供指针类型的高级语言, 若要采用链表结构,则可以使用游标实现 的静态链表。虽然静态链表在存储分配上 有不足之处,但它是和动态链表一样,具 有插入和删除方便的特点。 即使是对那些具有指针类型的语言, 静态链表也有其用武之地,特别是当线性 表的长度不变,仅需改变结点间的相对关 系时,静态链表比动态链表可能更方便。
本章完
80页


更多相关文档:

第二章线性表

第二章线性表 1.什么是顺序存储结构?什么是链式存储结构? 线性表的顺序存储指的是用一组地址连续的存储单元依次存储线性表的数据元 素, 它的特点是, 线性表中...

第二章 线性表(答案)

线性表中任何一个元素有且仅有一个直接后继 7.线性表是具有 n 个()的有限序列( n≠ 0) ( A) 表元素( B) 字符( C) 数据元素二、判断题 1.线性表的...

第二章 线性表

第二章 线性表 线性表的判断题 1.线性表的链接存储, 表中元素的逻辑顺序与物理顺序一 定相同。 ( )答案 选择题部分 1.一个线性表第一个元素的存储地址是 ...

第二章 线性表

第二章 线性表_工学_高等教育_教育专区。第二章 线性表 一 选择题 下述哪一条是顺序存储结构的优点?(?(A 1.下述哪一条是顺序存储结构的优点?(A ) A....

第二章 线性表作业参考答案

第二章 线性表 2.2 何时选用顺序表、何时选用链表作为线性表的存储结构为宜? 答: 在实际应用中,应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储...

第二章 线性表

第二章 线性表_理学_高等教育_教育专区。第二章 线性表一、选择题 1、若长度为 n 的线性表采用顺序存储结构,在其第 i 个位置插入一个新元素算法的时间复 杂...

第二章线性表

第二章线性表_数学_自然科学_专业资料。定义与名词解释: 线性表、顺序表、链表、静态链表。 习题集—基础知识 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.9 一、...

数据结构练习题 第二章 线性表 习题及答案

建表 7.字符串 8.串 9.顺序串 10.链串 二、填空题 1.为了便于讨论,有时将含 n(n>=0)个结点的线性结构表示成(a1,a2,……an),其中每 a a i 个 ...

第二章 线性表

第二章 线性表_电脑基础知识_IT/计算机_专业资料。第二章线性表一、单项选择题 1.线性表是___。 A.一个有限序列,可以为空 B.一个有限序列,不可以为空 C...
更多相关标签:
数据结构第二章线性表 | 线性表 | 线性表的顺序存储结构 | 线性表的基本操作 | 线性表的链式存储结构 | c 线性表 | 数据结构线性表 | 线性表和链表的区别 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com