C語言實(shí)現(xiàn)旅游景點(diǎn)咨詢系統(tǒng)
C語言課程設(shè)計之旅游景點(diǎn)咨詢系統(tǒng)
1.問題描述:創(chuàng)建一個至少有15個點(diǎn)的有向網(wǎng)表示的某個旅游景點(diǎn)的導(dǎo)游圖。頂點(diǎn)代表景點(diǎn),類型為字符串(例如,泰山導(dǎo)游圖:“天地廣場門”,“十八盤”,“馮玉祥墓”,“桃花峪門”,“中天門”,“南天門”,“玉皇頂”等),弧表示兩個景點(diǎn)之間可以直達(dá),弧上的權(quán)值表示兩個景點(diǎn)之間的路程(公里數(shù)),弧上還有到達(dá)方法的信息(有步行和索道兩種)。建立一個游客咨詢系統(tǒng)。
2.基本要求
(1)創(chuàng)建圖的存儲結(jié)構(gòu)。
(2)輸入兩個景點(diǎn)名,就可以得到從一個景點(diǎn)到達(dá)另一個景點(diǎn)的所有簡單路徑、相應(yīng)路徑的路程公里數(shù)、行走的方法(每一段是步行,還是坐索道);
(3)輸入兩個景點(diǎn)名,就可以得到其最短路徑,即:路程最短的行進(jìn)方法;如果兩者無路徑可通,就得出“兩景點(diǎn)不可達(dá)的信息”。
(4)按照題意要求獨(dú)立進(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];//頂點(diǎn)信息,string類型 EdgeType arc[MAXVEX][MAXVEX];//邊的信息 int numVertexes,numEdges;//頂點(diǎn)數(shù)和邊數(shù) }MGraph; void CreateMGraph(MGraph *G) { FILE *fp; fp=fopen("read.txt","r"); int i,j,k,w; cout<<"請輸入頂點(diǎn)數(shù)和邊數(shù)"<<endl; //cin>>G->numVertexes>>G->numEdges; fscanf(fp,"%d %d",&G->numVertexes,&G->numEdges); cout<<"請輸入"<<G->numVertexes<<"個景點(diǎn)名"<<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<<"條邊,包括起點(diǎn)下標(biāo)、終點(diǎn)下標(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<<"*******鄰接矩陣建立完成,各景點(diǎn)對應(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ù)為路徑上的第幾個點(diǎn) { flag=1; int sum=0; cout<<G.vexs[solution[1]]; for(int i=2;i<=len;++i){//第一個點(diǎn)已經(jīng)打印,打印剩下的點(diǎn) 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)前頂點(diǎn)加入路線 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);//從第一步起點(diǎn)開始 if(!flag) cout<<"無可行路徑!"<<endl; } int P[MAXVEX][MAXVEX];//用于存儲最短路徑下標(biāo)的數(shù)組 int D[MAXVEX][MAXVEX];//用于存儲到各點(diǎn)最短路徑的權(quán)值之和 void ShortestPath_Dijkstra(MGraph G,int v0)//最短路求解 { int v,w,k,Min; int Final[MAXVEX];//標(biāo)記,=1表示求得頂點(diǎn)V0至Vw的最短路徑 for(v=0;v<G.numVertexes;v++){//初始化數(shù)據(jù) Final[v]=0;//全部頂點(diǎn)初始化為未知最短路徑狀態(tài) D[v0][v]=G.arc[v0][v].wei;//將與V0有連線的頂點(diǎn)加上權(quán)值 P[v0][v]=v0;//初始化路徑數(shù)組pre頂點(diǎn)均為起始點(diǎn)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頂點(diǎn)離v0頂點(diǎn)更近 } } Final[k]=1;//將目前找到的最近的頂點(diǎn)位置置為1 for(w=0;w<G.numVertexes;++w){//修正當(dāng)前最短路徑及距離 //如果經(jīng)過v頂點(diǎn)的路徑比現(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);//終點(diǎn)先進(jìn)棧 while(P[s][e]!=s)//根據(jù)P數(shù)組倒著找 {//只要不到起點(diǎn) 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)的起點(diǎn)和終點(diǎn)下標(biāo)),輸入-1結(jié)束查找"<<endl; int s,e; while(cin>>s>>e&&(s+e)>=0) { if(s==e){ cout<<"您已在該景點(diǎn)"<<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.讀入景點(diǎn)信息文件:
2.查找:
更多學(xué)習(xí)資料請關(guān)注專題《管理系統(tǒng)開發(fā)》。
以上就是本文的全部內(nèi)容,希望對大家的學(xué)習(xí)有所幫助,也希望大家多多支持腳本之家。
相關(guān)文章
復(fù)數(shù)乘法中的結(jié)構(gòu)體賦值實(shí)現(xiàn)代碼
復(fù)數(shù)乘法中的結(jié)構(gòu)體賦值實(shí)現(xiàn)代碼。需要的朋友可以過來參考下,希望對大家有所幫助2013-10-10C++實(shí)現(xiàn)LeetCode(56.合并區(qū)間)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(56.合并區(qū)間),本篇文章通過簡要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07C++使用string的大數(shù)乘法運(yùn)算(3)
這篇文章主要為大家詳細(xì)介紹了C++使用string的大數(shù)乘法運(yùn)算,具有一定的參考價值,感興趣的小伙伴們可以參考一下2019-09-09C語言創(chuàng)建鏈表錯誤之通過指針參數(shù)申請動態(tài)內(nèi)存實(shí)例分析
這篇文章主要介紹了C語言創(chuàng)建鏈表錯誤之通過指針參數(shù)申請動態(tài)內(nèi)存,是鏈表創(chuàng)建過程中非常常見的經(jīng)典錯誤。實(shí)例中做了較為詳盡的分析,需要的朋友可以參考下2014-09-09C語言數(shù)據(jù)結(jié)構(gòu)之單向鏈表詳解
單向鏈表(單鏈表)是鏈表的一種,其特點(diǎn)是鏈表的鏈接方向是單向的,對鏈表的訪問要通過順序讀取從頭部開始。本文將為大家詳細(xì)講講單向鏈表的實(shí)現(xiàn)與使用,需要的可以參考一下2022-08-08