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

1、數(shù)據(jù)結(jié)構(gòu)實踐教程刖百數(shù)據(jù)結(jié)構(gòu)是計算機專業(yè)的必修。 主干課程之一， 它旨在使讀者學會分析研究數(shù)據(jù)對象的特性， 學會數(shù)據(jù)的組織方法， 以便選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)， 以及相應(yīng)的運算（操作） ， 把現(xiàn)實世界中的問題轉(zhuǎn)化為計算機內(nèi)部的表示和處理， 這是一個良好的程序設(shè)計技能訓(xùn)練的過程。 在整個教學或?qū)W習過程中， 解題能力和技巧的訓(xùn)練是一個重要的環(huán)節(jié)。 為了幫助教師講授 “數(shù)據(jù)結(jié)構(gòu) ” ， 滿足指導(dǎo)和評價 “課程設(shè)計 ” 的需要， 為了幫助和指導(dǎo)讀者更好地學習數(shù)據(jù)結(jié)構(gòu)這門課程， 我們特編寫了這本數(shù)據(jù)結(jié)構(gòu)實踐教程輔助教材，旨在彌補課堂教學和實驗中的不足，幫助學生充分理解和鞏固所學的基本概念、原理和

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

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

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

5、2 設(shè)計思路1.3.3 數(shù)據(jù)結(jié)構(gòu)1.3.4 程序清單1.3.5 運行結(jié)果1.4 約瑟夫雙向生死游戲1.4.1 項目簡介1.4.2 設(shè)計思路1.4.3 數(shù)據(jù)結(jié)構(gòu)1.4.4 程序清單1.4.5 運行結(jié)果第二章 棧和隊列2.1 迷宮旅行游戲2.1.1 項目簡介2.1.2 知識要點2.1.3 設(shè)計思路2.1.5 運行結(jié)果2.2 八皇后問題2.2.1 項目簡介2.2.2 知識要點2.2.3 設(shè)計思路2.2.4 程序清單2.2.5 運行結(jié)果2.3 停車場的停車管理2.3.1 項目簡介2.3.2 知識要點2.3.3 設(shè)計思路2.3.4 程序清單2.3.5 運行結(jié)果第三章 串、數(shù)組和廣義表3.1 單詞檢索統(tǒng)計

6、程序3.1.1 項目簡介3.1.2 設(shè)計思路3.1.3 數(shù)據(jù)結(jié)構(gòu)3.1.4 程序清單3.1.5 運行結(jié)果3.2 Internet 網(wǎng)絡(luò)通路管理3.2.1 項目簡介3.2.2 設(shè)計思路3.2.3 數(shù)據(jù)結(jié)構(gòu)3.2.4 程序清單3.2.5 運行結(jié)果第四章 樹和二叉樹4.1 家譜管理4.1.1 項目簡介4.1.2 設(shè)計思路4.1.3 數(shù)據(jù)結(jié)構(gòu)4.1.4 程序清單4.1.5 運行結(jié)果4.2 表達式求值問題4.2.1 項目簡介#4.2.2 設(shè)計思路4.2.3 數(shù)據(jù)結(jié)構(gòu)4.2.4 程序清單4.2.5 運行結(jié)果4.4 圖像壓縮編碼優(yōu)化4.4.1 項目簡介4.4.2 設(shè)計思路4.4.3 數(shù)據(jù)結(jié)構(gòu)4.4.4 程序

7、清單4.4.5 運行結(jié)果第五章 圖5.1 公交路線管理5.1.1 項目簡介5.1.2 設(shè)計思路5.1.3 數(shù)據(jù)結(jié)構(gòu)5.1.4 程序清單5.1.5 運行結(jié)果5.2 導(dǎo)航最短路徑查詢5.2.1 項目簡介5.2.2 設(shè)計思路5.2.3 數(shù)據(jù)結(jié)構(gòu)5.2.4 程序清單5.2.5 運行結(jié)果5.4 電網(wǎng)建設(shè)造價計算5.4.1 項目簡介5.4.2 設(shè)計思路5.4.3 數(shù)據(jù)結(jié)構(gòu)5.4.4 程序清單5.4.5 運行結(jié)果5.4 軟件工程進度規(guī)劃5.4.1 項目簡介5.4.2 設(shè)計思路5.4.3 數(shù)據(jù)結(jié)構(gòu)5.4.4 程序清單第六章 查找6.1 電話號碼查詢系統(tǒng)6.1.1 項目簡介6.1.2 知識要點6.1.3 設(shè)計思

