【正文】 《 C程序設(shè)計(jì)實(shí)例教程 》下 梁立 第 7章 動(dòng)態(tài)組織數(shù)據(jù) 第 8章 綜合應(yīng)用 第七章 動(dòng)態(tài)組織數(shù)據(jù) 建立鏈表的過(guò)程 ? 設(shè)想一下，我們看雜志時(shí)碰到有篇文章 3頁(yè)不夠放，4頁(yè)又空著太多。這時(shí)，編輯往往先給這篇文章（且稱它為文章 a）排 3頁(yè) (且稱這 3頁(yè)為 )，接著排其他文章，等什么時(shí)候有空的頁(yè)面還夠安排 a剩下的部分 (且稱它為 )時(shí)，就把 排進(jìn)去。由于文章 a在排版時(shí)被分成了不連續(xù)的兩塊，讀者怎樣才能找到第二個(gè)邏輯塊呢？編輯在“下接 XX頁(yè)”，讀者順著這個(gè)線索很容易就找到了 。如此一來(lái)， ，還有指示下一個(gè)邏輯塊在哪里的線索。通過(guò)這個(gè)線索， 。 ? 那么，讀者又是怎么知道 有沒(méi)有另外一個(gè)邏輯塊呢？其實(shí)每種雜志的每篇文章的最后都有一個(gè)特殊的符號(hào)，讀者看到這個(gè)符號(hào)就知道這已經(jīng)是最后一個(gè)邏輯塊了。而厚厚的一本書(shū)中，讀者又怎樣找到文章 a呢？翻翻目錄就知道了，那里有文章 a所在頁(yè)碼的信息。 圖 兩個(gè)結(jié)點(diǎn)構(gòu)成的鏈表 文章 a ... ... 下接 xx頁(yè) ... ... 完 文章 a xx頁(yè) ... ... 目錄 這樣， 構(gòu)成的鏈表：目錄中的頁(yè)碼指向鏈表 a的第一個(gè)結(jié)點(diǎn)，這個(gè)頁(yè)碼信息通常稱為頭指針，只要有這個(gè)頭指針就能找到整個(gè)鏈表；，指示下一個(gè)邏輯塊在哪里； 面不再有其他結(jié)點(diǎn)，稱為尾結(jié)點(diǎn)。如圖 所示。 ? 鏈表是一種重要并且很常用的數(shù)據(jù)結(jié)構(gòu)，可以動(dòng)態(tài)地組織數(shù)據(jù)。鏈表不要求兩個(gè)元素在物理上相鄰，元素的物理順序與邏輯順序可以不同，只要在元素結(jié)構(gòu)中加一個(gè)指針項(xiàng)，用來(lái)指向下一個(gè)元素的地址便可。 ? 組成鏈表的基本單元是結(jié)點(diǎn)，所謂結(jié)點(diǎn)至少由 2個(gè)域組成，一個(gè)是數(shù)據(jù)域，一個(gè)是指針域，數(shù)據(jù)域存儲(chǔ)結(jié)點(diǎn)本身的信息，指針域指向后繼結(jié)點(diǎn)。每個(gè)元素都有一個(gè)指針指向下一個(gè)元素，如此環(huán)環(huán)相扣下去，就組成了一個(gè)鏈表。 ? 鏈表的第一個(gè)結(jié)點(diǎn)也代表著這個(gè)鏈表的起始元素，通過(guò)這個(gè)結(jié)點(diǎn)的指針，可以一直訪問(wèn)完鏈表。所以，有必要定義一個(gè)頭指針來(lái)指向鏈表的第一個(gè)元素。尾結(jié)點(diǎn)的指針域置為“ NULL（空）”，作為鏈表結(jié)束的標(biāo)志。常見(jiàn)的鏈表有兩種結(jié)構(gòu)，如圖 所示： a1 a2 a3 a4 a1 a2 a3 a4 head （ b） 帶頭結(jié)點(diǎn)的單鏈表 圖 鏈表示意圖 ^ ^ （ a） 不帶頭結(jié)點(diǎn)的單鏈表 圖 ，符號(hào)“ ^”表示空指針，在 C語(yǔ)言中用“ NULL”表示空指針，這個(gè)空指針表示尾結(jié)點(diǎn)沒(méi)有后繼，鏈表到此結(jié)束。圖中所示鏈表有 4個(gè)結(jié)點(diǎn)，ai表示數(shù)據(jù)部分，可以是基本類型或構(gòu)造類型的數(shù)據(jù)。不帶頭結(jié)點(diǎn)的單鏈表頭指針 head直接指向鏈表的第一個(gè)結(jié)點(diǎn)，而帶頭結(jié)點(diǎn)的單鏈表頭指針head則指向一個(gè)附加的結(jié)點(diǎn)，這個(gè)附加結(jié)點(diǎn)的指針域才指向鏈表的第一個(gè)結(jié)點(diǎn)。由于這個(gè)附加結(jié)點(diǎn)的存在，無(wú)論怎么操作鏈表，頭指針的指向總是不變。此處以不帶頭結(jié)點(diǎn)的單鏈表為例講解鏈表的基本操作。所謂單鏈表就是每個(gè)結(jié)點(diǎn)只有一個(gè)指針域。 【 例 71】 用鏈表實(shí)現(xiàn)通信錄的管理。 【 分析 】 通信錄中每個(gè)聯(lián)系人的信息，一般應(yīng)該包括姓名、電話號(hào)碼和其他一些信息。為了方便查找和更新，經(jīng)常要對(duì)通信錄中添加新的記錄、刪除無(wú)效記錄和調(diào)整記錄位置，用鏈表來(lái)實(shí)現(xiàn)通信錄的管理比較方便。 ? 鏈表的每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?qū)?yīng)著一條通信錄所包含的數(shù)據(jù)信息，用一個(gè)結(jié)構(gòu)體變量來(lái)表示，例子中包含聯(lián)系人的姓名和電話。為了把兩個(gè)結(jié)點(diǎn)的連接起來(lái)，結(jié)點(diǎn)中還應(yīng)該有一個(gè)指向下一結(jié)點(diǎn)的指針域，這個(gè)指針的類型為結(jié)點(diǎn)的結(jié)構(gòu)數(shù)據(jù)類型。 ? 在創(chuàng)建的過(guò)程中，添加一個(gè)結(jié)點(diǎn)的時(shí)候要知道之前添加的那個(gè)結(jié)點(diǎn)，定義一個(gè)指針 q來(lái)指向之前添加的那個(gè)結(jié)點(diǎn)，即鏈表的最后一個(gè)結(jié)點(diǎn)，定義指針變量 p 指向當(dāng)前結(jié)點(diǎn)，q指針?biāo)附Y(jié)點(diǎn)為當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)， p就叫做 q的后繼。當(dāng)我們添加完成一個(gè)結(jié)點(diǎn)后，再將指針 q指向當(dāng)前鏈表的最后一個(gè)結(jié)點(diǎn)，為添加下一個(gè)結(jié)點(diǎn)作準(zhǔn)備。從 head開(kāi)始，通過(guò)各結(jié)點(diǎn)指針能夠訪問(wèn)到鏈表的每一個(gè)元素。鏈表的創(chuàng)建過(guò)程如圖 ： 圖 鏈表的創(chuàng)建過(guò)程 q … head NULL a1 head q head a1 a2 q NULL head a1 a2 a3 … an a2 pNew a3 pNew ? 如圖 ，鏈表創(chuàng)建的過(guò)程就像在穿一條珠鏈：有一根線頭能將整串珠鏈提起，稱頭指針 head。剛開(kāi)始時(shí)沒(méi)有任何珠子，只有一根空線頭 head；第一顆珠子（頭結(jié)點(diǎn)）接到 head上，而第一顆珠子后有一根線頭（指針域 next）可以接下一顆珠子；每次總把新加入的珠子 pNew（結(jié)點(diǎn)）接到最后一顆珠子后的線頭上。為了能快速找到最后一顆珠子，令指針 q指向每次最新接入的珠子 ,則新珠子接到 q的線頭上： qnext=pNew。當(dāng)不再需要接入其他珠子時(shí)，把最后一一顆珠子后的線頭qnext打上結(jié)： qnext=NULL。 ① 鏈表每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?qū)?yīng)著一條通信錄所包含的數(shù)據(jù)信息，可以是任意類型，用一個(gè)結(jié)構(gòu)體變量來(lái)表示，本例中包含聯(lián)系人的姓名和電話。為了把兩個(gè)結(jié)點(diǎn)連接起來(lái)，結(jié)點(diǎn)中還應(yīng)該有一個(gè)指向下一結(jié)點(diǎn)的指針域，這個(gè)指針指向結(jié)點(diǎn)自身的結(jié)構(gòu)類型，稱自引用結(jié)構(gòu)。 結(jié)點(diǎn)定義一般形式為： struct node { 數(shù)據(jù)類型 data。 /*數(shù)據(jù)域 */ struct node* next。 /*指針域 */ }。 如上例： struct NodeType { struct info data。 struct NodeType *next。 }。 ② 鏈表創(chuàng)建時(shí)設(shè)計(jì)為：當(dāng)輸入的聯(lián)系人姓名不為“ ”時(shí)都要插入新結(jié)點(diǎn)： 鏈表置空： head=NULL 當(dāng)輸入的聯(lián)系人姓名不為 “ ”時(shí) ， 循環(huán)：插入結(jié)點(diǎn) 設(shè)置尾結(jié)點(diǎn)： qnext=NULL 圖 “鏈表創(chuàng)建”的 PAD圖 ? 循環(huán)體中每插入一個(gè)結(jié)點(diǎn)需要做以下操作： 準(zhǔn)備新結(jié)點(diǎn) pNew：分配空間 ， 為新結(jié)點(diǎn)賦值 pNew插入鏈表 pNew成為新的尾結(jié)點(diǎn)： q=pNew 圖 “對(duì)鏈表插入一個(gè)結(jié)點(diǎn)”的 PAD圖 新結(jié)點(diǎn) pNew插入鏈表時(shí)有兩種情況：若鏈表為空，則放到 head后；否則，插入到尾結(jié)點(diǎn) q之后。 ③ 本例中創(chuàng)建鏈表時(shí)從鏈表尾一一插入結(jié)點(diǎn)，也可以從鏈表的頭部插入結(jié)點(diǎn)，即新結(jié)點(diǎn)pNew插入到 head之前： pNewnext=head。 head=pNew。 ④ 與數(shù)組不同，鏈表中每個(gè)元素的存儲(chǔ)空間都需要在使用前在程序中顯式地分配，并用指針指向所分配空間的首地址，用完以后再顯式地釋放每個(gè)元素占用的空間，需要?jiǎng)討B(tài)地分配和釋放內(nèi)存空間。 C語(yǔ)言庫(kù)函數(shù)中提供了兩個(gè)動(dòng)態(tài)分配和釋放內(nèi)存空間的函數(shù)： malloc()和 free()。在 Turbo C中的頭文件是 ，在 VC中是 。 malloc()函數(shù)的格式： void *malloc(size)。 malloc()函數(shù)用來(lái)分配 size個(gè)字節(jié)的存儲(chǔ)區(qū)域，返回一個(gè)指針，指向 void類型的存儲(chǔ)區(qū)首地址，在調(diào)用時(shí)，要使用強(qiáng)制類型轉(zhuǎn)換來(lái)保證賦值兼容。如： struct NodeType *p。 p=(struct NodeType *)malloc(sizeof(struct NodeType))。 free()函數(shù)的格式： void free(void *p)。 其中指針變量p指向要釋放的空間的首地址。 ⑤ 鏈表是在函數(shù) create( )中創(chuàng)建的，鏈表建立后head指向了頭結(jié)點(diǎn)，需要把頭結(jié)點(diǎn)的首地址帶回主調(diào)函數(shù)。因此，函數(shù)原型為 struct NodeType *create( )，并通過(guò) return head返回，即用返回值來(lái)實(shí)現(xiàn)信息傳遞。因?yàn)殒湵砜臻g的釋放是由程序來(lái)控制的，執(zhí)行 free(p)之前， p指向的空間都存在，因此在一個(gè)函數(shù)中分配的結(jié)點(diǎn)可以在另一個(gè)函數(shù)中使用。 create()函數(shù)的調(diào)用： int main( ) { …… head=create( )。 /* head指向鏈表的頭結(jié)點(diǎn) */ …… } ⑥ 也可以通過(guò)傳地址的方式來(lái)實(shí)現(xiàn)鏈表信息傳遞，此時(shí)傳遞的是指針變量 head的地址。 create( )函數(shù)中通過(guò) *phead直接修改主調(diào)函數(shù)中 head的指向，如圖 。 圖 通過(guò)傳地址方式傳遞鏈表頭指針 main( ) amp。head create( ) phead head ⑦ 在對(duì)鏈表遍歷的 void display( struct NodeType *head)中，由于遍歷時(shí)只需要通過(guò) head訪問(wèn)每一個(gè)結(jié)點(diǎn)，而不用改變鏈表頭指針的指向，因此單向傳遞指針變量 head即可如圖 ： 圖 通過(guò)傳值方式傳遞鏈表頭指針 main( ) display( ) head head ⑧ 單鏈表只能從鏈表頭 head開(kāi)始訪問(wèn)鏈表的各個(gè)結(jié)點(diǎn)，并且只有前一個(gè)結(jié)點(diǎn)的指針域才能找到后一個(gè)結(jié)點(diǎn)，因此 display()函數(shù)中遍歷鏈表時(shí)，指針 p從鏈表頭 head開(kāi)始，每訪問(wèn)過(guò)一個(gè)結(jié)點(diǎn)就讓 p指向下一個(gè)結(jié)點(diǎn) p=pnext，直到訪問(wèn)完最后一個(gè)結(jié)點(diǎn)，如圖 所示。 圖 通過(guò)指針 p遍歷鏈表各結(jié)點(diǎn) p head NULL p head NULL (a) p=head， 從頭開(kāi)始遍歷鏈表 (b) p=pnext， p指向下一個(gè)結(jié)點(diǎn) p head NULL (c) p==NULL時(shí)遍歷完鏈表 鏈表結(jié)點(diǎn)的查找 ? 由于單鏈表中結(jié)點(diǎn)只能通過(guò)前一個(gè)結(jié)點(diǎn)的指針域找到，有時(shí)得到結(jié)點(diǎn)的前驅(qū)比得到結(jié)點(diǎn)本身更重要。 【 例 72】 查找通信錄中第 i個(gè)結(jié)點(diǎn)及結(jié)點(diǎn)的前驅(qū) 【 分析 】 在數(shù)組中，通過(guò) arr[i]就可以引用第 i 個(gè)元素。 在鏈表中，結(jié)點(diǎn)間的順序關(guān)系是通過(guò)指針域維持的，不能由結(jié)點(diǎn)序號(hào) i直接得到對(duì)應(yīng)的結(jié)點(diǎn)，必須從頭結(jié)點(diǎn)開(kāi)始，沿著指針域的指向順序遍歷，直到找到第 i個(gè)結(jié)點(diǎn)為止。 【 程序 】 【 說(shuō)明 】 ? ① searchPre函數(shù)的算法思想，體現(xiàn)了鏈表操作的一般方法。對(duì)鏈表操作總是從頭開(kāi)始，由一個(gè)或兩個(gè)指針順序向后遍歷，直到找到目標(biāo)位置為止，如圖 。 p head NULL *pre NULL 圖 查找第 i個(gè)結(jié)點(diǎn)及其前驅(qū) (a) p=head， 從頭開(kāi)始查找 (b) *pre=p, p=pnext， *pre和 p一起后移 (d) p==NULL時(shí)遍歷完鏈表 ， 沒(méi)找到第 i個(gè)結(jié)點(diǎn) p head NULL *pre p head NULL *pre (c) 找到 ， p指向第 i個(gè)結(jié)點(diǎn) ， *pre指向 p的前驅(qū) p *pre head NULL ② 參數(shù)傳遞使用了 return語(yǔ)句和指針的地址傳遞，記住，不管是普通變量還是指針變量，只要希望子函數(shù)把結(jié)果帶回來(lái)，就傳送它的地址過(guò)去，否則傳值過(guò)去。 ③ 本章中后面的幾個(gè)例題中涉及到鏈表操作的，都需要加上鏈表結(jié)點(diǎn)的定義、鏈表的創(chuàng)建函數(shù)、遍歷函數(shù)及相應(yīng)的主函數(shù)后才能上機(jī)運(yùn)行。 【 例 73】 已知某結(jié)點(diǎn)的地址，來(lái)查找這個(gè)結(jié)點(diǎn)的前驅(qū) 【 分析 】 結(jié)點(diǎn)的指針 p已知 ,要找它的前驅(qū)結(jié)點(diǎn)。仍然只能從鏈表頭結(jié)點(diǎn)開(kāi)始順序往后查找，直到找到某個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)為 p結(jié)點(diǎn)，則它就是結(jié)點(diǎn) p的前驅(qū)了。 【 程序 】 struct NodeType *searchPre2(struct NodeType *head,struct NodeType *p) /*p為待查找結(jié)點(diǎn)的地址 */ { struct NodeType *q。 q=head。 while(q amp。amp。 qnext!=p) /*當(dāng)未查找到該結(jié)點(diǎn)且鏈表沒(méi)有結(jié)束 */ q=qnext。 /*指針后移 */ return q。 } 【 例 74】 已知結(jié)點(diǎn)中關(guān)鍵字的值，查找這個(gè)結(jié)點(diǎn)。 【 分析 】 通信錄的數(shù)據(jù)域是一個(gè)結(jié)構(gòu)體，里面包含了姓名和電話號(hào)碼信息?？梢愿鶕?jù)姓名查找，也可以根據(jù)電話號(hào)碼查找。仍需要從鏈表的頭結(jié)點(diǎn)開(kāi)始，依次檢索。本題查找與姓名匹配的結(jié)點(diǎn)