数据结构校园导游程序设计合集资料.doc

校园导游程序(c++)问题描述: 用无向网表示你所在学校的校园景点平面图,图中顶点表示主要景点,存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 基本要求： 1、查询各景点的相关信息。 2、查询图中任意两个景点间的最短路径。 3、查询图中任意两个景点间的所有路径。 4、增加、删除、更新有关景点和道路的信息。 /*校园导游程序*//*[问题描述] 用无向网表示学校的校园景点平面图，图中顶点表示主要景点， 存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。 游客通过终端可询问： （1）从某一景点到另一景点的最短路径。 （2）游客从公园进入，选取一条最佳路线。 （3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。 [基本要求] （1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路， 边上的权值表示距离．为此图选择适当的数据结构。 （2）把各种路径都显示给游客，由游客自己选择浏览路线。 （3）画出景点分布图于屏幕上。 [实现提示] （1）构造一个无向图G并用邻接矩阵来存储。 （2）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组p[i][]来记录， 最短路径长度就用一维数组d[i]存放；i的范围：0～20。 （3）一维数组have[]是用来记录最短路径出现顶点的顺序。 （4）根据起点和终点输出最短路径和路径长度。 */ #define INFINITY 10000 /*无穷大*/ #define MAX_VERTEX_NUM 40 #define MAX 40 #includestdlib.h #includestdio.h #includeconio.h #includestring.h typedef struct ArCell { int adj; //路径长度 }ArCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef struct //图中顶点表示主要景点，存放景点的编号、名称、简介等信息， { char name[30]; int num; char introduction[100];//简介 }infotype; typedef struct { infotype vexs[MAX_VERTEX_NUM]; AdjMatrix arcs; int vexnum,arcnum; }MGraph; MGraph b; void cmd(void); MGraph InitGraph(void); void Menu(void); void Browser(MGraph *G); void ShortestPath_DIJ(MGraph * G); void Floyd(MGraph *G); void Search(MGraph *G); int LocateVex(MGraph *G,char* v); MGraph * CreatUDN(MGraph *G); void print(MGraph *G); /******************************************************/ void main(void) { system(color 1f); system(mode con: cols=140 lines=130); cmd(); } /******************************************************/ void cmd(void) { int i; b=InitGraph(); Menu(); scanf(%d,i); while(i!=5) { switch(i) { case 1:system(cls);Browser(b);Menu();break; case 2:system(cls);ShortestPath_DIJ(b);Menu();break; case 3:system(cls);Floyd(b);Menu();break; case 4:system(cls);Search(b);Menu();break; case 5:exit(1);break; default:break; } scanf(%d,i); } } MGraph InitGraph(void)