1、第一講指針與鏈表第一講指針與鏈表 前面介紹的各種簡單類型的數(shù)據(jù)和構(gòu)造類型的數(shù)據(jù)屬于靜態(tài)數(shù)據(jù)。在程序中，這些類型的變量一經(jīng)說明，就在內(nèi)存中占有固定的存儲單元，直到該程序結(jié)束。 程序設(shè)計(jì)中，使用靜態(tài)數(shù)據(jù)結(jié)構(gòu)可以解決不少實(shí)際問題，但也有不便之處。如建立一個大小未定的姓名表，隨時(shí)要在姓名表中插入或刪除一個或幾個數(shù)據(jù)。而用新的數(shù)據(jù)類型指針類型。通過指針變量，可以在程序的執(zhí)行過程中動態(tài)地建立變量，它的個數(shù)不再受限制，可方便高效地增加或刪除若干數(shù)據(jù)，這比修改一個記錄數(shù)組更加方便。l指針的定義及操作指針的定義及操作 （1）指針類型和指針變量在Pascal中,指針變量(也稱動態(tài)變量)存放某個存儲單元的地址；也就

2、是說， 指針變量指示某個存儲單元。指針類型的格式為： 基類型說明：說明： 一個指針只能指示某一種類型數(shù)據(jù)的存儲單元，這種數(shù)據(jù)類型就是指針的基類型?；愋涂梢允浅羔?、文件外的所有類型。例如，下列說明：type pointer=integer;var p1,p2 : pointer; 定義了兩個指針變量p1和p2，這兩個指針可以指示一個整型存儲單元( 即p1、p2 中存放的是某存儲單元的地址，而該存儲單元恰好能存放一個整型數(shù)據(jù) )。 和其它類型變量一樣，也可以在var區(qū)直接定義指針型變量。 例如：var a : real;b : boolean; 又如：type person=record na

3、me : string20; sex : (maLe,femaLe); age : 1.100 end; var point : person;指針在內(nèi)存中的本質(zhì) Pascal規(guī)定所有類型都必須先定義后使用，但只有在定義指針類型時(shí)可以例外，如下列定義是合法的： type pointer=rec; /允許rec類型后定義rec=recorda : integer;b : char end;（2）開辟和釋放動態(tài)存儲單元 開辟動態(tài)存儲單元（特殊的賦值：assign 、new自動賦值） 在Pascal中，指針變量的值一般是通過系統(tǒng)分配的，開辟一個動態(tài)存儲單元必須調(diào)用標(biāo)準(zhǔn)過程new。 new過程調(diào)用的一

4、般格式： new(指針變量) 功能：開辟一個存儲單元，此單元能存放的數(shù)據(jù)的類型正好是指針的基類型，并把此存儲單元的地址賦給指針變量。說明：說明：1) 這實(shí)際上是給指針變量賦初值的基本方法。例如，設(shè)有說明：var p : integer;這只定義了P是一個指示整型存儲單元的指針變量，但這個單元尚未開辟，或者說P中尚未有值（某存儲單元的首地址）。當(dāng)程序中執(zhí)行了語句new(p)才給賦值，即在內(nèi)存中開辟（分配）一個整型變量存儲單元，并把此單元的地址放在變量中。示意如下圖：?F1A3?PPP(a)編譯時(shí)給P分配空間，？表示值不定(b)執(zhí)行new(p)后生成新單元，新單元地址為F1A3(c)(b)的簡略表

5、示2) 一個指針變量只能存放一個地址。如再一次執(zhí)行New(p)語句，將在內(nèi)存中開辟另外一個新的整型變量存儲單元，并把此新單元的地址放在中，從而丟失了原存儲單元的地址。3) 當(dāng)不再使用當(dāng)前所指的存儲單元時(shí)，可以通過標(biāo)準(zhǔn)過程Dispose釋放該存儲單元。 釋放動態(tài)存儲單元 dispose語句的一般格式：dispose(指針變量) 功能：釋放指針?biāo)赶虻拇鎯卧?，使指針變量的值無定義。例如： new(p); dispose(p);（3）動態(tài)存儲單元的引用 在給一個指針變量賦以某存儲單元的地址后，就可以使用這個存儲單元。 引用動態(tài)存儲單元一般格式：指針變量 說明： 在用New過程給指針變量開辟了一個它

