數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)全集

1、共享知識(shí)分享快樂盛年不重來，一日難再晨。及時(shí)宜自勉，歲月不待人。數(shù)據(jù)結(jié)構(gòu) 實(shí)踐教程卑微如螻蟻、堅(jiān)強(qiáng)似大象、八,、刖言數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)專業(yè)的必修。主干課程之一，它旨在使讀者學(xué)會(huì)分析研究數(shù)據(jù)對象的特性，學(xué)會(huì)數(shù)據(jù)的組織方法，以便選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，以及相應(yīng)的運(yùn)算（操作），把現(xiàn)實(shí)世界中的問題轉(zhuǎn)化為計(jì)算機(jī)內(nèi)部的表示和處理，這是一個(gè)良好的程序設(shè)計(jì)技能訓(xùn)練的過程。在整個(gè)教學(xué)或?qū)W習(xí)過程中，解題能力和技巧的訓(xùn)練是一個(gè)重要的環(huán)節(jié)。為了幫助教師講授數(shù)據(jù)結(jié)構(gòu)”，滿足指導(dǎo)和評價(jià) 課程設(shè)計(jì)”的需要，為了幫助和指導(dǎo)讀者更好地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程，我們特編寫了這本數(shù)據(jù)結(jié)構(gòu)實(shí)踐教程輔助教材，旨在彌補(bǔ)課堂教學(xué)和實(shí)驗(yàn)

2、中的不足，幫助學(xué)生充分理解和 鞏固所學(xué)的基本概念、原理和方法，達(dá)到融會(huì)貫通、舉一反三的目的。實(shí)踐證明，理解課程內(nèi)容與較好地解決實(shí)際問題之間存在著明顯差距，而算法設(shè)計(jì)完成的質(zhì)量與基本的程序設(shè)計(jì)素質(zhì)的培養(yǎng)是密切相關(guān)的。要想理解和鞏固所學(xué)的基本概念。原理和方法， 牢固地掌握所學(xué)的基本知識(shí)。基本技能， 達(dá)到融會(huì)貫通。 舉一反三的目的， 就必須多做。 多練。多見（見多識(shí)廣）。正是為了達(dá)到上述目的，書中用一些實(shí)際的應(yīng)用，對一些重要的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行解讀。經(jīng)過循序漸進(jìn)地訓(xùn)練，就可以使讀者掌握更多的程序設(shè)計(jì)技巧和方法，提高分析。解決問題的能力。本書根據(jù)學(xué)生的基礎(chǔ)知識(shí)和興趣愛好將內(nèi)容分為基礎(chǔ)篇和提高篇兩個(gè)部分

3、。第一部分基礎(chǔ)篇精 選出適當(dāng)?shù)摹⑴c實(shí)際生活結(jié)合密切的課程設(shè)計(jì)實(shí)例加以分析實(shí)現(xiàn)。第二部分提高篇旨在使讀者通過 運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)及復(fù)雜算法去解決現(xiàn)實(shí)世界中的一些實(shí)際問題。本書依據(jù)數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱要求，同時(shí)又獨(dú)立于具體的教科書，既重視實(shí)踐應(yīng)用，又重視 理論分析，本書的主要特點(diǎn)有：本書精選出來的實(shí)例項(xiàng)目經(jīng)典、實(shí)用、具有一定的趣味性，其內(nèi)容豐富、涉及面廣、難易適當(dāng)，能給讀者以啟發(fā)，達(dá)到讓讀者掌握相關(guān)知識(shí)和開闊視野的目的為了提高學(xué)生分析問題、解決問題的能力，本書對實(shí)例項(xiàng)目進(jìn)行分析，其設(shè)計(jì)思路清晰流暢， 值得參考。本書不僅僅是對照數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱舉些例子說明數(shù)據(jù)結(jié)構(gòu)能解決什么問題，而是通過 分析具體

4、的實(shí)例項(xiàng)目，得到對數(shù)據(jù)組織關(guān)系的需求，從而選擇某個(gè)數(shù)據(jù)結(jié)構(gòu)適應(yīng)一些特定的問題和 算法，并說明使用這種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)。所有實(shí)例項(xiàng)目都給出了參考算法和源程序代碼并在Turbo C和VisualC+6.0環(huán)境下運(yùn)行通過。由于作者水平有限、時(shí)間倉促，本書難免存在一些缺點(diǎn)和錯(cuò)誤，懇請廣大讀者及同行們批評指正。第一部分基礎(chǔ)篇第一章 線性表1.1學(xué)生成績管理1.1.1 項(xiàng)目簡介1.1.2 設(shè)計(jì)思路1.1.3 數(shù)據(jù)結(jié)構(gòu)1.1.4 程序清單1.1.5 運(yùn)行結(jié)果1.2考試報(bào)名管理1.2.1 項(xiàng)目簡介1.2.2 設(shè)計(jì)思路1.2.3 數(shù)據(jù)結(jié)構(gòu)1.2.4 程序清單1.2.5 運(yùn)行結(jié)果1.3約瑟夫生者死者游戲1.3.1

