第二章指針與鏈表

1、第二章指針與鏈表一、靜態(tài)存貯和動態(tài)存貯1、靜態(tài)存貯程序中的變量一經(jīng)說明，計(jì)算機(jī)操作系統(tǒng)就會在內(nèi)存空間中分配相應(yīng)的存貯單元，其中變量名是存貯單元的地址，而變量的值是存貯單元的內(nèi)容，且該存貯單元自始至終都被該變量所占用，直到程序結(jié)束。如果變量是局部變量，那么在它的作用域內(nèi)，一經(jīng)說明也占有一定的存貯單元，直到退出其作用域?yàn)橹?。這樣的變量，在程序執(zhí)行過程中，不能隨時(shí)使用隨時(shí)分配存貯空間，也不能在程序執(zhí)行的過程中，釋放這些空間。也就是說，一旦給這些變量分配存貯空間，無論程序是否還需要使用，它們都要占用一定的存貯空間，以便給用戶存貯數(shù)據(jù)。我們稱具有這樣特點(diǎn)的存貯為靜態(tài)存貯，它所對應(yīng)的變量稱為靜態(tài)變量。如字

2、符類型、數(shù)組類型、記錄類型等。這類變量的優(yōu)點(diǎn)是存貯方便，查找容易，可以通過一個(gè)簡單的公式隨機(jī)存取表中的任一元素，邏輯關(guān)系上相鄰的兩個(gè)元素在物理位置上也是相鄰的，很容易找到前趨與后繼元素；缺點(diǎn)是在線性表的長度不確定時(shí)，必須分配足夠大的存儲空間，經(jīng)常浪費(fèi)了寶貴的存儲資源；而線性表的容量一經(jīng)定義確定后就難以擴(kuò)充；在插入和刪除線性表的元素時(shí)，需要移動大量的元素，時(shí)間效率也比較差。2、動態(tài)存貯在程序執(zhí)行過程中，通過向操作系統(tǒng)申請存貯空間或釋放存貯空間的命令，達(dá)到動態(tài)管理計(jì)算機(jī)的存貯空間，以保證存貯空間的充分利用。存貯空間可以隨時(shí)申請、隨時(shí)釋放，這樣的存貯方式稱為動態(tài)存貯，其變量稱為動態(tài)變量。指針變量即為

3、動態(tài)變量。動態(tài)存儲所需要的空間可以是不連續(xù)的，這樣有利于充分利用零散的小空間。但缺無法用o（1）的時(shí)間實(shí)現(xiàn)存取了。如何用這些零散的空間存儲數(shù)組這些大規(guī)模數(shù)據(jù)呢？如何表示這些數(shù)據(jù)之間的邏輯關(guān)系呢？為了表示這些物理存儲單元之間的邏輯關(guān)系，對于每個(gè)數(shù)據(jù)元素來說，除了要存儲它本身的信息（數(shù)據(jù)域data）外，還要存儲它的直接后繼元素的存儲位置（指針域，一般用link 或 next 表示） 。我們往往把這兩部分信息合在一起稱為一個(gè)“結(jié)點(diǎn)node” 。 n 個(gè)結(jié)點(diǎn)鏈接在一起就構(gòu)成了一個(gè)鏈表。n=0 時(shí)，稱為空鏈表。同時(shí)，為了按照邏輯順序?qū)︽湵碇械脑剡M(jìn)行各種操作，我們需要定義一個(gè)變量用來存儲整個(gè)鏈表的第一個(gè)