8、路6.1.4 程序清單6.1.5 運行結(jié)果6.2 高校錄取分數(shù)線查詢系統(tǒng)6.2.1 項目簡介5.2.2 知識要點5.2.3 設(shè)計思路5.2.4 程序清單5.2.5 運行結(jié)果6.3 儲蓄賬戶查詢系統(tǒng)6.3.1 項目簡介6.3.2 知識要點6.3.3 設(shè)計思路6.3.4 程序清單6.3.5 運行結(jié)果6.3 期刊稿件查詢系統(tǒng)6.3.1 項目簡介6.3.2 知識要點6.3.3 設(shè)計思路6.3.4 程序清單6.3.5 運行結(jié)果第七章 排序7.1 設(shè)備清單排序7.1.1 項目簡介7.1.2 知識要點7.1.3 設(shè)計思路7.1.4 程序清單7.1.5 運行結(jié)果7.2 地名排序7.2.1 項目簡介7.2.2

9、知識要點#7.2.3 設(shè)計思路7.2.4 程序清單7.2.5 運行結(jié)果7.3 工廠產(chǎn)量排序7.3.1 項目簡介7.3.2 知識要點7.3.3 設(shè)計思路7.3.4 程序清單7.3.5 運行結(jié)果7.4 高?？蒲谐晒判?.4.1 項目簡介7.4.2 知識要點7.4.3 設(shè)計思路7.4.4 程序清單7.4.5 運行結(jié)果7.5 火車車次排序7.5.1 項目簡介7.5.2 知識要點7.5.3 設(shè)計思路7.5.4 程序清單7.5.5 運行結(jié)果7.6 IP 地址排序7.6.1 項目簡介7.6.2 知識要點7.6.3 設(shè)計思路7.6.4 程序清單7.6.5 運行結(jié)果第二部分綜合篇8.1 益智游戲之七巧板8.1

10、.1 項目需求8.1.2 知識要點8.1.3 設(shè)計流程8.1.4 程序清單8.2.1 項目需求8.2.2 知識要點8.2.3 設(shè)計流程8.2.4 程序清單8.2.5 運行測試8.4 景區(qū)旅游信息管理系統(tǒng)8.4.1 項目需求8.4.2 知識要點8.4.3 設(shè)計流程8.4.4 程序清單8.4.5 運行測試11第一部分 基礎(chǔ)篇第一章 線性表線性表是數(shù)據(jù)結(jié)構(gòu)中最簡單、最常用的一種線性結(jié)構(gòu)，也是學習數(shù)據(jù)結(jié)構(gòu)全部內(nèi)容的基礎(chǔ)，其掌握的好壞直接影響著后繼知識的學習。本章通過四個模擬項目來學習線性表的順序和鏈式存儲結(jié)構(gòu)，首先通過使用有關(guān)數(shù)組的操作實現(xiàn)學生成績管理，其次通過使用有關(guān)線性鏈表的操作實現(xiàn)考試報名管理，

11、然后通過使用循環(huán)鏈表的操作實現(xiàn)約瑟夫生者死者游戲。1.1 學生成績管理1.1.1 項目簡介學生成績管理是學校教務(wù)部門日常工作的重要組成部分，其處理信息量很大。本項目是對學生成績管理的簡單模擬， 用菜單選擇方式完成下列功能： 輸入學生數(shù)據(jù)； 輸出學生數(shù)據(jù)； 學生數(shù)據(jù)查詢；添加學生數(shù)據(jù)；修改學生數(shù)據(jù)；刪除學生數(shù)據(jù)。1.1.2 設(shè)計思路本項目的實質(zhì)是完成對學生成績信息的建立、查找、插入、修改、刪除等功能，可以首先定義項目的數(shù)據(jù)結(jié)構(gòu)，然后將每個功能寫成一個函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以驗證各個函數(shù)功能并得出運行結(jié)果。1.1.3 數(shù)據(jù)結(jié)構(gòu)本項目的數(shù)據(jù)是一組學生的成績信息，每條學生的成績信息由學