5、 項(xiàng)目簡介1.3.2 設(shè)計(jì)思路1.3.3 數(shù)據(jù)結(jié)構(gòu)1.3.4 程序清單1.3.5 運(yùn)行結(jié)果1.4約瑟夫雙向生死游戲1.4.1 項(xiàng)目簡介1.4.2 設(shè)計(jì)思路1.4.3 數(shù)據(jù)結(jié)構(gòu)1.4.4 程序清單1.4.5 運(yùn)行結(jié)果第二章棧和隊(duì)列2.1迷宮旅行游戲2.1.1項(xiàng)目簡介2.1.2知識(shí)要點(diǎn)2.1.3設(shè)計(jì)思路2.1.4程序清單2.1.5運(yùn)行結(jié)果22八皇后問題2.1.1項(xiàng)目簡介2.1.2知識(shí)要點(diǎn)2.1.3設(shè)計(jì)思路2.1.4程序清單2.1.5運(yùn)行結(jié)果2.3停車場的停車管理2.1.1項(xiàng)目簡介2.1.2知識(shí)要點(diǎn)2.1.3設(shè)計(jì)思路2.1.4程序清單2.1.5運(yùn)行結(jié)果第三章 串、數(shù)組和廣義表3.1單詞檢索統(tǒng)計(jì)程序3

6、.1.1項(xiàng)目簡介3.1.2設(shè)計(jì)思路3.1.3數(shù)據(jù)結(jié)構(gòu)3.1.4程序清單3.1.5運(yùn)行結(jié)果3.2 In ternet網(wǎng)絡(luò)通路管理3.2.1項(xiàng)目簡介3.2.2設(shè)計(jì)思路3.2.3數(shù)據(jù)結(jié)構(gòu)3.2.4程序清單3.2.5運(yùn)行結(jié)果第四章樹和二叉樹4.1家譜管理4.1.1項(xiàng)目簡介4.1.2設(shè)計(jì)思路4.1.3數(shù)據(jù)結(jié)構(gòu)4.1.4程序清單4.1.5運(yùn)行結(jié)果4.2表達(dá)式求值問題4.2.1項(xiàng)目簡介422設(shè)計(jì)思路423數(shù)據(jù)結(jié)構(gòu)4.2.4程序清單4.2.5運(yùn)行結(jié)果4.4圖像壓縮編碼優(yōu)化4.4.1項(xiàng)目簡介4.4.2設(shè)計(jì)思路4.4.3數(shù)據(jù)結(jié)構(gòu)4.4.4程序清單4.4.5運(yùn)行結(jié)果第五章 圖5.1公交路線管理5.1.1項(xiàng)目簡介5.

7、1.2設(shè)計(jì)思路5.1.3數(shù)據(jù)結(jié)構(gòu)5.1.4程序清單5.1.5運(yùn)行結(jié)果5.2導(dǎo)航最短路徑查詢5.2.1項(xiàng)目簡介5.2.2設(shè)計(jì)思路5.2.3數(shù)據(jù)結(jié)構(gòu)5.2.4程序清單5.2.5運(yùn)行結(jié)果5.4電網(wǎng)建設(shè)造價(jià)計(jì)算5.4.1項(xiàng)目簡介5.4.2設(shè)計(jì)思路5.4.3數(shù)據(jù)結(jié)構(gòu)5.4.4程序清單5.4.5運(yùn)行結(jié)果5.4軟件工程進(jìn)度規(guī)劃5.4.1項(xiàng)目簡介5.4.2設(shè)計(jì)思路5.4.3數(shù)據(jù)結(jié)構(gòu)544545程序清單運(yùn)行結(jié)果第八早查找6.1電話號碼查詢系統(tǒng)6.1.1項(xiàng)目簡介6.1.2知識(shí)要點(diǎn)6.1.3設(shè)計(jì)思路6.1.4程序清單6.1.5運(yùn)行結(jié)果6.2高校錄取分?jǐn)?shù)線查詢系統(tǒng)6.2.1項(xiàng)目簡介5.2.2知識(shí)要點(diǎn)6.2.3設(shè)計(jì)思路

8、6.2.4程序清單6.2.5運(yùn)行結(jié)果6.3儲(chǔ)畜賬戶查詢系統(tǒng)6.3.1項(xiàng)目簡介6.3.2知識(shí)要點(diǎn)6.3.3設(shè)計(jì)思路6.3.4程序清單6.3.5運(yùn)行結(jié)果6.3期刊稿件查詢系統(tǒng)6.3.1項(xiàng)目簡介6.3.2知識(shí)要點(diǎn)6.3.3設(shè)計(jì)思路6.3.4程序清單6.3.5運(yùn)行結(jié)果第七章排序7.1設(shè)備清單排序7.1.1項(xiàng)目簡介7.1.2知識(shí)要點(diǎn)7.1.3設(shè)計(jì)思路7.1.4程序清單7.1.5運(yùn)行結(jié)果7.2地名排序7.2.1項(xiàng)目簡介722知識(shí)要點(diǎn)723設(shè)計(jì)思路7.2.4程序清單7.2.5運(yùn)行結(jié)果7.3工廠產(chǎn)量排序7.3.1項(xiàng)目簡介7.3.2知識(shí)要點(diǎn)7.3.3設(shè)計(jì)思路7.3.4程序清單7.3.5運(yùn)行結(jié)果7.4高校科研成果

