數據結構課程設計報告-校園導游程序

1、-. z課 程 設 計 說 明 書課程名稱數據構造課程設計設計課題校園導游程序專業(yè)計算機科學與技術班級*完成日期課 程 設 計 任 務 書設計題目：校園導游程序設計容與要求：問題描述用無向網表示你所在學校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠答復有關景點介紹、游覽路徑等問題。根本要求 1 查詢各景點的相關信息；2 查詢圖中任意兩個景點間的最短路徑。3 查詢圖中任意兩個景點間的所有路徑。4 增加、刪除、更新有關景點和道路的信息。 指導教師：2016年 12月 20日課 程 設 計 評 語 成績： 指導教師：

2、_ 年 月 日-. z目錄TOC o 1-3 h z uHYPERLINK l _Toc470807539一、問題描述 PAGEREF _Toc470807539 h 1HYPERLINK l _Toc470807540二、根本要求 PAGEREF _Toc470807540 h 1HYPERLINK l _Toc470807541三、測試數據 PAGEREF _Toc470807541 h 2HYPERLINK l _Toc470807542四、算法思想 PAGEREF _Toc470807542 h 3HYPERLINK l _Toc470807543五、模塊劃分 PAGEREF _Toc

3、470807543 h 4HYPERLINK l _Toc4708075445.1應用函數 PAGEREF _Toc470807544 h 4HYPERLINK l _Toc470807545主函數 PAGEREF _Toc470807545 h 5HYPERLINK l _Toc470807546查詢景點信息函數 PAGEREF _Toc470807546 h 6HYPERLINK l _Toc470807547查詢兩景點之間最短路徑函數 PAGEREF _Toc470807547 h 6HYPERLINK l _Toc470807548查詢兩景點之間所有路徑函數 PAGEREF _Toc4

4、70807548 h 7HYPERLINK l _Toc470807549刪除已有的頂點和路徑 PAGEREF _Toc470807549 h 8HYPERLINK l _Toc470807550修改已有的頂點和路徑 PAGEREF _Toc470807550 h 9HYPERLINK l _Toc470807551六、數據構造 PAGEREF _Toc470807551 h 10HYPERLINK l _Toc470807552七、測試 PAGEREF _Toc470807552 h 11HYPERLINK l _Toc470807553八、心得 PAGEREF _Toc470807553

5、h 19HYPERLINK l _Toc470807554九、源程序 PAGEREF _Toc470807554 h 20-. z問題描述用無向網表示你所在學校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠答復有關景點介紹、游覽路徑等問題。二、 根本要求1 查詢各景點的相關信息；2 查詢圖中任意兩個景點間的最短路徑。3 查詢圖中任意兩個景點間的所有路徑。4 增加、刪除、更新有關景點和道路的信息。三、 測試數據菜單函數：依次輸入：1，2，3，4，5，6，0 分別對應景點信息查詢，最短路徑查詢，所有路徑查詢，添加景點

6、及路徑信息，刪除景點及路徑信息，修改景點及路徑信息，退出。查詢景點信息：輸入：1，2分別對應按編號查詢，按景點名稱查詢按編號查詢：輸入編號：1按景點名稱查詢：輸入名稱：大明橋最短路徑查詢：輸入起始景點和終點景點編號：1，7所有路徑查詢：輸入起始景點和終點景點編號：2，8添加景點及路徑信息：輸入新景點序號：9輸入新景點名稱：南門 輸入新景點相關信息：充滿古韻的門，適合拍照 輸入到其余各景點的距離：50，100，20刪除景點及路徑信息：輸入：1，2分別對應按編號查詢，按景點名稱查詢按編號查詢：輸入需要刪除的景點編號：8修改景點及路徑信息：輸入：1，2分別對應修改景點信息，修改道路信息修改景點信息：

