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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全集數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全集數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全集資料僅供參考文件編號：2022年4月數(shù)據(jù)結(jié)構(gòu)課程設(shè)計全集版本號：A修改號：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：數(shù)據(jù)結(jié)構(gòu)實(shí)踐教程前言數(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)實(shí)世界中的問題轉(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)實(shí)踐教程》輔助教材，旨在彌補(bǔ)課堂教學(xué)和實(shí)驗(yàn)中的不足，幫助學(xué)生充分理解和鞏固所學(xué)的基本概念、原理和方法，達(dá)到融會貫通、舉一反三的目的。

實(shí)踐證明，

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

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

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

原理和方法，

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

基本技能，

達(dá)到融會貫通。

舉一反三的目的，

就必須多做。

多練。

多見（見多識廣）。

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

書中用一些實(shí)際的應(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ù)?、與實(shí)際生活結(jié)合密切的課程設(shè)計實(shí)例加以分析實(shí)現(xiàn)。第二部分提高篇旨在使讀者通過運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識及復(fù)雜算法去解決現(xiàn)實(shí)世界中的一些實(shí)際問題。本書依據(jù)數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱要求，同時又獨(dú)立于具體的教科書，既重視實(shí)踐應(yīng)用，又重視理論分析，本書的主要特點(diǎn)有：●本書精選出來的實(shí)例項(xiàng)目經(jīng)典、實(shí)用、具有一定的趣味性，其內(nèi)容豐富、涉及面廣、難易適當(dāng)，能給讀者以啟發(fā)，達(dá)到讓讀者掌握相關(guān)知識和開闊視野的目的●為了提高學(xué)生分析問題、解決問題的能力，本書對實(shí)例項(xiàng)目進(jìn)行分析，其設(shè)計思路清晰流暢，值得參考?！癖緯粌H僅是對照數(shù)據(jù)結(jié)構(gòu)課程教學(xué)大綱舉些例子說明數(shù)據(jù)結(jié)構(gòu)能解決什么問題，而是通過分析具體的實(shí)例項(xiàng)目，得到對數(shù)據(jù)組織關(guān)系的需求，從而選擇某個數(shù)據(jù)結(jié)構(gòu)適應(yīng)一些特定的問題和算法，并說明使用這種數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點(diǎn)。●所有實(shí)例項(xiàng)目都給出了參考算法和源程序代碼并在TurboC和VisualC++環(huán)境下運(yùn)行通過。由于作者水平有限、時間倉促，本書難免存在一些缺點(diǎn)和錯誤，懇請廣大讀者及同行們批評指正。目錄第一部分基礎(chǔ)篇線性表學(xué)生成績管理項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果考試報名管理項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果約瑟夫生者死者游戲項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果約瑟夫雙向生死游戲項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果棧和隊列迷宮旅行游戲項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果八皇后問題項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果停車場的停車管理項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果串、數(shù)組和廣義表單詞檢索統(tǒng)計程序項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果Internet網(wǎng)絡(luò)通路管理項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果樹和二叉樹家譜管理項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果表達(dá)式求值問題項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果圖像壓縮編碼優(yōu)化項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果圖公交路線管理項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果導(dǎo)航最短路徑查詢項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果電網(wǎng)建設(shè)造價計算項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果軟件工程進(jìn)度規(guī)劃項(xiàng)目簡介設(shè)計思路數(shù)據(jù)結(jié)構(gòu)程序清單運(yùn)行結(jié)果查找電話號碼查詢系統(tǒng)項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果高校錄取分?jǐn)?shù)線查詢系統(tǒng)項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果儲蓄賬戶查詢系統(tǒng)項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果期刊稿件查詢系統(tǒng)項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果排序設(shè)備清單排序項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果地名排序項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果工廠產(chǎn)量排序項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果高校科研成果排序項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果火車車次排序項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果IP地址排序項(xiàng)目簡介知識要點(diǎn)設(shè)計思路程序清單運(yùn)行結(jié)果第二部分綜合篇益智游戲之七巧板項(xiàng)目需求知識要點(diǎn)設(shè)計流程程序清單運(yùn)行測試航空客運(yùn)定票系統(tǒng)項(xiàng)目需求知識要點(diǎn)設(shè)計流程程序清單運(yùn)行測試景區(qū)旅游信息管理系統(tǒng)項(xiàng)目需求知識要點(diǎn)設(shè)計流程程序清單運(yùn)行測試第一部分基礎(chǔ)篇第一章線性表線性表是數(shù)據(jù)結(jié)構(gòu)中最簡單、最常用的一種線性結(jié)構(gòu)，也是學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)全部內(nèi)容的基礎(chǔ)，其掌握的好壞直接影響著后繼知識的學(xué)習(xí)。本章通過四個模擬項(xiàng)目來學(xué)習(xí)線性表的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)，首先通過使用有關(guān)數(shù)組的操作實(shí)現(xiàn)學(xué)生成績管理，其次通過使用有關(guān)線性鏈表的操作實(shí)現(xiàn)考試報名管理，然后通過使用循環(huán)鏈表的操作實(shí)現(xiàn)約瑟夫生者死者游戲。學(xué)生成績管理項(xiàng)目簡介學(xué)生成績管理是學(xué)校教務(wù)部門日常工作的重要組成部分，其處理信息量很大。本項(xiàng)目是對學(xué)生成績管理的簡單模擬，用菜單選擇方式完成下列功能：輸入學(xué)生數(shù)據(jù)；輸出學(xué)生數(shù)據(jù)；學(xué)生數(shù)據(jù)查詢；添加學(xué)生數(shù)據(jù)；修改學(xué)生數(shù)據(jù)；刪除學(xué)生數(shù)據(jù)。設(shè)計思路本項(xiàng)目的實(shí)質(zhì)是完成對學(xué)生成績信息的建立、查找、插入、修改、刪除等功能，可以首先定義項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)，然后將每個功能寫成一個函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以驗(yàn)證各個函數(shù)功能并得出運(yùn)行結(jié)果。數(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ù)采用線性表來存儲。順序表是線性表的順序存儲結(jié)構(gòu)，是指用一組連續(xù)的內(nèi)存單元依次存放線性表的數(shù)據(jù)元素。在順序存儲結(jié)構(gòu)下，邏輯關(guān)系相鄰的兩個元素在物理位置上也相鄰，這是順序表的特點(diǎn)。本項(xiàng)目可以采用順序表的線性表順序存儲結(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ù)組實(shí)現(xiàn)線性表的順序存儲。數(shù)組實(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]; 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;}ame,==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;}core<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<<"1m運(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,"100001");=22;=88;La->ListInsert(1,e1);strcpy,"stu2");strcpy,"100002");=21;=79;La->ListInsert(2,e2);strcpy,"stu3");strcpy,"100003");=19;=87;La->ListInsert(3,e3);La->printlist(0);cout<<"表La長:"<<La->ListLength()<<endl;();Lb->init(&Lb,4);strcpy,"zmofun");strcpy,"100001");=20;=94;Lb->ListInsert(1,e4);strcpy,"bobjin");strcpy,"100002");=23;=69;Lb->ListInsert(2,e5);strcpy,"stu1");strcpy,"100001");=22;=88;Lb->ListInsert(3,e6);Lb->printlist(0);cout<<"表Lb長:"<<Lb->ListLength()<<endl;();k=Lc->ListDelete(-1,e6);if(k==0)cout<<"刪除失敗!\n";elsecout<<"刪除成功!\n";cout<<"輸出表Lc:\n";Lc->printlist(0);();cout<<"按成績升序輸出表Lc\n";Lc->printlist(1);();cout<<"按成績降序輸出表Lc\n";Lc->printlist(-1);();}運(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 考試報名管理項(xiàng)目簡介考試報名工作給各高校報名工作帶來了新的挑戰(zhàn)，給教務(wù)管理部門增加了很大的工作量，報名數(shù)據(jù)手工錄入既費(fèi)時又會不可避免地出現(xiàn)錯誤，同時也給不少學(xué)生以可乘之機(jī)。本項(xiàng)目是對考試報名管理的簡單模擬，用菜單選擇方式完成下列功能：輸入考生信息；輸出考生信息；查詢考生信息；添加考生信息；修改考生信息；刪除考生信息。設(shè)計思路本項(xiàng)目的實(shí)質(zhì)是完成對考生信息的建立、查找、插入、修改、刪除等功能，可以首先定義項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)，然后將每個功能寫成一個函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以驗(yàn)證各個函數(shù)功能并得出運(yùn)行結(jié)果。數(shù)據(jù)結(jié)構(gòu)本項(xiàng)目的數(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)是存儲密度小，存儲空間利用率低。事實(shí)上，鏈表插入、刪除運(yùn)算的快捷是以空間代價來換取時間。順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。本項(xiàng)目對考生數(shù)據(jù)主要進(jìn)行插入、刪除、修改等操作，所以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)比較適合。用結(jié)構(gòu)體類型定義每個考生信息，故該單鏈表中的每個結(jié)點(diǎn)的結(jié)構(gòu)可描述為：typedefstructexaminee{ charexamno[10]; 升0升0升3m1升intnews,olds;cout<<"\n請輸入要被修改的元素:";cin>>olds;cout<<"請輸入修改后要變成的元素:";cin>>news;(olds,news);cout<<"\n修改后單鏈表list變?yōu)?";(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é)束...";();();}運(yùn)行結(jié)果約瑟夫生者死者游戲項(xiàng)目簡介約瑟夫生者死者游戲的大意是：30個旅客同乘一條船，因?yàn)閲?yán)重超載，加上風(fēng)高浪大，危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定30個人圍成一圈，由第一個人開始，依次報數(shù)，數(shù)到第9人，便把他投入大海中，然后從他的下一個人數(shù)起，數(shù)到第9人，再將他投入大海，如此循環(huán)，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。設(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)行算法實(shí)現(xiàn)。數(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)鏈表解決這一問題，實(shí)現(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)報數(shù)上限k=”); scanf(“%d%d”,&n,&k); R=InitRing(n,R); R=DeleteDeath(n,k,R); OutRing(n,R);}運(yùn)行結(jié)果編譯運(yùn)行上述程序，提示：總?cè)藬?shù)n.報數(shù)上限k=輸入30和9后并“回車”可得出如下結(jié)果：918276162671930122482252321252829123410111314151720約瑟夫雙向生死游戲項(xiàng)目簡介約瑟夫雙向生死游戲是在約瑟夫生者死者游戲的基礎(chǔ)上，正向計數(shù)后反向計數(shù)，然后再正向計數(shù)。具體描述如下：30個旅客同乘一條船，因?yàn)閲?yán)重超載，加上風(fēng)高浪大，危險萬分；因此船長告訴乘客，只有將全船一半的旅客投入海中，其余人才能幸免遇難。無奈，大家只得同意這種辦法，并議定30個人圍成一圈，由第一個人開始，順時針依次報數(shù)，數(shù)到第9人，便把他投入大海中，然后從他的下一個人數(shù)起，逆時針數(shù)到第5人，將他投入大海，然后從他逆時針的下一個人數(shù)起，順時針數(shù)到第9人，再將他投入大海，如此循環(huán)，直到剩下15個乘客為止。問哪些位置是將被扔下大海的位置。設(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)行算法實(shí)現(xiàn)。數(shù)據(jù)結(jié)構(gòu)約瑟夫雙向生死游戲如果用單循環(huán)鏈表作為線性存儲結(jié)構(gòu)，就只能正向計數(shù)結(jié)點(diǎn)，反向計數(shù)比較困難，算法較為復(fù)雜，而且效率低。用雙向循環(huán)鏈表解決這一問題，實(shí)現(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)";return;}else{flag=true;for(intmove=direction,count=0;count<4;++count,++move,move%=4)switch(move){caseif(validMove(maze,row+1,col)){mazeTraversal(maze,xCoord,yCoord,row+1,col,LEFT);return;}break;caseif(validMove(maze,row,col+1)){mazeTraversal(maze,xCoord,yCoord,row,col+1,DOWN);return;}break;caseif(validMove(maze,row-1,col)){mazeTraversal(maze,xCoord,yCoord,row-1,col,RIGHT);return;}break;caseif(validMove(maze,row,col-1)){mazeTraversal(maze,xCoord,yCoord,row,col-1,UP);return;}break;}}}#0########0##000####000###xx##00###x#x####x#xx#xx###xxxxxx####x#xxx############八皇后問題項(xiàng)目簡介八皇后問題是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在88格的國際象棋棋盤上，安放八個皇后，要求沒有一個皇后能夠“吃掉”任何其他一個皇后，即任意兩個皇后都不能處于同一行、同一列或同一條對角線上，求解有多少種擺法。高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法得出結(jié)論，有92種擺法。設(shè)計思路八皇后在棋盤上分布的各種可能的格局?jǐn)?shù)目非常大，約等于232種，但是，可以將一些明顯不滿足問題要求的格局排除掉。由于任意兩個皇后不能同行，即每一行只能放置一個皇后，因此將第i個皇后放置在第i行上。這樣在放置第i個皇后時，只要考慮它與前i-1個皇后處于不同列和不同對角線位置上即可。解決該問題采用回溯法。首先將第一個皇后放于第一行第一列，然后依次在下一行上放置下一個皇后，直到八個皇后全放置安全。在放置每一個皇后時，都依次對每一列進(jìn)行檢測，首先檢測待第一列是否與已放置的皇后沖突，如不沖突，則將皇后放置在該列，否則，選擇該行的下一列進(jìn)行檢沒。如整行的八列都沖突，則回到上一行，重新選擇位置，依次類推。數(shù)據(jù)結(jié)構(gòu)八皇后問題是棧應(yīng)用的另一個典型例子。通過前面分析，我們知道在對八個皇后的位置進(jìn)行試探的過程中，可能遇到在某一行上的所有位置都不安全的情況，這時就要退回到上一行，重新擺放在上一行放置的皇后。為了能夠?qū)ι弦恍械幕屎罄^續(xù)尋找下一個安全位置，就必須記得該皇后目前所在的位置，即需要一種數(shù)據(jù)結(jié)構(gòu)來保存從第一行開始的每一行上的皇后所在的位置。在放置進(jìn)行不下去時，已經(jīng)放置的皇后中后放置的皇后位置先被糾正，先放置的皇后后被糾正，與棧的“后進(jìn)選出，先進(jìn)后出”特點(diǎn)一致，故在該問題求解的程序中可以采用棧這種數(shù)據(jù)結(jié)構(gòu)。在八個皇后都放置安全時，棧中保存的數(shù)據(jù)就是八個皇后在八行上的列位置。程序清單程序提示：用二維數(shù)組表示88格的國際象棋棋盤。棧用順序結(jié)構(gòu)實(shí)現(xiàn)。#include<>#include<>intline[8],answer=0;voidshow(){

