指針與動態(tài)變量

1、指針與動態(tài)變量引言n以前所講的簡單類型的數(shù)據(jù)或構(gòu)造類型的數(shù)據(jù)都是靜態(tài)數(shù)據(jù)，這些類型的變量一經(jīng)定義，就在內(nèi)存中占有固定的存儲單元，直至程序結(jié)束。n指針類型的變量屬于動態(tài)數(shù)據(jù)。是在程序執(zhí)行時，根據(jù)程序的數(shù)據(jù)存儲需要而擴(kuò)充或縮減。n在PASCAL中，指針變量存放某個存儲單元的地址，即指針變量指向某個存儲單元。指針類型說明的一般形式nType 指針類型標(biāo)識符=類型標(biāo)識符；n說明1：指針類型標(biāo)識符由用戶定義，必須符合標(biāo)識符命名規(guī)則；n說明2：類型標(biāo)識符：是除文件以外的任何數(shù)據(jù)類型。n例1：type point1=integer;point2=real;n解釋：上例定義了兩個指針類型，point1是整型指

2、針類型，point2是實(shí)型指針類型。指針類型變量的定義n說明了指針類型，就可以定義該類型的指針變量。n例var p1:point1;p2:point2;n類型說明可以與變量定義合并在一起。n例：var p1:integer;p2:real;n注意點(diǎn)：指針類型說明時，可以不遵循注意點(diǎn)：指針類型說明時，可以不遵循“先說明先說明”后后“使用使用”的原則。的原則。n例：point=node; node=record num:integer; name:string; end; var stu:point; 動態(tài)變量n靜態(tài)變量中存放的是相應(yīng)類型的數(shù)據(jù)，而指針變量中存放的是相應(yīng)類型數(shù)據(jù)所在的存儲單元的地址

3、。要訪問指針變量所指向的數(shù)據(jù)，必須使用動態(tài)變量。n動態(tài)變量不在變量說明中定義，在程序執(zhí)行過程中建立。它沒有標(biāo)識符，而是用指針變量后跟符號表示。如p:=245;n指針變量本身是簡單類型（靜態(tài)數(shù)據(jù)），它所指向的數(shù)據(jù)可以構(gòu)成動態(tài)數(shù)據(jù)整型變量P某個數(shù)據(jù)指針變量P動態(tài)變量p某個存儲單元的地址某個數(shù)據(jù)動態(tài)變量的建立n指針變量的值一般是通過系統(tǒng)分配的，建立一個動態(tài)變量（動態(tài)存儲單元）必須調(diào)用標(biāo)準(zhǔn)過程N(yùn)EW。nNew過程調(diào)用的格式：new(指針變量);nNew過程的作用:建立動態(tài)變量；為動態(tài)變量分配一定的存儲空間，用以存放動態(tài)變量；并將動態(tài)變量的存儲空間的首地址存入指針變量中。n例：var p:integer

4、;此時P的值為nil執(zhí)行語句：new(p); 此時P的值為一存儲單元地址p:=245;一個指針變量只一個指針變量只能存放一個地址能存放一個地址動態(tài)變量的撤消n釋放動態(tài)變量使用標(biāo)準(zhǔn)過程dispose。nDispose過程調(diào)用的格式：dispose(指針變量)nDispose過程的作用：釋放指針?biāo)赶虻拇鎯卧?，使指針變量的值為nil，不指向任何存儲單元。n例：dispose(p);動態(tài)變量的操作n動態(tài)變量的引用：指針變量n例：p:=4; i:=p;n對動態(tài)變量所能進(jìn)行的操作是該類型(指針的基類型)所允許的全部操作。n例：var p:integer; i:integer;New(p);i:=4:p

5、:=4;指針變量的操作n可調(diào)用new、dispose過程。如new(p); dispose(p);n具有同一基類型的指針變量之間相互賦值。n例：var p1,p2,p3:integer;New(p1);new(p2);new(p3);P1:=5;p2:=P1;p3:=p1+P2;n可以給指針變量賦nil值。Nil是pascal的關(guān)鍵字，它表示指針的值為“空”。n例：P1:=nil;n可以對指針變量進(jìn)行比較運(yùn)算。n例1：new(P1); write(p1=nil); 結(jié)果將輸出FALSEn例2：new(p1); new(p2); write(p1=p2); false指針的應(yīng)用一指針的應(yīng)用一 鏈

6、鏈 表表 結(jié)結(jié) 構(gòu)構(gòu)簡單鏈表結(jié)構(gòu)示意圖n每個框表示鏈表的一個元素，稱為結(jié)點(diǎn)n框的頂部表示了該存儲單元的地址(當(dāng)然，這里的地址是假想的)n每個結(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))的地址，稱為指針域n鏈表的第一個結(jié)點(diǎn)稱為表頭，最后一個結(jié)點(diǎn)稱為表尾n指向表頭的指針head稱為頭指針(當(dāng)head為nil時，稱為空鏈表)，在這個指針變量中存放了表頭的地址n在表尾結(jié)點(diǎn)中，指針域不指向任何結(jié)點(diǎn)，一般放入nil。 鏈表的基本結(jié)構(gòu)n鏈表中的每個結(jié)點(diǎn)至少應(yīng)該包含兩個域：一是數(shù)據(jù)域，一是指針域，因此，每個結(jié)點(diǎn)都是一個記錄類型。

