指針變量及基本使用

1、第十章 指針變量及基本使用 返回上頁 內(nèi)容提要1 了解pascal 語言中靜態(tài)存儲(chǔ)、動(dòng)態(tài)存儲(chǔ)的概念以及它們?cè)诖鎯?chǔ)過程中的不同點(diǎn)；2 掌握指針類型及指針變量的定義和使用方法；3 掌握指針變量的基本操作；4 掌握線性表、線性鏈表的基本概念以及線性鏈表建立方法；5 掌握線性鏈表、循環(huán)鏈表、雙向鏈表的基本操作；6 能夠應(yīng)用線性鏈表解決一些綜合實(shí)際問題；7 為學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)知識(shí)打下基礎(chǔ)。重點(diǎn)難點(diǎn)1 重點(diǎn)：指針概念和基本操作 線性鏈表的基本概念和對(duì)線性鏈表的操作 能夠用線性鏈表操作的算法思想解決實(shí)際問題。2 難點(diǎn)：指針變量與靜態(tài)變量的區(qū)別、使用方法 靈活運(yùn)用線性鏈接表的思想解決實(shí)際問題，線性鏈表的存儲(chǔ)與訪問

2、。3 關(guān)鍵：理解指針變量的意義及基本操作，線性鏈表的概念及基本操作內(nèi)容講授一、靜態(tài)存貯和動(dòng)態(tài)存貯1、靜態(tài)存儲(chǔ)：變量一經(jīng)說明，計(jì)算機(jī)管理系統(tǒng)就在內(nèi)存中分配相應(yīng)的存貯單元，其中變量名是存貯單元的地址，而變量的值是存貯單元的內(nèi)容，該存貯單元自始至終都被該變量所占用，直到程序結(jié)束。如果變量是局部變量，那么在它的作用域內(nèi)，一經(jīng)說明也占有一定的存貯單元，直到退出其作用域?yàn)橹?。這樣的變量，在程序的執(zhí)行過程中，不能隨時(shí)使用隨時(shí)分配存貯空間，也不能在程序執(zhí)行的過程中，釋放這些空間。也就是說，一旦給這些變量分配存貯空間，無論程序是否需要，它們都要占用一定的存貯空間，以便給用戶存貯數(shù)據(jù)。我們稱具有這樣特點(diǎn)的存貯為靜

3、態(tài)存貯，它所對(duì)應(yīng)的變量稱為靜態(tài)變量。如字符類型、數(shù)組類型、記錄類型等，這類變量的特點(diǎn)是存貯方便，查找容易。2、動(dòng)態(tài)存貯：在程序執(zhí)行過程中，通過向計(jì)算機(jī)申請(qǐng)存貯空間或釋放存貯空間的命令，以達(dá)到動(dòng)態(tài)管理計(jì)算機(jī)的存貯空間，保證存貯空間的充分利用。存貯空間可以隨時(shí)申請(qǐng)、隨時(shí)釋放，這樣的存貯方式稱為動(dòng)態(tài)存貯，其變量稱為動(dòng)態(tài)變量。指針變量即為動(dòng)態(tài)變量。二、指針類型與指針變量1、指針類型定義type 指針類型標(biāo)識(shí)符 基類型名； 其中基類型名是前面我們所學(xué)過的數(shù)據(jù)類型，但不能是文件類型。 如： type POINTinteger; CHchar ; var P1, P2, P3 : POINT ; H1, H

4、2 : CH ;這里的 POINT , CH 是指針類型名，即指針類型標(biāo)識(shí)符，而等號(hào)右邊的“”符號(hào)是指針類型的特征，它必不可少，表示所定義的類型是指針類型。在上面的例子中，P1, P2 , P3 是 POINT類型的變量，它指向一個(gè)整型數(shù)的存貯單元，而CH指針變量指向一個(gè)字符型的存貯單元。 也可以用如下方式表示： var P1, P2, P3 : integer ; H1, H2 : char ; 可以用指針變量，指向一個(gè)記錄型地址，如： type POINT SSS ; SSS record NAME : STRING 8 ; SEX : FALSE , TURE end; var P1,