7、輸入1，2分別對應修改景點名稱，修改景點描述修改景點信息：輸入修改序號：1 輸入修改后的名稱：圖書館123-. z四、算法思想先利用CreateUDN 創(chuàng)立初始無向網，通過main主函數調用顯示，操作功能的選擇通過Menu函數輸出，根據游客需求選擇景點信息查詢、景點之間最短路徑查詢、景點之間所有路徑查詢、添加景點信息、刪除景點信息或者修改信息。如果是景點信息查詢， 在search中完成，再調用SearchMenu選擇是按照景點編號或者景點名稱查詢，游客輸入相應容。如果是景點之間最短路徑查詢或是景點之間所有路徑查詢則游客輸入起始景點和完畢景點；最短路徑是用ShortestPath實現，其中運用了

8、迪杰斯特拉算法；所有路徑由Searchpath1調用disppath再調用path，在path過遞歸算法實現尋找每一條路并輸出。如果是添加景點信息調用Addnewsight函數，游客按照提示依次輸入信息容。如果是刪除景點信息，選擇按照名稱刪除或是按照序號刪除，再調用Deletesight函數，游客輸入相應容進展刪除。如果是修改信息，調用Changesight，Changemenu兩個函數，游客按提示選擇修改景點信息或者道路信息，再按提示輸入修改后得容。輸出使用調用的相應函數。信息保存于文件中。校園導游圖添加景點和路徑查詢所有路徑查詢最短路徑修改景點和路徑修改路徑修改景點刪除景點和路徑按編號按名

9、稱查詢景點信息按編號按名稱修改名稱修改描述五、 模塊劃分5.1應用函數void CreateUDN(int v,int a); /* 造圖函數 */void narrate(); /*說明函數*/void ShortestPath(int num); /*最短路徑函數*/void output(int sight1,int sight2); /*輸出函數*/int Menu(); /* 主菜單 */void search(); /* 查詢景點信息 */int SearchMenu(); /* 查詢子菜單 */void HaMiTonian(int); /* 圖的遍歷 */void Search

10、path1(MGraph g); /*查詢兩個景點間的所有路徑*/void disppath(MGraph g,int i,int j);void path(MGraph g,int i,int j,int k);/*確定路徑上第k+1個頂點的序號*/void Ne*tValue(int); void display(); /* 顯示遍歷結果 */int Addnewsight(int n); /*添加新的景點和路徑*/int Deletesight(); /*刪除景點和路徑*/void Changesight(); /*修改景點和路徑*/int Changemenu(); /*修改路徑或頂點

11、的選擇菜單*/int Sightmenu(); /*選擇需該景點的菜單*/5.2.1主函數1.功能：初始圖通過main主函數調用顯示，操作功能的選擇通過Menu函數輸出，顯示為菜單形式提醒用戶進展操作，用戶選擇后在main主函數中調用各個函數實現各種功能。2.流程圖：6101432151 輸入相應序號 完畢 開場查詢信息刪除信息所有路徑添加信息最短路徑修改信息退出景點信息和操作目錄5.2.2查詢景點信息函數1.功能：在main主函數中調用search,翻開存儲了信息的文件，在顯示界面顯示已有的景點名稱和序號，游客按需求進展序號查詢或者名稱查詢，輸入需要查詢的序號或者名稱后會顯示該景點的名稱及簡

12、介，而后按任意鍵返回上級菜單項選擇擇繼續(xù)查詢或者返回主界面，在查詢景點信息函數中實現。2.流程圖：noyes21 開場按編號查詢按景點查詢 完畢 輸入相關信息是否有此景點？沒有找到！ 輸出景點信息5.2.3查詢兩景點之間最短路徑函數1.功能：在main函數中調用narrate函數，翻開存儲了信息的文件，游客輸入起點編號或者終點編號，利用迪杰斯特拉算法由ShortestPath最短路徑函數 選擇一條兩點之間的最短路徑展示給游客，關閉文件。5.2.4查詢兩景點之間所有路徑函數1.功能：當游客輸入完畢后，根據之前構建的無向圖，執(zhí)行過程為進層和退層兩個階段。首先開場遞歸進層，考慮使用基于深度優(yōu)先思想，

