本文轉自王陸師哥，大家支持原作者，點此訪問原文

1 課題描述

設計一個校園導游程序，為來訪的客人提供各種信息查詢服務。查詢服務有：提供任意景點的信息，提供任意兩點之間的最短路徑，提供任意景點之間的所有路徑，提供多個景點之間的最佳訪問路徑。

2 問題分析和任務定義

任務要求：
1、 設計你的學校的校園平面圖，所含景點10-15個。以圖中頂點表示校園內各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信息。
2、 為來訪客人提供圖中任意景點相關信息的查詢。
3、 為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑。
4、 提供圖中任意景點問路查詢，即求任意兩個景點之間的所有路徑。
5、 提供校園圖中多個景點的最佳訪問路線查詢，即求途經這多個景點的最佳路徑。
6、 區分汽車線路與步行線路。
7、 設計一實用的查詢界面和功能菜單。

3 邏輯設計

根據高德地圖獲得山東工商學院的平面圖，根據平面圖抽象出各個景點以及其大體距離和位置關系。

4 詳細設計

struct vertex///景點信息結構體
{
int num;///景點編號
char name[20];///景點名稱
char info[300];///景點介紹
};
struct maps
{
int n;///點數
int m;///邊數
vertex v[M];
int edgs[M][M];///鄰接矩陣
} ; ///景點圖的結構體

<1>獲得景點信息函數：void Creat_vertex()
將各個景點對應的信息存入景點信息結構體數組中。

<2>生成圖和鄰接矩陣函數： void Creat_maps()
將獲得的景點信息構成鄰接矩陣來存圖。

<3>查詢景點信息函數：void Search_info()
通過選擇菜單，查詢任意一個景點的信息。

<4>多源最短路弗洛伊德算法：void Floyd()
通過弗洛伊德算法實現任意一點到n-1點最短路的建立。

<5>打印最短路徑函數：void Floyd_print(int s, int e)
回溯弗洛伊德算法打印從s點到e點的最短路徑經過的點，并統計所走的總路程。

<6>打印兩點之間所有路徑函數：void Dfs_allpath(int s,int e)
通過DFS深度優先搜索打印從s點到e點的所有路徑。

<7>提供多景點之間最佳路徑函數：void Bestpath_Multispot()
打印多個景點之間的最短路徑，并統計所要走的總路程。

5 程序編碼

