数据结构-校园导游程序(附源码)

《数据结构-校园导游程序(附源码)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、.实习报告实验名称：校园导游程序日期：2017年7月7日姓名：李琛学号：20153204班级：信1501-2指导教师：陈娜　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　1．实验题目校园导游程序[问题描述]用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。2．需求分析游客通过终端可询问：（1）从某一景点到另一景点的最短路径。（2）游客从公园进入，选取一条最佳路线。（3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。[基本要求]（1

2、）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离．为此图选择适当的数据结构。（2）把各种路径都显示给游客，由游客自己选择浏览路线。（3）画出景点分布图于屏幕上。3．概要设计数据类型定义#include#include//图的邻接矩阵存储表示#defineMaxInt32767//极大值#defineMVNum100//最大顶点数//顶点类型为字符型typedefintArcType;//边的权值为整型usingnamespacestd;inti,j;intS[100],D[100],min,Path[100]

3、;intN=49;intbestcost=MaxInt;//记录目前最少运费或代价intcurrentcost;//当前运费或代价intcurrent[MaxInt];//当前路径intbest[MaxInt];//记录最佳路径structAMGraphd{...stringvexs[MVNum];//顶点表intarcs[MVNum][MVNum];//邻接矩阵intvexnum;//图的当前点数intarcnum;//边数stringinfo[MVNum];//景点介绍}G;主函数调用其它函数4．详细设计#include#include//图的邻接矩阵

4、存储表示#defineMaxInt32767//极大值#defineMVNum100//最大顶点数//顶点类型为字符型typedefintArcType;//边的权值为整型usingnamespacestd;inti,j;intS[100],D[100],min,Path[100];intN=49;intbestcost=MaxInt;//记录目前最少运费或代价intcurrentcost;//当前运费或代价intcurrent[MaxInt];//当前路径intbest[MaxInt];//记录最佳路径structAMGraphd{stringvexs[MVNum];//顶点表intarc

5、s[MVNum][MVNum];//邻接矩阵intvexnum;//图的当前点数intarcnum;//边数stringinfo[MVNum];//景点介绍}G;...//-------------------------------------------------voidswap(int&a,int&b){inttemp=a;a=b;b=temp;}voidbacktrack(intt)//其实就是一个排列问题。。。{intj;if(t==N)//到了最后一层。。{if(G.arcs[current[t-1]][current[t]]+G.arcs[current[t]][1]+cur

6、rentcost(t-1)的代价或运费{currentcost+=G.arc

7、s[current[t-1]][current[t]];backtrack(t+1);//递归回溯currentcost-=G.arcs[current[t-1]][current[t]];}swap(current[t],current[j]);}}//-------------------------------------------voidall(){inti;...for(i=1;i<=N;i++)