inti,j;

for(i=0;i<8;i++)

{

for(j=0;j<8;j++)

{

if(line[i]==j)

cout<<"Q";

else

cout<<"*";

}

cout<<endl;

}

answer++;

cout<<endl;

cout<<answer<<endl;

getchar();}intJudge(intt){

inti,n=0;

for(i=0;i<t;i++)

{

if(line[i]==line[t])

{n=1;break;}

if(line[i]+i==line[t]+t)

{n=1;break;}

if(line[i]-i==line[t]-t)

{n=1;break;}

}

returnn;}voidcontrol(intn){

intt=8;

for(line[n]=0;line[n]<t;line[n]++)

{

if(Judge(n))

continue;

else

if(n!=7)

control(n+1);

else

show();

}}intmain(){

control(0);

cout<<answer<<endl;

return0;}運(yùn)行結(jié)果Q***********Q**********Q*****Q****Q***********Q**Q*********Q****1停車場管理項(xiàng)目簡介設(shè)停車場是一個可以停放n輛汽車的南北方向的狹長通道，且只有一個大門可供汽車進(jìn)出。汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在車場的最北端），若車場內(nèi)已停滿n輛車，那么后來的車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當(dāng)停車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進(jìn)入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費(fèi)用。試為停車場編制按上述要求進(jìn)行管理的模擬程序。要求程序輸出每輛車到達(dá)后的停車位置（停車場或便道上），以及某輛車離開停車場時應(yīng)繳納的費(fèi)用和它在停車場內(nèi)停留的時間。設(shè)計思路停車場的管理流程如下：①當(dāng)車輛要進(jìn)入停車場時，檢查停車場是否已滿，如果未滿則車輛進(jìn)入停車場；如果停車場已滿，則車輛進(jìn)入便道等候。②當(dāng)車輛要求出棧時，先讓在它之后進(jìn)入停車場的車輛退出停車場為它讓路，再讓該車退出停車場，讓路的所有車輛再按其原來進(jìn)入停車場的次序進(jìn)入停車場。之后，再檢查在便道上是否有車等候，有車則讓最先等待的那輛車進(jìn)入停車場。數(shù)據(jù)結(jié)構(gòu)由于停車場只有一個大門，當(dāng)停車場內(nèi)某輛車要離開時，在它之后進(jìn)入的車輛必須先退出車場為它讓路，先進(jìn)停車場的后退出，后進(jìn)車場的先退出，符合棧的“后進(jìn)先出，先進(jìn)后出”的操作特點(diǎn)，因此，可以用一個棧來模擬停車場。而當(dāng)停車場滿后，繼續(xù)來到的其它車輛只能停在便道上，根據(jù)便道停車的特點(diǎn)，先排隊的車輛先離開便道進(jìn)入停車場，符合隊列的“先進(jìn)先出，后進(jìn)后出”的操作特點(diǎn)，因此，可以用一個隊列來模擬便道。排在停車場中間的車輛可以提出離開停車場，并且停車場內(nèi)在要離開的車輛之后到達(dá)的車輛都必須先離開停車場為它讓路，然后這些車輛依原來到達(dá)停車場的次序進(jìn)入停車場，因此在前面已設(shè)的一個棧和一個隊列的基礎(chǔ)上，還需要有一個地方保存為了讓路離開停車場的車輛，由于先退出停車場的后進(jìn)入停車場，所以很顯然保存讓路車輛的場地也應(yīng)該用一個棧來模擬。因此，本題求解過程中需用到兩個棧和一個隊列。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。程序清單程序提示：以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號碼以及到達(dá)或離去的時刻。對每一組輸入數(shù)據(jù)進(jìn)行操作后的輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場內(nèi)或便道上的停車位置；若是車輛離去，則輸出汽車在停車場內(nèi)停留的時間和應(yīng)交納的費(fèi)用（在便道上停留的時間不收費(fèi)）。#include<>#include<>#include<>#include<>#include<>#define