9、排序7.4.1項(xiàng)目簡介7.4.2知識(shí)要點(diǎn)7.4.3設(shè)計(jì)思路7.4.4程序清單7.4.5運(yùn)行結(jié)果7.5火車車次排序7.5.1項(xiàng)目簡介7.5.2知識(shí)要點(diǎn)7.5.3設(shè)計(jì)思路7.5.4程序清單7.5.5運(yùn)行結(jié)果7.6 IP地址排序7.6.1項(xiàng)目簡介7.6.2知識(shí)要點(diǎn)7.6.3設(shè)計(jì)思路7.6.4程序清單7.6.5運(yùn)行結(jié)果第二部分綜合篇8.1益智游戲之七巧板8.1.1項(xiàng)目需求8.1.2 知識(shí)要點(diǎn)8.1.3設(shè)計(jì)流程8.1.4程序清單8.1.5運(yùn)行測試8.2航空客運(yùn)定票系統(tǒng)8.2.1項(xiàng)目需求8.2.2知識(shí)要點(diǎn)8.2.3設(shè)計(jì)流程8.2.4程序清單8.2.5運(yùn)行測試8.4景區(qū)旅游信息管理系統(tǒng)8.4.1項(xiàng)目需求8.

10、2.2知識(shí)要點(diǎn)8.4.2設(shè)計(jì)流程8.4.4程序清單8.4.5運(yùn)行測試第一部分基礎(chǔ)篇第一章線性表線性表是數(shù)據(jù)結(jié)構(gòu)中最簡單、最常用的一種線性結(jié)構(gòu)，也是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)全部內(nèi)容的基 礎(chǔ)，其掌握的好壞直接影響著后繼知識(shí)的學(xué)習(xí)。本章通過四個(gè)模擬項(xiàng)目來學(xué)習(xí)線性表的順序 和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，首先通過使用有關(guān)數(shù)組的操作實(shí)現(xiàn)學(xué)生成績管理，其次通過使用有關(guān)線性 鏈表的操作實(shí)現(xiàn)考試報(bào)名管理，然后通過使用循環(huán)鏈表的操作實(shí)現(xiàn)約瑟夫生者死者游戲。1.1學(xué)生成績管理1.1.1項(xiàng)目簡介學(xué)生成績管理是學(xué)校教務(wù)部門日常工作的重要組成部分，其處理信息量很大。本項(xiàng)目是 對學(xué)生成績管理的簡單模擬，用菜單選擇方式完成下列功能：輸入學(xué)生數(shù)據(jù)；輸出

11、學(xué)生數(shù)據(jù);學(xué)生數(shù)據(jù)查詢；添加學(xué)生數(shù)據(jù)；修改學(xué)生數(shù)據(jù)；刪除學(xué)生數(shù)據(jù)。1.1.2設(shè)計(jì)思路本項(xiàng)目的實(shí)質(zhì)是完成對學(xué)生成績信息的建立、查找、插入、修改、刪除等功能，可以首 先定義項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)，然后將每個(gè)功能寫成一個(gè)函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函 數(shù)以驗(yàn)證各個(gè)函數(shù)功能并得出運(yùn)行結(jié)果。1.1.3數(shù)據(jù)結(jié)構(gòu)本項(xiàng)目的數(shù)據(jù)是一組學(xué)生的成績信息，每條學(xué)生的成績信息由學(xué)號、姓名和成績組成， 這組學(xué)生的成績信息具有相同特性，屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。 由此可以看出，這些數(shù)據(jù)具有線性表中數(shù)據(jù)元素的性質(zhì)，所以該系統(tǒng)的數(shù)據(jù)采用線性表來存 儲(chǔ)。順序表是線性表的順序存儲(chǔ)結(jié)構(gòu)，是指用一組連續(xù)的內(nèi)存單元依

12、次存放線性表的數(shù)據(jù)元 素。在順序存儲(chǔ)結(jié)構(gòu)下， 邏輯關(guān)系相鄰的兩個(gè)元素在物理位置上也相鄰，這是順序表的特點(diǎn)。本項(xiàng)目可以采用順序表的線性表順序存儲(chǔ)結(jié)構(gòu)。若一個(gè)數(shù)據(jù)元素僅占一個(gè)存儲(chǔ)單元，則其存儲(chǔ)方式參見圖1-1。從圖1-1中可見，第i個(gè)數(shù)據(jù)元素的地址為Loc(ai)=loc(a1)+(i-1)假設(shè)線性表中每個(gè)元素占用k個(gè)存儲(chǔ)單元，那么在順序表中，線性表的第i個(gè)元素的存儲(chǔ)位置與第1個(gè)元素的存儲(chǔ)位置的關(guān)系是Loc(ai)=loc(a1)+(i-1)*k這里L(fēng)oc(ai)是第i個(gè)元素的存儲(chǔ)位置，Ioc(a1)是第1個(gè)元素的存儲(chǔ)位置，也稱為線性表 的基址。顯然，順序表便于進(jìn)行隨機(jī)訪問，故線性表的順序存儲(chǔ)結(jié)構(gòu)

