數(shù)據(jù)結(jié)構課程設計報告[共39頁]

1、洛 陽 理 工 學 院課 程 設 計 說 明 書課程名稱 數(shù)據(jù)結(jié)構課程設計 設計課題 校園導游程序 專 業(yè) 計算機科學與技術 班 級 學 號 姓 名 完成日期 課 程 設 計 任 務 書設計題目： 校園導游程序 設計內(nèi)容與要求：問題描述用無向網(wǎng)表示你所在學校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠回答有關景點介紹、游覽路徑等問題?；疽?（1） 查詢各景點的相關信息；（2） 查詢圖中任意兩個景點間的最短路徑。（3） 查詢圖中任意兩個景點間的所有路徑。（4） 增加、刪除、更新有關景點和道路的信息。 指導教師

2、： 2016 年 12 月 20 日課 程 設 計 評 語 成績： 指導教師：_ 年 月 日目錄一、問題描述1二、 基本要求1三、 測試數(shù)據(jù)2四、算法思想3五、 模塊劃分45.1應用函數(shù)45.2.1主函數(shù)55.2.2查詢景點信息函數(shù)65.2.3查詢兩景點之間最短路徑函數(shù)65.2.4查詢兩景點之間所有路徑函數(shù)75.2.6刪除已有的頂點和路徑85.2.7修改已有的頂點和路徑9六、 數(shù)據(jù)結(jié)構10七、 測試11八、 心得19九、 源程序20一、 問題描述用無向網(wǎng)表示你所在學校的校園景點平面圖，圖中頂點表示主要景點，存放景點的編號、名稱、簡介等信息，圖中的邊表示景點間的道路，存放路徑長度等信息。要求能夠

3、回答有關景點介紹、游覽路徑等問題。二、 基本要求（1） 查詢各景點的相關信息；（2） 查詢圖中任意兩個景點間的最短路徑。（3） 查詢圖中任意兩個景點間的所有路徑。（4） 增加、刪除、更新有關景點和道路的信息。三、 測試數(shù)據(jù)菜單函數(shù)：依次輸入：1，2，3，4，5，6，0 分別對應景點信息查詢，最短路徑查詢，所有路徑查詢，添加景點及路徑信息，刪除景點及路徑信息，修改景點及路徑信息，退出。查詢景點信息：輸入：1，2分別對應按編號查詢，按景點名稱查詢按編號查詢：輸入編號：1按景點名稱查詢：輸入名稱：大明橋最短路徑查詢：輸入起始景點和終點景點編號：1，7所有路徑查詢：輸入起始景點和終點景點編號：2，8添

4、加景點及路徑信息：輸入新景點序號：9 輸入新景點名稱：南門 輸入新景點相關信息：充滿古韻的門，適合拍照 輸入到其余各景點的距離：50，100，20刪除景點及路徑信息：輸入：1，2分別對應按編號查詢，按景點名稱查詢按編號查詢：輸入需要刪除的景點編號：8修改景點及路徑信息：輸入：1，2分別對應修改景點信息，修改道路信息修改景點信息：輸入1，2分別對應修改景點名稱，修改景點描述修改景點信息：輸入修改序號：1 輸入修改后的名稱：圖書館1232四、算法思想先利用CreateUDN 創(chuàng)建初始無向網(wǎng)，通過main主函數(shù)調(diào)用顯示，操作功能的選擇通過Menu函數(shù)輸出，根據(jù)游客需求選擇景點信息查詢、景點之間最短路

5、徑查詢、景點之間所有路徑查詢、添加景點信息、刪除景點信息或者修改信息。如果是景點信息查詢， 在search中完成，再調(diào)用SearchMenu選擇是按照景點編號或者景點名稱查詢，游客輸入相應內(nèi)容。如果是景點之間最短路徑查詢或是景點之間所有路徑查詢則游客輸入起始景點和結(jié)束景點；最短路徑是用ShortestPath實現(xiàn)，其中運用了迪杰斯特拉算法；所有路徑由Searchpath1調(diào)用disppath再調(diào)用path，在path中通過遞歸算法實現(xiàn)尋找每一條路并輸出。如果是添加景點信息調(diào)用Addnewsight函數(shù)，游客按照提示依次輸入信息內(nèi)容。如果是刪除景點信息，選擇按照名稱刪除或是按照序號刪除，再調(diào)用D

