指針與動態(tài)變量第一頁，共二十四頁，編輯于2023年，星期三引言以前所講的簡單類型的數(shù)據(jù)或構造類型的數(shù)據(jù)都是靜態(tài)數(shù)據(jù)，這些類型的變量一經定義，就在內存中占有固定的存儲單元，直至程序結束。指針類型的變量屬于動態(tài)數(shù)據(jù)。是在程序執(zhí)行時，根據(jù)程序的數(shù)據(jù)存儲需要而擴充或縮減。在PASCAL中，指針變量存放某個存儲單元的地址，即指針變量指向某個存儲單元。第二頁，共二十四頁，編輯于2023年，星期三指針類型說明的一般形式Type指針類型標識符=^類型標識符；說明1：指針類型標識符由用戶定義，必須符合標識符命名規(guī)則；說明2：類型標識符：是除文件以外的任何數(shù)據(jù)類型。例1：typepoint1=^integer; point2=^real;解釋：上例定義了兩個指針類型，point1是整型指針類型，point2是實型指針類型。第三頁，共二十四頁，編輯于2023年，星期三指針類型變量的定義說明了指針類型，就可以定義該類型的指針變量。例varp1:point1;p2:point2;類型說明可以與變量定義合并在一起。例：varp1:^integer; p2:^real;注意點：指針類型說明時，可以不遵循“先說明”后“使用”的原則。例：point=^node; node=recordnum:integer; name:string;end;varstu:^point;

第四頁，共二十四頁，編輯于2023年，星期三動態(tài)變量靜態(tài)變量中存放的是相應類型的數(shù)據(jù)，而指針變量中存放的是相應類型數(shù)據(jù)所在的存儲單元的地址。要訪問指針變量所指向的數(shù)據(jù)，必須使用動態(tài)變量。動態(tài)變量不在變量說明中定義，在程序執(zhí)行過程中建立。它沒有標識符，而是用指針變量后跟符號^表示。如p^:=245;指針變量本身是簡單類型（靜態(tài)數(shù)據(jù)），它所指向的數(shù)據(jù)可以構成動態(tài)數(shù)據(jù)整型變量P某個數(shù)據(jù)指針變量P動態(tài)變量p^某個存儲單元的地址某個數(shù)據(jù)第五頁，共二十四頁，編輯于2023年，星期三動態(tài)變量的建立指針變量的值一般是通過系統(tǒng)分配的，建立一個動態(tài)變量（動態(tài)存儲單元）必須調用標準過程NEW。New過程調用的格式：new(指針變量);New過程的作用:建立動態(tài)變量；為動態(tài)變量分配一定的存儲空間，用以存放動態(tài)變量；并將動態(tài)變量的存儲空間的首地址存入指針變量中。例：varp:^integer; 此時P的值為nil

執(zhí)行語句：new(p);此時P的值為一存儲單元地址

p^:=245;一個指針變量只能存放一個地址第六頁，共二十四頁，編輯于2023年，星期三動態(tài)變量的撤消釋放動態(tài)變量使用標準過程dispose。Dispose過程調用的格式：dispose(指針變量)Dispose過程的作用：釋放指針所指向的存儲單元，使指針變量的值為nil，不指向任何存儲單元。例：dispose(p);第七頁，共二十四頁，編輯于2023年，星期三動態(tài)變量的操作動態(tài)變量的引用：指針變量^例：p^:=4;i:=p^;對動態(tài)變量所能進行的操作是該類型(指針的基類型)所允許的全部操作。例：varp:^integer; i:integer;New(p); i:=4: p^:=4;第八頁，共二十四頁，編輯于2023年，星期三指針變量的操作可調用new、dispose過程。如new(p); dispose(p);具有同一基類型的指針變量之間相互賦值。例：varp1,p2,p3:^integer;New(p1); new(p2); new(p3);P1^:=5; p2:=P1; p3^:=p1^+P2^;可以給指針變量賦nil值。Nil是pascal的關鍵字，它表示指針的值為“空”。例：P1:=nil;可以對指針變量進行比較運算。例1：new(P1);write(p1=nil);結果將輸出FALSE例2：new(p1);new(p2);write(p1=p2);false第九頁，共二十四頁，編輯于2023年，星期三指針的應用一

——

鏈表結構第十頁，共二十四頁，編輯于2023年，星期三簡單鏈表結構示意圖每個框表示鏈表的一個元素，稱為結點框的頂部表示了該存儲單元的地址(當然，這里的地址是假想的)每個結點包含兩個域：一個域存放整數(shù)，稱為數(shù)據(jù)域，另一個域存放下一個結點(稱為該結點的后繼結點，相應地，該結點為后繼結點的前趨結點)的地址，稱為指針域鏈表的第一個結點稱為表頭，最后一個結點稱為表尾指向表頭的指針head稱為頭指針(當head為nil時，稱為空鏈表)，在這個指針變量中存放了表頭的地址在表尾結點中，指針域不指向任何結點，一般放入nil。第十一頁，共二十四頁，編輯于2023年，星期三鏈表的基本結構鏈表中的每個結點至少應該包含兩個域：一是數(shù)據(jù)域，一是指針域，因此，每個結點都是一個記錄類型。指針的基類型也正是這個記錄類型。因此，head可以這樣定義：