12、號、姓名和成績組成，這組學生的成績信息具有相同特性，屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。由此可以看出，這些數(shù)據(jù)具有線性表中數(shù)據(jù)元素的性質(zhì)，所以該系統(tǒng)的數(shù)據(jù)采用線性表來存儲。順序表是線性表的順序存儲結(jié)構(gòu)，是指用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素。 在順序存儲結(jié)構(gòu)下， 邏輯關(guān)系相鄰的兩個元素在物理位置上也相鄰， 這是順序表的特點。本項目可以采用順序表的線性表順序存儲結(jié)構(gòu)。若一個數(shù)據(jù)元素僅占一個存儲單元，則其存儲方式參見圖 1-1 。從圖 1-1 中可見，第i 個數(shù)據(jù)元素的地址為Loc(ai)=loc(a1)+(i-1)假設(shè)線性表中每個元素占用 k 個存儲單元，那么在順序表中，線

13、性表的第 i 個元素的存儲位置與第1 個元素的存儲位置的關(guān)系是Loc(ai)=loc(a1)+(i-1)*k這里Loc(ai)是第i個元素的存儲位置，10c(a1)是第1個元素的存儲位置，也稱為線性表 的基址。顯然，順序表便于進行隨機訪問，故線性表的順序存儲結(jié)構(gòu)是一種隨機存儲結(jié)構(gòu)。順序表適宜于做查找這樣的靜態(tài)操作；順序存儲的優(yōu)點是存儲密度大，存儲空間利用率高。缺點是插入或刪除元素時不方便。由于 C 語言的數(shù)組類型也有隨機存儲的特點， 一維數(shù)組的機內(nèi)表示就是順序結(jié)構(gòu)。 因此，可用 C 語言的一維數(shù)組實現(xiàn)線性表的順序存儲。 數(shù)組實現(xiàn)線性表的順序存儲的優(yōu)點是可以隨機存取表中任一元素 O(1) ，存儲

14、空間使用緊湊；缺點是在插入，刪除某一元素時，需要移動大量元素 O(n) ，預(yù)先分配空間需按最大空間分配，利用不充分，表容量難以擴充。用結(jié)構(gòu)體類型定義每個學生數(shù)據(jù)，故該數(shù)組中的每個數(shù)據(jù)的結(jié)構(gòu)可描述為：typedef struct STU char stuno10;/學號char name10;/姓名f1oat score;/成績 E1emType;1.1.4 程序清單#inc1ude<iostream.h>#inc1ude<iomanip.h>#inc1ude<ma11oc.h>#inc1ude<string.h>#define MaxListSi

15、ze 20#define EQUAL 1typedef struct STUchar stuno 10;char name 10;f1oat score;ElemType;class Listprivate:/線性表的數(shù)組表示ElemType elemMaxListSize;int length;int MaxSize;public:/輸入學生數(shù)據(jù)void init(List *L,int ms);/刪除所有學生數(shù)據(jù)void DestroyList(List &L)free(&L);/將順序表置為空表void ClearList()length=0;/判斷順序表是否為空表boo

