pascal-指針與鏈表電子版本

1、Good is good, but better carries it.精益求精，善益求善。pascal-指針與鏈表-指針與鏈表前面介紹的各種簡(jiǎn)單類型的數(shù)據(jù)和構(gòu)造類型的數(shù)據(jù)屬于靜態(tài)數(shù)據(jù)。在程序中，這些類型的變量一經(jīng)說(shuō)明，就在內(nèi)存中占有固定的存儲(chǔ)單元，直到該程序結(jié)束。程序設(shè)計(jì)中，使用靜態(tài)數(shù)據(jù)結(jié)構(gòu)可以解決不少實(shí)際問題，但也有不便之處。如建立一個(gè)大小未定的姓名表，隨時(shí)要在姓名表中插入或刪除一個(gè)或幾個(gè)數(shù)據(jù)。而用新的數(shù)據(jù)類型指針類型。通過(guò)指針變量，可以在程序的執(zhí)行過(guò)程中動(dòng)態(tài)地建立變量，它的個(gè)數(shù)不再受限制，可方便地高效地增加或刪除若干數(shù)據(jù)。一、指針的定義及操作（一）指針類型和指針變量在pascal中,指針

2、變量(也稱動(dòng)態(tài)變量)存放某個(gè)存儲(chǔ)單元的地址；也就是說(shuō)，指針變量指示某個(gè)存儲(chǔ)單元。指針類型的格式為:基類型說(shuō)明:一個(gè)指針只能指示某一種類型數(shù)據(jù)的存儲(chǔ)單元，這種數(shù)據(jù)類型就是指針的基類型?；愋涂梢允浅羔?、文件外的所有類型。例如，下列說(shuō)明：typepointer=Integer;varp1,p2:pointer;定義了兩個(gè)指針變量p1和p2，這兩個(gè)指針可以指示一個(gè)整型存儲(chǔ)單元(即p1、p2中存放的是某存儲(chǔ)單元的地址，而該存儲(chǔ)單元恰好能存放一個(gè)整型數(shù)據(jù))。和其它類型變量一樣，也可以在var區(qū)直接定義指針型變量。例如：vara:real;b:boolean;又如：typeperson=recordna

3、me:string20;sex:(male,female);age:1.100end;varpts:person;pascal規(guī)定所有類型都必須先定義后使用，但只有在定義指針類型時(shí)可以例外，如下列定義是合法的：typepointer=rec;rec=recorda:integer;b:charend;（二）開辟和釋放動(dòng)態(tài)存儲(chǔ)單元1、開辟動(dòng)態(tài)存儲(chǔ)單元在pascal中，指針變量的值一般是通過(guò)系統(tǒng)分配的，開辟一個(gè)動(dòng)態(tài)存儲(chǔ)單元必須調(diào)用標(biāo)準(zhǔn)過(guò)程new。new過(guò)程的調(diào)用的一般格式:New(指針變量)功能：開辟一個(gè)存儲(chǔ)單元，此單元能存放的數(shù)據(jù)的類型正好是指針的基類型，并把此存儲(chǔ)單元的地址賦給指針變量。說(shuō)明：

4、這實(shí)際上是給指針變量賦初值的基本方法。例如，設(shè)有說(shuō)明：varp:Integer;這只定義了P是一個(gè)指示整型存儲(chǔ)單元的指針變量，但這個(gè)單元尚未開辟，或者說(shuō)P中尚未有值（某存儲(chǔ)單元的首地址）。當(dāng)程序中執(zhí)行了語(yǔ)句new(p)才給賦值，即在內(nèi)存中開辟（分配）一個(gè)整型變量存儲(chǔ)單元，并把此單元的地址放在變量中。示意如下圖：(a)編譯時(shí)給(b)執(zhí)行New(p)后(c)(b)的簡(jiǎn)略表示p分配空間生成新單元?表示值不定新單元的地址為XXXX內(nèi)存單元示意圖一個(gè)指針變量只能存放一個(gè)地址。如再一次執(zhí)行New(p)語(yǔ)句，將在內(nèi)存中開辟另外一個(gè)新的整型變量存儲(chǔ)單元，并把此新單元的地址放在中，從而丟失了原存儲(chǔ)單元的地址。當(dāng)

