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

1、動(dòng)態(tài)數(shù)據(jù)類型指針第1頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一一、指針的定義及操作（一）指針類型和指針變量在pascal中,指針變量(也稱動(dòng)態(tài)變量)存放某個(gè)存儲(chǔ)單元的地址；也就是說， 指針變量指示某個(gè)存儲(chǔ)單元。指針類型的格式為:基類型說明: 一個(gè)指針只能指示某一種類型數(shù)據(jù)的存儲(chǔ)單元，這種數(shù)據(jù)類型就是指針的基類型，基類型可以是除指針、文件外的所有類型。type pointer=Integer;var p1,p2:pointer;定義了兩個(gè)指針變量p1和p2，這兩個(gè)指針可以指示一個(gè)整型存儲(chǔ)單元(即p1、p2 中存放的是某存儲(chǔ)單元的地址，而該存儲(chǔ)單元恰好能存放一個(gè)整型數(shù)據(jù))。第2頁，

2、共28頁，2022年，5月20日，15點(diǎn)11分，星期一和其它類型變量一樣，也可以在var區(qū)直接定義指針型變量。例如：var a:real; b:boolean;又如：type person=recordname:string20;sex:(male,female);age:1.100end;var pts:person;第3頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一pascal規(guī)定所有類型都必須先定義后使用，但只有在定義指針類型時(shí)可以例外，如下列定義是合法的：type pointer=rec;rec=recorda:integer;b:charend;第4頁，共28頁，2022

3、年，5月20日，15點(diǎn)11分，星期一（二）開辟和釋放動(dòng)態(tài)存儲(chǔ)單元1、開辟動(dòng)態(tài)存儲(chǔ)單元在pascal中，指針變量的值一般是通過系統(tǒng)分配的，開辟一個(gè)動(dòng)態(tài)存儲(chǔ)單元必須調(diào)用標(biāo)準(zhǔn)過程new。new過程的調(diào)用的一般格式:New(指針變量)功能：開辟一個(gè)存儲(chǔ)單元，此單元能存放的數(shù)據(jù)的類型正好是指針的基類型，并把此存儲(chǔ)單元的地址賦給指針變量。第5頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一幾點(diǎn)說明：這實(shí)際上是給指針變量賦初值的基本方法。例如，設(shè)有說明：var p:Integer;這只定義了P是一個(gè)指示整型存儲(chǔ)單元的指針變量，但這個(gè)單元尚未開辟，或者說P中尚未有值（某存儲(chǔ)單元的首地址）。當(dāng)程序中執(zhí)

4、行了語句new(p)才給賦值，即在內(nèi)存中開辟（分配）一個(gè)整型變量存儲(chǔ)單元，并把此單元的地址放在變量中。示意如下圖：(a)編譯時(shí)給 (b)執(zhí)行New(p)后 (c)(b)的簡略表示 p分配空間 生成新單元 ?表示值不定 新單元的地址為XXXX內(nèi)存單元示意圖第6頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一一個(gè)指針變量只能存放一個(gè)地址。如再一次執(zhí)行New(p)語句，將在內(nèi)存中開辟另外一個(gè)新的整型變量存儲(chǔ)單元，并把此新單元的地址放在中，從而丟失了原存儲(chǔ)單元的地址。當(dāng)不再使用當(dāng)前所指的存儲(chǔ)單元時(shí)，可以通過標(biāo)準(zhǔn)過程Dispose釋放該存儲(chǔ)單元。如： New(p); New(p);Dispos

5、e(p);第7頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一釋放動(dòng)態(tài)存儲(chǔ)單元dispose語句的一般格式: dispose(指針變量);功能：釋放指針?biāo)赶虻拇鎯?chǔ)單元，使指針變量的值無定義。Dispose(p);如： New(p); 第8頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一（三）動(dòng)態(tài)存儲(chǔ)單元的引用在給一個(gè)指針變量賦以某存儲(chǔ)單元的地址后，就可以使用這個(gè)存儲(chǔ)單元.引用動(dòng)態(tài)存儲(chǔ)單元一般格式：指針變量說明：在用New過程給指針變量開辟了一個(gè)它所指向的存儲(chǔ)單元后，要使用此存儲(chǔ)單元的唯一方法是利用該指針。對動(dòng)態(tài)存儲(chǔ)單元所能進(jìn)行的操作是該類型（指針的基類型）所允許的全部操作