13、在搜素過程中，按照景點編號大小依次每一個節(jié)點，假設到一個未被且有路徑相通的點則將其參加數組P，直到找到目的地，輸出第一條路徑，然后開場遞歸退層，按照之前的方式遞歸它的所有未被的相鄰節(jié)點。并通過相應的設置標志visited的方式使最終能不重復地走遍所有的簡單路徑。最后輸出這些路徑即可。5.2.5添加新的頂點和路徑1.功能：在Addnewsight添加新的景點和路徑函數 中實現，翻開存儲了信息的文件，輸入需要新添加的景點名稱，根本信息介紹并依次輸入它到原有各景點的距離，將新信息存儲到文件中并保存。5.2.6刪除已有的頂點和路徑1.功能：刪除不需要的景點信息，并保存刪除后的文件，方便下一次瀏覽。2流

14、程圖：21no 完畢 是否有此景點？輸入需要刪除的景點刪除成功沒有找到yes 開場按景點編號按景點名稱5.2.7修改已有的頂點和路徑1.功能：修改有誤的景點信息，并保存修改后的文件，方便下一次瀏覽。2流程圖：221221 開場修改道路信息 完畢 輸入相關信息修改景點信息 輸入道路信息 輸入景點編號修改景點名稱修改景點描述 輸入相關信息六、 數據構造MGraph定義圖的類型 ，其中包含景點，景點之間的距離，景點數和邊數。Verte*Type是景點的構造體，里面包含了景點編號，景點名稱，景點描述。ArcCell是邊的構造體，其中包含了邊的長度即景點之間的距離。typedef struct ArcC

15、ellint adj; /* 相鄰接的景點之間的路程 */ArcCell; /* 定義邊的類型 */typedef struct Verte*Typeint number; /* 景點編號 */char sight100; /* 景點名稱 */ char description1000; /* 景點描述 */Verte*Type; /* 定義頂點的類型 */typedef structVerte*Type ve*20; /* 圖中的頂點，即為景點 */ArcCell arcs2020; /* 圖中的邊，即為景點間的距離 */int ve*num,arum; /* 頂點數，邊數 */MGraph

16、; /* 定義圖的類型 */七、 測試7.1.測試數據輸入：根據游客需求選擇景點信息查詢、景點之間最短路徑查詢、景點之間所有路徑查詢、添加景點信息、刪除景點信息或者修改信息。如果是景點信息查詢，再選擇是按照景點編號或者景點名稱查詢，游客輸入相應容；如果是景點之間最短路徑查詢或是景點之間所有路徑查詢則游客輸入起始景點和完畢景點；如果是添加景點信息則按照提示依次輸入信息容；如果是刪除景點信息，選擇按照名稱刪除或是按照序號刪除，再輸入相應容進展刪除；如果是修改信息，按提示選擇修改景點信息或者道路信息，再按提示輸入修改后得容預期的輸出結果：運行程序直接出現各景點及其編號，同時出現操作菜單，其他結果依使

17、用者需求而定，請參見程序后的運行結果。菜單函數2.查詢景點信息按編號3.查詢景點信息按名稱4.查詢兩景點之間的最短路徑5.查詢兩點之間的所有路徑6.添加新的景點及其路徑添加過程添加后7.刪除景點刪除過程刪除后8.修改景點信息修改后9.文件容八、 心得通過對這次對校園導游系統程序編寫，我切實體會到了如何編寫一個較大的程序。這是我自己相對獨立做的最大的一個程序，過程中遇到了各種各樣的問題。但同時穩(wěn)固了課堂上所學的知識，也學到了很多新的東西，也收獲了很多。 拿到題目，第一步就是構思，分析，創(chuàng)立。題目要求用無向網完成，所以我考慮的是用鄰接矩陣存儲這個無向網，參考了書上的無向網的鄰接矩陣存儲程序寫了Cr

