動態(tài)數(shù)據(jù)類型

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

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

3、maIe);age:1.100end;var ptsbpers on; pascal規(guī)定所有類型都必須先定義后使用，但只有在定義指針類型時可以例外，如下 列定義是合法的：type poin ter=Arec;rec=recorda:integer;b:charend;（二）開辟和釋放動態(tài)存儲單元1、開辟動態(tài)存儲單元在 pascal 中，指針變量的值一般是通過系統(tǒng)分配的， 開辟一個動態(tài)存儲單元必須調用標 準過程 new。new 過程的調用的一般格式 :New（ 指針變量 ）功能： 開辟一個存儲單元， 此單元能存放的數(shù)據(jù)的類型正好是指針的基類型， 并把此存 儲單元的地址賦給指針變量。說明：這實際上

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

5、了原存儲單元的地址。 當不再使用P當前所指的存儲單元時，可以通過標準過程Dispose釋放該存儲單元。2. 釋放動態(tài)存儲單元dispose語句的一般格式:dispose(指針變量)功能：釋放指針所指向的存儲單元，使指針變量的值無定義。(三) 動態(tài)存儲單元的引用在給一個指針變量賦以某存儲單元的地址后，就可以使用這個存儲單元。引用動態(tài)存儲單元一般格式：v指針變量人說明：在用 New過程給指針變量開辟了一個它所指向的存儲單元后，要使用此存儲 單元的唯一方法是利用該指針。對動態(tài)存儲單元所能進行的操作是該類型(指針的基類型)所允許的全部操作。例1 設有下列說明 :var p:A in teger; i:

6、i nteger;畫出執(zhí)行下列操作后的內(nèi)存示意圖：New(p); PA:=4;i:=pA;解 : 如下圖所示。(a)編譯時(b)執(zhí)行New語句(c)執(zhí)行卩人：=4(d)執(zhí)行i:=PA分配存儲單元內(nèi)存單元示意圖（四）對指針變量的操作前已述及，對指針所指向的變量（如PA）可以進行指針的基類型所允許的全部操作。對指針變量本身，除可用 New 、Dispose 過程外，尚允許下列操作：1、具有同一基類型的指針變量之間相互賦值例2 設有下列說明與程序段 :var p1,p2,p3? in teger;beginNew（P1） ; New（P2）; New（P3）;P1:=P2; P2:=P3;end;2

7、、可以給指針變量賦 nil 值nil 是 PASCAL 的關鍵字，它表示指針的值為 "空"。例如，執(zhí)行：p1:=ni1 后， p1 的值是有定義的，但 p1 不指向任何存儲單元。3、可以對指針變量進行相等或不相等的比較運算在實際應用中，通?？梢栽谥羔樧兞恐g，或指針變量與nil之間進行相等（=）或不相等（v> =的比較，比較的結果為布爾量。例 3 輸入兩個整數(shù)，按從小到大打印出來。分析：不用指針類型可以很方便地編程，但為了示例指針的用法，我們利用指針類型。 定義一個過程 swap 用以交換兩個指針的值。源程序如下：Type poin ter=A in teger;va

8、r p1,p2:pointer;procedure swap(var q1,q2:pointer);var q:pointer;beginq:=q1;q1:=q2;q2:=q;end;beginnew(p1);new(p2);write('Input 2 data:');readln(pqA,p2A);if p1A>p2A then swap(p1,p2);writeln('Output 2 data:',p1A:4,p2A:4);end.二、鏈表結構設有一批整數(shù)(12, 56, 45, 86, 77,)，如何存放呢？當然我們可以選擇以前學 過的數(shù)組類型。

9、 但是，在使用數(shù)組前必須確定數(shù)組元素的個數(shù)。如果把數(shù)組定義得大了，就 會有大量空閑存儲單元, 定義得小了, 又會在運行中發(fā)生下標越界的錯誤, 這是靜態(tài)存儲分 配的局限性。利用本章介紹的指針類型可以構造一個簡單而實用的動態(tài)存儲分配結構鏈表結構。圖是一個簡單鏈表結構示意圖：其中：每個框表示鏈表的一個元素，稱為結點。 框的頂部表示了該存儲單元的地址 （當然，這里的地址是假想的 ）。 每個結點包含兩個域：一個域存放整數(shù)，稱為數(shù)據(jù)域，另一個域存放下一個結點（稱為該結點的后繼結點，相應地，該結點為后繼結點的前趨結點）的地址。 鏈表的第一個結點稱為表頭，最后一個結點表尾，稱為指針域; 指向表頭的指針 hea

