快捷導(dǎo)航

C語言實現(xiàn)旅游景點咨詢系統(tǒng)

更新時間：2019年12月27日 14:16:46 作者：夏.謹(jǐn)之

這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)旅游景點咨詢系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下

C語言課程設(shè)計之旅游景點咨詢系統(tǒng)

1．問題描述：創(chuàng)建一個至少有15個點的有向網(wǎng)表示的某個旅游景點的導(dǎo)游圖。頂點代表景點,類型為字符串（例如，泰山導(dǎo)游圖：“天地廣場門”，“十八盤”，“馮玉祥墓”，“桃花峪門”，“中天門”，“南天門”，“玉皇頂”等），弧表示兩個景點之間可以直達(dá)，弧上的權(quán)值表示兩個景點之間的路程（公里數(shù)），弧上還有到達(dá)方法的信息（有步行和索道兩種）。建立一個游客咨詢系統(tǒng)。

2．基本要求

（1）創(chuàng)建圖的存儲結(jié)構(gòu)。
（2）輸入兩個景點名，就可以得到從一個景點到達(dá)另一個景點的所有簡單路徑、相應(yīng)路徑的路程公里數(shù)、行走的方法（每一段是步行，還是坐索道）；
（3）輸入兩個景點名，就可以得到其最短路徑，即：路程最短的行進(jìn)方法；如果兩者無路徑可通，就得出“兩景點不可達(dá)的信息”。
（4）按照題意要求獨立進(jìn)行設(shè)計，設(shè)計結(jié)束后按要求寫出設(shè)計報告。

一、代碼塊：

#include<bits/stdc++.h>
/*#include<iostream>
#include<fstream>
#include<algorithm>
#include<stack>*/
using namespace std;
const int MAXVEX=50;
const int INF=0x3fffffff;
//s表示索道 w表示步行

typedef struct{//邊的結(jié)構(gòu)
 int wei;//權(quán)值
 char way;//到達(dá)方式
}EdgeType;

typedef struct{
 string vexs[MAXVEX];//頂點信息,string類型
 EdgeType arc[MAXVEX][MAXVEX];//邊的信息
 int numVertexes,numEdges;//頂點數(shù)和邊數(shù)
}MGraph;

void CreateMGraph(MGraph *G)
{
 FILE *fp;
 fp=fopen("read.txt","r");
 int i,j,k,w;
 cout<<"請輸入頂點數(shù)和邊數(shù)"<<endl;
 //cin>>G->numVertexes>>G->numEdges;
 fscanf(fp,"%d %d",&G->numVertexes,&G->numEdges);
 cout<<"請輸入"<<G->numVertexes<<"個景點名"<<endl;
 char temp[MAXVEX];
 for(i=0;i<G->numVertexes;++i){
 fscanf(fp,"%s",temp);//cin>>G->vexs[i];
 G->vexs[i]=temp;
 }
 //初始化鄰接矩陣
 for(i=0;i<G->numVertexes;++i)
 for(j=0;j<G->numVertexes;++j)
  G->arc[i][j].wei=INF;
 cout<<"請輸入"<<G->numEdges<<"條邊，包括起點下標(biāo)、終點下標(biāo)、路程（KM）和到達(dá)方式(s表示索道 w表示步行)"<<endl;
 for(k=0;k<G->numEdges;++k){
 char ch;
 fscanf(fp,"%d %d %d %c",&i,&j,&w,&ch);//cin>>i>>j>>w>>ch;
 G->arc[i][j].wei=w;
 G->arc[i][j].way=ch;
 }
 cout<<endl<<"*******鄰接矩陣建立完成，各景點對應(yīng)的編號如下*******"<<endl<<endl;
 for(i=0;i<G->numVertexes;++i){
 cout<<"編號"<<i<<" "<<G->vexs[i]<<endl;
 }
}

int solution[MAXVEX];//記錄路線
bool vis[MAXVEX];//標(biāo)記數(shù)組
int flag;//通路標(biāo)記

void print(MGraph G,int len)//參數(shù)為路徑上的第幾個點
{
 flag=1;
 int sum=0;
 cout<<G.vexs[solution[1]];
 for(int i=2;i<=len;++i){//第一個點已經(jīng)打印,打印剩下的點
 if(G.arc[solution[i-1]][solution[i]].way=='s') cout<<" -> "<<"(索道)"<<G.vexs[solution[i]];
 else cout<<" -> "<<"(步行)"<<G.vexs[solution[i]];
 sum+=G.arc[solution[i-1]][solution[i]].wei;
 }
 cout<<endl<<"該路徑總路程為"<<sum<<"KM"<<endl;
 cout<<endl;
}

void dfs(MGraph G,int k,int loc,int e)//k為第幾步，loc為當(dāng)前的位置,e為目標(biāo)
{
 solution[k]=loc;//當(dāng)前頂點加入路線
 vis[loc]=1;//標(biāo)記置為1
 if(loc==e) print(G,k);
 else
 for(int i=0;i<G.numVertexes;++i){
 if(vis[i]==0&&G.arc[loc][i].wei<INF) dfs(G,k+1,i,e);
 }
 vis[loc]=0;//取消標(biāo)記
}

void slove_allpath(MGraph G,int s,int e)//查找所有可行路徑
{
 flag=0;//有無路徑標(biāo)記
 memset(vis,0,sizeof(vis));
 dfs(G,1,s,e);//從第一步起點開始
 if(!flag) cout<<"無可行路徑!"<<endl;
}

int P[MAXVEX][MAXVEX];//用于存儲最短路徑下標(biāo)的數(shù)組
int D[MAXVEX][MAXVEX];//用于存儲到各點最短路徑的權(quán)值之和

void ShortestPath_Dijkstra(MGraph G,int v0)//最短路求解
{
 int v,w,k,Min;
 int Final[MAXVEX];//標(biāo)記，=1表示求得頂點V0至Vw的最短路徑
 for(v=0;v<G.numVertexes;v++){//初始化數(shù)據(jù)
 Final[v]=0;//全部頂點初始化為未知最短路徑狀態(tài)
 D[v0][v]=G.arc[v0][v].wei;//將與V0有連線的頂點加上權(quán)值
 P[v0][v]=v0;//初始化路徑數(shù)組pre頂點均為起始點V0
 }
 D[v0][v0]=0;//v0至v0路徑為0
 Final[v0]=1;//v0至v0不需要求路徑
 for(v=1;v<G.numVertexes;v++){
 Min=INF;//初始化最小值為INF
 for(w=0;w<G.numVertexes;w++){
  if(!Final[w]&&D[v0][w]<Min){
  k=w;
  Min=D[v0][w];//w頂點離v0頂點更近
  }
 }
 Final[k]=1;//將目前找到的最近的頂點位置置為1
 for(w=0;w<G.numVertexes;++w){//修正當(dāng)前最短路徑及距離
  //如果經(jīng)過v頂點的路徑比現(xiàn)在這條路徑的長度短的話
  if(!Final[w]&&(Min+G.arc[k][w].wei<D[v0][w])){
  D[v0][w]=Min+G.arc[k][w].wei;//修改當(dāng)前路徑長度
  P[v0][w]=k;
  }
 }
 }
}

stack<int> xiang;//輔助棧

void slove_ShortestPath(MGraph G,int s,int e)//查找最短路徑
{
 int tempe=e;
 if(D[s][e]==INF) cout<<"無可行路徑!"<<endl;
 else{//有最短路徑
 int temp=D[s][e];
 xiang.push(e);//終點先進(jìn)棧
 while(P[s][e]!=s)//根據(jù)P數(shù)組倒著找
 {//只要不到起點
  xiang.push(P[s][e]);
  e=P[s][e];
 }
 //cout<<"由"<<G.vexs[s]<<"到"<<G.vexs[tempe]<<"的最短路徑為："<<endl;
 cout<<G.vexs[s];
 int pre=s;
 while(!xiang.empty())
 {
  int top=xiang.top();
  if(G.arc[pre][top].way=='s') cout<<" -> "<<"(索道)"<<G.vexs[top];
  else cout<<" -> "<<"(步行)"<<G.vexs[top];
  pre=top;
  xiang.pop();
 }
 cout<<endl<<"該路徑總路程為"<<temp<<"KM"<<endl;
 }
 cout<<endl;
}

int main()
{
 MGraph G;
 CreateMGraph(&G);
 for(int i=0;i<G.numVertexes;++i) ShortestPath_Dijkstra(G,i);
 /*
 for(int i=0;i<G.numVertexes;++i){
 for(int j=0;j<G.numVertexes;++j)
  cout<<P[i][j]<<' ';
 cout<<endl;
 }
 cout<<endl;
 for(int i=0;i<G.numVertexes;++i){
 for(int j=0;j<G.numVertexes;++j)
  cout<<D[i][j]<<' ';
 cout<<endl;
 }
 */
 cout<<"請輸入需要查找的路徑（對應(yīng)的起點和終點下標(biāo)），輸入-1結(jié)束查找"<<endl;
 int s,e;
 while(cin>>s>>e&&(s+e)>=0)
 {
 if(s==e){
  cout<<"您已在該景點"<<endl;
  continue;
 }
 cout<<"*******由"<<G.vexs[s]<<"到"<<G.vexs[e]<<"可行的路徑有：*******"<<endl;
 slove_allpath(G,s,e);//查找所有可行路徑
 cout<<"*******由"<<G.vexs[s]<<"到"<<G.vexs[e]<<"的最短路徑為：*******"<<endl;
 slove_ShortestPath(G,s,e);//查找最短路徑
 }
 cout<<"********************查 找 結(jié) 束********************"<<endl;
 return 0;
}

二、運(yùn)行：

1.讀入景點信息文件：