數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目

1、風從水上走過，留下粼粼波紋；駱駝從沙漠上走過，留下深深的腳印 ；哨鴿從天空飛過，留下串串歡韻 ；歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時代的舞臺走過，將給社會留下些什么？花從春走過，留下縷縷花香；葉從夏走過，留下片片蔭涼；風從秋走過，留下陣陣金浪；雪從冬走過，留下種種希望。啊，朋友，我們從人生的四季走過，將給人生留下些什么？數(shù)據(jù)結(jié)構(gòu)實踐教程沒有落日般的瑰麗，沒有流云般的飄逸，但可以有水晶般的清純與透明。沒有大山般的巍峨，沒有湖水般的輕柔，但可以有巖石般的堅毅與穩(wěn)重。沒有大海般的浩瀚，沒有瀑布般的飛瀉，但可以有泥土般的樸素與隨和。第一部分基礎(chǔ)篇第一章線性表1.1 學生成績管理1.1.1

2、項目簡介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.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.4 程序清單2.1.5 運行結(jié)果2.2

3、 八皇后問題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)計程序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

4、 數(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 程序清單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

5、設(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 程序清單5.4.5 運行結(jié)果第二部分綜合篇1.1 景區(qū)旅游信息管理系統(tǒng)1.1.1 項目需求1.1.2 知識要點1.1.3 設(shè)計流程1.1.4 程序清單1.1.5 運行測試風從水上走過，留下粼粼波紋；駱駝從沙漠上走過，留下深深的腳印 ；哨鴿從天空飛過，留下串串歡韻 ；歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時代的舞臺走過，將給社會留下些什么？花從春走過，留下縷縷花香；葉從夏走過，留下片片蔭涼；風從秋走過，留下陣陣金浪；雪從冬走過，

6、留下種種希望。啊，朋友，我們從人生的四季走過，將給人生留下些什么？第一部分基礎(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)考試報名管理，然后通過使用循環(huán)鏈表的操作實現(xiàn)約瑟夫生者死者游戲。1.1 學生成績管理1.1.1 項目簡介學生成績管理是學校教務(wù)部門日常工作的重要組成部分，其處理信息量很大。本項目是對學生成績管理的簡單模擬，用菜單選擇方式完成下列功能：輸入學生數(shù)據(jù)；輸出學生數(shù)

7、據(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ù)是一組學生的成績信息，每條學生的成績信息由學號、姓名和成績組成，這組學生的成績信息具有相同特性，屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。由此可以看出，這些數(shù)據(jù)具有線性表中數(shù)據(jù)元素的性質(zhì)，所以該系統(tǒng)的數(shù)據(jù)采用線性表來存儲。順序表是線性表的順序存儲結(jié)構(gòu)，是指用一組連續(xù)的內(nèi)存單元依次存放線性表

8、的數(shù)據(jù)元素。在順序存儲結(jié)構(gòu)下，邏輯關(guān)系相鄰的兩個元素在物理位置上也相鄰，這是順序表的特點。沒有落日般的瑰麗，沒有流云般的飄逸，但可以有水晶般的清純與透明。沒有大山般的巍峨，沒有湖水般的輕柔，但可以有巖石般的堅毅與穩(wěn)重。沒有大海般的浩瀚，沒有瀑布般的飛瀉，但可以有泥土般的樸素與隨和。風從水上走過，留下粼粼波紋；駱駝從沙漠上走過，留下深深的腳印 ；哨鴿從天空飛過，留下串串歡韻 ；歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時代的舞臺走過，將給社會留下些什么？花從春走過，留下縷縷花香；葉從夏走過，留下片片蔭涼；風從秋走過，留下陣陣金浪；雪從冬走過，留下種種希望。啊，朋友，我們從人生的四季走過，將給

9、人生留下些什么？本項目可以采用順序表的線性表順序存儲結(jié)構(gòu)。若一個數(shù)據(jù)元素僅占一個存儲單元，則其存儲方式參見圖1-1。從圖1-1中可見，第i個數(shù)據(jù)元素的地址為Loc(ai)=loc(a1)+(i-1)假設(shè)線性表中每個元素占用k個存儲單元，那么在順序表中，線性表的第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)點是存儲密度大，存儲空間利

10、用率高。缺點是插入或刪除元素時不方便。由于C語言的數(shù)組類型也有隨機存儲的特點，一維數(shù)組的機內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語言的一維數(shù)組實現(xiàn)線性表的順序存儲。數(shù)組實現(xiàn)線性表的順序存儲的優(yōu)點是可以隨機存取表中任一元素0(1),存儲空間使用緊湊；缺點是在插入，刪除某一元素時，需要移動大量元素0(n),預(yù)先分配空間需按最大空間分配，利用不充分，表容量難以擴充。用結(jié)構(gòu)體類型定義每個學生數(shù)據(jù)，故該數(shù)組中的每個數(shù)據(jù)的結(jié)構(gòu)可描述為：typedefstructSTUcharstuno10;/學號charname10;/姓名floatscore;/成績ElemType;1.1.4 程序清單#include<

11、;iostream.h>#include<iomanip.h>#include<malloc.h>#include<string.h>#defineMaxListSize20#defineEQUAL1typedefstructSTUcharstuno10;charname10;floatscore;ElemType;classListprivate:/線性表的數(shù)組表示ElemTypeelemMaxListSize;intlength;intMaxSize;public:輸入學生數(shù)據(jù)voidinit(List*L,intms);刪除所有學生數(shù)據(jù)voidD

12、estroyList(List&L)free(&L);將順序表置為空表voidClearList()length=0;判斷順序表是否為空表boolListEmpty()returnlength=0;判斷順序表是否為滿boolListFull()returnlength=MaxSize;刪除某個學生數(shù)據(jù)boolListDelete(int,ElemType&e);遍歷順序表voidListTraverse();返回順序表的長度intListLength();學生數(shù)據(jù)查詢voidGetElem(int,ElemType*);修改學生數(shù)據(jù)boolUpdateList(Elem

13、Type&e,ElemType);添加學生數(shù)據(jù)boolListInsert(int,ElemType&);/對學生數(shù)據(jù)按升序或降序輸出voidprintlist(int);；voidList:init(List*L,intms)*L=(List*)malloc(sizeof(List);(*L)->length=0;(*L)->MaxSize=ms;intList:ListLength()returnlength;boolList:ListDelete(intmark,ElemType&e)inti,j;if(ListEmpty()returnfalse;i

14、f(mark>0)刪除表頭元素e=elem0;for(i=1;i<length;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)returnfalse;elsee=elemi;for(j=i+1;j<length;j+)elemj-1=elemj;length-;returntrue;voidList:ListTraverse()for(in

15、ti=0;i<length;i+)cout<<setw(8)<<;cout<<setw(10)<<elemi.stuno;cout<<setw(9)<<elemi.age;cout<<setw(8)<<elemi.score<<endl;voidList:GetElem(inti,ElemType*e)*e=elemi;boolList:EqualList(ElemType*e1,ElemType*e2)if(strcmp(e1->name,e2->

16、name)returnfalse;if(strcmp(e1->stuno,e2->stuno)returnfalse;if(e1->age!=e2->age)returnfalse;if(e1->score!=e2->score)returnfalse;returntrue;boolList:Less_EqualList(ElemType*e1,ElemType*e2)if(strcmp(e1->name,e2->name)<=0)returntrue;elsereturnfalse;boolList:LocateElem(ElemType

17、e,inttype)inti;switch(type)caseEQUAL:for(i=0;i<length;i+)if(EqualList(&elemi,&e)returntrue;break;default:break;returnfalse;修改學生數(shù)據(jù)boolList:UpdateList(ElemType&e,ElemTypee1)for(inti=0;i<length;i+)if(strcmp(,)=0)elemi=e1;returntrue;returnfalse;boolList:ListInsert(inti,

18、ElemType&e)ElemType*p,*q;if(i<1|i>length+1)returnfalse;q=&elemi-1;for(p=&elemlength-1;p>=q;-p)*(p+1)=*p;*q=e;+length;returntrue;/對學生成績按升序或降序輸出voidList:printlist(intmark)int*b=newintlength;inti,k;cout<<"姓名學號成績n"if(mark!=0)for(i=0;i<length;i+)bi=i;for(i=0;i<l

19、ength;i+)k=i;for(intj=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)intx=bi;bi=bk;bk=x;for(inti=0;i<length;i+)cout<<setw(8)<<;cout<<setw(10)<<elembi.stuno;cout<<setw(9)&l

20、t;<elembi.age;cout<<setw(8)<<elembi.score<<endl;elsefor(i=0;i<length;i+)cout<<setw(8)<<;cout<<setw(10)<<elemi.stuno;cout<<setw(9)<<elemi.age;cout<<setw(8)<<elemi.score<<endl;voidmain()cout<<"linelist1m

21、.cpp運行結(jié)果：n"ElemTypee,e1,e2,e3,e4,e5,e6;List*La,*Lb,*Lc;intk;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(,"stu2");strcpy(e2.stuno,"100002&q

22、uot;);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()<<endl;cin.get();Lb->init(&Lb,4);strcpy(e4.n

23、ame,"zmofun");strcpy(e4.stuno,"100001");e4.age=20;e4.score=94;Lb->ListInsert(1,e4);strcpy(,"bobjin");strcpy(e5.stuno,"100002");e5.age=23;e5.score=69;Lb->ListInsert(2,e5);strcpy(,"stu1");strcpy(e6.stuno,"100001");e6.age=2

24、2;e6.score=88;Lb->ListInsert(3,e6);Lb->printlist(0);cout<"表Lb長:"<<Lb->ListLength()<<endl;cin.get();k=Lc->ListDelete(-1,e6);沒有落日般的瑰麗，沒有流云般的飄逸，但可以有水晶般的清純與透明。沒有大山般的巍峨，沒有湖水般的輕柔，但可以有巖石般的堅毅與穩(wěn)重。沒有大海般的浩瀚，沒有瀑布般的飛瀉，但可以有泥土般的樸素與隨和。風從水上走過，留下粼粼波紋；駱駝從沙漠上走過，留下深深的腳印 ；哨鴿從天空飛過，留下串串

25、歡韻 ；歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時代的舞臺走過，將給社會留下些什么？花從春走過，留下縷縷花香；葉從夏走過，留下片片蔭涼；風從秋走過，留下陣陣金浪；雪從冬走過，留下種種希望。啊，朋友，我們從人生的四季走過，將給人生留下些什么？if(k=0)cout<<"刪除失??！n"elsecout<<"刪除成功!n"cout<<"輸出表Lc:n"Lc->printlist(0);cin.get()；cout<<"按成績升序輸出表Lcn"Lc->pri

26、ntlist(1);cin.get();cout<<"按成績降序輸出表Lcn"Lc->printlist(-1);cin.get();1.1.5 運行結(jié)果首先建立學生信息管理，輸出結(jié)果為：姓名學號成績Stu110000180Stu210000291Stu310000356其次查詢學號為100002的學生的成績，輸出結(jié)果為：91再次調(diào)用插入函數(shù)，插入Stu4成功！輸入結(jié)果為姓名學號成績Stu110000180Stu210000291Stu310000356Stu410000475最后刪除Stu2成果：!輸出結(jié)果為：姓名學號成績Stu110000180Stu3

27、10000356Stu410000475查詢不及格的學生，輸出結(jié)果為：Stu3 10000356沒有落日般的瑰麗，沒有流云般的飄逸，但可以有水晶般的清純與透明。沒有大山般的巍峨，沒有湖水般的輕柔，但可以有巖石般的堅毅與穩(wěn)重。沒有大海般的浩瀚，沒有瀑布般的飛瀉，但可以有泥土般的樸素與隨和。風從水上走過，留下粼粼波紋；駱駝從沙漠上走過，留下深深的腳印 ；哨鴿從天空飛過，留下串串歡韻 ；歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時代的舞臺走過，將給社會留下些什么？花從春走過，留下縷縷花香；葉從夏走過，留下片片蔭涼；風從秋走過，留下陣陣金浪；雪從冬走過，留下種種希望。啊，朋友，我們從人生的四季走過

28、，將給人生留下些什么？1.2 考試報名管理1.2.1 項目簡介考試報名工作給各高校報名工作帶來了新的挑戰(zhàn)，給教務(wù)管理部門增加了很大的工作量，報名數(shù)據(jù)手工錄入既費時又會不可避免地出現(xiàn)錯誤，同時也給不少學生以可乘之機。本項目是對考試報名管理的簡單模擬，用菜單選擇方式完成下列功能：輸入考生信息；輸出考生信息；查詢考生信息；添加考生信息；修改考生信息；刪除考生信息。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ù)

29、是一組考生信息，每條考生信息由準考證號、姓名、性別、年齡、報考類別等信息組成，這組考生信息具有相同特性，屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。由此可以看出，這些數(shù)據(jù)也具有線性表中數(shù)據(jù)元素的性質(zhì)，所以該系統(tǒng)的數(shù)據(jù)可以采用線性表來存儲。從上一節(jié)的例子中可見，線性表的順序存儲結(jié)構(gòu)的特點是邏輯關(guān)系相鄰的兩個元素在物理位置上也相鄰，因此可以隨機存儲表中任一元素，它的存儲位置可用一個簡單、直觀的公式來表示。然而，從另一個方面來看，這個特點也鑄成了這種存儲結(jié)構(gòu)的弱點：在做插入或刪除操作時，需要移動大量元素。為克服這一缺點，我們引入另一種存儲形式一一鏈式存儲。鏈式存儲是線性表的另一種表示方法，由于它

30、不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構(gòu)的弱點，但同時也失去了順序表可隨機存取的特點。鏈式存儲的優(yōu)點是插入或刪除元素時很方便，使用靈活。缺點是存儲密度小，存儲空間利用率低。事實上，鏈表插入、刪除運算的快捷是以空間代價來換取時間。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。本項目對考生數(shù)據(jù)主要進行插入、刪除、修改等操作，所以采用鏈式存儲結(jié)構(gòu)比較適合。沒有落日般的瑰麗，沒有流云般的飄逸，但可以有水晶般的清純與透明。沒有大山般的

31、巍峨，沒有湖水般的輕柔，但可以有巖石般的堅毅與穩(wěn)重。沒有大海般的浩瀚，沒有瀑布般的飛瀉，但可以有泥土般的樸素與隨和。用結(jié)構(gòu)體類型定義每個考生信息，故該單鏈表中的每個結(jié)點的結(jié)構(gòu)可描述為：typedefstructexamineecharexamno10;準考證號charname10;姓名charsex;floatage;charexamtype5;成績ElemType;1.2.4 程序清單單鏈表的類定義linklist3.h#ifndeflinklist3H#definelinklist3H#defineLEN30定義ElemType為inttypedefintElemType;單鏈表中結(jié)點的類

32、型typedefstructLNodeElemTypedata;/值域LNode*next;指針域LNode;classLinkListLNode*head;public:構(gòu)造函數(shù)LinkList();析構(gòu)函數(shù)LinkList();清空單鏈表voidClearList();求單鏈表長度intListSize();沒有落日般的瑰麗，沒有流云般的飄逸，但可以有水晶般的清純與透明。沒有大山般的巍峨，沒有湖水般的輕柔，但可以有巖石般的堅毅與穩(wěn)重。沒有大海般的浩瀚，沒有瀑布般的飛瀉，但可以有泥土般的樸素與隨和。風從水上走過，留下粼粼波紋；駱駝從沙漠上走過，留下深深的腳印 ；哨鴿從天空飛過，留下串串歡韻

33、；歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時代的舞臺走過，將給社會留下些什么？花從春走過，留下縷縷花香；葉從夏走過，留下片片蔭涼；風從秋走過，留下陣陣金浪；雪從冬走過，留下種種希望。啊，朋友，我們從人生的四季走過，將給人生留下些什么？檢查單鏈表是否為空boolListEmpty();返回單鏈表中指定序號的結(jié)點值ElemTypeGetElem(intpos);遍歷單鏈表voidTraverseList(voidf(ElemType&);從單鏈表中查找元素boolFindList(ElemType&item);更新單鏈表中的給定元素boolUpdateList(constEl

34、emType&item,ElemTypee);向單鏈表插入元素，mark=0插在表首，否則插在表尾voidInsertList(ElemTypeitem,intmark);從單鏈表中刪除元素，mark為要刪除的第幾個元素boolDeleteList(ElemType&item,intmark);/對單鏈表進行有序排列mark>0升序，否則降序voidpailie(intmark=1);/對單鏈表進行有序輸出，mark=0不排序，mark>0升序，mark<0降序voidOrderOutputList(intmark=0);#endiflinklist3.cpp

35、#include"linklist3.h"LinkList:LinkList()構(gòu)造函數(shù)head=newLNode;head->next=NULL;LinkList:LinkList()析構(gòu)函數(shù)LNode*p=head->next,*q;while(p)q=p->next;free(p);p=q;voidLinkList:ClearList()清空單鏈表LNode*p=head->next,*q;while(p)q=p->next;free(p);p=q；head->next=NULL;intLinkList:ListSize()求單鏈表

36、長度LNode*p=head->next;inti=0;while(p)i+;p=p->next;returni;boolLinkList:ListEmpty()/檢查單鏈表是否為空returnListSize()=0;返回單鏈表中指定序號的結(jié)點值ElemTypeLinkList:GetElem(intpos)LNode*p=head->next;inti=1;while(p)if(i+=pos)returnp->data;p=p->next;returnhead->data;voidLinkList:TraverseList(voidf(ElemType&

37、amp;)/遍歷單鏈表LNode*p=head->next;while(p)f(p->data);p=p->next;boolLinkList:FindList(ElemType&item)/從單鏈表中查找元素LNode*p=head->next;while(p)if(p->data=item)return1;p=p->next;return0;更新單鏈表中的給定元素boolLinkList:UpdateList(constElemType&item,ElemTypee)LNode*p=head->next;boolflag=0;whi

38、le(p)if(p->data=item)p->data=e;flag=1;p=p->next;returnflag;向單鏈表插入元素voidLinkList:InsertList(ElemTypeitem,intmark)LNode*q=newLNode;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;從單鏈表中刪除元素boolLin

39、kList:DeleteList(ElemType&item,intmark)if(ListEmpty()|mark<1|mark>ListSize()return0;LNode*p=head,*q;for(inti=0;i<mark-1;i+)p=p->next;item=p->next->data;q=p->next->next;free(p->next);p->next=q;return1;/對單鏈表進行有序排列mark>0升序，否則降序voidLinkList:pailie(intmark)ElemTypeaLE

40、N+1;LNode*p=head->next;intk;for(k=1;p!=NULL;k+,p=p->next)ak=p->data;k-;for(inti=1;i<k;i+)for(intj=1;j<=k-i;j+)intt;if(mark>0&&aj>aj+1|mark<0&&aj<aj+1)t=aj+1;aj+1=aj;aj=t；p=head->next;for(intj=1;j<=k;j+,p=p->next)p->data=aj;/對單鏈表進行有序輸出voidLinkLis

41、t:OrderOutputList(intmark)ElemTypeaLEN+1;LNode*p=head->next;intk;for(k=1;p!=NULL;k+,p=p->next)ak=p->data;k-;for(inti=1;i<k;i+)for(intj=1;j<=k-i;j+)intt;if(mark>0&&aj>aj+1|mark<0&&aj<aj+1)t=aj+1;aj+1=aj;aj=t;for(intj=1;j<=k;j+)cout<<aj<<"

42、"#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#include<stdio.h>#include"linklist3.cpp"voidff(int&a)用于遍歷的函數(shù)cout<<a<<""voidmain()cout<<"nlinklist3m.cpp運行結(jié)果：n"intinit_size,seed,xu;cout<<”首先請構(gòu)造單鏈表list"

43、;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.ListEmpty();cout<<"n長

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

45、):"cin>>i;list.DeleteList(it,i);cout<<"n單鏈表list刪除第"<<i<<"個元素"<<"'"<<it<<"'"<<"后變?yōu)椋?quot;；list.TraverseList(ff);/對單鏈表list每個數(shù)進行遍歷.intnews,olds;cout<<"n請輸入要被修改的元素："；cin>>olds;

46、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_size;seed=120;cout<<"請選擇是否排序：(二0不排序,=1升序，=-1降序

47、):"cin>>xu;cout<<"n按回車鍵結(jié)束"；cin.get();cin.get();1.2.5 運行結(jié)果1.3 約瑟夫生者死者游戲1.3.1 項目簡介約瑟夫生者死者游戲的大意是：30個旅客同乘一條船，因為嚴重超載，加上風高浪大，危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定30個人圍成一圈，由第一個人開始，依次報數(shù)，數(shù)到第9人，便把他投入大海中，然后從他的下一個人數(shù)起，數(shù)到第9人，再將他投入大海，如此循環(huán)，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。1.

48、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 .剩余旅客的序號；所以，根據(jù)上面的模型分析及輸入輸出參數(shù)分析，可以定義一種數(shù)據(jù)結(jié)構(gòu)后進行算法實現(xiàn)。沒有落日般的瑰麗，沒有流云般的飄逸，但可以有水晶般的清純與透明。

49、沒有大山般的巍峨，沒有湖水般的輕柔，但可以有巖石般的堅毅與穩(wěn)重。沒有大海般的浩瀚，沒有瀑布般的飛瀉，但可以有泥土般的樸素與隨和。風從水上走過，留下粼粼波紋；駱駝從沙漠上走過，留下深深的腳印 ；哨鴿從天空飛過，留下串串歡韻 ；歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時代的舞臺走過，將給社會留下些什么？花從春走過，留下縷縷花香；葉從夏走過，留下片片蔭涼；風從秋走過，留下陣陣金浪；雪從冬走過，留下種種希望。啊，朋友，我們從人生的四季走過，將給人生留下些什么？1.3.3數(shù)據(jù)結(jié)構(gòu)為了解決這一問題，可以用長度為30的數(shù)組作為線性存儲結(jié)構(gòu)，并把該數(shù)組看成是一個首尾相接的環(huán)形結(jié)構(gòu)，那么每投入大海一個乘客

50、，就要在該數(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ù)到第8個結(jié)點，就將下一個結(jié)點從循環(huán)鏈表中刪去，然后再從刪去結(jié)點的下一個結(jié)點開始數(shù)起，數(shù)到第8個結(jié)點，再將其下一個結(jié)點刪去，如此進行下去，直到剩下15個結(jié)點為止。為了不失一般性，將30改為一個任意輸入的正整數(shù)n,而報數(shù)上限(原為9)也為一個任選的正整數(shù)

51、ko這樣該算法描述如下：(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;i自增1;(3)輸出所有生者的位置。1.3.4 程序清單LinkListInitRing(intn,LinkListR)尾插入法建立單循環(huán)鏈表函數(shù)ListNode*p,*q;intI;R=q=(LinkNode*)malloc(sizeof(LinkNode);for(i=1;i<n;i+)q->d

52、ata=i;q->next=p;q=p;p->data=n;p->next=R;R=p;returnR;LinkListDeleteDeath(intn,intk,LinkListR)/生者與死者的選擇inti,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;returnR;voidOutRing(intn,L

53、inkListR)輸出所有生者inti;LinkNode*p;p=R;for(i=1;i<=n/2;i+,p=p->next)printf(%4d”,p->data)有了上述算法分析和設(shè)計之后，實現(xiàn)就比較簡單了。首先要定義一個鏈表結(jié)構(gòu)類型，然后編寫一個主函數(shù)調(diào)用上面已定義好的函數(shù)即可。主函數(shù)的源程序如下：#include<stdio.h>#include<stdlib.h>typedefstructnodeintdata;structnode*next;ListNode;typedefListNode*LinkList;voidmain()LinkLi

54、stR;intn,k;LinkListInitRing(intn,LinkListR);LinkListDeleteDeath(intn,intk,LinkListR);voidOutRing(intn,LinkListR);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é)果：91827616267193012248225232

55、1252829123410111314151720沒有落日般的瑰麗，沒有流云般的飄逸，但可以有水晶般的清純與透明。沒有大山般的巍峨，沒有湖水般的輕柔，但可以有巖石般的堅毅與穩(wěn)重。沒有大海般的浩瀚，沒有瀑布般的飛瀉，但可以有泥土般的樸素與隨和。風從水上走過，留下粼粼波紋；駱駝從沙漠上走過，留下深深的腳印 ；哨鴿從天空飛過，留下串串歡韻 ；歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時代的舞臺走過，將給社會留下些什么？花從春走過，留下縷縷花香；葉從夏走過，留下片片蔭涼；風從秋走過，留下陣陣金浪；雪從冬走過，留下種種希望。啊，朋友，我們從人生的四季走過，將給人生留下些什么？1.4約瑟夫雙向生死游戲

56、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個旅

57、客排成一個環(huán)形，依次順序編號1,2,，no從某個指定的第1號開始，沿環(huán)計數(shù)，數(shù)到第m個人就讓其出列，然后從第m+1個人反向計數(shù)到m-k+1個人，讓其出列，然后從m-k個人開始重新正向沿環(huán)計數(shù)，再數(shù)m個人后讓其出列，然后再反向數(shù)k個人后讓其出列。這個過程一直進行到剩下q個旅客為止。本游戲的要求用戶輸入的內(nèi)容包括：1 .旅客的個數(shù)，也就是n的值；2 .正向離開旅客的間隔數(shù)，也就是m的值；3 .反向離開旅客的間隔數(shù)，也就是k的值；4 .所有旅客的序號作為一組數(shù)據(jù)要求存放在某種數(shù)據(jù)結(jié)構(gòu)中。本游戲要求輸出的內(nèi)容是包括1 .離開旅客的序號；2 .剩余旅客的序號；所以，根據(jù)上面的模型分析及輸入輸出參數(shù)分析，可以定義一種數(shù)據(jù)結(jié)構(gòu)后進行算法實現(xiàn)。3 .4.4數(shù)據(jù)結(jié)構(gòu)約瑟夫雙向生死游戲如果用單循環(huán)鏈表作為線性存儲結(jié)構(gòu)，就只能正向計數(shù)結(jié)點，反向計數(shù)比較困難，算法較為復(fù)雜，而且效率低。用雙向循環(huán)鏈表解決這一問題，實現(xiàn)的方法相沒有落日般的瑰麗，沒有流云般的飄逸，但可以有水晶般的清純與透明。沒有大山般的巍峨，沒有湖水般的輕柔，但可以有巖石般的堅毅與穩(wěn)重。沒有大海般的浩瀚，沒有瀑布般的飛瀉，但可以有泥土般的樸素與隨和。風從水上走過，留下粼粼波紋；駱駝從沙漠上走過，留下深深的腳印 ；哨鴿從天空飛過，留下串串歡韻 ；歲月從樹林穿過，留下圈圈年輪。啊，朋友，我們從時代的舞臺走過，將給社會留下