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

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

2、别查询人行路径或车行路径。(6)扩充每个景点的林洁景点的方向等信息，使得路径查询结果能提供详尽的导向信息。(7)实现校园导游的仿真界面。一、概要设计4.二、详细设计6.三、调试分析12四、调用关系12五、用户操作指南1.3测试数据注：图中未标明类型的退防均为人行、车行道共寻一、概要设计1.数据类型#defineV_MAX20#defineE_MAX200typedefstructcharname10;名字/charcode10;/代码charinfo20;/信息，简介intx,y;坐标VType;/顶点类型typedefstructintlive;/标记是否存在，如果被删除则为0,存在为1ch

3、arname10;/路名intlength;/路的长度charivex10,jvex10;/路（边）连接的两个顶点的名字inttype;/表示道路类型，。表示两个都是，1表示人行道，2表示行车道EdgeType;/边类型typedefstructAdjNodeintlength;/弧的长度charname10;/关联的顶点的名字structAdjNode*next;下一条弧AdjNode;弧结点typedefstructintlive;/标记是否存在，如果被删除则为0,存在为1intflag;/标记是否被访问过VTypedata;顶点的信息AdjNode*first_adj;/指向该顶点的第一

4、条弧VNode;/景点(顶点)结点typedefstructVNodevexV_MAX;/顶点数组EdgeTypeedgeE_MAX;/边的数组intv_num,e_num;Graph;/图类型/GraphG;AdjNode*p;2.基本函数/voidcreatGraph(Graph&G);/创建校园图voidload(Graph&G);/从文件中读取数据voidsave(Graph&G);/保存数据入文件intfind_v(GraphG,charname10);/通过输入景点名字，返回该景点在vex数组里的下标voidprint_Graph(GraphG);/以邻接矩

5、阵的形式输出图信息intdirection(GraphG,charbname10,charfname10);用于判断并输出一个景点在另外一个景点的方位信息voidsearch_view(GraphG);/查询并输出景点的所有信息voiddel_v(Graph&G);/删除景点voidadd_v(Graph&G);/增加景点voidadd_e(Graph&G)/增加道路voidmodify_v(Graph&G);/修改景点信息voiddel_e(Graph&G);/删除道路二、详细设计本程序由m.cpp、head.h、Menu.h、dijie.h4个文件构

6、成。1. m.cpp主要用于调用菜单函数#include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#include"head.h"#include"dijie.h"#include"allpath.h"#include"Menu.h"voidmain()load(G);/while(1)menu();2. Menu.h存放用于显示系统仿真界面的函数voidmobifyMenu()whi

7、le(1)system("cls");intchoose;printf("");printf("n");printf("校园导游系统");printf("n");printf("");printf("n");printf("景点或者道路信息的修改扩充");printf("n");printf("n");printf("");printf("n");print

8、f（"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)case1:add_v(

9、G);break;case2:del_v(G);break;case3:modify_v(G);break;case4:add_e(G);break;case5:creatGraph(G);break;case0:return;voidmenu()intchoose;printf("");printf("n");printf("校园导游系统");printf("n");printf("");printf("n");printf("景点预览");printf

10、("n");for(inti=0;i<G.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");pri

11、ntf("0.退出系统n");printf("请输入操作代码：");scanf("%d",&choose);getchar();system("cls");switch(choose)case1:mobifyMenu();break;case2:search_view(G);getchar();break;case3:FDijkstra(G);getchar();break;case0:exit(0);break;system("cls");3. head.h本文件用于存放基本操作函数，

12、在此不做详细介绍4. dijie.h本文件用于查询并输出两个景点间的最佳路径并输出constintmaxnum=20;constintmaxint=10000;intcmaxnummaxnum;/图的邻接矩阵intPmaxnummaxnum;/标明最短路径经过哪个点boolfinalmaxnum;/标明从原点到某个点的最短路径已经找到intDmaxnum;/记录最短路径的长度intpathmaxnum,jishu=0;/path用于按顺序存放已找到最短路径的顶点，path1为第二个已经找到的需要注意的是，如果图中有9个顶点，其中有两个无法到达，则path的最后面3个就是重复的/要注意区分开/用

13、迪杰斯特拉算法找出最短路径voidDIJ(GraphG,intv0,intPmaxnummaxnum,intDmaxnum)jishu=0;intmin;for(intv=0;v<G.v_num;v+)finalv=false;Dv=cv0v;for(intw=0;w<G.v_num;+w)Pvw=0;if(Dv<maxint)Pvv0=1;Pvv=1;Dv0=0;finalv0=true;pathjishu=v0;jishu+;for(inti=1;i<G.v_num;+i)min=maxint;for(intw=0;w<G.v_num;+w)if(!final

14、w)if(Dw<min)v=w;min=Dw;finalv=true;pathjishu=v;jishu+;for(w=0;w<G.v_num;+w)if(!finalw&&(min+cvw<Dw)Dw=min+cvw;/Pw=Pv;for(intj=0;j<G.v_num;j+)Pwj=Pvj；Pww=1;纠正jishufor(jishu=1,i=1;i<G.v_num;i+)if(pathi=pathi-1)break;elsejishu+;/输出最短路径voidprint_path(GraphG,intb_v,intf_v)if(Df_v&g

15、t;1000)printf("没有能够到达的路径n");return;intshortPathV_MAX,count=0;/count指最短路径里到底有几个点/shortPath里面是正确连续的最短路径若果shortPath=0,4,3,5,则最短路径为0->4->3->5shortPath0=b_v;for(inti=1;i<jishu;i+)if(Pf_vpathi=1)/问题出在pathi上，由于有两个景点是无法到达的/所以pathi后面三个元素都是重复的，导致count数多了2个count+;shortPathcount=pathi;puts

16、(G.);/通过shortPath输出路线信息introadV_MAX;/road0记录的是从shortPath0至1JshortPath1要走的路for(i=0;i<count;i+)/i指向两个邻接点的起点，i+1表示终点for(intj=0;j<G.e_num;j+)找连接这两个顶点的边，j指向边if(strcmp(G.edgej.ivex,G.vexshortP)=0&&strcmp(G.edgej.jvex,G.vexshortPathi+1.)=0)roadi=j;brea

17、k;if(strcmp(G.edgej.jvex,G.vexshortP)=0&&strcmp(G.edgej.ivex,G.vexshortPathi+1.)=0)roadi=j;break;printf("从")；for(i=0;i<count;i+)printf("%sn",G.vexshortP);printf("往");direction(G,G.vexshortP,G.vexshortPathi+1.

18、);printf("沿着s路走%d米至1Jn",G.,G.edgeroadi.length);puts(G.vexf_);/查询两个景点间最短路径函数voidFDijkstra(GraphG)intvi,vj;charbegin_p10,final_p10;intb_v,f_v;for(intg=0;g<G.v_num;g+)for(inth=0;h<G.v_num;h+)cgh=maxint;for(inth=0;h<V_MAX;h+)for(g=0;g<V_MAX;g+)Pgh=

19、0;for(h=0;h<V_MAX;h+)finalh=false;for(h=0;h<V_MAX;h+)Dh=10000;for(h=0;h<V_MAX;h+)pathh=0;jishu=0;intt;printf("选择道路类型(人行道1/行车道2/两者都行0)：");scanf("%d",&t);getchar();/构建邻接矩阵for(inti=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("不存在该景点，t#重新输入：");continue;break;b_v=fi