4、結(jié)點(diǎn)的物理位置，這個(gè)變量稱為“頭指針，一般用h 或 head 表示”。也可以把頭指針定義成一個(gè)結(jié)點(diǎn)，稱為“頭結(jié)點(diǎn)”，頭結(jié)點(diǎn)的數(shù)據(jù)域可以不存儲任何信息，也可以存儲線性表的長度等附加信息，頭結(jié)點(diǎn)的指針域（頭指針）存儲指向第一個(gè)結(jié)點(diǎn)的指針，若線性表為空表，則頭結(jié)點(diǎn)的指針域?yàn)榭眨?nil） 。由于最后一個(gè)元素沒有后繼，所以線性表中最后一個(gè)結(jié)點(diǎn)的指針域?yàn)榭眨╪il） 。由于此鏈表中的每個(gè)結(jié)點(diǎn)都只包含一個(gè)指針域，故稱為“線性鏈表或單向鏈表”。二、指針類型與指針變量1指針類型和指針變量的說明type指針類型標(biāo)識符= 基類型名；基類型不能為文件類型var 指針變量名：指針類型標(biāo)識符；2申請存儲單元動態(tài)申請、空

5、間大小由指針變量的基類型決定new(指針變量名 )；pascal 標(biāo)準(zhǔn)過程 3指針變量的賦值指針變量名：=nil；初始化，暫時(shí)不指向任何存儲單元如何表示和操作指針變量？不同于簡單變量（如a：=0； ） ，pascal 規(guī)定用“指針變量名”的形式引用指針變量（如p：=0； ） 。區(qū)分如下圖所示：如計(jì)算機(jī)執(zhí)行下面的程序段時(shí)：new（h） ；h:=123；new（h） ；h:=234;內(nèi)存示意圖如圖所示（陰影部分表示該單元已被占）：4相同基類型的指針變量之間可以進(jìn)行相互賦值。如有下面的程序段，可以畫出右邊的示意圖：varp1,p2:integer;new(p1);new(p2);p1:=90;p2:

6、=80;p1:=p2;5關(guān)系運(yùn)算如：ifp1=p2thenwhilep nildo 6釋放動態(tài)存儲單元dispose( 指針變量名 );系統(tǒng)收回指針變量所指的內(nèi)存單元另作它用，此時(shí)指針變量的值變成無定義。注意，我們應(yīng)該養(yǎng)成一個(gè)好的習(xí)慣，就是及時(shí)釋放不用的動態(tài)存儲單元，很多同學(xué)使用指針變量時(shí)就知道new(p) ，而不知道及時(shí)dispose(p)，最后造成內(nèi)存空間溢出錯誤、出現(xiàn)死循環(huán)甚至死機(jī)現(xiàn)象。三、單向鏈表1、單向鏈表的結(jié)構(gòu)由于單向鏈表的每個(gè)結(jié)點(diǎn)都有一個(gè)數(shù)據(jù)域和一個(gè)指針域，所以，每個(gè)結(jié)點(diǎn)都可以定義成一個(gè)記錄。一般，把 head 稱為頭結(jié)點(diǎn)， head.next 稱為頭指針。比如，有如下一個(gè)單向鏈

7、表，如何定義這種數(shù)據(jù)結(jié)構(gòu)呢？方法如下：type pointer=nodetype;nodetype=recorddata:datatype;next:pointer;嵌套定義 end;var head,p,q,r:pointer;2、單鏈表的建立、輸出下面結(jié)合一個(gè)例子，給出建立并輸出單向鏈表的程序。例 1、從鍵盤輸入若干個(gè)正整數(shù)，請按輸入順序建立一個(gè)單向鏈表并輸出它，輸入-1 時(shí)表示結(jié)束。program creat;type pointer=nodetype;nodetype=recorddata:integer;next:pointer;end;var head,p,r:pointer;r

