您好,登錄后才能下訂單哦!
這篇文章主要介紹C語言如何實(shí)現(xiàn)旅游景點(diǎn)咨詢系統(tǒng),文中介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們一定要看完!
C語言課程設(shè)計(jì)之旅游景點(diǎn)咨詢系統(tǒng)
1.問題描述:創(chuàng)建一個(gè)至少有15個(gè)點(diǎn)的有向網(wǎng)表示的某個(gè)旅游景點(diǎn)的導(dǎo)游圖。頂點(diǎn)代表景點(diǎn),類型為字符串(例如,泰山導(dǎo)游圖:“天地廣場門”,“十八盤”,“馮玉祥墓”,“桃花峪門”,“中天門”,“南天門”,“玉皇頂”等),弧表示兩個(gè)景點(diǎn)之間可以直達(dá),弧上的權(quán)值表示兩個(gè)景點(diǎn)之間的路程(公里數(shù)),弧上還有到達(dá)方法的信息(有步行和索道兩種)。建立一個(gè)游客咨詢系統(tǒng)。
2.基本要求
(1)創(chuàng)建圖的存儲結(jié)構(gòu)。
(2)輸入兩個(gè)景點(diǎn)名,就可以得到從一個(gè)景點(diǎn)到達(dá)另一個(gè)景點(diǎn)的所有簡單路徑、相應(yīng)路徑的路程公里數(shù)、行走的方法(每一段是步行,還是坐索道);
(3)輸入兩個(gè)景點(diǎn)名,就可以得到其最短路徑,即:路程最短的行進(jìn)方法;如果兩者無路徑可通,就得出“兩景點(diǎn)不可達(dá)的信息”。
(4)按照題意要求獨(dú)立進(jìn)行設(shè)計(jì),設(shè)計(jì)結(jié)束后按要求寫出設(shè)計(jì)報(bào)告。
一、代碼塊:
#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<<"個(gè)景點(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ù)為路徑上的第幾個(gè)點(diǎn) { flag=1; int sum=0; cout<<G.vexs[solution[1]]; for(int i=2;i<=len;++i){//第一個(gè)點(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.查找:
以上是“C語言如何實(shí)現(xiàn)旅游景點(diǎn)咨詢系統(tǒng)”這篇文章的所有內(nèi)容,感謝各位的閱讀!希望分享的內(nèi)容對大家有幫助,更多相關(guān)知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。