5、P2 : POINT ; 在這里POINT 指向一個(gè)記錄類型的存貯單元，該記錄類型由 NAME 域和 SEX域組成。這兒的 POINT 可以是尚未定義的標(biāo)識(shí)符，即可以先使用后定義，但對(duì)記錄類型來說是先定義，后使用。PASCAL 語句允許指針變量可以先使用后定義，而其它類型變量則不可以。2、指針變量的使用方法(1) 申請(qǐng)存貯單元的過程： NEW （指針變量） 如：NEW （H1）(2) 釋放動(dòng)態(tài)存貯單元當(dāng)用戶不再需要H1所指向的存貯單元時(shí)，可以通過調(diào)用DISPOSE過程來釋放該存貯單元，其方法是： DISPOSE ( H1 )當(dāng)執(zhí)行該過程時(shí)，H1 所指向的存貯單元就被釋放，歸還給計(jì)算機(jī)，可另作它

6、用， 此時(shí)的變量 H1 的值變成無定義。3、指針變量的賦值和操作（1）賦值操作利用NEW 過程，可以給一個(gè)指針變量賦予存貯單元的地址值，而引用該存儲(chǔ)單元的操作是（設(shè)為指針變量） 用 P表示 P 所指的存貯單元， P:數(shù)據(jù)；表示給該單元所賦的值，P 和 P 的關(guān)系如圖1所示: P P 地址 a 存貯單元 圖 1語句 P:' a '即將字符 'a'存放到 P 所指的存貯單元 P中。又如：type classesstudents; studentsrecord name : string 8 ; num : 1.100; link : classes ; end; v

7、ar clas1 , clas2 : classes ;通過執(zhí)行 NEW ( clas1 ) ; NEW ( clas2 )過程則： 計(jì)算機(jī)開辟了兩個(gè) students 記錄類型的存貯空間，分別由 clas1 , clas2指向這兩個(gè)記錄，記錄中的數(shù)據(jù)域可用: , clas1.num , clas1.link 及 , clas2.num , clas2.link 表示，它們的存貯結(jié)構(gòu)如下： li.ming clas1 90 clas1.num clas1.link wang.ping clas2 80 cl

8、as2.num clas2.link NIL 圖 2 假設(shè)兩個(gè)學(xué)生的姓名分別是 : " li.ming " 和" wang.ping", 他們的成績(jī)是90 和 80 , clas1.link 指向 clas2 ,其存貯形式如上圖。 :'li.ming' :'wang. clas1.num : 90 ; clas2.num : 80 ; clas1.link : clas2; clas2.link : NIL ;（2） 對(duì)指針變量的操作l 同一基類型的指針變量的操作 同一基類型的指針變量，

9、它們之間可以互相賦值，如： var P1 , P2, P3 : integer ; . NEW ( P1 ); NEW ( P2 ); NEW ( P3 );設(shè)P1：=90； P2：=85 ；P3：= 92；且執(zhí)行P1：= P2則存貯形式如下： P1 P1：= P2 p1 90 p1 90 p2 p2 p2 85 p2 85 P3 p3 92 圖 3 以上操作中，當(dāng)執(zhí)行 P1:=P2 時(shí),P2 的地址傳遞給 P1，此時(shí) P1也指向 P2 所指的存貯地址，原先 P1 所指的存貯單元地址便丟失了，計(jì)算機(jī)無法訪問此單元，在程序設(shè)計(jì)中如遇到此類問題可以先收回再做賦值操作。l 給指針變量賦 NIL 值

10、當(dāng)希望某個(gè)指針變量不指向任何存貯空間時(shí)，可以賦值為空即 NIL ，如：P1 :NIL ;l 對(duì)指針變量可以進(jìn)行關(guān)系運(yùn)算 如: if P1 < > P2 then 語句 1 else 語句 2 ; while P3 < > NIL do . . end; 關(guān)系運(yùn)算的結(jié)果仍是 FALSE , TRUE 。三、線性鏈表結(jié)構(gòu)及操作1、線性鏈表的基本結(jié)構(gòu)head 1142 1635 1789 2214 bus cup pen box 1142 1635 1789 2214 NIL 圖 4 1001 1002 1003 1004數(shù)組buscuppen box 圖 5 圖4 是一個(gè)簡(jiǎn)