16、l ListEmpty()return length=0;/判斷順序表是否為滿bool ListFull()return length=MaxSize;/刪除某個學生數(shù)據(jù)bool ListDelete(int,ElemType &e);/遍歷順序表void ListTraverse();/返回順序表的長度int ListLength();/學生數(shù)據(jù)查詢void GetElem(int,ElemType *);/修改學生數(shù)據(jù)bool UpdateList(ElemType& e,ElemType);/添加學生數(shù)據(jù)bool ListInsert(int,ElemType &

17、);/對學生數(shù)據(jù)按升序或降序輸出void printlist(int);void List:init(List *L,int ms)*L=(List *)malloc(sizeof(List);(*L)->length=0;(*L)->MaxSize=ms;int List:ListLength()return length;bool List:ListDelete(int mark,ElemType &e)int i,j;if(ListEmpty() return false;if(mark>0) /刪除表頭元素e=elem0;for(i=1; i<lengt

18、h; i+)elemi-1=elemi;else /刪除表尾元素if(mark<0) e=elemlength-1;else /刪除值為 e 的元素for(i=0;i<length;i+)if(strcmp(,)=0) break;if(i>=length) return false;else e=elemi;for(j=i+1;j<length;j+)elemj-1=elemj;length-;return true;void List:ListTraverse()for(int i=0;i<length;i+)cout<&

19、lt;setw(8)<<;cout<<setw(10)<<elemi.stuno;cout<<setw(9)<<elemi.age;cout<<setw(8)<<elemi.score<<endl;void List:GetElem(int i,ElemType *e)*e=elemi; bool List:EqualList(ElemType *e1,ElemType *e2) if (strcmp(e1->name,e2->name)return false;if

20、 (strcmp(e1->stuno,e2->stuno)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(e1->name,e2->name)<=0) return true;else return false;bool List:LocateElem(ElemType e,

21、int type) int i;switch (type) case EQUAL:for(i=0;i<length;i+)if(EqualList(&elemi,&e)return true;break;default:break;return false;/修改學生數(shù)據(jù)bool List:UpdateList(ElemType& e,ElemType e1)for(int i=0;i<length;i+)if(strcmp(,)=0) elemi=e1;return true;return false;)bool List:

22、ListInsert(int i,ElemType &e)ElemType *p,*q;if(i<1|i>length+1) return false;q=&elemi-1;for(p=&elemlength-1;p>=q;-p)*(p+1)=*p;*q=e;+length;return true;)/對學生成績按升序或降序輸出void List:printlist(int mark)int* b=new intlength;int i,k;cout<<" 姓名 學號 成績n"if(mark!=0)for(i=0; i&

23、lt;length;i+) bi=i;for(i=0; i<length;i+) k=i;for(int j=i+1;j<length;j+) if(mark=1&&elembj.score<elembk.score) k=j;if(mark=-1&&elembk.score<elembj.score) k=j;if(k!=i) int x=bi;bi=bk;bk=x;for(int i=0;i<length;i+)cout<<setw(8)<<;cout<<setw(10)

24、<<elembi.stuno;cout<<setw(9)<<elembi.age;cout<<setw(8)<<elembi.score<<endl;else for(i=0;i<length;i+)cout<<setw(8)<<;cout<<setw(10)<<elemi.stuno;cout<<setw(9)<<elemi.age;cout<<setw(8)<<elemi.score<<

25、endl;void main() cout<<"linelist1m.cpp 運行結(jié)果 :n"ElemType e,e1,e2,e3,e4,e5,e6;List *La,*Lb,*Lc;int k;cout<<" 首先調(diào)用插入函數(shù).n"La->init(&La,4);strcpy(,"stu1");strcpy(e1.stuno,"100001");e1.age=22;e1.score=88;La->ListInsert(1,e1);strcpy(e2.na

26、me,"stu2");strcpy(e2.stuno,"100002");e2.age=21;e2.score=79;La->ListInsert(2,e2);strcpy(,"stu3");strcpy(e3.stuno,"100003");e3.age=19;e3.score=87;La->ListInsert(3,e3);La->printlist(0);cout<<" 表 La 長 :"<<La->ListLength()&l

27、t;<endl;cin.get();Lb->init(&Lb,4);strcpy(,"zmofun");strcpy(e4.stuno,"100001");e4.age=20;e4.score=94;Lb->ListInsert(1,e4);strcpy(,"bobjin");strcpy(e5.stuno,"100002");15e5.age=23;e5.score=69;Lb->ListInsert(2,e5);strcpy(,"

28、;stu1");strcpy(e6.stuno,"100001");e6.age=22;e6.score=88;Lb->ListInsert(3,e6);Lb->printlist(0);cout<<" 表 Lb 長 :"<<Lb->ListLength()<<endl;cin.get();k=Lc->ListDelete(-1,e6);if(k=0) cout<<" 刪除失敗 !n"else cout<<" 刪除成功 !n&quo

29、t;cout<<" 輸出表 Lc:n"Lc->printlist(0);cin.get();cout<<" 按成績升序輸出表Lcn"Lc->printlist(1);cin.get();cout<<" 按成績降序輸出表Lcn"Lc->printlist(-1);cin.get();1.1.5 運行結(jié)果首先建立學生信息管理，輸出結(jié)果為：姓名學號成績Stu110000180Stu210000291Stu310000356其次查詢學號為 100002 的學生的成績，輸出結(jié)果為：91再次調(diào)

30、用插入函數(shù)，插入 Stu4 成功！輸入結(jié)果為：姓名 學號成績Stu110000180Stu210000291Stu310000356Stu410000475最后刪除Stu2成果!輸出結(jié)果為:姓名學號成績Stu110000180Stu310000356Stu410000475查詢不及格的學生，輸出結(jié)果為：輸出結(jié)果為：Stu3100003561.2 考試報名管理1.2.1 項目簡介考試報名工作給各高校報名工作帶來了新的挑戰(zhàn)， 給教務(wù)管理部門增加了很大的工作量，報名數(shù)據(jù)手工錄入既費時又會不可避免地出現(xiàn)錯誤，同時也給不少學生以可乘之機。本項目是對考試報名管理的簡單模擬，用菜單選擇方式完成下列功能：輸入

31、考生信息；輸出考生信息；查詢考生信息；添加考生信息；修改考生信息；刪除考生信息。1.2.2 設(shè)計思路本項目的實質(zhì)是完成對考生信息的建立、查找、插入、修改、刪除等功能，可以首先定義項目的數(shù)據(jù)結(jié)構(gòu)，然后將每個功能寫成一個函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以驗證各個函數(shù)功能并得出運行結(jié)果。1.2.3 數(shù)據(jù)結(jié)構(gòu)本項目的數(shù)據(jù)是一組考生信息，每條考生信息由準考證號、姓名、性別、年齡、報考類別等信息組成，這組考生信息具有相同特性，屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。由此可以看出，這些數(shù)據(jù)也具有線性表中數(shù)據(jù)元素的性質(zhì)，所以該系統(tǒng)的數(shù)據(jù)可以采用線性表來存儲。從上一節(jié)的例子中可見，線性表的順序存儲

32、結(jié)構(gòu)的特點是邏輯關(guān)系相鄰的兩個元素在物理位置上也相鄰，因此可以隨機存儲表中任一元素，它的存儲位置可用一個簡單、直觀的公式來表示。然而，從另一個方面來看，這個特點也鑄成了這種存儲結(jié)構(gòu)的弱點：在做插入或刪除操作時， 需要移動大量元素。 為克服這一缺點， 我們引入另一種存儲形式鏈式存儲。鏈式存儲是線性表的另一種表示方法， 由于它不要求邏輯上相鄰的元素在物理位置上也相鄰， 因此它沒有順序存儲結(jié)構(gòu)的弱點，但同時也失去了順序表可隨機存取的特點。鏈式存儲的優(yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。事實上，鏈表插入、刪除運算的快捷是以空間代價來換取時間。順序表適宜于做查找這樣

33、的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。本項目對考生數(shù)據(jù)主要進行插入、 刪除、 修改等操作， 所以采用鏈式存儲結(jié)構(gòu)比較適合。 用結(jié)構(gòu)體類型定義每個考生信息，故該單鏈表中的每個結(jié)點的結(jié)構(gòu)可描述為：typedef struct examinee char examno10;/準考證號char name10;/姓名char sex;float age;char examtype5;/成績 ElemType;1.2.4 程序清單/單鏈表的類定義linklist3.h# i

34、fndef linklist3H# define linklist3H# define LEN 30/定義ElemType 為 inttypedef int ElemType;/單鏈表中結(jié)點的類型typedef struct LNodeElemType data;/ 值域LNode *next;/指針域LNode;class LinkListLNode *head;public:17/構(gòu)造函數(shù)LinkList();/析構(gòu)函數(shù)LinkList();/清空單鏈表void ClearList();/求單鏈表長度int ListSize();/檢查單鏈表是否為空bool ListEmpty();/返回

35、單鏈表中指定序號的結(jié)點值ElemType GetElem(int pos);/遍歷單鏈表void TraverseList(void f(ElemType &);/從單鏈表中查找元素bool FindList(ElemType& item);/更新單鏈表中的給定元素bool UpdateList(const ElemType& item,ElemType e);/向單鏈表插入元素,mark=0 插在表首,否則插在表尾void InsertList(ElemType item,int mark);/從單鏈表中刪除元素 , mark 為要刪除的第幾個元素bool Delet

36、eList(ElemType& item,int mark);/對單鏈表進行有序排列 mark>0 升序 ,否則降序void pailie(int mark=1);/對單鏈表進行有序輸出 ,mark=0 不排序 ,mark>0 升序 ,mark<0 降序void OrderOutputList(int mark=0);#endif/linklist3.cpp#include "linklist3.h"LinkList:LinkList()/ 構(gòu)造函數(shù)head=new LNode;head->next=NULL;LinkList:LinkLis

37、t()/ 析構(gòu)函數(shù)LNode *p=head->next ,*q;while(p) q=p->next ;free(p);p=q;void LinkList:ClearList()/ 清空單鏈表LNode*p=head->next ,*q;while(p)q=p->next;free(p);p=q;head->next =NULL;int LinkList:ListSize()/ 求單鏈表長度LNode*p=head->next ;int i=0;while(p)i+;p=p->next ;return i;bool LinkList:ListEmpt

38、y()/ 檢查單鏈表是否為空return ListSize()=0;/返回單鏈表中指定序號的結(jié)點值ElemType LinkList:GetElem(int pos) LNode*p=head->next ;int i=1;while(p)if(i+=pos)return p->data ;p=p->next ;#return head->data ;void LinkList:TraverseList(void f(ElemType &)/ 遍歷單鏈表LNode*p=head->next ;while(p)f(p->data );p=p->n

39、ext ;bool LinkList:FindList(ElemType& item)/ 從單鏈表中查找元素LNode*p=head->next ;while(p)if(p->data=item)return 1;p=p->next ;return 0;/更新單鏈表中的給定元素bool LinkList:UpdateList(const ElemType &item,ElemType e) LNode*p=head->next ;bool flag=0;while(p)if(p->data=item)p->data=e;flag=1;p=p-

40、>next ;return flag;/向單鏈表插入元素void LinkList:InsertList(ElemType item,int mark)LNode *q= new LNode;q->data = item;if(mark=0)q->next = head->next ;head->next=q;return;LNode *p=head;while(p->next)p=p->next ;q->next =NULL;p->next =q;從單鏈表中刪除元素bool LinkList:DeleteList(ElemType&

41、; item,int mark) if(ListEmpty()|mark<1|mark>ListSize()return 0;LNode *p=head,*q;for(int i=0;i<mark-1;i+)p=p->next;item=p->next->data;q=p->next->next ;free(p->next );p->next=q;return 1;/對單鏈表進行有序排列mark>0升序，否則降序void LinkList二pailie(int mark)ElemType aLEN+1;LNode *p=head

42、->next;int k ;for(k=1;p!=NULL;k+,p=p->next )ak=p->data;k-;for(int i=1;i<k;i+)for(int j=1;j<=k-i;j+)int t;if( mark>0&&aj>aj+1|mark<0&&aj<aj+1)t=aj+1;aj+1=aj;aj=t;p=head->next;for(int j=1;j<=k;j+,p=p->next ) p->data=aj;/對單鏈表進行有序輸出void LinkList:Ord

43、erOutputList(int mark)ElemType aLEN+1;LNode *p=head->next;int k ;for( k=1;p!=NULL;k+,p=p->next )ak=p->data;k-;for(int i=1;i<k;i+)for(int j=1;j<=k-i;j+)int t;if( mark>0&&aj>aj+1|mark<0&&aj<aj+1)t=aj+1;aj+1=aj;aj=t;for(int j=1;j<=k;j+)cout<<aj<<

44、;""#include<iostream.h>#include<iomanip.h>#include<stdlib.h>/#include<stdio.h>#include"linklist3.cpp"void ff(int &a)/ 用于遍歷的函數(shù)cout<<a<<""void main()cout<<"nlinklist3m.cpp 運行結(jié)果 :n"int init_size,seed,xu;cout<<”首

45、先請構(gòu)造單鏈表list"cout<<"n 初始化長度(1-30):"cin>>init_size;seed=150;cout<<" 是否排序 :(=0 不排序 ,=1 升序 ,=-1 降序 ):"cin>>xu;cout<<"n 單鏈表 list 構(gòu)造成功 !"<<"n 它是 :"list.TraverseList(ff);cout<<"n 它為空嗎 ?(1:是;0:不是 ):"<<list

46、.ListEmpty();cout<<"n 長度為:"<<list.ListSize() ;int i;cout<<"n 請輸入你想得到第幾個元素的值(1-"<<init_size<<"):"cin>>i;cout<<"單鏈表 list 中第"<<i<<"的值是"<<list.GetElem(i);int it;cout<<"n 請輸入你想刪除第幾個元素的

47、值(1-"<<init_size<<"):"cin>>i;list.DeleteList(it,i);cout<<"n 單鏈表 list 刪除第 "<<i<<" 個元素 "<<"'"<<it<<"'"<<" 后變?yōu)?:"list.TraverseList(ff);/ 對單鏈表 list 每個數(shù)進行遍歷.int news,olds;c

48、out<<"n 請輸入要被修改的元素:" cin>>olds;cout<<"請輸入修改后要變成的元素："cin>>news;list.UpdateList(olds,news);cout<<"n 修改后單鏈表list 變?yōu)?:"list.TraverseList(ff);cout<<"n 下面請構(gòu)造單鏈表list2"cout<<"n 請輸入單鏈表list2 初始化長度(1-30):"cin>>init

49、_size;seed=120;cout<<"請選擇是否排序：(二0不排序,=1升序,=-1降序):"；cin>>xu;cout<<"n 按回車鍵結(jié)束."cin.get();cin.get();1.2.5 運行結(jié)果1.3 約瑟夫生者死者游戲1.3.1 項目簡介約瑟夫生者死者游戲的大意是： 30 個旅客同乘一條船，因為嚴重超載，加上風高浪大，危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定 30 個人圍成一圈，由第一個人開始，依次報數(shù)，數(shù)到第9 人，便把他投入

50、大海中，然后從他的下一個人數(shù)起，數(shù)到第 9 人，再將他投入大海，如此循環(huán)，直到剩下15 個乘客為止。問哪些位置是將被扔下大海的位置。1.3.2 設(shè)計思路本游戲的數(shù)學建模如下：假設(shè)n個旅客排成一個環(huán)形，依次順序編號1, 2,，no從某個指定的第1 號開始，沿環(huán)計數(shù)，每數(shù)到第m 個人就讓其出列，且從下一個人開始重新計數(shù)，繼續(xù)進行下去。這個過程一直進行到剩下k 個旅客為止。本游戲的要求用戶輸入的內(nèi)容包括：1. 旅客的個數(shù)，也就是n 的值；2. 離開旅客的間隔數(shù)，也就是m 的值；3. 所有旅客的序號作為一組數(shù)據(jù)要求存放在某種數(shù)據(jù)結(jié)構(gòu)中。本游戲要求輸出的內(nèi)容是包括1. 離開旅客的序號；2. 剩余旅客的序

51、號；所以，根據(jù)上面的模型分析及輸入輸出參數(shù)分析，可以定義一種數(shù)據(jù)結(jié)構(gòu)后進行算法實現(xiàn)。1.3.3 數(shù)據(jù)結(jié)構(gòu)為了解決這一問題， 可以用長度為 30 的數(shù)組作為線性存儲結(jié)構(gòu)， 并把該數(shù)組看成是一個首尾相接的環(huán)形結(jié)構(gòu)， 那么每投入大海一個乘客， 就要在該數(shù)組的相應(yīng)位置做一個刪除標記，該單元以后就不再作為計數(shù)單元。這樣做不僅算法較為復(fù)雜，而且效率低，還要移動大量的元素。用單循環(huán)鏈表解決這一問題，實現(xiàn)的方法相對要簡單得多。首先要定義鏈表結(jié)點，單循環(huán)鏈表的結(jié)點結(jié)構(gòu)與一般的結(jié)點結(jié)構(gòu)完全相同，只是數(shù)據(jù)域用一個整數(shù)來表示位置；然后將它們組成具有30 個結(jié)點的單循環(huán)鏈表。 接下來從位置為 1 的結(jié)點開始數(shù)， 數(shù)到第

52、 8 個結(jié)點，就將下一個結(jié)點從循環(huán)鏈表中刪去，然后再從刪去結(jié)點的下一個結(jié)點開始數(shù)起，數(shù)到第 8 個結(jié)點，再將其下一個結(jié)點刪去，如此進行下去，直到剩下15 個結(jié)點為止。為了不失一般性，將30 改為一個任意輸入的正整數(shù)n ，而報數(shù)上限(原為9)也為一個任選的正整數(shù) k 。這樣該算法描述如下：(1) 創(chuàng)建含有 n 個結(jié)點的單循環(huán)鏈表；(2) 生著與死者的選擇：p 指向鏈表的第一個結(jié)點，初始i 置為 1 ；while(i<=n/2)/刪除一半的結(jié)點從p指向的結(jié)點沿鏈前進 k-1步；刪除第 k 個結(jié)點( q 所指向的結(jié)點) ；p 指向 q 的下一個結(jié)點；輸出其位置q->data;1 自增 1

53、；(3) 輸出所有生者的位置。1.3.4 程序清單LinkList InitRing(int n, LinkList R)/尾插入法建立單循環(huán)鏈表函數(shù)ListNode *p, *q;int I;R=q=(LinkNode *)malloc(sizeof(LinkNode);for(i=1;i<n;i+)p=(LinkNode *)malloc(sizeof(LinkNode);q->data=i;q->next=p;q=p;p->data=n;p->next=R;R=p;return R;LinkList DeleteDeath(int n, int k, Lin

54、kList R)/生者與死者的選擇int i, j;ListNode *p, *q;p=R;for(i=1; i<n/2; i+)/刪除一半結(jié)點for(j=1; j<k-1; j+) / 沿鏈前進 k-1 步p=p->next;q=p->next;p->next=q->next;printf( “%4d” , q->data);free(q);R=p; return R;void OutRing(int n, LinkList R)/輸出所有生者int i;LinkNode *p;p=R;for(i=1;i<=n/2; i+, p=p->n

55、ext)printf( “%4d”, p->data)有了上述算法分析和設(shè)計之后，實現(xiàn)就比較簡單了。首先要定義一個鏈表結(jié)構(gòu)類型，然后編寫一個主函數(shù)調(diào)用上面已定義好的函數(shù)即可。主函數(shù)的源程序如下：#include<stdio.h>#include<stdlib.h>typedef struct nodeint data;struct node * next;ListNode;typedef ListNode * LinkList;void main()LinkList R;int n,k;LinkList InitRing(int n, LinkList R);Li

56、nkList DeleteDeath(int n, int k, LinkList R);void OutRing(int n, LinkList R);printf( “總?cè)藬?shù) n. 報數(shù)上限 k= ”);scanf( “%d%d ”,&n, &k);R=InitRing(n, R);R=DeleteDeath(n, k, R);OutRing(n, R);1.3.5 運行結(jié)果編譯運行上述程序，提示：總?cè)藬?shù)n. 報數(shù)上限 k=輸入 30 和 9 后并“回車”可得出如下結(jié)果：918 276 16267 19 30 12 248 225 232125 282912 34 10 1

57、1 1314 1517 201.4 約瑟夫雙向生死游戲1.4.1 項目簡介約瑟夫雙向生死游戲是在約瑟夫生者死者游戲的基礎(chǔ)上，正向計數(shù)后反向計數(shù)，然后再正向計數(shù)。 具體描述如下： 30 個旅客同乘一條船， 因為嚴重超載， 加上風高浪大， 危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定 30 個人圍成一圈，由第一個人開始，順時針依次報數(shù)，數(shù)到第9人，便把他投入大海中，然后從他的下一個人數(shù)起，逆時針數(shù)到第 5 人，將他投入大海，然后從他逆時針的下一個人數(shù)起，順時針數(shù)到第 9 人，再將他投入大海，如此循環(huán)，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。1.4.2 設(shè)計思路本游戲的數(shù)學建模如下：假設(shè)n個旅客排成一個環(huán)形，依次順序編號1, 2,，no從某個指定的第1 號開始，沿環(huán)計數(shù)，數(shù)到第m 個人就