動態(tài)數(shù)據(jù)類型指針

動態(tài)數(shù)據(jù)類型指針第一頁，共二十八頁，2022年，8月28日一、指針的定義及操作（一）指針類型和指針變量在pascal中,指針變量(也稱動態(tài)變量)存放某個存儲單元的地址；也就是說，指針變量指示某個存儲單元。指針類型的格式為:＾基類型說明:

①一個指針只能指示某一種類型數(shù)據(jù)的存儲單元，這種數(shù)據(jù)類型就是指針的基類型，基類型可以是除指針、文件外的所有類型。typepointer=^Integer;

varp1,p2:pointer;定義了兩個指針變量p1和p2，這兩個指針可以指示一個整型存儲單元(即p1、p2中存放的是某存儲單元的地址，而該存儲單元恰好能存放一個整型數(shù)據(jù))。第二頁，共二十八頁，2022年，8月28日②和其它類型變量一樣，也可以在var區(qū)直接定義指針型變量。例如：vara:^real;b:^boolean;又如：typeperson=record

name:string[20];

sex:(male,female);

age:1..100

end;

varpts:^person;第三頁，共二十八頁，2022年，8月28日③pascal規(guī)定所有類型都必須先定義后使用，但只有在定義指針類型時可以例外，如下列定義是合法的：typepointer=^rec;

rec=record

a:integer;

b:char

end;第四頁，共二十八頁，2022年，8月28日（二）開辟和釋放動態(tài)存儲單元1、開辟動態(tài)存儲單元在pascal中，指針變量的值一般是通過系統(tǒng)分配的，開辟一個動態(tài)存儲單元必須調(diào)用標(biāo)準(zhǔn)過程new。new過程的調(diào)用的一般格式:New(指針變量)功能：開辟一個存儲單元，此單元能存放的數(shù)據(jù)的類型正好是指針的基類型，并把此存儲單元的地址賦給指針變量。第五頁，共二十八頁，2022年，8月28日幾點說明：①這實際上是給指針變量賦初值的基本方法。例如，設(shè)有說明：varp:^Integer;這只定義了P是一個指示整型存儲單元的指針變量，但這個單元尚未開辟，或者說P中尚未有值（某存儲單元的首地址）。當(dāng)程序中執(zhí)行了語句new(p)才給ｐ賦值，即在內(nèi)存中開辟（分配）一個整型變量存儲單元，并把此單元的地址放在變量ｐ中。示意如下圖：(a)編譯時給(b)執(zhí)行New(p)后(c)(b)的簡略表示

p分配空間生成新單元

?表示值不定新單元的地址為XXXX

內(nèi)存單元示意圖第六頁，共二十八頁，2022年，8月28日②一個指針變量只能存放一個地址。如再一次執(zhí)行New(p)語句，將在內(nèi)存中開辟另外一個新的整型變量存儲單元，并把此新單元的地址放在ｐ中，從而丟失了原存儲單元的地址。③當(dāng)不再使用ｐ當(dāng)前所指的存儲單元時，可以通過標(biāo)準(zhǔn)過程Dispose釋放該存儲單元。如：New(p);New(p);Dispose(p);第七頁，共二十八頁，2022年，8月28日⒉釋放動態(tài)存儲單元dispose語句的一般格式:dispose(指針變量);功能：釋放指針?biāo)赶虻拇鎯卧?，使指針變量的值無定義。Dispose(p);如：New(p);第八頁，共二十八頁，2022年，8月28日（三）動態(tài)存儲單元的引用在給一個指針變量賦以某存儲單元的地址后，就可以使用這個存儲單元.引用動態(tài)存儲單元一般格式：＜指針變量＞＾說明：①在用New過程給指針變量開辟了一個它所指向的存儲單元后，要使用此存儲單元的唯一方法是利用該指針。②對動態(tài)存儲單元所能進(jìn)行的操作是該類型（指針的基類型）所允許的全部操作。第九頁，共二十八頁，2022年，8月28日例1設(shè)有下列說明:

varp:^integer;i:integer;

畫出執(zhí)行下列操作后的內(nèi)存示意圖：

New(p);P^:=4;i:=p^;

(a)編譯時(b)執(zhí)行New語句(c)執(zhí)行P^:=4(d)執(zhí)行i:=P^

分配存儲

單元內(nèi)存單元示意圖第十頁，共二十八頁，2022年，8月28日（四）對指針變量的操作

