【正文】 標(biāo)志。圖中所示鏈表有 4個(gè)結(jié)點(diǎn)，ai表示數(shù)據(jù)部分，可以是基本類型或構(gòu)造類型的數(shù)據(jù)。由于這個(gè)附加結(jié)點(diǎn)的存在，無(wú)論怎么操作鏈表，頭指針的指向總是不變。所謂單鏈表就是每個(gè)結(jié)點(diǎn)只有一個(gè)指針域。 【 分析 】 通信錄中每個(gè)聯(lián)系人的信息，一般應(yīng)該包括姓名、電話號(hào)碼和其他一些信息。 ? 鏈表的每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?qū)?yīng)著一條通信錄所包含的數(shù)據(jù)信息，用一個(gè)結(jié)構(gòu)體變量來(lái)表示，例子中包含聯(lián)系人的姓名和電話。 ? 在創(chuàng)建的過程中，添加一個(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的后繼。從 head開始，通過各結(jié)點(diǎn)指針能夠訪問到鏈表的每一個(gè)元素。剛開始時(shí)沒有任何珠子，只有一根空線頭 head；第一顆珠子（頭結(jié)點(diǎn)）接到 head上，而第一顆珠子后有一根線頭（指針域 next）可以接下一顆珠子；每次總把新加入的珠子 pNew（結(jié)點(diǎn)）接到最后一顆珠子后的線頭上。當(dāng)不再需要接入其他珠子時(shí)，把最后一一顆珠子后的線頭qnext打上結(jié)： qnext=NULL。為了把兩個(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)。 /*數(shù)據(jù)域 */ struct node* next。 如上例： struct NodeType { struct info data。 }。 ③ 本例中創(chuàng)建鏈表時(shí)從鏈表尾一一插入結(jié)點(diǎn)，也可以從鏈表的頭部插入結(jié)點(diǎn)，即新結(jié)點(diǎn)pNew插入到 head之前： pNewnext=head。 ④ 與數(shù)組不同，鏈表中每個(gè)元素的存儲(chǔ)空間都需要在使用前在程序中顯式地分配，并用指針指向所分配空間的首地址，用完以后再顯式地釋放每個(gè)元素占用的空間，需要?jiǎng)討B(tài)地分配和釋放內(nèi)存空間。在 Turbo C中的頭文件是 ，在 VC中是 。 malloc()函數(shù)用來(lái)分配 size個(gè)字節(jié)的存儲(chǔ)區(qū)域，返回一個(gè)指針，指向 void類型的存儲(chǔ)區(qū)首地址，在調(diào)用時(shí)，要使用強(qiáng)制類型轉(zhuǎn)換來(lái)保證賦值兼容。 p=(struct NodeType *)malloc(sizeof(struct NodeType))。 其中指針變量p指向要釋放的空間的首地址。因此，函數(shù)原型為 struct NodeType *create( )，并通過 return head返回，即用返回值來(lái)實(shí)現(xiàn)信息傳遞。 create()函數(shù)的調(diào)用： int main( ) { …… head=create( )。 create( )函數(shù)中通過 *phead直接修改主調(diào)函數(shù)中 head的指向，如圖 。head create( ) phead head ⑦ 在對(duì)鏈表遍歷的 void display( struct NodeType *head)中，由于遍歷時(shí)只需要通過 head訪問每一個(gè)結(jié)點(diǎn)，而不用改變鏈表頭指針的指向，因此單向傳遞指針變量 head即可如圖 ： 圖 通過傳值方式傳遞鏈表頭指針 main( ) display( ) head head ⑧ 單鏈表只能從鏈表頭 head開始訪問鏈表的各個(gè)結(jié)點(diǎn)，并且只有前一個(gè)結(jié)點(diǎn)的指針域才能找到后一個(gè)結(jié)點(diǎn)，因此 display()函數(shù)中遍歷鏈表時(shí)，指針 p從鏈表頭 head開始，每訪問過一個(gè)結(jié)點(diǎn)就讓 p指向下一個(gè)結(jié)點(diǎn) p=pnext，直到訪問完最后一個(gè)結(jié)點(diǎn)，如圖 所示。 【 例 72】 查找通信錄中第 i個(gè)結(jié)點(diǎn)及結(jié)點(diǎn)的前驅(qū) 【 分析 】 在數(shù)組中，通過 arr[i]就可以引用第 i 個(gè)元素。 【 程序 】 【 說(shuō)明 】 ? ① searchPre函數(shù)的算法思想，體現(xiàn)了鏈表操作的一般方法。 p head NULL *pre NULL 圖 查找第 i個(gè)結(jié)點(diǎn)及其前驅(qū) (a) p=head， 從頭開始查找 (b) *pre=p, p=pnext， *pre和 p一起后移 (d) p==NULL時(shí)遍歷完鏈表 ， 沒找到第 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)，就傳送它的地址過去，否則傳值過去。 【 例 73】 已知某結(jié)點(diǎn)的地址，來(lái)查找這個(gè)結(jié)點(diǎn)的前驅(qū) 【 分析 】 結(jié)點(diǎn)的指針 p已知 ,要找它的前驅(qū)結(jié)點(diǎn)。 【 程序 】 struct NodeType *searchPre2(struct NodeType *head,struct NodeType *p) /*p為待查找結(jié)點(diǎn)的地址 */ { struct NodeType *q。 while(q amp。 qnext!=p) /*當(dāng)未查找到該結(jié)點(diǎn)且鏈表沒有結(jié)束 */ q=qnext。 } 【 例 74】 已知結(jié)點(diǎn)中關(guān)鍵字的值，查找這個(gè)結(jié)點(diǎn)?？梢愿鶕?jù)姓名查找，也可以根據(jù)電話號(hào)碼查找。本題查找與姓名匹配的結(jié)點(diǎn)。 p=head。 while(p amp。 strcmp(p,name)!=0) /*當(dāng)鏈表沒有結(jié)束并且沒有查找到匹配的姓名信息 */ { q=p。 /*指針后移 */ } return q。但鏈表有創(chuàng)建和銷毀的代價(jià)。 【 例 75】 在通信錄中第 i個(gè)記錄之后插入一個(gè)記錄。而在鏈表結(jié)構(gòu)中實(shí)現(xiàn)結(jié)點(diǎn)的插入比較簡(jiǎn)單。在結(jié)點(diǎn) p之后插入結(jié)點(diǎn) s的語(yǔ)句為： {snext=pnext 。} 注意：這兩個(gè)語(yǔ)句的順序是不能顛倒的。 【 說(shuō)明 】 單鏈表的操作中，由于每個(gè)結(jié)點(diǎn)只知道其直接后繼，因此記錄結(jié)點(diǎn)的前驅(qū)尤為重要。 例 76】 在通信錄中第 i個(gè)位置前插入一個(gè)記錄。 s pre p NULL head ① ② 圖 在 p之前插入結(jié)點(diǎn) 與在第 i個(gè)結(jié)點(diǎn)后的插入不同的是：當(dāng) i==1時(shí)，頭結(jié)點(diǎn)發(fā)生改變，插入結(jié)點(diǎn)變?yōu)轭^結(jié)點(diǎn)。如： void insert2(struct NodeType **head,int i,struct info a) 【 說(shuō)明 】 修改指針時(shí)，不能切斷鏈表的鏈接。 對(duì)于鏈表的操作，最好能夠畫出示意圖來(lái)幫助理解。 ? 刪除結(jié)點(diǎn)時(shí)要保證不破壞鏈表原來(lái)的連接關(guān)系，并且先要找到結(jié)點(diǎn)的前驅(qū)。 【 分析 】 鏈表元素的刪除與鏈表中插入結(jié)點(diǎn)類似，關(guān)鍵是要找到待刪除結(jié)點(diǎn)前驅(qū)結(jié)點(diǎn)。 s p pre NULL head 圖 鏈表結(jié)點(diǎn)的刪除 ? 由圖 ，刪除結(jié)點(diǎn)的語(yǔ)句為： ? { prenext=s。 }； ? 要養(yǎng)成一個(gè)良好的習(xí)慣：鏈表結(jié)點(diǎn)刪除后，用 free()釋放該結(jié)點(diǎn)占用的內(nèi)存空間。若是刪除的是頭結(jié)點(diǎn)則會(huì)改變頭指針的指向。尤其當(dāng)鏈表結(jié)點(diǎn)為大對(duì)象時(shí)，后一點(diǎn)更為明顯。 【 例 78 】 從通信錄中刪除姓名為 name的記錄。當(dāng)然，也可以按照電話號(hào)碼來(lái)刪除，與前例一樣，關(guān)鍵是找到待刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。在一個(gè)鏈表中插入一個(gè)結(jié)點(diǎn)或刪除一個(gè)結(jié)點(diǎn)，關(guān)鍵是要得到結(jié)點(diǎn)及前趨結(jié)點(diǎn)的指針，然后改變鏈表中結(jié)點(diǎn)的鏈接關(guān)系即可完成。 循環(huán)鏈表 【 例 79】 猴子選大王。 【 分析 】 以 n=8,m=3為例，猴子選大王的過程如圖 ：從 1號(hào)開始報(bào)數(shù)，數(shù)到 3時(shí)， 3號(hào)出圈。 7號(hào)接著從 1開始報(bào)數(shù)， 8號(hào)數(shù) 2，由于是一個(gè)圈， 1號(hào)接著數(shù) 3并出圈 ......如此下去，直到圈中只剩下一只猴子 7號(hào)，它就是要找的猴王。由于有大量的刪除，采用單鏈表存儲(chǔ)每個(gè)猴子數(shù)據(jù)。猴子選大王的過程就是循環(huán)鏈表的結(jié)點(diǎn)不斷被刪除的過程。當(dāng)圈中只剩下一個(gè)結(jié)點(diǎn)： prenext==pre時(shí)，pre就是要找的猴王。剛開始報(bào)數(shù)時(shí) p從頭結(jié)點(diǎn)開始，所以先讓 pre指向鏈表的最后一個(gè)結(jié)點(diǎn)。 。例如，第一次報(bào)數(shù)時(shí)， pre指向最后一個(gè)結(jié)點(diǎn)， p從 prenext開始，也就是從第一個(gè)結(jié)點(diǎn)開始報(bào)數(shù)。 當(dāng)報(bào)數(shù)計(jì)數(shù)到 m時(shí)即找到了要出圈的猴子 p，輸出 p的信息，并將 p從鏈表中刪除即可。從鏈表頭開始，沿著指向后繼結(jié)點(diǎn)的指針達(dá)到某個(gè)結(jié)點(diǎn)之后，可以從它開始遍歷鏈表的后面部分，而它的前面部分，除非仍從頭開始，否則不可能找到它們。在單鏈表中，將終端結(jié)點(diǎn)的指針域由 NULL改為指向表頭結(jié)點(diǎn)即可構(gòu)成單循環(huán)鏈表。在循環(huán)單鏈表中，從任一結(jié)點(diǎn)出發(fā)都可訪問到表中所有結(jié)點(diǎn)。 第 8章 綜合應(yīng)用 本章要點(diǎn) ? ：打開問題的缺口 – – 減少窮舉量，提高窮舉效率 – 局部窮舉 ? ：系統(tǒng)地搜索問題的解 ? ：簡(jiǎn)單通信錄管理 ? 本章小結(jié) ? 習(xí)題 8 ? 窮舉法（也稱枚舉法）：將所有的可能狀態(tài)列舉出來(lái)，然后逐一檢驗(yàn)是否是滿足條件，從而判斷哪些是需要的解，哪些不是 ? 運(yùn)用窮舉法的條件： – (1) 可以預(yù)先確定每種狀態(tài)下的元素個(gè)數(shù) n – (2) 每種狀態(tài)下元素 的可能值為一個(gè)連續(xù)的值域。 a1a1max。 a2a2max。 aiaimax。 ananmax。你能算出原來(lái)有幾個(gè)面包嗎？ 分面包 分析 ? (1) 窮舉變量及窮舉范圍 – 直接枚舉所問的 面包總數(shù) n： ? (2) 應(yīng)滿足的條件 – A分得的面包數(shù)： a=n*+ – B分得的面包數(shù)： b=(na)*+ – C分得的面包數(shù)： c=(nab)*+ – 三人 剛好分完所有面包 ，則 n為滿足要求的最小整數(shù) ? (3) 重要變量用途說(shuō)明 – int n。 A、 B、 C每人分得的面包數(shù) 0n a b c? ? ? ?1~?/*主要功能：窮舉算法，分面包 */ include include int main( ) { int n=1。 while(1) { a=n*+。 c=(nab)*+。 n++。 return 0。 break語(yǔ)句在該循環(huán)結(jié)構(gòu)中起了什么作用？ ? 修改程序，使控制循環(huán)在執(zhí)行指定次數(shù)（如 10000次，或更大的數(shù)）后結(jié)束，看看還能得到什么結(jié)果？把 n定義為 short類型后再試試。請(qǐng)上機(jī)實(shí)現(xiàn)，并比較兩種實(shí)現(xiàn)方式的不同。凡百錢買百雞，問雞翁、母、雛各幾何？ 窮舉變量及窮舉范圍 ? 直接枚舉所問的 公雞、母雞、小雞只數(shù)cock, hen, chick。 /*主要功能：窮舉算法，百錢買百雞 */ include int main( ) { int cock,hen,chick。 for(cock=0。 cock++) { maxhen=(100cock*5)/3。 hen= maxhen。 if((chick%3==0) amp。 (5*cock+3*hen+chick/3==100)) printf(100錢買公雞 %d只 ,母雞 %d只 ,小雞 %d只 \n, cock, hen, chick)。 } 【 例 83】 選人方案 ? 班上要在 A, B, C, D, E, F 6名同學(xué)中選派若干人去參加比賽，綜合比較各人的情況，得出選擇的條件如下： – E和 F兩人中至少去一個(gè)； – C和 D兩人中去一個(gè)； – D和 E要么都去，要么都不去； – A,B,F三人中要去兩個(gè)； –若 C不去，則 B也不去； – C和 F不能一起去。amp。amp。這兩種可能性是或的關(guān)系 – c2 = (c amp。 !d) || (d amp。 !c) ? 條件 c3： D和 E要么都去，要么都不去 ? 可能是“ A和 B去（ a amp。 b）” ，或“ A和 F去（ aamp。 f）” ，或“ B和 F去（ b amp。 f）” 。amp。amp。amp。amp。amp。amp。amp。amp。amp。amp。amp。amp。 窮舉變量，取值為 0或 1，表示 6個(gè)人