10、d 稱為頭指針 （當 head 為 nil 時，稱為空鏈表 ），在這個指針變量中 存放了表頭的地址。 在表尾結點中，由指針域不指向任何結點，一般放入nil。（一）鏈表的基本結構由上圖可以看出：是指針域。 因此， 每個結點head 可以這樣定義：鏈表中的每個結點至少應該包含兩個域；一是數(shù)據(jù)域，都是一個記錄類型，指針的基類型也正是這個記錄類型。因此，type pointer=A rec ；rec=recorddata： integer;next:pointer;end;var head:pointer; 相鄰結點的地址不一定是連續(xù)的。整個鏈表是通過指針來順序訪問的， 一旦失去了一個指針值，后面的元

11、素將全部丟失。 與數(shù)組結構相比，使用鏈表結構時； 可根據(jù)需要采用適當?shù)牟僮鞑襟E使鏈表加長或縮短，而使存儲分配具有一定的靈活性。這是鏈表結構的優(yōu)點。 與數(shù)組結構相比，數(shù)組元素的引用比較簡單，直接用"數(shù)組名下標"即可，因為數(shù)組元素占用連續(xù)的存儲單元，而引用鏈表元素的操作卻比較復雜。（二）單向鏈表的基本操作圖所示的鏈表稱為單向鏈表。下面我們通過一些例題來說明對單向鏈表的基本操作， 并假設類型說明如前所述。例6 編寫一個過程，將讀入的一串整數(shù)存入鏈表， 并統(tǒng)計整數(shù)的個數(shù)。分析： 過程的輸入為一串整數(shù)， 這在執(zhí)行部分用讀語句完成。 過程的輸出有兩個： 鏈表的頭指針，一是整數(shù)的個數(shù)，這

12、兩個輸出可以用變量形參來實現(xiàn)。由于不知道整數(shù)的個數(shù)，我們用一個特殊的 9999 作為結束標記。過程如下：procedure creat(var h:pointer;var n:integer);var p,q:pointer;x:integer;beginn:=0;h:=nil; read(x);while x<>9999 do beginNew(p);n:=n +1;pdata:=x;if n=1 then h:=pelse qn ext:=p;q:=p;read(x)end;if h<>nil the n q» next:=n il; Dispose(p)

13、;end;例7編一過程打印鏈表 head中的所有整數(shù),5個一行。分析：設置一個工作指針P從頭結點順次移到尾結點，每移一次打印一個數(shù)據(jù)。過程如下：procedure print(head:pointer);var p:pointer; n:integer;beginn:=0;p:=head;while p<>nil dobeginwrite(pdata:8); n:=n+1;if n mod 5=0 then writeln;p:=pA. next;end;writeln;end;(三) 鏈表結點的插入與刪除鏈表由于使用指針來連接，因而提供了更多了靈活性，可以插入刪除任何一個成分。

14、設有如下定義：type pointer=Arec;rec=recorddata:integer;next:pointerend;var head:pointer;1結點的插入如下圖所示，要在P結點和Q結點之間插入一個結點m,其操作如下：只要作如下操作即可 :New(m);read(midata);mn ext:=q;p» next:=m;例8設鏈表head中的數(shù)據(jù)是按從小到大順序存放的，在鏈表中插入一個數(shù)，使鏈表仍 有序。分析：顯然，應分兩步：查找、插入。設po指向要插入的結點，若僅知道po應插在P之前(作為P的前趨結點)是無法插入的，應同時知道P的前趨結點地址q。當然， 如果插在鏈

15、表原頭結點這前或原鏈表為空表或插在原尾結點之后，則插入時又必須作特殊處理。過程如下：procedure inserting(var head:pointer;x:integer);var po,p,q:pointer;beginn ew(po);poA.data:=x;p:=head;if head=nil 原表為空表 then beginhead:=po;poA.next:=nil;endelse beginwhile (pdata<x)a nd(p» next< >n il)do beginq:=p;p:=pA .n extend;if pA.data>=