13、是一種隨機(jī)存儲(chǔ)結(jié)構(gòu)。順序表適宜于做查找這樣的靜態(tài)操作；順序存儲(chǔ)的優(yōu)點(diǎn)是存儲(chǔ)密度大，存儲(chǔ)空間利用率 高。缺點(diǎn)是插入或刪除元素時(shí)不方便。由于C語言的數(shù)組類型也有隨機(jī)存儲(chǔ)的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此,可用C語言的一維數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)。數(shù)組實(shí)現(xiàn)線性表的順序存儲(chǔ)的優(yōu)點(diǎn)是可以隨機(jī)存取表中任一元素 0(1)，存儲(chǔ)空間使用緊湊；缺點(diǎn)是在插入，刪除某一元素時(shí)，需要移動(dòng) 大量元素0(n),預(yù)先分配空間需按最大空間分配，利用不充分，表容量難以擴(kuò)充。用結(jié)構(gòu)體類型定義每個(gè)學(xué)生數(shù)據(jù)，故該數(shù)組中的每個(gè)數(shù)據(jù)的結(jié)構(gòu)可描述為：typedef struct STUchar stu no10;學(xué)號char n

14、ame10;姓名float score;成績 ElemType;1.1.4程序清單#in clude#i nclude#in clude#in clude#define MaxListSize 20#define EQUAL 1typedef struct STUchar stuno 10;char n ame 10;float score;ElemType;class Listprivate:/線性表的數(shù)組表示ElemType elemMaxListSize;in t le ngth;int MaxSize;public:/輸入學(xué)生數(shù)據(jù)void init(List *L,int ms);刪除

15、所有學(xué)生數(shù)據(jù)void DestroyList(List & L)free(&L);將順序表置為空表void ClearList()le ngth=0;/判斷順序表是否為空表bool ListEmpty()retur n len gth=0;/判斷順序表是否為滿bool ListFull()return len gth=MaxSize;刪除某個(gè)學(xué)生數(shù)據(jù)bool ListDelete(i nt,ElemType &e);/遍歷順序表void ListTraverse();/返回順序表的長度int ListLe ngth();/學(xué)生數(shù)據(jù)查詢void GetElem(i nt,ElemType *);

