当前位置:首页 >> 学科竞赛 >>

广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 02线性表教案


§2
§2.1 线性表的定义及其基本运算

线性表

线性表是 n 个数据元素(结点)a1,a2,??,an 组成的有限序列。其中数据元素的个数 n 定义为表的长度。当 n=0 时称为空表。 线性表的常用的运算: (1)置空表。 (2)求线性表 L 的长度。 (3)取表中的第 i 个结点 (4)按值查找。 (5)插入:在表 L 的

第 i 个位置上插入新的结点 X。 (6)删除:删除表 L 的第 i 个结点。 线性表可采用两种存储结构:顺序存储和链式存储。 §2.2 线性表的顺序存储结构

它的特点是逻辑上相邻的结点其物理位置亦相邻,下标可以看成是结点的相对地址。 · 运算: 1) 插入 用顺序表作为线性表的存储结构时,由于结点的物理顺序必须和结点的逻辑顺序保持 一致, 因此我们必须将表中位置 n,n-1,...,i 上的结点依次后移到位置 n+1,n,...,i+1 上, 腾出第 i 个位置,然后在该位置上插入新结点 x。仅当插入位置 i=n+1 时,才无须移动结 点,直接将 x 插入表的末尾。

2)删除 在顺序表上实现删除运算也必须移动结点,才能反映出结点间逻辑关系的变化。仅当 i=n,才能简单地删除终端结点,无须移动结点;

3)取表 S 中的第 i 个结点: 直接以 S[i]表示 4) 查找 须顺序取出表中元素逐一比较

· 顺序表有如下优缺点: 优点: (1)无须为表示结点间的逻辑关系而增加额外的存储空间; (2)可以方便地随机存取表中的任一结点。 缺点: (1)插入和删除运算不方便,除表尾的位置外,在表的其它位置上进行插入和删除操作 都必须移动大量的结点,其效率较低; (2)由于顺序表要求占用连续的存储空间,存储分配只能预先进行(静态分配) ,因此 当表变化较大时,难以确定合适的存规模,若按可能达到的最大长度预先分配表 空间,则可能造成一部分空间长期闲置而得不到充分利用,若事先对表长估计不 足,则插入操作可能使表长超过预先分配的空间而造成溢出。 §2.3 线性表的链式存储结构

从链接方式上可分为:单链表、循环链表和双链表。 1)单链表 2)循环链表 3)双链表 §2.3.1 单链表基本运算

一、建立单链表 建立链表就是要在表中逐一增加新的结点。为此,必须反复执行下列步骤: i)使用过程 NEW,获得新的存储单元; ii)读入新结点分量的数据域 iii)将指针向后推移,跟踪链表的增长到链表的长度满足要求为止。 (1)头插法建表 该方法从一个空表开始,重复读入数据,生成新结点,将读入数据存放到新结点的 数据域中,然后将新结点插入到当前链表的表头上,直至读入结束标志为止。

【练习 1】 :完成下面的程序 {逐个输入字符型数据,以 '$' 为结束符,用头插法建立单链 表} program lian; type point=^node; node=Record data:char;

next:point; end; var Ch : char; Head, S, R : point; begin Head := nil; {将单链表置为空表} read(Ch); {读入第一个结点的值} while (Ch <> '$') do begin new(S); {生成新结点 S} {将读入数据放到新结点的数据域中} {将新结点插入链表的表头上} read(Ch) ; end; end. (2)尾插法建表 该方法从一个空表开始,重复读入数据,生成新结点,将读入数据存放到新结点的 数据域中,然后将新结点插入到当前链表的表尾上,直至读入结束标志为止。为此必须 增加一个尾指针 R,使其始终指向当前链表的表尾上。 {读入下一个结点的值}

【练习 2】 :完成下面的程序 {尾插法建立单链表 Head,数据说明如前} begin Head := nil; {将链表 Head 置为空表} R := nil; {尾指针初值为空} read(Ch); {读入第一个结点的值} while (Ch <> '$') do begin {'$'为输入结束符} new(S); {生成新结点 S} {将读入数据放到新结点的数据域中} If (Head = nil) then {新结点 S 插入空表} else {S 插入非空表尾结点 R 之后} {尾指针 R 指向新的表尾} read(Ch); {读入下一个结点的值} end; If (R <> nil) then {R = nil 时是空表} R^.next = nil; {将非空表的终端结点的指针域置空}

