信息学奥赛数据结构教程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规定用指针变量名人”的形式引用 指针变量（如PA: =0;）。如下图：PA地址 0存储单元地址存储单元指针变量6.释放动态存储单元disp

5、ose（指针变量名）;简单变量4 .相同基类型的指针变量之间可以进行相互赋值如有下面的程序段，可以画出右边的示意图:var p1,p25nteger;new(p1);new(p2);p1A:=90;p2A:=80;p1:=p2;5 .关系运算如：if p1=p2 then while p nil do （二）单链表的结构、建立、输出由于单链表的每个结点都有一个数据域和一个指针域， 所以，每个结点都可以定义成一个记录。比如,有如下一个单链表，如何定义这种数据结构呢?type pointer=Anodetype； nodetype=recorddata:datatype;next:pointer;

6、 嵌套定义 end;var head,p,q,r:pointer;下面给出建立并输出单链表的程序，大家可以把它改成过程用在以后的程序当中Program creat;type pointer=Anodetype；nodetype=record data: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;

7、while x-1 do 读入的数非-1beginnew(p); 则，申请一个新结点 pAdata:=x;pAnext:=nil;S.next:=p; 把新结点链接到前面的链表中，实际上 r是p的直接前趋r:=p; 尾指针后移一个read(x); end;S.next:=nil; 最后一个结点的指针域赋空 readln; writeln(output: ); 输出 p:=headA.next; 头指针没有数据，只要从第一个结点开始就可以了while pA.nextnil do beginwrite(pdata:4);p:=pA.next;end;write(pA.data:4); 最后一个结点

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

9、:=pA.next;end;2 .取出单链表的第i个结点的数据域function get(head:pointer;i:integer):integer;varp:pointer;j:integer;beginp:=headA.next;j：=1；while (pnil) and (ji) dobeginp:=pA.next;j：=j+1；end;if (p nil) and (j=i) then writeln(pA.data) else writeln( i not exsit! );end;3.插入一个结点在单链表中去-A I P插入结点前和后的链表变化procedure insert(

10、head:pointer;i:integer;x:integer);插入 X 至U第 i 个元素之前 varp,s:pointer;j:integer;beginp:=head;j：=0；while (pnil) and (ji- 1) then writeln( no this position! )else begin 插入new(s);sA.data:=x;sA.next:=pA.next;pA.next:=s;end;end;4 .删除单链表中的第i个结点（如下图的 “段点）P删除一个结点前和后链表的变化procedure delete(head:pointer;i:integer;)