6、所指向的存儲單元后，要使用此存儲單元的唯一方法是利用該指針。 對動態(tài)存儲單元所能進(jìn)行的操作是該類型（指針的基類型）所允許的全部操作。例例8.1 設(shè)有下列說明：設(shè)有下列說明：Var p : integer; i : integer;畫出執(zhí)行下列操作后的內(nèi)存示意圖：畫出執(zhí)行下列操作后的內(nèi)存示意圖： New(p); p : =4; i : =p;【分析】【分析】 如下圖所示。?4?44iiiippppP(a)編譯時(shí)分配存儲單元(b)執(zhí)行new語句(c)執(zhí)行p : = 4(d)執(zhí)行i : =p（4）對指針變量的操作 前已述及，對指針?biāo)赶虻淖兞浚ㄈ纾┛梢赃M(jìn)行指針的基類型所允許的全部操作。對指針變量本身

7、，除可用New、Dispose過程外，尚允許下列操作： 具有同一基類型的指針變量之間相互賦值例例8.2 設(shè)有下列說明與程序段設(shè)有下列說明與程序段 : var p1,p2,p3 : integer;begin new(p1); new(p2); new(p3); p1 : =p2; /同一基類型的指針變量之間可以相互賦值 p2 : =p3;end; 可以給指針變量賦nil值nil是Pascal的關(guān)鍵字，它表示指針的值為空。例如，執(zhí)行：p1 : =nil后，p1的值是有定義的，但p1不指向任何存儲單元。 可以對指針變量進(jìn)行相等或不相等的比較運(yùn)算在實(shí)際應(yīng)用中，通常可以在指針變量之間，或指針變量與ni

8、l之間進(jìn)行相等(=)或不相等()的比較，比較的結(jié)果為布爾值。例例8.3 輸入兩個整數(shù)，按從小到大打印出來。輸入兩個整數(shù)，按從小到大打印出來?！痉治觥俊痉治觥?不用指針類型可以很方便地編程，但為了示例指針的用法，我們利用指針類型。定義一個過程swap用以交換兩個指針的值。程序如下：程序如下： Type pointer=integer;var p1,p2 : pointer;procedure swap(var q1,q2 : pointer);var q : pointer;begin q : =q1; q1 : =q2; q2 : =q;end;BEGIN new(p1); new(p2);

9、readln(p1,p2); if p1p2 then swap(p1,p2); writeln(Output 2 data : ,p1 : 4,p2 : 4);END. l鏈表結(jié)構(gòu)鏈表結(jié)構(gòu) 1、單向鏈表的結(jié)構(gòu)、單向鏈表的結(jié)構(gòu)由于單向鏈表的每個結(jié)點(diǎn)都有一個數(shù)據(jù)域和一個指針域，所以，每個結(jié)點(diǎn)都可以定義成一個記錄。一般，把head稱為頭結(jié)點(diǎn)，head.next稱為頭指針。比如，有如下一個單向鏈表，如何定義這種數(shù)據(jù)結(jié)構(gòu)呢？方法如下：type pointer=nodetype; nodetype=record data:datatype; next:pointer; /嵌套定義，背會 end;var

10、head,p,q,r:pointer;2、單鏈表的建立、輸出、單鏈表的建立、輸出下面結(jié)合一個例子，給出建立并輸出單向鏈表的程序。例例8.4 從鍵盤輸入若干個正整數(shù)，請按輸入順序建立一個單向鏈表并輸出從鍵盤輸入若干個正整數(shù)，請按輸入順序建立一個單向鏈表并輸出它，輸入它，輸入-1時(shí)表示結(jié)束。時(shí)表示結(jié)束。Program creat;type pointer=nodetype; nodetype=record data:integer; next:pointer; end;var head,p,r:pointer; /r指向鏈表的當(dāng)前最后一個結(jié)點(diǎn)，可以稱為尾指針 x:integer;begin wri

11、teln(please input num(-1 is end):); read(x); new(head); /申請頭結(jié)點(diǎn) head.next:=nil; /頭結(jié)點(diǎn)初始化 r:=head; while x-1 do /讀入的數(shù)非-1 begin new(p); /則，申請一個新結(jié)點(diǎn) p.data:=x; p.next:=nil; r.next:=p; /把新結(jié)點(diǎn)鏈接到前面的鏈表中，實(shí)際上r（尾 巴）是p的直接前趨 r:=p; /尾指針后移一個 read(x); end; r.next:=nil; /最后一個結(jié)點(diǎn)的指針域賦空,其實(shí)這個可以省略 writeln(output: ); /輸出 p:

12、=head.next; /頭指針沒有數(shù)據(jù)，只要從第一個結(jié)點(diǎn)開始 就可以了 while p.nextnil do begin write(p.data:4); p:=p.next; end; write(p.data:4); /最后一個結(jié)點(diǎn)的數(shù)據(jù)單獨(dú)輸出，也可以改用 REPEAT循環(huán) readln; / 停頓，輸入回車后，才跳出程序end.思考一下l怎么更改程序，在head的data域中存入鏈表的真實(shí)長度。 為了充分利用空間和隨時(shí)統(tǒng)計(jì)出鏈表的實(shí)際結(jié)點(diǎn)個數(shù)，我們經(jīng)常把鏈表的實(shí)際結(jié)點(diǎn)個數(shù)存入到頭結(jié)點(diǎn)的數(shù)據(jù)域（head.data）中，請大家改寫上面的程序，并輸出最后的結(jié)點(diǎn)個數(shù)。參考程序見creat.p

13、as。3、查找、查找“數(shù)據(jù)域滿足一定條件的結(jié)點(diǎn)數(shù)據(jù)域滿足一定條件的結(jié)點(diǎn)”（1）從前往后找到第一個滿足條件的結(jié)點(diǎn),程序如下： p:=headnext; while (p.data x) and (p.nextnil) do p:=p.next; 找到第一個就結(jié)束 if p.data = x then 找到了處理 else 輸出不存在；（2）如果想找到所有滿足條件的結(jié)點(diǎn)，則修改如下： p:=headnext; while p.nextnil do 一個一個判斷 begin if p.data = x then 找到一個處理一個； p:=p.next; end;4、獲取第、獲取第i個結(jié)點(diǎn)的數(shù)據(jù)域個結(jié)

14、點(diǎn)的數(shù)據(jù)域function get(head:pointer;i:integer):integer;var p:pointer;j:integer;begin p:=head.next; j:=1; while (pnil) and (ji) do begin p:=p.next; j:=j+1; end; if (p nil) and (j=i) then writeln(p.data) else writeln(i not exsit!);end;5、插入一個結(jié)點(diǎn)到單鏈表中、插入一個結(jié)點(diǎn)到單鏈表中一般情況：s.next:=p.next; p.next:=s;特殊情況，插在表頭：s.next

15、:=head; head:=s;插在表尾（假設(shè)p已是表尾）:p.next:=s; p:=s;程序?qū)崿F(xiàn)時(shí)，從表頭開始找，是一致的。procedure insert(head:pointer;i:integer;x:integer); /插入X到第i個元素之前var p,s:pointer;j:integer;begin p:=head; j:=0; while (pnil) and (ji-1) then writeln(no this position!) else begin /插入 new(s); s.data:=x; s.next:=p.next; p.next:=s; end;end;

16、6、刪除單向鏈表中的第、刪除單向鏈表中的第i個結(jié)點(diǎn)（如下圖中數(shù)據(jù)域?yàn)閭€結(jié)點(diǎn)（如下圖中數(shù)據(jù)域?yàn)椤癰”的結(jié)點(diǎn)）的結(jié)點(diǎn)）procedure delete(head:pointer;i:integer;); /刪除第i個元素var p,s:pointer;j:integer;begin p:=head; j:=0; while (p.nextnil) and (ji-1) then writeln(no this position!) else begin /刪除p的后繼結(jié)點(diǎn)，假設(shè)為s s:=p.next; p.next:=p.next.next; /或p.next:=s.next dispose(s

17、); end;end;7、求單向鏈表的實(shí)際長度、求單向鏈表的實(shí)際長度 function len(head:pointer):integer; var n:integer; begin p:=head; n:=0; while p nil do begin n:=n+1; p:=p.next; end; len:=n; end;l雙向鏈表雙向鏈表 每個結(jié)點(diǎn)有兩個指針域和若干數(shù)據(jù)域，其中一個指針域指向它的直接前趨結(jié)點(diǎn)，一個指向它的直接后繼結(jié)點(diǎn)。它的優(yōu)點(diǎn)是訪問、插入、刪除更方便，速度也快了。實(shí)質(zhì)上是以空間換時(shí)間。數(shù)據(jù)結(jié)構(gòu)的定義：type pointer=nodetype; nodetype=reco

18、rd data:datatype; pre,next:pointer; /pre指向前趨，next指向后繼 end;var head,p,q,r:pointer;下面給出雙向鏈表的插入和刪除過程。Procedure delete(head:pointer;i:integer); /刪除雙向鏈表的第i個結(jié)點(diǎn)Var p:pointer;j:integer;Begin P:=head; j:=0; while (p.nextnil) and (ji) do begin p:=p.next; j:=j+1; end; /p指向第i個結(jié)點(diǎn) if p=nil then writeln(no this po

19、sition!) else begin /將結(jié)點(diǎn)P刪除 p.prenext:=p.next; /P的前趨結(jié)點(diǎn)的后繼賦值為P的后繼 p.next.pre:=p.pre; /P的后繼結(jié)點(diǎn)的前趨賦值為P的前趨 end;End;Procedure insert(head:pointer;i,x:integer); /在雙向鏈表的第i個結(jié)點(diǎn)之前插入XVar s,p:pointer;j:integer;Begin New(s); S.data:=x; P:=head; j:=0; while (p.nextnil) and (ji) do begin p:=p.next; j:=j+1; end; /p指