size

1

建立文件的實(shí)現(xiàn)思路是：(1)定義一個串變量；(2)定義文本文件；(3)輸入文件名，打開該文件；(4)循環(huán)讀入文本行，寫入文本文件，其過程如下： while(不是文件輸入結(jié)束){ 讀入一文本行至串變量； 串變量寫入文件； 輸入是否結(jié)束輸入標(biāo)志； ｝(5)關(guān)閉文件。2.給定單詞計數(shù)的實(shí)現(xiàn)思路是：該功能需要用到模式匹配算法，逐行掃描文本文件。匹配一個，計數(shù)器加1，直到整個文件掃描結(jié)束；然后輸出單詞出現(xiàn)的次數(shù)。串是非數(shù)值處理中的主要對象，如在信息檢索、文本編輯、符號處理等許多領(lǐng)域，得到越來越廣泛的應(yīng)用。在串的基本操作中，在主串中查找模式串的模式匹配算法是文本處理中最常用、最重要的操作之一，稱為模式匹配或串匹配，就是求子串在主串中首次出現(xiàn)的位置。樸素模式匹配算法的基本思路是將給定字串與主串從第一個字符開始比較，找到首次與子串完全匹配的子串為止，并記住該位置。但為了實(shí)現(xiàn)統(tǒng)計子串出現(xiàn)的個數(shù)，不僅需要從主串的第一個字符位置開始比較，而且需要從主串的任一位置檢索匹配字符串。其實(shí)現(xiàn)過程如下：(1)輸入要檢索的文本文件名，打開相應(yīng)的文件；(2)輸入要檢索統(tǒng)計的單詞；(3)循環(huán)讀文本文件，讀入一行，將其送入定義好的串中，并求該串的實(shí)際長度，調(diào)用串匹配函數(shù)進(jìn)行計數(shù)。具體描述如下： while(不是文件結(jié)束){ 讀入一行并到串中； 求出串長度； 模式匹配函數(shù)計數(shù)； ｝(4)關(guān)閉文件，輸出統(tǒng)計結(jié)果。3.檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置的實(shí)現(xiàn)思路是：這個設(shè)計要求同上一個設(shè)計類似，但是要相對復(fù)雜一些。其實(shí)現(xiàn)過程描述如下：(1)輸入要檢索的文本文件名，打開相應(yīng)的文件；(2)輸入要檢索統(tǒng)計的單詞；(3)行計數(shù)器置初值0；(4)while(不是文件結(jié)束){ 讀入一行到指定串中； 求出串長度； 行單詞計數(shù)器0； 調(diào)用模式匹配函數(shù)匹配單詞定位、該行匹配單詞計數(shù)； 行號計數(shù)器加1； if(行單詞計數(shù)器!=0)輸出行號、該行有匹配單詞的個數(shù)以及相應(yīng)的位置；} 4.主控菜單程序的結(jié)構(gòu) 該部分內(nèi)容如下： (1)頭文件包含； (2)菜單選項(xiàng)包括： 1.建立文件 2.單詞計數(shù) 3.單詞定位 4.退出程序(3)選擇1-4執(zhí)行相應(yīng)的操作，其他字符為非法。數(shù)據(jù)結(jié)構(gòu)如果在程序設(shè)計語言中，串只是作為輸入或輸出的常量出現(xiàn)，則只需存儲此串的串值，即字符序列即可.但在多數(shù)非數(shù)值處理的程序中，串也以變量的形式出現(xiàn)。串有三種機(jī)內(nèi)表示方法：定長順序存儲表示、堆分配存儲表示和串的塊鏈存儲表示。定長順序存儲表示類似于線性表的順序存儲結(jié)構(gòu)，用一組地址連續(xù)的存儲單元存儲串值的字符序列。在串的定長順序存儲結(jié)構(gòu)中，按照予定義的大小，為每個定義的串變量分配一個固定長度的存儲區(qū)，則可用定長數(shù)組描述?！亩ㄩL順序存儲表示——

#defineMAXSTRLEN255if(poss[0]||lenS[0]-pos+1)returnERROR;

Sub[1..len]=S[pos..pos+len-1];

Sub[0]=len;

returnOK;

}C2F5G1C4F5G4C2F5G4C2F5f{

if(OperatorA==OperatorB||(OperatorA=='*'&&OperatorB=='/')||(OperatorA=='/'&&OperatorB=='*')||(OperatorA==''&&OperatorB=='-')||(OperatorA=='-'&&OperatorB==''))

returntrue;

elsereturnfalse;

}

boolTakesPrecedence(charOperatorA,charOperatorB)oot);