6、。第9頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一例1 設(shè)有下列說明:var p:integer; i:integer;畫出執(zhí)行下列操作后的內(nèi)存示意圖：New(p); P:=4;i:=p; (a)編譯時(shí) (b)執(zhí)行New語句(c)執(zhí)行P:=4 (d)執(zhí)行i:=P分配存儲(chǔ) 單元 內(nèi)存單元示意圖第10頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一（四）對指針變量的操作 具有同一基類型的指針變量之間相互賦值例2 設(shè)有下列說明與程序段:var p1,p2,p3:integer;begin New(P1) ; New(P2); New(P3);P1:=P2; P2:=P3;en

7、d;2、可以給指針變量賦nil值nil是PASCAL的關(guān)鍵字，它表示指針的值為空。例如，執(zhí)行：p1:=ni1后，p1的值是有定義的，但p1不指向任何存儲(chǔ)單元。第11頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一3、可以對指針變量進(jìn)行相等或不相等的比較運(yùn)算在實(shí)際應(yīng)用中，通常可以在指針變量之間，或指針變量與nil之間進(jìn)行相等()或不相等(的比較，比較的結(jié)果為布爾量。例3 輸入兩個(gè)整數(shù)，按從小到大打印出來。分析：不用指針類型可以很方便地編程，但為了示例指針的用法，我們利用指針類型。定義一個(gè)過程swap用以交換兩個(gè)指針的值。Type pointer=integer;var p1,p2:po

8、inter;procedure swap(var q1,q2:pointer);var q:pointer;beginq:=q1;q1:=q2;q2:=q;end;beginnew(p1);new(p2);write(Input 2 data:);readln(pq,p2);if p1p2 then swap(p1,p2);writeln(Output 2 data:,p1:4,p2:4);end.第12頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一例1 分別用簡單變量和指針變量交換兩個(gè)變量的值。 解：設(shè)兩個(gè)變量a,b的值分別為5, 8 (1)用簡單變量交換： Program Ex

9、am101; const a=5; b=8; 常量 var c: integer; begin c:=a; a:=b; b:=c; 用簡單變量交換Type 指針類型名 = 基類型； writeln(a=:8, a, b=:8, b ); readln end. 第13頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一(2)用指針變量交換： Program Exam102; type pon= integer; pon為指針類型 var a,b,c: pon; a,b,c為指針變量 begin New（指針變量）; new(a ); new(b ); new(c ); 開辟動(dòng)態(tài)存儲(chǔ)單元

10、a :=5; b :=8; 給a,b指向的存儲(chǔ)單元賦值 c:=a; a:=b; b:=c; 交換存儲(chǔ)單元的指針 writeln(a=:8, a , b=:8, b ); 輸出a,b所指單元的值 Dispose（指針變量）； readln End. 第14頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一第(2)種方法，對各存儲(chǔ)單元所保存的值并不改變，只是交換了指向這些單元的存儲(chǔ)地址（指針值），可以簡略地用如下圖示說明： 第(1)種方法，直接采用變量賦值進(jìn)行交換，（實(shí)際上給各存儲(chǔ)單元重新賦值）其過程如下圖所示：第15頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一(圖中“-”表

11、示指向存儲(chǔ)單元)指針類型的指針變量a,b存有各指向單元的地址值，將指針交換賦值步驟為：將c:=a (讓c具有a的指針值);將a:=b (讓a具有b的指針值);將b:=c (讓b具有c的指針值);最后輸出a,b所指向存儲(chǔ)單元(a 和b )的值，此時(shí)的a指向了存儲(chǔ)整數(shù)8的單元（即a = 8），b指向了存儲(chǔ)整數(shù)5的單元（即b = 5）。存儲(chǔ)單元的值沒有重新賦值，只是存放指針值的變量交換了指針值。第16頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一例2 利用指針對數(shù)組元素值進(jìn)行排序。 分析：定義一個(gè)各元素為指針類型的數(shù)組a :定義一個(gè)交換指針值的過程(swap)；定義一個(gè)打印過程(prin

12、t)；定義過程(int)將數(shù)組b的值賦給a數(shù)組各元素所指向的各存儲(chǔ)單元。過程pixu用交換指針值的方式，按a數(shù)組所指向的存儲(chǔ)單元內(nèi)容值從小到大地調(diào)整各元素指針值，實(shí)現(xiàn)“指針”排序；按順序打印a數(shù)組各元素指向單元的值(a i )。 第17頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一Program Exam2; const n=8; b: array1.n of integer=(44,46,98,86,36,48,79,71); type pon= integer; var a: array1.n of pon; Procedure swap(var p1, p2: pon); 交

13、換指針 var p: pon; begin p:=p1; p1:=p2; p2:=p end; Procedure print; 打印數(shù)組各元素指向單元(a i )的值 var i: integer; begin for i:=1 to n do write(a i :6); writeln; writeln; end; 第18頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一 Procedure int; 將數(shù)組b的值賦給a數(shù)組各元素所指向的存儲(chǔ)單元 var i: integer; begin for i:=1 to n do begin new(a i ); a i :=b i ;

14、 end; print; end; Procedure pixu; 排序 var i,j,k: integer; begin for i:=1 to n-1 do begin k:=i; for j:=i+1 to n do if aj ak then k:=j; swap(ak, a i ) end end; 第19頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一Begin 主程序部分 int; pixu; print; readln End.第20頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一例3 有m只猴子要選猴王，選舉辦法如下：所有猴子按1.m編號(hào)圍坐成圓圈，從第

15、一號(hào)開始按順序1,2, .,n連續(xù)報(bào)數(shù)，凡報(bào)n號(hào)的退出到圈外。如此循環(huán)報(bào)數(shù)，直到圈上只剩下一只猴子即當(dāng)選為王。普通方法經(jīng)仔細(xì)分析，此題實(shí)質(zhì)與篩選法求素?cái)?shù)類似。1）開始時(shí)將m個(gè)下標(biāo)變量的值均賦為1，表示大家都在圈上。2）假設(shè)我們用變量K來計(jì)數(shù)，當(dāng)報(bào)到n時(shí)（即K的值為n）退出，將相應(yīng)的下標(biāo)變量的值改賦為0，表示他已退出圈，其值不影響K的下一次計(jì)數(shù)。3）連圈問題：計(jì)數(shù)時(shí)下標(biāo)值從1開始依次增加，超n時(shí)重新賦為1，這樣做就連成圈了。第21頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一Program monkey;Var a:array1.100 of integer; I,k,p,x:int

