信息学奥赛数据结构教程PASCAL版

1、信息学奥赛数据结构教程PASCAL 版第三课链表存储方式的分类：顺序存储结构和链式存储结构；顺序存储结构 ：在（子）程序的说明部分就必须加以说明，以便分配固定大小的存储单元，直到（子）程序结束，才释放空间。因此，这种存储方式又称为静态存储。所定义的变量相应的称为静态变量。它的优缺点如下：1 优点：可以通过一个简单的公式随机存取表中的任一元素，逻辑关系上相邻的两个元素在物理位置上也是相邻的，且很容易找到前趋与后继元素；2 缺点：在线性表的长度不确定时，必须分配最大存储空间，使存储空间得不到充分利用，浪费了宝贵的存储资源；线性表的容量一经定义就难以扩充；在插入和删除线性表的元素时，需要移动大量的元

2、素，浪费了时间；链式存储结构 ：在程序的执行过程中，通过两个命令向计算机随时申请存储空间或随时释放存储空间，以达到动态管理、使用计算机的存储空间，保证存储资源的充分利用。这样的存储方式称为动态存储。所定义的变量称为动态变量。它的优点如下：1 优点：可以用一组任意的存储单元（这些存储单元可以是连续的，也可以不连续的）存储线性表的数据元素，这样就可以充分利用存储器的零碎空间；2 概念 1：为了表示任意存储单元之间的逻辑关系，对于每个数据元素来说，除了要存储它本身的信息（数据域、 data）外，还要存储它的直接后继元素的存储位置（指针域、link 或 next ）。我们把这两部分信息合在一起称为一个

3、“结点 node”。3 概念 2：N 个结点链接在一起就构成了一个链表。N=0 时，称为空链表。4 概念 3：为了按照逻辑顺序对链表中的元素进行各种操作，我们需要定义一个变量用来存储整个链表的第一个结点的物理位置，这个变量称为“头指针、 H 或 head”。也可以把头指针定义成一个结点，称为“头结点 ”，头结点的数据域可以不存储任何信息，也可以存储线性表的长度等附加信息，头结点的指针域（头指针）存储指向第一个结点的指针，若线性表为空表，则头结点的指针域为空（NIL ）。由于最后一个元素没有后继，所以线性表中最后一个结点的指针域为空（NIL ）。5 概念 4：由于此链表中的每个结点都只包含一个指

4、针域，故称为“线性链表或单链表”。（一）指针类型和指针变量的说明、使用、操作1类型和变量的说明type 指针类型标识符= 基类型名； 基类型不能为文件类型var 指针变量名：指针类型标识符；2申请存储单元 动态申请、空间大小由指针变量的基类型决定new(指针变量名 )； PASCAL标准过程 3指针变量的赋值指针变量名： =NIL ； 初始化，暂时不指向任何存储单元如何表示和操作指针变量？不同于简单变量（如A ：=0；）， PASCAL 规定用 “指针变量名 ”的形式引用指针变量（如P：=0 ；）。如下图：4相同基类型的指针变量之间可以进行相互赋值如有下面的程序段，可以画出右边的示意图：var

5、 p1,p2:integer;new(p1);new(p2);p1:=90;p2:=80;p1:=p2;5关系运算如： if p1=p2 thenwhile p<> nil do6释放动态存储单元dispose(指针变量名 );（二）单链表的结构、建立、输出由于单链表的每个结点都有一个数据域和一个指针域，所以，每个结点都可以定义成一个记录。比如，有如下一个单链表，如何定义这种数据结构呢？type pointer=nodetype;nodetype=recorddata:datatype;next:pointer; 嵌套定义 end;var head,p,q,r:pointer;下面

6、给出建立并输出单链表的程序，大家可以把它改成过程用在以后的程序当中。Program creat;type pointer=nodetype;nodetype=recorddata:integer;next:pointer;end;varhead,p,r:pointer;r 指向链表的当前最后一个结点，可以称为尾指针 x:integer;beginwriteln('please input num(-1 is end):');read(x);new(head); 申请头结点 head:=nil; 头结点初始化 r:=head;while x<>-1 do 读入的数非