6、eletesight函數(shù)，游客輸入相應內(nèi)容進行刪除。如果是修改信息，調(diào)用Changesight，Changemenu兩個函數(shù)，游客按提示選擇修改景點信息或者道路信息，再按提示輸入修改后得內(nèi)容。輸出使用調(diào)用的相應函數(shù)。信息保存于文件中。校園導游圖添加景點和路徑查詢所有路徑查詢最短路徑修改景點和路徑修改路徑修改景點刪除景點和路徑按編號按名稱查詢景點信息按編號按名稱修改名稱修改描述五、 模塊劃分5.1應用函數(shù)void CreateUDN(int v,int a); /* 造圖函數(shù) */void narrate(); /*說明函數(shù)*/void ShortestPath(int num); /*最短路徑

7、函數(shù)*/void output(int sight1,int sight2); /*輸出函數(shù)*/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 N

8、extValue(int); void display(); /* 顯示遍歷結(jié)果 */int Addnewsight(int n); /*添加新的景點和路徑*/int Deletesight(); /*刪除景點和路徑*/void Changesight(); /*修改景點和路徑*/int Changemenu(); /*修改路徑或頂點的選擇菜單*/int Sightmenu(); /*選擇需該景點的菜單*/5.2.1主函數(shù)1.功能：初始圖通過main主函數(shù)調(diào)用顯示，操作功能的選擇通過Menu函數(shù)輸出，顯示為菜單形式提醒用戶進行操作，用戶選擇后在main主函數(shù)中調(diào)用各個函數(shù)實現(xiàn)各種功能。2.流程

9、圖：6101432151 輸入相應序號 結(jié)束 開始查詢信息刪除信息所有路徑添加信息最短路徑修改信息退出景點信息和操作目錄5.2.2查詢景點信息函數(shù)1.功能：在main主函數(shù)中調(diào)用search,打開存儲了信息的文件，在顯示界面顯示已有的景點名稱和序號，游客按需求進行序號查詢或者名稱查詢，輸入需要查詢的序號或者名稱后會顯示該景點的名稱及簡介，而后按任意鍵返回上級菜單選擇繼續(xù)查詢或者返回主界面，在查詢景點信息函數(shù)中實現(xiàn)。2.流程圖：noyes21 開始按編號查詢按景點查詢 結(jié)束 輸入相關信息是否有此景點？沒有找到！ 輸出景點信息 5.2.3查詢兩景點之間最短路徑函數(shù)1.功能：在main函數(shù)中調(diào)用na

10、rrate函數(shù)，打開存儲了信息的文件，游客輸入起點編號或者終點編號，利用迪杰斯特拉算法 由ShortestPath最短路徑函數(shù) 選擇一條兩點之間的最短路徑展示給游客，關閉文件。5.2.4查詢兩景點之間所有路徑函數(shù)1.功能：當游客輸入完畢后，根據(jù)之前構建的無向圖，執(zhí)行過程為進層和退層兩個階段。首先開始遞歸進層，考慮使用基于深度優(yōu)先思想，在搜素過程中，按照景點編號大小依次訪問每一個節(jié)點，若訪問到一個未被訪問且有路徑相通的點則將其加入數(shù)組P，直到找到目的地，輸出第一條路徑，然后開始遞歸退層，按照之前的方式遞歸訪問它的所有未被訪問的相鄰節(jié)點。并通過相應的設置標志visited的方式使最終能不重復地走遍

