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

1、数据结构课程设计校园导游咨询院:信息学院级:计算机1008班名:t=r.号:20101221180日期： 2012年 3月校园导航问题问题描述设计一个校园导游程序，为来访的客人提供各种信息查询服务。基本要求可、（1）设计所在学校的校园平面图，所含景点不少于十个。以图中顶点表示校 内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度 等信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供图中任意景点的问路查询，即查询任意两个顶点之间的 一条最短的简单路径。（4）校园导游图的景点和道路的修改扩充功能。（5）扩充道路信息，如道路类别（车道、人行道），以致可按客人

2、所需分别查 询人行路径或车行路径。（6）扩充每个景点的林洁景点的方向等信息，使得路径查询结果能提供详尽 的导向信息。（7）实现校园导游的仿真界面。概要设计4,详细设计6.调试分析12四、调用关系12五、用户操作指南13测试数据注：圏中未你明类型的追15均为人 行、车行道共仔概要设计1.数据类型#defi ne V_MAX 20#defi ne E_MAX 200typ edef struct char name10;/ 名字 /char code10;/ 代码 char info20;/ 信息，简介 int x,y;/ 坐标VType;/顶点类型typ edef struct int live

3、;/标记是否存在，如果被删除则为0,存在为1char name10;/ 路名 int len gth;/路的长度char ivex10,jvex10;/路（边）连接的两个顶点的名字int type;/表示道路类型，0表示两个都是，1表示人行道，2表示行车道EdgeTy pe;/ 边类型typ edef struct AdjNodeint length;/弧的长度 char name10;/关联的顶点的名字 struct AdjNode *next;/ 下一条弧AdjNode;/ 弧结点typ edef struct int live;/标记是否存在，如果被删除则为0，存在为1int flag;

4、/标记是否被访问过VType data;/顶点的信息AdjNode *first_adj;/指向该顶点的第一条弧VNode;/景点（顶点）结点typ edef struct VNode vexV_MAX;/ 顶点数组EdgeType edgeE_MAX;/ 边的数组 int v_nu m,e_ num;Graph;/图类型/Graph G;AdjNode *p;2.基本函数/void creatGraph(Graph &G);/ 创建校园图void load(Graph &G);/从文件中读取数据void save(Graph &G);/保存数据入文件int find_

5、v(Graph G ,char name10);/通过输入景点名字，返回该景点在 vex数组里的下标 void print_Graph(Graph G);/以邻接矩阵的形式输出图信息int direction(Graph Gchar bname10,char fname10);/ 用于判断并输出一个景点在另外一个 景点的方位信息void search_view(Graph G);/查询并输出景点的所有信息void del_v(Graph &G);/ 删除景点void add_v(Graph &G);/ 增加景点void add_e(Graph &G)/ 增加道路void

6、 modify_v(Graph &G);/ 修改景点信息void del_e(Graph &G);/ 删除道路二、详细设计本程序由 m.cPP、head.h、Menu.h、dijie.h4 个文件构成。1、 m.cpp主要用于调用菜单函数#in clude <stdio.h>#i nclude <stdlib.h> #in clude <malloc.h> #in clude <stri ng.h> #in clude "head.h" #i nclude "dijie.h" #i nclu

7、de "all path.h" #in clude "Me nu.h" void mai n() load(G);/ while(1) menu();2. Menu.h存放用于显示系统仿真界面的函数void mobifyMe nu()while(1)system("cls"); int choose; prin tf(" printf(” prin tf(" printf(”");prin tf("n");校园导游系统");prin tf("n");景点或

