校园导航课程设计说明书.doc

数 据 结 构课 程 设 计 说 明 书   学生姓名:学 号：学 院:软件学院专 业:信息管理与信息系统 题 目:校园导航成绩指导教师 一.设计目的：数据结构课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：1)了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3)提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 4)训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。本系统为用户提供以下功能:(一)、查询了解学校概况，为导游参观者提供关于学校的相关信息。(二)、查询校园各个场所和景点信息;(三)、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学校。校园导航查询系统的开发方法总结如下：(1) 调查，了解学校各个场所与 场所或者是各个景点与景点之间的信息，路径和距离，从外来人员或者参观者和走访者的角度出发，该如何设计才能满足用户需求。(2) 分析，对调查得到的数据进行分析，根据其要求实现的功能分析系统结构和界面将实现的基本功能。(3) 设计与开发，设计系统界面并编辑实现其各个功能的代码。(4) 调试，在设计完成后，调试系统运行的状况，修改完善系统,然后进行测试。二.涉及内容和要求 设计内容：（1）设计学校的平面图（至少包括10个以上的场所）。每两个场所间可以有不同的路，且路长也可能不同；（2）提供起始点与终点能自动找出从任意场所到达另一场所的最佳路径（最短路径）。 设计要求：(1) 符合课题要求，实现相应功能；(2) 要求界面友好美观，操作方便易行；(3) 注意程序的实用性、安全性；三.本设计所采用的数据结构校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所，用图的边代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路径时可用迪杰斯特拉（Dijkastra）算法实现。最后用switch选择语句选择执行浏览景点信息或查询最短路径和距离。1. 图的存储结构常用的有4种，分别是数组表示法，邻接表，十字链表，邻接多重表。在此程序中运用的是数组表示法：网的邻接矩阵：Aij= wi,j 若<vi,vj>或(vi,vj)VR 反之 #define INFINITY INT_MAX /最大值无穷大#define MAX_VERTEX_NUM 20 /最大顶点个数typedef enumDG,DN,AG,AN GraphKind; /有向图，有向网，无向图，无向网typedef struct ArcCell VRType adj; InfoType *info; /该弧相关信息的指针ArcCell,AdjMatrixmax_vertex_nummax_vertex_num;tpyedef struct VertexType vexsMAX_VERTEX_NUM; /顶点向量 AdjMatrix arcs; /邻接矩阵 int vexnum,arcnum; /图的当前顶点数和弧数 GraphKind kind; /图的种类标志MGraph;创建一个二维数组用来存储两个地点的距离，数组两个下标分别代表两个地点的位置（起点与终点），若两个地点之间没有路线可走则用无穷大表示两点之间没有路，依据此条件完成初始化平面矩阵。例子：Edge00.value=0 , Edge01.value=25 , Edge02.value=25 ; Edge03.value=90, Edge04.value=uplimit, Edge05.value=uplimit ; Edge06.value=10 , Edge07.value=uplimit , Edge08.value=uplimit; Edge09.value=uplimit, Edge010.value=uplimit;2.迪杰斯特拉(Dijkstra)算法思想:按路径长度递增的次序产生最短路径.算法的一级实现：辅助数组D0.n-1Di: 表示当前所找到的从始点v到终点vi的最短路径的长度.算法的二级实现: (用邻接矩阵arcs来存储有向图)(1) S:表示已找到从v出发的最短路径的终点的集合; Di:表示当前所找到的从v到终点vi的最短路径的长度. S=v; Di=arcsLocate-vex(G,v)i viV(2)选择vj, 使得 Dj=minDi| viV-S 令 S=Sj(3)修改从v出发到集合V-S上任顶点Vk可达的最短路径长度. if Dj+arcsj,k<Dk Dk=Dj+arcsjk(4)重复(2)、(3)共n-1次; 即可求得从v到图上其余各顶点的最短路径.以下为迪杰斯特拉算法void ShortestDist(int s) for ( int i=0;i<11;i+) /dist和path数组初始化 disti.value=Edgesi.value; /邻接矩阵第s行元素赋值到dist中 Si.value=0; /已求出最短路径的顶点集合初始化 if(i!=s && disti.value<uplimit) pathi.value=s; else pathi.value=-1; /路径存放数组初始化 Ss.value=1; /顶点s加入顶点集合 dists.value=0; /* 循环计算该场所与邻接场所之间的最短距离 */ for (i=0;i<11-1;i+) /从顶点s确定n-1条路径 float min=uplimit; int u=s; for (int j=0;j<11;j+) /选择当前不在集合S中具有最短路径的顶点u /* 如果有路径比目前的最小值还小，则替换这个最小值 */ if (!Sj.value && distj.value<min) u=j; min=distj.value; Su.value=1; /将顶点u加入集合S，表示它已在最短路径上 for (int w=0;w<11;w+) /修改 if (!Sw.value && Edgeuw.value<uplimit && distu.value+Edgeuw.value<distw.value) distw.value=distu.value+Edgeuw.value; pathw.value=u; 3.用switch语句，分支case语句出现友好界面，提示相关的输入信息，为用户的使用提供方便的输入信息，例如：switch(c) case 0: printf("女生公寓");break; case 1: printf( "图书馆");break; case 2: printf( "体育馆");break; case 3: printf( "一道门");break; case 4: printf( "一教学楼");break; case 5: printf( "男生公寓");break; case 6: printf( "食堂");break; case 7: printf( "体育场");break; case 8: printf( "五道门");break; case 9: printf( "十号教学楼");break; case 10:printf("实验楼");break;四、功能模块详细设计（一）设计功能的实现接下来根据以上搭建的程序框架完成各个模块的算法1、 首先是抽象数据类型的定义：图的抽象数据类型的 定义：ADT Mgragh数据对象V: V是具有相同特征的数据元素的 集合，称为定点集数据关系R=VRVR= <V,W> | V, WV, <V , W>表示从V到W的边 2、 基本操作：CreateUDN(&G,V,VR); / 创建图初始条件：V是图的顶点集，VR是图中边的 集合。操作结果：按V和VR的定义构造图 G。（二）主要算法设计及相关算法补充先创建图存储学校各个景点或场所，以图的顶点表示景点或场所，以边表示路径，再利用迪杰斯特拉（DijkStra）算法求出校园各个地方的最短路径，然后根据需要进行补充相关算法。void BuildMap() 生成地图，输入地图的基本信息void ShortestDist(int s) 找出场所间的最短距离void bh() 显示场所名称void Outpath(int c) 将顶点序列号转换成场所名称 void getdata(int s,int e) 输出两个场所之间的最短距离，和最短路径void info(int c) c为场所对应的数字号，输出场所的具体信息，方便用户的信息获取void num()用于显示校园导航系统的界面显示，输出10个地点的名称void main()在主程序中运用switch语句分别调用不同的子函数完成相应的操作程序的具体操作流程：1. 打开导航，在屏幕上显示出学校各个景点场所；2. 进入主菜单，用switch语句选择相应的数字，查找学校简介，路线和个景点与场所之间的距离3. 进入子菜单，选择相应的数字，查询了解景点与场所信息及景点与场所的最短距离4. 退出导航系统源程序:#include <stdio.h> #include <iostream.h> #include <malloc.h> #include <conio.h> #include <stdlib.h> #define Num 11 /最多顶点个数 #define uplimit 100000 /定义一个无穷大的值 struct inttint value;intt EdgeNumNum; /Edge为带权邻接矩阵 intt distNum; /dist为最短路程 intt pathNum; /path为最短路径上该顶点的前一顶点的顶点号 intt SNum; /S为已求得的在最短路径上的顶点号 intt DNum; /D为输出最短距离时的辅助数组 /* * 生成地图，输入地图的基本信息 * */ void BuildMap() int i,j; /* 初始化平面图矩阵 */ for ( i=0;i<11;i+) for ( j=0;j<11;j+) Edge00.value=0 , Edge01.value=25 , Edge02.value=25 ; Edge03.value=90, Edge04.value=uplimit, Edge05.value=uplimit ; Edge06.value=10 , Edge07.value=uplimit , Edge08.value=uplimit; Edge09.value=uplimit, Edge010.value=uplimit; Edge10.value=25 , Edge11.value=0 , Edge12.value=10 ; Edge13.value=32, Edge14.value=uplimit, Edge15.value=uplimit ; Edge16.value=10 , Edge17.value=uplimit , Edge18.value=21; Edge19.value=16, Edge110.value=uplimit; Edge20.value=25 , Edge21.value=10 , Edge22.value=0 ; Edge23.value=uplimit, Edge24.value=uplimit, Edge25.value=uplimit ; Edge26.value=uplimit, Edge27.value=uplimit , Edge28.value=uplimit; Edge29.value=uplimit, Edge210.value=uplimit; Edge30.value=90 , Edge31.value=32 , Edge32.value=uplimit ; Edge33.value=0 , Edge34.value=uplimit, Edge35.value=uplimit ; Edge36.value=uplimit, Edge37.value=uplimit , Edge38.value=26; Edge39.value=uplimit, Edge310.value=uplimit; Edge40.value=uplimit, Edge41.value=uplimit , Edge42.value=uplimit ; Edge43.value=uplimit, Edge44.value=0, Edge45.value=9 ; Edge46.value=uplimit, Edge47.value=uplimit , Edge48.value=uplimit; Edge49.value=uplimit, Edge410.value=60; Edge50.value=uplimit , Edge51.value=uplimit , Edge52.value=uplimit ; Edge53.value=uplimit, Edge54.value=9, Edge55.value=0 ; Edge56.value=uplimit , Edge57.value=15 , Edge58.value=50; Edge59.value=14, Edge510.value=uplimit; Edge60.value=10 , Edge61.value=10 , Edge62.value=uplimit; Edge63.value=uplimit, Edge64.value=uplimit, Edge65.value=uplimit ; Edge66.value=0 , Edge67.value=35 , Edge68.value=uplimit; Edge69.value=30, Edge610.value=uplimit; Edge70.value=uplimit , Edge71.value=uplimit , Edge72.value=uplimit ; Edge73.value=uplimit, Edge74.value=uplimit, Edge75.value=15 ; Edge76.value=35 , Edge77.value=0 , Edge78.value=uplimit; Edge79.value=13, Edge710.value=uplimit; Edge80.value=uplimit , Edge81.value=21 , Edge82.value=uplimit ; Edge83.value=26, Edge84.value=uplimit; Edge85.value=50 ; Edge86.value=uplimit , Edge87.value=uplimit , Edge88.value=0; Edge89.value=22, Edge810.value=10; Edge90.value=uplimit , Edge91.value=16 , Edge92.value=uplimit ; Edge93.value=uplimit, Edge94.value=uplimit, Edge95.value=14 ; Edge96.value=30 , Edge97.value=13 , Edge98.value=22; Edge99.value=0, Edge910.value=uplimit; Edge100.value=uplimit , Edge101.value=uplimit , Edge102.value=uplimit; Edge103.value=uplimit, Edge104.value=60; Edge105.value=uplimit ; Edge106.value=uplimit , Edge107.value=uplimit , Edge108.value=10; Edge109.value=uplimit, Edge1010.value=0; /* 找出场所间的最短距离-迪杰斯特拉算法 */ void ShortestDist(int s) for ( int i=0;i<11;i+) /dist和path数组初始化 disti.value=Edgesi.value; /邻接矩阵第s行元素赋值到dist中 Si.value=0; /已求出最短路径的顶点集合初始化 if(i!=s && disti.value<uplimit) pathi.value=s; else pathi.value=-1; /路径存放数组初始化 Ss.value=1; /顶点s加入顶点集合 dists.value=0; /* 循环计算该场所与邻接场所之间的最短距离 */ for (i=0;i<11-1;i+) /从顶点s确定n-1条路径 float min=uplimit; int u=s; for (int j=0;j<11;j+) /选择当前不在集合S中具有最短路径的顶点u /* 如果有路径比目前的最小值还小，则替换这个最小值 */ if (!Sj.value && distj.value<min) u=j; min=distj.value; Su.value=1; /将顶点u加入集合S，表示它已在最短路径上 void bh() /显示场所名称 printf("0.女生公寓 1.图书馆 2.体育馆n"); printf("3.五道门 4.一号教学楼 5.男生公寓n"); printf("6.食堂 7.体育场 8.一道门n"); printf("9.十号教学楼 10.实验楼n"); /*将顶点序列号转换成场所名称*/ void Outpath(int c) switch(c) case 0: printf("女生公寓");break; case 1: printf("图书馆");break; case 2: printf( "体育馆");break; case 3: printf("五道门");break; case 4: printf("一号教学楼");break; case 5: printf( "男生公寓");break; case 6: printf("食堂");break; case 7: printf("体育场");break; case 8: printf("一道门");break; case 9: printf( "十号教学楼");break; case 10:printf("实验楼");break; /* 输出两个场所之间的最短距离，和最短路径 */ void getdata(int s,int e) D0.value=e; int k; for (k=0;Dk.value!=s;k+) Dk+1.value=pathDk.value.value; if(Se.value) printf("nt场所%d,%d之间的最短距离是：%d",s,e,diste.value); cout<<"nt场所"<<s<<","<<e<<"之间的最短路径是:" for(; k!=-1;k-) Outpath(Dk.value); if (k!=0) cout<<" -> " else printf("nt场所%d到场所%d之间没有路径!",s,e); void Begin() int flag=1; int s,e; while ( flag ) bh(); printf("nt请输入起始场所号与目的场所号："); scanf("%d%d",&s,&e); if(s<11 && s>=0 && e<11 && e>=0) flag=0; else printf("n场所号非法，请重新输入！"); ShortestDist(s); getdata(s,e); /*显示场所的具体信息*/void info(int c) /c为场所对应的数字号 switch(c)case 0: printf("t 女生公寓，住宿条件较好。"); break; case 1: printf("t 图书馆，内部藏有丰富的书籍，供同学们学习参考，也可以自习。"); break; case 2: printf("t 体育馆，供同学们进行体育活动以及上体育课。"); break; case 3: printf("t 校门。"); break; case 4: printf("t 一号教学楼，供同学们上课和自习使用。"); break; case 5: printf("t 男生公寓，提供居住。"); break; case 6: printf("t 食堂，有两层楼,是同学们用餐的地方。"); break; case 7: printf("t 体育场，是同学们开运动会和进行体育赛事的地方。"); break; case 8: printf("t 一道门，晚上的时候这里最热闹。"); break; case 9: printf("t 十号教学楼，这栋楼供学习上课使用。"); break; case 10: printf("t 实验楼，是同学们计算机上机，各系做实验的地方。"); break;default: printf("t输入不合法，请重新输入!"); break; void num()printf("*n"); printf("* 校园导航系统 *n"); printf("*n"); printf(" 0.女生公寓n"); printf(" 1.图书馆n"); printf(" 2.体育馆n"); printf(" 3.五道门n"); printf(" 4.一号教学楼n"); printf(" 5.男生公寓n"); printf(" 6.食堂n"); printf(" 7.体育场n"); printf(" 8.一道门n"); printf(" 9.十号教学楼n"); printf(" 10.实验楼n"); void main() int c; char option; printf("*n"); printf("tt欢迎光临中北大学n"); printf("*n"); printf("-n"); printf("1.显示场所的编号n"); printf("2.查看场所的具体信息n"); printf("3.找出最短路径及计算路径长度n"); printf("4.退出n"); printf("-n"); printf("What do you want to do?请输入选择：n"); cin>>option; while (option!='0') switch(option) case '1': num(); printf("tt*n"); printf("ttt1.显示场所的编号n"); printf("ttt2.查看场所的具体信息n"); printf("ttt3.找出最短路径及计算路径长度n"); printf("ttt4.退出n"); printf("tt*n"); printf("tWhat do you want to do ?请输入选择:n"); cin>>option; system("cls"); /清屏 break; case '2': /具体信息 printf("nt请从010中选择任意字母，查看所对应场所的具体信息：n");printf("t选择11则退出n");bh(); /显示所有场所cin>>c;info(c);if(c=11) printf("tt*