16、eger;Begin readln(m,n); for I:=1 to n do ai:=1; k:=0;p:=0; while pm-1 do 當(dāng)P=m-1時(shí)結(jié)束任務(wù)，即只有一個(gè)人還在圈上 begin x:=0; 每次計(jì)數(shù)時(shí)清零 while xm then k:=1; 連成圈 x:=x+ak; end; write(k, ); ak:=0; p:=p+1; end;End.程序說明： K：數(shù)組下標(biāo)值，為了連成圈 P：統(tǒng)計(jì)出圈個(gè)數(shù) X：報(bào)數(shù)值第22頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一例3 有m只猴子要選猴王，選舉辦法如下：所有猴子按1.m編號(hào)圍坐成圓圈，從第一號(hào)開始按順序

17、1,2, .,n連續(xù)報(bào)數(shù)，凡報(bào)n號(hào)的退出到圈外。如此循環(huán)報(bào)數(shù)，直到圈上只剩下一只猴子即當(dāng)選為王。用指針（環(huán)形鏈表）編程。分析：讓指針pon指向的單元為記錄類型，記錄內(nèi)容含有兩個(gè)域： 編號(hào)變量 鏈指針變量 用過程crea建立環(huán)形鏈； 用過程king進(jìn)行報(bào)數(shù)處理：每報(bào)數(shù)一次t計(jì)數(shù)累加一次，當(dāng)所報(bào)次數(shù)能被n整除，就刪去該指針指向的記錄，將前一個(gè)記錄的鏈指針指向下一個(gè)記錄。刪去的指向單元（記錄）應(yīng)釋放。直到鏈指針?biāo)赶虻膯卧峭粏卧?，就說明只剩下一個(gè)記錄。 打印指向單元記錄中編號(hào)域（num)的值。 第23頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一program Exam03; typ

18、e pon= rec; 指向rec類型 rec=record rec為記錄類型 num: byte; 域名num為字節(jié)類型 nxt: pon 域名nxt為pon類型 end; var hd: pon; m, n: byte; procedure crea; 建立環(huán)形鏈 var s,p: pon; i: byte; begin new(s); hd:=s; s . num :=1; p:=s; for i:=2 to n do begin new(s); s . num :=i; p . nxt:=s; p:=s end; p . nxt :=hd end; 第24頁，共28頁，2022年，5月

19、20日，15點(diǎn)11分，星期一procedure king; 報(bào)數(shù)處理 var p,q: pon; i, t: byte; begin p:=hd; t:=0; q:=p; repeat p:=q . nxt; inc(t); if t=n then begin q . nxt :=p . nxt; dispose(p); t:=0 end else q:=p until p=p . nxt; hd:=p end; begin write(m, n=); readln(m, n); 輸入m只猴，報(bào)數(shù)到n號(hào) crea; king; writeln(then king is :, hd . num); readln end. 第25頁，共28頁，2022年，5月20日，15點(diǎn)11分，星期一1.請將下列八個(gè)國家的國名按英文字典順序排列輸出。 China(中國) Japan(日本) Cancda(加拿大) Korea(朝鮮) England(英格蘭) France(法蘭西) American(美國) India(