16、/修改學(xué)生數(shù)據(jù)bool UpdateList(ElemType & e,ElemType);/添加學(xué)生數(shù)據(jù)bool List In sert(i nt,ElemType &);/對學(xué)生數(shù)據(jù)按升序或降序輸出void prin tlist(i nt);void List:init(List *L,int ms) *L=(List *)malloc(sizeof(List);(*L)-le ngth=O;(*L)-MaxSize=ms;int List:ListLe ngth()return len gth;bool List:ListDelete(i nt mark,ElemType &e)int

17、 i,j;if(ListEmpty() return false;if(mark0) 刪除表頭元素e=elem0;for(i=1; ile ngth; i+)elemi-1=elemi;else刪除表尾元素if(mark0) e=elemle ngth-1;else 刪除值為e的元素for(i=0;i=length) return false;else e=elemi;for(j=i+1;jle ngth;j+) elemj-1=elemj;len gth-;return true;void List:ListTraverse()for(i nt i=0;ile ngth;i+)coutset

18、w(8)elemi. name;coutsetw(10)elemi.st uno;coutsetw(9)elemi.age;coutsetw(8)elemi.scoren ame,e2-n ame)return false;if (strcmp(e1-st uno ,e2-st uno)return false;if (e1-age!=e2-age)return false;if (e1-score!=e2-score)return false;return true;bool List:Less_EqualList(ElemType *e1,ElemType *e2) if(strcmp(e

19、1- n ame,e2-n ame)=0) retur n true;else return false;bool List:LocateElem(ElemType e,i nt type) int i;switch (type) case EQUAL:for(i=0;ile ngth;i+)if(EqualList( &elemi, &e)return true;break;default:break;return false;/修改學(xué)生數(shù)據(jù)bool List:UpdateList(ElemType & e,ElemType e1)for(i nt i=0;ile ngth;i+)if(st

20、rcmp(elemi. name,e. name)=O) elemi=e1;return true;return false;bool List:Listlnsert(int i,ElemType &e)ElemType *p,*q;if(ile ngth+1) return false;q=&elemi-1;for(p=& elemle ngth_1;p=q;_p)*(p+1)=*p;*q=e;+le ngth;return true;/對學(xué)生成績按升序或降序輸出void List:printlist(int mark)int* b=new in tle ngth;int i,k;cout

21、姓名 學(xué)號成績n;if(mark!=0)for(i=0; ile ngth;i+) bi=i;for(i=0; ile ngth;i+) k=i;for(i nt j=i+1;jle ngth;j+) if(mark=1 &elembj.scoreelembk.score) k=j;if(mark=-1 &elembk.scoreelembj.score) k=j; if(k!=i) int x=bi;bi=bk;bk=x;for(i nt i=0;ile ngth;i+)coutsetw(8)elembi .n ame;coutsetw(10)elembi.st uno;coutsetw(9

22、)elembi.age; coutsetw(8)elembi.scoree ndl;else for(i=0;ile ngth;i+)coutsetw(8)elemi. name;coutsetw(10)elemi.st uno;coutsetw(9)elemi.age;coutsetw(8)elemi.scoree ndl;void mai n() coutlinelist1m.cpp 運(yùn)行結(jié)果:n;ElemType e,e1,e2,e3,e4,e5,e6;List *La,*Lb,*Lc;int k;couti nit(&La,4);strcpy(e1. name,stu1);strcpy

23、(e1.stu no,100001);e1.age=22;e1.score=88;La-Listl nsert(1,e1);strcpy(e2. name,stu2);strcpy(e2.stu no,100002);e2.age=21;e2.score=79;La-ListI nsert(2,e2);strcpy(e3. name,stu3);strcpy(e3.stu no,100003);e3.age=19;e3.score=87;La-ListI nsert(3,e3);La-pri ntlist(O);cout表 La 長:ListLength()i nit(&Lb,4);strcp

24、y(e4 .n ame,zmofu n);strcpy(e4.stu no,100001);e4.age=20;e4.score=94;Lb-Listl nsert(1,e4);strcpy(e5 .n ame,bobj in ”)；strcpy(e5.stu no,100002);e5.age=23;e5.score=69;Lb-ListI nsert(2,e5);strcpy(e6 .n ame,stu1);strcpy(e6.stu no,100001);e6.age=22;e6.score=88;Lb-ListI nsert(3,e6);Lb-pri ntlist(O);cout表 L

25、b 長:ListLength()ListDelete(-1,e6);if(k=O) cout刪除失敗!n;else cout刪除成功!n;coutpri ntlist(O);cin .get();coutpri ntlist(1);ci n. get();coutpri ntlist(-1);ci n. get();1.1.5運(yùn)行結(jié)果首先建立學(xué)生信息管理，輸出結(jié)果為姓名學(xué)號成績Stu110000180Stu210000291Stu3 10000356其次查詢學(xué)號為100002的學(xué)生的成績，輸出結(jié)果為：91再次調(diào)用插入函數(shù)，插入Stu4成功！輸入結(jié)果為：姓名學(xué)號成績Stu110000180Stu

26、210000291Stu310000356Stu410000475最后刪除Stu2成果！輸出結(jié)果為：姓名學(xué)號成績Stu110000180Stu310000356Stu410000475查詢不及格的學(xué)生，輸出結(jié)果為：Stu3100003561.2考試報(bào)名管理1.2.1項(xiàng)目簡介考試報(bào)名工作給各高校報(bào)名工作帶來了新的挑戰(zhàn)，給教務(wù)管理部門增加了很大的工作量,報(bào)名數(shù)據(jù)手工錄入既費(fèi)時(shí)又會(huì)不可避免地出現(xiàn)錯(cuò)誤，同時(shí)也給不少學(xué)生以可乘之機(jī)。本項(xiàng)目 是對考試報(bào)名管理的簡單模擬，用菜單選擇方式完成下列功能：輸入考生信息；輸出考生信 息；查詢考生信息；添加考生信息；修改考生信息；刪除考生信息。1.2.2設(shè)計(jì)思路本項(xiàng)目

27、的實(shí)質(zhì)是完成對考生信息的建立、查找、插入、修改、刪除等功能，可以首先定 義項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)，然后將每個(gè)功能寫成一個(gè)函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以 驗(yàn)證各個(gè)函數(shù)功能并得出運(yùn)行結(jié)果。1.2.3數(shù)據(jù)結(jié)構(gòu)本項(xiàng)目的數(shù)據(jù)是一組考生信息，每條考生信息由準(zhǔn)考證號、姓名、性別、年齡、報(bào)考類 別等信息組成，這組考生信息具有相同特性，屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在序 偶關(guān)系。由此可以看出，這些數(shù)據(jù)也具有線性表中數(shù)據(jù)元素的性質(zhì)，所以該系統(tǒng)的數(shù)據(jù)可以 采用線性表來存儲(chǔ)。從上一節(jié)的例子中可見，線性表的順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系相鄰的兩個(gè)元素在物 理位置上也相鄰，因此可以隨機(jī)存儲(chǔ)表中任一元素，它的存儲(chǔ)位置

28、可用一個(gè)簡單、直觀的公 式來表示。然而，從另一個(gè)方面來看，這個(gè)特點(diǎn)也鑄成了這種存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)：在做插入或 刪除操作時(shí)，需要移動(dòng)大量元素。為克服這一缺點(diǎn)，我們引入另一種存儲(chǔ)形式一一鏈?zhǔn)酱鎯?chǔ)。 鏈?zhǔn)酱鎯?chǔ)是線性表的另一種表示方法，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲(chǔ)結(jié)構(gòu)的弱點(diǎn)，但同時(shí)也失去了順序表可隨機(jī)存取的特點(diǎn)。鏈?zhǔn)酱鎯?chǔ)的優(yōu)點(diǎn)是插入或刪除元素時(shí)很方便，使用靈活。缺點(diǎn)是存儲(chǔ)密度小，存儲(chǔ)空間 利用率低。事實(shí)上，鏈表插入、刪除運(yùn)算的快捷是以空間代價(jià)來換取時(shí)間。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性 表的長度變化不大，且其主要操作是查找，