();

>right_child=;

=NULL;

copy,().root);

>left_child=;

();

=NULL;

copy,;

(temp_tree);

=NULL;

}

(c);

}

}

elseif(c=='(')

(c);

elseif(c==')')

{

while()!='(')

{

binary_treetemp_tree;

stringthisstring="";

thisstring=thisstring();

();

=build_node(thisstring);

copy,().root);

();

>right_child=;

=NULL;

copy,().root);

>left_child=;

();

=NULL;

copy,;

(temp_tree);

=NULL;

}

();

}

}

/*************************************************************/while(!())

{

binary_treetemp_tree;

stringthisstring="";

thisstring=thisstring();

();

=build_node(thisstring);

copy,().root);

();

>right_child=;

=NULL;

copy,().root);

>left_child=;

();

=NULL;

copy,;

(temp_tree);

if(!())

{

=NULL;

}

}

cout<<"打印結(jié)點(diǎn)如下:";

();

binary_treetemp;

copy,;

cout<<'\n';

cout<<"結(jié)點(diǎn)個數(shù)為："<<()<<'\n';

cout<<"以下是，中間的計算結(jié)果："<<'\n';

();

cout<<'\n';

cout<<"結(jié)果是:";

cout<<>data<<'\n';

cout<<"--------------------------------------------------------------------------------"<<'\n';

