指针类型与动态数据结构

1、第五节  指针类型与动态数据结构前面所学的变量都具有共同的特点：系统依据程序说明部分获得变量名和类型信息，即为变量分配对应大小的存储空间，在程序执行过程中，各变量对应的存储空间始终存在且保持不变，这些变量均称为静态变量。与静态变量对应的是动态变量，在程序执行过程中可以动态产生或撤消，所使用的存储空间也随之动态地分配或回收。为了使用动态变量。PASCAL系统提供了指针类型，用指针变量（静态变量）来指示动态变量（存储地址变量）。下面介绍如何利用指针建立动态数据结构。 例5.19 分别用简单变量和指针变量交换两个变量的值。解：设两个变量a,b的值分别为5, 8(1)用简单变量交换

2、：Program Exam519;  const  a=5; b=8;                             常量  var c: integer;  begin    c:=a; a:=b; b:=c;  &#

3、160;                     用简单变量交换Type  指针类型名 = 基类型；    writeln(a=:8, a, b=:8, b );    readln  end.(2)用指针变量交换：Var  指针变量名 :  基类型；Program Exam519_1;  

4、; type pon= integer;                          pon为指针类型  var  a,b,c: pon;               

5、60;              a,b,c为指针变量  begin    New（指针变量）;      new(a ); new(b ); new(c );              开辟动态存储单元    

6、;  a :=5;  b :=8;                        给a,b指向的存储单元赋值      c:=a; a:=b; b:=c;            &

7、#160;           交换存储单元的指针      writeln('a=':8, a , b=':8, b );  输出a,b所指单元的值    Dispose（指针变量）；readln  End. 第(2)种方法，对各存储单元所保存的值并不改变，只是交换了指向这些单元的存储地址（指针值），可以简略地用如下图示说明：(图中“”表示指向存储单元)指针类型

8、的指针变量a,b存有各指向单元的地址值，将指针交换赋值步骤为：将c:=a (让c具有a的指针值);将a:=b (让a具有b的指针值);将b:=c (让b具有c的指针值);最后输出a,b所指向存储单元(a 和b )的值，此时的a指向了存储整数8的单元（即a = 8），b指向了存储整数5的单元（即b = 5）。存储单元的值没有重新赋值，只是存放指针值的变量交换了指针值。    程序Exam519_1  Type pon= integer; 是定义指针类型，一般格式为：基类型就是指针所指向的数据元素的数据类型。也可以将类型说明合并在变量说明中直接定义说明：例如

9、Exam519_1中类型说明与变量可以合并说明为：Var  a,b,c: integer;    与程序中分开说明的作用相同定义了指针变量的类型之后，必须调用New过程开辟存储单元，调用格式如下：如果不再需要指针变量当前所指向的存储单元，可调用Dispose过程释放所占用的存储单元，Dispose和New的作用正好相反，其格式为：在程序中对所指存储单元（为a ）可以视作简单变量进行赋值计算和输出。如：a := 5例5.20 利用指针对数组元素值进行排序。解：定义一个各元素为指针类型的数组a :    定义一个交换指针值的过程

10、(swap)；    定义一个打印过程(print)；    定义过程(int)将数组b的值赋给a数组各元素所指向的各存储单元。    过程pixu用交换指针值的方式，按a数组所指向的存储单元内容值从小到大地调整各元素指针值，实现“指针”排序；    按顺序打印a数组各元素指向单元的值(a i )。Program Exam520;  const n=8;        b: array1.n of

11、 integer          =(44,46,98,86,36,48,79,71);  type pon= integer;  var  a: array1.n of pon;  Procedure swap(var p1, p2: pon);  交换指针    var p: pon;    begin      p:=p1; p1:=p2;

12、 p2:=p    end;  Procedure print;         打印数组各元素指向单元(a i )的值    var i: integer;    begin      for i:=1 to n do write(a i :6);      writeln; writeln;  

13、  end;  Procedure int;        将数组b的值赋给a数组各元素所指向的存储单元    var i: integer;    begin      for i:=1 to n do       begin         new(a i

14、 );         a i :=b i ;       end;      print;    end;  Procedure pixu;                 排序  

15、60; var i,j,k: integer;    begin      for i:=1 to n-1 do        begin          k:=i;          for j:=i+1 to n do    

16、;        if aj < ak   then  k:=j;          swap(ak, a i )        end    end;  Begin   int;   pixu;   print;   re

17、adln  End. 例5.21 有m只猴子要选猴王，选举办法如下：所有猴子按1 . . m编号围坐成圆圈，从第一号开始按顺序1, 2, . . , n连续报数，凡报n号的退出到圈外。如此循环报数，直到圈上只剩下一只猴子即当选为王。用指针（环形链表）编程。解：让指针pon指向的单元为记录类型，记录内容含有两个域：             编号变量  链指针变量 用过程crea建立环形链；用过程king进行报数处理：  

18、;    每报数一次t计数累加一次，当所报次数能被n整除，就删去该指针指向的记录，将前一个记录的链指针指向下一个记录。删去的指向单元（记录）应释放。直到链指针所指向的单元是同一单元，就说明只剩下一个记录。打印指向单元记录中编号域（num)的值。program Exam521; type  pon= rec;                指向rec类型    

19、;   rec=record                    rec为记录类型             num: byte;            域名n

20、um为字节类型             nxt: pon                域名nxt为pon类型           end; var hd: pon;    m, n: by

21、te; procedure crea;                   建立环形链    var s,p: pon;         i: byte;    begin      new(s);  hd:=

22、s;  s . num :=1;  p:=s;      for i:=2 to n do        begin          new(s);  s . num :=i;  p . nxt:=s;  p:=s        end;  

23、60;   p . nxt :=hd    end; procedure king;                   报数处理   var p,q: pon;       i, t: byte;   begin    

24、; p:=hd;  t:=0;  q:=p;     repeat       p:=q . nxt;  inc(t);       if t=n then          begin            q . nxt :=p . nxt;