8、者道路信息的修改扩充”);prin tf("n");”);prin tf("n");prin tf("n"); prin tf("- prin tf("1. prin tf("2. prin tf("3. prin tf("4. prin tf("5. prin tf("0.”);prin tf("n");增加新景点n");删除景点n");修改景点n"); 增加新道路n");重新构建校园景点和路径信息n&q

9、uot;);返回上一个菜单n");printf("请输入操作代码："); scan f("%d",&choose); getcharO;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:creatGra ph(G);break; case 0:retur n;void menu()int choose;printf(

10、”"); prin tf("n");prin tf("校园导游系统printf(”"); prin tf("n");prin tf("景点预览for(int i=0;i<G .v_num;i+)printf(”%s ",G.vexi.data. name);if(i+1)%2=0) prin tf("n");prin tf("n");/prin t_Gra ph(G);prin tf("-prin tf("1.prin tf("2

11、.prin tf("3.prin tf("0.printf("请输入操作代码： scan f("%d",&choose);getchar(); system("cls");switch(choose)case 1:mobifyMe nu( );break;case 2:search_view(G);getchar();break;case 3:FDijkstra(G);getchar();break;”);prin tf("n");”);prin tf("n");%s"

12、;);prin tf("n");景点或者道路信息的修改扩充 n"); 查询景点信息n");查询最佳观光路径n");退出系统n");");case 0:exit(0);break; system("cls");3. head.h本文件用于存放基本操作函数，在此不做详细介绍4. dijie.h本文件用于查询并输出两个景点间的最佳路径并输出const int maxnum = 20;const int maxi nt = 10000;int cmaxnummaxnum;/ 图的邻接矩阵int P max nu

13、m max num;/标明最短路径经过哪个点bool finalmaxnum;/标明从原点到某个点的最短路径已经找到int Dmaxnum;/记录最短路径的长度int P athmax nu m,jishu=0;path用于按顺序存放已找到最短路径的顶点，Path1为第二个已经找到的需要注意的是，如果图中有9个顶点，其中有两个无法到达，则Path的最后面3个就是重复的/要注意区分开/用迪杰斯特拉算法找出最短路径void DIJ(Gra ph G,i nt v0,i nt P maxnu m maxnu m,i nt Dmax nu m) jishu=0;int min;for(int v=0;

14、v<G .v_num;v+)fin alv=false; Dv=cv0v;for(int w=0;w<G .v_num;+w) Pvw=0; if(Dv<maxi nt) P vv0=1; Pvv=1;Dv0=0;fi nalv0=true; pathjishu=v0;jishu+;for(int i=1;i<G .v_num;+i)mi n=maxi nt;for(int w=0;w<G .v_num;+w)if(!fi nalw)if (Dw<mi n) v=w;mi n=Dw;fin alv=true ;p athjishu=v;jishu+;for(

15、w=0;w<G .v_num;+w) if(!fi nalw &&(mi n+cvw<Dw) Dw=mi n+cvw;/P w=Pv;for(int j=0;j<G .v_num;j+)P wj=Pvj;P ww=1;/纠正 jishufor(jishu=1,i=1;i<G .v_num;i+) if(p athi=p athi-1) break; else jishu+;/输出最短路径void printPath(Graph G ,int b_v,int f_v)if(Df_v>1000) printf(”没有能够到达的路径n");re

16、turn ;int short PathV_MAX,cou nt=0;/cou nt指最短路径里到底有几个点/ short Path里面是正确连续的最短路径/若果 shortPath=0, 4，3，5，则最短路径为 0->4->3->5 shortP ath0=b_v; for(i nt i=1;i<jishu;i+) if(Pf_vpathi=1)/问题出在pathi上，由于有两个景点是无法到达的/所以Pathi后面三个元素都是重复的，导致count数多了 2个coun t+;short Pathco un t=p athi;/pu ts(G.vex p athi.d

17、ata .n ame);/通过short Path输出路线信息int roadV_MAX;/road0 记录的是从 shortPath0到 shortPath1要走的路for(i=0;i<count;i+)/i指向两个邻接点的起点，i+1表示终点for(int j=0;j<G .e_num;j+)/找连接这两个顶点的边，j指向边 if(strcmp(G.edgej.ivex,G .vexshortP)=0&&strcmp(G.edgej.jvex,G.vexshortP athi+1.data .n ame)=0) roadi=j;bre

18、ak; if(strcmp(G.edgej.jvex,G .vexshortP)=0&&strcmp(G .edgej.ivex,G .vexshort P athi+1.data .n ame)=0) roadi=j;break; printf(” 从”);for(i=0;i<co un t;i+)prin tf(”sn",G.vexshort Pathi.data. name);printf("往");direction(G ,G.vexshortP,G .vexshortPathi

19、+1.);printf(”沿着 %s 路走 %d 米到 n”,G.,G .edgeroadi.length);p uts(G.vexf_v.data. name); /查询两个景点间最短路径函数 void FDijkstra(Gra ph G)int vi,vj;char begin_ p10,fi nal_p 10; int b_v,f_v;for(i nt g=0;g<G.v_ nu m;g+) for(i nt h=0;h<G.v_ nu m;h+) cgh=maxi nt;for(i nt h=0;h<V_MAX;h+)f

20、or(g=0;g<V_MAX;g+)P gh=0；for( h=O;h<V_MAX;h+) fin alh=false;for(h=0;h<V_MAX;h+) Dh=10000;for(h=0;h<V_MAX;h+) pathh=O;jishu=0;int t;printf("选择道路类型(人行道1/行车道2俩者都行0):"); scan f("%d", &t);getchar();/构建邻接矩阵for(int i=0;i<G .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(”不存在该景点，请重新输入：&qu