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

PAGEPAGE6數(shù)據(jù)結(jié)構(gòu)實踐教程前言數(shù)據(jù)結(jié)構(gòu)是計算機(jī)專業(yè)的必修。

主干課程之一，

它旨在使讀者學(xué)會分析研究數(shù)據(jù)對象的特性，

學(xué)會數(shù)據(jù)的組織方法，

以便選擇合適的數(shù)據(jù)邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)，

以及相應(yīng)的運(yùn)算（操作），

把現(xiàn)實世界中的問題轉(zhuǎn)化為計算機(jī)內(nèi)部的表示和處理，

這是一個良好的程序設(shè)計技能訓(xùn)練的過程。

在整個教學(xué)或?qū)W習(xí)過程中，

解題能力和技巧的訓(xùn)練是一個重要的環(huán)節(jié)。

為了幫助教師講授“數(shù)據(jù)結(jié)構(gòu)”，

滿足指導(dǎo)和評價“課程設(shè)計”的需要，

為了幫助和指導(dǎo)讀者更好地學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)這門課程，

我們特編寫了這本《數(shù)據(jù)結(jié)構(gòu)實踐教程》輔助教材，旨在彌補(bǔ)課堂教學(xué)和實驗中的不足，幫助學(xué)生充分理解和鞏固所學(xué)的基本概念、原理和方法，達(dá)到融會貫通、舉一反三的目的。

實踐證明，

理解課程內(nèi)容與較好地解決實際問題之間存在著明顯差距，

而算法設(shè)計完成的質(zhì)量與基本的程序設(shè)計素質(zhì)的培養(yǎng)是密切相關(guān)的。

要想理解和鞏固所學(xué)的基本概念。

原理和方法，

牢固地掌握所學(xué)的基本知識。

基本技能，

達(dá)到融會貫通。

舉一反三的目的，

就必須多做。

多練。

多見（見多識廣）。

正是為了達(dá)到上述目的，

書中用一些實際的應(yīng)用，

對一些重要的數(shù)據(jù)結(jié)構(gòu)和算法進(jìn)行解讀。

經(jīng)過循序漸進(jìn)地訓(xùn)練，

就可以使讀者掌握更多的程序設(shè)計技巧和方法，提高分析。

