数据结构课程设计（四）：校园导游程序

问题描述：用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。
基本要求：查询各景点的相关信息；查询图中任意两个景点间的最短路径；查询图中任意两个景点间的所有路径；增加、删除、更新有关景点和道路的信息。
操作：给景点之间的路径赋最大值；最短路径的C语言函数；输出最短路径和最短距离函数；输入景点代码查景点名称和简介；输入景点代码查到其它景点的最短距离。

#include using namespace std;#define MaxInt 32767
#define MVNum 100typedef struct message
{int num;          //景点代码char name[100];    //景点名称char pro[500];      //简介
} Ciceroni;typedef Ciceroni VerTexType;
typedef int ArcType;
typedef struct
{VerTexType vexs[MVNum];ArcType arcs[MVNum][MVNum];int vexnum,arcnum;
} AMGraph;Ciceroni  school[20]= {{1,"第9寝室楼","5:30-22:30"},{2,"食堂","5:30-11:00"},{3,"文法楼","5:00-23:00,一楼可补办学生卡"},{4,"篮球场","全天开放"},{5,"丹青楼","5:00-23:00"},{6,"行政楼","5:00到11:00"},{7,"图书馆","6:00-21:45,星期三下午12:00-18:00阅览室闭馆"},{8,"锦绣楼","5:00-23:00"},{9,"理化楼","5:00-23:00"},{10,"林学楼","5:00-23:00"}
};void CreatMap(AMGraph &G)
{int i,j;G.vexnum=10;G.arcnum=12;for(i=0; i<G.vexnum; i++)for(j=0; j<G.vexnum; j++)G.arcs[i][j]=MaxInt;//已知路线长度G.arcs[0][1]=150;G.arcs[0][2]=100;G.arcs[1][9]=200;G.arcs[2][3]=200;G.arcs[2][9]=300;G.arcs[2][4]=300;G.arcs[3][6]=200;G.arcs[4][5]=100;G.arcs[4][7]=50;G.arcs[5][6]=100;G.arcs[7][8]=50;G.arcs[8][9]=100;for(i=0; i<10; i++)G.vexs[i]=school[i];for(i=0; i<G.vexnum; i++)for(j=0; j<G.vexnum; j++)G.arcs[j][i]=G.arcs[i][j];
}
void PrintMap()
{cout<<"\n";cout<<"                【学校地图】\n";cout<<"食堂(2)--------9号宿舍楼(1)                      \n";cout<<" |                 |                             \n";cout<<"林学楼(10)------文法楼(3)------------ 篮球场(4) \n";cout<<" |                  |                     |      \n";cout<<"理化楼(9)-锦绣楼(8)-丹青楼(5)-行政楼(6)-图书馆(7)\n\n";
}void PrintPlace(AMGraph G,int num)
{cout<<"【景点编码】:"<<G.vexs[num-1].num<<"\n【景点名称】:"<<G.vexs[num-1].name<<"\n【景点简介】:"<<G.vexs[num-1].pro<<endl;
}void SeePlace(AMGraph G)
{for(int i=0; i<G.vexnum; i++)PrintPlace(G,i+1);
}
void DFS_AM(AMGraph G,int v,int visited[])
{PrintPlace(G,v+1);visited[v]=1;for(int w=0; w<G.vexnum; w++)if((G.arcs[v][w]!=0)&&(!visited[w]))DFS_AM(G,w,visited);
}
void Menu()
{cout<<"┍---------------------------------------┑\n";cout<<"             【校园导游程序】\n";cout<<"【1】--查看学校平面图\n";cout<<"【2】--求两景点之间的最短路径\n";cout<<"【3】--增加新的景点\n";cout<<"【4】--删除指定路线\n";cout<<"【5】--查看指定景点信息\n";cout<<"【6】--更改景点相关信息\n";cout<<"【7】--查看所有现有景点\n";cout<<"【0】--退出程序\n";cout<<"┕----------------------------------------┙\n";cout<<"请输入指令(1-6):";
}int CheckNum(int num,AMGraph G)
{for(int i=0; i<G.vexnum; i++)if(G.vexs[i].num==num)return 1;return 0;
}void Change(AMGraph &G,int v,int n,int visited[])
{if(n==v){cout<<"请输入新的景点名称:";cin>>G.vexs[n].name;cout<<">景点名称更改为:"<<G.vexs[n].name<<endl;cout<<"请输入新的景点简介:";cin>>G.vexs[n].pro;cout<<">景点简介更改为:"<<G.vexs[n].pro<<endl;cout<<"景点信息更改完成."<<endl;}visited[v]=1;for(int w=0; w<G.vexnum; w++)if((G.arcs[v][w]!=0)&&(!visited[w]))Change(G,w,n,visited);
}void NewPlace(AMGraph &G)
{int new_num,num,n,i,j;cout<<"输入新景点编码:";cin>>school[G.vexnum].num;if(CheckNum(school[G.vexnum].num,G)){cout<<"景点编码已存在!\n";return;}cout<<"输入新景点名称:";cin>>school[G.vexnum].name;cout<<"输入新景点简介:";cin>>school[G.vexnum].pro;G.vexs[G.vexnum]=school[G.vexnum];//cout<for(int i=0; i<=G.vexnum; i++)G.arcs[i][G.vexnum]=MaxInt;cout<<"输入新景点相关路线信息(应包含两端点以及路线长度,输入0 0结束):\n";cin>>new_num>>num;while(new_num!=0){new_num=new_num-1;num=num-1;n++;//增加边数cin>>G.arcs[new_num][num];G.arcs[num][new_num]=G.arcs[new_num][num];//注意编码比数组坐标大1！cin>>new_num>>num;}cout<<"景点【"<<school[G.vexnum].name<<"】创建成功";for(i=0; i<=G.vexnum; i++)for(j=0; j<=G.vexnum; j++)G.arcs[j][i]=G.arcs[i][j];G.vexnum++;G.arcnum=G.arcnum+n;
}void ShortestPath_Floyd(AMGraph G)//佛洛伊德算法求vi,vj之间最短距离
{int i,j,k,D[MVNum][MVNum],path[MVNum][MVNum];int place[MVNum];int v0,v1;for(i=0; i<G.vexnum; i++)for(j=0; j<G.vexnum; j++){D[i][j]=G.arcs[i][j];if(D[i][j]<MaxInt&&i!=j)path[i][j]=i;//j前驱为ielsepath[i][j]=-1;//j前驱为-1}for(k=0; k<G.vexnum; k++)for(i=0; i<G.vexnum; i++)for(j=0; j<G.vexnum; j++)if(D[i][k]+D[k][j]<D[i][j])//从i到k,再到j路径更短{D[i][j]=D[i][k]+D[k][j];path[i][j]=path[k][j];}for(i=0; i<G.vexnum; i++)for(j=0; j<G.vexnum; j++)if(i==j)D[i][j]=D[j][i]=0;cout<<"请输入起点:";cin>>v0;cout<<"请输入终点:";cin>>v1;v0--;v1--;//下标从0开始int t=v1;//v1接下来会改变,寄存给ti=0;cout<<"【"<<G.vexs[v0].name<<"】到【"<<G.vexs[v1].name<<"】的最短距离为 "<<D[v0][v1]<<" m\n";cout<<"\n其最短路线为 :【"<<G.vexs[v0].name<<"】<->";while(path[v0][v1]!=v0){place[i]=path[v0][v1];i++;v1=path[v0][v1];}i--;for(i; i>=0; i--)cout<<"【"<<G.vexs[place[i]].name<<"】<->";cout<<"【"<<G.vexs[t].name<<"】"<<endl;
}void DeleteRoad(AMGraph &G)
{int num1,num2;cout<<"输入删除路线端点:";cin>>num1>>num2;num1--;num2--;G.arcs[num1][num2]=MaxInt;G.arcs[num2][num1]=MaxInt;cout<<"删除【"<<G.vexs[num1].name<<"】到【"<<G.vexs[num2].name<<"】路线成功\n";
}
void Order(AMGraph G)
{while(1){int x,num,visited[MVNum]= {0};;Menu();cin>>x;switch(x){case 0:cout<<"\n成功退出程序...\n";return;break;case 1:PrintMap();system("pause");system("cls");break;case 2:ShortestPath_Floyd(G);system("pause");system("cls");break;case 3:NewPlace(G);system("pause");system("cls");break;case 4:DeleteRoad(G);system("pause");system("cls");break;case 5:cout<<"请输入查找景点编码:";cin>>num;if(!CheckNum(num,G))cout<<"无效编码！"<<endl;elsePrintPlace(G,num);system("pause");system("cls");break;case 6:cout<<"要更改的景点编码:";cin>>num;if(!CheckNum(num,G))cout<<"无效编码！"<<endl;elseChange(G,0,num-1,visited);system("pause");system("cls");break;case 7:DFS_AM(G,0,visited);system("pause");system("cls");break;default:cout<<"无效指令！"<<endl;system("pause");system("cls");}}
}
int main()
{AMGraph G;CreatMap(G);Order(G);return 0;
}
//小绵杨Yeanling

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！