pascal-指针与链表.doc

【精品文档】如有侵权，请联系网站删除，仅供学习与交流pascal-指针与链表.精品文档.指针与链表前面介绍的各种简单类型的数据和构造类型的数据属于静态数据。在程序中，这些类型的变量一经说明，就在内存中占有固定的存储单元，直到该程序结束。程序设计中，使用静态数据结构可以解决不少实际问题，但也有不便之处。如建立一个大小未定的姓名表，随时要在姓名表中插入或删除一个或几个数据。而用新的数据类型指针类型。通过指针变量，可以在程序的执行过程中动态地建立变量，它的个数不再受限制，可方便地高效地增加或删除若干数据。 一、指针的定义及操作（一）指针类型和指针变量在pascal中,指针变量(也称动态变量)存放某个存储单元的地址；也就是说， 指针变量指示某个存储单元。指针类型的格式为:基类型说明: 一个指针只能指示某一种类型数据的存储单元，这种数据类型就是指针的基类型。基类型可以是除指针、文件外的所有类型。例如，下列说明：type pointer=Integer;var p1,p2:pointer;定义了两个指针变量p1和p2，这两个指针可以指示一个整型存储单元(即p1、p2 中存放的是某存储单元的地址，而该存储单元恰好能存放一个整型数据)。和其它类型变量一样，也可以在var区直接定义指针型变量。例如：var a:real; b:boolean;又如：type person=recordname:string20;sex:(male,female);age:1.100end;var pts:person;pascal规定所有类型都必须先定义后使用，但只有在定义指针类型时可以例外，如下列定义是合法的：type pointer=rec;rec=recorda:integer;b:charend;（二）开辟和释放动态存储单元1、开辟动态存储单元在pascal中，指针变量的值一般是通过系统分配的，开辟一个动态存储单元必须调用标 准过程new。new过程的调用的一般格式:New(指针变量)功能：开辟一个存储单元，此单元能存放的数据的类型正好是指针的基类型，并把此存储单元的地址赋给指针变量。说明：这实际上是给指针变量赋初值的基本方法。例如，设有说明：var p:Integer;这只定义了P是一个指示整型存储单元的指针变量，但这个单元尚未开辟，或者说P中尚未有值（某存储单元的首地址）。当程序中执行了语句new(p)才给赋值，即在内存中开辟（分配）一个整型变量存储单元，并把此单元的地址放在变量中。示意如下图：(a)编译时给 (b)执行New(p)后 (c)(b)的简略表示p分配空间 生成新单元?表示值不定 新单元的地址为XXXX内存单元示意图一个指针变量只能存放一个地址。如再一次执行New(p)语句，将在内存中开辟另外一个新的整型变量存储单元，并把此新单元的地址放在中，从而丢失了原存储单元的地址。当不再使用当前所指的存储单元时，可以通过标准过程Dispose释放该存储单元。释放动态存储单元dispose语句的一般格式:dispose(指针变量)功能：释放指针所指向的存储单元，使指针变量的值无定义。（三）动态存储单元的引用在给一个指针变量赋以某存储单元的地址后，就可以使用这个存储单元。引用动态存储单元一般格式：指针变量说明：在用New过程给指针变量开辟了一个它所指向的存储单元后，要使用此存储单元的唯一方法是利用该指针。对动态存储单元所能进行的操作是该类型（指针的基类型）所允许的全部操作。例1 设有下列说明:var p:integer; i:integer;画出执行下列操作后的内存示意图：New(p); P:=4;i:=p;解: 如下图所示。(a)编译时 (b)执行New语句 (c)执行P:=4 (d)执行i:=P分配存储 单元内存单元示意图（四）对指针变量的操作前已述及，对指针所指向的变量（如）可以进行指针的基类型所允许的全部操作。对指针变量本身，除可用New、Dispose过程外，尚允许下列操作：具有同一基类型的指针变量之间相互赋值例2 设有下列说明与程序段:var p1,p2,p3:integer;begin New(P1) ; New(P2); New(P3);P1:=P2; P2:=P3;end;2、可以给指针变量赋nil值nil是PASCAL的关键字，它表示指针的值为"空"。例如，执行：p1:=ni1后，p1的值是有定义的，但p1不指向任何存储单元。3、可以对指针变量进行相等或不相等的比较运算在实际应用中，通常可以在指针变量之间，或指针变量与nil之间进行相等()或不相等(的比较，比较的结果为布尔量。4需要注意之处 1、P与P的区别 P是指向该动态变量的指针变量名，P则称为动态变量或标志变量。P的值是P的首地址，P的值为与基类型相同的一个值。 2、定义后及时分配存储单元 定义了一个指针变量后，并没有为该指针分配动态存储单元，此时的P的值无定义，调用P则会产生运行错误。若想使该指针可用，可以对指针赋值，也可以通过NEW（）过程分配存储单元。 3、使用后及时收回存储单元 指针使用后，不会自动归还占用的存储空间，应及时使用DISPOSE（）过程来释放P所占用的存储单元，以免浪费有限的存储空间例3 输入两个整数，按从小到大打印出来。分析：不用指针类型可以很方便地编程，但为了示例指针的用法，我们利用指针类型。定义一个过程swap用以交换两个指针的值。源程序如下： Type pointer=integer;var p1,p2:pointer;procedure swap(var q1,q2:pointer);var q:pointer;beginq:=q1;q1:=q2;q2:=q;end;beginnew(p1);new(p2);write('Input 2 data:');readln(pq,p2);if p1>p2 then swap(p1,p2);writeln('Output 2 data:',p1:4,p2:4);end. 二、链表结构设有一批整数(12，56，45，86，77，)，如何存放呢? 当然我们可以选择以前学过的数组类型。但是，在使用数组前必须确定数组元素的个数。如果把数组定义得大了，就会有大量空闲存储单元，定义得小了，又会在运行中发生下标越界的错误，这是静态存储分配的局限性。利用本章介绍的指针类型可以构造一个简单而实用的动态存储分配结构链表结构。下图是一个简单链表结构示意图：其中：每个框表示链表的一个元素，称为结点。框的顶部表示了该存储单元的地址(当然，这里的地址是假想的)。每个结点包含两个域：一个域存放整数，称为数据域，另一个域存放下一个结点(称为该结点的后继结点，相应地，该结点为后继结点的前趋结点)的地址。链表的第一个结点称为表头，最后一个结点表尾，称为指针域；指向表头的指针head称为头指针(当head为nil时，称为空链表)，在这个指针变量中 存放了表头的地址。在表尾结点中，由指针域不指向任何结点，一般放入nil。（一）链表的基本结构由上图可以看出：链表中的每个结点至少应该包含两个域；一是数据域，一是指针域。因此，每个结点都是一个记录类型，指针的基类型也正是这个记录类型。因此，head可以这样定义：type pointer= rec；rec=recorddata：integer;next:pointer;end;var head:pointer;相邻结点的地址不一定是连续的。整个链表是通过指针来顺序访问的，一旦失去了一个指针值，后面的元素将全部丢失。 与数组结构相比，使用链表结构时；可根据需要采用适当的操作步骤使链表加长或缩 短，而使存储分配具有一定的灵活性。这是链表结构的优点。与数组结构相比，数组元素的引用比较简单，直接用"数组名下标"即可，因为数组元素占用连续的存储单元，而引用链表元素的操作却比较复杂。（二）单向链表的基本操作上图所示的链表称为单向链表。下面我们通过一些例题来说明对单向链表的基本操作，并假设类型说明如前所述。例6 编写一个过程，将读入的一串整数存入链表， 并统计整数的个数。分析：过程的输入为一串整数，这在执行部分用读语句完成。过程的输出有两个：一是链表的头指针，一是整数的个数，这两个输出可以用变量形参来实现。 由于不知道整数的个数，我们用一个特殊的9999作为结束标记。过程如下：procedure creat(var h:pointer;var n:integer);var p,q:pointer;x:integer;beginn:=0;h:=nil; read(x);while x<>9999 dobeginNew(p);n:=n+1;p.data:=x;if n=1 then h:=pelse q.next:=p;q:=p;read(x)end;if h<>nil then q.next:=nil;Dispose(p);end;例7 编一过程打印链表head中的所有整数,5个一行。分析：设置一个工作指针P,从头结点顺次移到尾结点，每移一次打印一个数据。 过程如下：procedure print(head:pointer);var p:pointer; n:integer;beginn:=0;p:=head;while p<>nil dobeginwrite(p.data:8);n:=n+1;if n mod 5=0 then writeln;p:=p.next;end;writeln;end;（三）链表结点的插入与删除链表由于使用指针来连接，因而提供了更多了灵活性，可以插入删除任何一个成分。设有如下定义：type pointer=rec;rec=recorddata:integer;next:pointerend;var head:pointer;结点的插入如下图所示,要在P结点和Q结点之间插入一个结点m,其操作如下:只要作如下操作即可:New(m);read(m.data);m.next:=q;p.next:=m; 例8 设链表head中的数据是按从小到大顺序存放的，在链表中插入一个数，使链表仍有序。分析：显然，应分两步：查找、插入。设o指向要插入的结点，若仅知道o应插在之前（作为的前趋结点）是无法插入的，应同时知道的前趋结点地址。当然，如果插在链表原头结点这前或原链表为空表或插在原尾结点之后，则插入时又必须作特殊处理。过程如下：procedure inserting(var head:pointer;x:integer);var po,p,q:pointer;beginnew(po);po.data:=x;p:=head;if head=nil原表为空表then beginhead:=po;po.next:=nil;endelse beginwhile (p.data<x)and(p.next<>nil)dobeginq:=p;p:=p.nextend;if p.data>=x不是插在原尾结点之后then beginif head=p then head:=poelse q.next:=po;po.next:=pendelse beginpo.next:=po;po.next:=nilend;end;end;结点的删除如下图所示，要在删除结点P的操作如下:要删除结点P,则只要将其前趋结点的指针域指向P 的后继结点即可。q.next:=p.next;dispose(p);例9 将链表head中值为X的第一个结点删除分析: 有三种情况存在:头结点的值为X; 除头结点外的某个结点值为X;无值为X的结点。为将前两种情况统一起来， 我们在头结点之前添加一个值不为的哨兵结点。算法分两步：查找、删除。过程如下：procedure deleteing(var head:pointer;x:integer);var p,q:pointer;beginNew(p);p.data:=x-1;p.next:=head;head:=p;以上为添加哨兵结点while(x<>p.data)and(p.next<>nil)dobeginq:=p;p:=p.nextend;if x=p.data存在值为X的结点then q.next:=p.nextelse writeln('NOt found!');head:=head.next删除哨兵end;（四）环形链表结构在单向链表中，表尾结点的指针为空。如果让表尾结点的指针域指向表头结点，则称为单向环形链表，简称单链环。如图所示。单链环示意图（五）双向链表结构单链表中，每个结点只有一个指向其后继结点的指针域。如果每个结点不仅有一个指向其后继结点的指针域，还有一个指向其前趋的指针域，则这种链表称为双向链表。如图所示。双向链表示意图可用如下定义一个数据域为整型的双向链表:type pointer=node;node=recordprev:pointer;data:integer;next:pointer;end;对双向链表的插入、删除特别方便。与单向链环相似，我们还可定义双向链环。三、综合例析例10 读入一串以""为结束标志的字符，统计每个字符出现的次数。分析：设置一个链表存放，每读入一个字符，就从链表的头结点向后扫描链表，如果在链表中此字符已存在，则其频率加1， 否则将该字符的结点作为链表的新头结点，相应频率为1。源程序如下：program ex11_10;type ref=letters; 定义指针ref：含三个域key,count,nextletters=recordkey:char;count:integer;next:ref;end;var k:char;sentinel,head:ref; procedure search(x:char); 在链表中扫描查找xvar w:ref;beginw:=head;sentinel.key:=x;while w.key<>x do w:=w.next;if w<>sentinel 若w<>sentinel，则说明x在链表中存在个数1then w.count:=w.count+1else begin 否则，在链表中的最后插入一个结点，存放该值w:=head;new(head);with head dobeginkey:=x;count:=1;next:=w;endend;end;of searchprocedure printlist(w:ref); 过程：输出链表beginwhile w<>sentinel dobeginwriteln(w.key:2,w.count:10);w:=w.next;end;end;of printlistbeginmain programnew(sentine); 建立一个空结点，这是第一个链表结点with sentinel dobeginkey:='#'count:=0;next:=nil;end;head:=sentinel; 将head指向空结点（第一个结点），读入一个字符read(k);while k<>'#' dobeginsearch(k);read(k);end;printlist(head);end.例11用链表重写筛法求2100之间所有素数程序。 源程序如下：program ex11_12;uses crt;type link=code;code=recordkey:integer;next:link;end;var head:link;procedure printlist(h:link);打印链表hvar p:link;beginp:=h;while p<>nil dobeginwrite(p.key,'->');p:=p.next;end;end;procedure buildlink;建立链表var p,q:link;i:integer;beginnew(head);head.key:=2;p:=head;for i:=3 to 100 dobeginnew(q);q.key:=i;q.next:=nil;p.next:=q;p:=q;end;end;procedure prime;筛法将找到的素数的倍数从链表中删除var h,p,q:link;beginh:=head;while h<>nil dobeginp:=h;q:=p.next;while q<>nil doif (q.key mod h.key=0) thenbeginp.next:=q.next;dispose(q);q:=p.next;endelse beginp:=q;q:=q.next;end;h:=h.next;end;end;beginmain programclrscr;buildlink;printlist(head);writeln;prime;printlist(head);end.多项式 (Polynomial)n阶多项式Pn(x)有n+1项系数 a0, a1, a2, , an 指数 0, 1, 2, , n。按升幂排列多项式的链接表示在多项式的链表表示中每个结点增加了一个数据成员link，作为链接指针。优点是：多项式的项数可以动态地增长。插入、删除方便，不移动元素。多项式链表的相加AH = 1 - 10x6 + 2x8 +7x14 BH = - x4 + 10x6 - 3x10 + 8x14 +4x18多项式的相加的算法设立表头Aiter,Biter，检测指针pa,pb利用pa,pb扫描两个相加多项式，直到其中一个检测完毕： 若当前被检测项指数相等，系数相加。若不为0，则加入结果链表。 若当前被检测项指数不等，将指数小者加入结果链表。若有一个多项式已检测完，将另一个多项式剩余部分加入结果链表。程序：Polynomial.pasprogram polynomial; type data=term; term=record coef:integer; exp:integer; link:data; end; var first,pa,pb,ch1,ch2:data; x,y:integer; procedure plink(head:data);建立多项式链表 var p,h:data; x,y:integer; begin p:=head; read(x,y); while y<>-1 do begin new(h); h.coef:=x; h.exp:=y;p.link:=h;p:=h; read(x,y); end; new(h);h:=nil;p.link:=h;p.link:=nil; end; procedure ins(x,y:integer;ch2:data);过程：插入一个结点 var ch:data; begin new(ch);ch1.link:=ch; ch.coef:=x;ch.exp:=y;ch1:=ch; end; begin new(pa);pa:=nil;first:=pa;plink(pa);pa:=first.link;建立第一个多项式PA new(pb);pb:=nil;first:=pb;plink(pb);pb:=first.link;建立第二个多项式PB new(ch1); first:=ch1; repeat begin if pa.exp=pb.exp then 若PA和PB的指数相等 begin x:=pa.coef+pb.coef;y:=pa.exp;ins(x,y,ch1); pa:=pa.link;pb:=pb.link; end else begin if pa.exp<pb.exp then begin x:=pa.coef;y:=pa.exp; ins(x,y,ch1); pa:=pa.link; end else begin x:=pb.coef;y:=pb.exp; ins(x,y,ch1); pb:=pb.link; end end; end; until (pa=nil) or (pb=nil); if pa<>nil then ch1.link:=pa; if pb<>nil then ch1.link:=pb; repeat first:=first.link;write(first.coef:6,first.exp:4); until first.link=nil; end.练习1、围绕着山顶有10个洞，一只兔子和一只狐狸各住一个洞，狐狸总想吃掉兔子。一天兔子对狐狸说，你想吃我有一个条件，你先把洞编号到10。你从第10号洞出发，先到第号洞找我，第二次隔一个洞找我，第三次隔两个洞找我，以后依次类推，次数不限。若能找到我，你就可以饱餐一顿，在没找到我之前不能停止。狐狸一想只有10个洞，寻找的次数又不限，哪有找不到的道理，就答应了条件。结果就是没找着。利用单链环编程，假定狐狸找了次，兔子躲在哪个洞里才安全。2、某医院病房的订位管理中， 将病人的记录按姓名的字母顺序排成一个链表。试编写程序，从键盘上输入下列字母，就可对病员记录进行管理：（）新病人入院（插入一个病员记录）。（）病人出院（删除一个病员记录，并显示该记录）。（）查询某病员记录（显示该记录或"未找到"）。（）在屏幕上列出所有的病员记录并结束程序。3、编写一个简单的大学生新生入校登记表处理程序。