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