end;

☆ 头结点: 如果我们在链表的开始结点之前附加一个结点,并称它为头结点,那么会带来以下两 个优点: (a)由于开始结点位置被存放在头结点的指针域中,所以在链表的第一个位置上的操 作就和在表的其它位置上的操作一致,无须进行特殊处理; (b)无论链表是否为空,其头指针是指向结点的非空指针(空表中头结点的指针域为 空) ,因此空表和非空表的处理也就统一了。

图:带头结点的单链表 Head 二、查找运算 (1)按序号查找 在带头结点的单链表 Head 中查找第 i 个结点(0≤i≤n), 若找到则输出该结点的数 据域,否则输出’none’。 begin P := Head; j := 0; {从头结点开始扫描} while ((P^.Next<>nil) and (j < i)) do begin P := P^.Next; {扫描下一个结点} j:= j+1; {计数器累计扫描过的结点数} end; If (i = j) then writeln(P^.data); {找到了第 i 个结点} else writeln(‘none’); {i < 0 或 i > N 时找不到第 i 个结点} end; (2)按值查找 在带头结点的单链表 Head 中查找其结点值等于 Key 的结点, 若找到则返回该结点的 位置 P;否则返回 nil begin P := Head^.next; {从开始结点起比较} while ((P <>nil) and (P^.Data <> Key)) do P := P^.Next; {继续往下扫描} return(P);

end; 三、插入运算 (1)后插操作:将值为 X 的新结点插入 P 之后 【练习 3】 :完成下面的程序 begin new(S); S^.Data := X ;

{给新结点 S 赋值 X} {将 S 插入 P 之后}

end;

(2)前插操作:在带头结点的单链表中,将值为 X 新结点插入 P 之前(上图) begin new(S); S^.Data := X; Q := Head; {从头指针开始} while (Q^.Next <> P) {查找 P 的前趋结点 Q} Q := Q^.Next; S^.Next := P; Q^.Next := S; {将新结点 S 插入 P 之前} end; 四、删除运算 删除 P 的后继结点 R

begin R := P^.Next; P^.Next := R^.Next; dispose(R);

{将结点*R 从链上摘下} {设放结点*R}

end;

【练习 4】 :完成下面的程序 试写一算法实现在单链表中删除多余的、值相同的结点。在单链表上实现时,用指针 P 指向当前将变为无重复值的结点, 指针 R 用来扫描 P 的后继结点, 并且用指针 Q 始终指向 R 的前趋。当*R 的值和*P 的值相同时,删去 R,即 Q 的后继,具体算法如下: procedure PURGE2 (var L:point); {在不带头结点的单链表中删除多余的、值相同的结点} var P , Q , R : point; begin P := L; while ((P <> nil) and (P^.Next <> nil)) do begin {P 不空且 P 不是终端结点} Q := P; R := P^.Next; {从 P 的后继开始扫描} while (R <> nil) do If (P^.Data = R^.Data) then begin Q^.Next := R^.Next; dispose(R); {删去结点 R} {R 指向被删结点的后继} end else begin R := R^.Next; end; end; end; {继续扫描}

练习参考答案: 练习 1: S^.data:=ch; S^.next:=head; 练习 2: S^.data:=Ch; Head:=S 练习 3: S^.next:=P^.next; P^.next:=S; 练习 4: R:=Q^.next; Q:=R;

Head:=S;

R^.next:=S; R:=S;

§2.3.2

循环链表(Circular Linked List)

是有一种首尾相接的链表。其特点是无需增加存储量,仅对表的链接方式稍作改变, 即可使得表处理更加灵活。 (1) 单循环链表:在单链表中,将终端结点指针域 nil 改为指向表头结点或开始结点,就得 到了单链表形式的循环链表:

(2) 双链表(Double Linked List):可以在单链表的每一个结点里再增加一个指向其前趋的 指针域 Prior。这样链表中有两条不同方向的链。 结构定义: type point=^DNode; Dnode=record Data : real; Prior, Next : point; end;

在带头结点的双链表中,将值为 X 的新结点插入 P 之前: new(S); S^.Data := X; S^.Prior := P^.Prior; S^.Next := P; P^.Prior^.Next := S; P^.Prior := S; 删除双链表结点 P:

P^.Prior^.Next := P^.Next; P^.Next^.Prior := P^.Prior; dispose(P); 【综合练习】 1.约瑟夫问题(ysf.pas)

n 个人围成一个圆圈,首先第 k 个人从 1 开始一个人一个人顺时针报数, 报到第 m 个人, 令其出列。然后再从下一个人开始,从 1 顺时针报数,报到第 m 个人,再令其出列,?,如此
下去, 直到圆圈中只剩一个人为止。此人即为优胜者。 输入:n、m、k 输出:优胜者的序号 2.多项式相加、减、乘 (dxs.pas) 编程进行多项式的加、减、乘的运算。 输入: (从文件 dxs.in 读取) 第一行: c (c 为字符:’+’、’-‘ 或 ’ * ‘ ) ,表示所要进行的操作 第二行: (多项式 A)最高项的系数 最高项的指数 次高项的系数 次高项的指数 ?? 第三行: (多项式 B)最高项的系数 最高项的指数 次高项的系数 次高项的指数 ?? 输出: (输出到文件 dxs.out) (运算结果)最高项的系数 最高项的指数 次高项的系数 次高项的指数 ?? 输入输出举例: 输入: + 1 4 10 3 3 2 14 0 3 5 5 3 –3 2 –6 0 3.法雷序列 (falei.pas) 给定任意一个自然数 N; 将分母小于等于 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 输出:N 级法雷序列 提示:① 由于预先不能计算法雷序列的个数,于是用“链”来描述法雷序列,对实型数要避 免等于或不等于的比较,于是每个结点存放分子分母。 ② 给定一个数 N,首先生成一个分母小于等于 N 的不可约的真分数,产生该真分数利 用求最大真公约数的函数。然后,对当前真分数找插入位置。重复此工作直到生成有 输出: 3 5 1 4 15 3 8 0 A(X) = X4+10X3+3X2+14 B(X) = 3X5+5X3-3X2-6 A(X)+B(X)=3X5+X4+15X3+8

序的法雷序列。 ③ 生成法雷序列后,先打印分子;然后,输出一串字符‘—’ ;最后树出分母。


相关文章:
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 02线性表教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 02线性表教案_学科竞赛_高中教育_教育专区。§2 §2.1 线性表的定义及其基本运算 线性表 线性表是...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 01数据结构概论教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 01数据结构概论教案_学科竞赛_高中教育_教育专区。§1 §1.1 什么是数据结构 概论 数据结构(Data ...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 08图教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 08图教案_学科竞赛_高中教育_教育专区。§8 §8.1 图的基本概念 图 图: 图是数据结构 G=(V,...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 04串教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 04串教案_学科竞赛_高中教育_教育专区。§4 §4.1 串的匹配 串 子串的定位操作称为串的模式匹配,...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 07树教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 07树教案_其它...的孩子链 为空) ,而将这 n 条链的头结点按顺序排列起来,组成一个线性表。...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 06广义表教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 06广义表教案_学科...§6 §6.1 广义表的定义 广义表 广义表 (Lists) 又称列表, 是线性表的推广...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 03栈和队列教案_...(stack)是一种仅限于在称为栈顶(top)的一端进行插入和删除操作的线性表, ...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 05矩阵的压缩存储教案_学科竞赛_高中教育_教育专区。§5 §5.1 特殊矩阵 §5.1.1 三角矩阵与...
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 09内部排序教案
广东省汕头市金山中学高中信息技术 竞赛班数据结构专项培训教程 09内部排序教案_学科竞赛_高中教育_教育专区。§9 内部排序 在《数据结构》里,排序一般分为:插入...
广东省汕头市金山中学高中信息技术 pascal教程02 第二课 读懂程序教案
广东省汕头市金山中学高中信息技术 pascal教程02 第二课 读懂程序教案_其它课程_高中教育_教育专区。第二课 读懂程序接下来,我们要学着去读懂程序。 我们用上节课...
更多相关标签:
广东省汕头市金山中学 | 广东省汕头市 | 广东省汕头市潮阳区 | 广东省汕头市潮南区 | 广东省汕头市邮编 | 广东省汕头市澄海区 | 广东省汕头市金平区 | 广东省汕头市地图 |