29、則采用順序表；若線性表的長度變化較大，且其 主要操作是插入、刪除操作，則采用鏈表。本項(xiàng)目對考生數(shù)據(jù)主要進(jìn)行插入、刪除、修改等操作，所以采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)比較適合。用結(jié)構(gòu)體類型定義每個(gè)考生信息，故該單鏈表中的每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)可描述為：typedef struct exam inee char exa mn o10;準(zhǔn)考證號char name10;姓名char sex;float age;char examtype5;成績 ElemType;1.2.4程序清單單鏈表的類定義 lin klist3.h#ifndef lin klist3H#define linklist3H#define LEN 30/

30、定義 ElemType 為 inttypedef int ElemType;/單鏈表中結(jié)點(diǎn)的類型typedef struct LNodeElemType data;/ 值域LNode *n ext;指針域LNode;class Lin kListLNode *head;public:/構(gòu)造函數(shù)Li nkList();析構(gòu)函數(shù)L in kList();/清空單鏈表void ClearList();求單鏈表長度int ListSize();/檢查單鏈表是否為空bool ListEmpty();/返回單鏈表中指定序號的結(jié)點(diǎn)值ElemType GetElem(i nt pos);/遍歷單鏈表void

31、TraverseList(void f(ElemType &);/從單鏈表中查找元素bool Fin dList(ElemType& item);/更新單鏈表中的給定元素bool UpdateList(c onst ElemType& item,ElemType e);/向單鏈表插入元素,mark=0插在表首，否則插在表尾void In sertList(ElemType item ,int mark);從單鏈表中刪除元素 ，mark為要?jiǎng)h除的第幾個(gè)元素bool DeleteList(ElemType& item,i nt mark);對單鏈表進(jìn)行有序排列mark0升序，否則降序void pa

32、ilie(i nt mark=1);對單鏈表進(jìn)行有序輸出,mark=0不排序,mark0升序,markn ext ,*q;while(p)q=p-n ext ;free(p);p=q;void Lin kList:ClearList() 清空單鏈表LNode*p=head-n ext ,*q;while(p)q=p-n ext;free(p);p=q;head- next =NULL;int LinkList:ListSize() 求單鏈表長度LNode*p=head-n ext ;int i=0;while(p)i+;p=p-n ext ;return i;bool Lin kList:Li