11、;删除第 i 个元素 varp,s:pointer;j:integer;beginp:=head;j：=0；while (pA.nextnil) and (ji- 1) then writeln( no this position!else begin 删除p的后继结点，假设为 ss:=pA.next;pA.next:=pA.nextA.next; 或 pA.next:=sA.nextdispose(s);end;end;5 .求单链表的实际长度function len(head:pointer):integer;varn:integer;beginp:=head;n:=0;while p n

12、il dobeginn:=n+1;p:=pA.next;end;len:=n;end;（四）双向链表每个结点有两个指针域和若干数据域，其中一个指针域指向它的前趋结点，一个指向它的后继结点是以空间换时间它的优点是访问、插入、删除更方便，速度也快了。但数据结构的定义：type pointehnodetype;nodetype=recorddata:datatype;pre,next:pointer; pre 指向前趋， next 指向后继 end;var head,p,q,r:pointer;下面给出双向链表的插入和删除过程。删除P结点前后的指针变化在P结点之前插入S结点前后的指针变化Proced

13、ure insert(head:pointer;i,x:integer);在双向链表的第 i 个结点之前插入 XVars,p:pointer;j:integer;BeginNew(s);SA.data:=x;P:=head;j：=0；while (pA.nextnil) and (ji) dobeginp:=pA.next;j：=j+1；end; p指向第i个结点if p=nil then writeln(no this position! )else begin 将结点S插入到结点P之前sA.pre:=pA.pre; 将S的前趋指向P的前趋pA.pre:=s; 将S作为P的新前趋sA.nex

14、t:=p; 将S的后继指向PpA.preA.next:=s; 将P的本来前趋结点的后继指向Send;End;Procedure delete(head:pointer;i:integer);删除双向链表的第 i 个结点Varp:pointer;j:integer;BeginP:=head;j:=0;while (pA.nextnil) and (ji) dobeginp:=pA.next;j：=j+1；end; p指向第i个结点if p=nil then writeln(no this position! )else begin 将结点P删除pA.preAnext：=pA.next； P的前趋

15、结点的后继赋值为P的后继pA.nextA.pre：=pA.pre； P的后继结点的前趋赋值为P的前趋end;End;非空袭单向循环鞋表双向循环链表：最后一个结点的指针指向头结点，且头结点的前趋指向最后一个结点。如下图:head非空袭空表Ow9d next ；(head * * pr*三hsail)循环链表的应用举例：约瑟夫问题。双向循环链表问题描述有n只猴子，按顺时针方向围成一圈（开始时编号为1, 2,n数1,2, 3，数到m号时该猴子退出到圈外，如此报数直到圈内只剩下一只猴子时,从第1号猴子开始报 此猴便是大王。你的任务是从键盘读入 n,m,程序判断输出最后的大王是几号？数据结构和算法分析数

16、据结构：显然是一个单向循环链表。数据域为猴子的编号，指针域为下一个猴子的地址。算法：报数实际上是计数，只要设一个计数器就可以了。当计数器由 数器回0继续计数（或者用求余运算）。直到链表中剩下一个结点。0变化到m时，删除该结点，计参考程序program king(input,output);type pointer=Amonkey;monkey=record num:integer; next:pointer;end;varhead,p,q:pointer;n,m:integer;procedure creat(var head:pointer;n:integer); 建立一个单向循环链表var

17、p,q:pointer;i:integer;beginnew(p); 建立头结点 head:=p;pAnum:=1;q:=p; q 指向链表的尾结点 for i:=2 to n do 建立链表 beginnew(p);pnum:=i;qnext:=p; 把P结点连接到q的后面q:=p;end;qAnext:=head; 建立循环链表end;procedure selectking(var head:pointer;var m:integer);varp,q:pointer;i,count:integer;beginp:=head;count:=1; 指向第一个结点，洋计数 1q:=p; q 为

18、 p 的前趋 repeatp:=qA.next;count:=count+1;if count mod m=0 then begin 该猴子出圈，即删除结点 qA.next:=pA.next;dispose(p);endelse q:=p; 指针往后移一个until pA.next=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 m

19、oneyking is no. ,headA.num); readlnend. 运行测试 输入：input monkey num :13the baoshu number:5输出：the moneyking is no.6(六)线性表的应用举例1 链表的归并操作 问题描述 已知线性表L1 和 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 ，

20、 8， 8， 9，10，11 ，12 )。注意：相同元素照算。 标准过程 procedure merge(h1,h2:pointer; var h3:pointer); 将头指针分别为 h1,h2 的两个单链表归并成一个新的单链表，该链表头指针为 h3 varp1,p2,p3:pointer; 临时用工作指针，一般不能破坏头指针 beginp1:=h1A.next;p2:=h2A.next;h3:=h1; 新链表共用第一个链表，简化，也可以另外开辟一个头结点 p3:=h3;while (p1nil) and (p2nil) do 归并 beginif p1A.data=p2A.data the

21、nbegin 将 p1 结点链接到 p3 中去 p3A.next:=p1; 指向 p3:=p1; p3 后移 p1:=p1A.next p1 后移 endelse begin 将 p2 结点链接到 p3 中去 p3A.next:=p2;p3:=p2;p2:=p2A.nextend;end;if p1nil then p3A.next:=p1 将pl中剩下的结点一起链接到 p3中else p3A.next:=p2; 将p2中剩下的结点一起链接到 p3中end;2 一元多相式的表示和加减运算问题描述在数学上，一个一元 n次多项式Pn(x),可以按升嘉写成：Pn(x)=P0 + P1X + P2X2 + P3X3 + PnXn它由n+1个系数唯一确定。因此，在计算机里，它可以用一个线性表P来表示：P = (P0, P1, P2,Pn)每一项的指数i隐含在系数Pi的序号里。任务给定一个一元n次多项式Pn(x)和一个一元 m次多项式Qm(x),求它们的和与差。数据结构方法1 ：按n,m分别生成n+1和m+1个结点的两个单链表，即不管系数是否为0都生成一个结点。一个指针域指向后继结点，一个数据域存放系数(不存在的项系数为0)。浪费了很多空间，尤其是指数很高，而项数很少的