【正文】 ? ⑴ p=head； ? ⑵ 當(dāng) p≠NULL時(shí)，若 pdata==m，則找到要求結(jié)點(diǎn)，查找結(jié)束，返回結(jié)點(diǎn)地址 p；否則，執(zhí)行下一步⑶；當(dāng) p== NULL時(shí)，鏈表中不存在要找的結(jié)點(diǎn)，查找結(jié)束，返回空指針 NULL； ? ⑶ p=pnext,轉(zhuǎn)步驟⑵。 鏈表結(jié)點(diǎn)的查找 ?查找函數(shù) find() struct node *find(struct node *head,int m) { struct node *p=head。 while(p!=NULLamp。amp。pdata!=m) p=pnext。 if(p==NULL) return(NULL) else return(p)。 } 鏈表結(jié)點(diǎn)的查找 例 88 對圖示的 head鏈表，刪除其值是 x的結(jié)點(diǎn)。具體要求： ⑴ 輸出被刪除結(jié)點(diǎn)的值； ⑵ 當(dāng)指定值結(jié)點(diǎn)不存在時(shí)，顯示一個(gè)提示信息； ⑶ x的值由鍵盤輸入。 程序 d a t a 1 d a t a 2 d a t a 3 d a t a n ∧. . .h e a d?分析 該問題的關(guān)鍵點(diǎn)有兩點(diǎn)： ?查找 data等于 x的結(jié)點(diǎn) p； ?刪除 p結(jié)點(diǎn)。 結(jié)構(gòu)體應(yīng)用舉例 ? 字符串加密 ? 學(xué)生成績排序 ? Josephus問題 字符串加密 例 89 將輸入的一個(gè)字符串加密后輸出，加密表中未出現(xiàn)的源字符原樣輸出。 源字符 加密后字符 源字符 加密后字符 a f b g w d f 9 v * x s m 3 h k p t u ? ?1．問題分析與算法設(shè)計(jì) ⑴ 設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)存儲字母加密對照表。 struct table { char input。 char output。 }。 ⑵ 定義 struct table型數(shù)組用于存儲密碼表。 ⑶ 輸入一個(gè)字符串，在密碼表的 input成員中查找每一個(gè)輸入的字符，查找成功后使用對應(yīng)的 output成員加密輸出，否則，原樣輸出源字符。 ?2．實(shí)現(xiàn)程序 include struct table { char input。 /* 存儲輸入的源字符 */ char output。 /* 存儲加密后的字符 */ }。 int main( ) { char ch。 int length,i。 struct table encrypt[10]= {39。a39。,39。f39。,39。b39。,39。g39。,39。w39。,39。d39。,39。f39。,39。939。,39。v39。,39。*39。,39。x39。,39。s39。,39。m39。,39。339。, 39。h39。,39。k39。,39。p39。,39。t39。,39。u39。,39。?39。 }。 while((ch=getchar())!=39。\n39。) { for(i=0。encrypt[i].input!=champ。amp。i10。i++)。 if(i10) putchar(encrypt[i].output)。 else putchar (ch)。 } return 0。 } 學(xué)生成績排序 例 810 用結(jié)構(gòu)體表示學(xué)生的姓名和成績，編寫程序，對一個(gè)班級的學(xué)生信息按成績進(jìn)行降序排序，并輸出結(jié)果。 ?問題分析與算法設(shè)計(jì) ⑴ 定義結(jié)構(gòu)體數(shù)據(jù)類型。 struct stu_info { char name[20]。 int score。 }； ⑵ 定義 struct stu_info類型的結(jié)構(gòu)體數(shù)組 stu用于存儲一個(gè)班級的學(xué)生數(shù)據(jù)。 ⑶ 定義學(xué)生數(shù)據(jù)輸入函數(shù) input()，用于建立結(jié)構(gòu)體數(shù)組 stu。 ⑷ 定義學(xué)生數(shù)據(jù)輸出函數(shù) output()，用于輸出數(shù)組 stu。 ⑸ 定義排序函數(shù) sort_stu()，用于對 stu數(shù)組排序，排序方法選用冒泡排序法。 ⑹ 在主函數(shù)中調(diào)用 input()函數(shù)、調(diào)用 sort_stu()函數(shù)、調(diào)用 output()函數(shù)。 ?程序?qū)崿F(xiàn) ⑴ 建立 head為頭指針的循環(huán)鏈表。 ⑵ 設(shè)置 p指針，其初值為 head。 ⑶ 對 p指向的結(jié)點(diǎn)從 1開始報(bào)數(shù)，每數(shù)一個(gè)結(jié)點(diǎn)后， p指針便沿指針鏈下移一個(gè)位置（ p=pnext），指向下一個(gè)結(jié)點(diǎn)。 當(dāng) p指向的結(jié)點(diǎn)數(shù)到 m時(shí)，輸出該結(jié)點(diǎn)的值并將其從鏈表中刪除（出列），這時(shí)使 p指向下一個(gè)結(jié)點(diǎn)，然后從 1開始重新報(bào)數(shù)。當(dāng)鏈表中只有一個(gè)結(jié)點(diǎn)時(shí)，報(bào)數(shù)結(jié)束，輸出該結(jié)點(diǎn)。 Josephus問題 例 811 Josephus問題。有 n個(gè)人圍成一圈，從 1開始順序編號到 n，現(xiàn)在從 1號開始順時(shí)針從 1數(shù)數(shù)，數(shù)到 m者自動出列，然后從下一個(gè)人開始重新數(shù)數(shù)，仍然每次數(shù)到 m者自動出列。給出這 n個(gè)人出列的順序。 ?問題分析與算法設(shè)計(jì) . . .h e a d1 2 3 4 n? 實(shí)現(xiàn)程序 小 結(jié) (1) (1) 結(jié)構(gòu)體數(shù)據(jù)類型不是系統(tǒng)固有的，它需要在程序中先行定義，然后才能使用。 (2) 結(jié)構(gòu)體變量的定義有 3種方法：先定義結(jié)構(gòu)體類型，再定義結(jié)構(gòu)體變量；在定義結(jié)構(gòu)體類型的同時(shí)定義結(jié)構(gòu)體變量；不定義結(jié)構(gòu)體類型名，直接定義結(jié)構(gòu)體類型變量。 (3) 引用結(jié)構(gòu)體成員的方法主要有兩種：使用結(jié)構(gòu)體變量名引用結(jié)構(gòu)體成員；通過指向結(jié)構(gòu)體變量的指針引用結(jié)構(gòu)體成員。 4．?dāng)?shù)組元素是結(jié)構(gòu)體類型的數(shù)組，稱為結(jié)構(gòu)體數(shù)組，結(jié)構(gòu)體數(shù)組具有數(shù)組的一切性質(zhì)。 (4) 指向結(jié)構(gòu)體變量的指針，稱為結(jié)構(gòu)體指針，結(jié)構(gòu)體指針既可以指向單一的結(jié)構(gòu)體變量，也可以指向結(jié)構(gòu)體數(shù)組變量，結(jié)構(gòu)體指針也可以作函數(shù)的參數(shù)。使用結(jié)構(gòu)體指針作函數(shù)的實(shí)參時(shí)，實(shí)參和形參必須是同一種結(jié)構(gòu)體類型。 小 結(jié) (2) (6) 鏈表是一種動態(tài)的數(shù)據(jù)存儲結(jié)構(gòu)，它的每一個(gè)結(jié)點(diǎn)都是結(jié)構(gòu)體類型的數(shù)據(jù)，同一個(gè)鏈表中的所有結(jié)點(diǎn)具有相同的數(shù)據(jù)類型。一個(gè)鏈表結(jié)點(diǎn)包括數(shù)據(jù)域和指針域兩部分，數(shù)據(jù)域存儲需要處理的數(shù)據(jù)，指針域存儲下一個(gè)結(jié)點(diǎn)的位置。 C語言使用動態(tài)內(nèi)存管理函數(shù)為鏈表申請結(jié)點(diǎn)空間。 (7) 鏈表的基本操作有插入結(jié)點(diǎn)、刪除結(jié)點(diǎn)、查找結(jié)點(diǎn)、結(jié)點(diǎn)數(shù)據(jù)讀寫等，向鏈表插入結(jié)點(diǎn)前必須先用動態(tài)內(nèi)存分配函數(shù)獲得存儲空間，從鏈表中刪除的結(jié)點(diǎn)要進(jìn)行釋放操作。 (8) 從空鏈表開始不斷地插入結(jié)點(diǎn)即可建立一個(gè)鏈表，任何一個(gè)鏈表必須有一個(gè)頭指針，只有通過頭指針才能訪問鏈表結(jié)點(diǎn)。當(dāng)一個(gè)鏈表結(jié)點(diǎn)的指針域?yàn)榭諘r(shí)，表明是鏈表的最后一個(gè)結(jié)點(diǎn)，當(dāng)最后一個(gè)結(jié)點(diǎn)的指針指向開頭結(jié)點(diǎn)時(shí)，便形成一個(gè)循環(huán)鏈表。