33、stEmpty() 檢查單鏈表是否為空return ListSize()=O;/返回單鏈表中指定序號的結(jié)點(diǎn)值ElemType Lin kList:GetElem(i nt pos)LNode*p=head-n ext ;int i=1;while(p)if(i+=pos)retur n p-data ;p=p-n ext ;retur n head-data ;void Lin kList:TraverseList(void f(ElemType &)/ 遍歷單鏈表LNode*p=head-n ext ;while(p)f(p-data );p=p-n ext ;bool Lin kList:

34、Fi ndList(ElemType & item)/ 從單鏈表中查找元素LNode*p=head-n ext ;while(p)if(p-data=item)return 1;p=p-n ext ;return 0;/更新單鏈表中的給定元素bool Lin kList:UpdateList(c onst ElemType &item,ElemType e)LNode*p=head-n ext ;bool flag=O;while(p)if(p-data=item)p-data=e;flag=1;p=p-n ext ;retur n flag;/向單鏈表插入元素void Lin kList:l

35、 nsertList(ElemType item,i nt mark) LNode *q= new LNode;q-data = item;if(mark=0)q-n ext = head-next ;head-n ext=q;return;LNode *p=head;while(p- next)p=p-n ext ;q- next =NULL;p_n ext =q;/從單鏈表中刪除元素bool Li nkList:DeleteList(ElemType & item ,int mark) if(ListEmpty()|markListSize()return 0;LNode *p=head,

36、*q;for(int i=0;in ext;item=p-n ext-data;q=p-n ext- next ;free(p-next );p-n ext=q;return 1;/對單鏈表進(jìn)行有序排列mark0升序，否則降序void Lin kList:pailie(i nt mark)ElemType aLEN+1;LNode *p=head-n ext;int k ;for(k=1;p!=NULL;k+,p=p-next)ak=p-data;k-;for(i nt i=1;ik;i+)for(i nt j=1;j0&ajaj+1|mark0&ajn ext;for(i nt j=1;jn

37、ext )p-data=aj;/對單鏈表進(jìn)行有序輸出void Lin kList:OrderOutputList(i nt mark)ElemType aLEN+1;LNode *p=head-n ext;int k ;for( k=1;p!=NULL;k+,p=p- next )ak=p-data;k-;for(i nt i=1;ik;i+)for(i nt j=1;j0&ajaj+1|mark0&ajaj+1)t=aj+1;aj+1=aj;aj=t;for(i nt j=1;j=k;j+)coutaj;#in clude#i nclude#i nclude#in clude#i nclud

38、eli nklist3.cppvoid ff(int &a)用于遍歷的函數(shù)couta;void mai n()coutnlinklist3m.cpp 運(yùn)行結(jié)果:n;int ini t_size,seed,xu;cout首先請構(gòu)造單鏈表list;cout i ni t_size;seed=150;cout xu;coutn單鏈表list構(gòu)造成功!n它是:;list.TraverseList(ff);coutn 它為空嗎?(1:是;0:不是):list.ListEmpty();coutn 長度為:list.ListSize();int i;coutn請輸入你想得到第幾個(gè)元素的值(1-init_si

39、ze i;cout單鏈表 list 中第i的值是list.GetElem(i);int it;coutn請輸入你想刪除第幾個(gè)元素的值(1-init_size i;list.DeleteList(it,i);后變?yōu)?;coutn 單鏈表 list 刪除第i個(gè)元素it list.TraverseList(ff);/對單鏈表list每個(gè)數(shù)進(jìn)行遍歷.int n ews,olds;coutolds;cout news;list.UpdateList(olds ,n ews);coutn修改后單鏈表list變?yōu)?;list.TraverseList(ff);coutn下面請構(gòu)造單鏈表list2;cout

40、i ni t_size;seed=120;cout xu;coutn按回車鍵結(jié)束.；cin .get();ci n.get();1.2.5運(yùn)行結(jié)果1.3約瑟夫生者死者游戲1.3.1項(xiàng)目簡介約瑟夫生者死者游戲的大意是：30個(gè)旅客同乘一條船，因?yàn)閲?yán)重超載，加上風(fēng)高浪大，危險(xiǎn)萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無 奈，大家只得同意這種辦法，并議定30個(gè)人圍成一圈，由第一個(gè)人開始，依次報(bào)數(shù)，數(shù)到第9人，便把他投入大海中，然后從他的下一個(gè)人數(shù)起，數(shù)到第9人，再將他投入大海，如此循環(huán)，直到剩下15個(gè)乘客為止。問哪些位置是將被扔下大海的位置。1.3.2設(shè)計(jì)思路本游戲的數(shù)

41、學(xué)建模如下：假設(shè)n個(gè)旅客排成一個(gè)環(huán)形，依次順序編號1, 2,，n。從某個(gè)指定的第1號開始，沿環(huán)計(jì)數(shù)，每數(shù)到第m個(gè)人就讓其出列，且從下一個(gè)人開始重新計(jì)數(shù)，繼續(xù)進(jìn)行下去。這個(gè)過程一直進(jìn)行到剩下k個(gè)旅客為止。本游戲的要求用戶輸入的內(nèi)容包括：1. 旅客的個(gè)數(shù)，也就是 n的值；2. 離開旅客的間隔數(shù)，也就是 m的值；3. 所有旅客的序號作為一組數(shù)據(jù)要求存放在某種數(shù)據(jù)結(jié)構(gòu)中。本游戲要求輸出的內(nèi)容是包括1. 離開旅客的序號；2. 剩余旅客的序號；所以，根據(jù)上面的模型分析及輸入輸出參數(shù)分析，可以定義一種數(shù)據(jù)結(jié)構(gòu)后進(jìn)行算法實(shí) 現(xiàn)。133數(shù)據(jù)結(jié)構(gòu)為了解決這一問題，可以用長度為30的數(shù)組作為線性存儲(chǔ)結(jié)構(gòu)，并把該數(shù)組

42、看成是一個(gè) 首尾相接的環(huán)形結(jié)構(gòu)， 那么每投入大海一個(gè)乘客，就要在該數(shù)組的相應(yīng)位置做一個(gè)刪除標(biāo)記，該單元以后就不再作為計(jì)數(shù)單元。這樣做不僅算法較為復(fù)雜，而且效率低，還要移動(dòng)大量的 元素。用單循環(huán)鏈表解決這一問題，實(shí)現(xiàn)的方法相對要簡單得多。首先要定義鏈表結(jié)點(diǎn)，單 循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)與一般的結(jié)點(diǎn)結(jié)構(gòu)完全相同，只是數(shù)據(jù)域用一個(gè)整數(shù)來表示位置；然后 將它們組成具有30個(gè)結(jié)點(diǎn)的單循環(huán)鏈表。接下來從位置為1的結(jié)點(diǎn)開始數(shù)，數(shù)到第8個(gè)結(jié)點(diǎn)， 就將下一個(gè)結(jié)點(diǎn)從循環(huán)鏈表中刪去，然后再從刪去結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)開始數(shù)起，數(shù)到第8個(gè)結(jié)點(diǎn)，再將其下一個(gè)結(jié)點(diǎn)刪去，如此進(jìn)行下去，直到剩下15個(gè)結(jié)點(diǎn)為止。為了不失一般性，將 30改

