指針變量及基本使用

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

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

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

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

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

6、用， 此時的變量 H1 的值變成無定義。3、指針變量的賦值和操作（1）賦值操作利用NEW 過程，可以給一個指針變量賦予存貯單元的地址值，而引用該存儲單元的操作是（設為指針變量） 用 P表示 P 所指的存貯單元， P:數據；表示給該單元所賦的值，P 和 P 的關系如圖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 )過程則： 計算機開辟了兩個 students 記錄類型的存貯空間，分別由 clas1 , clas2指向這兩個記錄，記錄中的數據域可用: , clas1.num , clas1.link 及 , clas2.num , clas2.link 表示，它們的存貯結構如下： li.ming clas1 90 clas1.num clas1.link wang.ping clas2 80 cl

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

9、它們之間可以互相賦值，如： var P1 , P2, P3 : integer ; . NEW ( P1 ); NEW ( P2 ); NEW ( P3 );設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 以上操作中，當執(zhí)行 P1:=P2 時,P2 的地址傳遞給 P1，此時 P1也指向 P2 所指的存貯地址，原先 P1 所指的存貯單元地址便丟失了，計算機無法訪問此單元，在程序設計中如遇到此類問題可以先收回再做賦值操作。l 給指針變量賦 NIL 值

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

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

12、沒有數組方便，若要查找某個結點，必須從表頭開始順序查找，直到找到所找結點為止，但如果進行插入、刪除操作，則不會引起數據的大量移動，應用時靈活性大，數據元素可多可少，所以也稱之為動態(tài)存貯結構。2、線性鏈表的建立線性鏈表的建立有兩種方法：一種將結點插入表尾，另一種是將結點插入表頭，書上P.175介紹了將結點插入表尾建立線性鏈表的方法，這里介紹從表頭插入結點的方法。例題1：輸入一個整數序列,按輸入數據的順序建立如下鏈表:（從表頭插入結點） 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. 運行示例 : Enter number n: ( n0 ) 52 40 68 20 the output will be : 20 68 40 52 注意：在線性鏈表操作中，一定要注意保存鏈表第一個結點的地址，不能丟失，否則鏈表無法訪問。所以習慣用head保存第一個結點地址。3、單向線性表的查找、插入和刪除的基本操作：這一部分是指針鏈接表的主要應用，這里可以分為單向鏈接表、雙向鏈

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

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

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

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

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

20、號。 分析: (1) N 個猴子按序號圍坐一圈，即第 1 個猴子后是第 2 個猴子.第N 個猴子后繼猴子是第 1 個猴子,形成循環(huán)鏈表的結構， 所以可采用循環(huán)鏈表表示這 N 個猴子;(2) 每一個結點有兩個域: 數據域猴子的編號, 指針域指向下一個猴子的地址; (3) 報數 : 即數猴子個數, 每當數到 M 時, 則該號猴子走出圈內刪除該結點, 輸出猴子號 ; (4) 重復 (3)過程, 直到只有一個猴子為止。 此算法實質是循環(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 ; （只剩一個結點）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 . 程序上機運行，當，時的結果：the

24、 king is no : 6 例題3 設有一個按字符順序排列的循環(huán)鏈表， 編一個程序完成對該鏈表的插入和刪除操作，若該鏈表只有一個頭結點，則說明表空。 分析 : 1) 設已建立一個按字典順序排列的線性表; 2) 進行插入和刪除操作，直到輸入的數是結束。程序如下: 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 ) ; 建立一個頭結點 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 );插入一個結點 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 插入 到尾部結點 else begin q.next := r ; r.next := p ; q := q.next ; end ; end ; PROCEDURE delet ( head : point ; ch1 :char ) ; 刪除一個結點 var p , q : point ; begin p := head ; q := p ; if p := p.next then begin writeln ( ' error ') ; exit ; end 鏈表已刪空 ,只剩頭結點 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 找到結點并刪除 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 模擬一個民航定票系統(tǒng)：該系統(tǒng)中有一張用雙重鏈表表示的乘客表，表中的結點按乘客的姓名（拼音字母）順序鏈接。編一個程序模擬乘客訂票或退票。設該鏈表的每個結點如下圖所示： LLINK name num RLINK 結點的結構 我們采用帶頭結點的雙重循環(huán)鏈表結構 LLIN

30、K name num RLINK 空格 0 鏈 表 的 初 始 狀 態(tài) 此題實質是雙重鏈表的插入和刪除操作，程序如下： 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; 插入 一個結點 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 )