C++實現(xiàn)景區(qū)旅游信息管理系統(tǒng)
本文實例為大家分享了C++實現(xiàn)景區(qū)旅游信息管理系統(tǒng)的具體代碼，供大家參考，具體內(nèi)容如下
1 問題描述
如今生活水平提高，大家都喜歡在假期中到一個旅游景點參觀，在旅游景區(qū)中經(jīng)常聽到游客打聽從一個景點到另一個景點的最短路徑和最短距離，這類不喜歡按照導(dǎo)游圖來游覽的游客常常需要一個景區(qū)管理系統(tǒng)來挑選自己喜歡的旅游景點，再規(guī)劃一個最短路徑和最短距離來游覽，一邊節(jié)省時間跟提高旅游效率。
2 數(shù)據(jù)結(jié)構(gòu)的設(shè)計
建立一個景區(qū)旅游信息管理系統(tǒng)，實現(xiàn)如下功能：
1、創(chuàng)建景區(qū)景點分布圖
通過一個鄰接矩陣（實質(zhì)是一個二維數(shù)組,m[i][j]表示從i到j(luò)的權(quán)值大小，為零表示沒有直達(dá)的路徑）記錄景區(qū)景點的分布圖.
2、輸出景區(qū)景點分布圖（鄰接矩陣）
通過掃描鄰接矩陣輸出景區(qū)景點分布圖
3、輸出導(dǎo)游線路圖：深度優(yōu)先策略
首先通過遍歷景點，通過用戶給出的一個入口景點c，建立一個導(dǎo)游線路圖，導(dǎo)游線路圖用有向圖表示。遍歷采用深度優(yōu)先策略（遞歸），這個也是正常的游客的心理
4、判斷導(dǎo)游線路圖有無回路：拓?fù)渑判颍ú檎胰攵却笥?的景點）
為了使導(dǎo)游線路圖能夠優(yōu)化，可以通過拓?fù)渑判蚺袛鄨D中有無回路，若有回路則打印輸出回路中的景點，供人工優(yōu)化
5、求兩個景點間的最短路徑和最短距離：floyd算法
在導(dǎo)游線路圖中，還為一些不愿按線路走的游客提供信息服務(wù)，比如從一個景點到另一個景點的最短路徑和最短距離。在本線路圖中將輸出任意景點間的最短路徑和最短距離
6、輸出道路修建規(guī)劃圖：prime算法
在景區(qū)建設(shè)中，道路建設(shè)是其中一個重要的內(nèi)容。道路建設(shè)首先要保證能連通所有景點，但又要花最小的代價，可以通過求最小生成樹來解決這個問題，通過prime算法來求最小生成樹
通過修改后添加的功能：
7、將景區(qū)景點分布圖安裝指定的文件名（可以景區(qū)名字命名）保存到默認(rèn)的目錄file下
在這里我遇到了路徑格式問題，通過查詢資料得以解決這個問題
8、從默認(rèn)目錄file下讀取指定文件名的景區(qū)景點分布圖
這樣就減少了每次都要創(chuàng)建景區(qū)景點分布圖，也方便從已有的景區(qū)景點分布圖導(dǎo)入系統(tǒng)，不用手動新建，實際應(yīng)用中更加的方便人性化
9、為當(dāng)前的景區(qū)添加景點道路
一開始沒有將景區(qū)景點的路徑清零，以至于添加景點道路后，再從新導(dǎo)入景點較少的景區(qū)景點分布圖，再添加景點道路的時候發(fā)現(xiàn)之前的道路依然存在，因此在添加景點道路之前要將道路景區(qū)清零
3 算法設(shè)計（核心代碼）
//深度優(yōu)先搜索導(dǎo)游線路
int visited[M]={0};
int np=0;//找到的景點個數(shù)
int p[M];//表示各個景點的入度值
void DFS(int c){
? ? //c為景點編號
? ? np++;//每遞歸調(diào)用一次就自加一次，作為判斷是否到了最后一個景點
? ? p[c]++;
? ? if(np==S.count){
? ? ? ? //到了最后一個景點
? ? ? ? cout<<S.mat.Pname[c]<<endl;
? ? ? ? returnMainFace();
? ? }else{
? ? ? ?cout<<S.mat.Pname[c]<<"-->";
? ? }
? ? ?visited[c]=1;
? ? ?for(int i=0;i<S.count;i++){
? ? ? ? if(S.mat.m[c][i]>0&&visited[i]==0){
? ? ? ? ? ? ?DFS(i);
? ? ? ? ? ? ?if(S.count>np){
? ? ? ? ? ? ? ? ?cout<<S.mat.Pname[c]<<"-->";
? ? ? ? ? ? ? ? ?p[c]++;
? ? ? ? ? ? ?}
? ? ? ? ?}
? ? ?}
? ? ?if(np==S.count)
? ? ? ? ?returnMainFace();
}
void guide_line()//導(dǎo)游線路
{
? ? ?checked();
? ? ?cout<<"\n*請輸入起始景點的景點編號：";
? ? ?int c;
? ? ?cin>>c;
? ? ?c--;
? ? ?for(int i=0;i<S.count;i++){
? ? ? ? ?visited[i]=0;
? ? ? ? ?p[i]=0;//入度置初值為0
? ? ?}
? ? ?np=0;
? ? ?cout<<"*形成的導(dǎo)游線路圖（采取深度優(yōu)先策略）如下所示：\n\n\t";
? ? ?DFS(c);
}
//Floyd（佛洛依德）算法，A[M][M]表示最短距離，path[M][M]表示輔助數(shù)組，記住前驅(qū)
void Floyd(int A[M][M],int path[M][M]){
? ? ?int i,j,k;
? ? ?for(i=0;i<S.count;i++){
? ? ? ? ?for(j=0;j<S.count;j++){
? ? ? ? ? ? if(S.mat.m[i][j]==0&&i!=j){
? ? ? ? ? ? ? ? ?//如果兩點之間沒有邊相連，則權(quán)為無窮大
? ? ? ? ? ? ? ? ?A[i][j]=INF;//INF=999666333
? ? ? ? ? ? ?}else if(i==j){
? ? ? ? ? ? ? ? ?A[i][j]=0;
? ? ? ? ? ? ?}else{
? ? ? ? ? ? ? ? ?//S.mat.m[i][j]表示兩個景點之間的道路長度
? ? ? ? ? ? ? ? A[i][j]=S.mat.m[i][j];
? ? ? ? ? ? ?}
? ? ? ? ? ? ?//給所有的path[i][j]賦值
? ? ? ? ? ? ?if(i!=j&&S.mat.m[i][j]<INF){
? ? ? ? ? ? ? ? ?path[i][j]=i;
? ? ? ? ? ? ?}else{
? ? ? ? ? ? ? ? ?//（i==j&&S.mat.m[i][j]=INF
? ? ? ? ? ? ? ? ?path[i][j]=-1;
? ? ? ? ? ? ?}
? ? ? ? ?}
? ? ?}
? ? ? ? //k注意放到最外層，讓A[i][j]檢測都經(jīng)過每一個k
? ? ? ? ?for(k=0;k<S.count;k++){
? ? ? ? ? ? ?for(i=0;i<S.count;i++){
? ? ? ? ? ? ? ? for(j=0;j<S.count;j++){
? ? ? ? ? ? ? ? ? ? if(A[i][j]>A[i][k]+A[k][j]){//如果i->j的權(quán)值大于i->k->j的權(quán)值
? ? ? ? ? ? ? ? ? ? ? ? A[i][j]=A[i][k]+A[k][j];
? ? ? ? ? ? ? ? ? ? ? ? path[i][j]=path[k][j];//path[k][j]=k前驅(qū)?k是指向的下一個景點
? ? ? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ? ? ?}
? ? ? ? ? ? ?}
? ? ? ? ?}
}
void min_distance()//最短路徑、距離
{
? ? ?checked();
? ? ?int A[M][M],path[M][M];
? ? ?Floyd(A,path);//A是一個景點到另一個景點的最短路徑的長度
? ? ?while(true){
? ? ? ? ?Num_Name();//編號對應(yīng)的景點名稱
? ? ? ? ?int i,j,k,s;
? ? ? ? ?int apath[M],d;//apath[M]是記錄路徑的數(shù)組
? ? ? ? ?bool flag=true;
? ? ? ? ?while(flag){
? ? ? ? ? ? ?cout<<"\t-景點1：";
? ? ? ? ? ? ?cin>>i;
? ? ? ? ? ? ?i--;
? ? ? ? ? ? if(i<0||i>S.count-1){
? ? ? ? ? ? ? ? ?cout<<"*請輸入合法的景點編號:\n";
? ? ? ? ? ? ?}else{
? ? ? ? ? ? ? ? ?flag=false;
? ? ? ? ? ? ?}
? ? ? ? ?}
? ? ? ? ?flag=true;
? ? ? ? ?while(flag){
? ? ? ? ? ? ?cout<<"\t-景點2：";
? ? ? ? ? ? ?cin>>j;
? ? ? ? ? ? ?j--;
? ? ? ? ? ? if(j<0||j>S.count-1){
? ? ? ? ? ? ? ? ?cout<<"*請輸入合法的景點編號:\n";
? ? ? ? ? ? ?}else{
? ? ? ? ? ? ? ? ?flag=false;
? ? ? ? ? ? ?}
? ? ? ? ?}
? ? ? ? if(A[i][j]<INF&&i!=j){
? ? ? ? ? ? ?k=path[i][j];//k是指向的下一個景點
? ? ? ? ? ? ?d=0;//路徑有d+2個景點,是數(shù)組apath的下標(biāo)
? ? ? ? ? ? ?//將待輸出的路徑的點存放在棧apath中
? ? ? ? ? ? ?apath[d]=j;//最后一個景點
? ? ? ? ? ? while(k!=-1&&k!=i){
? ? ? ? ? ? ? ? ?d++;
? ? ? ? ? ? ? ? ?apath[d]=k;
? ? ? ? ? ? ? ? ?//再繼續(xù)判斷還有沒有景點
? ? ? ? ? ? ? ? ?k=path[i][k];
? ? ? ? ? ? ?}
? ? ? ? ? ? ?d++;
? ? ? ? ? ? ?apath[d]=i;//加上第一點
? ? ? ? ? ? ?cout<<"\n*從 "<<S.mat.Pname[i]<<" 到"<<S.mat.Pname[j]<<" 最短路徑為：";
? ? ? ? ? ? ?cout<<S.mat.Pname[apath[d]];//apath[M]數(shù)組最后一個，就是第一個起點,相當(dāng)于棧
? ? ? ? ? ? ?for(s=d-1;s>=0;s--){//將剩下的景點（apath[M]數(shù)組剩下的元素）打印出來
? ? ? ? ? ? ? ? ?cout<<"-->"<<S.mat.Pname[apath[s]];
? ? ? ? ? ? ?}
? ? ? ? ? ? ?cout<<" ，最短距離為："<<A[i][j]<<endl;//Floyd算法已經(jīng)將最短路徑算出來存放到了A[i][j](將INF的值用最短路徑代替了)
? ? ? ? ?}else if(i==j){
? ? ? ? ? ? ?cout<<"\n*景點輸入不合法，輸入的兩個景點不能相同!\n";
? ? ? ? ?}else{
? ? ? ? ? ? ?cout<<"\n*這兩個景點間不存在路徑\n";
? ? ? ? ?}
? ? ? ? ?cout<<"\n是否繼續(xù)執(zhí)行最短路徑和最短距離的查詢（Y/N）";
? ? ? ? ?Y_N();
? ? ?}
? ? ?returnMainFace();
}
//道路修建規(guī)劃圖、最小生成樹(prime算法)
void build_road()
{
? ? ?checked();
? ? ?cout<<"\n*道路修建規(guī)劃圖（prime算法）規(guī)劃如下：\n";
? ? ?//Ai[M]表示待選邊的權(quán)值,鄰接矩陣的一行,closest[M]：點編號數(shù)組，記錄下一條路的起點景點的編號
? ? ?intAi[M],min,closest[M],i,j,k,sum=0,num=0;//num表示第幾條路
? ? ?int A[M][M];
? ? ?//賦權(quán)值
? ? ?for(i=0;i<S.count;i++){
? ? ? ? ?for(j=0;j<S.count;j++){
? ? ? ? ? ? if(S.mat.m[i][j]==0&&i!=j){
? ? ? ? ? ? ? ? ?A[i][j]=INF;
? ? ? ? ? ? ?}else if(i==j){
? ? ? ? ? ? ? ? ?A[i][j]=0;
? ? ? ? ? ? ?}else{
? ? ? ? ? ? ? ? A[i][j]=S.mat.m[i][j];
? ? ? ? ? ? ?}
? ? ? ? ?}
? ? ?}
? ? ?for(i=0;i<S.count;i++){
? ? ? ? ?Ai[i]=A[0][i];//取第一行存四個Ai[i]，就是一個景點到所有景點的權(quán)值
? ? ? ? ?closest[i]=0;//0
? ? ?}
? ? ?for(i=1;i<S.count;i++){
? ? ? ? ?min=INF;
? ? ? ? ?//從Ai[j]中選出最小的值存放在min
? ? ? ? ?for(j=0;j<S.count;j++){
? ? ? ? ? ? if(Ai[j]!=0&&Ai[j]<min){
? ? ? ? ? ? ? ? ?min=Ai[j];
? ? ? ? ? ? ? ? ?k=j;//記錄最小的值的列j:k=j，為了下面標(biāo)志此路已選
? ? ? ? ? ? ?}
? ? ? ? ?}
? ? ? ? ?if(min<INF){
? ? ? ? ? ? ?cout<<"\t-第 "<<++num<<" 條路： 從"<<S.mat.Pname[closest[k]]<<" 到"<<S.mat.Pname[k]<<" , 該道路長度為："<<min<<endl;
? ? ? ? ? ? ?sum+=min;//sum累計道路長度，即是已選的權(quán)值
? ? ? ? ?}
? ? ? ? ?Ai[k]=0;//標(biāo)志為已選的邊的權(quán)值，避免重復(fù)選擇
? ? ? ? ?//例子：對比a到c和b到c的權(quán)值，取最小存進(jìn)Ai[j]中
? ? ? ? ?for(j=0;j<S.count;j++){
? ? ? ? ? ? if(A[k][j]!=0&&A[k][j]<Ai[j]){
? ? ? ? ? ? ? ? ?Ai[j]=A[k][j];
? ? ? ? ? ? ? ? ?closest[j]=k;//點編號數(shù)組，記錄下一條路的起點景點的編號
? ? ? ? ? ? ?}
? ? ? ? ?}
? ? ?}
? ? ?cout<<"*修建道路的總長度為："<<sum<<endl;
? ? ?returnMainFace();
}4 運(yùn)行與測試
通過創(chuàng)建不同的景區(qū)景點分布圖來測試，測試結(jié)果正確無誤。
5 總結(jié)與心得
通過認(rèn)真對待數(shù)據(jù)結(jié)構(gòu)課程設(shè)計，認(rèn)真思考如何用算法和代碼來解決現(xiàn)實生活中的問題，認(rèn)真參考優(yōu)秀參考文獻(xiàn)和優(yōu)秀作品后，收獲甚多。一開始，面對現(xiàn)實生活的問題，毫無頭緒，不知如何入手來實現(xiàn)解決現(xiàn)實生活的問題，后來通過參考文獻(xiàn)和別人的類似作品后，才發(fā)現(xiàn)原來數(shù)據(jù)結(jié)構(gòu)算法是這樣使用的，也因此解開之前在上數(shù)據(jù)結(jié)構(gòu)課堂上的疑惑：數(shù)據(jù)結(jié)構(gòu)如何運(yùn)用在我們的工作代碼上?？偟膩碚f，收獲的東西確實不少，只要認(rèn)真對待學(xué)習(xí)上的每一個環(huán)節(jié)，就一定會有收獲。
通過老師的指導(dǎo)，此系統(tǒng)優(yōu)化了很大哦，并且讓我學(xué)會了很多東西，很多實際問題都沒有考慮周全，老師都可以指出并要求我修改，正是因為修改，才讓我學(xué)到了更多的知識，使我明白了，做課程設(shè)計，不單單但是做課程設(shè)計，還要通過這次課程設(shè)計來考慮實際問題，不斷優(yōu)化。
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
如果用qt寫程序作為上位機(jī),然后通過和usb和下位機(jī)通信的時候,就需要用到qt中的串口通信了,下面這篇文章主要給大家介紹了關(guān)于QT實現(xiàn)串口通信的相關(guān)資料,需要的朋友可以參考下2023-02-02
基于C++詳解數(shù)據(jù)結(jié)構(gòu)(附帶例題)
數(shù)據(jù)結(jié)構(gòu)作為每一個IT人不可回避的問題,本文基于C++編寫,下面這篇文章主要給大家介紹了關(guān)于數(shù)據(jù)結(jié)構(gòu)的相關(guān)資料,文中通過實例代碼介紹的非常詳細(xì),需要的朋友可以參考下2022-06-06
trait模板和policy模板技術(shù)是把模板的trait和policy這兩個針對不同具體類型有變化的方面抽離出來形成兩個獨立的模板。由于trait和policy本身是模板，它的行為是可配置的，在模板中通過組合或者以模板實參傳進(jìn)來的方式使用trait和policy，就可以配置出不同的具體實現(xiàn)2021-06-06
這篇文章主要為大家詳細(xì)介紹了C語言實現(xiàn)電影院選座管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-12-12
C++實現(xiàn)LeetCode(159.最多有兩個不同字符的最長子串)
這篇文章主要介紹了C++實現(xiàn)LeetCode(159.最多有兩個不同字符的最長子串),本篇文章通過簡要的案例,講解了該項技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
獨立鉆石是源于18世紀(jì)法國的宮廷貴族的自我挑戰(zhàn)類單人棋游戲，可以鍛煉邏輯思維能力。本文將用C語言實現(xiàn)這一簡單的游戲，感興趣的小伙伴可以了解一下2023-02-02
C語言scandir函數(shù)獲取文件夾內(nèi)容的實現(xiàn)
scandir?函數(shù)用于列舉指定目錄下的文件列表,本文主要介紹了C語言scandir函數(shù)獲取文件夾內(nèi)容的實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2024-03-03
本文主要介紹了用C語言遞歸實現(xiàn)火車調(diào)度算法詳解，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章主要為大家詳細(xì)介紹了C語言控制臺應(yīng)用程序GDI繪制正弦曲線，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-06-06
C語言實現(xiàn)的統(tǒng)計php代碼行數(shù)功能源碼（支持文件夾、多目錄）
這篇文章主要介紹了C語言實現(xiàn)的統(tǒng)計php代碼行數(shù)功能源碼,支持文件夾、多級目錄的統(tǒng)計,在一些環(huán)境中會用到這個功能,需要的朋友可以參考下2014-08-08