一、指针的定义及操作

　　（一）指针类型和指针变量

　　在pascal中,指针变量(也称动态变量)存放某个存储单元的地址；也就是说， 指针变量
指示某个存储单元。
　　指针类型的格式为:＾基类型

　　说明: ①一个指针只能指示某一种类型数据的存储单元，这种数据类型就是指针的基类
型。基类型可以是除指针、文件外的所有类型。例如，下列说明：
　　type pointer=^Integer;
　　　　　　　　var p1,p2:pointer;
　　定义了两个指针变量p1和p2，这两个指针可以指示一个整型存储单元(即p1、p2 中存放的是某存储单元的地址，而该存储单元恰好能存放一个整型数据)。

　　②和其它类型变量一样，也可以在var区直接定义指针型变量。
　　例如：var a:^real; b:^boolean;
　　又如：type person=record
　　　　　　　　　　　name:string[20];
　　　　　　　　　　　sex:(male,female);
　　　　　　　　　　　age:1..100
　　　　　　　　　　end;
　　　　　var pts:^person;

　　③pascal规定所有类型都必须先定义后使用，但只有在定义指针类型时可以例外，如下
列定义是合法的：
　　type pointer=^rec;
　　　　　　rec=record
　　　　　　　　a:integer;
　　　　　　　　b:char
　　　　　　　end;

