数据结构课程设计校园导游系统

1、数据结构课程设计学 院： 信息科学与工程学院专 业： 计算机科学与技术班 级： 学 号： 学生姓名： 指导教师： 2012 年 3 月 12 日目录目录1一、校园导游咨询系统的需求分析21.1 系统开发目的及功能21.1.1系统研发目的21.1.2系统功能21.2 系统开发周期21.3 系统测试结果2二、系统框架设计32.1 功能模块间的关系32.2变量的物理存储32.3 主要函数名4三、部分模块的详细设计43.1 求最短路径43.2 求全部路径53.3 求图的关节点6四、用户使用说明6五、调试结果（重要功能）75.1 地图浏览75.2 求最短路径85.3 查找地图的关节点85.4 查找全部路

2、径9六、体会与心得10七、参考教材10八、附录108.1 程序源码108.2 文本文档内容228.2.1建筑景点（图的节点）文本文档228.2.2路径（图的边）信息文本文档23一、校园导游咨询系统的需求分析1.1 系统开发目的及功能1.1.1系统研发目的校园导游咨询系统的研发目的既是为济南大学的游客提供路径咨询、信息查看等服务，亦为管理者对济南大学地理设施进行及时的更新提供后台管理服务。1.1.2系统功能校园导游咨询系统分为游客以下功能：1. 浏览济南大学模拟地图2. 查询建筑（景点）详情3. 查找两景点之间的最短路径4. 查找地图的关节点5. 查找两景点间的所有路径6. 查询路径信息7. 查

3、询与某景点相邻景点的方位本系统在以上功能的基础上还为系统管理员提供后台操作服务：1. 修改景点名称和信息2. 修改道路名称和信息3. 添加新景点和道路（构建新地图）并存储在txt文件中4. 浏览新地图的所有节点1.2 系统开发周期2012-02-272012-03-04搭建系统框架，分析各功能实现算法2012-03-052012-03-07程序调试与修改2012-03-072012-03-14文档整理与总结1.3 系统测试结果程序无语法错误，所列功能都可实现。（详见 五、调试结果）二、系统框架设计2.1 功能模块间的关系主函数身份识别游客功能管理员功能浏览济南大学模拟地图查询建筑（景点）详情查

4、找两景点之间的最短路径查找地图的关节点查找两景点间的所有路径查询路径信息查询与某景点相邻景点的方位游客的功能；地图的修改扩充功能2.2变量的物理存储/=存储定义=typedef struct arcnodeint adjvertex; /关联的顶点序号struct arcnode *nextarc; /指向下一条边 arcnode, *arclink; /边结点的定义typedef struct vertexnodechar dataunlimmax; /景点名称char infounlimmax; /景点信息bool flag; /标志，是否被访问过arcnode *firstarc; /指

5、向关联的第一条边 vertexnode; /顶点结点的定义typedef struct graphvertexnode vertexvernum;int vexnum,arcnum; /图的顶点数，边数int arcvernumvernum;graph; /图的定义typedef struct graph2vertexnode vertexvernum2;int vexnum,arcnum; /图的顶点数，边数int arcvernum2vernum2;graph2; /图的定义/=全局变量=graph g;graph2 q;/shortest pathint pvernumvernum;in

6、t dvernum;arcnode *pathvernum;/the key pointint visitedvernum;/ 访问标志数组(全局量) int count; / 全局量count对访问计数 int lowvernum;/all pathint stackvernum;int top;/pathinfochar *pinfarcnum*2;char *directionarcnum*2;char *pinf2arcnum*2;char *direction2arcnum*2;/passint password=12345678;2.3 主要函数名void creategraph_

7、fomer(graph &g,file *f,file *g) ;/创建图void dfs(graph &g,int i,int num) ;/遍历图void dfstraverse(graph &g,int num) ;/深度遍历void dfsarticul(graph &g,int v0) ; / 从第v0个顶点深度优先遍历图g，查找并输出关节点void findarticul(graph &g) ; / 连通图g以邻接表作存储结构，查找并输出g上全部关节点。void allpath(graph &g,int v0,int v) ; /全部

8、路径void shortestpath_dij(graph &g,int v0) ;/迪杰斯特拉算法求最短路径三、部分模块的详细设计3.1 求最短路径/=最短路径_dijkstra=void shortestpath_dij(graph &g,int v0)int v,w;int i,j,k=0;int min;int finalvernum;arclink p;for(v=0;v<g.vexnum;v+)finalv=false;dv=g.arcv0v;for(w=0;w<g.vexnum;w+)pvw=false;if(dv<unlimmax)pvv0=t