7、-1beginnew(p); 则，申请一个新结点p.data:=x;p.next:=nil;r.next:=p; 把新结点链接到前面的链表中，实际上r 是 p 的直接前趋r:=p; 尾指针后移一个read(x);end;r.next:=nil; 最后一个结点的指针域赋空readln;writeln('output: '); 输出p:=head.next; 头指针没有数据，只要从第一个结点开始就可以了 while p.next<>nil dobeginwrite(p.data:4);p:=p.next;end;write(p.data:4); 最后一个结点的数据单独输

8、出，也可以改用 REPEAT 循环 readln;end. 请大家改写这个程序，把链表的实际结点个数存入到头结点中，并输出（三）单链表的操作1 查找 “数据域满足一定条件的结点”p:=headnext;while (p.data<> x) and (p.next<>nil) do p:=p.next; 找到第一个就结束 if p.data = x then 找到了处理 else 输出不存在；如果想找到所有满足条件的结点，则修改如下：p:=headnext;while p.next<>nil do 一个一个判断 beginif p.data = x then找

9、到一个处理一个；p:=p.next;end;2 取出单链表的第i 个结点的数据域function get(head:pointer;i:integer):integer;varp:pointer;j:integer;beginp:=head.next;j:=1;while (p<>nil) and (j<i) dobeginp:=p.next;j:=j+1;end;if (p <> nil) and (j=i) then writeln(p.data)else writeln(i not exsit!);end;3 插入一个结点在单链表中去procedure in

10、sert(head:pointer;i:integer;x:integer); 插入 X 到第 i 个元素之前 varp,s:pointer;j:integer;beginp:=head;j:=0;while (p<>nil) and (j<i-1) do 寻找第 i-1 个结点 ,插在它的后面 beginp:=p.next;j:=j+1;end;if (p=nil) or (j>i-1) then writeln(no this position!)else begin 插入 new(s);s.data:=x;s.next:=p.next;p.next:=s;end;

11、end;4 删除单链表中的第i 个结点（如下图的“ b结”点）procedure delete(head:pointer;i:integer;); 删除第 i 个元素 varp,s:pointer;j:integer;beginp:=head;j:=0;while (p.next<>nil) and (j<i-1) dobeginp:=p.next;j:=j+1;end; p 指向第 i-1 个结点 if (p.next=nil) or (j>i-1) then writeln(no this position!)else begin 删除p 的后继结点，假设为ss:=

12、p.next;p.next:=p.next.next; 或 p.next:=s.nextdispose(s);end;end;5 求单链表的实际长度function len(head:pointer):integer;varn:integer;beginp:=head;n:=0;while p<> nil dobeginn:=n+1;p:=p.next;end;len:=n;end;（四）双向链表每个结点有两个指针域和若干数据域，其中一个指针域指向它的前趋结点，一个指向它的后继结点。它的优点是访问、插入、删除更方便，速度也快了。但“是以空间换时间”。数据结构的定义：type poi

13、nter=nodetype;nodetype=recorddata:datatype;pre,next:pointer; pre 指向前趋， next 指向后继 end;var head,p,q,r:pointer;下面给出双向链表的插入和删除过程。Procedure insert(head:pointer;i,x:integer);在双向链表的第i 个结点之前插入XVars,p:pointer;j:integer;BeginNew(s);S.data:=x;P:=head;j:=0;while (p.next<>nil) and (j<i) dobeginp:=p.next

14、;j:=j+1;end; p指向第i 个结点 if p=nil then writeln(no this position!)else begin 将结点 S 插入到结点P 之前 s.pre:=p.pre; 将 S 的前趋指向P 的前趋 p.pre:=s; 将 S 作为 P 的新前趋 s.next:=p; 将 S 的后继指向Pp.pre.next:=s; 将 P 的本来前趋结点的后继指向Send;End;Procedure delete(head:pointer;i:integer);删除双向链表的第i 个结点 Varp:pointer;j:integer;BeginP:=head;j:=0;

15、while (p.next<>nil) and (j<i) dobeginp:=p.next;j:=j+1;end; p 指向第 i 个结点 if p=nil then writeln(no this position!)else begin 将结点 P 删除 p.prenext:=p.next; P 的前趋结点的后继赋值为p.next.pre:=p.pre; P 的后继结点的前趋赋值为end;P的后继 P的前趋End;（五）循环链表单向循环链表：最后一个结点的指针指向头结点。如下图：双向循环链表：最后一个结点的指针指向头结点，且头结点的前趋指向最后一个结点。如下图：循环链表