cout<<"是不要進(jìn)行二叉樹排序，并顯示若是升序點(diǎn)A，若是降序點(diǎn)B,若不是點(diǎn)C"<<'\n';

charc1;

cin>>c1;

if(c1=='A'||c1=='a')

{

binary_treetemp1;

copy,().root);以沒有輸出.

}

elseif(c1=='B'||c1=='b')

{

binary_treetemp1;

copy,().root);

;

}

cout<<"\n\nRunProgramagainEnter<y/n>:";

cin>>choice;

}

else

{

cout<<"************************************************"<<'\n';

cout<<"ERROR:InvalidExpression"<<'\n';

cout<<"************************************************"<<'\n';

cout<<"\n\nRunProgramagainEnter<y/n>:";

cin>>choice;

}

}

return0;

}

&&HT[j].parent==0){m2=m1;x2=x1;m1=HT[j].weight;x1=j;}elseif(HT[j].weight<m2&&HT[j].parent==0){m2=HT[j].weight;x2=j;}}arent=i;HT[x2].parent=i;HT[i].left=x1;HT[i].right=x2;HT[i].weight=HT[x1].weight+HT[x2].weight;}arent;f!=0;c=f,f=HT[f].parent)if(HT[f].left==c)cd[--start]='0';elsecd[--start]='1';eight;cout<<"Code="<<hc[i]<<'\n';}();}運(yùn)行結(jié)果第五章圖圖是一種較線性表和樹更為復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，也是日常生活中應(yīng)用廣泛的結(jié)構(gòu)之一。在線性表中，數(shù)據(jù)元素之間僅僅有線性關(guān)系，每個數(shù)據(jù)元素只有一個直接前驅(qū)和一個直接后繼；在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每一層上的數(shù)據(jù)元素可能和下一層中多個元素（即其孩子結(jié)點(diǎn)）相關(guān)，但只能和上一層中的一個元素（即其雙親結(jié)點(diǎn)相關(guān)）；而在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。由此，圖的應(yīng)用極為廣泛，特別是近年來的迅速發(fā)展，已滲入到諸如語言學(xué)、邏輯學(xué)、物理、化學(xué)、電訊工程、計算機(jī)科學(xué)以及數(shù)學(xué)的其他分支中。公交線路管理項(xiàng)目簡介本項(xiàng)目是對公交車線路信息的簡單模擬，以完成建立公交路線信息、修改公交路線信息和刪除公交路線信息等功能。設(shè)計思路本項(xiàng)目的實(shí)質(zhì)是完成對公交線路信息的建立、查找、插入、修改、刪除等功能，可以首先定義項(xiàng)目的數(shù)據(jù)結(jié)構(gòu)，然后將每個功能寫成一個函數(shù)來完成對數(shù)據(jù)的操作，最后完成主函數(shù)以驗(yàn)證各個函數(shù)功能并得出運(yùn)行結(jié)果。數(shù)據(jù)結(jié)構(gòu)公交站點(diǎn)之間的關(guān)系可以是任意的，任意兩個站點(diǎn)之間都可能相關(guān)。而在圖形結(jié)構(gòu)中，結(jié)點(diǎn)之間的關(guān)系可以是任意的，圖中任意兩個數(shù)據(jù)元素之間都可能相關(guān)。所以可以用圖形結(jié)構(gòu)來表示n個公交站點(diǎn)之間以及站點(diǎn)之間可能設(shè)置的公交路線，其中網(wǎng)的頂點(diǎn)表示公交站點(diǎn)，邊表示兩個站點(diǎn)之間的路線，賦予邊的權(quán)值表示相應(yīng)的距離。 因?yàn)楣宦肪€是有一定的連續(xù)關(guān)系的，如果想輸出從某一個起始點(diǎn)開始到某一終點(diǎn)結(jié)束的公交路線，就需要找到從某一頂點(diǎn)開始的第一個鄰接點(diǎn)和下一個鄰接點(diǎn)。因?yàn)樵卩徑颖碇腥菀渍业饺我豁旤c(diǎn)的第一個鄰接點(diǎn)和下一個鄰接點(diǎn)，所以本項(xiàng)目使用了圖的鄰接表存儲結(jié)構(gòu)。鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。在鄰接表中，對圖的每一個頂點(diǎn)建立一個單鏈表，第i個單鏈表中的結(jié)點(diǎn)表示依附于頂點(diǎn)vi的邊（對有向圖是以頂點(diǎn)vi為尾的?。Ｃ總€結(jié)點(diǎn)由三個域組成，其中鄰接點(diǎn)域(adjvex)指示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置，鏈域(nextarc)指示下一條邊或弧的結(jié)點(diǎn)；數(shù)據(jù)域(info)存儲和邊或弧相關(guān)的信息，如權(quán)值等。每個鏈表上附設(shè)一個表頭結(jié)點(diǎn)，在表頭結(jié)點(diǎn)中，除了設(shè)有鏈域(firstarc)指向鏈表中第一個結(jié)點(diǎn)之外，還設(shè)有存儲頂點(diǎn)vi的名或其它有關(guān)信息的數(shù)據(jù)域(data)。這些表頭結(jié)點(diǎn)通常以順序結(jié)構(gòu)的形式存儲，以便隨機(jī)訪問任意頂點(diǎn)的鏈表。圖的鄰接表存儲表示結(jié)構(gòu)可形式的說明如下：#defineMAX_VERTEX_NUM20typedefstructArcNode{size=numE=0;}ow;j=rcw[k].col;w=rcw[k].weight;ata<<':'<<i<<"";visited[i]=true;ata<<':'<<i<<"";ata<<':'<<j<<"";visited[j]=true;rear=(rear+1)%MaxLength;ata;}dj;while(p!=NULL&&p->adjvex<v2)p=p->next;if(v2!=p->adjvex){cerr<<"邊<v1,v2>不存在!\n";exit(1);}returnp->weight;}ata=V;size++;}dj==NULL)dj=q;elsedj,*pre=NULL;while(curr!=NULL&&curr->adjvex<v2){pre=curr;curr=curr->next;}if(pre==NULL)dj;g[v1].adj=q;}elsedj;while(curr!=NULL&&curr->adjvex<v){pre=curr;curr=curr->next;}if(pre==NULL&&curr->adjvex==v){g[i].adj=curr->next;dj,*q;for(i=v;i<size-1;i++)g[i]=g[i+1];dj,*pre=NULL;while(curr!=NULL&&curr->adjvex<v2){pre=curr;curr=curr->next;}if(pre==NULL&&curr->adjvex==v2)dj=curr->next;deletecurr;numE--;}elseif(curr!=NULL&&curr->adjvex==v2)ow,E[k].col,E[k].weight);cout<<"輸出建立的圖:\n";for(i=0;i<n;i++)cout<<g[i].data<<"";cout<<endl;}CTeight=0;numE=0;}eight>0){k++;cout<<'('<<ge[i].row<<','<<ge[i].col;cout<<','<<ge[i].weight<<")";if(k%5==0)cout<<endl;}if(e>0&&ge[i].weight>0){cout<<'('<<ge[e-1].row<<','<<ge[e-1].col;cout<<','<<ge[e-1].weight<<')';}cout<<'}'<<endl;}ow;j=r[k].col;w=r[k].weight;ow=i;GE[k].col=j;GE[k].weight=GA[i][j];k++;}}eight)GE[j+1]=GE[j];elsebreak;GE[j+1]=x;}}RCWCTow=0;CT[i].col=i+1;CT[i].weight=GA[0][i+1];}eight<min){min=CT[j].weight;m=j;}ol;ol;w=GA[j][t];if(w<CT[i].weight){CT[i].weight=w;CT[i].row=j;}}}}4214213567891011if(r[p].w2==G->data[k])j=k;}G->edge[i][j]=r[p].w;}};free(D);free;}voidmain(){cout<<"運(yùn)行結(jié)果:\n";GraphG;intn=6,e=8;irstedge;while(p!=NULL){j=p->adjvex;a[i][j]=p->weight;p=p->next;}}for(i=0;i<n;i++)vexno[i]=i;k=topo_sort(a,vex,vexno,n);if(k==0)printf(“該圖有回路，拓樸排序失敗\n”);else{printf(“拓樸排序序列：”);for(i=0;i<n-1;i++)printf(“%s->”,g->adjlist[vex[i]].vertex);printf(“%s\n”,g->adjlist[vex[n-1]].vertex);}}運(yùn)行結(jié)果第二部分綜合篇景區(qū)旅游信息管理系統(tǒng)項(xiàng)目需求在旅游景區(qū)，經(jīng)常會遇到游客打聽從一個景點(diǎn)到另一個景點(diǎn)的最短路徑和最短距離，這類游客不喜歡按照導(dǎo)游圖的線路來游覽，而是挑選自己感興趣的景點(diǎn)游覽。為于幫助這類游客信息查詢，就需要計算出所有景點(diǎn)之間最短路徑和最短距離。算法采用迪杰斯特拉算法或弗洛伊德算法均可。建立一個景區(qū)旅游信息管理系統(tǒng)，實(shí)現(xiàn)的主要功能包括制訂旅游景點(diǎn)導(dǎo)游線路策略和制訂景區(qū)道路鋪設(shè)策略。任務(wù)中景點(diǎn)分布是一個無向帶權(quán)連通圖，圖中邊的權(quán)值是景點(diǎn)之間的距離。