typepointer=^rec；

rec=record

data：integer;

next:pointer;

end;

varhead:pointer;相鄰結點的地址不一定是連續(xù)的。整個鏈表是通過指針來順序訪問的，一旦失去了一個指針值，后面的元素將全部丟失與數(shù)組結構相比，使用鏈表結構時可根據(jù)需要采用適當?shù)牟僮鞑襟E使鏈表加長或縮短，而使存儲分配具有一定的靈活性，這是鏈表結構的優(yōu)點與數(shù)組結構相比，數(shù)組元素的引用比較簡單，直接用“數(shù)組名[下標]”即可，因為數(shù)組元素占用連續(xù)的存儲單元，而引用鏈表元素的操作卻比較復雜。第十二頁，共二十四頁，編輯于2023年，星期三線性鏈表鏈表中的每個結點只包含一個指針域，故稱為線性鏈表或單鏈表。線性鏈表的存取必須從頭指針開始進行，頭指針指示鏈表中第一個結點（表頭）的存儲位置。同時，由于最后一個結點（表尾）沒有后繼，故線性鏈表中最后一個結點的指針域的值為空，即為nil。第十三頁，共二十四頁，編輯于2023年，星期三

線性鏈表的主要操作

1、線性鏈表的建立例：編寫一個程序，將讀入的一串正整數(shù)存入鏈表，遇負數(shù)結束并統(tǒng)計鏈表的長度。分析：每讀入一個數(shù)，必須開辟一個存儲單元，并將該數(shù)存入存儲單元中，并鏈入鏈表中。步驟：（1）申請新結點、調用new過程開辟一個存儲單元（2）在結點的數(shù)據(jù)域填讀入的數(shù)據(jù)（3）將結點鏈入表中某個位置（頭指針指向第一個結點.）鏈表尾結點的后繼結點為空第十四頁，共二十四頁，編輯于2023年，星期三programcreate_link;typepointer=^rec;rec=recorddata:integer;next:pointer;end;varhead,p,q:pointer;num,j,outnum:integer;beginnum:=0; read(j);whilej>=0dobeginnum:=num+1;new(p);p^.data:=j;ifnum=1thenhead:=pelseq^.next:=p;

q:=p;read(j);end;ifhead<>nilthenq^.next:=nil;//dispose(p);writeln('num:',num);End.第十五頁，共二十四頁，編輯于2023年，星期三2、鏈表的遍歷與輸出從表頭開始依次訪問至表尾,方法如下：（1)設臨時工作變量P指針鏈表的頭結點（頭結點的地址不能丟失或改變，否則會丟失整個鏈表）（2）whilep<>nildobegin

輸出p所指結點（當前結點）的數(shù)據(jù)值；

p移向后一個結點；

end;練習：請將前面的鏈表輸出第十六頁，共二十四頁，編輯于2023年，星期三3、線性鏈表的查找在鏈表中查找符合條件的結點（一般是指定數(shù)據(jù)值）（1）設臨時變量p指向鏈表頭結點（2）while(未到表尾)and(未找到)doif(找到)then退出循環(huán)elsep移向下一個結點（3）if到了表尾then輸出“未找到”else（找到）對p所指結點進行相應處理。While(p<>nil)andnot(found)dobeginifx=p^.datathenfound:=trueelsep:=p^.nextend;Iffoundthen……elsewriteln(‘nofound’);第十七頁，共二十四頁，編輯于2023年，星期三4、結點的插入在P結點和Q結點之間插入一個結點m，其操作如下圖所示，用下列語句即可完成。P^.next:=m;M^.next:=q;這兩步的順序可以顛倒嗎？第十八頁，共二十四頁，編輯于2023年，星期三5、結點的刪除要刪除單向鏈表中結點P，則只要將其前趨結點的指針域指向P的后繼結點即可，如上圖所示。

q^.next:=p^.next;

dispose(p);第十九頁，共二十四頁，編輯于2023年，星期三循環(huán)鏈表對于單向鏈表（線性鏈表），讓尾部結點的指針指向鏈表的頭部，這樣就形成了一個鏈環(huán)，從任何一個結點開始都可以訪問完全部的結點。這就是循環(huán)鏈表，也成為環(huán)形鏈表。對于單向鏈表（線性鏈表），每個結點都只有一個指向其后繼結點的指針域，如果鏈表的每個結點再加上一個指向其前趨結點的指針域，則稱這種鏈表為雙向鏈表。對雙向鏈表的插入、刪除特別方便。同樣我們也可以定義雙向循環(huán)鏈表。第二十頁，共二十四頁，編輯于2023年，星期三小結：掌握線性鏈表的訪問的基本方法是：從頭結點開始沿線性鏈表反向進行探求，一般用到兩個指針變量：一個用于指向剛查過的結點地址，另一個用于指向下一個待查的結點地址。結束訪問的條件有兩個：一個是結點地址為nil，另一個是找到了相應的結點。第二十一頁，共二十四頁，編輯于2023年，星期三指針的應用二

——

二叉樹第二十二頁，共二十四頁，編輯于2023年，星期三二叉樹是計算機中常用的另外一種動態(tài)數(shù)據(jù)結構，每個結點最多有兩個后繼結點，一左一右，分別稱為左子女和右