43、為一個(gè)任意輸入的正整數(shù)n,而報(bào)數(shù)上限(原為 9)也為一個(gè)任選的正整數(shù)k。這樣該算法描述如下：(1) 創(chuàng)建含有n個(gè)結(jié)點(diǎn)的單循環(huán)鏈表；(2) 生著與死者的選擇：p指向鏈表的第一個(gè)結(jié)點(diǎn)，初始i置為1 ；while(idata;i自增1；(3) 輸出所有生者的位置。1.3.4程序清單Lin kList InitRin g(i nt n, Li nkList R)/尾插入法建立單循環(huán)鏈表函數(shù)ListNode *p, *q;int I;R=q=(L in kNode *)malloc(sizeof(Li nkNode);for(i=1;idata=i;q_n ext=p;q=p;p-data=n;p_n

44、ext=R;R=p；return R;Li nkList DeleteDeath(i nt n, i nt k, Li nkList R)生者與死者的選擇int i, j;ListNode *p, *q;p=R;for(i=1; in/2; i+)/刪除一半結(jié)點(diǎn)for(j=1; jn ext;q=p-n ext;p_n ext=q _n ext;printf( %4d”，q-data);free(q);R=p; return R;void OutR in g(i nt n, Li nkList R)/ 輸出所有生者int i;Lin kNode *p;p=R;for(i=1;in ext)pr

45、intf( %4d ”，p-data)有了上述算法分析和設(shè)計(jì)之后，實(shí)現(xiàn)就比較簡單了。首先要定義一個(gè)鏈表結(jié)構(gòu)類型，然 后編寫一個(gè)主函數(shù)調(diào)用上面已定義好的函數(shù)即可。主函數(shù)的源程序如下：#i nclude#in cludetypedef struct no deint data;struct node * n ext;ListNode;typedef ListNode * Lin kList;void mai n()Li nkList R;int n ,k;Lin kList Ini tR ing(int n, Li nkList R);Li nkList DeleteDeath(i nt n, i

46、nt k, L in kList R); void OutRing(int n, LinkList R);printf(總?cè)藬?shù)n.報(bào)數(shù)上限k= ”)； scanf( %d%d ,&n, &k);R=I ni tRi ng( n, R);R=DeleteDeath(n, k, R);OutRi ng( n, R);1.3.5運(yùn)行結(jié)果編譯運(yùn)行上述程序，提示：總?cè)藬?shù) n.報(bào)數(shù)上限k= 輸入30和9后并“回車”可得出如下結(jié)果：91827616 267193012248225232125282912 34101113141517201.4約瑟夫雙向生死游戲1.4.1項(xiàng)目簡介約瑟夫雙向生死游戲是在約瑟夫生

47、者死者游戲的基礎(chǔ)上，正向計(jì)數(shù)后反向計(jì)數(shù)，然后再正向計(jì)數(shù)。具體描述如下：30個(gè)旅客同乘一條船， 因?yàn)閲?yán)重超載，加上風(fēng)高浪大，危險(xiǎn)萬分； 因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定 30個(gè)人圍成一圈，由第一個(gè)人開始，順時(shí)針依次報(bào)數(shù)，數(shù)到第9人，便把他投入大海中，然后從他的下一個(gè)人數(shù)起，逆時(shí)針數(shù)到第5人，將他投入大海，然9人，再將他投入大海，如此循環(huán)，直到剩下后從他逆時(shí)針的下一個(gè)人數(shù)起，順時(shí)針數(shù)到第15個(gè)乘客為止。問哪些位置是將被扔下大海的位置。142設(shè)計(jì)思路本游戲的數(shù)學(xué)建模如下：假設(shè) n個(gè)旅客排成一個(gè)環(huán)形，依次順序編號 1, 2,，n。從 某個(gè)指定的第1號開始，沿環(huán)計(jì)數(shù)，數(shù)到第 m個(gè)人就讓其出列，然后從第 m+1個(gè)人反向計(jì) 數(shù)到m-k+1個(gè)人，讓其出列，然后從 m-k個(gè)人開始重新正向沿環(huán)計(jì)數(shù)，再數(shù) m個(gè)人后讓其 出列，然后再反向數(shù) k個(gè)人后讓其出列。這個(gè)過程一直進(jìn)行到剩下q個(gè)旅客為止。本游戲的要求用戶輸入的內(nèi)容包括：1. 旅客的個(gè)數(shù)，也就是 n的值；2. 正向離開旅客的間隔數(shù)，也就是m的值；3. 反向離開旅客的間隔數(shù)，也就是k的值；4. 所有旅客的序號作為一組數(shù)據(jù)要求存放在某種數(shù)據(jù)結(jié)