11、單的鏈表結(jié)構(gòu)示意圖， 在鏈表結(jié)構(gòu)中我們稱一個(gè)基本的存貯空間為一個(gè)結(jié)點(diǎn)，其形式如下： 數(shù)據(jù)域指針域 從表中還可以看出，相鄰結(jié)點(diǎn)的地址是互不連續(xù)的，它們靠指針將相互間的關(guān)系連接起來，如果表中某個(gè)結(jié)點(diǎn)的連接指針丟失，則該線性表無法訪問和操作，因此在使用指針變量連接結(jié)點(diǎn)時(shí)必須注意，每個(gè)結(jié)點(diǎn)的地址都應(yīng)該用指針變量連接，頭指針的地址一定要保存，以便在程序設(shè)計(jì)中能夠訪問到線性表，并且能對(duì)其操作。圖 5 是數(shù)組存貯結(jié)構(gòu)，它的存貯單元的地址是連續(xù)的。 比較鏈表的存貯結(jié)構(gòu)和數(shù)組存貯結(jié)構(gòu)我們可以看到：數(shù)組存貯訪問方便，查找方便，但若進(jìn)行插入、刪除操作，將引起數(shù)據(jù)的移動(dòng)，它是一種靜態(tài)存貯；而對(duì)鏈表結(jié)構(gòu)進(jìn)行訪問、查找就

12、沒有數(shù)組方便，若要查找某個(gè)結(jié)點(diǎn)，必須從表頭開始順序查找，直到找到所找結(jié)點(diǎn)為止，但如果進(jìn)行插入、刪除操作，則不會(huì)引起數(shù)據(jù)的大量移動(dòng)，應(yīng)用時(shí)靈活性大，數(shù)據(jù)元素可多可少，所以也稱之為動(dòng)態(tài)存貯結(jié)構(gòu)。2、線性鏈表的建立線性鏈表的建立有兩種方法：一種將結(jié)點(diǎn)插入表尾，另一種是將結(jié)點(diǎn)插入表頭，書上P.175介紹了將結(jié)點(diǎn)插入表尾建立線性鏈表的方法，這里介紹從表頭插入結(jié)點(diǎn)的方法。例題1：輸入一個(gè)整數(shù)序列,按輸入數(shù)據(jù)的順序建立如下鏈表:（從表頭插入結(jié)點(diǎn)） head 20 68 40 52 NIL PROGRAM exp10_1; type ref object objectrecord num : integer