11、所有的簡單路徑。最后輸出這些路徑即可。5.2.5添加新的頂點和路徑1.功能：在Addnewsight添加新的景點和路徑函數(shù) 中實現(xiàn)，打開存儲了信息的文件，輸入需要新添加的景點名稱，基本信息介紹并依次輸入它到原有各景點的距離，將新信息存儲到文件中并保存。5.2.6刪除已有的頂點和路徑1.功能：刪除不需要的景點信息，并保存刪除后的文件，方便下一次瀏覽。2流程圖：21no 結(jié)束 是否有此景點？輸入需要刪除的景點刪除成功沒有找到y(tǒng)es 開始按景點編號按景點名稱5.2.7修改已有的頂點和路徑1.功能：修改有誤的景點信息，并保存修改后的文件，方便下一次瀏覽。2流程圖：221221 開始修改道路信息 結(jié)束

12、輸入相關信息修改景點信息 輸入道路信息 輸入景點編號修改景點名稱修改景點描述 輸入相關信息六、 數(shù)據(jù)結(jié)構MGraph定義圖的類型 ，其中包含景點，景點之間的距離，景點數(shù)和邊數(shù)。VertexType是景點的結(jié)構體，里面包含了景點編號，景點名稱，景點描述。ArcCell是邊的結(jié)構體，其中包含了邊的長度即景點之間的距離。typedef struct ArcCellint adj; /* 相鄰接的景點之間的路程 */ArcCell; /* 定義邊的類型 */typedef struct VertexTypeint number; /* 景點編號 */ char sight100; /* 景點名稱 */

13、 char description1000; /* 景點描述 */VertexType; /* 定義頂點的類型 */typedef structVertexType vex20; /* 圖中的頂點，即為景點 */ ArcCell arcs2020; /* 圖中的邊，即為景點間的距離 */ int vexnum,arcnum; /* 頂點數(shù)，邊數(shù) */MGraph; /* 定義圖的類型 */七、 測試 7.1.測試數(shù)據(jù)輸入：根據(jù)游客需求選擇景點信息查詢、景點之間最短路徑查詢、景點之間所有路徑查詢、添加景點信息、刪除景點信息或者修改信息。如果是景點信息查詢，再選擇是按照景點編號或者景點名稱查詢，游

14、客輸入相應內(nèi)容；如果是景點之間最短路徑查詢或是景點之間所有路徑查詢則游客輸入起始景點和結(jié)束景點；如果是添加景點信息則按照提示依次輸入信息內(nèi)容；如果是刪除景點信息，選擇按照名稱刪除或是按照序號刪除，再輸入相應內(nèi)容進行刪除；如果是修改信息，按提示選擇修改景點信息或者道路信息，再按提示輸入修改后得內(nèi)容預期的輸出結(jié)果：運行程序直接出現(xiàn)各景點及其編號，同時出現(xiàn)操作菜單，其他結(jié)果依使用者需求而定，請參見程序后的運行結(jié)果。1. 菜單函數(shù)2.查詢景點信息（按編號）3.查詢景點信息（按名稱）4.查詢兩景點之間的最短路徑5.查詢兩點之間的所有路徑6.添加新的景點及其路徑添加過程添加后7.刪除景點刪除過程刪除后8.

15、修改景點信息修改后9.文件內(nèi)容八、 心得 通過對這次對校園導游系統(tǒng)程序編寫，我切實體會到了如何編寫一個較大的程序。這是我自己相對獨立做的最大的一個程序，過程中遇到了各種各樣的問題。但同時鞏固了課堂上所學的知識，也學到了很多新的東西，也收獲了很多。 拿到題目，第一步就是構思，分析，創(chuàng)建。題目要求用無向網(wǎng)完成，所以我考慮的是用鄰接矩陣存儲這個無向網(wǎng)，參考了書上的無向網(wǎng)的鄰接矩陣存儲程序?qū)懥薈reatUDN。查詢兩個景點之間的最短路徑剛開始我參考的是書上的迪杰斯特拉算法，后來發(fā)現(xiàn)書上定義的頂點的結(jié)構體數(shù)組內(nèi)容太簡單，程序考慮的情況也很簡單，無法滿足我題目的需求，于是我又把迪杰斯特拉算法研讀了一遍，自