8、指向鏈表的當(dāng)前最后一個(gè)結(jié)點(diǎn)，可以稱為尾指針x:integer;beginwriteln(please input num(-1 is end):);read(x);new(head);申請頭結(jié)點(diǎn) head.next:=nil;頭結(jié)點(diǎn)初始化 r:=head;while x-1 do讀入的數(shù)非 -1beginnew(p);則，申請一個(gè)新結(jié)點(diǎn)p.data:=x;p.next:=nil;r.next:=p;把新結(jié)點(diǎn)鏈接到前面的鏈表中，實(shí)際上r 是 p 的直接前趨 r:=p;尾指針后移一個(gè)read(x);end;r.next:=nil;最后一個(gè)結(jié)點(diǎn)的指針域賦空readln;writeln(output:

9、);輸出p:=head.next;頭指針沒有數(shù)據(jù)，只要從第一個(gè)結(jié)點(diǎn)開始就可以了while p.nextnil dobeginwrite(p.data:4);p:=p.next;end;write(p.data:4);最后一個(gè)結(jié)點(diǎn)的數(shù)據(jù)單獨(dú)輸出，也可以改用repeat 循環(huán) readln;end.為了充分利用空間和隨時(shí)統(tǒng)計(jì)出鏈表的實(shí)際結(jié)點(diǎn)個(gè)數(shù)，我們經(jīng)常把鏈表的實(shí)際結(jié)點(diǎn)個(gè)數(shù)存入到頭結(jié)點(diǎn)的數(shù)據(jù)域（head.data ）中，請大家改寫上面的程序，并輸出最后的結(jié)點(diǎn)個(gè)數(shù)。3、查找“數(shù)據(jù)域滿足一定條件的結(jié)點(diǎn)”（1）從前往后找到第一個(gè)滿足條件的結(jié)點(diǎn),程序如下：p:=headnext;while(p.data

10、x) and(p.nextnil)do p:=p.next;找到第一個(gè)就結(jié)束ifp.data= xthen找到了處理else輸出不存在；（2）如果想找到所有滿足條件的結(jié)點(diǎn)，則修改如下：p:=headnext;whilep.nextnildo一個(gè)一個(gè)判斷 beginifp.data = xthen找到一個(gè)處理一個(gè)；p:=p.next;end;4、獲取第i 個(gè)結(jié)點(diǎn)的數(shù)據(jù)域functionget(head:pointer;i:integer):integer;var p:pointer;j:integer;beginp:=head.next;j:=1;while(pnil) and (ji) dob

11、eginp:=p.next; j:=j+1;end;if(p nil)and(j=i)thenwriteln(p.data)elsewriteln(inot exsit! );end;5、插入一個(gè)結(jié)點(diǎn)到單鏈表中一般情況： s.next:=p.next;p.next:=s;特殊情況，插在表頭：s.next:=head;head:=s;插在表尾（假設(shè)p 已是表尾）：p.next:=s;p:=s;程序?qū)崿F(xiàn)時(shí)，從表頭開始找，是一致的。procedureinsert(head:pointer;i:integer;x:integer);插入 x 到第 i 個(gè)元素之前 varp,s:pointer;j:in

12、teger;beginp:=head;j:=0;while(pnil) and (ji-1)thenwriteln( nothis position!)elsebegin插入 new(s);s.data:=x;s.next:=p.next;p.next:=s;end;end;6、刪除單向鏈表中的第i 個(gè)結(jié)點(diǎn)（如下圖中數(shù)據(jù)域?yàn)椤癰”的結(jié)點(diǎn)）proceduredelete(head:pointer;i:integer;);刪除第 i 個(gè)元素 varp,s:pointer;j:integer;beginp:=head;j:=0;while(p.nextnil) and (ji-1)thenwrite

13、ln( nothis position!)elsebegin刪除 p 的后繼結(jié)點(diǎn)，假設(shè)為ss:=p.next;p.next:=p.next.next;或 p.next:=s.nextdispose(s);end;end;7、求單向鏈表的實(shí)際長度functionlen(head:pointer):integer;var n:integer;beginp:=head;n:=0;whilep nildobeginn:=n+1;p:=p.next;end;len:=n;end;四、雙向鏈表每個(gè)結(jié)點(diǎn)有兩個(gè)指針域和若干數(shù)據(jù)域，其中一個(gè)指針域指向它的直接前趨結(jié)點(diǎn)，一個(gè)指向它的直接后繼結(jié)點(diǎn)。它的優(yōu)點(diǎn)是訪問、插