13、; next : ref ; end ; var p , q , r : ref ; n : integer ; BEGIN write ( ' Enter number n: ( n 0 ) ' ) ; readln ( n ) ; p: NIL ; r : p ; while n < > 0 do 插入表頭,形成鏈表 begin NEW ( q ) ; q.num := n ; q.next := p ; p := q ; read ( n ) ; end ; q := p ; 保存頭指針的地址 writeln ( ' the output will b

14、e : ' ) ; while q < > NIL do begin write ( q.num : 8 ) ; q := q.next ; end ; 打印鏈表過程 writeln ; END. 運(yùn)行示例 : Enter number n: ( n0 ) 52 40 68 20 the output will be : 20 68 40 52 注意：在線性鏈表操作中，一定要注意保存鏈表第一個(gè)結(jié)點(diǎn)的地址，不能丟失，否則鏈表無法訪問。所以習(xí)慣用head保存第一個(gè)結(jié)點(diǎn)地址。3、單向線性表的查找、插入和刪除的基本操作：這一部分是指針鏈接表的主要應(yīng)用，這里可以分為單向鏈接表、雙向鏈

15、表、循環(huán)鏈表三種形式鏈表關(guān)于查找操作這里不再贅述，重點(diǎn)用圖示方法說明線性鏈接表的插入、刪除操作及相應(yīng)命令。（1）插入操作 ： 如圖6所示單向鏈接表 q r head NIL P P P NIL 插入到頭結(jié)點(diǎn): 插入到某一個(gè)結(jié)點(diǎn): 插入到尾部: P.next:=head; P.next:=q.next; r.next :=p; head:= p; q.next:= p ; r := p ; q:= x ; 圖6 （2）刪除操作 ： 如圖7所示單向鏈接表 q p head NIL 刪除頭結(jié)點(diǎn) 刪除某一個(gè)結(jié)點(diǎn) P：=head ; q.next := p.next ; Head:=head.

16、next; dispose ( p ) ; Dispose (p); 圖7（3）求線性表的長(zhǎng)度：即統(tǒng)計(jì)結(jié)點(diǎn)個(gè)數(shù)。4、雙向鏈表、循環(huán)鏈表的知識(shí)及操作（1） 雙向鏈表在單向鏈表中，結(jié)點(diǎn)的域中只有一個(gè)指針域，該指針域用于指向后繼元素的地址，靠一個(gè)指針將線性表連接起來。然而在處理某些問題中，需要有雙向指針將前后的相關(guān)結(jié)點(diǎn)聯(lián)系起來，這種用兩個(gè)指針域?qū)⒕€性表的結(jié)點(diǎn)連接起來的鏈表稱為雙x向鏈表。每個(gè)結(jié)點(diǎn)的兩個(gè)指針，一個(gè)指針指向它的前趨結(jié)點(diǎn)，另一個(gè)指針指向它的后繼結(jié)點(diǎn)。其形式如下圖：head P NIL NIL NIL 圖 8 這樣的雙向鏈表，若對(duì)鏈表進(jìn)行訪問、插入、刪除操作是很方便的，速度也加快了。它是用消

17、耗內(nèi)存的代價(jià)，換取時(shí)間的。雙向鏈表的結(jié)點(diǎn)定義的方法，基本等同單向鏈表，所不同的是結(jié)點(diǎn)中增加了一個(gè)指針域。如：type point letter letterrecord let : char ; Llink : point ; Rlink : point ; end ; 對(duì)雙向鏈表我們?nèi)钥梢赃M(jìn)行插入、刪除、歸并等操作，而且很方便。如：在結(jié)點(diǎn)之后插入一個(gè)q結(jié)點(diǎn)，其方法是：q.rlink := p.rlink ; q.llink := p ; p.rlink := q ; 刪除結(jié)點(diǎn) 的操作 : p.llink.rlink := p.rlink ;讀者可以自己建立一個(gè)雙向鏈表，對(duì)鏈表進(jìn)行插入、刪除等

18、操作，有關(guān)這方面的程序我們不再做詳細(xì)解答。（2） 循環(huán)鏈表單向鏈表、雙向鏈表它們的共同特點(diǎn)是：頭結(jié)點(diǎn)的指針都是指向下一個(gè)后繼結(jié)點(diǎn)，尾部都是指向空；對(duì)于雙向鏈表頭結(jié)點(diǎn)和尾結(jié)點(diǎn)都有一個(gè)指向空，即不指向任何地址的指針量。如果在單向鏈表中，我們將最后一個(gè)結(jié)點(diǎn)的指針變量不指向空而是指向頭結(jié)點(diǎn)，這樣從頭結(jié)點(diǎn)開始，每一個(gè)結(jié)點(diǎn)都有一個(gè)指向后繼結(jié)點(diǎn)的指針，而最后一個(gè)結(jié)點(diǎn)的指針變量指向頭結(jié)點(diǎn)形成一個(gè)循環(huán)的鏈，如下圖所示： P head 頭結(jié)點(diǎn) 單 向 循 環(huán) 鏈 表 圖 9 P head 頭結(jié)點(diǎn) 雙 向 循 環(huán) 鏈 表 圖 10 在上面兩個(gè)循環(huán)鏈表中，我們都多定義了一個(gè)特殊的頭結(jié)點(diǎn)，其目的在于方便對(duì)循環(huán)鏈表的操作