18、eatUDN。查詢兩個景點之間的最短路徑剛開場我參考的是書上的迪杰斯特拉算法，后來發(fā)現書上定義的頂點的構造體數組容太簡單，程序考慮的情況也很簡單，無法滿足我題目的需求，于是我又把迪杰斯特拉算法研讀了一遍，自己做了改良。查找所有路徑的Searchpath1函數剛開場一直沒有寫出來，我和同學先在紙上畫出頂點，參考深度優(yōu)先遍歷把整個路徑走了一遍，但是編程沒有什么思路，上網查找了關于這個算法的資料，看到有人說可以考慮用遞歸實現，就試著用遞歸實現，同時參照迪杰斯特拉算法用一個數組收集過的頂點，還設置了一個標志量標記頂點是否被。文件在上學期的課設中我寫過，當時學習了一些關于文件的知識，所以運用并沒有遇到太

19、多問題，利用文件保存數據，需要fopen翻開文件進展讀寫，還要fclose函數進展關閉操作，可能還會用到fread讀取文件。后來知道a+可以繼續(xù)錄入，于是我通過參加一個a+形式的語句，實現了可不定時地增加景點數據的功能所有框架寫查找、刪除、修改和添加函數本身并不太難，寫好以后用main函數調用可以了。寫出框架后，剛開場運行也是沒什么問題的，但是多做幾步就遇到了問題。在添加的時候，剛開場沒有考慮序號，程序自動生成的序號和我想。要的并不是一種，于是我在添加景點里面讓游客自己輸入序號。后來又發(fā)現刪除沒有考慮找不到需要刪除的目標的可能性，用一個判斷符a來判斷是否刪除成功。接下來整個運行都沒有錯但是如果

20、刪除兩個景點就會出現問題了，試了很久發(fā)現是循環(huán)條件有問題，雖然固定了景點編號number，但是循環(huán)的num和number不能對應，于是去詢問教師，教師說可以把整個鄰接矩陣重新修改或者設置特殊符號控制輸出，我選擇了相對簡便的修改方法。這個程序很長，編寫花了很多時間，在程序編寫過程中，我不斷遇到困難，調試時更是出現了很多問題，一個個的修改，有的花了很長的時間。但我的努力和辛苦沒有白費，在教師的指導，同學的幫助，和自己的努力下我終于完成了這個程序。很感教師最后的點睛之筆，在我和同學冥思苦想很長時間都沒有解決方案的時候是教師幫助我們解決了問題。同時也反映出我思考問題的不全面和經歷的欠缺。 在程序編寫和

21、解決問題時，每一個細節(jié)都很重要，既要防止功能的重復也要防止功能疏漏的地方。理論和實踐相結合是學好數據構造的關鍵，這次的課設既培養(yǎng)了我們的自學能力，也提高了我們的學習興趣。九、 源程序#include #include #include #include #define Ma* 20000typedef struct ArcCellint adj; /* 相鄰接的景點之間的路程 */ArcCell; /* 定義邊的類型 */typedef struct Verte*Typeint number; /* 景點編號 */ char sight100; /* 景點名稱 */ char descript

22、ion1000; /* 景點描述 */Verte*Type; /* 定義頂點的類型 */typedef structVerte*Type ve*20; /* 圖中的頂點，即為景點 */ ArcCell arcs2020; /* 圖中的邊，即為景點間的距離 */ int ve*num,arum; /* 頂點數，邊數 */MGraph; /* 定義圖的類型 */FILE *fp,*count ; /*變量類型聲明，聲明fp是FILE型指針，用于指向file類型 */MGraph G; /* 把圖定義為全局變量 */char nameofschool100; /*學校名稱*/ int NUM=9;i

23、nt P2020; /* 用來存放圖中的邊 */int p20; /*全局數組，用來存放路徑上的各頂點*/int visited20; /*全局數組，用來記錄各頂點被的情況*/int a=0; /*全局變量，用來記錄每對頂點之間的所有路徑的條數*/long int D20; /* 輔助變量存儲最短路徑長度 */void CreateUDN(int v,int a); /* 造圖函數 */void narrate(); /*說明函數*/void ShortestPath(int num); /*最短路徑函數*/void output(int sight1,int sight2); /*輸出函數*

24、/int Menu(); /* 主菜單 */void search(); /* 查詢景點信息 */int SearchMenu(); /* 查詢子菜單 */void HaMiTonian(int); /* 圖的遍歷 */void Searchpath1(MGraph g); /*查詢兩個景點間的所有路徑*/void disppath(MGraph g,int i,int j);void path(MGraph g,int i,int j,int k); /*確定路徑上第k+1個頂點的序號*/void Ne*tValue(int); void display(); /* 顯示遍歷結果 */int