（1）景區(qū)旅游信息管理系統(tǒng)中制訂旅游景點(diǎn)導(dǎo)游線路策略，首先通過遍歷景點(diǎn)，給出一個入口景點(diǎn)，建立一個導(dǎo)游線路圖，導(dǎo)游線路圖用有向圖表示。遍歷采用深度優(yōu)先策略，這也比較符合游客心理。

（2）為了使導(dǎo)游線路圖能夠優(yōu)化，可通過拓樸排序判斷圖中有無回路，若有回路，則打印輸出回路中的景點(diǎn)，供人工優(yōu)化。

（3）在導(dǎo)游線路圖中，還為一些不愿按線路走的游客提供信息服務(wù)，比如從一個景點(diǎn)到另一個景點(diǎn)的最短路徑和最短距離。在本線路圖中將輸出任意景點(diǎn)間的最短路徑和最短距離。

（4）在景區(qū)建設(shè)中，道路建設(shè)是其中一個重要內(nèi)容。道路建設(shè)首先要保證能連通所有景點(diǎn)，但又要花最小的代價，可以通過求最小生成樹來解決這個問題。本任務(wù)中假設(shè)修建道路的代價只與它的里程相關(guān)。因此歸納起來，本任務(wù)有如下功能模塊：創(chuàng)建景區(qū)景點(diǎn)分布圖；輸出景區(qū)景點(diǎn)分布圖（鄰接矩陣）輸出導(dǎo)游線路圖；判斷導(dǎo)游線路圖有無回路；求兩個景點(diǎn)間的最短路徑和最短距離；輸出道路修建規(guī)劃圖。主程序用菜單選項(xiàng)供用戶選擇功能模塊。設(shè)計流程主程序采用設(shè)計主菜單調(diào)用若干功能模塊，同時在主程序中定義兩個鄰接鏈表類型變量G和G1，作為調(diào)用子函數(shù)的參數(shù)。建圖子模塊建立無向帶權(quán)圖，輸入頂點(diǎn)信息和邊的信息，輸出鄰接鏈表G。由于是無向邊，輸入一條邊時構(gòu)建兩條邊。輸出圖子模塊：從鄰接鏈表g轉(zhuǎn)換成鄰接矩陣a，并輸出鄰接矩陣a。圖中邊的權(quán)值∞用32767表示。遍歷子模塊：通過遍歷圖G，只得到遍歷的頂點(diǎn)序列。我們先將頂點(diǎn)序列存在數(shù)組vex中，然后再轉(zhuǎn)換成導(dǎo)游線路存入數(shù)組vex1中，最后生成導(dǎo)游線路圖G1（同樣用鄰接鏈表存儲，供拓樸排序用）。將遍歷頂點(diǎn)序列轉(zhuǎn)換成導(dǎo)游線路。圖10-43（a）（b）（c）三個無向圖的深度優(yōu)先搜索遍歷的結(jié)果均為v1→v2→v3→v4。但它們的導(dǎo)游線路圖卻不同。圖（a）的導(dǎo)游線路圖為v1→v2→v3→v4，與遍歷結(jié)果相同。圖（b）的導(dǎo)游線路圖為v1→v2→v3→v2→v4，圖（c）的導(dǎo)游線路圖為v1→v2→v3→v2→v1→v4。遍歷結(jié)點(diǎn)序列與導(dǎo)游線路圖轉(zhuǎn)換的策略：設(shè)遍歷結(jié)果為v1→v2→…→vi→vi+1→…→vn對于結(jié)點(diǎn)vi和vi+1，如果vi和vi+1存在邊，則直接轉(zhuǎn)換。否則，加入邊vi→vi-1，如果vi-1和vi+1存在邊，則加入邊vi-1→vi+1。再否則，加入邊vi-1→vi-2，如果vi-2和vi+1存在邊，則加入邊vi-2→vi+1。如果vi-2和vi+1還不存在邊，繼續(xù)回溯，一定能找到某個整數(shù)k（因?yàn)榫包c(diǎn)分布圖是連通圖），使得vi-k和vi+1存在邊，則加入邊vi-k→vi+1。在本任務(wù)中，轉(zhuǎn)換后的線路圖存于數(shù)組vex1中。流程圖見10-29。拓樸排序子模塊流程圖，見圖10-39源程序，參見節(jié)的。求最短路徑子模塊流程圖：見10-34。源程序，參見節(jié)的。求最小生成樹子模塊流程圖：見19-33。源程序，參見節(jié)的。數(shù)據(jù)結(jié)構(gòu)景點(diǎn)的信息包括景點(diǎn)的名稱和近鄰景點(diǎn)之間的通路和距離。用鄰接鏈表存儲景點(diǎn)分布圖的信息。（帶權(quán)無向）圖的鄰接鏈表/***************************************************************//*程序功能：建立一個旅游景區(qū)管理系統(tǒng)，實(shí)現(xiàn)旅游路線選擇*//*景區(qū)道路優(yōu)化等功能*//***************************************************************/#include“”#include“”#include“”#defineMAX_EDGE_NUM100/*定義圖的最大邊數(shù)*/#defineMAX_VERTEX_NUM20#defineMAXNUM32767typedefcharVertex_type[10];typedefstructnode/*邊表結(jié)點(diǎn)*/{intadjvex;/*鄰接點(diǎn)域*/intweight;structnode*next;/*指向下一個鄰接點(diǎn)的指針域*/}Edge_node;typedefstruct/*頂點(diǎn)表結(jié)點(diǎn)*/{Vertex_typevertex;/*頂點(diǎn)域，存放景點(diǎn)名稱*/Edge_node*firstedge;/*邊表頭指針*/}Vertex_node;typedefstruct{Vertex_nodeadjlist[MAX_VERTEX_NUM];/*鄰接表*/intn,m;/*頂點(diǎn)數(shù)和邊數(shù)*/}Lgraph;邊的類型定義在求最小生成樹時，用到邊的定義。typedefstruct{inti;/*頂點(diǎn)vi的序號*/intj;/*頂點(diǎn)vi的序號*/intweight;}Edge_type;程序清單主程序源程序/*************************************************************//*函數(shù)名：main*//*入口參數(shù)：無*//*返回值：無*//*************************************************************/voidmain(){Lgraph*g,*g1;intsele;voidcreate_graph();voidoutput_graph();voiddfs_main();voidtopo_sort_main();voidmin_distance_main();voidmin_tree();g=(Lgraph*)malloc(sizeof(Lgraph));g->m=0;g1=(Lgraph*)malloc(sizeof(Lgraph));while(1){system("cls");printf(“\n\n******景區(qū)旅游管理信息系統(tǒng)******\n”);printf(“1.輸入景點(diǎn)分布圖\n”);printf(“2.輸出景點(diǎn)分布圖鄰接矩陣\n”);printf(“3.生成導(dǎo)游線路圖\n”);printf(“4.輸出導(dǎo)游線路圖中回路\n”);printf(“5.求兩景點(diǎn)間最短路徑和最短距離\n”);printf(“6.輸出景區(qū)道路修建規(guī)劃圖\n”);printf(“0.退出\n”);printf(“請選擇功能序號:”);scanf(“%d”,&sele);printf("\n\n***************************************************\n\n");switch(sele){case1:create_graph(g);break;case2:output_graph(g);break;case3:dfs_main(g,g1);break;case4:topo_sort_main(g1);break;case5:min_distance_main(g);break;case6:min_tree(g);break;case0:exit(0);}getchar();printf("按回車鍵繼續(xù)......");getchar();}}建圖子模塊源程序參見節(jié)的create_graph()函數(shù)。輸出圖子模塊/**************************************************************//*函數(shù)名：output_graph*//*函數(shù)功能：輸出圖G的鄰接矩陣*//*入口參數(shù)：g---鄰接鏈表*//*返回值：無*//**************************************************************/voidoutput_graph(Lgraph*g){inti,j,n;inta[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Edge_node*p;if(g->n==0){printf(“景點(diǎn)分布圖未輸入，無法輸出！\n”);return;}for(i=0;i<g->n;i++)for(j=0;j<g->n;j++)if(i==j)a[i][j]=0;elsea[i][j]=MAXNUM;for(i=0;i<g->n;i++){p=g->adjlist[i].firstedge;while(p!=NULL){j=p->adjvex;a[i][j]=p->weight;p=p->next;}}printf("景點(diǎn)分布圖鄰接矩陣為:\n\n");printf("%8s","");for(i=0;i<g->n;i++)printf("%8s",g->adjlist[i].vertex);for(i=0;i<g->n;i++){printf("%8s",g->adjlist[i].vertex);for(j=0;j<g->n;j++)printf("%9d",a[i][j]);printf(“\n”);}}遍歷子模塊/**************************************************************//*函數(shù)名：dfs_main*//*函數(shù)功能：生成導(dǎo)游線路圖*//*入口參數(shù)：g--景點(diǎn)分布圖*//*g1—導(dǎo)游線路圖*//*返回值：無*//**************************************************************/voiddfs_main(Lgraph*g,Lgraph*g1){intvisited[MAX_VERTEX_NUM];intx,i;intvex[MAX_VERTEX_NUM];intj,k,i1,tag;intvex1[MAX_VERTEX_NUM];Edge_node*p,*q;for(i=0;i<MAX_VERTEX_NUM;i++)visited[i]=0;if(g->n==0){printf(“景點(diǎn)分布圖未輸入，無法生成導(dǎo)游線圖！\n”);return;}do{printf("請輸入口景點(diǎn)序號：");scanf("%d",&x);if(x>=1&&x<=g->n){x--;break;}elseprintf("景點(diǎn)號輸入有誤，請重新輸入！\n");}while(1);j=0;dfs(g,x,visited,vex,&j);irstedge;while(p!=NULL&&p->adjvex!=j)/*判斷vi+k與vj之間有沒有邊*/p=p->next;