14、入、刪除更方便，速度也快了。實(shí)質(zhì)上是以空間換時(shí)間。數(shù)據(jù)結(jié)構(gòu)的定義：type pointer=nodetype;nodetype=recorddata:datatype;pre,next:pointer;pre 指向前趨， next 指向后繼 end;var head,p,q,r:pointer;下面給出雙向鏈表的插入和刪除過程。procedure insert(head:pointer;i,x:integer);在雙向鏈表的第i 個(gè)結(jié)點(diǎn)之前插入xvars,p:pointer;j:integer;beginnew(s);s.data:=x;p:=head;j:=0;while(p.nextnil

15、) and (ji) dobeginp:=p.next;j:=j+1;end;p 指向第 i 個(gè)結(jié)點(diǎn) if p=nil then writeln( nothis position!)elsebegin將結(jié)點(diǎn) s 插入到結(jié)點(diǎn)p之前 s.pre:=p.pre;1、將 s 的前趨指向p 的前趨 p.pre:=s;2、將 s 作為 p 的新前趨 s.next:=p;3、將 s的后繼指向ps.pre.next:=s;4、將 p 的本來前趨結(jié)點(diǎn)的后繼指向send;end;proceduredelete(head:pointer;i:integer);刪除雙向鏈表的第i 個(gè)結(jié)點(diǎn) varp:pointer;j

16、:integer;beginp:=head;j:=0;while(p.nextnil) and (ji) dobeginp:=p.next;j:=j+1;end;p 指向第 i 個(gè)結(jié)點(diǎn) if p=nil then writeln( nothis position!)elsebegin將結(jié)點(diǎn) p 刪除 p.prenext:=p.next;1、p 的前趨結(jié)點(diǎn)的后繼賦值為p的后繼 p.next.pre:=p.pre;2、p 的后繼結(jié)點(diǎn)的前趨賦值為p的前趨 end;end;五、循環(huán)鏈表1、單向循環(huán)鏈表：最后一個(gè)結(jié)點(diǎn)的指針指向頭結(jié)點(diǎn)。如下圖：2、雙向循環(huán)鏈表：最后一個(gè)結(jié)點(diǎn)的后繼指針指向頭結(jié)點(diǎn)，且頭結(jié)點(diǎn)的

17、前趨指針指向最后一個(gè)結(jié)點(diǎn)。如下圖：六、循環(huán)鏈表的應(yīng)用舉例例 2、約瑟夫問題【問題描述】有 n 只猴子，按順時(shí)針方向圍成一圈（開始時(shí)編號為1，2， n） ，選大王。從第1 號猴子開始報(bào)數(shù)1，2， 3，數(shù)到m 號時(shí)該猴子退出到圈外，如此報(bào)數(shù)直到圈內(nèi)只剩下一只猴子時(shí)，此猴便是大王。你的任務(wù)是從鍵盤讀入n,m，程序判斷輸出最后的大王是幾號？如輸入： 135輸出： 6換個(gè)問法：n 只猴子圍成一個(gè)圈，按順時(shí)針方向報(bào)數(shù)，報(bào)到m 的出圈，直到剩下一只猴子結(jié)束。輸出猴子依次出圈的序號?！舅惴ǚ治觥亢苊黠@這是一個(gè)單向循環(huán)鏈表。數(shù)據(jù)域?yàn)楹镒拥木幪?，指針域?yàn)橄乱粋€(gè)猴子的地址。從第1 個(gè)猴子開始一一報(bào)數(shù)，報(bào)數(shù)實(shí)際上是計(jì)

18、數(shù)，只要設(shè)一個(gè)計(jì)數(shù)器就可以了。當(dāng)計(jì)數(shù)器由1 變化到 m 時(shí)，刪除該結(jié)點(diǎn)，從下一個(gè)結(jié)點(diǎn)開始繼續(xù)計(jì)數(shù)（計(jì)數(shù)器回1 或者用求余運(yùn)算） 。直到鏈表中只剩下一個(gè)結(jié)點(diǎn)?！緟⒖汲绦颉縫rogram king;typepoint=node;node=recorddata:integer;next:point;end;varm,n,s:integer;p,q,head:point;beginwrite(input n,m:); readln(n,m);new(head);q:=head;head.data:=1;for s:=2to n dobeginnew(p);p.data:=s;q.next:=p;q:=