20、向第i個結(jié)點(diǎn) if p=nil then writeln(no this position!) else begin /將結(jié)點(diǎn)S插入到結(jié)點(diǎn)P之前 s.pre:=p.pre; /1、將S的前趨指向P的前趨 p.pre:=s; /2、將S作為P的新前趨 s.next:=p; /3、將S的后繼指向P p.pre.next:=s; /4、將P的本來前趨結(jié)點(diǎn)的后繼指向S end;End;l循環(huán)鏈表循環(huán)鏈表 1、單向循環(huán)鏈表：、單向循環(huán)鏈表： 2、雙向循環(huán)鏈表：、雙向循環(huán)鏈表：使用使用“鏈表鏈表”解題，思考的問題解題，思考的問題單向雙向循環(huán)非循環(huán)？l循環(huán)鏈表的應(yīng)用舉例循環(huán)鏈表的應(yīng)用舉例 例例8.5 約瑟夫

21、問題約瑟夫問題【問題描述】【問題描述】 有有n只猴子，按順時(shí)針方向圍成一圈（開始時(shí)編號為只猴子，按順時(shí)針方向圍成一圈（開始時(shí)編號為1，2，n），），選大王。從第選大王。從第1號猴子開始報(bào)數(shù)號猴子開始報(bào)數(shù)1，2，3，數(shù)到，數(shù)到m號時(shí)該猴子退出到圈號時(shí)該猴子退出到圈外，如此報(bào)數(shù)直到圈內(nèi)只剩下一只猴子時(shí)，此猴便是大王。你的任務(wù)是從鍵外，如此報(bào)數(shù)直到圈內(nèi)只剩下一只猴子時(shí)，此猴便是大王。你的任務(wù)是從鍵盤讀入盤讀入n,m，程序判斷輸出最后的大王是幾號？，程序判斷輸出最后的大王是幾號？ 如輸入：13 5 輸出：6 換個問法： n只猴子圍成一個圈，按順時(shí)針方向報(bào)數(shù)，報(bào)到m的出圈，直到剩下一只猴子結(jié)束。輸出猴子

22、依次出圈的序號?！緲恿休斎搿俊緲恿休斎搿?13 5【樣列輸出】【樣列輸出】 5 10 2 8 1 9 4 13 12 3 7 11the king is:6【算法分析】【算法分析】 很明顯這是一個單向循環(huán)鏈表。數(shù)據(jù)域?yàn)楹镒拥木幪?，指針域?yàn)橄乱粋€猴子的地址。從第1個猴子開始一一報(bào)數(shù)，報(bào)數(shù)實(shí)際上是計(jì)數(shù)，只要設(shè)一個計(jì)數(shù)器就可以了。當(dāng)計(jì)數(shù)器由1變化到m時(shí)，刪除該結(jié)點(diǎn)，從下一個結(jié)點(diǎn)開始繼續(xù)計(jì)數(shù)（計(jì)數(shù)器回1或者用求余運(yùn)算）。直到鏈表中只剩下一個結(jié)點(diǎn)。我們這里最好規(guī)定（1）（2）當(dāng)我們刪除節(jié)點(diǎn)的時(shí)候，P停留在要刪除的那個節(jié)點(diǎn)的前一個（3）當(dāng)我們插入節(jié)點(diǎn)的時(shí)候，P停留在要刪除的那個節(jié)點(diǎn)的前一個【參考程序一】【

23、參考程序一】program king;type point=node; node=record data:integer; next:point; end;var m,n,i:integer; p,tail,head,del:point;begin write(input n,m:); readln(n,m); new(head); /data 存入鏈表長度 head.data:=0; head.next:=nil; tail:=head; for i:=1 to n do begin new(p); p.data:=i; p.next:=nil; tail.next:=p; tail:=p;

24、 inc(head.data); end; /構(gòu)成循環(huán)鏈表 tail.next:=head.next; p:=head; while true do begin if head.data=1 then break; /當(dāng)我們進(jìn)行刪除時(shí)，定位的是要刪除的前一個節(jié)點(diǎn)處,這里假定m大于1 for i:=1 to m-1 do begin p:=p.next; end; del:=p.next; /if del= head.next then head.next:=head.next.next; /當(dāng)要刪除的是第一個的時(shí)候，head的指針就要發(fā)生變化 writeln(del.data:4); p.ne