7、指針的基類型也正是這個記錄類型。因此，head可以這樣定義： type pointer= rec； rec=record data：integer; next:pointer; end; var head:pointer; n相鄰結(jié)點(diǎn)的地址不一定是連續(xù)的。整個鏈表是通過指針來順序訪問的，一旦失去了一個指針值，后面的元素將全部丟失n與數(shù)組結(jié)構(gòu)相比，使用鏈表結(jié)構(gòu)時可根據(jù)需要采用適當(dāng)?shù)牟僮鞑襟E使鏈表加長或縮短，而使存儲分配具有一定的靈活性，這是鏈表結(jié)構(gòu)的優(yōu)點(diǎn)n與數(shù)組結(jié)構(gòu)相比，數(shù)組元素的引用比較簡單，直接用“數(shù)組名下標(biāo)”即可，因?yàn)閿?shù)組元素占用連續(xù)的存儲單元，而引用鏈表元素的操作卻比較復(fù)雜。 線性鏈表n

8、鏈表中的每個結(jié)點(diǎn)只包含一個指針域，故稱為線性鏈表或單鏈表。n線性鏈表的存取必須從頭指針開始進(jìn)行，頭指針指示鏈表中第一個結(jié)點(diǎn)（表頭）的存儲位置。同時，由于最后一個結(jié)點(diǎn)（表尾）沒有后繼，故線性鏈表中最后一個結(jié)點(diǎn)的指針域的值為空，即為nil。線性鏈表的主要操作線性鏈表的主要操作1、線性鏈表的建立、線性鏈表的建立n例：編寫一個程序，將讀入的一串正整數(shù)存入鏈表，遇負(fù)數(shù)結(jié)束并統(tǒng)計(jì)鏈表的長度。n分析：每讀入一個數(shù)，必須開辟一個存儲單元，并將該數(shù)存入存儲單元中，并鏈入鏈表中。n步驟：步驟：（1）申請新結(jié)點(diǎn)、調(diào)用new過程開辟一個存儲單元（2）在結(jié)點(diǎn)的數(shù)據(jù)域填讀入的數(shù)據(jù)（3）將結(jié)點(diǎn)鏈入表中某個位置（頭指針指向第

9、一個結(jié)點(diǎn).）鏈表尾結(jié)點(diǎn)的后繼結(jié)點(diǎn)為空program create_link;type pointer=rec; rec=record data:integer; next:pointer; end;var head,p,q:pointer; num,j,outnum:integer;begin num:=0;read(j); while j=0 do begin num:=num+1; new(p); p.data:=j; if num=1 then head:=p else q.next:=p; q:=p; read(j); end; if headnil then q.next:=nil;

10、/ dispose(p); writeln(num:,num);End.2、鏈表的遍歷與輸出鏈表的遍歷與輸出n從表頭開始依次訪問至表尾,方法如下：n（1)設(shè)臨時工作變量P指針鏈表的頭結(jié)點(diǎn)（頭結(jié)點(diǎn)的地址不能丟失或改變，否則會丟失整個鏈表）n（2）while pnil do begin 輸出p所指結(jié)點(diǎn)（當(dāng)前結(jié)點(diǎn)）的數(shù)據(jù)值； p移向后一個結(jié)點(diǎn)； end;練習(xí)：請將前面的鏈表輸出3、線性鏈表的查找、線性鏈表的查找n在鏈表中查找符合條件的結(jié)點(diǎn)（一般是指定數(shù)據(jù)值）（1）設(shè)臨時變量p指向鏈表頭結(jié)點(diǎn)（2）while (未到表尾) and (未找到) do if (找到) then 退出循環(huán) else p移向下

11、一個結(jié)點(diǎn) （3）if 到了表尾 then 輸出“未找到” else （找到）對p所指結(jié)點(diǎn)進(jìn)行相應(yīng)處理。nWhile (pnil) and not(found) do begin if x=p.data then found:=true else p:=p.next end;nIf found thenelse writeln(no found);4、結(jié)點(diǎn)的插入n在P結(jié)點(diǎn)和Q結(jié)點(diǎn)之間插入一個結(jié)點(diǎn)m，其操作如下圖所示，用下列語句即可完成。P.next:=m;M.next:=q; 這兩步的順序可以顛倒嗎？這兩步的順序可以顛倒嗎？5、結(jié)點(diǎn)的刪除n要刪除單向鏈表中結(jié)點(diǎn)P，則只要將其前趨結(jié)點(diǎn)的指針域指向P

12、的后繼結(jié)點(diǎn)即可，如上圖所示。 q.next:=p.next; dispose(p); 循環(huán)鏈表n對于單向鏈表（線性鏈表），讓尾部結(jié)點(diǎn)的指針指向鏈表的頭部，這樣就形成了一個鏈環(huán)，從任何一個結(jié)點(diǎn)開始都可以訪問完全部的結(jié)點(diǎn)。這就是循環(huán)鏈表，也成為環(huán)形鏈表。n對于單向鏈表（線性鏈表），每個結(jié)點(diǎn)都只有一個指向其后繼結(jié)點(diǎn)的指針域，如果鏈表的每個結(jié)點(diǎn)再加上一個指向其前趨結(jié)點(diǎn)的指針域，則稱這種鏈表為雙向鏈表。n對雙向鏈表的插入、刪除特別方便。同樣我們也可以定義雙向循環(huán)鏈表。小結(jié)：n掌握線性鏈表的訪問的基本方法是：從頭結(jié)點(diǎn)開始沿線性鏈表反向進(jìn)行探求，一般用到兩個指針變量：一個用于指向剛查過的結(jié)點(diǎn)地址，另一個用于指向下一個待查的結(jié)點(diǎn)地址。結(jié)束訪問的條件有兩個：一個是結(jié)點(diǎn)地址為nil ，另一個是找到了相應(yīng)的結(jié)點(diǎn)。指針的應(yīng)用二指針的應(yīng)用二 二二 叉叉 樹樹n二叉樹是計(jì)算機(jī)中常用的另外一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，每個結(jié)點(diǎn)最多有兩個后繼結(jié)點(diǎn)，一左一右，分別稱為左子女和右子女。因此對