9、rue;pvv=true;/初始化行进路径 paht1 表示 从源点到2(标记从0开始)点的最短路径【反】链表 在此初始化 /printf("*n%dn*",v);p=(arclink) malloc (sizeof(arcnode); /新建边结点，插入在顶点结点后面p->adjvertex= v;p->nextarc=null;pathv=p; elsepathv = null;/for dv0=0;finalv0=true;for(i=1;i<g.vexnum;i+)min=unlimmax;for(w=0;w<g.vexnum;w+)if(!

10、finalw)if(dw<min)v=w;min=dw;finalv=true;for(w=0;w<g.vexnum;w+)if(!finalw&&(min+g.arcvw<dw)dw=min+g.arcvw;/更新最短路径p=(arclink) malloc (sizeof(arcnode); /新建边结点，插入在顶点结点后面p->adjvertex= w;p->nextarc= pathv;pathw= p ; for(j=0;j<g.arcnum;j+)pwj=pvj;pww=true; 3.2 求全部路径void allpath(gr

11、aph &g,int v0,int v)top=0;/栈顶初始化int i,j,k,h=0;stacktop=v0;top+;for(i=v0;i<vernum;i+)/双重循环遍历图for(j=0;j<vernum;j+)if(g.arcij>0)&&(g.arcij<unlimmax)if(j != v)stacktop=j;top+;else/stacktop=j;top+;/景点标号进栈h+;printf("n【路径%d】：",h);for(k=0;k<top;k+)printf("%s->&qu

12、ot;,g.vertex(stackk).data);/景点标号出栈printf("%s",g.vertexv.data);printf("nn");top=0;stacktop=v0;top+; 3.3 求图的关节点/ 算法7.11 p178 / 从第v0个顶点出发深度优先遍历图g，查找并输出关节点。void dfsarticul(graph &g,int v0)int min,w;arcnode *p;visitedv0=min=+count; / v0是第count个访问的顶点 for(p=g.vertexv0.firstarc;p;p=p

13、->nextarc) / 对v0的每个邻接顶点检查 w=p->adjvertex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 dfsarticul(g,w); / 返回前求得loww if(loww<min)min=loww;if(loww>=visitedv0)printf("%d: %sn",v0+1,g.vertexv0.data); / 关节点 else if(visitedw<min)min=visitedw; / w已访问，w是v0在生成树上的祖先 lowv0=min;/ 算法7.10 p1

14、78 / 连通图g以邻接表作存储结构，查找并输出g上全部关节点。 / 全局量count对访问计数。 void findarticul(graph &g)int i,v;arcnode *p;count=1;low0=visited0=1; / 设定邻接表上0号顶点为生成树的根 for(i=1;i<g.vexnum;+i)visitedi=0; / 其余顶点尚未访问 p=g.vertex0.firstarc;v=p->adjvertex;dfsarticul(g,v); / 从第v顶点出发深度优先查找关节点 if(count<g.vexnum) / 生成树的根有至少两棵

15、子树 printf("%d: %sn",0+1,g.vertex0.data); / 根是关节点，输出 while(p->nextarc)p=p->nextarc;v=p->adjvertex;if(visitedv=0)dfsarticul(g,v); 四、用户使用说明以游客为例简介校园导航系统的使用：1. 进入主界面选择用户身份（游客）；2. 选择游客身份；3. 进入游客功能界面选择所要查询的功能。五、调试结果（重要功能）5.1 地图浏览选择地图浏览后，即可观看： 5.2 求最短路径5.3 查找地图的关节点 5.4 查找全部路径（其他功能暂不赘述） 六

16、、体会与心得我在这次课程设计的实践研究之后，感触有以下两点：1. 经典的算法是经过不计其数的实验之后而得出的，所以其算法的可靠性毋庸置疑，而我们应该做的就是怎样利用已有的经典算法达到用户所需要的功能。比如，迪杰斯特拉算法求最短路径，算法已经很经典，所以，开发人员要做的就是怎样把节点的标号记录下来并输出接点的名称。2. 我的水平仍然一般，很多问题也是很长时间才能解决，所以有段时间也很抓狂，并且，我的程序运行之后，仍存在小瑕疵，比如建立新的地图之后不能用新的地图进行路径的查找等。主要是因为我在动态分配这一部分仍然无法运用自如。所以，我一定要在以后的学习中更加努力彭杨自己的编程能力！七、参考教材数据

17、结构（c语言）严蔚敏版数据结构习题集（c语言）严蔚敏版c语言程序设计基础清华大学出版社八、附录8.1 程序源码#include"string.h"#include"stdio.h"#include"stdlib.h"#define error 0#define ok 1typedef int status;#define arcnum 35#define vernum 20#define vernum2 30#define unlimmax 25000#define false 0#define true 1/=存储定义=typede

18、f struct arcnodeint adjvertex; /关联的顶点序号struct arcnode *nextarc; /指向下一条边 arcnode, *arclink; /边结点的定义typedef struct vertexnodechar dataunlimmax; /景点名称char infounlimmax; /景点信息bool flag; /标志，是否被访问过arcnode *firstarc; /指向关联的第一条边 vertexnode; /顶点结点的定义typedef struct graphvertexnode vertexvernum;int vexnum,arc

19、num; /图的顶点数，边数int arcvernumvernum;graph; /图的定义typedef struct graph2vertexnode vertexvernum2;int vexnum,arcnum; /图的顶点数，边数int arcvernum2vernum2;graph2; /图的定义/=全局变量=graph g;graph2 q;/shortest pathint pvernumvernum;int dvernum;arcnode *pathvernum;/the key pointint visitedvernum;/ 访问标志数组(全局量) int count;

20、/ 全局量count对访问计数 int lowvernum;/all pathint stackvernum;int top;/pathinfochar *pinfarcnum*2;char *directionarcnum*2;char *pinf2arcnum*2;char *direction2arcnum*2;/passint password=12345678;/=图的创建=void creategraph_fomer(graph &g,file *f,file *g)int m,n,i,j;int fl=0;arclink p;g.vexnum=vernum;g.arcnu

21、m=arcnum;/构建顶点集for(i=0;i<g.vexnum;i+)for(j=0;j<g.vexnum;j+)if(i != j)g.arcij=unlimmax;elseg.arcij=0;/从txt文档中读取地图信息for(i=0;i<g.vexnum;i+) fscanf(f,"%s",g.vertexi.data);fscanf(f,"%s",g.);g.vertexi.flag=0;g.vertexi.firstarc=null; /构建边集for(i=0;i<g.arcnum;i+)fs

22、canf(g,"%d",&m);fscanf(g,"%d",&n);fscanf(g,"%d",&g.arcmn);fscanf(g,"%s",pinf+(m+n);fscanf(g,"%s",direction+(m+n);p=(arclink) malloc (sizeof(arcnode); /新建边结点，插入在顶点结点后面p->adjvertex=n;p->nextarc=g.vertexm.firstarc;g.vertexm.firstarc=p;

23、 /=图的遍历=void dfs(graph &g,int i,int num)printf("%d:%st",i+1,g.vertexi.data);g.vertexi.flag=ok;for(int j=0;j<num;j+)if(g.vertexi.flag=1 && visitedj)dfs(g,j,num);void dfstraverse(graph &g,int num)puts("ttt济南大学重要建筑设施：n");int i;for(i=0;i<num;i+)visitedi=0;for(i=

24、0;i<num;i+)if(!visitedi)dfs(g,i,num);/=打印地图=void map()/system("cls");printf("");printf(" 济南大学模拟地图 ");printf(" 方向：%c北 ",24);printf(" ");printf(" ");printf(" 4j3s ");printf(" 12j ");printf("g1 ");printf("

25、 library ");printf(" gym jiaz 11j ");printf(" lake ");printf(" ");printf(" ");printf(" ");printf(" 10j ");printf("g2 m* 7j 9j8s ");printf(" ");printf(" 1j ");printf(" square ");printf(" 8j &

26、quot;);printf(" 2j ");printf(" g4 ");printf(" ");printf(" g3 ");printf(" ");printf(" ");printf("");/=查询详情=void dfs_searchinfo(graph &g,int i,int num,char nameunlimmax)if(strcmp(name,g.vertexi.data)=0)printf("nt【%s】 %sn&qu

27、ot;,g.vertexi.data,g.);g.vertexi.flag=ok;for(int j=0;j<num;j+)if(g.vertexi.flag=1 && visitedj)dfs_searchinfo(g,j,num,name);void dfstraverse_searchinfo(graph &g,int num,char nameunlimmax)puts("tt济南大学重要建筑设施详情:");int i;for(i=0;i<num;i+)visitedi=0;for(i=0;i<num

28、;i+)if(!visitedi)dfs_searchinfo(g,i,num,name);void printinfo(graph &g,char nameunlimmax)dfstraverse_searchinfo(g,vernum,name);/=最短路径=void displaypath(graph &g,arcnode *p,int v0)arcnode *prep , *nowp , *nextp;if(p != null)printf(" %d:%s ",v0 + 1,g.vertexv0.data);prep = null; nowp=p;

29、 while(nowp!=null) nextp=nowp->nextarc; nowp->nextarc=prep; prep=nowp;nowp = nextp; doprintf(" -> %d:%s ",prep->adjvertex + 1,g.vertexprep->adjvertex.data);if(prep->nextarc = null) break;prep = prep->nextarc;while(1);printf("n");/=最短路径_dijkstra=void shortestp

30、ath_dij(graph &g,int v0)int v,w;int i,j,k=0;int min;int finalvernum;arclink p;for(v=0;v<g.vexnum;v+)finalv=false;dv=g.arcv0v;for(w=0;w<g.vexnum;w+)pvw=false;if(dv<unlimmax)pvv0=true;pvv=true;/初始化行进路径 paht1 表示 从源点到2(标记从0开始)点的最短路径【反】链表 在此初始化 /printf("*n%dn*",v);p=(arclink) mallo

31、c (sizeof(arcnode); /新建边结点，插入在顶点结点后面p->adjvertex= v;p->nextarc=null;pathv=p; elsepathv = null;/for dv0=0;finalv0=true;for(i=1;i<g.vexnum;i+)min=unlimmax;for(w=0;w<g.vexnum;w+)if(!finalw)if(dw<min)v=w;min=dw;finalv=true;for(w=0;w<g.vexnum;w+)if(!finalw&&(min+g.arcvw<dw)dw

32、=min+g.arcvw;/更新最短路径/ p=(arclink) malloc (sizeof(arcnode); /新建边结点，插入在顶点结点后面p->adjvertex= w;p->nextarc= pathv;pathw= p ; /= by end lgfor(j=0;j<g.arcnum;j+)pwj=pvj;pww=true;void getshortestpath(graph &g,int v0,int v)shortestpath_dij(g,v0);if(dv < unlimmax)printf("n【%s】到【%s】的最短路径为：

33、nn",g.vertexv0.data,g.vertexv.data); displaypath(g,pathv,v0);printf("nn【%s】到【%s】的最短距离为：%d米n",g.vertexv0.data,g.vertexv.data,dv);elseprintf("对不起，无法找到【%s】至【%s】之间的最短路径！",g.vertexv0.data,g.vertexv.data);/=关节点=/ 算法7.11 p178 / 从第v0个顶点出发深度优先遍历图g，查找并输出关节点。void dfsarticul(graph &

34、g,int v0)int min,w;arcnode *p;visitedv0=min=+count; / v0是第count个访问的顶点 for(p=g.vertexv0.firstarc;p;p=p->nextarc) / 对v0的每个邻接顶点检查 w=p->adjvertex; / w为v0的邻接顶点 if(visitedw=0) / w未曾访问，是v0的孩子 dfsarticul(g,w); / 返回前求得loww if(loww<min)min=loww;if(loww>=visitedv0)printf("%d: %sn",v0+1,g.

35、vertexv0.data); / 关节点 else if(visitedw<min)min=visitedw; / w已访问，w是v0在生成树上的祖先 lowv0=min;/ 算法7.10 p178 / 连通图g以邻接表作存储结构，查找并输出g上全部关节点。 / 全局量count对访问计数。 void findarticul(graph &g)int i,v;arcnode *p;count=1;low0=visited0=1; / 设定邻接表上0号顶点为生成树的根 for(i=1;i<g.vexnum;+i)visitedi=0; / 其余顶点尚未访问 p=g.vert

36、ex0.firstarc;v=p->adjvertex;dfsarticul(g,v); / 从第v顶点出发深度优先查找关节点 if(count<g.vexnum) / 生成树的根有至少两棵子树 printf("%d: %sn",0+1,g.vertex0.data); / 根是关节点，输出 while(p->nextarc)p=p->nextarc;v=p->adjvertex;if(visitedv=0)dfsarticul(g,v);/=全部路径=void allpath(graph &g,int v0,int v)top=0;i

37、nt i,j,k,h=0;stacktop=v0;top+;for(i=v0;i<vernum;i+)for(j=0;j<vernum;j+)if(g.arcij>0)&&(g.arcij<unlimmax)if(j != v)stacktop=j;top+;else/stacktop=j;top+;h+;printf("n【路径%d】：",h);for(k=0;k<top;k+)printf("%s->",g.vertex(stackk).data);printf("%s",g.v

38、ertexv.data);printf("nn");top=0;stacktop=v0;top+;/=路径信息=void pathinfo(int s,int v0,int v,graph &g)puts("n您所要查询的路径信息如下：n");printf("%s>%s：%sn",g.vertexv0.data,g.vertexv.data,pinf+s);/=路径信息=void direct(graph &g,int v0)int i,j,k=0;puts("n您所要查询的方向信息如下：n"

39、);for(i=v0;i=v0;i+)for(j=0;j<g.vexnum;j+)if(g.arcij>0)&&(g.arcij<unlimmax)k+;printf("%d:【%s】在【%s】的【%s】面。n",k,g.vertexj.data,g.vertexi.data,direction+(i+j);/=修改地图=void editvertex(graph &g,int v0)printf("n原有信息：n%s:%sn",g.vertexv0.data,g.);printf(&q

40、uot;n请输入景点修改后的名字：");scanf("%s",&g.vertexv0.data);getchar();printf("请输入景点修改后的相应信息：");scanf("%s",&g.);getchar();printf("n操作成功！确认信息：n%s:%sn",g.vertexv0.data,g.);void editarc(graph &g,int v0,int v)printf("n原有信息：n【%s】

41、与【%s】之间的距离为：%dn",g.vertexv0.data,g.vertexv.data,g.arcv0v);printf("n请输入景点修改后路径的长度：");scanf("%d",&g.arcv0v);getchar();printf("n操作成功！确认信息：n【%s】与【%s】之间的距离为：%dn",g.vertexv0.data,g.vertexv.data,g.arcv0v);void dfs_newmap(graph2 &q,int i,int num)printf("%d:%st

42、",i+1,q.vertexi.data);q.vertexi.flag=ok;for(int j=0;j<num;j+)if(q.vertexi.flag=1 && visitedj)dfs_newmap(q,j,num);void dfstraverse_newmap(graph2 &q,int num)puts("ttt修改后的济南大学建筑名称：n");int i;for(i=0;i<num;i+)visitedi=0;for(i=0;i<num;i+)if(!visitedi)dfs_newmap(q,i,num)

43、;void creatgraph_newmap(graph2 &q,int n1,int n2,file *f,file *g)file *f,*g;f=fopen("building2.txt","w");g=fopen("edge2.txt","w");rewind(f);rewind(g);int i,j,m,n,count = 0;arclink p;q.vexnum = vernum + n1;q.arcnum = arcnum + n2;for(i=0;i<vernum;i+)for(j=

44、0;j<vernum;j+)if(i != j)q.arcij=unlimmax;elseq.arcij=0;for(i=0;i<vernum;i+) fscanf(f,"%s",q.vertexi.data);fprintf(f,"%s",&q.vertexi.data);fprintf(f, " ");fscanf(f,"%s",q.);fprintf(f,"%s",&q.);fprintf(f, "n&q

45、uot;);q.vertexi.flag = 0;q.vertexi.firstarc = null;for(i=vernum;i<q.vexnum;i+)count+;printf("请输入新增景点%d的名称：",count); scanf("%s",&q.vertexi.data);getchar();fprintf(f,"%s",&q.vertexi.data);fprintf(f, " ");printf("请输入新增景点%d的信息：",count);scanf(&

46、quot;%s",&q.);getchar();fprintf(f,"%s",&q.);fprintf(f, "n");q.vertexi.flag=0;q.vertexi.firstarc=null;count = 0;for(i=0;i<arcnum;i+)fscanf(g,"%d",&m);fprintf(g,"%d",m);fprintf(g," ");fscanf(g,"%d",&n);fprintf(g,"%d",n);fprintf(g," ");fscanf(g,"%d",&q.arcmn);fprintf(g,&qu