19、p;end;q.next:=head; s:=1;q:=head;repeatp:=q.next;s:=s+1;if smod m=0 then beginq.next:=p.next;writeln(p.data:4);dispose(p);endelse q:=puntil q.next=q;writeln(the king is:,q.data)end.七、線性表的綜合應(yīng)用【例 3】用單向鏈表實(shí)現(xiàn)線性表的歸并操作問題描述 已知線性表l1 和 l2 中的數(shù)據(jù)元素按值非遞減有序排列，現(xiàn)要求將l1 和 l2 歸并成一個(gè)新的線性表 l3，使 l3 中的數(shù)據(jù)元素仍按非遞減有序排列。例如：l1=（1

20、，3，4，5，8，9，10，11，12） ，l2=（2 ，4， 6， 8） ，則 l3=（ 1，2，3，4，4，5，6， 8，8，9，10，11，12） 。注意：相同元素照算。標(biāo)準(zhǔn)過程 proceduremerge(h1,h2:pointer;varh3:pointer);將頭指針分別為h1,h2 的兩個(gè)單鏈表歸并成一個(gè)新的單鏈表，該鏈表頭指針為h3varp1,p2,p3:pointer;臨時(shí)用工作指針，一般不能破壞頭指針beginp1:=h1.next;p2:=h2.next;h3:=h1;新鏈表共用第一個(gè)鏈表，簡化，也可以另外開辟一個(gè)頭結(jié)點(diǎn)p3:=h3;while(p1nil)and (p

21、2nil)do歸并beginifp1.data=p2.datathenbegin將 p1 結(jié)點(diǎn)鏈接到p3 中去p3.next:=p1;指向p3:=p1;p3 后移p1:=p1.nextp1 后移endelsebegin將 p2 結(jié)點(diǎn)鏈接到p3 中去p3.next:=p2;p3:=p2;p2:=p2.nextend;end;ifp1nilthenp3.next:=p1將 p1 中剩下的結(jié)點(diǎn)一起鏈接到p3 中elsep3.next:=p2;將 p2 中剩下的結(jié)點(diǎn)一起鏈接到p3 中end;2一元多相式的表示和加減運(yùn)算問題描述 在數(shù)學(xué)上，一個(gè)一元n 次多項(xiàng)式pn(x) ，可以按升冪寫成：pn(x)=p

22、0 + p1x + p2x2+ p3x3+pnxn它由 n+1 個(gè)系數(shù)唯一確定。因此，在計(jì)算機(jī)里，它可以用一個(gè)線性表p來表示：p = （p0，p1，p2， pn）每一項(xiàng)的指數(shù)i 隱含在系數(shù)pi 的序號里?！救蝿?wù)】輸入兩行，每行為一個(gè)字符串，分別表示一個(gè)一元n 次多項(xiàng)式pn(x)和一個(gè)一元m次多項(xiàng)式qm(x)，輸出它們的和。注意：不許輸出系數(shù)為0 的項(xiàng)、不要輸出為1 的系數(shù)和冪，且按冪的升序輸出?！据斎胼?出樣例】輸入 ：3x2+8-5x6+x6x6+5x-3x2+8x9-20輸 出： -12+6x+x6+8x9【數(shù)據(jù)結(jié)構(gòu)】方法 1：按 n,m 分別生成 n+1 和m+1 個(gè)結(jié)點(diǎn)的 兩個(gè)單 鏈表，即不 管 系數(shù)是 否為0 都生成一個(gè)結(jié)點(diǎn)。一個(gè)指針域指 向后繼 結(jié)點(diǎn)，一個(gè)數(shù)據(jù)域存放 系數(shù)（不存在的項(xiàng)系數(shù)為0）。浪費(fèi) 了很多空 間，尤其 是指數(shù)很高 ，而項(xiàng)數(shù) 很少 的 情況 下， 浪費(fèi) 更 嚴(yán)重。方法 2