[基本要求]

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

[測試數據]

10
1 校門口 出入校園都需要經過校門口
2 教學樓 學生學習的地方,書聲瑯瑯,學習氛圍濃重
3 女生宿舍 女生休息的地方
4 男生宿舍 男生休息的地方
5 食堂 學生和老師吃飯的地方
6 鵝卵石路 校園的偏僻小徑
7 亭子 冷清,一般沒有人來往
8 湖邊 湖面很大,不要靠近湖邊玩水或扔垃圾
9 停車場 校園里車輛停放的地方
10 操場 供師生們運動的地方
12
1 2 5
1 10 7
1 6 4
2 9 6
2 8 5
3 10 3
3 5 2
4 5 3
4 8 8
5 10 3
5 8 7
6 7 4
6
1 2 5
2 3 10
2 4 9
2 9 6
3 4 4
4 9 10
24
1 6 東
1 10 東南
1 2 西南
2 1 東北
2 8 南
2 9 西南
3 10 西北
3 5 西
4 5 北
4 8 西北
5 10 北
5 3 東
5 4 南
5 8 西
6 1 西
6 7 東
7 6 西
8 2 北
8 5 東
8 4 東南
9 2 東北
10 1 西北
10 3 東南
10 5 南
12
1 2 西南
2 1 東北
2 3 東偏南
2 4 南偏東
2 9 西南
3 2 西北
3 4 西南
4 9 西偏北
4 2 北偏西
4 3 東北
9 2 東北
9 4 東南

[選做內容]

1、擴充道路信息，如道路類別（車道、人行道等）、沿途景色等，以至可按客人所需分別查詢人行路徑和車行路徑或觀察路徑。
2、擴充每個景點的鄰接景點的方向等信息，使得路徑查詢結果能提供詳盡的導向信息。
3、實現校園導游圖的仿真界面。

[代碼實現]

