【正文】 6 1 2 4 5 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 2 4 5 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 2 4 5 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 2 4 5 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 2 4 5 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 2 4 5 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 5 2 4 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 5 2 4 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 5 2 4 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 5 2 4 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 5 2 4 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 5 2 4 7 8 圖 猴子選大王 猴子出圈的順序： 3 6 1 5 2 8 4 7 圖 猴子選大王 猴子出圈的順序： 3 6 1 5 2 8 7 4 圖 猴子選大王 猴子出圈的順序： 3 6 1 5 2 8 7 4 圖 猴子選大王 猴子出圈的順序： 3 6 1 5 2 8 4 7 猴子選大王的過(guò)程中，需要將其他的 n1個(gè)猴子從圈中刪除。 4號(hào)接著從1開(kāi)始報(bào)數(shù)， 5號(hào)數(shù) 2， 6號(hào)出圈。 給一群猴子都做了編號(hào)，編號(hào)是 1， 2， 3 ...n ,這群猴子（ n個(gè)）按照 1~n的順序圍坐一圈，從第 1開(kāi)始數(shù)，每數(shù)到第 m個(gè)，該猴子就要離開(kāi)此圈，這樣依次下來(lái)，直到圈中只剩一只猴子，最后出圈的即為大王。 ② 鏈表能夠方便地實(shí)現(xiàn)結(jié)點(diǎn)的插入和刪除操作，這是鏈表結(jié)構(gòu)具有動(dòng)態(tài)分配存儲(chǔ)空間的體現(xiàn)，是它優(yōu)于數(shù)組的地方之一。 【 程序 】 【 說(shuō)明 】 ① 鏈表常用于保存非連續(xù)存儲(chǔ)線性結(jié)構(gòu)的數(shù)據(jù)，其優(yōu)點(diǎn)在于能夠方便地進(jìn)行數(shù)據(jù)元素的插入和刪除。 【 分析 】 從鏈表的頭結(jié)點(diǎn)開(kāi)始查找，找到與 name匹配的記錄，然后刪除。但這是有代價(jià)的，鏈表操作中需要先建立鏈表；而且每個(gè)結(jié)點(diǎn)都要保存后繼結(jié)點(diǎn)的地址，這需要額外的存儲(chǔ)空間。 【 程序 】 【 說(shuō)明 】 對(duì)于插入 /刪除操作頻繁的情況，鏈表的插入 /刪除算法簡(jiǎn)單，僅僅修改幾個(gè)指針變量的指向即可；而且，插入 /刪除操作的代價(jià)低，僅需為幾個(gè)指針變量賦地址，相當(dāng)于整數(shù)賦值的代價(jià)。 ? 和插入一樣，刪除時(shí)也要區(qū)分：刪除的是頭結(jié)點(diǎn)，還是一般結(jié)點(diǎn)。 free(p)。題目要求的是刪除第 i個(gè)結(jié)點(diǎn)，關(guān)鍵是要找到第 i－ 1個(gè)結(jié)點(diǎn)，可以調(diào)用例 72的 searchPre()函數(shù)。 【 例 77】 從通信錄中刪除第 i個(gè)記錄。 鏈表結(jié)點(diǎn)的刪除 ? 在數(shù)組操作中，無(wú)論是插入元素還是刪除元素都有大量的數(shù)據(jù)需要移動(dòng)，以保持?jǐn)?shù)組元素的物理順序和邏輯順序的一致性，但在鏈表中卻不用做那么多的工作，刪除鏈表結(jié)點(diǎn)只要對(duì)個(gè)別結(jié)點(diǎn)的指針做一些調(diào)整即可。在鏈表中插入結(jié)點(diǎn)，就是改變鏈表相關(guān)結(jié)點(diǎn)之間的鏈接關(guān)系，但要注意區(qū)分：結(jié)點(diǎn)插在頭結(jié)點(diǎn)前時(shí)，會(huì)改變頭指針的指向；插在其他位置則不改變頭指針的指向。因?yàn)樵诓迦氲倪^(guò)程中，頭結(jié)點(diǎn)有可能改變，所以函數(shù)間傳遞的參數(shù)應(yīng)該為鏈表頭指針的地址。 【 分析 】 此時(shí)新結(jié)點(diǎn)要插入到 pre與 p之間，如圖 所示，用 searchPre函數(shù)查找出的節(jié)點(diǎn)便成為了要插入結(jié)點(diǎn)的后繼結(jié)點(diǎn)。本例中， s要插入到 p之后，找到 p即可，而pre作為 p的前驅(qū)并沒(méi)有用到。 插入一個(gè)結(jié)點(diǎn)的關(guān)鍵是要查找到該結(jié)點(diǎn)的前驅(qū)，這樣才便于操作，所以還需要調(diào)用查找函數(shù) searchPre( )。 pnext=s。 s p NULL ① ② 圖 在 p之后插入結(jié)點(diǎn) head 從圖中可以看出，插入一個(gè)元素只需要修改兩個(gè)指針即可。 【 分析 】 在第 i個(gè)記錄后插入一個(gè)記錄，即在第 i+1個(gè)位置插入新結(jié)點(diǎn)，如圖 ，此時(shí)新結(jié)點(diǎn)要插入到 p之后，與數(shù)組元素的插入不同，數(shù)組元素是連續(xù)存放的，插入元素前，其后的元素都要后移。 ? 插入結(jié)點(diǎn)時(shí)要保證不破壞鏈表原來(lái)的連接關(guān)系，并且先要找到結(jié)點(diǎn)該放的位置。 } 鏈表結(jié)點(diǎn)的插入 ? 使用鏈表存儲(chǔ)數(shù)據(jù)的一個(gè)重要原因是：結(jié)點(diǎn)的插入和刪除效率高，只需要改變幾個(gè)指針變量的指向就可以了。 /*記下前驅(qū) */ p=pnext。amp。 q=NULL。 【 程序 】 struct NodeType * searchPre3(struct NodeType * head,char name[20]) { struct NodeType * p,*q。仍需要從鏈表的頭結(jié)點(diǎn)開(kāi)始，依次檢索。 【 分析 】 通信錄的數(shù)據(jù)域是一個(gè)結(jié)構(gòu)體，里面包含了姓名和電話號(hào)碼信息。 /*指針后移 */ return q。amp。 q=head。仍然只能從鏈表頭結(jié)點(diǎn)開(kāi)始順序往后查找，直到找到某個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)為 p結(jié)點(diǎn)，則它就是結(jié)點(diǎn) p的前驅(qū)了。 ③ 本章中后面的幾個(gè)例題中涉及到鏈表操作的，都需要加上鏈表結(jié)點(diǎn)的定義、鏈表的創(chuàng)建函數(shù)、遍歷函數(shù)及相應(yīng)的主函數(shù)后才能上機(jī)運(yùn)行。對(duì)鏈表操作總是從頭開(kāi)始，由一個(gè)或兩個(gè)指針順序向后遍歷，直到找到目標(biāo)位置為止，如圖 。 在鏈表中，結(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)為止。 圖 通過(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)本身更重要。 圖 通過(guò)傳地址方式傳遞鏈表頭指針 main( ) amp。 /* head指向鏈表的頭結(jié)點(diǎn) */ …… } ⑥ 也可以通過(guò)傳地址的方式來(lái)實(shí)現(xiàn)鏈表信息傳遞，此時(shí)傳遞的是指針變量 head的地址。因?yàn)殒湵砜臻g的釋放是由程序來(lái)控制的，執(zhí)行 free(p)之前， p指向的空間都存在，因此在一個(gè)函數(shù)中分配的結(jié)點(diǎn)可以在另一個(gè)函數(shù)中使用。 ⑤ 鏈表是在函數(shù) create( )中創(chuàng)建的，鏈表建立后head指向了頭結(jié)點(diǎn)，需要把頭結(jié)點(diǎn)的首地址帶回主調(diào)函數(shù)。 free()函數(shù)的格式： void free(void *p)。如： struct NodeType *p。 malloc()函數(shù)的格式： void *malloc(size)。 C語(yǔ)言庫(kù)函數(shù)中提供了兩個(gè)動(dòng)態(tài)分配和釋放內(nèi)存空間的函數(shù)： malloc()和 free()。 head=pNew。 ② 鏈表創(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之后。 struct NodeType *next。 /*指針域 */ }。 結(jié)點(diǎn)定義一般形式為： struct node { 數(shù)據(jù)類型 data。 ① 鏈表每個(gè)結(jié)點(diǎn)的數(shù)據(jù)域?qū)?yīng)著一條通信錄所包含的數(shù)據(jù)信息，可以是任意類型，用一個(gè)結(jié)構(gòu)體變量來(lái)表示，本例中包含聯(lián)系人的姓名和電話。為了能快速找到最后一顆珠子，令指針 q指向每次最新接入的珠子 ,則新珠子接到 q的線頭上： qnext=pNew。鏈表的創(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。當(dāng)我們添加完成一個(gè)結(jié)點(diǎn)后，再將指針 q指向當(dāng)前鏈表的最后一個(gè)結(jié)點(diǎn)，為添加下一個(gè)結(jié)點(diǎn)作準(zhǔ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ù)類型。為了方便查找和更新，經(jīng)常要對(duì)通信錄中添加新的記錄、刪除無(wú)效記錄和調(diào)整記錄位置，用鏈表來(lái)實(shí)現(xiàn)通信錄的管理比較方便。 【 例 71】 用鏈表實(shí)現(xiàn)通信錄的管理。此處以不帶頭結(jié)點(diǎn)的單鏈表為例講解鏈表的基本操作。不帶頭結(jié)點(diǎn)的單鏈表頭指針 head直接指向鏈表的第一個(gè)結(jié)點(diǎn)，而帶頭結(jié)點(diǎn)的單鏈表頭指針head則指向一個(gè)附加的結(jié)點(diǎn)，這個(gè)附加結(jié)點(diǎn)的指針域才指向鏈表的第一個(gè)結(jié)點(diǎn)。常見(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é)束。所以，有必要定義一個(gè)頭指針來(lái)指向鏈表的第一個(gè)元素。每個(gè)元素都有一個(gè)指針指向下一個(gè)元素，如此環(huán)環(huán)相扣下去，就組成了一個(gè)鏈表。鏈表不要求兩個(gè)元素在物理上相鄰，元素的物理順序與邏輯順序可以不同，只要在元素結(jié)構(gòu)中加一個(gè)指針項(xiàng)，用來(lái)指向下一個(gè)元素的地址便可。如圖 所示。而厚厚的一本書中，讀者又怎樣找到文章 a呢？翻翻目錄就知道了，那里有文章 a所在頁(yè)碼的信息。通過(guò)這個(gè)線索， 。由于文章 a在排版時(shí)被分成了不連續(xù)的兩塊，讀者怎樣才能找到第二個(gè)邏輯塊呢？編輯在“下接 XX頁(yè)”，讀者順著這個(gè)線索很容易就找到了 。《 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)去。如此一來(lái)， ，還有指示下一個(gè)邏輯塊在哪里的線索。 ? 那么，讀者又是怎么知道 有沒(méi)有另外一個(gè)邏輯塊呢？其實(shí)每種雜志的每篇文章的最后都有一個(gè)特殊的符號(hào)，讀者看到這個(gè)符號(hào)就知道這已經(jīng)是最后一個(gè)邏輯塊了。 圖 兩個(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ù)。 ? 組成鏈表的基本單元是結(jié)點(diǎn)，所謂結(jié)點(diǎn)至少由 2個(gè)域組成，一個(gè)是數(shù)據(jù)域，一個(gè)是指針域，數(shù)據(jù)域存儲(chǔ)結(jié)點(diǎn)本身的信息，指針域指向后繼結(jié)點(diǎn)。 ? 鏈表的第一個(gè)結(jié)點(diǎn)也代表著這個(gè)鏈表的起始元素，通過(guò)這個(gè)結(jié)點(diǎn)的指針，可以一直訪問(wèn)完鏈表。尾結(jié)點(diǎn)的指針域置為“ NULL（空）”，作為鏈表結(jié)束的