指針類型與動態(tài)數(shù)據(jù)結(jié)構(gòu)

1、第五節(jié)  指針類型與動態(tài)數(shù)據(jù)結(jié)構(gòu)前面所學(xué)的變量都具有共同的特點：系統(tǒng)依據(jù)程序說明部分獲得變量名和類型信息，即為變量分配對應(yīng)大小的存儲空間，在程序執(zhí)行過程中，各變量對應(yīng)的存儲空間始終存在且保持不變，這些變量均稱為靜態(tài)變量。與靜態(tài)變量對應(yīng)的是動態(tài)變量，在程序執(zhí)行過程中可以動態(tài)產(chǎn)生或撤消，所使用的存儲空間也隨之動態(tài)地分配或回收。為了使用動態(tài)變量。PASCAL系統(tǒng)提供了指針類型，用指針變量（靜態(tài)變量）來指示動態(tài)變量（存儲地址變量）。下面介紹如何利用指針建立動態(tài)數(shù)據(jù)結(jié)構(gòu)。 例5.19 分別用簡單變量和指針變量交換兩個變量的值。解：設(shè)兩個變量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 );              開辟動態(tài)存儲單元    

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指向了存儲整數(shù)8的單元（即a = 8），b指向了存儲整數(shù)5的單元（即b = 5）。存儲單元的值沒有重新賦值，只是存放指針值的變量交換了指針值。    程序Exam519_1  Type pon= integer; 是定義指針類型，一般格式為：基類型就是指針所指向的數(shù)據(jù)元素的數(shù)據(jù)類型。也可以將類型說明合并在變量說明中直接定義說明：例如

9、Exam519_1中類型說明與變量可以合并說明為：Var  a,b,c: integer;    與程序中分開說明的作用相同定義了指針變量的類型之后，必須調(diào)用New過程開辟存儲單元，調(diào)用格式如下：如果不再需要指針變量當(dāng)前所指向的存儲單元，可調(diào)用Dispose過程釋放所占用的存儲單元，Dispose和New的作用正好相反，其格式為：在程序中對所指存儲單元（為a ）可以視作簡單變量進行賦值計算和輸出。如：a := 5例5.20 利用指針對數(shù)組元素值進行排序。解：定義一個各元素為指針類型的數(shù)組a :    定義一個交換指針值的過程

10、(swap)；    定義一個打印過程(print)；    定義過程(int)將數(shù)組b的值賦給a數(shù)組各元素所指向的各存儲單元。    過程pixu用交換指針值的方式，按a數(shù)組所指向的存儲單元內(nèi)容值從小到大地調(diào)整各元素指針值，實現(xiàn)“指針”排序；    按順序打印a數(shù)組各元素指向單元的值(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;         打印數(shù)組各元素指向單元(a i )的值    var i: integer;    begin      for i:=1 to n do write(a i :6);      writeln; writeln;  

13、  end;  Procedure int;        將數(shù)組b的值賦給a數(shù)組各元素所指向的存儲單元    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連續(xù)報數(shù)，凡報n號的退出到圈外。如此循環(huán)報數(shù)，直到圈上只剩下一只猴子即當(dāng)選為王。用指針（環(huán)形鏈表）編程。解：讓指針pon指向的單元為記錄類型，記錄內(nèi)容含有兩個域：             編號變量  鏈指針變量 用過程crea建立環(huán)形鏈；用過程king進行報數(shù)處理：  

18、;    每報數(shù)一次t計數(shù)累加一次，當(dāng)所報次數(shù)能被n整除，就刪去該指針指向的記錄，將前一個記錄的鏈指針指向下一個記錄。刪去的指向單元（記錄）應(yīng)釋放。直到鏈指針所指向的單元是同一單元，就說明只剩下一個記錄。打印指向單元記錄中編號域（num)的值。program Exam521; type  pon= rec;                指向rec類型    

19、;   rec=record                    rec為記錄類型             num: byte;            域名n

20、um為字節(jié)類型             nxt: pon                域名nxt為pon類型           end; var hd: pon;    m, n: by

21、te; procedure crea;                   建立環(huán)形鏈    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;                   報數(shù)處理   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;