解決問題的能力。本書根據(jù)學(xué)生的基礎(chǔ)知識和興趣愛好將內(nèi)容分為基礎(chǔ)篇和提高篇兩個部分。第一部分基礎(chǔ)篇精選出適當(dāng)?shù)?、與實際生活結(jié)合密切的課程設(shè)計實例加以分析實現(xiàn)。第二部分提高篇旨在使讀者通過運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識及復(fù)雜算法去解決現(xiàn)實世界中的一些實際問題。本書依據(jù)數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱要求，同時又獨(dú)立于具體的教科書，既重視實踐應(yīng)用，又重視理論分析，本書的主要特點(diǎn)有：●本書精選出來的實例項目經(jīng)典、實用、具有一定的趣味性，其內(nèi)容豐富、涉及面廣、難易適當(dāng)，能給讀者以啟發(fā)，達(dá)到讓讀者掌握相關(guān)知識和開闊視野的目的●為了提高學(xué)生分析問題、解決問題的能力，本書對實例項目進(jìn)行分析，其設(shè)計思路清晰流暢，值得參考?！癖緯粌H僅是對照數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱舉些例子說明數(shù)據(jù)結(jié)構(gòu)能解決什么問題，而是通過分析具體的實例項目，得到對數(shù)據(jù)組織關(guān)系的需求，從而選擇某個數(shù)據(jù)結(jié)構(gòu)適應(yīng)一些特定的問題和算法，并說明使用這種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)?！袼袑嵗椖慷冀o出了參考算法和源程序代碼并在TurboC和VisualC++6.0環(huán)境下運(yùn)行通過。由于作者水平有限、時間倉促，本書難免存在一些缺點(diǎn)和錯誤，懇請廣大讀者及同行們批評指正。目錄第一部分基礎(chǔ)篇線性表學(xué)生成績管理項目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果考試報名管理項目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果約瑟夫生者死者游戲項目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果約瑟夫雙向生死游戲項目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果棧和隊列2.1迷宮旅行游戲2.1.1項目簡介2.1.2知識要點(diǎn)2.1.3設(shè)計思路2.1.4程序清單2.1.5運(yùn)行結(jié)果2.2八皇后問題2.1.1項目簡介2.1.2知識要點(diǎn)2.1.3設(shè)計思路2.1.4程序清單2.1.5運(yùn)行結(jié)果2.3停車場的停車管理2.1.1項目簡介2.1.2知識要點(diǎn)2.1.3設(shè)計思路2.1.4程序清單2.1.5運(yùn)行結(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運(yùn)行結(jié)果3.2Internet網(wǎng)絡(luò)通路管理3.2.1項目簡介3.2.2設(shè)計思路3.2.3數(shù)據(jù)結(jié)構(gòu)3.2.4程序清單3.2.5運(yùn)行結(jié)果樹和二叉樹4.1家譜管理4.1.1項目簡介4.1.2設(shè)計思路4.1.3數(shù)據(jù)結(jié)構(gòu)4.1.4程序清單4.1.5運(yùn)行結(jié)果4.2表達(dá)式求值問題4.2.1項目簡介4.2.2設(shè)計思路4.2.3數(shù)據(jù)結(jié)構(gòu)4.2.4程序清單4.2.5運(yùn)行結(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運(yùn)行結(jié)果圖5.1公交路線管理5.1.1項目簡介5.1.2設(shè)計思路5.1.3數(shù)據(jù)結(jié)構(gòu)5.1.4程序清單5.1.5運(yùn)行結(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運(yùn)行結(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運(yùn)行結(jié)果5.4軟件工程進(jìn)度規(guī)劃5.4.1項目簡介5.4.2設(shè)計思路5.4.3數(shù)據(jù)結(jié)構(gòu)5.4.4程序清單5.4.5運(yùn)行結(jié)果查找6.1電話號碼查詢系統(tǒng)6.1.1項目簡介6.1.2知識要點(diǎn)6.1.3設(shè)計思路6.1.4程序清單6.1.5運(yùn)行結(jié)果6.2高校錄取分?jǐn)?shù)線查詢系統(tǒng)6.2.1項目簡介5.2.2知識要點(diǎn)6.2.3設(shè)計思路6.2.4程序清單6.2.5運(yùn)行結(jié)果6.3儲蓄賬戶查詢系統(tǒng)6.3.1項目簡介6.3.2知識要點(diǎn)6.3.3設(shè)計思路6.3.4程序清單6.3.5運(yùn)行結(jié)果6.3期刊稿件查詢系統(tǒng)6.3.1項目簡介6.3.2知識要點(diǎn)6.3.3設(shè)計思路6.3.4程序清單6.3.5運(yùn)行結(jié)果排序7.1設(shè)備清單排序7.1.1項目簡介7.1.2知識要點(diǎn)7.1.3設(shè)計思路7.1.4程序清單7.1.5運(yùn)行結(jié)果7.2地名排序7.2.1項目簡介7.2.2知識要點(diǎn)7.2.3設(shè)計思路7.2.4程序清單7.2.5運(yùn)行結(jié)果7.3工廠產(chǎn)量排序7.3.1項目簡介7.3.2知識要點(diǎn)7.3.3設(shè)計思路7.3.4程序清單7.3.5運(yùn)行結(jié)果7.4高?？蒲谐晒判?.4.1項目簡介7.4.2知識要點(diǎn)7.4.3設(shè)計思路7.4.4程序清單7.4.5運(yùn)行結(jié)果7.5火車車次排序7.5.1項目簡介7.5.2知識要點(diǎn)7.5.3設(shè)計思路7.5.4程序清單7.5.5運(yùn)行結(jié)果7.6IP地址排序7.6.1項目簡介7.6.2知識要點(diǎn)7.6.3設(shè)計思路7.6.4程序清單7.6.5運(yùn)行結(jié)果第二部分綜合篇8.1益智游戲之七巧板8.1.1項目需求8.1.2知識要點(diǎn)8.1.3設(shè)計流程8.1.4程序清單8.1.5運(yùn)行測試8.2航空客運(yùn)定票系統(tǒng)8.2.1項目需求8.2.2知識要點(diǎn)8.2.3設(shè)計流程8.2.4程序清單8.2.5運(yùn)行測試PAGEPAGE1608.4景區(qū)旅游信息管理系統(tǒng)8.4.1項目需求8.2.2知識要點(diǎn)8.4.2設(shè)計流程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ǔ)，其掌握的好壞直接影響著后繼知識的學(xué)習(xí)。本章通過四個模擬項目來學(xué)習(xí)線性表的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)，首先通過使用有關(guān)數(shù)組的操作實現(xiàn)學(xué)生成績管理，其次通過使用有關(guān)線性鏈表的操作實現(xiàn)考試報名管理，然后通過使用循環(huán)鏈表的操作實現(xiàn)約瑟夫生者死者游戲。1.1學(xué)生成績管理1.1.1項目簡介學(xué)生成績管理是學(xué)校教務(wù)部門日常工作的重要組成部分，其處理信息量很大。本項目是對學(xué)生成績管理的簡單模擬，用菜單選擇方式完成下列功能：輸入學(xué)生數(shù)據(jù)；輸出學(xué)生數(shù)據(jù)；學(xué)生數(shù)據(jù)查詢；添加學(xué)生數(shù)據(jù)；修改學(xué)生數(shù)據(jù)；刪除學(xué)生數(shù)據(jù)。1.1.2設(shè)計思路本項目的實質(zhì)是完成對學(xué)生成績信息的建立、查找、插入、修改、刪除等功能，可以首先定義項目的數(shù)據(jù)結(jié)構(gòu)，然后將每個功能寫成一個函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以驗證各個函數(shù)功能并得出運(yùn)行結(jié)果。1.1.3數(shù)據(jù)結(jié)構(gòu)本項目的數(shù)據(jù)是一組學(xué)生的成績信息，每條學(xué)生的成績信息由學(xué)號、姓名和成績組成，這組學(xué)生的成績信息具有相同特性，屬于同一數(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)系相鄰的兩個元素在物理位置上也相鄰，這是順序表的特點(diǎn)。本項目可以采用順序表的線性表順序存儲結(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這里L(fēng)oc(ai)是第i個元素的存儲位置，loc(a1)是第1個元素的存儲位置，也稱為線性表的基址。顯然，順序表便于進(jìn)行隨機(jī)訪問，故線性表的順序存儲結(jié)構(gòu)是一種隨機(jī)存儲結(jié)構(gòu)。順序表適宜于做查找這樣的靜態(tài)操作；順序存儲的優(yōu)點(diǎn)是存儲密度大，存儲空間利用率高。缺點(diǎn)是插入或刪除元素時不方便。由于C語言的數(shù)組類型也有隨機(jī)存儲的特點(diǎn)，一維數(shù)組的機(jī)內(nèi)表示就是順序結(jié)構(gòu)。因此，可用C語言的一維數(shù)組實現(xiàn)線性表的順序存儲。數(shù)組實現(xiàn)線性表的順序存儲的優(yōu)點(diǎn)是可以隨機(jī)存取表中任一元素O(1)，存儲空間使用緊湊；缺點(diǎn)是在插入，刪除某一元素時，需要移動大量元素O(n)，預(yù)先分配空間需按最大空間分配，利用不充分，表容量難以擴(kuò)充。用結(jié)構(gòu)體類型定義每個學(xué)生數(shù)據(jù)，故該數(shù)組中的每個數(shù)據(jù)的結(jié)構(gòu)可描述為：typedefstructSTU{ charstuno[10]; //學(xué)號 charname[10]; //姓名 floatscore; //成績}ElemType;1.1.4程序清單#include<iostream.h>#include<iomanip.h>#include<malloc.h>#include<string.h>#defineMaxListSize20#defineEQUAL1typedefstructSTU{charstuno[10];charname[10];floatscore;}ElemType;classList{private://線性表的數(shù)組表示ElemTypeelem[MaxListSize];intlength;intMaxSize;public://輸入學(xué)生數(shù)據(jù)voidinit(List**L,intms);//刪除所有學(xué)生數(shù)據(jù)voidDestroyList(List&L){free(&L);}//將順序表置為空表voidClearList(){length=0;}//判斷順序表是否為空表boolListEmpty(){returnlength==0;}//判斷順序表是否為滿boolListFull(){returnlength==MaxSize;}//刪除某個學(xué)生數(shù)據(jù)boolListDelete(int,ElemType&e);//遍歷順序表voidListTraverse();//返回順序表的長度intListLength();//學(xué)生數(shù)據(jù)查詢voidGetElem(int,ElemType*);//修改學(xué)生數(shù)據(jù)boolUpdateList(ElemType&e,ElemType);//添加學(xué)生數(shù)據(jù)boolListInsert(int,ElemType&);//對學(xué)生數(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;if(mark>0){//刪除表頭元素e=elem[0];for(i=1;i<length;i++)elem[i-1]=elem[i];}else//刪除表尾元素if(mark<0)e=elem[length-1];else{//刪除值為e的元素for(i=0;i<length;i++)if(strcmp(elem[i].name,)==0)break;if(i>=length)returnfalse;elsee=elem[i];for(j=i+1;j<length;j++)elem[j-1]=elem[j];}length--;returntrue;}voidList::ListTraverse(){for(inti=0;i<length;i++){cout<<setw(8)<<elem[i].name;cout<<setw(10)<<elem[i].stuno;cout<<setw(9)<<elem[i].age;cout<<setw(8)<<elem[i].score<<endl;}}voidList::GetElem(inti,ElemType*e){*e=elem[i];}boolList::EqualList(ElemType*e1,ElemType*e2){if(strcmp(e1->name,e2->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(ElemTypee,inttype){inti;switch(type){caseEQUAL: for(i=0;i<length;i++) if(EqualList(&elem[i],&e)) returntrue; break;default:break;}returnfalse;}//修改學(xué)生數(shù)據(jù)boolList::UpdateList(ElemType&e,ElemTypee1){for(inti=0;i<length;i++)if(strcmp(elem[i].name,)==0){elem[i]=e1;returntrue;}returnfalse;}boolList::ListInsert(inti,ElemType&e){ElemType*p,*q;if(i<1||i>length+1)returnfalse;q=&elem[i-1];for(p=&elem[length-1];p>=q;--p)*(p+1)=*p;*q=e;++length;returntrue;}//對學(xué)生成績按升序或降序輸出voidList::printlist(intmark){int*b=newint[length];inti,k;cout<<"姓名學(xué)號成績\n";if(mark!=0){for(i=0;i<length;i++)b[i]=i;for(i=0;i<length;i++){k=i;for(intj=i+1;j<length;j++){if(mark==1&&elem[b[j]].score<elem[b[k]].score)k=j;if(mark==-1&&elem[b[k]].score<elem[b[j]].score)k=j;}if(k!=i){intx=b[i];b[i]=b[k];b[k]=x;}}for(inti=0;i<length;i++){cout<<setw(8)<<elem[b[i]].name;cout<<setw(10)<<elem[b[i]].stuno;cout<<setw(9)<<elem[b[i]].age;cout<<setw(8)<<elem[b[i]].score<<endl;}}else{for(i=0;i<length;i++){cout<<setw(8)<<elem[i].name;cout<<setw(10)<<elem[i].stuno;cout<<setw(9)<<elem[i].age;cout<<setw(8)<<elem[i].score<<endl;}}}voidmain(){cout<<"linelist1m.cpp運(yùn)行結(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");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(,"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=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";elsecout<<"刪除成功!\n";cout<<"輸出表Lc:\n";Lc->printlist(0);cin.get();cout<<"按成績升序輸出表Lc\n";Lc->printlist(1);cin.get();cout<<"按成績降序輸出表Lc\n";Lc->printlist(-1);cin.get();}1.1.5運(yùn)行結(jié)果首先建立學(xué)生信息管理，輸出結(jié)果為：姓名 學(xué)號 成績Stu1 100001 80 Stu2 100002 91 Stu3 100003 56其次查詢學(xué)號為100002的學(xué)生的成績，輸出結(jié)果為：91再次調(diào)用插入函數(shù)，插入Stu4成功！輸入結(jié)果為：姓名 學(xué)號 成績 Stu1 100001 80 Stu2 100002 91 Stu3 100003 56 Stu4 100004 75 最后刪除Stu2成果！輸出結(jié)果為：姓名 學(xué)號 成績 Stu1 100001 80 Stu3 100003 56 Stu4 100004 75 查詢不及格的學(xué)生，輸出結(jié)果為：Stu3 100003 56 1.2考試報名管理1.2.1項目簡介考試報名工作給各高校報名工作帶來了新的挑戰(zhàn)，給教務(wù)管理部門增加了很大的工作量，報名數(shù)據(jù)手工錄入既費(fèi)時又會不可避免地出現(xiàn)錯誤，同時也給不少學(xué)生以可乘之機(jī)。本項目是對考試報名管理的簡單模擬，用菜單選擇方式完成下列功能：輸入考生信息；輸出考生信息；查詢考生信息；添加考生信息；修改考生信息；刪除考生信息。1.2.2設(shè)計思路本項目的實質(zhì)是完成對考生信息的建立、查找、插入、修改、刪除等功能，可以首先定義項目的數(shù)據(jù)結(jié)構(gòu)，然后將每個功能寫成一個函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以驗證各個函數(shù)功能并得出運(yùn)行結(jié)果。1.2.3數(shù)據(jù)結(jié)構(gòu)本項目的數(shù)據(jù)是一組考生信息，每條考生信息由準(zhǔn)考證號、姓名、性別、年齡、報考類別等信息組成，這組考生信息具有相同特性，屬于同一數(shù)據(jù)對象，相鄰數(shù)據(jù)元素之間存在序偶關(guān)系。由此可以看出，這些數(shù)據(jù)也具有線性表中數(shù)據(jù)元素的性質(zhì)，所以該系統(tǒng)的數(shù)據(jù)可以采用線性表來存儲。從上一節(jié)的例子中可見，線性表的順序存儲結(jié)構(gòu)的特點(diǎn)是邏輯關(guān)系相鄰的兩個元素在物理位置上也相鄰，因此可以隨機(jī)存儲表中任一元素，它的存儲位置可用一個簡單、直觀的公式來表示。然而，從另一個方面來看，這個特點(diǎn)也鑄成了這種存儲結(jié)構(gòu)的弱點(diǎn)：在做插入或刪除操作時，需要移動大量元素。為克服這一缺點(diǎn)，我們引入另一種存儲形式――鏈?zhǔn)酱鎯?。鏈?zhǔn)酱鎯κ蔷€性表的另一種表示方法，由于它不要求邏輯上相鄰的元素在物理位置上也相鄰，因此它沒有順序存儲結(jié)構(gòu)的弱點(diǎn)，但同時也失去了順序表可隨機(jī)存取的特點(diǎn)。鏈?zhǔn)酱鎯Φ膬?yōu)點(diǎn)是插入或刪除元素時很方便，使用靈活。缺點(diǎn)是存儲密度小，存儲空間利用率低。事實上，鏈表插入、刪除運(yùn)算的快捷是以空間代價來換取時間。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。本項目對考生數(shù)據(jù)主要進(jìn)行插入、刪除、修改等操作，所以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)比較適合。用結(jié)構(gòu)體類型定義每個考生信息，故該單鏈表中的每個結(jié)點(diǎn)的結(jié)構(gòu)可描述為：typedefstructexaminee{ charexamno[10]; //準(zhǔn)考證號 charname[10]; //姓名 charsex; floatage;charexamtype[5]; //成績}ElemType;1.2.4程序清單//單鏈表的類定義linklist3.h#ifndeflinklist3H#definelinklist3H#defineLEN30//定義ElemType為inttypedefintElemType;//單鏈表中結(jié)點(diǎn)的類型typedefstructLNode{ElemTypedata;//值域LNode*next;//指針域}LNode;classLinkList{LNode*head;public://構(gòu)造函數(shù)LinkList();//析構(gòu)函數(shù)~LinkList();//清空單鏈表voidClearList();//求單鏈表長度intListSize();//檢查單鏈表是否為空boolListEmpty();//返回單鏈表中指定序號的結(jié)點(diǎn)值ElemTypeGetElem(intpos);//遍歷單鏈表voidTraverseList(voidf(ElemType&));//從單鏈表中查找元素boolFindList(ElemType&item);//更新單鏈表中的給定元素boolUpdateList(constElemType&item,ElemTypee);//向單鏈表插入元素,mark=0插在表首,否則插在表尾voidInsertList(ElemTypeitem,intmark);//從單鏈表中刪除元素,mark為要刪除的第幾個元素boolDeleteList(ElemType&item,intmark);//對單鏈表進(jìn)行有序排列mark>0升序,否則降序voidpailie(intmark=1);//對單鏈表進(jìn)行有序輸出,mark=0不排序,mark>0升序,mark<0降序voidOrderOutputList(intmark=0);};#endif//linklist3.cpp#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()//求單鏈表長度{LNode*p=head->next;inti=0;while(p){i++;p=p->next;}returni;}boolLinkList::ListEmpty()//檢查單鏈表是否為空{(diào)returnListSize()==0;}//返回單鏈表中指定序號的結(jié)點(diǎn)值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&))//遍歷單鏈表{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;while(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;}//從單鏈表中刪除元素boolLinkList::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;}//對單鏈表進(jìn)行有序排列mark>0升序,否則降序voidLinkList::pailie(intmark){ElemTypea[LEN+1];LNode*p=head->next;intk;for(k=1;p!=NULL;k++,p=p->next)a[k]=p->data;k--;for(inti=1;i<k;i++)for(intj=1;j<=k-i;j++){intt;if(mark>0&&a[j]>a[j+1]||mark<0&&a[j]<a[j+1]){t=a[j+1];a[j+1]=a[j];a[j]=t;}}p=head->next;for(intj=1;j<=k;j++,p=p->next)p->data=a[j];}//對單鏈表進(jìn)行有序輸出voidLinkList::OrderOutputList(intmark){ElemTypea[LEN+1];LNode*p=head->next;intk;for(k=1;p!=NULL;k++,p=p->next)a[k]=p->data;k--;for(inti=1;i<k;i++)for(intj=1;j<=k-i;j++){intt;if(mark>0&&a[j]>a[j+1]||mark<0&&a[j]<a[j+1]){t=a[j+1];a[j+1]=a[j];a[j]=t;}}for(intj=1;j<=k;j++)cout<<a[j]<<"";}#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運(yùn)行結(jié)果:\n";intinit_size,seed,xu;cout<<"首先請構(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.ListEmpty();cout<<"\n長度為:"<<list.ListSize();inti;cout<<"\n請輸入你想得到第幾個元素的值(1--"<<init_size<<"):";cin>>i;cout<<"單鏈表list中第"<<i<<"的值是"<<list.GetElem(i);intit;cout<<"\n請輸入你想刪除第幾個元素的值(1--"<<init_size<<"):";cin>>i;list.DeleteList(it,i);cout<<"\n單鏈表list刪除第"<<i<<"個元素"<<"\'"<<it<<"\'"<<"后變?yōu)?";list.TraverseList(ff);//對單鏈表list每個數(shù)進(jìn)行遍歷.intnews,olds;cout<<"\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_size;seed=120;cout<<"請選擇是否排序:(=0不排序,=1升序,=-1降序):";cin>>xu;cout<<"\n按回車鍵結(jié)束...";cin.get();cin.get();}1.2.5運(yùn)行結(jié)果1.3約瑟夫生者死者游戲1.3.1項目簡介約瑟夫生者死者游戲的大意是：30個旅客同乘一條船，因為嚴(yán)重超載，加上風(fēng)高浪大，危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定30個人圍成一圈，由第一個人開始，依次報數(shù)，數(shù)到第9人，便把他投入大海中，然后從他的下一個人數(shù)起，數(shù)到第9人，再將他投入大海，如此循環(huán)，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。1.3.2設(shè)計思路本游戲的數(shù)學(xué)建模如下：假設(shè)n個旅客排成一個環(huán)形，依次順序編號1，2，…，n。從某個指定的第1號開始，沿環(huán)計數(shù)，每數(shù)到第m個人就讓其出列，且從下一個人開始重新計數(shù)，繼續(xù)進(jìn)行下去。這個過程一直進(jìn)行到剩下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)后進(jìn)行算法實現(xiàn)。1.3.3數(shù)據(jù)結(jié)構(gòu)為了解決這一問題，可以用長度為30的數(shù)組作為線性存儲結(jié)構(gòu)，并把該數(shù)組看成是一個首尾相接的環(huán)形結(jié)構(gòu)，那么每投入大海一個乘客，就要在該數(shù)組的相應(yīng)位置做一個刪除標(biāo)記，該單元以后就不再作為計數(shù)單元。這樣做不僅算法較為復(fù)雜，而且效率低，還要移動大量的元素。用單循環(huán)鏈表解決這一問題，實現(xiàn)的方法相對要簡單得多。首先要定義鏈表結(jié)點(diǎn)，單循環(huán)鏈表的結(jié)點(diǎn)結(jié)構(gòu)與一般的結(jié)點(diǎn)結(jié)構(gòu)完全相同，只是數(shù)據(jù)域用一個整數(shù)來表示位置；然后將它們組成具有30個結(jié)點(diǎn)的單循環(huán)鏈表。接下來從位置為1的結(jié)點(diǎn)開始數(shù)，數(shù)到第8個結(jié)點(diǎn)，就將下一個結(jié)點(diǎn)從循環(huán)鏈表中刪去，然后再從刪去結(jié)點(diǎn)的下一個結(jié)點(diǎn)開始數(shù)起，數(shù)到第8個結(jié)點(diǎn)，再將其下一個結(jié)點(diǎn)刪去，如此進(jìn)行下去，直到剩下15個結(jié)點(diǎn)為止。為了不失一般性，將30改為一個任意輸入的正整數(shù)n，而報數(shù)上限（原為9）也為一個任選的正整數(shù)k。這樣該算法描述如下：(1)創(chuàng)建含有n個結(jié)點(diǎn)的單循環(huán)鏈表；(2)生著與死者的選擇：p指向鏈表的第一個結(jié)點(diǎn)，初始i置為1；while(i<=n/2)//刪除一半的結(jié)點(diǎn)｛從p指向的結(jié)點(diǎn)沿鏈前進(jìn)k-1步； 刪除第k個結(jié)點(diǎn)（q所指向的結(jié)點(diǎn)）； p指向q的下一個結(jié)點(diǎn)； 輸出其位置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++){ p=(LinkNode*)malloc(sizeof(LinkNode)); q->data=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é)點(diǎn) for(j=1;j<k-1;j++) //沿鏈前進(jìn)k-1步 p=p->next; q=p->next; p->next=q->next; printf(“%4d”,q->data); free(q);}R=p;returnR; } voidOutRing(intn,LinkListR){//輸出所有生者 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>typedefstructnode{ intdata; structnode*next;}ListNode;typedefListNode*LinkList;voidmain(){ LinkListR; 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運(yùn)行結(jié)果編譯運(yùn)行上述程序，提示：總?cè)藬?shù)n.報數(shù)上限k=輸入30和9后并“回車”可得出如下結(jié)果：9182761626719301224822523212528291234101113141517201.4約瑟夫雙向生死游戲1.4.1項目簡介約瑟夫雙向生死游戲是在約瑟夫生者死者游戲的基礎(chǔ)上，正向計數(shù)后反向計數(shù)，然后再正向計數(shù)。具體描述如下：30個旅客同乘一條船，因為嚴(yán)重超載，加上風(fēng)高浪大，危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定30個人圍成一圈，由第一個人開始，順時針依次報數(shù)，數(shù)到第9人，便把他投入大海中，然后從他的下一個人數(shù)起，逆時針數(shù)到第5人，將他投入大海，然后從他逆時針的下一個人數(shù)起，順時針數(shù)到第9人，再將他投入大海，如此循環(huán)，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。1.4.2設(shè)計思路本游戲的數(shù)學(xué)建模如下：假設(shè)n個旅客排成一個環(huán)形，依次順序編號1，2，…，n。從某個指定的第1號開始，沿環(huán)計數(shù)，數(shù)到第m個人就讓其出列，然后從第m+1個人反向計數(shù)到m-k+1個人，讓其出列，然后從m-k個人開始重新正向沿環(huán)計數(shù)，再數(shù)m個人后讓其出列，然后再反向數(shù)k個人后讓其出列。這個過程一直進(jìn)行到剩下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)后進(jìn)行算法實現(xiàn)。1.4.4數(shù)據(jù)結(jié)構(gòu)約瑟夫雙向生死游戲如果用單循環(huán)鏈表作為線性存儲結(jié)構(gòu)，就只能正向計數(shù)結(jié)點(diǎn)，反向計數(shù)比較困難，算法較為復(fù)雜，而且效率低。用雙向循環(huán)鏈表解決這一問題，實現(xiàn)的方法相對要簡單得多。為了不失一般性，將30改為一個任意輸入的正整數(shù)n，而正向報數(shù)上限（原為9）也為一個任選的正整數(shù)m，正向報數(shù)上限（原為5）也為一個任選的正整數(shù)k，。這樣該算法描述如下：(1)創(chuàng)建含有n個結(jié)點(diǎn)的雙向循環(huán)鏈表；(2)生著與死者的選擇：p指向鏈表的第一個結(jié)點(diǎn)，初始i置為1；while(i<=n/2)//刪除一半的結(jié)點(diǎn)｛從p指向的結(jié)點(diǎn)沿鏈前進(jìn)m-1步； 刪除第m個結(jié)點(diǎn)（q所指向的結(jié)點(diǎn)）； p指向q的下一個結(jié)點(diǎn)； 輸出其位置q->data; i自增1； 從p指向的結(jié)點(diǎn)沿鏈后退k-1步； 刪除第k個結(jié)點(diǎn)（q所指向的結(jié)點(diǎn)）； p指向q的上一個結(jié)點(diǎn)； 輸出其位置q->data; i自增1；｝(3)輸出所有生者的位置。1.4.4程序清單//雙向循環(huán)鏈表的類定義dcirlinkl.htypedefintElemType;//雙向鏈表結(jié)點(diǎn)的類型定義typedefstructDuLNode{ElemTypedata;structDuLNode*prior;//左指針structDuLNode*next;//右指針}DuLNode;#defineLEN20classDuLinkList{private:DuLNode*head;//指向表頭的指針DuLNode*curr;//當(dāng)前結(jié)點(diǎn)指針intcount;//雙向循環(huán)鏈表的結(jié)點(diǎn)個數(shù)public://構(gòu)造函數(shù)DuLinkList();//析構(gòu)函數(shù)~DuLinkList(){deletehead;}//創(chuàng)建有序或無序的帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表DuLNode*CreateCLinkL(int,int,intmark=0);//清空單循環(huán)鏈表voidClearCList();//求雙向循環(huán)鏈表長度intCListSize();//檢查雙向循環(huán)鏈表是否為空boolCListEmpty();//返回指向第pos個結(jié)點(diǎn)的指針DuLNode*Index(intpos);//返回雙向循環(huán)鏈表中指定序號的結(jié)點(diǎn)值ElemTypeGetElem(intpos);//遍歷雙向循環(huán)鏈表voidTraverseCList();//當(dāng)前指針curr指向pos結(jié)點(diǎn)并返回currDuLNode*Reset(intpos=0);//當(dāng)前指針curr指向下一結(jié)點(diǎn)并返回DuLNode*Next();//當(dāng)前指針curr指向上一結(jié)點(diǎn)并返回DuLNode*Prior();//判雙向循環(huán)鏈表當(dāng)前指針curr==head否boolEndOCList();//判雙向循環(huán)鏈表當(dāng)前指針curr->next是否到達(dá)表尾boolEndCList();//判雙向循環(huán)鏈表當(dāng)前指針curr->prior是否到達(dá)表尾boolPEndCList();//刪除curr->next所指結(jié)點(diǎn),并返回所刪結(jié)點(diǎn)的dataElemTypeDeleteNt();//從雙向循環(huán)鏈表中查找元素boolFindCList(ElemType&item);//更新雙向循環(huán)鏈表中的給定元素boolUpdateCList(constElemType&item,ElemType&e);//向鏈表中第pos個結(jié)點(diǎn)前插入域值為item的新結(jié)點(diǎn)voidInsertCLfront(constElemType&item,intpos);//向鏈表中第pos個結(jié)點(diǎn)后插入域值為item的新結(jié)點(diǎn)voidInsertCLafter(constElemType&item,intpos);//從鏈表中刪除第pos個結(jié)點(diǎn)并返回被刪結(jié)點(diǎn)的dataElemTypeDeleteCList(intpos);};//雙向循環(huán)鏈表的實現(xiàn)dcirlinkl.cpp#include<iostream.h>#include<stdlib.h>#include"dcirlinkl.h"http://構(gòu)造函數(shù)DuLinkList::DuLinkList(){head=newDuLNode;head->prior=head;head->next=head;curr=NULL;count=0;}//創(chuàng)建有序或無序的帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表DuLNode*DuLinkList::CreateCLinkL(intn,intm,intmark){ElemTypex,a[LEN];srand(m);for(inti=0;i<n;i++)a[i]=rand()%100;for(i=0;i<n-1;i++){intk=i;for(intj=i+1;j<n;j++)if(a[k]>a[j])k=j;if(k!=i){x=a[k];a[k]=a[i];a[i]=x;}}DuLNode*p;head=newDuLNode;head->prior=NULL;head->next=curr=p=newDuLNode;curr->prior=head;for(i=0;i<n;i++){if(mark==1)p->data=a[i];//升序elseif(mark==-1)p->data=a[n-1-i];//降序elsep->data=rand()%100;//無序if(i<n-1){curr=curr->next=newDuLNode;curr->prior=p;p=curr;}count++;}head->prior=curr;curr->next=head;returnhead;}//清空雙向循環(huán)鏈表voidDuLinkList::ClearCList(){DuLNode*cp,*np;cp=head->next;while(cp!=head){np=cp->next;deletecp;cp=np;}head=NULL;}//求雙向循環(huán)鏈表長度intDuLinkList::CListSize(){DuLNode*p=head->next;inti=0;while(p!=head){i++;p=p->next;}returni;}//檢查雙向循環(huán)鏈表是否為空boolDuLinkList::CListEmpty(){returnhead->next==head;}//返回指向第pos個結(jié)點(diǎn)的指針DuLNode*DuLinkList::Index(intpos){if(pos<1){cerr<<"posisoutrange!"<<endl;exit(1);}DuLNode*p=head->next;inti=0;while(p!=head){i++;if(i==pos)break;p=p->next;}if(p!=head)returnp;else{cerr<<"posisoutrange!"<<endl;returnNULL;}}//返回雙向循環(huán)鏈表中指定序號的結(jié)點(diǎn)值ElemTypeDuLinkList::GetElem(intpos){if(pos<1){cerr<<"posisoutrange!"<<endl;exit(1);}DuLNode*p=head->next;inti=0;while(p!=head){i++;if(i==pos)break;p=p->next;}if(p!=head)returnp->data;else{cerr<<"posisoutrange!"<<endl;returnpos;}}//遍歷雙向循環(huán)鏈表voidDuLinkList::TraverseCList(){DuLNode*p=head->next;while(p!=head){cout<<setw(4)<<p->data;p=p->next;}cout<<endl;}//當(dāng)前指針curr指向pos結(jié)點(diǎn)并返回currDuLNode*DuLinkList::Reset(intpos){DuLNode*p=curr=head->next;inti=-1;while(p!=head){i++;if(i==pos)break;p=p->next;curr=curr->next;}returncurr;}//當(dāng)前指針curr指向下一結(jié)點(diǎn)并返回DuLNode*DuLinkList::Next(){curr=curr->next;returncurr;}//當(dāng)前指針curr指向上一結(jié)點(diǎn)并返回DuLNode*DuLinkList::Prior(){curr=curr->prior;returncurr;}//判雙向循環(huán)鏈表當(dāng)前指針curr==head否boolDuLinkList::EndOCList(){returncurr==head;}//判雙向循環(huán)鏈表當(dāng)前指針curr->next是否到達(dá)表尾boolDuLinkList::EndCList(){returncurr->next==head;}//判雙向循環(huán)鏈表當(dāng)前指針curr->prior是否到達(dá)表尾boolDuLinkList::PEndCList(){returncurr->prior==head;}//刪除curr->next所指結(jié)點(diǎn),并返回所刪結(jié)點(diǎn)的dataElemTypeDuLinkList::DeleteNt(){DuLNode*p=curr->next;curr->next=p->next;curr->next->next->prior=p->prior;ElemTypedata=p->data;deletep;count--;returndata;}//從雙向循環(huán)鏈表中查找元素boolDuLinkList::FindCList(ElemType&item){DuLNode*p=head->next;while(p!=head)if(p->data==item){item=p->data;returntrue;}elsep=p->next;returnfalse;}//更新雙向循環(huán)鏈表中的給定元素boolDuLinkList::UpdateCList(constElemType&item,ElemType&e){DuLNode*p=head->next;while(p!=head)//查找元素if(p->data==item)break;elsep=p->next;if(p==head)returnfalse;else{//更新元素p->data=e;returntrue;}}//向鏈表中第pos個結(jié)點(diǎn)前插入域值為item的新結(jié)點(diǎn)voidDuLinkList::InsertCLfront(constElemType&item,intpos){DuLNode*newP=newDuLNode;newP->data=item;DuLNode*p=head->next;inti=0;while(p!=head){i++;if(i==pos)break;p=p->next;}newP->prior=p->prior;p->prior->next=newP;newP->next=p;p->prior=newP;count++;}//向鏈表中第pos個結(jié)點(diǎn)后插入域值為item的新結(jié)點(diǎn)voidDuLinkList::InsertCLafter(constElemType&item,intpos){DuLNode*newP=newDuLNode;newP->data=item;DuLNode*p=head->next;inti=-1;while(p!=head){i++;if(i==pos)break;p=p->next;}newP->prior=p->prior;p->prior->next=newP;newP->next=p;p->prior=newP;count++;}//從鏈表中刪除第pos個結(jié)點(diǎn)并返回被刪結(jié)點(diǎn)的dataElemTypeDuLinkList::DeleteCList(intpos){if(pos<1){cerr<<"posisoutrange!"<<endl;exit(1);}DuLNode*p=head->next;ElemTypedata;inti=0;while(p!=head){i++;if(i==pos)break;p=p->next;}if(p!=head){data=p->data;p->prior->next=p->next;p->next->prior=p->prior;delete[]p;count--;returndata;}elsereturnpos;}//雙向循環(huán)鏈表的測試與應(yīng)用dcirlinklm.cpp#include<iomanip.h>#include"dcirlinkl.cpp"voidmain(){cout<<"dcirlinklm.cpp運(yùn)行結(jié)果:\n";intm=150,i,n=10,x,it;DuLinkListp,t,q,mylink;p.CreateCLinkL(n,m,1);if(p.CListEmpty())cout<<"雙向循環(huán)鏈表p空!\n";elsecout<<"雙向循環(huán)鏈表p非空!\n";cout<<"雙向循環(huán)鏈表p(升序):\n";p.TraverseCList();if(p.CListEmpty())cout<<"雙向循環(huán)鏈表p空!\n";elsecout<<"雙向循環(huán)鏈表p非空!\n";if(p.EndCList())cout<<"雙向循環(huán)鏈表p滿!\n";elsecout<<"雙向循環(huán)鏈表p非滿!\n";cout<<"雙向循環(huán)鏈表t(無序):\n";t.CreateCLinkL(n-2,m);t.TraverseCList();cout<<"雙向循環(huán)鏈表t的長度:"<<t.CListSize()<<endl;cout<<"雙向循環(huán)鏈表q(降序):\n";q.CreateCLinkL(n,m,-1);q.TraverseCList();cout<<"雙向循環(huán)鏈表q的長度:"<<q.CListSize()<<endl;cout<<"鏈表q的第1個元素:"<<q.GetElem(1)<<endl;cout<<"鏈表q的第1個元素地址:"<<q.Index(1)<<endl;cout<<"鏈表q的第5個元素:"<<q.GetElem(5)<<endl;cout<<"鏈表q的第5個元素地址:"<<q.Index(5)<<endl;cout<<"鏈表q的第10個元素:"<<q.GetElem(10)<<endl;cout<<"鏈表q的第10個元素地址:"<<q.Index(10)<<endl;cout<<"鏈表q的curr->next所指元素地址:"<<q.Next()<<endl;x=65;it=66;if(q.FindCList(x))cout<<x<<"查找成功!\n";elsecout<<x<<"查找不成功!\n";if(q.UpdateCList(x,it))cout<<x<<"更新成功!\n";elsecout<<x<<"更新不成功!\n";cout<<"更新后雙向循環(huán)鏈表q:\n";q.TraverseCList();cout<<"插入后雙向循環(huán)鏈表q:\n";it=100;q.InsertCLfront(it,1);q.TraverseCList();cout<<"插入后雙向循環(huán)鏈表q:\n";it=101;q.InsertCLfront(it,5);q.TraverseCList();cout<<"插入后雙向循環(huán)鏈表q:\n";it=102;q.InsertCLfront(it,13);q.TraverseCList();cout<<"插入后q表長:"<<q.CListSize()<<endl;cout<<"第1個數(shù):"<<q.DeleteCList(1)<<"刪除成功!\n";cout<<"刪除后q表長:"<<q.CListSize()<<endl;q.TraverseCList();cout<<"第5個數(shù):"<<q.DeleteCList(5)<<"刪除成功!\n";cout<<"刪除后q表長:"<<q.CListSize()<<endl;q.TraverseCList();cout<<"第11個數(shù):"<<q.DeleteCList(11)<<"刪除成功!\n";cout<<"刪除后q表長:"<<q.CListSize()<<endl;q.TraverseCList();cout<<"刪除的數(shù)為:"<<q.DeleteNt()<<endl;cout<<"刪除后q表長:"<<q.CListSize()<<endl;q.TraverseCList();cin.get();cin.get();}1.4.5運(yùn)行結(jié)果第二章棧與隊列棧和隊列是兩種重要的線性結(jié)構(gòu)。從數(shù)據(jù)結(jié)構(gòu)角度上看，棧和隊列也是線性表，其特殊性在于棧和隊列的基本操作是線性表操作的子集，它們是受限的線性表，因此，可稱為限定性的數(shù)據(jù)結(jié)構(gòu)。但從數(shù)據(jù)類型角度看，它們是和線性表大不相同的兩類重要的抽象數(shù)據(jù)類型。由于它們廣泛應(yīng)用在各種軟件系統(tǒng)中，因此在面向?qū)ο蟮某绦蛟O(shè)計中，它們是多型數(shù)據(jù)類型。本章通過迷宮旅行游戲、八皇后問題和停車場管理三個項目來學(xué)習(xí)棧和隊列的定義、表示方法和實現(xiàn)。2.1迷宮旅行游戲2.1.1項目簡介迷宮只有兩個門，一個門叫入口，另一個門叫出口。一個騎士騎馬從入口走進(jìn)迷宮，迷宮中設(shè)置很多墻壁，對前進(jìn)方向形成了多處障礙。騎士需要在迷宮中尋找通路以到達(dá)出口。2.1.2設(shè)計思路迷宮問題的求解過程可以采用回溯法即在一定的約束條件下試探地搜索前進(jìn)，若前進(jìn)中受阻，則及時回頭糾正錯誤另擇通路繼續(xù)搜索的方法。從入口出發(fā)，按某一方向向前探索，若能走通（未走過的），即某處可達(dá)，則到達(dá)新點(diǎn)，否則試探下一方向；若所有的方向均沒有通路，則沿原路返回前一點(diǎn)，換下一個方向再繼續(xù)試探，直到所有可能的通路都探索到，或找到一條通路，或無路可走又返回到入口點(diǎn)。在求解過程中，為了保證在到達(dá)某一點(diǎn)后不能向前繼續(xù)行走（無路）時，能正確返回前一點(diǎn)以便繼續(xù)從下一個方向向前試探，則需要在試探過程中保存所能夠到達(dá)的每一點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向，當(dāng)找到出口時試探過程就結(jié)束了。為了確保程序能夠終止，調(diào)整時，必須保證曾被放棄過的填數(shù)序列不被再次試驗，即要求按某種有序模型生成填數(shù)序列。給解的候選者設(shè)定一個被檢驗的順序，按這個順序逐一生成候選者并檢驗。2.1.3數(shù)據(jù)結(jié)構(gòu)迷宮問題是棧應(yīng)用的一個典型例子。通過前面分析，我們知道在試探過程中為了能夠沿著原路逆序回退，就需要一種數(shù)據(jù)結(jié)構(gòu)來保存試探過程中曾走過的點(diǎn)的下標(biāo)及從該點(diǎn)前進(jìn)的方向，在不能繼續(xù)走下去時就要退回前一點(diǎn)繼續(xù)試探下一個方向，棧底元素是入口，棧頂元素是回退的第一站，也即后走過的點(diǎn)先退回，先走過的點(diǎn)后退回，與棧的“后進(jìn)選出，先進(jìn)后出”特點(diǎn)一致，故在該問題求解的程序中可以采用棧這種數(shù)據(jù)結(jié)構(gòu)。在迷宮有通路時，棧中保存的點(diǎn)逆序連起來就是一條迷宮的通路，否則棧中沒有通路。2.1.4程序清單程序提示：用二維數(shù)組表示二維迷宮中各個點(diǎn)是否有通路，在二維迷宮里面，從出發(fā)點(diǎn)開始，每個點(diǎn)按四鄰域計算，按照右、上、左、下的順序搜索一下落腳點(diǎn)，有路則走，無路即退回前點(diǎn)再從下一個方向搜索，即可構(gòu)成一有序模型。棧用順序結(jié)構(gòu)實現(xiàn)。//求解迷宮問題maze.cpp#include<iostream.h>#include<stdlib.h>#include<time.h>enumDirection{DOWN,RIGHT,UP,LEFT};constintROWS=8,COLS=10;voidmazeTraversal(char[][COLS],constint,constint,int,int,int);voidmazeGenerator(char[][COLS],int*,int*);voidprintMaze(constchar[][COLS]);boolvalidMove(constchar[][COLS],int,int);boolcoordsAreEdge(int,int);voidmain(){cout<<"maze.cpp運(yùn)行結(jié)果:\n";cout<<"迷宮問題求解:\n";charmaze[ROWS][COLS];intxStart,yStart,x,y;srand(time(0));for(intloop=0;loop<ROWS;++loop)for(intloop2=0;loop2<COLS;++loop2)maze[loop][loop2]='#';mazeGenerator(maze,&xStart,&yStart);x=xStart;//開始行y=yStart;//開始列mazeTraversal(maze,xStart,yStart,x,y,RIGHT);printMaze(maze);cin.get();}voidmazeTraversal(charmaze[][COLS],constintxCoord,constintyCoord,introw,intcol,intdirection){staticboolflag=false;//開始位置標(biāo)志變量maze[row][col]='x';//在當(dāng)前位置插入xif(coordsAreEdge(row,col)&&row!=xCoord&&col!=yCoord){cout<<endl<<"成功走出迷宮!\n";return;}elseif(row==xCoord&&col==yCoord&&flag){cout<<"\n返回迷宮開始位置.\n";return;}else{flag=true;for(intmove=direction,count=0;count<4;++count,++move,move%=4)switch(move){caseDOWN://向下移動if(validMove(maze,row+1,col)){mazeTraversal(maze,xCoord,yCoord,row+1,col,LEFT);return;}break;caseRIGHT://向右移動if(validMove(maze,row,col+1)){mazeTraversal(maze,xCoord,yCoord,row,col+1,DOWN);return;}break;caseUP://向上移動if(validMove(maze,row-1,col)){mazeTraversal(maze,xCoord,yCoord,row-1,col,RIGHT);return;}break;caseLEFT://向左移動if(validMove(maze,row,col-1)){mazeTraversal(m