第十三章動態(tài)數(shù)據(jù)類型前面介紹的各種簡單類型的數(shù)據(jù)和構(gòu)造類型的數(shù)據(jù)屬于靜態(tài)數(shù)據(jù)。在程序中，這些類型的變量一經(jīng)說明，就在內(nèi)存中占有固定的存儲單元，直到該程序結(jié)束。程序設(shè)計中，使用靜態(tài)數(shù)據(jù)結(jié)構(gòu)可以解決不少實(shí)際問題，但也有不便之處。如建立一個大小未定的姓名表，隨時要在姓名表中插入或刪除一個或幾個數(shù)據(jù)。而用新的數(shù)據(jù)類型——指針類型。通過指針變量，可以在程序的執(zhí)行過程中動態(tài)地建立變量，它的個數(shù)不再受限制，可方便地高效地增加或刪除若干數(shù)據(jù)。一、指針的定義及操作（一） 指針類型和指針變量在pascal中，指針變量（也稱動態(tài)變量）存放某個存儲單元的地址；也就是說，指針變量指示某個存儲單元。指針類型的格式為：八基類型說明：①一個指針只能指示某一種類型數(shù)據(jù)的存儲單元，這種數(shù)據(jù)類型就是指針的基類型。基類型可以是除指針、文件外的所有類型。例如，下列說明：typepointer="lnteger;varp1,p2:pointer;定義了兩個指針變量P1和p2,這兩個指針可以指示一個整型存儲單元（即pl、p2中存放的是某存儲單元的地址，而該存儲單元恰好能存放一個整型數(shù)據(jù)）。和其它類型變量一樣，也可以在var區(qū)直接定義指針型變量。例如：vara:"real;b:"boolean;又如：typeperson=recordname:string[20];sex:（male,female）;age:1..100end;varpts:"person;pascal規(guī)定所有類型都必須先定義后使用，但只有在定義指針類型時可以例外，如下列定義是合法的：typepointer="rec;rec=recorda:integer;b:charend;（二） 開辟和釋放動態(tài)存儲單元1、開辟動態(tài)存儲單元在pascal中，指針變量的值一般是通過系統(tǒng)分配的，開辟一個動態(tài)存儲單元必須調(diào)用標(biāo)準(zhǔn)過程new。new過程的調(diào)用的一般格式：New(指針變量)功能：開辟一個存儲單元，此單元能存放的數(shù)據(jù)的類型正好是指針的基類型，并把此存儲單元的地址賦給指針變量。說明：①這實(shí)際上是給指針變量賦初值的基本方法。例如，設(shè)有說明：varp:”Integer;這只定義了P是一個指示整型存儲單元的指針變量，但這個單元尚未開辟，或者說P中尚未有值(某存儲單元的首地址)。當(dāng)程序中執(zhí)行了語句new(p)才給P賦值，即在內(nèi)存中開辟(分配)一個整型變量存儲單元，并把此單元的地址放在變量P中。示意如下圖：(a)編譯時給 (b)執(zhí)行New(p)后(c)(b)的簡略表示p分配空間 生成新單元?表示值不定新單元的地址為XXXX內(nèi)存單元示意圖一個指針變量只能存放一個地址。如再一次執(zhí)行New(p)語句，將在內(nèi)存中開辟另外一個新的整型變量存儲單元，并把此新單元的地址放在P中，從而丟失了原存儲單元的地址。當(dāng)不再使用P當(dāng)前所指的存儲單元時，可以通過標(biāo)準(zhǔn)過程Dispose釋放該存儲單元。釋放動態(tài)存儲單元dispose語句的一般格式：dispose(指針變量)功能：釋放指針?biāo)赶虻拇鎯卧怪羔樧兞康闹禑o定義。動態(tài)存儲單元的引用在給一個指針變量賦以某存儲單元的地址后，就可以使用這個存儲單元。引用動態(tài)存儲單元一般格式：〈指針變量〉八說明：①在用New過程給指針變量開辟了一個它所指向的存儲單元后，要使用此存儲單元的唯一方法是利用該指針。②對動態(tài)存儲單元所能進(jìn)行的操作是該類型(指針的基類型)所允許的全部操作。例1設(shè)有下列說明：varp:"integer;i:integer;畫出執(zhí)行下列操作后的內(nèi)存示意圖：New(p);p.：=4;i:=p";解：如下圖所示。P ?p| |、 4 礦■F| |、 4(a)編譯時(b)執(zhí)行New語句 (c)執(zhí)行P”：=4 (d)執(zhí)行i:=P分配存儲單元內(nèi)存單元示意圖對指針變量的操作前已述及，對指針?biāo)赶虻淖兞?如P")可以進(jìn)行指針的基類型所允許的全部操作。對指針變量本身，除可用New、Dispose過程外，尚允許下列操作：1、 具有同一基類型的指針變量之間相互賦值例2設(shè)有下列說明與程序段：varp1,p2,p3:"integer;beginNew(P1);New(P2);New(P3);P1:=P2;P2:=P3;end;2、 可以給指針變量賦nil值nil是PASCAL的關(guān)鍵字，它表示指針的值為"空"。例如，執(zhí)行：P1:=ni1后，p1的值是有定義的，但p1不指向任何存儲單元。3、 可以對指針變量進(jìn)行相等或不相等的比較運(yùn)算在實(shí)際應(yīng)用中，通常可以在指針變量之間，或指針變量與nil之間進(jìn)行相等(=)或不相等(<>=的比較，比較的結(jié)果為布爾量。例3輸入兩個整數(shù)，按從小到大打印出來。分析：不用指針類型可以很方便地編程，但為了示例指針的用法，我們利用指針類型。定義一個過程swap用以交換兩個指針的值。源程序如下：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”);ifp1">p2"thenswap(p1,p2);writeln('Output2data:',p1”:4,p2":4);end.二、鏈表結(jié)構(gòu)設(shè)有一批整數(shù)(12,56,45,86,77,……，)，如何存放呢？當(dāng)然我們可以選擇以前學(xué)過的數(shù)組類型。但是，在使用數(shù)組前必須確定數(shù)組元素的個數(shù)。如果把數(shù)組定義得大了，就會有大量空閑存儲單元，定義得小了，又會在運(yùn)行中發(fā)生下標(biāo)越界的錯誤，這是靜態(tài)存儲分配的局限性。利用本章介紹的指針類型可以構(gòu)造一個簡單而實(shí)用的動態(tài)存儲分配結(jié)構(gòu)一一鏈表結(jié)構(gòu)。下圖是一個簡單鏈表結(jié)構(gòu)示意圖：其中：①每個框表示鏈表的一個元素，稱為結(jié)點(diǎn)。框的頂部表示了該存儲單元的地址(當(dāng)然，這里的地址是假想的)。每個結(jié)點(diǎn)包含兩個域：一個域存放整數(shù)，稱為數(shù)據(jù)域，另一個域存放下一個結(jié)點(diǎn)(稱為該結(jié)點(diǎn)的后繼結(jié)點(diǎn)，相應(yīng)地，該結(jié)點(diǎn)為后繼結(jié)點(diǎn)的前趨結(jié)點(diǎn))的地址。鏈表的第一個結(jié)點(diǎn)稱為表頭，最后一個結(jié)點(diǎn)表尾，稱為指針域；指向表頭的指針head稱為頭指針(當(dāng)head為nil時，稱為空鏈表)，在這個指針變量中存放了表頭的地址。在表尾結(jié)點(diǎn)中，由指針域不指向任何結(jié)點(diǎn)，一般放入nil。鏈表的基本結(jié)構(gòu)由上圖可以看出：鏈表中的每個結(jié)點(diǎn)至少應(yīng)該包含兩個域；一是數(shù)據(jù)域，一是指針域。因此，每個結(jié)點(diǎn)都是一個記錄類型，指針的基類型也正是這個記錄類型。因此，head可以這樣定義：typepointer="rec；rec=recorddata：integer;next:pointer;end;varhead:pointer;相鄰結(jié)點(diǎn)的地址不一定是連續(xù)的。整個鏈表是通過指針來順序訪問的，一旦失去了一個指針值，后面的元素將全部丟失。與數(shù)組結(jié)構(gòu)相比，使用鏈表結(jié)構(gòu)時；可根據(jù)需要采用適當(dāng)?shù)牟僮鞑襟E使鏈表加長或縮短，而使存儲分配具有一定的靈活性。這是鏈表結(jié)構(gòu)的優(yōu)點(diǎn)。與數(shù)組結(jié)構(gòu)相比，數(shù)組元素的引用比較簡單，直接用"數(shù)組名［下標(biāo)］"即可，因?yàn)閿?shù)組元素占用連續(xù)的存儲單元，而引用鏈表元素的操作卻比較復(fù)雜。單向鏈表的基本操作上圖所示的鏈表稱為單向鏈表。下面我們通過一些例題來說明對單向鏈表的基本操作，并假設(shè)類型說明如前所述。例6編寫一個過程，將讀入的一串整數(shù)存入鏈表，并統(tǒng)計整數(shù)的個數(shù)。分析：過程的輸入為一串整數(shù)，這在執(zhí)行部分用讀語句完成。過程的輸出有兩個：一是鏈表的頭指針，一是整數(shù)的個數(shù)，這兩個輸出可以用變量形參來實(shí)現(xiàn)。由于不知道整數(shù)的個數(shù)，我們用一個特殊的9999作為結(jié)束標(biāo)記。過程如下：procedurecreat(varh:pointer;varn:integer);varp,q:pointer;x:integer;beginn:=0;h:=nil;read(x);whilex<>9999dobeginNew(p);n:=n+1;p”.data:=x;ifn=1thenh:=pelseq”.next:=p;q:=p;read(x)end;ifh<>nilthenq”.next:=nil;Dispose(p);end;例7編一過程打印鏈表head中的所有整數(shù),5個一行。分析：設(shè)置一個工作指針P,從頭結(jié)點(diǎn)順次移到尾結(jié)點(diǎn)，每移一次打印一個數(shù)據(jù)。過程如下：procedureprint(head:pointer);varp:pointer;n:integer;beginn:=0;p:=head;whilep<>nildobeginwrite(p”.data:8);n:=n+1;ifnmod5=0thenwriteln;p:=p".next;end;writeln;end;鏈表結(jié)點(diǎn)的插入與刪除鏈表由于使用指針來連接，因而提供了更多了靈活性，可以插入刪除任何一個成分。設(shè)有如下定義：typepointer="rec;rec=recorddata:integer;next:pointerend;varhead:pointer;1.結(jié)點(diǎn)的插入只要作如下操作即可：New(m);read(m”.data);m”.next:=q;p”.next:=m;例8設(shè)鏈表head中的數(shù)據(jù)是按從小到大順序存放的，在鏈表中插入一個數(shù)，使鏈表仍有序。分析：顯然，應(yīng)分兩步：查找、插入。設(shè)P。指向要插入的結(jié)點(diǎn)，若僅知道P。應(yīng)插在P之前(作為P的前趨結(jié)點(diǎn))是無法插入的，應(yīng)同時知道P的前趨結(jié)點(diǎn)地址q。當(dāng)然，如果插在鏈表原頭結(jié)點(diǎn)這前或原鏈表為空表或插在原尾結(jié)點(diǎn)之后，則插入時又必須作特殊處理。過程如下：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”.data<x)and(p”.next<>nil)dobeginq:=p;p:=p.nextend;ifp".data〉=x｛不是插在原尾結(jié)點(diǎn)之后｝thenbeginifhead=pthenhead:=poelseq”.next:=po;po”.next:=pendelsebeginpo”.next:=po;po”.next:=nilend;end;end;2.結(jié)點(diǎn)的刪除如下圖所示，要在刪除結(jié)點(diǎn)P的操作如下：，田一413—□ 4D3]□rDpP要刪除結(jié)點(diǎn)p,則只要將其前趨結(jié)點(diǎn)的指針域指向p的后繼結(jié)點(diǎn)即可。q”.next:=p".next;dispose(p);例9將鏈表head中值為X的第一個結(jié)點(diǎn)刪除分析：有三種情況存在:頭結(jié)點(diǎn)的值為X;除頭結(jié)點(diǎn)外的某個結(jié)點(diǎn)值為X;無值為X的結(jié)點(diǎn)。為將前兩種情況統(tǒng)一起來，我們在頭結(jié)點(diǎn)之前添加一個值不為X的哨兵結(jié)點(diǎn)。算法分兩步：查找、刪除。過程如下：proceduredeleteing(varhead:pointer;x:integer);varp,q:pointer;beginNew(p);p".data:=xT;p".next:=head;head:=p;｛以上為添加哨兵結(jié)點(diǎn)｝while(x＜〉p".data)and(p”.next＜〉nil)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)形鏈表，簡稱單鏈環(huán)。如圖所示。hudr-,jj—In—r~n—EZG-*—-tjEdn單鏈環(huán)示意圖（五）雙向鏈表結(jié)構(gòu)單鏈表中，每個結(jié)點(diǎn)只有一個指向其后繼結(jié)點(diǎn)的指針域。如果每個結(jié)點(diǎn)不僅有一個指向其后繼結(jié)點(diǎn)的指針域，還有一個指向其前趨的指針域，則這種鏈表稱為雙向鏈表。如圖所示。雙向鏈表示意圖可用如下定義一個數(shù)據(jù)域?yàn)檎偷碾p向鏈表：typepointer="node;node=recordprev:pointer;data:integer;next:pointer;end;對雙向鏈表的插入、刪除特別方便。與單向鏈環(huán)相似，我們還可定義雙向鏈環(huán)。三、綜合例析例10讀入一串以"#"為結(jié)束標(biāo)志的字符，統(tǒng)計每個字符出現(xiàn)的次數(shù)。分析：設(shè)置一個鏈表存放，每讀入一個字符，就從鏈表的頭結(jié)點(diǎn)向后掃描鏈表，如果在鏈表中此字符已存在，則其頻率加1，否則將該字符的結(jié)點(diǎn)作為鏈表的新頭結(jié)點(diǎn)，相應(yīng)頻率為1。源程序如下：programex11_10;typeref="letters;letters=recordkey:char;count:integer;next:ref;end;vark:char;sentinel,head:ref;proceduresearch(x:char);varw:ref;beginw:=head;sentinel”.key:=x;whilew”.key<〉xdow:=w".next;ifw<>sentinelthenw”.count:=w".count+1elsebeginw:=head;new(head);withhead"dobeginkey:=x;count:=1;next:=w;endend;end;{ofsearch}procedureprintlist(w:ref);beginwhilew<>sentineldobeginwriteln(w”.key:2,w”.count:10);w:=w".next;end;end;{ofprintlist}begin{mainprogram}new(sentine);withsentinel"dobeginkey:='#';count:=0;next:=nil;end;head:=sentinel;read(k);whilek<〉'#'dobeginsearch(k);read(k);end;printlist(head);end.例11用鏈表重寫篩法求2?100之間所有素數(shù)程序。源程序如下：programex11_12;usescrt;typelink="code;code=recordkey:integer;next:link;end;varhead:link;procedureprintlist(h:link);｛打印鏈表h｝varp:link;beginp:=h;whilep<>nildobeginwrite(pLkey,'—>');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;procedureprim