⒈具有同一基類型的指針變量之間相互賦值例2設(shè)有下列說明與程序段:

varp1,p2,p3:^integer;

begin

New(P1);New(P2);New(P3);

P1:=P2;P2:=P3;

end;2、可以給指針變量賦nil值nil是PASCAL的關(guān)鍵字，它表示指針的值為"空"。例如，執(zhí)行：

p1:=ni1后，p1的值是有定義的，但p1不指向任何存儲單元。第十一頁，共二十八頁，2022年，8月28日3、可以對指針變量進(jìn)行相等或不相等的比較運(yùn)算在實際應(yīng)用中，通?？梢栽谥羔樧兞恐g，或指針變量與nil之間進(jìn)行相等(＝)或不相等(＜＞＝的比較，比較的結(jié)果為布爾量。例3輸入兩個整數(shù)，按從小到大打印出來。分析：不用指針類型可以很方便地編程，但為了示例指針的用法，我們利用指針類型。定義一個過程swap用以交換兩個指針的值。Typepointer=^integer;

varp1,p2:pointer;

procedureswap(varq1,q2:pointer);

varq:pointer;

begin

q:=q1;

q1:=q2;

q2:=q;

end;

begin

new(p1);new(p2);

write('Input2data:');readln(pq^,p2^);

ifp1^>p2^thenswap(p1,p2);

writeln('Output2data:',p1^:4,p2^:4);

end.第十二頁，共二十八頁，2022年，8月28日[例1]分別用簡單變量和指針變量交換兩個變量的值。解：設(shè)兩個變量a,b的值分別為5,8(1)用簡單變量交換：ProgramExam101;consta=5;b=8;{常量}varc:integer;beginc:=a;a:=b;b:=c;{用簡單變量交換}Type指針類型名=^基類型；

writeln(’a=’:8,a,’b=’:8,b);readlnend.

第十三頁，共二十八頁，2022年，8月28日(2)用指針變量交換：ProgramExam102;typepon=^integer;{pon為指針類型}vara,b,c:pon;{a,b,c為指針變量}beginNew（指針變量）;

new(a);new(b);new(c);{開辟動態(tài)存儲單元}a^:=5;b^:=8;{給a,b指向的存儲單元賦值}c:=a;a:=b;b:=c;{交換存儲單元的指針}writeln('a=':8,a^,‘b=':8,b^);{輸出a,b所指單元的值}Dispose（指針變量）；

readlnEnd.

第十四頁，共二十八頁，2022年，8月28日第(2)種方法，對各存儲單元所保存的值并不改變，只是交換了指向這些單元的存儲地址（指針值），可以簡略地用如下圖示說明：

第(1)種方法，直接采用變量賦值進(jìn)行交換，（實際上給各存儲單元重新賦值）其過程如下圖所示：第十五頁，共二十八頁，2022年，8月28日(圖中“--〉”表示指向存儲單元)指針類型的指針變量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）。存儲單元的值沒有重新賦值，只是存放指針值的變量交換了指針值。第十六頁，共二十八頁，2022年，8月28日[例2]利用指針對數(shù)組元素值進(jìn)行排序。

分析：①定義一個各元素為指針類型的數(shù)組a:②定義一個交換指針值的過程(swap)；③定義一個打印過程(print)；④定義過程(int)將數(shù)組b的值賦給a數(shù)組各元素所指向的各存儲單元。⑤過程pixu用交換指針值的方式，按a數(shù)組所指向的存儲單元內(nèi)容值從小到大地調(diào)整各元素指針值，實現(xiàn)“指針”排序；⑥按順序打印a數(shù)組各元素指向單元的值(a[i]^)。

第十七頁，共二十八頁，2022年，8月28日ProgramExam2;constn=8;b:array[1..n]ofinteger=(44,46,98,86,36,48,79,71);typepon=^integer;vara:array[1..n]ofpon;Procedureswap(varp1,p2:pon);{交換指針}varp:pon;beginp:=p1;p1:=p2;p2:=pend;Procedureprint;{打印數(shù)組各元素指向單元(a[i]^)的值}vari:integer;beginfori:=1tondowrite(a[i]^:6);writeln;writeln;end;

第十八頁，共二十八頁，2022年，8月28日Procedureint;{將數(shù)組b的值賦給a數(shù)組各元素所指向的存儲單元}vari:integer;beginfori:=1tondobeginnew(a[i]);a[i]^:=b[i];end;print;end;Procedurepixu;{排序}vari,j,k:integer;beginfori:=1ton-1dobegink:=i;forj:=i+1tondoifa[j]^<a[k]^thenk:=j;swap(a[k],a[i])endend;

第十九頁，共二十八頁，2022年，8月28日Begin{主程序部分}int;pixu;print;readlnEnd.第二十頁，共二十八頁，2022年，8月28日[例3]有m只猴子要選猴王，選舉辦法如下：所有猴子按1..m編號圍坐成圓圈，從第一號開始按順序1,2,..,n連續(xù)報數(shù)，凡報n號的退出到圈外。如此循環(huán)報數(shù)，直到圈上只剩下一只猴子即當(dāng)選為王。普通方法經(jīng)仔細(xì)分析，此題實質(zhì)與篩選法求素數(shù)類似。1）開始時將m個下標(biāo)變量的值均賦為1，表示大家都在圈上。2）假設(shè)我們用變量K來計數(shù)，當(dāng)報到n時（即K的值為n）退出，將相應(yīng)的下標(biāo)變量的值改賦為0，表示他已退出圈，其值不影響K的下一次計數(shù)。3）連圈問題：計數(shù)時下標(biāo)值從1開始依次增加，超n時重新賦為1，這樣做就連成圈了。第二十一頁，共二十八頁，2022年，8月28日Programmonkey;Vara:array[1..100]ofinteger;I,k,p,x:integer;Beginreadln(m,n);forI:=1tondoa[i]:=1;k:=0;p:=0;whilep<m-1do{當(dāng)P=m-1時結(jié)束任務(wù)，即只有一個人還在圈上}beginx:=0;{每次計數(shù)時清零}whilex<ndobegink:=k+1;ifk>mthenk:=1;{連成圈}x:=x+a[k];end;write(k,’‘);a[k]:=0;p:=p+1;end;End.程序說明：

K：數(shù)組下標(biāo)值，為了連成圈P：統(tǒng)計出圈個數(shù)X：報數(shù)值第二十二頁，共二十八頁，2022年，8月28日[例3]有m只猴子要選猴王，選舉辦法如下：所有猴子按1..m編號圍坐成圓圈，從第一號開始按順序1,2,..,n連續(xù)報數(shù)，凡報n號的退出到圈外。如此循環(huán)報數(shù)，直到圈上只剩下一只猴子即當(dāng)選為王。用指針（環(huán)形鏈表）編程。分析：①讓指針pon指向的單元為記錄類型，記錄內(nèi)容含有兩個域：

編號變量鏈指針變量

②用過程crea建立環(huán)形鏈；

③用過程king進(jìn)行報數(shù)處理：每報數(shù)一次t計數(shù)累加一次，當(dāng)所報次數(shù)能被n整除，就刪去該指針指向的記錄，將前一個記錄的鏈指針指向下一個記錄。刪去的指向單元（記錄）應(yīng)釋放。直到鏈指針?biāo)赶虻膯卧峭粏卧?，就說明只剩下一個記錄。

④打印指向單元記錄中編號域（num)的值。

第二十三頁，共二十八頁，2022年，8月28日programExam03;typepon=^rec;｛指向rec類型｝rec=record｛rec為記錄類型｝num:byte;｛域名num為字節(jié)類型｝nxt:pon｛域名nxt為pon類型｝end;varhd:pon;m,n:byte;procedurecrea;{建立環(huán)形鏈}vars,p:pon;i:byte;beginnew(s);hd:=s;s^.num:=1;p:=s;fori:=2tondobeginnew(s);s^.num:=i;p^.nxt:=s;p:=send;p^.nxt:=hdend;

第二十四頁，共二十八頁，2022年，8月28日procedureking;{報數(shù)處理}varp,q:pon;i,t:byte;beginp:=hd;t:=0;q:=p;repeatp:=q^.nxt;inc(t);ift=nthenbeginq^.nxt:=p^.nxt;dispose(p);t:=0endelseq:=puntilp=p^.nxt;hd:=pend;beginwrite('m,n=');readln(m,n);｛輸入m只猴，報數(shù)到n號｝crea;king;writeln('thenkingis:',hd^.num);readlnend.

第二十五頁，共二十八頁，2022年，8月28日1.請將下列八個國家的