25、xt:=del.next; dispose(del); dec(head.data); end; /writeln(the king is:,head.next.data); writeln(the king is:,p.data);end.【參考程序二】【參考程序二】program king;type point=node; node=record data:integer; next:point; end;var m,n,i:integer; p,q,head:point;begin write(input n,m:); readln(n,m); new(head); q:=head; h

26、ead.data:=1; for i:=2 to n do begin new(q.next); q:=q.next; q.data:=i; end; q.next:=head; i:=1; q:=head; repeat p:=q.next ; i:=i+1; if i mod m=0 then begin q.next:=p.next; writeln(p.data:4); dispose(p); end else q:=p until q.next=q; writeln(the king is:,q.data)end.【參考程序三】【參考程序三】program ex11-6b;type

27、pointer=node;node=record val:integer; next:pointer end;var ptr,ptb:pointer; i,j,n,m:integer;begin readln(n,m); new(ptb);ptb.val:=1;ptr:=ptb; /申請第1個結(jié)點(diǎn) for i:=2 to n do begin new(ptr.next);ptr:=ptr.next; /申請第2到n結(jié)點(diǎn) ptr.val:=i; end;ptr.next:=ptb; j:=0; /第n結(jié)點(diǎn)指針指向第1個結(jié)點(diǎn)repeat i:=1; repeat /報(bào)數(shù),報(bào)到m人出列 ptr:=p

28、tb; ptb:=ptb.next; i:=i+1; until i=m; write(ptb.val:2); ptb:=ptb.next; ptr.next:=ptb; j:=j+1; /將m結(jié)點(diǎn)驅(qū)出鏈表until j=n-1; /直到n個人均出隊(duì)為止 writeln(ptb.val:4)end.2 2、初賽題初賽題對鏈表的總結(jié)：對鏈表的總結(jié)：在鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表中，邏輯上相鄰的在鏈?zhǔn)酱鎯Y(jié)構(gòu)的線性表中，邏輯上相鄰的兩元素，其物理位置不要求相鄰。采用動態(tài)指針。數(shù)組元素兩元素，其物理位置不要求相鄰。采用動態(tài)指針。數(shù)組元素和動態(tài)變量的類型一般采用記錄類型，數(shù)據(jù)域存儲結(jié)點(diǎn)的值，和動態(tài)變量的類型一

29、般采用記錄類型，數(shù)據(jù)域存儲結(jié)點(diǎn)的值，指針域存儲后件的數(shù)組下標(biāo)或地址。最后一個結(jié)點(diǎn)的指針域指針域存儲后件的數(shù)組下標(biāo)或地址。最后一個結(jié)點(diǎn)的指針域的值為的值為nilnil?？碱}考題: :線性表若采用鏈表存貯結(jié)構(gòu)，要求內(nèi)存中可用存貯單元地址線性表若采用鏈表存貯結(jié)構(gòu)，要求內(nèi)存中可用存貯單元地址（）（）(NOIP6)(NOIP6)A.A.必須連續(xù)必須連續(xù)B. B. 部分地址必須連續(xù)部分地址必須連續(xù)C. C. 一定不連續(xù)一定不連續(xù)D. D. 連續(xù)不連續(xù)均可連續(xù)不連續(xù)均可【上機(jī)練習(xí)】【上機(jī)練習(xí)】1、狐貍捉兔子、狐貍捉兔子【問題描述】【問題描述】圍繞著山頂有10個洞，（10個洞排成圓圈）一只兔子和一只狐貍各住一

30、個洞，狐貍總想吃掉兔子。一天兔子對狐貍說，你想吃我有一個條件，第一次走一個間隔（相鄰的兩洞間為一個間隔），進(jìn)入1號洞尋找我，第二次走2個間隔，進(jìn)入3號洞尋找我，依次類推，次數(shù)不限。若能找到我，你就可以飽餐一頓，在沒找到我之前不能停止。狐貍一想只有10個洞，尋找的次數(shù)又不限，哪有找不到的道理，就答應(yīng)了條件。結(jié)果就是沒找著?，F(xiàn)請你編寫一程序，假定狐貍找了1000次，兔子躲在哪個洞里才安全。 【答案】2，4，7，9type point=node; node=record data:1.10; /洞標(biāo)號 life:boolean; / 兔子是否能生存 next:point; /單向環(huán)形鏈表 end;var head,tail,p: