校园导游咨询程序设计报告.doc

数据结构课程设计设计题目： 校园导游咨询 学 院： 信息学院 班 级： 计算机1008班 姓 名： 学 号： 20101221180 日期： 2012 年 3 月校园导航问题问题描述设计一个校园导游程序，为来访的客人提供各种信息查询服务。基本要求（1）设计所在学校的校园平面图，所含景点不少于十个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供图中任意景点的问路查询，即查询任意两个顶点之间的一条最短的简单路径。（4）校园导游图的景点和道路的修改扩充功能。（5）扩充道路信息，如道路类别（车道、人行道），以致可按客人所需分别查询人行路径或车行路径。（6）扩充每个景点的林洁景点的方向等信息，使得路径查询结果能提供详尽的导向信息。（7）实现校园导游的仿真界面。一、 概要设计4二、 详细设计6三、 调试分析12四、 调用关系12五、用户操作指南13测试数据1、 概要设计1. 数据类型#define V_MAX 20#define E_MAX 200typedef struct char name10;/名字/char code10;/代码char info20;/信息，简介int x,y;/坐标VType;/顶点类型typedef struct int live;/标记是否存在，如果被删除则为0，存在为1char name10;/ 路名int length;/路的长度char ivex10,jvex10;/路(边)连接的两个顶点的名字int type;/表示道路类型，0表示两个都是，1表示人行道，2表示行车道EdgeType;/边类型typedef struct AdjNodeint length;/ 弧的长度char name10;/关联的顶点的名字struct AdjNode *next;/下一条弧AdjNode;/弧结点typedef struct int live;/标记是否存在，如果被删除则为0，存在为1int flag;/标记是否被访问过VType data;/顶点的信息 AdjNode *first_adj;/指向该顶点的第一条弧VNode;/景点（顶点）结点typedef struct VNode vexV_MAX;/顶点数组EdgeType edgeE_MAX;/边的数组int v_num,e_num;Graph;/图类型/Graph G;AdjNode *p;2.基本函数/void creatGraph(Graph &G);/创建校园图void load(Graph &G);/从文件中读取数据void save(Graph &G);/保存数据入文件int find_v(Graph G,char name10);/通过输入景点名字，返回该景点在vex数组里的下标void print_Graph(Graph G);/以邻接矩阵的形式输出图信息int direction(Graph G,char bname10,char fname10);/用于判断并输出一个景点在另外一个景点的方位信息void search_view(Graph G);/查询并输出景点的所有信息void del_v(Graph &G);/删除景点void add_v(Graph &G);/增加景点void add_e(Graph &G)/增加道路void modify_v(Graph &G);/修改景点信息void del_e(Graph &G);/删除道路2、 详细设计本程序由m.cpp、head.h、Menu.h、dijie.h4个文件构成。1、 m.cpp主要用于调用菜单函数#include #include #include #include #include head.h#include dijie.h#include allpath.h#include Menu.hvoid main() load(G);/while(1)menu();2. Menu.h存放用于显示系统仿真界面的函数void mobifyMenu()while(1)system(cls);int choose;printf(-);printf(n);printf( 校园导游系统 );printf(n);printf(-);printf(n);printf( 景点或者道路信息的修改扩充 );printf(n);printf(n);printf(-);printf(n);printf(1. 增加新景点n);printf(2. 删除景点n);printf(3. 修改景点n);printf(4. 增加新道路n);printf(5. 重新构建校园景点和路径信息n);printf(0. 返回上一个菜单n);printf(请输入操作代码：);scanf(%d,&choose);getchar();system(cls);switch(choose)case 1:add_v(G);break;case 2:del_v(G);break;case 3:modify_v(G);break;case 4:add_e(G);break;case 5:creatGraph(G);break;case 0:return;void menu()int choose;printf(-);printf(n);printf( 校园导游系统 );printf(n);printf(-);printf(n);printf( 景点预览 );printf(n);for(int i=0;iG.v_num;i+) printf( %s ,G.);if(i+1)%2=0) printf(n);printf(n);/print_Graph(G);printf(-);printf(n);printf(1. 景点或者道路信息的修改扩充n);printf(2. 查询景点信息n);printf(3. 查询最佳观光路径n);printf(0. 退出系统n);printf(请输入操作代码：);scanf(%d,&choose);getchar();system(cls);switch(choose)case 1:mobifyMenu();break;case 2:search_view(G);getchar();break;case 3:FDijkstra(G);getchar();break;case 0:exit(0);break;system(cls);3. head.h本文件用于存放基本操作函数，在此不做详细介绍4. dijie.h本文件用于查询并输出两个景点间的最佳路径并输出const int maxnum = 20;const int maxint = 10000;int cmaxnummaxnum;/图的邻接矩阵int P maxnum maxnum;/标明最短路径经过哪个点bool finalmaxnum;/标明从原点到某个点的最短路径已经找到int Dmaxnum;/记录最短路径的长度int pathmaxnum,jishu=0;/path用于按顺序存放已找到最短路径的顶点，path1为第二个已经找到的/需要注意的是，如果图中有9个顶点，其中有两个无法到达，则path的最后面3个就是重复的/要注意区分开/ 用迪杰斯特拉算法找出最短路径void DIJ(Graph G,int v0,int P maxnum maxnum,int Dmaxnum)jishu=0;int min;for(int v=0;vG.v_num;v+)finalv=false; Dv=cv0v;for(int w=0;wG.v_num;+w) Pvw=0;if(Dvmaxint) Pvv0=1;Pvv=1;Dv0=0;finalv0=true;pathjishu=v0;jishu+;for(int i=1;iG.v_num;+i)min=maxint;for(int w=0;wG.v_num;+w) if(!finalw) if (Dwmin) v=w;min=Dw; finalv=true;pathjishu=v;jishu+;for(w=0;wG.v_num;+w)if(!finalw&(min+cvwDw)Dw=min+cvw;/Pw=Pv;for(int j=0;jG.v_num;j+)Pwj=Pvj;Pww=1;/纠正jishufor(jishu=1,i=1;i1000) printf(没有能够到达的路径n);return ;int shortPathV_MAX,count=0;/count指最短路径里到底有几个点/ shortPath里面是正确连续的最短路径/若果shortPath=0，4，3，5，则最短路径为0-4-3-5shortPath0=b_v;for(int i=1;ijishu;i+)if(Pf_vpathi=1) / 问题出在pathi上，由于有两个景点是无法到达的/ 所以pathi后面三个元素都是重复的,导致count数多了2个count+;shortPathcount=pathi;/puts(G.);/ 通过shortPath输出路线信息int roadV_MAX;/road0记录的是从shortPath0到shortPath1要走的路for(i=0;icount;i+) /i指向两个邻接点的起点，i+1表示终点for(int j=0;jG.e_num;j+) /找连接这两个顶点的边，j指向边 if(strcmp(G.edgej.ivex,G.vexshortP)=0&strcmp(G.edgej.jvex,G.vexshortPathi+1.)=0) roadi=j;break; if(strcmp(G.edgej.jvex,G.vexshortP)=0&strcmp(G.edgej.ivex,G.vexshortPathi+1.)=0) roadi=j;break; printf(从 );for(i=0;icount;i+)printf(%sn,G.vexshortP);printf(往);direction(G,G.vexshortP,G.vexshortPathi+1.); printf( 沿着%s路走 %d 米到n,G.,G.edgeroadi.length);puts(G.vexf_);/ 查询两个景点间最短路径函数void FDijkstra(Graph G)int vi,vj;char begin_p10,final_p10;int b_v,f_v; for(int g=0;gG.v_num;g+) for(int h=0;hG.v_num;h+) cgh=maxint;for(int h=0;hV_MAX;h+)for(g=0;gV_MAX;g+)Pgh=0;for( h=0;hV_MAX;h+)finalh=false;for(h=0;hV_MAX;h+)Dh=10000;for(h=0;hV_MAX;h+)pathh=0;jishu=0;int t;printf(选择道路类型(人行道1/行车道2/两者都行0)：);scanf(%d,&t);getchar();/ 构建邻接矩阵for(int i=0;iG.e_num;i+)if(G.edgei.type=t|G.edgei.type=0) vi=find_v(G,G.edgei.ivex); vj=find_v(G,G.edgei.jvex); cvivj=G.edgei.length; cvjvi=G.edgei.length;printf(请输入起点：);while(1)gets(begin_p); if(find_v(G,begin_p)=100) printf(不存在该景点，请重新输入：);continue;break;b_v=find_v(G,begin_p);printf(请输入终点：);while(1)gets(final_p); if(find_v(G,final_p)=100) printf(不存在该景点，请重新输入：);continue;break;f_v=find_v(G,final_p); DIJ(G,b_v,P,D);print_path(G,b_v,f_v);3、 调试分析数据结构书中的迪杰斯特拉算法只能求出最短路径中有哪个景点，但无法求出这几个景点的经过顺序，所以先利用迪杰斯特拉算法记录下某个顶点求出到最短路径的顺序，然后再比对哪几个景点是最短路径里所经过的得出最短路径及