5、不再使用當(dāng)前所指的存儲(chǔ)單元時(shí)，可以通過(guò)標(biāo)準(zhǔn)過(guò)程Dispose釋放該存儲(chǔ)單元。釋放動(dòng)態(tài)存儲(chǔ)單元dispose語(yǔ)句的一般格式:dispose(指針變量)功能：釋放指針?biāo)赶虻拇鎯?chǔ)單元，使指針變量的值無(wú)定義。（三）動(dòng)態(tài)存儲(chǔ)單元的引用在給一個(gè)指針變量賦以某存儲(chǔ)單元的地址后，就可以使用這個(gè)存儲(chǔ)單元。引用動(dòng)態(tài)存儲(chǔ)單元一般格式：指針變量說(shuō)明：在用New過(guò)程給指針變量開辟了一個(gè)它所指向的存儲(chǔ)單元后，要使用此存儲(chǔ)單元的唯一方法是利用該指針。對(duì)動(dòng)態(tài)存儲(chǔ)單元所能進(jìn)行的操作是該類型（指針的基類型）所允許的全部操作。例1設(shè)有下列說(shuō)明:varp:integer;i:integer;畫出執(zhí)行下列操作后的內(nèi)存示意圖：New(

6、p);P:=4;i:=p;解:如下圖所示。(a)編譯時(shí)(b)執(zhí)行New語(yǔ)句(c)執(zhí)行P:=4(d)執(zhí)行i:=P分配存儲(chǔ)單元內(nèi)存單元示意圖（四）對(duì)指針變量的操作前已述及，對(duì)指針?biāo)赶虻淖兞浚ㄈ纾┛梢赃M(jìn)行指針的基類型所允許的全部操作。對(duì)指針變量本身，除可用New、Dispose過(guò)程外，尚允許下列操作：具有同一基類型的指針變量之間相互賦值例2設(shè)有下列說(shuō)明與程序段:varp1,p2,p3:integer;beginNew(P1);New(P2);New(P3);P1:=P2;P2:=P3;end;2、可以給指針變量賦nil值nil是PASCAL的關(guān)鍵字，它表示指針的值為空。例如，執(zhí)行：p1:=ni1后

7、，p1的值是有定義的，但p1不指向任何存儲(chǔ)單元。3、可以對(duì)指針變量進(jìn)行相等或不相等的比較運(yùn)算在實(shí)際應(yīng)用中，通?？梢栽谥羔樧兞恐g，或指針變量與nil之間進(jìn)行相等()或不相等(的比較，比較的結(jié)果為布爾量。4需要注意之處1、P與P的區(qū)別P是指向該動(dòng)態(tài)變量的指針變量名，P則稱為動(dòng)態(tài)變量或標(biāo)志變量。P的值是P的首地址，P的值為與基類型相同的一個(gè)值。2、定義后及時(shí)分配存儲(chǔ)單元定義了一個(gè)指針變量后，并沒有為該指針分配動(dòng)態(tài)存儲(chǔ)單元，此時(shí)的P的值無(wú)定義，調(diào)用P則會(huì)產(chǎn)生運(yùn)行錯(cuò)誤。若想使該指針可用，可以對(duì)指針賦值，也可以通過(guò)NEW（）過(guò)程分配存儲(chǔ)單元。3、使用后及時(shí)收回存儲(chǔ)單元指針使用后，不會(huì)自動(dòng)歸還占用的存儲(chǔ)空

8、間，應(yīng)及時(shí)使用DISPOSE（）過(guò)程來(lái)釋放P所占用的存儲(chǔ)單元，以免浪費(fèi)有限的存儲(chǔ)空間例3輸入兩個(gè)整數(shù)，按從小到大打印出來(lái)。分析：不用指針類型可以很方便地編程，但為了示例指針的用法，我們利用指針類型。定義一個(gè)過(guò)程swap用以交換兩個(gè)指針的值。源程序如下：Typepointer=integer;varp1,p2:pointer;procedureswap(varq1,q2:pointer);varq:pointer;beginq:=q1;q1:=q2;q2:=q;end;beginnew(p1);new(p2);write(Input2data:);readln(pq,p2);ifp1p2then

9、swap(p1,p2);writeln(Output2data:,p1:4,p2:4);end.二、鏈表結(jié)構(gòu)設(shè)有一批整數(shù)(12，56，45，86，77，)，如何存放呢?當(dāng)然我們可以選擇以前學(xué)過(guò)的數(shù)組類型。但是，在使用數(shù)組前必須確定數(shù)組元素的個(gè)數(shù)。如果把數(shù)組定義得大了，就會(huì)有大量空閑存儲(chǔ)單元，定義得小了，又會(huì)在運(yùn)行中發(fā)生下標(biāo)越界的錯(cuò)誤，這是靜態(tài)存儲(chǔ)分配的局限性。利用本章介紹的指針類型可以構(gòu)造一個(gè)簡(jiǎn)單而實(shí)用的動(dòng)態(tài)存儲(chǔ)分配結(jié)構(gòu)鏈表結(jié)構(gòu)。下圖是一個(gè)簡(jiǎn)單鏈表結(jié)構(gòu)示意圖：其中：每個(gè)框表示鏈表的一個(gè)元素，稱為結(jié)點(diǎn)?？虻捻敳勘硎玖嗽摯鎯?chǔ)單元的地址(當(dāng)然，這里的地址是假想的)。每個(gè)結(jié)點(diǎn)包含兩個(gè)域：一個(gè)域存放整數(shù)

10、，稱為數(shù)據(jù)域，另一個(gè)域存放下一個(gè)結(jié)點(diǎn)(稱為該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，相應(yīng)地，該結(jié)點(diǎn)為后繼結(jié)點(diǎn)的前趨結(jié)點(diǎn))的地址。鏈表的第一個(gè)結(jié)點(diǎn)稱為表頭，最后一個(gè)結(jié)點(diǎn)表尾，稱為指針域；指向表頭的指針head稱為頭指針(當(dāng)head為nil時(shí)，稱為空鏈表)，在這個(gè)指針變量中存放了表頭的地址。在表尾結(jié)點(diǎn)中，由指針域不指向任何結(jié)點(diǎn)，一般放入nil。（一）鏈表的基本結(jié)構(gòu)由上圖可以看出：鏈表中的每個(gè)結(jié)點(diǎn)至少應(yīng)該包含兩個(gè)域；一是數(shù)據(jù)域，一是指針域。因此，每個(gè)結(jié)點(diǎn)都是一個(gè)記錄類型，指針的基類型也正是這個(gè)記錄類型。因此，head可以這樣定義：typepointer=rec；rec=recorddata：integer;next:poi

11、nter;end;varhead:pointer;相鄰結(jié)點(diǎn)的地址不一定是連續(xù)的。整個(gè)鏈表是通過(guò)指針來(lái)順序訪問的，一旦失去了一個(gè)指針值，后面的元素將全部丟失。與數(shù)組結(jié)構(gòu)相比，使用鏈表結(jié)構(gòu)時(shí)；可根據(jù)需要采用適當(dāng)?shù)牟僮鞑襟E使鏈表加長(zhǎng)或縮短，而使存儲(chǔ)分配具有一定的靈活性。這是鏈表結(jié)構(gòu)的優(yōu)點(diǎn)。與數(shù)組結(jié)構(gòu)相比，數(shù)組元素的引用比較簡(jiǎn)單，直接用數(shù)組名下標(biāo)即可，因?yàn)閿?shù)組元素占用連續(xù)的存儲(chǔ)單元，而引用鏈表元素的操作卻比較復(fù)雜。（二）單向鏈表的基本操作上圖所示的鏈表稱為單向鏈表。下面我們通過(guò)一些例題來(lái)說(shuō)明對(duì)單向鏈表的基本操作，并假設(shè)類型說(shuō)明如前所述。例6編寫一個(gè)過(guò)程，將讀入的一串整數(shù)存入鏈表，并統(tǒng)計(jì)整數(shù)的個(gè)數(shù)。分析

12、：過(guò)程的輸入為一串整數(shù)，這在執(zhí)行部分用讀語(yǔ)句完成。過(guò)程的輸出有兩個(gè)：一是鏈表的頭指針，一是整數(shù)的個(gè)數(shù)，這兩個(gè)輸出可以用變量形參來(lái)實(shí)現(xiàn)。由于不知道整數(shù)的個(gè)數(shù)，我們用一個(gè)特殊的9999作為結(jié)束標(biāo)記。過(guò)程如下：procedurecreat(varh:pointer;varn:integer);varp,q:pointer;x:integer;beginn:=0;h:=nil;read(x);whilex9999dobeginNew(p);n:=n+1;p.data:=x;ifn=1thenh:=pelseq.next:=p;q:=p;read(x)end;ifhnilthenq.next:=nil;

13、Dispose(p);end;例7編一過(guò)程打印鏈表head中的所有整數(shù),5個(gè)一行。分析：設(shè)置一個(gè)工作指針P,從頭結(jié)點(diǎn)順次移到尾結(jié)點(diǎn)，每移一次打印一個(gè)數(shù)據(jù)。過(guò)程如下：procedureprint(head:pointer);varp:pointer;n:integer;beginn:=0;p:=head;whilepnildobeginwrite(p.data:8);n:=n+1;ifnmod5=0thenwriteln;p:=p.next;end;writeln;end;（三）鏈表結(jié)點(diǎn)的插入與刪除鏈表由于使用指針來(lái)連接，因而提供了更多了靈活性，可以插入刪除任何一個(gè)成分。設(shè)有如下定義：typep

14、ointer=rec;rec=recorddata:integer;next:pointerend;varhead:pointer;結(jié)點(diǎn)的插入如下圖所示,要在P結(jié)點(diǎn)和Q結(jié)點(diǎn)之間插入一個(gè)結(jié)點(diǎn)m,其操作如下:只要作如下操作即可:New(m);read(m.data);m.next:=q;p.next:=m;例8設(shè)鏈表head中的數(shù)據(jù)是按從小到大順序存放的，在鏈表中插入一個(gè)數(shù)，使鏈表仍有序。分析：顯然，應(yīng)分兩步：查找、插入。設(shè)o指向要插入的結(jié)點(diǎn)，若僅知道o應(yīng)插在之前（作為的前趨結(jié)點(diǎn)）是無(wú)法插入的，應(yīng)同時(shí)知道的前趨結(jié)點(diǎn)地址。當(dāng)然，如果插在鏈表原頭結(jié)點(diǎn)這前或原鏈表為空表或插在原尾結(jié)點(diǎn)之后，則插入時(shí)又必須

15、作特殊處理。過(guò)程如下：procedureinserting(varhead:pointer;x:integer);varpo,p,q:pointer;beginnew(po);po.data:=x;p:=head;ifhead=nil原表為空表thenbeginhead:=po;po.next:=nil;endelsebeginwhile(p.datax)and(p.nextnil)dobeginq:=p;p:=p.nextend;ifp.data=x不是插在原尾結(jié)點(diǎn)之后thenbeginifhead=pthenhead:=poelseq.next:=po;po.next:=pendelseb

16、eginpo.next:=po;po.next:=nilend;end;end;結(jié)點(diǎn)的刪除如下圖所示，要在刪除結(jié)點(diǎn)P的操作如下:要?jiǎng)h除結(jié)點(diǎn)P,則只要將其前趨結(jié)點(diǎn)的指針域指向P的后繼結(jié)點(diǎn)即可。q.next:=p.next;dispose(p);例9將鏈表head中值為X的第一個(gè)結(jié)點(diǎn)刪除分析:有三種情況存在:頭結(jié)點(diǎn)的值為X;除頭結(jié)點(diǎn)外的某個(gè)結(jié)點(diǎn)值為X;無(wú)值為X的結(jié)點(diǎn)。為將前兩種情況統(tǒng)一起來(lái)，我們?cè)陬^結(jié)點(diǎn)之前添加一個(gè)值不為的哨兵結(jié)點(diǎn)。算法分兩步：查找、刪除。過(guò)程如下：proceduredeleteing(varhead:pointer;x:integer);varp,q:pointer;beginN

17、ew(p);p.data:=x-1;p.next:=head;head:=p;以上為添加哨兵結(jié)點(diǎn)while(xp.data)and(p.nextnil)dobeginq:=p;p:=p.nextend;ifx=p.data存在值為X的結(jié)點(diǎn)thenq.next:=p.nextelsewriteln(NOtfound!);head:=head.next刪除哨兵end;（四）環(huán)形鏈表結(jié)構(gòu)在單向鏈表中，表尾結(jié)點(diǎn)的指針為空。如果讓表尾結(jié)點(diǎn)的指針域指向表頭結(jié)點(diǎn)，則稱為單向環(huán)形鏈表，簡(jiǎn)稱單鏈環(huán)。如圖所示。單鏈環(huán)示意圖（五）雙向鏈表結(jié)構(gòu)單鏈表中，每個(gè)結(jié)點(diǎn)只有一個(gè)指向其后繼結(jié)點(diǎn)的指針域。如果每個(gè)結(jié)點(diǎn)不僅有一個(gè)指

18、向其后繼結(jié)點(diǎn)的指針域，還有一個(gè)指向其前趨的指針域，則這種鏈表稱為雙向鏈表。如圖所示。雙向鏈表示意圖可用如下定義一個(gè)數(shù)據(jù)域?yàn)檎偷碾p向鏈表:typepointer=node;node=recordprev:pointer;data:integer;next:pointer;end;對(duì)雙向鏈表的插入、刪除特別方便。與單向鏈環(huán)相似，我們還可定義雙向鏈環(huán)。三、綜合例析例10讀入一串以為結(jié)束標(biāo)志的字符，統(tǒng)計(jì)每個(gè)字符出現(xiàn)的次數(shù)。分析：設(shè)置一個(gè)鏈表存放，每讀入一個(gè)字符，就從鏈表的頭結(jié)點(diǎn)向后掃描鏈表，如果在鏈表中此字符已存在，則其頻率加1，否則將該字符的結(jié)點(diǎn)作為鏈表的新頭結(jié)點(diǎn)，相應(yīng)頻率為1。源程序如下：pro

19、gramex11_10;typeref=letters;定義指針ref：含三個(gè)域key,count,nextletters=recordkey:char;count:integer;next:ref;end;vark:char;sentinel,head:ref;proceduresearch(x:char);在鏈表中掃描查找xvarw:ref;beginw:=head;sentinel.key:=x;whilew.keyxdow:=w.next;ifwsentinel若wsentinel，則說(shuō)明x在鏈表中存在個(gè)數(shù)1thenw.count:=w.count+1elsebegin否則，在鏈表中的

20、最后插入一個(gè)結(jié)點(diǎn)，存放該值w:=head;new(head);withheaddobeginkey:=x;count:=1;next:=w;endend;end;ofsearchprocedureprintlist(w:ref);過(guò)程：輸出鏈表beginwhilewsentineldobeginwriteln(w.key:2,w.count:10);w:=w.next;end;end;ofprintlistbeginmainprogramnew(sentine);建立一個(gè)空結(jié)點(diǎn)，這是第一個(gè)鏈表結(jié)點(diǎn)withsentineldobeginkey:=#;count:=0;next:=nil;end;

21、head:=sentinel;將head指向空結(jié)點(diǎn)（第一個(gè)結(jié)點(diǎn)），讀入一個(gè)字符read(k);whilek#dobeginsearch(k);read(k);end;printlist(head);end.例11用鏈表重寫篩法求2100之間所有素?cái)?shù)程序。源程序如下：programex11_12;usescrt;typelink=code;code=recordkey:integer;next:link;end;varhead:link;procedureprintlist(h:link);打印鏈表hvarp:link;beginp:=h;whilepnildobeginwrite(p.key,

22、-);p:=p.next;end;end;procedurebuildlink;建立鏈表varp,q:link;i:integer;beginnew(head);head.key:=2;p:=head;fori:=3to100dobeginnew(q);q.key:=i;q.next:=nil;p.next:=q;p:=q;end;end;procedureprime;篩法將找到的素?cái)?shù)的倍數(shù)從鏈表中刪除varh,p,q:link;beginh:=head;whilehnildobeginp:=h;q:=p.next;whileqnildoif(q.keymodh.key=0)thenbegin

23、p.next:=q.next;dispose(q);q:=p.next;endelsebeginp:=q;q:=q.next;end;h:=h.next;end;end;beginmainprogramclrscr;buildlink;printlist(head);writeln;prime;printlist(head);end.多項(xiàng)式(Polynomial)n階多項(xiàng)式Pn(x)有n+1項(xiàng)系數(shù)a0,a1,a2,an指數(shù)0,1,2,n。按升冪排列多項(xiàng)式的鏈接表示在多項(xiàng)式的鏈表表示中每個(gè)結(jié)點(diǎn)增加了一個(gè)數(shù)據(jù)成員link，作為鏈接指針。優(yōu)點(diǎn)是：多項(xiàng)式的項(xiàng)數(shù)可以動(dòng)態(tài)地增長(zhǎng)。插入、刪除方便，不移動(dòng)元素

24、。多項(xiàng)式鏈表的相加AH=1-10 x6+2x8+7x14BH=-x4+10 x6-3x10+8x14+4x18多項(xiàng)式的相加的算法設(shè)立表頭Aiter,Biter，檢測(cè)指針pa,pb利用pa,pb掃描兩個(gè)相加多項(xiàng)式，直到其中一個(gè)檢測(cè)完畢：若當(dāng)前被檢測(cè)項(xiàng)指數(shù)相等，系數(shù)相加。若不為0，則加入結(jié)果鏈表。若當(dāng)前被檢測(cè)項(xiàng)指數(shù)不等，將指數(shù)小者加入結(jié)果鏈表。若有一個(gè)多項(xiàng)式已檢測(cè)完，將另一個(gè)多項(xiàng)式剩余部分加入結(jié)果鏈表。程序：Polynomial.pasprogrampolynomial;typedata=term;term=recordcoef:integer;exp:integer;link:data;end;

25、varfirst,pa,pb,ch1,ch2:data;x,y:integer;procedureplink(head:data);建立多項(xiàng)式鏈表varp,h:data;x,y:integer;beginp:=head;read(x,y);whiley-1dobeginnew(h);h.coef:=x;h.exp:=y;p.link:=h;p:=h;read(x,y);end;new(h);h:=nil;p.link:=h;p.link:=nil;end;procedureins(x,y:integer;ch2:data);過(guò)程：插入一個(gè)結(jié)點(diǎn)varch:data;beginnew(ch);ch1.link:=ch;ch.coef:=x;ch.exp:=y;ch1:=ch;end;beginnew(pa);pa:=nil;first:=pa;plink(pa);pa:=first.link;建立第一個(gè)多項(xiàng)式PAnew(pb);pb:=nil;first:=pb;plink(pb)