19、。如當(dāng)我們對(duì)循環(huán)鏈表做刪除操作時(shí)，若表為空，有了頭結(jié)點(diǎn)便可以方便判斷表空，即如下圖11所示： head.link:=head head.rlink:=head ; head.llink:=head ; 圖 11 表空的表示當(dāng)頭指針和尾指針都指向頭結(jié)點(diǎn)時(shí)，則表示該循環(huán)鏈表為空。有關(guān)循環(huán)鏈表的插入、刪除、歸并等操作和運(yùn)算，這兒不再作詳細(xì)介紹，我們通過例題說明單向鏈表和循環(huán)鏈表的應(yīng)用。5綜合應(yīng)用例題2 約瑟夫問題：有個(gè)猴子，按順時(shí)針方向圍成一圈，選大王。從第號(hào)開始報(bào)數(shù)按順序1, 2, .，數(shù)到號(hào)時(shí)該猴子退出到圈外，如此報(bào)數(shù)直到圈內(nèi)只剩下一個(gè)猴子時(shí)，則此猴子便是大王。由鍵盤輸入、打印出走出圈內(nèi)的猴子序

20、號(hào)。 分析: (1) N 個(gè)猴子按序號(hào)圍坐一圈，即第 1 個(gè)猴子后是第 2 個(gè)猴子.第N 個(gè)猴子后繼猴子是第 1 個(gè)猴子,形成循環(huán)鏈表的結(jié)構(gòu)， 所以可采用循環(huán)鏈表表示這 N 個(gè)猴子;(2) 每一個(gè)結(jié)點(diǎn)有兩個(gè)域: 數(shù)據(jù)域猴子的編號(hào), 指針域指向下一個(gè)猴子的地址; (3) 報(bào)數(shù) : 即數(shù)猴子個(gè)數(shù), 每當(dāng)數(shù)到 M 時(shí), 則該號(hào)猴子走出圈內(nèi)刪除該結(jié)點(diǎn), 輸出猴子號(hào) ; (4) 重復(fù) (3)過程, 直到只有一個(gè)猴子為止。 此算法實(shí)質(zhì)是循環(huán)鏈表的刪除操作。 程序如下：PROGRAM exp4_6 ; type pointmonkey ; monkeyrecord num : integer ; next

21、: point ; end ; var head , p , q : point ; n , m : integer ; PROCEDURE creat ( var head : point ; n : integer ) ; var （建立循環(huán)鏈表 ）p , q :point ; i : integer ; begin NEW ( p ) ; head := p ; p.num := 1 ; q := p ; for i:=2 to n do begin NEW (p ); p.num := i ; q.next := p ; q:= p; end ; q.next := head ; en

22、d ; PROCEDURE select ( var head : point ; m :integer ) ; var （選舉大王的過程）p , q :point ; i , x : integer ; begin p := head ; x := 1 ; q := p ; （ Q 為 P 的前趨指針 ） repeat p := q.next ; x := x 1 ; if x mod m = 0 then begin q.next := p.next ; write ( p.num : 8 ) ; dispose ( p ) ; end 猴子出圈 else q := p ; until p

23、 := p.next ; （只剩一個(gè)結(jié)點(diǎn)）writeln ; head := p ; end ; BEGIN 主程序 write ( ' Enter monkey num n : ' ); read ( n ) ; writeln ; write ( ' number m : ') ; read ( m ) ; writeln ; creat ( head , n ) ; elect ( head , m ) ; writeln ( ' the king is no : ' head.num ) ; END . 程序上機(jī)運(yùn)行，當(dāng)，時(shí)的結(jié)果：the

24、 king is no : 6 例題3 設(shè)有一個(gè)按字符順序排列的循環(huán)鏈表， 編一個(gè)程序完成對(duì)該鏈表的插入和刪除操作，若該鏈表只有一個(gè)頭結(jié)點(diǎn)，則說明表空。 分析 : 1) 設(shè)已建立一個(gè)按字典順序排列的線性表; 2) 進(jìn)行插入和刪除操作，直到輸入的數(shù)是結(jié)束。程序如下: PROGRAM exp4_7 ; type point letter ; letterrecord ch : char ; next : point ; var head , p , q : point ; chr : char ; PROCEDURE creat ( var head : point ) ; 建立循環(huán)鏈表 var