16、x不是插在原尾結點之后 then beginif head=p then head:=poelse qA.next:=po;poA.next:=pendelse beginpoA.next:=po;poA.next:=nilend;end;end;2結點的刪除如下圖所示，要在刪除結點 P 的操作如下 :要刪除結點P則只要將其前趨結點的指針域指向P的后繼結點即可。qA. next:=pA .n ext;dispose(p);例9將鏈表head中值為X的第一個結點刪除分析：有三種情況存在：頭結點的值為X;除頭結點外的某個結點值為X;無值為X的結點。為將前兩種情況統(tǒng)一起來，我們在頭結點之前添加一個值

17、不為X的哨兵結點。算法分兩步：查找、刪除。過程如下：procedure deleteing(var head:pointer;x:integer);var p,q:pointer;beginNew(p);pA.data:=x-1;pA.next:=head;head:=p; 以上為添加哨兵結點 while(x<>pA.data)and(pA.next<>nil)dobeginq:=p;p:=pA.nextend;if x=pA.data 存在值為 X 的結點 then qA.next:=pA.nextelse writeln('NOt found!');

18、head:=headA.next 刪除哨兵 end;（四）環(huán)形鏈表結構在單向鏈表中， 表尾結點的指針為空。 如果讓表尾結點的指針域指向表頭結點， 則稱為 單向環(huán)形鏈表，簡稱單鏈環(huán)。如圖所示。單鏈環(huán)示意圖（五）雙向鏈表結構單鏈表中， 每個結點只有一個指向其后繼結點的指針域。 如果每個結點不僅有一個指向 其后繼結點的指針域， 還有一個指向其前趨的指針域， 則這種鏈表稱為雙向鏈表。 如圖所示。雙向鏈表示意圖可用如下定義一個數(shù)據(jù)域為整型的雙向鏈表 :type poin ter=A no de;node=recordprev:pointer;data:integer;next:pointer;end;對

19、雙向鏈表的插入、刪除特別方便。與單向鏈環(huán)相似，我們還可定義雙向鏈環(huán)。三、綜合例析例 10 讀入一串以 " " 為結束標志的字符，統(tǒng)計每個字符出現(xiàn)的次數(shù)。分析： 設置一個鏈表存放， 每讀入一個字符， 就從鏈表的頭結點向后掃描鏈表，如果在 鏈表中此字符已存在，則其頻率加1， 否則將該字符的結點作為鏈表的新頭結點，相應頻率為 1。源程序如下：program ex11_10;type ref=qetters;letters=recordkey:char;count:integer;next:ref;end;var k:char;sentinel,head:ref;procedure

20、 search(x:char);var w:ref;beginw:=head;sen ti nelkey:=x;while wA.key<>x do w:=wA .n ext;if w<>sentinelthen wA.count:=wA.count+1else beginw:=head;new(head);with headA dokey:=x;count:=1;next:=w;beginendend;end;of searchprocedure printlist(w:ref);beginwhile w<>sentinel dobeginwritein

21、(wA.key:2,wcou nt:10);w:=wA. next;end;end;of printiistbeginmain programnew(sentine);with sentineiA dobeginkey:='#'count:=0;next:=nii;end;head:=sentinei;read(k);whiie k<>'#' dosearch(k);read(k);beginend;printlist(head);end.例11用鏈表重寫篩法求 2100之間所有素數(shù)程序。源程序如下：program ex11_12;uses crt;

22、type lin k=Acode;code=recordkey:integer;next:link;end;var head:link;procedure printlist(h:link); 打印鏈表 hvar p:link;beginp:=h;while p<>nil dobeginwrite(pA.key,'->');p:=pA.next;end;end;procedure buildlink; 建立鏈表 var p,q:link;i:integer;beginnew(head);headkey:=2;p:=head;for i:=3 to 100 dobeginnew(q);qA.key:=i;qA. next:=n il;pA.next:=q;p:=q;end;end;procedure pr