16、己做了改進。查找所有路徑的Searchpath1函數(shù)剛開始一直沒有寫出來，我和同學先在紙上畫出頂點，參考深度優(yōu)先遍歷把整個路徑走了一遍，但是編程沒有什么思路，上網(wǎng)查找了關于這個算法的資料，看到有人說可以考慮用遞歸實現(xiàn)，就試著用遞歸實現(xiàn)，同時參照迪杰斯特拉算法用一個數(shù)組收集訪問過的頂點，還設置了一個標志量標記頂點是否被訪問。文件在上學期的課設中我寫過，當時學習了一些關于文件的知識，所以運用并沒有遇到太多問題，利用文件保存數(shù)據(jù)，需要fopen打開文件進行讀寫，還要fclose函數(shù)進行關閉操作，可能還會用到fread讀取文件。后來知道a+可以繼續(xù)錄入，于是我通過加入一個a+形式的語句，實現(xiàn)了可不定時

17、地增加景點數(shù)據(jù)的功能所有框架寫查找、刪除、修改和添加函數(shù)本身并不太難，寫好以后用main函數(shù)調(diào)用可以了。寫出框架后，剛開始運行也是沒什么問題的，但是多做幾步就遇到了問題。在添加的時候，剛開始沒有考慮序號，程序自動生成的序號和我想。要的并不是一種，于是我在添加景點里面讓游客自己輸入序號。后來又發(fā)現(xiàn)刪除沒有考慮找不到需要刪除的目標的可能性，用一個判斷符a來判斷是否刪除成功。接下來整個運行都沒有錯但是如果刪除兩個景點就會出現(xiàn)問題了，試了很久發(fā)現(xiàn)是循環(huán)條件有問題，雖然固定了景點編號number，但是循環(huán)的num和number不能對應，于是去詢問老師，老師說可以把整個鄰接矩陣重新修改或者設置特殊符號控制

18、輸出，我選擇了相對簡便的修改方法。這個程序很長，編寫花了很多時間，在程序編寫過程中，我不斷遇到困難，調(diào)試時更是出現(xiàn)了很多問題，一個個的修改，有的花了很長的時間。但我的努力和辛苦沒有白費，在老師的指導，同學的幫助，和自己的努力下我終于完成了這個程序。很感謝老師最后的點睛之筆，在我和同學冥思苦想很長時間都沒有解決方案的時候是老師幫助我們解決了問題。同時也反映出我思考問題的不全面和經(jīng)驗的欠缺。 在程序編寫和解決問題時，每一個細節(jié)都很重要，既要避免功能的重復也要避免功能疏漏的地方。理論和實踐相結(jié)合是學好數(shù)據(jù)結(jié)構的關鍵，這次的課設既培養(yǎng)了我們的自學能力，也提高了我們的學習興趣。九、 源程序#includ

19、e #include #include #include #define Max 20000typedef struct ArcCellint adj; /* 相鄰接的景點之間的路程 */ArcCell; /* 定義邊的類型 */typedef struct VertexTypeint number; /* 景點編號 */ char sight100; /* 景點名稱 */ char description1000; /* 景點描述 */VertexType; /* 定義頂點的類型 */typedef structVertexType vex20; /* 圖中的頂點，即為景點 */ ArcCe

20、ll arcs2020; /* 圖中的邊，即為景點間的距離 */ int vexnum,arcnum; /* 頂點數(shù)，邊數(shù) */MGraph; /* 定義圖的類型 */FILE *fp,*count ; /*變量類型聲明，聲明fp是FILE型指針，用于指向file類型 */MGraph G; /* 把圖定義為全局變量 */char nameofschool100; /*學校名稱*/ int NUM=9;int P2020; /* 用來存放圖中的邊 */int p20; /*全局數(shù)組，用來存放路徑上的各頂點*/int visited20; /*全局數(shù)組，用來記錄各頂點被訪問的情況*/int a=

