題目:校園導航問題
班級:信計0901 姓名:劉佺學號:3090104020 完成日期:2011.6
1. 執行環境:
microsoft visual c++ 6.0
2. 程式所實現的功能:
設計乙個校園導遊程式,為來訪的客人提供各種資訊查詢服務。為來訪客人提供圖中任意景點相關資訊的查詢。為來訪客人提供圖中任意景點相關資訊的查詢。
3. 程式的輸入和包含輸入的資料格式和說明:
使用者只需要按照頁面的提示輸入需要操作的序號,然後按回車確認即可。
4. 程式的輸出格式和說明:
當使用者輸入所要查詢的地點序號,並且回車後,螢幕自動生成所查詢路徑的最短路線和距離。
5. 測試資料:
當使用者進入最短距離查詢介面後,輸入起始地點序號1(江蘇大學校大門)和終點序號後5(藥學院),螢幕上自動生成這兩條路徑之間的最短距離519公尺,和最短路徑江蘇大學校大門→圖書館→藥學院。當使用者輸入起始地點序號7(三江樓)和終點序號後13(女生一區),螢幕上自動生成這兩條路徑之間的最短距離1305公尺,和最短路徑為三江樓→三山樓→東山操場→女生一區。
(1).主要的資料結構設計說明:
結構體的定義:
typedef struct vertextypevertextype;
typedef structmgraph;
常量的定義:
#define max 32767
#define num 1
各個函式的定義:
void createmgraph(int v) //建立圖的函式,其中v表示圖中的頂點數
void map() //地圖展示函式,用於輸出西安科技大學的平面簡略圖
char menu() //主選單顯示於操作介面
void info() //資料介紹函式,用於當使用者選擇查詢地點資料時輸出地點的資料資訊
void dijkstra(int num) //迪傑斯特拉函式
void display(int sight1,int sight2) //地圖展示函式
void main() //主函式的定義
(2).程式的主要流程圖
求最短路徑演算法流程圖:
(3.)主函式對各個函式的呼叫工作
(4).主要函式的說明:
#define max 32767 //用max來表示權值為此時的兩點間直接不可達
#define num 15 //選取了學校的十七個地點用陣列儲存,其中陣列第乙個元素不儲存地點以方便操作
typedef struct vertextypevertextype; //定義頂點的結構體型別,number表示頂點編號,字元陣列表示頂點的名稱
typedef structmgraph; //定義圖的結構體型別,vex[num]陣列儲存頂點,arcsp[num][num]矩陣儲存邊的權值,vexnum表示頂點的個數
mgraph g;
int p[num][num]; //定義全域性變數p[num][num]儲存點之間的最短路徑
long int d[num]; //定義全域性變數d[num]儲存點之間最短路徑的權值
void dijkstra(int num) //通過迪傑斯特拉演算法求num點到其餘點的最短路徑,並將最短路徑儲存在陣列p[num][num]中,將最短路徑的權值儲存在陣列d[num]中
}d[num]=0;
final[num]=1; //初始化num頂點屬於s集
for(i=1;i
}char menu() //主選單顯示於操作介面從而讓使用者選擇查詢路徑功能或者查詢地點資訊功能
char c;
int flag; //定義標誌flag確定迴圈條件
dowhile(flag);
return c;
}void display(int sight1,int sight2) //輸出函式用於通過陣列p[num][num]提取出從點sight1到點sight2的最短路徑,從d[num]中輸出點sight1到點sight2的最短路徑的權值
}}void main() //主函式
break;
goto gate;
case'2':
system("cls");
info();
printf("\n\n\t\t\t\t請按回車鍵退回首頁...\n");
getchar();
getchar();
break;
}while(ck!='e當識別符號ck不等於e時繼續迴圈
}1.測試結果:(如圖所示)
開啟程式所顯示的介面。我們選擇服務一,查詢地點之間最短路徑。選擇1,回車
如若我們選擇出發點點是藝術學院,終點是東山操場,則輸入3回車,在輸入11回車
然後螢幕上顯示出最短路徑
我們選擇選擇江蘇大學景點介紹服務,則輸入2回車
最後螢幕上顯示是景點的簡介,如圖
2.時間複雜度分析
(1) void createmgraph(int v)
其中為頂點賦值用了一次for迴圈,為鄰接矩陣賦值用了兩次for迴圈且相互巢狀,故時間複雜度為o(+)
資料結構迷宮問題
base.h 公用的常量和型別 include include include include 函式結果狀態 define true 1 define false 0 define ok 1 define error 0 define infeasible 1 define overflow 2 t...
校園導遊系統資料結構實習報告
least 兩個景點之間的全部路徑 void dfs path adjm g,int m,int n,int k else s試探從下乙個頂點 s 開始是否有到終點的路徑 void all path adjm g 任意兩個地點之間最短路徑演算法 shortestpath floyd adjm g弗洛...
資料結構實驗報告 校園導遊諮詢
軟體學院 學生實驗報告冊 實驗課程名稱 資料結構與演算法 實驗專案名稱 校園導遊諮詢 實驗型別 打 基礎 綜合 設計 院系 資訊工程學院計算機系專業 姓名學號 指導老師 軟體學院教務處編制 一 實驗預習報告內容 預習日期 2010年 6 月 19日 二 實驗原始 資料 記錄 實驗時間 2007 年 ...