25、p, q : point ; BEGIN NEW ( p ) ; head := p ; q := p ; write ( 'Enter a char : ' ) ; read ( chr ) ; 建立一個(gè)頭結(jié)點(diǎn) while chr < > '# ' do begin p.ch := chr ; q.next := p ; q : = q.next ; NEW ( P ) ; write ( 'Enter a char : ' ) ; read ( chr ) ; end ; q.next :=head ; p := head ; e

26、nd ; 建立完循環(huán)鏈表 PROCEDURE insert ( head : point ; ch1 :char );插入一個(gè)結(jié)點(diǎn) var p , q , r : point ; begin p := head ; q := p ; NEW ( r ) ; r.ch:= ch1 ; r.next := NIL ; while ( ch1 > p.ch ) and ( p.next < > head ) do begin q := p ; p := p.next ; end ; 比較和查找 if p.next = head then begin P.next := r ; r.

27、next := head ; p := p.next ; end 插入 到尾部結(jié)點(diǎn) else begin q.next := r ; r.next := p ; q := q.next ; end ; end ; PROCEDURE delet ( head : point ; ch1 :char ) ; 刪除一個(gè)結(jié)點(diǎn) var p , q : point ; begin p := head ; q := p ; if p := p.next then begin writeln ( ' error ') ; exit ; end 鏈表已刪空 ,只剩頭結(jié)點(diǎn) else begin

28、repeat q := p ; p := p.next ; until ( p.ch = ch1 ) or ( p = head ) if p.ch = ch1 then begin q.next := p.next ; writeln ( p.ch ) ; dispose ( p ) ; end 找到結(jié)點(diǎn)并刪除 else writeln ( ' not found ') ; end ; else end end;BEGIN 主程序 head := NIL ; creat ( head ); writeln ( ' Enter number n : 1 , 2 '

29、;) ; case n of 1 : write ('input a chr :'); read( chr ); insert(head ,chr); 2 : write (' input a chr :');read( chr ); delet( head , chr); end ;END . 例4 模擬一個(gè)民航定票系統(tǒng)：該系統(tǒng)中有一張用雙重鏈表表示的乘客表，表中的結(jié)點(diǎn)按乘客的姓名（拼音字母）順序鏈接。編一個(gè)程序模擬乘客訂票或退票。設(shè)該鏈表的每個(gè)結(jié)點(diǎn)如下圖所示： LLINK name num RLINK 結(jié)點(diǎn)的結(jié)構(gòu) 我們采用帶頭結(jié)點(diǎn)的雙重循環(huán)鏈表結(jié)構(gòu) LLIN

30、K name num RLINK 空格 0 鏈 表 的 初 始 狀 態(tài) 此題實(shí)質(zhì)是雙重鏈表的插入和刪除操作，程序如下： PROGRAM exp4_8 ; const len=15 ; type Link= passen ; passen= record name : stringlen ; num : integer ; Llink , Rlink :Link; end; var head :link ; fname:string8; ch :char ; PROCEDURE READch ( var cha : char); 輸入 var f: file of char ; BEGIN AS

31、SIGN (f,'con:'); RESET (f) ; cha:=f; while not ( cha in '1'.'5') do begin read(f); cha:=f; end ; close (f); writeln(cha); end; 插入 一個(gè)結(jié)點(diǎn) PROCEDURE print ; 輸出 var f : text ; i : integer ; next : link ; begin ASSIGN ( f, fname ); REWRITE (f); next := head.rlink ; repeat writeln (

32、f, ); next:=next.rlink ; i:=i+1 ; until next=head ; writeln(f,'* all numbers :',i:5,'*'); close(f); end; PROCEDURE dele; 退票 var na : string8 ; next : link ; begin write('input your name :'); readln( na); next:=head.rlink ; while ( <> na ) and (next <> head ) do next :=next .rlink ; if next .name =na then begin next.rlink.llink:=next.llink; next.llink.rlink:=next.rlink; writeln('*delete end *'); end else writeln( '* not found *'); end; dele PROCEDURE newpoint; 訂購票 var P,Q : link ; PROCEDURE takeone ; begin NEW ( p )