16、的应用举例：约瑟夫问题。 问题描述 有 n 只猴子，按顺时针方向围成一圈（开始时编号为1， 2， n），选大王。从第1 号猴子开始报数 1， 2，3 ，数到 m 号时该猴子退出到圈外，如此报数直到圈内只剩下一只猴子时，此猴便是大王。你的任务是从键盘读入 n,m ，程序判断输出最后的大王是几号？ 数据结构和算法分析数据结构：显然是一个单向循环链表。数据域为猴子的编号，指针域为下一个猴子的地址。算法：报数实际上是计数，只要设一个计数器就可以了。当计数器由0 变化到 m 时，删除该结点，计数器回 0 继续计数（或者用求余运算）。直到链表中剩下一个结点。 参考程序 program king(input

17、,output);type pointer=monkey;monkey=recordnum:integer;next:pointer;end;varhead,p,q:pointer;n,m:integer;procedure creat(var head:pointer;n:integer); 建立一个单向循环链表 varp,q:pointer;i:integer;beginnew(p); 建立头结点 head:=p;p.num:=1;q:=p; q 指向链表的尾结点for i:=2 to n do 建立链表 beginnew(p);p.num:=i;q.next:=p; 把 P 结点连接到q

18、 的后面 q:=p;end;q.next:=head; 建立循环链表 end;procedure selectking(var head:pointer;var m:integer);varp,q:pointer;i,count:integer;beginp:=head;count:=1; 指向第一个结点，洋计数1q:=p; q 为 p 的前趋 repeatp:=q.next;count:=count+1;if count mod m=0 then begin 该猴子出圈，即删除结点q.next:=p.next;dispose(p);endelse q:=p; 指针往后移一个until p.n

19、ext=p; 只剩下一个结点head:=p;end;begin mainwrite( input monkey num :);readln(n);writeln(the baoshu number: );readln(m);creat(head,n);selectking(head,m);writeln(the moneyking is no.,head.num);readlnend. 运行测试 输入： input monkey num :13the baoshu number:5输出： the moneyking is no.6（六）线性表的应用举例1 链表的归并操作 问题描述已知线性表L1

20、和 L2 中的数据元素按值非递减有序排列，现要求将L1和 L2 归并成一个新的线性表L3，使L3 中的数据元素仍按非递减有序排列。例如：L1=（1，3，4，5，8，9，10，11，12）， L2=（2，4，6，8），则L3= （1， 2，3，4， 4， 5，6，8， 8， 9，10， 11，12）。注意：相同元素照算。 标准过程procedure merge(h1,h2:pointer; var h3:pointer); 将头指针分别为h1,h2 的两个单链表归并成一个新的单链表，该链表头指针为h3varp1,p2,p3:pointer; 临时用工作指针，一般不能破坏头指针beginp1:=h

21、1.next;p2:=h2.next;h3:=h1; 新链表共用第一个链表，简化，也可以另外开辟一个头结点p3:=h3;while (p1<>nil) and (p2<>nil) do 归并 beginif p1.data<=p2.data thenbegin 将 p1 结点链接到p3 中去 p3.next:=p1; 指向 p3:=p1; p3后移 p1:=p1.next p1后移 endelse begin 将 p2 结点链接到p3 中去 p3.next:=p2;p3:=p2;p2:=p2.nextend;end;if p1<>nil then p3

22、.next:=p1 将 p1 中剩下的结点一起链接到p3 中else p3.next:=p2; 将 p2 中剩下的结点一起链接到p3 中 end;2一元多相式的表示和加减运算 问题描述 在数学上，一个一元 n 次多项式 Pn(x)，可以按升幂写成：Pn(x)=P0 + P 1X + P 2 X2 + P3X 3 + PnX n它由 n+1 个系数唯一确定。因此，在计算机里，它可以用一个线性表P 来表示：P = （ P0， P1，P2，Pn ）每一项的指数 i 隐含在系数 Pi 的序号里。任务 给定一个一元n 次多项式 Pn(x) 和一个一元m 次多项式 Qm(x) ，求它们的和与差。 数据结构 方法 1：按 n,m 分别生成 n+1 和 m+1 个结点的两个单链表，即不管