《pascal-指针与链表》由会员分享，可在线阅读，更多相关《pascal-指针与链表（11页珍藏版）》请在金锄头文库上搜索。
1、指针与链表前面介绍的各种简洁类型的数据和构造类型的数据属于静态数据。在程序中，这些类型的变量一经说明，就在内存中占有固定的存储单元，直到该程序完毕。程序设计中，使用静态数据构造可以解决不少实际问题，但也有不便之处。如建立一个 大小未定的姓名表，随时要在姓名表中插入或删除一个或几个数据。而用新的数据类型 指针类型。通过指针变量，可以在程序的执行过程中动态地建立变量，它的个数不再受限制， 可便利地高效地增加或删除假设干数据。一、指针的定义及操作一指针类型和指针变量在 pascal 中,指针变量(也称动态变量)存放某个存储单元的地址；也就是说， 指针变量指示某个存储单元。指针类型的格式为:基类型说明
2、: 一个指针只能指示某一种类型数据的存储单元，这种数据类型就是指针的基类型。基类型可以是除指针、文件外的全部类型。例如，以下说明：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.100
3、end; var pts:erson;pascal 规定全部类型都必需先定义后使用，但只有在定义指针类型时可以例外，如以下定义是合法的：type pointer=rec;rec=recorda:integer; b:charend;二开拓和释放动态存储单元1、开拓动态存储单元在 pascal 中，指针变量的值一般是通过系统安排的，开拓一个动态存储单元必需调用标准过程 new。new 过程的调用的一般格式:New(指针变量)功能：开拓一个存储单元，此单元能存放的数据的类型正好是指针的基类型，并把此存储单元的地址赋给指针变量。说明：这实际上是给指针变量赋初值的根本方法。例如，设有说明：var p:
4、Integer;这只定义了 P 是一个指示整型存储单元的指针变量，但这个单元尚未开拓，或者说P 中尚未有值某存储单元的首地址。当程序中执行了语句new(p)才给赋值，即在内存中开拓安排一个整型变量存储单元，并把此单元的地址放在变量中。示意如以下图：(a) 编译时给(b)执行New(p)后(c)(b)的简单表示p 安排空间生成新单元?表示值不定新单元的地址为XXXX内存单元示意图一个指针变量只能存放一个地址。如再一次执行 New(p)语句，将在内存中开拓另外一个新的整型变量存储单元，并把此新单元的地址放在中，从而丧失了原存储单元的地址。当不再使用当前所指的存储单元时，可以通过标准过程 Dispo
5、se 释放该存储单元。释放动态存储单元dispose 语句的一般格式:dispose(指针变量)功能：释放指针所指向的存储单元，使指针变量的值无定义。三动态存储单元的引用在给一个指针变量赋以某存储单元的地址后，就可以使用这个存储单元。引用动态存储单元一般格式：指针变量说明：在用 New 过程给指针变量开拓了一个它所指向的存储单元后，要使用此存储单元的唯一方法是利用该指针。对动态存储单元所能进展的操作是该类型指针的基类型所允许的全部操作。例 1 设有以下说明:var p:integer; i:integer;画出执行以下操作后的内存示意图：New(p); P:=4;i:=p;解: 如以下图所示。
6、(a) 编译时 (b)执行New 语句(c)执行P:=4(d)执行i:=P安排存储单元内存单元示意图四对指针变量的操作前已述及，对指针所指向的变量如可以进展指针的基类型所允许的 全部操作。对指针变量本身，除可用 New、Dispose 过程外，尚允许以下操作：具有同一基类型的指针变量之间相互赋值例 2 设有以下说明与程序段:var p1,p2,p3:integer; beginNew(P1) ; New(P2); New(P3); P1:=P2; P2:=P3;end;2、可以给指针变量赋 nil 值nil 是 PASCAL 的关键字，它表示指针的值为“空“。例如，执行： p1:=ni1 后，
7、p1 的值是有定义的，但p1 不指向任何存储单元。3、可以对指针变量进展相等或不相等的比较运算在实际应用中，通常可以在指针变量之间，或指针变量与 nil 之间进展相等()或不相等(的比较，比较的结果为布尔量。4需要留意之处1、P 与 P的区分P 是指向该动态变量的指针变量名，P那么称为动态变量或标志变量。P 的值是 P的首地址，P的值为与基类型一样的一个值。2、定义后准时安排存储单元定义了一个指针变量后，并没有为该指针安排动态存储单元，此时的P 的值无定义，调用P那么会产生运行错误。假设想使该指针可用，可以对指针赋值，也可以通过 NEW过程安排存储单元。3、使用后准时收回存储单元指针使用后，不
8、会自动归还占用的存储空间，应准时使用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:”)
9、;readln(pq,p2); if p1p2 then swap(p1,p2); writeln(”Output 2 data:”,p1:4,p2:4);二、链表构造end.设有一批整数(12，56，45，86，77，)，如何存放呢? 固然我们可以选择以前学过的数组类型。但是， 在使用数组前必需确定数组元素的个数。假设把数组定义得大了，就会有大量空闲存储单元，定义得小了，又会在运行中发生下标越界的错误，这是静态存储安排的局限性。利用本章介绍的指针类型可以构造一个简洁而有用的动态存储安排构造链表构造。以下图是一个简洁链表构造示意图：其中：每个框表示链表的一个元素，称为结点。框的顶部表示了该存储
10、单元的地址(固然，这里的地址是假想的)。每个结点包含两个域：一个域存放整数，称为数据域，另一个域存放下一个结点(称为该结点的后继结点， 相应地，该结点为后继结点的前趋结点)的地址。链表的第一个结点称为表头，最终一个结点表尾，称为指针域；指向表头的指针 head 称为头指针(当 head 为nil 时，称为空链表)，在这个指针变量中 存放了表头的地址。在表尾结点中，由指针域不指向任何结点，一般放入 nil。一链表的根本构造由上图可以看出：链表中的每个结点至少应当包含两个域；一是数据域，一是指针域。因此，每个结点都是一个记录类型， 指针的基类型也正是这个记录类型。因此，head 可以这样定义：ty
11、pe pointer= rec； rec=recorddata：integer; next:pointer;end;var head:pointer;相邻结点的地址不肯定是连续的。整个链表是通过指针来挨次访问的，一旦失去了一个指针值，后面的元素将全部丧失。与数组构造相比，使用链表构造时；可依据需要承受适当的操作步骤使链表加长或缩 短，而使存储安排具有肯定的机敏性。这是链表构造的优点。与数组构造相比，数组元素的引用比较简洁，直接用“数组名下标“即可，由于数组元素占用连续的存储单元，而引用链表元素的操作却比较简单。二单向链表的根本操作上图所示的链表称为单向链表。下面我们通过一些例题来说明对单向链表
12、的根本操作，并假设类型说明如前所述。例 6 编写一个过程，将读入的一串整数存入链表， 并统计整数的个数。分析：过程的输入为一串整数，这在执行局部用读语句完成。过程的输出有两个：一是链表的头指针，一是整数的个数，这两个输出可以用变量形参来实现。由于不知道整数的个数，我们用一个特别的 9999 作为完毕标记。过程如下：procedure creat(var h:pointer;var n:integer); var p,q:pointer;x:integer;beginn:=0;h:=nil; read(x); while x9999 do beginNew(p); n:=n+1;p.data:=
13、x; if n=1 then h:=p else q.next:=p; q:=p;read(x)end;if hnil 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 pnil dobeginwrite(p.data:8);n:=n+1; if n mod 5=0 the
14、n 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 中的数据是按从小到大挨次存放的，在链表中插入一个数，
15、使链表仍有序。分析：明显，应分两步：查找、插入。设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.datax)and(p.nextnil)do beginq:=p;p:=p.next end;i