//0!='0' #include<queue> #include<stdio.h> #include<string.h> #include<stdlib.h> #include<algorithm> #include<stack> using namespace std; #define scnaf scanf #define ll long long const int N=1e2+50; const int INF=0x3f3f3f3f; int head[2][N],cnt[2],n=10,m[2],f[2];//鏈式前向星: 第一個以i為頂點的邊 邊的個數 路徑數 景點的個數 方位數 | 0人1車 int dfsv[N]={0},p[N],top=0,way;//dijkstra: 標記是否入"棧"過 存路徑|"類棧" 棧中元素數 int floydp[N],floydw[N][N],pathw[N],pcnt; //floyd: 多源最短路所需途徑景點代號 floydw[i][j]從景點i到j需要途徑的代號 記錄多源最短路徑 記錄查找到的路徑上景點數 void printff(); struct S {char name[20],intr[50],fang[2][15][10];//名字 簡介 方向 }sce[N];//景點信息 struct ss {int next,to,w;//下一個以i為頂點的邊的位置 該邊的尾 該邊的權值 }e[2][N]; void add(int x,int y,int w,int flag)//添加無向邊 {e[flag][++cnt[flag]].to=y;e[flag][cnt[flag]].w=w;e[flag][cnt[flag]].next=head[flag][x];head[flag][x]=cnt[flag]; } void scene(int k)//查詢k景點信息 {printf(" 查詢景點代號為%d\n 名稱:%s\n 簡介:%s\n",k,sce[k].name,sce[k].intr); } void dij(int x,int y,int flag)//單源點最短路->dijkstra {int d[N],v[N],path[N],i,j,k,t[N];//v[i]景點i被訪問過，d[i]景點x到景點i的最短距離，path[i]=j表明從x到i最后一段是i->jmemset(d,INF,sizeof(d));memset(path,INF,sizeof(path));memset(v,0,sizeof(v));d[x]=0;while(1){k=-1,j=INF;for(i=1;i<=n;i++)if(d[i]<j&&!v[i])//被訪問到但沒有被選擇過{k=i;j=d[i];}if(k==-1)//沒有連通點或者全部選擇結束break;v[k]=1;//要在進循環前標記，否則會反復訪問k點for(i=head[flag][k];i;i=e[flag][i].next){if(!v[e[flag][i].to]&&((d[k]+e[flag][i].w)<d[e[flag][i].to])){d[e[flag][i].to]=d[k]+e[flag][i].w;path[e[flag][i].to]=k;}}}k=0,j=y;while(path[j]!=INF){t[++k]=path[j];j=path[j];}if(!k){printf("\n 您查詢的兩點之間不通,請重新輸入\n");return ;}printf("\n 兩景點最短路線為: ");for(i=k,t[0]=y;i>0;i--){printf(" %d",t[i]);printf(" %s ->",sce[t[i]].fang[flag][t[i-1]]);}printf(" %d",y);printf("\n 兩景點距離為: %d(單位/百米)\n",d[y]); } void priath(int p[],int top,int way,int flag)//打印路徑 {printf(" 路徑%d:",++way);int i;for(i=1;i<top;i++){printf(" %d ",p[i]);printf("%s ->",sce[p[i]].fang[flag][p[i+1]]);}printf(" %d\n",p[top]); } void dfsway(int x,int y,int flag,int top)//深搜所有路徑 {dfsv[x]=1;p[++top]=x;if(p[top]==y)priath(p,top,way,flag);for(int i=head[flag][x];i;i=e[flag][i].next)if(!dfsv[e[flag][i].to])dfsway(e[flag][i].to,y,flag,top);dfsv[x]=0;//遞歸. 當退到棧內點時,已經循環過,所以所有點可以共用一個標記數組top--; } void evway(int x,int y,int flag)//初始化"棧" {way=top=0;memset(dfsv,0,sizeof(dfsv));dfsway(x,y,flag,top);if(!way)printf("\n 您查詢的兩點之間不通,請重新輸入\n"); } void pathway(int l,int r)//遞歸回推路徑 {if(l==r)return ;if(floydw[l][r]==-1)pathw[++pcnt]=r;else{pathway(l,floydw[l][r]);pathway(floydw[l][r],r);} } void floyd(int flag)//處理多源最短距離 {int i,j,k,p,dp[N][N];// dp[i][j]從景點i到景點j的距離memset(dp,INF,sizeof(dp));memset(floydw,-1,sizeof(floydw));for(i=1;i<=n;i++)dp[i][i]=0;for(i=1;i<=n;i++){for(j=head[flag][i];j;j=e[flag][j].next)dp[i][e[flag][j].to]=e[flag][j].w;}for(k=1;k<=n;k++)//景點for(i=1;i<=n;i++)//遍歷數組松弛每對景點for(j=1;j<=n;j++)if((dp[i][k]+dp[k][j])<dp[i][j]){dp[i][j]=dp[i][k]+dp[k][j];floydw[i][j]=k;}for(i=2,k=1,pcnt=0;floydp[i];i++)//i是終點 k是起點 pcnt是{for(j=1,p=0;j<=pcnt;j++)if(floydp[i]==pathw[j])p=1;if(dp[floydp[k]][floydp[i]]==INF){printf(" 您查詢的地點不互通,請重新輸入\n");return ;}if(!p){pathway(floydp[k],floydp[i]);k=i;}}pathw[0]=floydp[1];//出發點for(i=0;i<pcnt;i++){printf("%d",pathw[i]);printf(" %s -> ",sce[pathw[i]].fang[flag][pathw[i+1]]);}printf("%d",pathw[i]); } int main() {int i,j,k,x,y,w,p,flag=0;printf("請輸入景點個數\n");scnaf("%d",&n);printf("\n請輸入景點信息(代號 名稱 簡介):\n");for(i=1;i<=n;i++)scnaf("%d%s%s",&j,&sce[j].name,&sce[j].intr);printf("\n請輸入景點步行路線數:\n");scanf("%d",&m[0]);printf("\n請依次輸入景點步行路線:\n");for(i=1;i<=m[0];i++){scnaf("%d%d%d",&x,&y,&w);add(x,y,w,0);add(y,x,w,0);}printf("\n請輸入景點汽車路線數:\n");scanf("%d",&m[1]);printf("\n請依次輸入景點汽車路線:\n");for(i=1;i<=m[1];i++){scnaf("%d%d%d",&x,&y,&w);add(x,y,w,1);add(y,x,w,1);}printf("\n請輸入步行方位數:\n");scanf("%d",&f[0]);printf("\n請依次輸入景點間步行的方位:\n");for(i=1;i<=f[0];i++){scnaf("%d%d",&x,&y);scanf("%s",&sce[x].fang[0][y]);}printf("\n請輸入汽車方位數:\n");scanf("%d",&f[1]);printf("\n請依次輸入景點間步行的方位:\n");for(i=1;i<=f[1];i++){scnaf("%d%d",&x,&y);scnaf("%s",&sce[x].fang[1][y]);}while(1){printf("請輸入:\n 0.退出\n 1.查詢任意景點信息\n 2.查詢任意兩個景點最短路線\n");printf(" 3.查詢任意兩個景點所有路線\n 4.查詢多個景點最佳路線\n 5.導游仿真圖\n");scanf("%d",&p);if(!p)break;switch(p){case 1:{printf("\n請輸入查詢景點的代號:\n");scanf("%d",&k);scene(k);break;}case 2:{printf("\n請輸入查詢路線類型:\n 0.步行\n 1.汽車\n");scanf("%d",&flag);printf("\n請輸入兩景點的代號(將默認第一個數字為起點):\n");scnaf("%d%d",&x,&y);dij(x,y,flag);break;}case 3:{printf("\n請輸入查詢路線類型:\n 0.步行\n 1.汽車\n");scnaf("%d",&flag);printf("\n請輸入兩景點代號(將默認第一個數字為起點):\n");scnaf("%d%d",&x,&y);evway(x,y,flag);break;}case 4:{printf("\n請輸入查詢路線類型:\n 0.步行\n 1.汽車\n");scnaf("%d",&flag);printf("\n請依次輸入景點代號(將默認第一個數字為起點),輸入數字0結束\n");for(i=1;;i++){scanf("%d",&floydp[i]);if(!floydp[i])break;}floyd(flag);break;}case 5:printff();break;}}return 0; } void printff() {printf("\n步行導游仿真圖:\n");printf(" 1校門口***6鵝卵石路***7亭子\n");printf(" * * \n");printf(" * * \n");printf(" * * \n");printf(" 2教學樓 10操場 \n");printf(" * * * \n");printf(" * * * \n");printf(" * * * \n");printf("9停車場 8湖邊*******5食堂***3女生宿舍\n");printf(" * * \n");printf(" ***** * \n");printf(" **4男生宿舍 \n");printf("\n\n汽車導游仿真圖:\n");printf(" 1校門口\n");printf(" * \n");printf(" * \n");printf(" * \n");printf(" 2教學樓 \n");printf(" * ***** \n");printf(" * ***** \n");printf(" * ***** \n");printf("9停車場 *****3女生宿舍\n");printf(" **** ** \n");printf(" **** ** \n");printf(" ****4男生宿舍 \n"); }

總結

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

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