　　（二）开辟和释放动态存储单元

　　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之间进行相等(＝)或不相等(＜＞＝的比较，比较的结果为布尔量。

　　例3 输入两个整数，按从小到大打印出来。
　　分析：不用指针类型可以很方便地编程，但为了示例指针的用法，我们利用指针类型。定义一个过程swap用以交换两个指针的值。

　　源程序如下：
　　Type pointer=^integer;
　　var p1,p2:pointer;
　　procedure swap(var q1,q2:pointer);
　　　var q:pointer;
　　　begin
　　　　q:=q1;
　　　　q1:=q2;
　　　　q2:=q;
　　　end;
　　begin
　　　new(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=record
　　　　　　data：integer;
　　　　　　next:pointer;
　　　　　end;
　　　var head:pointer;
　　②相邻结点的地址不一定是连续的。整个链表是通过指针来顺序访问的，一旦失去了一个指针值，后面的元素将全部丢失。
　　③与数组结构相比，使用链表结构时；可根据需要采用适当的操作步骤使链表加长或缩 短，而使存储分配具有一定的灵活性。这是链表结构的优点。
　　④与数组结构相比，数组元素的引用比较简单，直接用"数组名[下标]"即可，因为数组元素占用连续的存储单元，而引用链表元素的操作却比较复杂。

　　（二）单向链表的基本操作

　　上图所示的链表称为单向链表。下面我们通过一些例题来说明对单向链表的基本操作，并假设类型说明如前所述。

　　例6 编写一个过程，将读入的一串整数存入链表， 并统计整数的个数。
　　分析：过程的输入为一串整数，这在执行部分用读语句完成。过程的输出有两个：一是链表的头指针，一是整数的个数，这两个输出可以用变量形参来实现。
　　由于不知道整数的个数，我们用一个特殊的9999作为结束标记。

　　过程如下：
　　procedure creat(var h:pointer;var n:integer);
　　var p,q:pointer;x:integer;
　　begin
　　　　n:=0;h:=nil; read(x);
　　　　while x<>9999 do
　　　　begin
　　　　　New(p);
　　　　　n:=n+1;p^.data:=x;
　　　　　if n=1 then h:=p
　　　　　else 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;
　　begin
　　　n:=0;p:=head;
　　　while p<>nil do
　　　　begin
　　　　　write(p^.data:8);n:=n+1;
　　　　　if n mod 5=0 then writeln;
　　　　　p:=p^.next;
　　　　end;
　　　writeln;
　　end;

　　（三）链表结点的插入与删除

　　链表由于使用指针来连接，因而提供了更多了灵活性，可以插入删除任何一个成分。
　　设有如下定义：
　　type pointer=^rec;
　　rec=record
　　　　data:integer;
　　　　next:pointer
　　　end;
　　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;
　　begin
　　　new(po);po^.data:=x;
　　　p:=head;
　　　if head=nil{原表为空表}
　　　　then begin
　　　　　head:=po;po^.next:=nil;
　　　　end
　　　else begin
　　　　while (p^.data<x)and(p^.next<>nil)do
　　　　begin
　　　　　q:=p;p:=p^.next
　　　　end;
　　　　if p^.data>=x{不是插在原尾结点之后}
　　　　then begin
　　　　　　if head=p then head:=po
　　　　　　else q^.next:=po;
　　　　　　po^.next:=p
　　　　　end
　　　else begin
　　　　　　po^.next:=po;
　　　　　　po^.next:=nil
　　　　end;
　　　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;
　　begin
　　　New(p);p^.data:=x-1;p^.next:=head;
　　　head:=p;{以上为添加哨兵结点}
　　　while(x<>p^.data)and(p^.next<>nil)do
　　　begin
　　　　q:=p;
　　　　p:=p^.next
　　　end;
　　　if x=p^.data{存在值为X的结点}
　　　then q^.next:=p^.next
　　　else writeln('NOt found!');
　　　head:=head^.next{删除哨兵}
　　end;

　　（四）环形链表结构

　　在单向链表中，表尾结点的指针为空。如果让表尾结点的指针域指向表头结点，则称为单向环形链表，简称单链环。如图所示。
　　　　

　　　　　　　　　　　　　　　　单链环示意图
　　（五）双向链表结构

　　单链表中，每个结点只有一个指向其后继结点的指针域。如果每个结点不仅有一个指向其后继结点的指针域，还有一个指向其前趋的指针域，则这种链表称为双向链表。如图所示。
　　　　　

　　　　　　　　　　　双向链表示意图
　　可用如下定义一个数据域为整型的双向链表:
　　　　type pointer=^node;
　　　　　　node=record
　　　　　　　　　prev:pointer;
　　　　　　　　　data:integer;
　　　　　　　　　next:pointer;
　　　　　　　　end;
　　对双向链表的插入、删除特别方便。与单向链环相似，我们还可定义双向链环。

　　三、综合例析

　　例10 读入一串以"＃"为结束标志的字符，统计每个字符出现的次数。
　　分析：设置一个链表存放，每读入一个字符，就从链表的头结点向后扫描链表，如果在链表中此字符已存在，则其频率加1， 否则将该字符的结点作为链表的新头结点，相应频率为1。

　　源程序如下：
　　program ex11_10;
　　type ref=^letters;
　　　　　letters=record
　　　　　　　　　key:char;
　　　　　　　　　count:integer;
　　　　　　　　　next:ref;
　　　　　　　　end;
　　　var k:char;
　　　　sentinel,head:ref;
　　　procedure search(x:char);
　　　var w:ref;
　　　begin
　　　　w:=head;
　　　　sentinel^.key:=x;
　　　　while w^.key<>x do w:=w^.next;
　　　　if w<>sentinel
　　　　then w^.count:=w^.count+1
　　　　else begin
　　　　　　　　w:=head;new(head);
　　　　　　　　with head^ do
　　　　　　　　　begin
　　　　　　　　　　　key:=x;count:=1;next:=w;
　　　　　　　end
　　end;
　　end;{of search}
　　procedure printlist(w:ref);
　　　begin
　　　　while w<>sentinel do
　　　　　begin
　　　　　　writeln(w^.key:2,w^.count:10);
　　　　　　w:=w^.next;
　　　　　end;
　　　end;{of printlist}
　　begin{main program}
　　　new(sentine);
　　　with sentinel^ do
　　　　begin
　　　　　key:='#';count:=0;next:=nil;
　　　　end;
　　　head:=sentinel;
　　　read(k);
　　　while k<>'#' do
　　　　begin
　　　　　search(k);read(k);
　　　　end;
　　　printlist(head);
　　end.

　　例11　用链表重写筛法求2～100之间所有素数程序。
　　源程序如下：
　　program ex11_12;
　　　uses crt;
　　　type link=^code;
　　　　　　code=record
　　　　　　　　　key:integer;
　　　　　　　　　next:link;
　　　　　　　　end;
　　　var head:link;
　　　procedure printlist(h:link);{打印链表h}
　　　　var p:link;
　　　　begin
　　　　　p:=h;
　　　　　while p<>nil do
　　　　　　begin
　　　　　　　write(p^.key,'-->');
　　　　　　　p:=p^.next;
　　　　　　end;
　　　　end;
　　　procedure buildlink;{建立链表}
　　　　var p,q:link;
　　　　i:integer;
　　　　begin
　　　　　new(head);
　　　　　head^.key:=2;
　　　　　p:=head;
　　　　　for i:=3 to 100 do
　　　　　　begin
　　　　　　　new(q);
　　　　　　　q^.key:=i;
　　　　　　　q^.next:=nil;
　　　　　　　p^.next:=q;
　　　　　　　p:=q;
　　　　　　end;
　　　　end;
　　　procedure prime;{筛法将找到的素数的倍数从链表中删除}
　　　　var h,p,q:link;
　　　　begin
　　　　　h:=head;
　　　　　while h<>nil do
　　　　　　begin
　　　　　　　p:=h;q:=p^.next;
　　　　　　　while q<>nil do
　　　　　　　　if (q^.key mod h^.key=0) then
　　　　　　　　　begin
　　　　　　　　　　p^.next:=q^.next;
　　　　　　　　　　dispose(q);
　　　　　　　　　　q:=p^.next;
　　　　　　　　　end
　　　　　　　　else begin
　　　　　　　　　　　　p:=q;
　　　　　　　　　　　　q:=q^.next;
　　　　　　　　　　　end;
　　　　　　　h:=h^.next;
　　　　　　end;
　　　　end;
　　　begin{main program}
　　　　　clrscr;
　　　　　buildlink;
　　　　　printlist(head);
　　　　　writeln;
　　　　　prime;
　　　　　printlist(head);
　　　　end.

练习

　　1、围绕着山顶有10个洞，一只兔子和一只狐狸各住一个洞，狐狸总想吃掉兔子。一天兔子对狐狸说，你想吃我有一个条件，你先把洞编号１到10。你从第10号洞出发，先到第１号洞找我，第二次隔一个洞找我，第三次隔两个洞找我，以后依次类推，次数不限。若能找到我，你就可以饱餐一顿，在没找到我之前不能停止。狐狸一想只有10个洞，寻找的次数又不限，哪有找不到的道理，就答应了条件。结果就是没找着。
　　利用单链环编程，假定狐狸找了１０００次，兔子躲在哪个洞里才安全。

　　2、某医院病房的订位管理中， 将病人的记录按姓名的字母顺序排成一个链表。试编写程序，从键盘上输入下列字母，就可对病员记录进行管理：
　　（１）ｉ───新病人入院（插入一个病员记录）。
　　（２）ｄ───病人出院（删除一个病员记录，并显示该记录）。
　　（３）ｓ───查询某病员记录（显示该记录或"未找到"）。
　　（４）ｑ───在屏幕上列出所有的病员记录并结束程序。

　　3、编写一个简单的大学生新生入校登记表处理程序。