25、 Addnewsight(int n); /*添加新的景點和路徑*/int Deletesight(); /*刪除景點和路徑*/void Changesight(); /*修改景點和路徑*/int Changemenu(); /*修改路徑或頂點的選擇菜單*/int Sightmenu(); /*選擇需該景點的菜單*/void main() /* 主函數 */ int v0,v1; int ck; CreateUDN(NUM,11); do ck=Menu(); switch(ck)case 1: search(); break; case 2:system(cls);narrate(); pr

26、intf(nnttt請選擇起點景點0%d：,NUM-1); scanf(%d,&v0); printf(ttt請選擇終點景點0%d：,NUM-1); scanf(%d,&v1); ShortestPath(v0); /* 計算兩個景點之間的最短路徑 */ output(v0,v1); /* 輸出結果 */ printf(nntttt請按任意鍵繼續(xù).n); getchar(); getchar();break; case 3:system(cls); narrate(); Searchpath1(G); printf(nntttt請按任意鍵繼續(xù).n); getchar(); getchar();

27、 break;case 4: system(cls); narrate(); NUM=Addnewsight(NUM); system(cls); narrate(); break;case 5: NUM=Deletesight(); break;case 6:Changesight(); break;while(ck!=0); int Menu() /* 主菜單 */ int c; int flag; do flag=1; system(cls); narrate(); printf(ntttn); printf(tttn); printf(ttt 1、查詢景點信息 n); printf(t

28、tt 2、查詢兩景點間最短路徑 n); printf(ttt 3、查詢兩景點間所有路線 n); printf(ttt 4、添加新的景點和路徑 n); printf(ttt 5、刪除已有景點和路徑 n); printf(ttt 6、修改已有景點或路徑 n); printf(ttt 0、退出 n); printf(tttn); printf(tttn); printf(tttt請輸入您的選擇：); scanf(%d,&c); if(c=1|c=2|c=3|c=4|c=5|c=6|c=0) flag=0; while(flag); return c;int SearchMenu() /* 查詢子菜單

29、函數 */ int c; int flag; do flag=1; system(cls); narrate(); printf(ntttn); printf(tttn); printf(ttt 1、按照景點編號查詢 n); printf(ttt 2、按照景點名稱查詢 n); printf(ttt 0、返回 n); printf(tttn); printf(tttn); printf(tttt請輸入您的選擇：); scanf(%d,&c); if(c=1|c=2|c=0) flag=0; while(flag); return c;void search() /* 查詢景點信息函數 */ in

30、t num; int i; int c; char name20; fp=fopen(guide.t*t,r+); /*讀翻開原文件book.t*t*/ count=fopen(count.t*t,r+); /*讀寫count文件*/ do system(cls); c=SearchMenu(); switch (c) case 1: system(cls); narrate(); printf(nntt請輸入您要查找的景點編號：); scanf(%d,&num); for(i=0;iNUM;i+) if(num=G.ve*i.number) printf(nnttt您要查找景點信息如下:);