21、0; /*全局變量，用來記錄每對頂點之間的所有路徑的條數(shù)*/long int D20; /* 輔助變量存儲最短路徑長度 */ void CreateUDN(int v,int a); /* 造圖函數(shù) */void narrate(); /*說明函數(shù)*/void ShortestPath(int num); /*最短路徑函數(shù)*/void output(int sight1,int sight2); /*輸出函數(shù)*/int Menu(); /* 主菜單 */void search(); /* 查詢景點信息 */int SearchMenu(); /* 查詢子菜單 */void HaMiTonian

22、(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 NextValue(int); void display(); /* 顯示遍歷結(jié)果 */int Addnewsight(int n); /*添加新的景點和路徑*/int Deletesight(); /*刪除景點和路徑*/void Changesight(); /*修改景點和路徑

23、*/int Changemenu(); /*修改路徑或頂點的選擇菜單*/int Sightmenu(); /*選擇需該景點的菜單*/void main() /* 主函數(shù) */ int v0,v1; int ck; CreateUDN(NUM,11); do ck=Menu(); switch(ck)case 1: search(); break; case 2:system(cls);narrate(); printf(nnttt請選擇起點景點（0%d）：,NUM-1); scanf(%d,&v0); printf(ttt請選擇終點景點（0%d）：,NUM-1); scanf(%d,&v1);

24、 ShortestPath(v0); /* 計算兩個景點之間的最短路徑 */ output(v0,v1); /* 輸出結(jié)果 */ printf(nntttt請按任意鍵繼續(xù).n); getchar(); getchar();break; case 3:system(cls); narrate(); Searchpath1(G); printf(nntttt請按任意鍵繼續(xù).n); getchar(); getchar(); break;case 4: system(cls); narrate(); NUM=Addnewsight(NUM); system(cls); narrate(); brea

25、k;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(ttt n); printf(ttt 1、查詢景點信息 n); printf(ttt 2、查詢兩景點間最短路徑 n); printf(ttt 3、查詢兩景點間所有路線 n); printf(ttt 4、添加新的景點和路徑 n); printf(ttt 5、

26、刪除已有景點和路徑 n); printf(ttt 6、修改已有景點或路徑 n); printf(ttt 0、退出 n); printf(ttt n); 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() /* 查詢子菜單函數(shù) */ int c; int flag; do flag=1; system(cls); narrate(); printf(ntttn); printf(ttt n);

27、 printf(ttt 1、按照景點編號查詢 n); printf(ttt 2、按照景點名稱查詢 n); printf(ttt 0、返回 n); printf(ttt n); printf(tttn); printf(tttt請輸入您的選擇：); scanf(%d,&c); if(c=1|c=2|c=0) flag=0; while(flag); return c;void search() /* 查詢景點信息函數(shù) */ int num; int i; int c; char name20; fp=fopen(guide.txt,r+); /*讀打開原文件book.txt*/ count=fo

28、pen(count.txt,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.vexi.number) printf(nnttt您要查找景點信息如下:); printf(nnttt%s: %-25snn,G.vexi.sight,G.vexi.description); printf(nttt按任意鍵返回.); getch

29、ar(); 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.vexi.sight) printf(nnttt您要查找景點信息如下:); printf(nnttt%s:%-25snn,G.vexi.sight,G.vexi.desc

30、ription); 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); fprintf(count,%d,NUM); fclose(count);void CreateUDN(int v,int a) /* 創(chuàng)建初始圖函數(shù) */ int i,j; if(

31、fp=fopen(guide.txt,a+)=NULL) /調(diào)用了fopen,要用fclose關閉 ticket文件保存記錄的詳細信息 printf(文件未找到n); if(count=fopen(count.txt,w+ )=NULL) /count文件保存記錄的條數(shù) fprintf(count,0); else fscanf(count,%d,&NUM); strcpy(nameofschool,洛陽理工學院開元校區(qū)); G.vexnum=v; /* 初始化結(jié)構中的景點數(shù)和邊數(shù) */ G.arcnum=a; for(i=0;i20;+i) G.vexi.number=i; /* 初始化每一

32、個景點的編號 */ /* 初始化每一個景點名及其景點描述 */ strcpy(G.vex0.sight,大明橋); strcpy(G.vex0.description,落于小河上，風景優(yōu)美); strcpy(G.vex1.sight,圖書館); strcpy(G.vex1.description,環(huán)境優(yōu)雅，充滿書香氣息，呈環(huán)形); strcpy(G.vex2.sight,教學樓); strcpy(G.vex2.description,上課和自習的地方,臨近圖書館); strcpy(G.vex3.sight,子衿餐廳); strcpy(G.vex3.description,一餐廳，新裝修過的餐廳

33、，臨近實驗樓，是男女比例最適中的餐廳); strcpy(G.vex4.sight,實驗A樓); strcpy(G.vex4.description,老師辦公室); strcpy(G.vex5.sight,實驗B樓); strcpy(G.vex5.description,計算機機房); strcpy(G.vex6.sight,實驗C樓); strcpy(G.vex6.description,電氣實驗樓); strcpy(G.vex7.sight,璞院餐廳); strcpy(G.vex7.description,第二餐廳，臨近男生宿舍，食物種類比較多); strcpy(G.vex8.sight,琇

34、院餐廳); strcpy(G.vex8.description,第三餐廳，臨近女生宿舍樓，比較便宜); /* 這里把所有的邊假定為20000，含義是這兩個景點之間是不可到達,極大值 */ for(i=0;i20;+i) for(j=0;j20;+j) G.arcsij.adj=Max; /* 下邊是可直接到達的景點間的距離，由于兩個景點間距離是互相的， 所以要對圖中對稱的邊同時賦值。 */ G.arcs01.adj=G.arcs10.adj=50; G.arcs13.adj=G.arcs31.adj=70; G.arcs06.adj=G.arcs60.adj=250; G.arcs14.adj