#include<cstdio> #include<cstring> #include<algorithm> #include<stack> #define INF 999999 #define M 20 int dist[M][M];///距離 int path[M][M];///路徑 int Stack[M];///路徑棧 int top;///棧頂 int counts;///記錄路徑數 int visited[M];///標記數組 using namespace std; struct vertex///景點信息結構體 {int num;///景點編號char name[20];///景點名稱char info[300];///景點介紹 }; struct maps {int n;///點數int m;///邊數vertex v[M];int edgs[M][M];///鄰接矩陣 } g; ///景點圖的結構體 void Creat_vertex() {g.v[0].num=1;strcpy(g.v[0].name,"教職工家屬樓");strcpy(g.v[0].info,"這是學校老師職工的家屬樓");g.v[1].num=2;strcpy(g.v[1].name,"大學生活動中心");strcpy(g.v[1].info,"這是舉辦文藝活動的場所");g.v[2].num=3;strcpy(g.v[2].name,"餐飲區");strcpy(g.v[2].info,"這里集中著學校的三大餐廳，物美價廉");g.v[3].num=4;strcpy(g.v[3].name,"辦公實驗樓");strcpy(g.v[3].info,"8樓一下是學生實驗區，以上是領導老師的辦公區域");g.v[4].num=5;strcpy(g.v[4].name,"四教");strcpy(g.v[4].info,"這是學校的第四座教學樓");g.v[5].num=6;strcpy(g.v[5].name,"五教");strcpy(g.v[5].info,"這是學校的第五座教學樓");g.v[6].num=7;strcpy(g.v[6].name,"二教");strcpy(g.v[6].info,"這是學校的第二座教學樓，也是計算機科學與技術學院的系樓");g.v[7].num=8;strcpy(g.v[7].name,"圖書館");strcpy(g.v[7].info,"這是學校的圖書館，藏書豐富，是同學們閱讀自習的好去處");g.v[8].num=9;strcpy(g.v[8].name,"三教");strcpy(g.v[8].info,"這是學校的第三座教學樓");g.v[9].num=10;strcpy(g.v[9].name,"體育館");strcpy(g.v[9].info,"這是學生進行室內比賽和體育活動的場所");g.v[10].num=11;strcpy(g.v[10].name,"男生宿舍");strcpy(g.v[10].info,"這是東校男生休息生活區域，有兩座巨大的樓");g.v[11].num=12;strcpy(g.v[11].name,"東操場");strcpy(g.v[11].info,"這是東校的田徑操場，同學們都在這里鍛煉身體");g.v[12].num=13;strcpy(g.v[12].name,"落雪湖");strcpy(g.v[12].info,"這是學校的一座人工湖"); } void Creat_maps() {int i,j;g.n=13;///13個景點g.m=18;///18條雙向路徑for(i=0; i<g.n; i++) ///初始化鄰接矩陣{for(j=0; j<g.n; j++){g.edgs[i][j]=INF;}}g.edgs[0][1]=g.edgs[1][0]=500;///寫入邊的信息g.edgs[0][2]=g.edgs[2][0]=1000;g.edgs[0][7]=g.edgs[7][0]=500;g.edgs[1][3]=g.edgs[3][1]=200;g.edgs[1][4]=g.edgs[4][1]=200;g.edgs[2][7]=g.edgs[7][2]=400;g.edgs[2][10]=g.edgs[10][2]=300;g.edgs[3][4]=g.edgs[4][3]=300;g.edgs[4][5]=g.edgs[5][4]=300;g.edgs[4][6]=g.edgs[6][4]=100;g.edgs[5][6]=g.edgs[6][5]=300;g.edgs[5][8]=g.edgs[8][5]=200;g.edgs[6][8]=g.edgs[8][6]=200;g.edgs[6][12]=g.edgs[12][6]=100;g.edgs[6][7]=g.edgs[7][6]=200;g.edgs[8][9]=g.edgs[9][8]=500;g.edgs[9][11]=g.edgs[11][9]=450;g.edgs[10][11]=g.edgs[11][10]=300; } void Search_info() {int i,n;printf("山東工商學院東校區的景點有：\n");for(i=0; i<13; i++){printf("%d:%s\n",g.v[i].num,g.v[i].name);}while(1){printf("請輸入你想要查詢的景點編號：\n");printf("按0退出\n\n");scanf("%d",&n);getchar();if(n==0){break;}else if(n<0||n>13){printf("輸入有誤，請重新輸入！！！\n\n");continue;}else{printf("%d:%s\n",g.v[n-1].num,g.v[n-1].name);printf("%s\n\n",g.v[n-1].info);}}return ; } void Floyd() ///弗洛伊德 {int i,j,k;for(i=0; i<g.n; i++) ///初始化距離與路徑矩陣{for(j=0; j<g.n; j++){dist[i][j]=g.edgs[i][j];if(i!=j&&dist[i][j]<INF){path[i][j]=i;}else{path[i][j]=-1;///-1代表不可達}}}//printf("%d\n",g.n);for(k=0; k<g.n; k++){for(i=0; i<g.n; i++){for(j=0; j<g.n; j++){if(dist[i][j]>(dist[i][k]+dist[k][j])){dist[i][j]=dist[i][k]+dist[k][j];///更新path[i][j]=k; ///path用于記錄最短路徑上的結點*/}}}}return ; } void Floyd_print(int s, int e) {if(path[s][e]==-1||path[s][e]==e||path[s][e]==s)///遞歸終止條件{return;}else{Floyd_print(s,path[s][e]);///將中間點作為終點繼續打印路徑printf("%s->",g.v[path[s][e]].name);///打印中間景點名字Floyd_print(path[s][e],e);///將中間點作為起點繼續打印路徑} }void Dfs_allpath(int s,int e) {int dis=0;int i,j;Stack[top]=s;top++; ///起點入棧visited[s]=1;///標記入棧for(i=0; i<g.n; i++){if(g.edgs[s][i]>0&&g.edgs[s][i]!=INF&&!visited[i]){///表明兩點可達且未被訪問if(i==e)///DFS到了終點，打印路徑{printf("第%d條路:",counts++);for(j=0; j<top; j++){printf("%s->",g.v[Stack[j]].name);if(j<top-1)///統計路徑長度{dis=dis+g.edgs[Stack[j]][Stack[j+1]];}}dis=dis+g.edgs[Stack[top-1]][e];printf("%s\n",g.v[e].name);///打印終點printf("總長度是：%dm\n\n",dis);}else///不是終點接著DFS{Dfs_allpath(i,e);top--;///支路全被訪問一遍,頂點出棧visited[i]=0;///出棧點標記為已出棧，允許下次訪問}}} } void Bestpath_Multispot() {int vNum[M]= {0};int i,j,dis;j=1;dis=0;///統計全程總長printf("請輸入你要游覽的第%d個景點的編號（輸入-1結束輸入）：",j);scanf("%d",&vNum[j-1]);while(vNum[j-1]!=-1&&j<13){printf("請輸入你要游覽的第%d個景點編號：",++j);scanf("%d", &vNum[j-1]);if(vNum[j-1]==-1){break;}}printf("\n這是最佳訪問路徑：");for(i=0; vNum[i]>0&&vNum[i+1]>0; i++){printf("%s->",g.v[vNum[i]-1].name);///輸出路徑上的起點Floyd_print(vNum[i]-1,vNum[i+1]-1);///利用佛洛依德算法dis+=dist[vNum[i]-1][vNum[i+1]-1];}printf("%s\n\n",g.v[vNum[j-2]-1].name);///*輸出路徑上的終點*/printf("全程總長為：%dm\n\n",dis); }void Dis_menu() {printf("\n");printf(" ************歡迎使用山東工商學院導游咨詢系統***********\n\n");printf(" ***** 1.山商景點信息查詢 ******************\n");printf(" ***** 2.兩景點之間最短路查詢 ******************\n");printf(" ***** 3.兩景點間所有路徑查詢 ******************\n");printf(" ***** 4.多景點間訪問路線查詢 ******************\n");printf(" ***** 5.退出系統 ******************\n");printf(" *******************************************************\n");return ; } void Dis_map() {printf("\n *山商東校區校園景點地圖一覽*\n\n");printf(" ⑽體育館 \n");printf(" ⑹五教 ⑼三教 ◎------| \n");printf(" ◎ ◎---------------| | \n");printf(" |------------| | | \n");printf(" | |------◎ \n");printf(" ⑸四教 ⑺二教 | (13)落雪湖| ⑿東操場 \n");printf(" ◎ ◎ ◎ | | \n");printf(" ⑷辦公實驗樓◎-------|------------------—-|------|---------| | \n");printf(" | | | ◎-------| \n");printf(" | | | ⑾ 男生宿舍 \n");printf(" | | ◎ | \n");printf(" ◎⑵大學生活動中心 ⑻圖書館 | \n");printf(" |--------------------------------| | \n");printf(" | |---------------⑶餐廳 \n");printf(" | \n");printf(" ◎⑴ 職工家屬樓 \n\n"); } int main() {int i,n;int start,ends;Creat_vertex();Creat_maps();Dis_map();while(1){Dis_menu();printf("請輸入需要操作的命令：\n");scanf("%d",&n);getchar();if(n<1||n>5){printf("輸入有誤，請重新輸入！！！\n");continue;}else{if(n==1){Search_info();}else if(n==2){Dis_map();printf("請輸入起點的景點：\n");scanf("%d",&start);printf("請輸入終點的景點：\n");scanf("%d",&ends);Floyd();///弗洛伊德printf("從%s到%s最短距離是：%d\n",g.v[start-1].name,g.v[ends-1].name,dist[start-1][ends-1]);printf("%s->",g.v[start-1].name);Floyd_print(start-1, ends-1);printf("%s\n",g.v[ends-1].name);}else if(n==3){Dis_map();counts=1;///起始路徑數為1printf("請輸入起點的景點：\n");scanf("%d",&start);printf("請輸入終點的景點：\n");scanf("%d",&ends);Dfs_allpath(start-1,ends-1);}else if(n==4){Dis_map();Floyd();///弗洛伊德Bestpath_Multispot();}else if(n==5){return 0;}}}return 0; }

6 程序調試與測試

1）主菜單：

2）景點信息查詢

3）兩景點之間最短路徑查詢

4）兩景點之間所有路徑查詢

5）多景點間訪問路線查詢

總結

以上是生活随笔為你收集整理的数据结构实训——校园导游系统的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。