31、 printf(nnttt%s: %-25snn,G.ve*i.sight,G.ve*i.description); printf(nttt按任意鍵返回.); getchar(); getchar(); break; if(i=NUM) printf(nnttt沒有找到！); printf(nnttt按任意鍵返回.); getchar(); getchar(); break; case 2: system(cls); narrate(); printf(nntt請輸入您要查找的景點名稱：); scanf(%s,name); for(i=0;iNUM;i+) if(!strcmp(name,G.

32、ve*i.sight) printf(nnttt您要查找景點信息如下:); printf(nnttt%s:%-25snn,G.ve*i.sight,G.ve*i.description); printf(nttt按任意鍵返回.); getchar(); getchar(); break; if(i=NUM) printf(nnttt沒有找到！); printf(nnttt按任意鍵返回.); getchar(); getchar(); break; while(c!=0); fwrite(&G,sizeof(MGraph),1,fp); /*保存到文件中*/ fclose(fp); fprint

33、f(count,%d,NUM); fclose(count);void CreateUDN(int v,int a) /* 創(chuàng)立初始圖函數 */ int i,j; if(fp=fopen(guide.t*t,a+)=NULL) /調用了fopen,要用fclose關閉 ticket文件保存記錄的詳細信息 printf(文件未找到n); if(count=fopen(count.t*t,w+ )=NULL) /count文件保存記錄的條數 fprintf(count,0); else fscanf(count,%d,&NUM); strcpy(nameofschool,理工學院開元校區(qū)); G.

34、ve*num=v; /* 初始化構造中的景點數和邊數 */ G.arum=a; for(i=0;i20;+i) G.ve*i.number=i; /* 初始化每一個景點的編號 */ /* 初始化每一個景點名及其景點描述 */ strcpy(G.ve*0.sight,大明橋); strcpy(G.ve*0.description,落于小河上，風景優(yōu)美); strcpy(G.ve*1.sight,圖書館); strcpy(G.ve*1.description,環(huán)境優(yōu)雅，充滿書香氣息，呈環(huán)形); strcpy(G.ve*2.sight,教學樓); strcpy(G.ve*2.description,

35、上課和自習的地方,臨近圖書館); strcpy(G.ve*3.sight,子衿餐廳); strcpy(G.ve*3.description,一餐廳，新裝修過的餐廳，臨近實驗樓，是男女比例最適中的餐廳); strcpy(G.ve*4.sight,實驗A樓); strcpy(G.ve*4.description,教師辦公室); strcpy(G.ve*5.sight,實驗B樓); strcpy(G.ve*5.description,計算機機房); strcpy(G.ve*6.sight,實驗C樓); strcpy(G.ve*6.description,電氣實驗樓); strcpy(G.ve*7.s

36、ight,璞院餐廳); strcpy(G.ve*7.description,第二餐廳，臨近男生宿舍，食物種類比擬多); strcpy(G.ve*8.sight,琇院餐廳); strcpy(G.ve*8.description,第三餐廳，臨近女生宿舍樓，比擬廉價); /* 這里把所有的邊假定為20000，含義是這兩個景點之間是不可到達,極大值 */ for(i=0;i20;+i) for(j=0;j20;+j) G.arcsij.adj=Ma*; /* 下邊是可直接到達的景點間的距離，由于兩個景點間距離是互相的， 所以要對圖中對稱的邊同時賦值。 */ G.arcs01.adj=G.arcs10.

37、adj=50; G.arcs13.adj=G.arcs31.adj=70; G.arcs06.adj=G.arcs60.adj=250; G.arcs14.adj=G.arcs41.adj=80; G.arcs24.adj=G.arcs42.adj=100; G.arcs35.adj=G.arcs53.adj=90; G.arcs52.adj=G.arcs25.adj=100; G.arcs46.adj=G.arcs64.adj=75; G.arcs47.adj=G.arcs74.adj=300; G.arcs27.adj=G.arcs72.adj=400; G.arcs78.adj=G.ar

38、cs87.adj=40; fwrite(&G,sizeof(MGraph),1,fp); /保存到文件中fclose(fp); /關閉文件,但不是屏幕fprintf(count,%d,NUM); fclose(count); void narrate() /* 說明函數 */ int i; printf(nt*歡送使用%s校園導游程序*n,nameofschool); printf(t_n); printf(tttt 景點名稱ttttttn); printf(ttt_n); for(i=0;iNUM;i+) if(G.ve*i.number!=-1) printf(tttt%c (%2d)%-

39、10s%cn,3,G.ve*i.number,G.ve*i.sight,3); /* 輸出景點列表 */ printf(ttt_n);void ShortestPath(int num) /* 迪杰斯特拉算法最短路徑函數 num為入口點的編號 */ int v,w,i,t; /* i、w和v為計數輔助變量 */ int final20; /* 輔助數組 */ int min; fp=fopen(guide.t*t,r+); /讀翻開原文件book.t*t count=fopen(count.t*t,r+); /讀寫count文件 for(v=0;vNUM;v+) finalv=0; /* 假設

40、從頂點num到頂點v沒有最短路徑 */ Dv=G.arcsnumv.adj;/* 將與之相關的權值放入D中存放 */ for(w=0;wNUM;w+) /* 設置為空路徑 */ Pvw=0; if(Dv20000) /* 存在路徑 */ Pvnum=1; /* 存在標志置為1 */ Pvv=1; /* 自身到自身 */ Dnum=0; finalnum=1; /* 初始化num頂點屬于S集合 */ /* 開場主循環(huán)，每一次求得num到*個頂點的最短路徑，并將其參加到S集合 */ for(i=0;iNUM;+i) /* 其余G.ve*num-1個頂點 */ min=Ma*; /* 當前所知離頂點

41、num的最近距離 */ for(w=0;wNUM;+w) if(!finalw) /* w頂點在v-s中 */ if(Dwmin) /* w頂點離num頂點更近 */ v=w; min=Dw; finalv=1; /* 離num頂點更近的v參加到s集合 */ for(w=0;wNUM;+w) /* 更新當前最短路徑極其距離 */ if(!finalw&(min+G.arcsvw.adj)Dw)/* 不在s集合，并且比以前所找到的路徑都短就更新當前路徑 */ Dw=min+G.arcsvw.adj; for(t=0;tNUM;t+) Pwt=Pvt; Pww=1; fwrite(&G,sizeo

42、f(MGraph),1,fp); /保存到文件中 fclose(fp); fprintf(count,%d,NUM); fclose(count);void output(int sight1,int sight2) /* 輸出函數 */int a,b,c,d,q=0; a=sight2; /* 將景點二賦值給a */ if(a!=sight1) /* 如果景點二不和景點一輸入重合，則進展. */printf(nt從%s到%s的最短路徑是,G.ve*sight1.sight,G.ve*sight2.sight);/* 輸出提示信息 */ printf(t(最短距離為 %dm.)nnt,Da);

43、 /* 輸出sight1到sight2的最短路徑長度，存放在D數組中 */ printf(t%s,G.ve*sight1.sight); /* 輸出景點一的名稱 */ d=sight1; /* 將景點一的編號賦值給d */ for(c=0;cNUM;+c) gate:; /* 標號，可以作為goto語句跳轉的位置 */ Pasight1=0; for(b=0;bNUM;b+) if(G.arcsdb.adj%s,G.ve*b.sight); /* 輸出此節(jié)點的名稱 */ q=q+1; /* 計數變量加一，滿8控制輸出時的換行 */ Pab=0; d=b; /* 將b作為出發(fā)點進展下一次循環(huán)輸出

44、，如此反復 */ if(q%8=0) printf(n); goto gate; /*從當前位置出發(fā)*/ void Searchpath1(MGraph g)/*查詢兩個景點間的所有路徑*/int l=0;int k=0;int i,j;fp=fopen(guide.t*t,r+);/讀翻開原文件book.t*tcount=fopen(count.t*t,r+);/讀寫count文件 printf(選擇出發(fā)景點：); scanf(%d,&i); printf(選擇目地景點：); scanf(%d,&j); for(;kg.ve*num;k+)/*g.ve*number表示網中的頂點個數*/ i

45、f(i=g.ve*k.number) i=k;/*在網中找到其編號與輸入的出發(fā)景點的編號一樣的頂點*/ for(;lg.ve*num;l+) if(j=g.ve*l.number) j=l;/*在網中找到其編號與輸入的目地景點的編號一樣的頂點*/ printf(n從%s到%s的所有游覽路徑有:nn,g.ve*i.sight,g.ve*j.sight);/*輸出出發(fā)景點和目地景點的名稱*/disppath(g,i,j);/*調用disppath函數,用來輸出兩個景點間的所有路徑*/ fwrite(&G,sizeof(MGraph),1,fp); /保存到文件中 fclose(fp); fprin

46、tf(count,%d,NUM); fclose(count);void disppath(MGraph g,int i,int j) int k;p0=i; /把i賦給P0，P是一條道路上的所有景點的數組for(k=0;kg.ve*num;k+)visitedi=0;/*初始化各頂點的標志位，即都為未過的*/a=0;/*初始化路徑的條數*/path(g,i,j,0);/*通過調用path函數，找到從vi到vj的所有路徑并輸出*/void path(MGraph g,int i,int j,int k)/*確定路徑上第k+1個頂點的序號*/int s;if(pk=j)/*找到一條路徑*/a+;

47、/*路徑的條數值加1*/printf(第%d條:t,a);for(s=0;s);/coutg.ve*ps.sight;printf(%sn,g.ve*ps.sight); s=0; /從第一個景點開場while(sg.ve*num)if(s!=i)/*保證找到的是簡單路徑*/if(g.arcspks.adj!=Ma*&visiteds=0)/*當vk與vs之間有邊存在且vs未被過*/visiteds=1;/*置標志位為1,即已的*/pk+1=s;/*將頂點s參加到p數組中*/ path(g,i,j,k+1);/*遞歸調用之*/ visiteds=0;/*重置標志位為0，即未的，以便該頂點能被重

48、新使用*/s+; int Addnewsight(int n) /添加函數int i,b;char sight100,description1000;int length; fp=fopen(guide.t*t,r+);/讀翻開原文件book.t*tcount=fopen(count.t*t,r+);/讀寫count文件 printf(請輸入新景點的序號：n);scanf(%d,&b);printf(請輸入新景點的名稱：n);scanf(%s,&sight);printf(請輸入新景點的相關信息：n);scanf(%s,&description);G.ve*n.number=b;strcpy(

49、G.ve*n.sight,sight); strcpy(G.ve*n.description,description);for(i=0;in;i+) system(cls); narrate();printf(請輸入此景點到第%d個景點的距離單位：m同一景點或不可到達用20000表示，極大值：n,i);scanf(%d,&length);if(length!=20000);G.arum+;G.arcsni.adj=G.arcsin.adj=length;NUM+;n+;G.ve*num+; fwrite(&G,sizeof(MGraph),1,fp); /保存到文件中 fclose(fp);

50、fprintf(count,%d,NUM); fclose(count);return n;int Deletesight(int n) /*刪除函數*/ int i,a=0;int j;int c;int num;char name20;system(cls); fp=fopen(guide.t*t,r+);/讀翻開原文件book.t*tcount=fopen(count.t*t,r+);/讀寫count文件 c=SearchMenu(); switch (c) case 1: system(cls); narrate(); printf(nntt請輸入您要刪除景點的編號：); scanf(

51、%d,&num); for(i=0;iNUM;i+) if(num=G.ve*i.number) /查找到編號 a=1;for(j=0;jNUM;j+)if(G.arcsij.adj!=20000)G.arum-; /如果該頂點與其他頂點間有邊相連，邊數減一 G.arcsij.adj=G.arcsji.adj=20000; /將該頂點與其他頂點間的距離初始化為無窮大20000) G.ve*num.number=-1; /從要刪除的頂點之后的頂點開場，向前覆蓋 即刪除操作strcmp(G.ve*num.sight,*); strcmp(G.ve*num.description,+); if(a=

52、1) printf(nttt刪除成功！按任意鍵返回.);getchar(); getchar(); if(a=0)printf(該編號不存在！); getchar(); getchar(); break; case 2: system(cls); narrate(); printf(nntt請輸入您要刪除景點的名稱：); scanf(%s,name); for(i=0;iNUM;i+) if(!strcmp(name,G.ve*i.sight) a=1; num=i; for(j=0;jNUM;j+) if(G.arcsij.adj!=20000) G.arum-;G.arcsij.adj=G.arcsji.adj=20000; G.ve*num.number=-1; /從要刪除的頂點之后的頂點開場，向前覆蓋 即刪除操作 strcmp(G.ve*num.sight,*); strcmp(G.ve*num.description,+); if(a=1) printf(刪除成功！); printf(nttt按任意鍵返回.); getchar()