35、=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.arcs87.adj=40; fwrite(&G,sizeof(MGraph),1,fp); /保存到文件中fclose(fp); /關閉文件,但不是屏幕fprint

36、f(count,%d,NUM); fclose(count); void narrate() /* 說明函數(shù) */ int i; printf(nt*歡迎使用%s校園導游程序*n,nameofschool); printf(t_n); printf(tttt 景點名稱ttttttn); printf(ttt_n); for(i=0;iNUM;i+) if(G.vexi.number!=-1) printf(tttt%c (%2d)%-10s%cn,3,G.vexi.number,G.vexi.sight,3); /* 輸出景點列表 */ printf(ttt_n);void ShortestP

37、ath(int num) /* 迪杰斯特拉算法最短路徑函數(shù) num為入口點的編號 */ int v,w,i,t; /* i、w和v為計數(shù)輔助變量 */ int final20; /* 輔助數(shù)組 */ int min; fp=fopen(guide.txt,r+); /讀打開原文件book.txt count=fopen(count.txt,r+); /讀寫count文件 for(v=0;vNUM;v+) finalv=0; /* 假設從頂點num到頂點v沒有最短路徑 */ Dv=G.arcsnumv.adj;/* 將與之相關的權值放入D中存放 */ for(w=0;wNUM;w+) /* 設置

38、為空路徑 */ 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.vexnum-1個頂點 */ min=Max; /* 當前所知離頂點num的最近距離 */ for(w=0;wNUM;+w) if(!finalw) /* w頂點在v-s中 */ if(Dwmin) /* w頂點離num頂點更近

39、*/ 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,sizeof(MGraph),1,fp); /保存到文件中 fclose(fp); fprintf(count,%d,NUM); fclose(count);void output(int sight1,int sight2) /* 輸出函數(shù) */int a,b,c,d,q=0; a=sight2; /* 將景點二賦值給a */ if(a!=sight1) /* 如果景點二不和景點一輸入重合，則進行. */printf(nt從%s到%s的最短路徑是,G.vexsight1.sight,G.vexsight2.