校园导航课程设计.docx

数据结构课程设计课程名称数据结构课程设计题目名称校园导航系统专业班级2014级计算机科学与技术本学生姓名陈杰 张隆焱 高阳 张文利 苏磊 笪志鹏学号51402011053 51402011051 51402011034 51402011024 51402011014 51402011030 指导教师姚保峰 分工协作说明课题名称学生姓名学号所做的工作校园导航系统 陈杰 张隆焱51402011053 51402011051全程参与课程设计各项工作，包括资料查阅，算法设计、程序调试、课程设计报告撰写等。 高阳 51402011034资料查阅、算法设计。 张文利51402011024算法设计、程序调试。 苏磊51402011014算法设计、程序调试、课程设计报告排版。 笪志鹏51402011030算法设计、课程设计报告撰写、课程设计报告排版。37 蚌埠学院计算机科学与技术系课程设计任务书课 程数据结构班级14级计算机科学与技术指导教师姚保峰题 目校园导航系统完成时间2016年5月25日至2016年6月17日主要内容要求完成以下功能：设计你的学校的平面图，至少包括8个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。1）基本要求：（1）设计校园平面图，在校园景点选8个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。2） 实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。设计报告要求1封面：（格式附后）2课程设计任务书3课程设计报告：(1)项目研究背景与意义 (2)需求分析：在该部分中叙述，每个模块的功能要求； (3)概要设计：在此说明每个部分的算法设计说明（可以是描述算法的流程图）。 (4)详细设计：各个算法实现的源程序、注释及程序说明。 (5)调试分析：测试程序运行情况，遇到的问题及解决方法。(6)总结：可以包括课程设计过程中的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据结构这门课程的思考等。说明：学生完成课程设计后，提交课程设计报告及程序，要求结构完整、语句通顺、说明清楚，文字不少于5000 字，并装订成册。版面要求1 题目用黑体一号，段后距18磅（或1行）；2 一级标题用宋体三号，二级标题用宋体小三号，段前、段后距0.5行；3 正文用小四号宋体，行距为22磅；4 标题按“1”、“1.1”、“1.1.1”、“”顺序编号。上机时间安排星期周次一二三四五六日第14周-第17周数据结构课程设计A505(7-8)数据结构课程设计A505(7-8)指导时间地点上机时间，多媒体技术实验室（A505）目录1 引 言41.1 问题的提出41.2任务与功能简介41.2.1任务41.2.2功能简介42 程序运行平台53 总体设计与模块分析63.1抽象数据类型定义63.2主程序模块的整体流程63.3各模块调用和函数关系如下64 程序的主要功能实现84.1 main()主函数84.2赋值init函数84.3输出蚌埠学院校园导航平面图的map函数104.4菜单menu函数114.5输出地点信息的information函数124.7输出路径way函数134.8调用floyd和way的最短路径shortestpath算法145系统测试155.1系统运行后主界面155.2查询最短路径165.3查询地点信息17致谢19参考文献20附录211 引 言 为了加深对数据结构这一课程所学内容的进一步理解与巩固，我们这一组按课程设计要求完成了校园导航系统的设计。1.1 问题的提出 我们这次基于对导航这个热门问题的研究设计了简易校园导航系统，我们的导航平面图中至少包括8个以上校园的场所，每两个场所间可以有不同的路，且路长也可能不同，给出校园各主要建筑的名称信息及有线路联通的建筑之间的距离，利用校园导航系统计算出给定的起点到终点之间的最近距离及线路。本导航系统能够很好的向同学们提供距离与地点的详细信息。1.2任务与功能简介1.2.1任务 （1）本次作业的核心是利用弗洛伊德算法计算给定有向网中两点最短距离；给出有向网中所要求点的信息。在调试过程中，除了简单语法错误外，就是对弗洛伊德算法的理解和实现，以及菜单的设置，这是我以前没有实现过的。出于简单化，并没有对有向图中各个点进行输入，而是在程序中直接赋值。 （2）在对各个功能操作的实现上，由于有弗洛伊德算法时间复杂度大多数是O(n3)，空间上增加了二维数组，空间复杂度为O(n+s)。1.2.2功能简介程序所能达到的功能： (1) map输出蚌埠学院导航平面图。(2) init()按相应编号输入各个节点内容，对相应路径赋值的函数。(3) menu()菜单函数(4) information()输出简介的函数(5) way()最短路径的输出函数(6) shortestpath()调用弗洛伊德和最短路径输出的函数(7) main()主函数2 程序运行平台 本次课程设计我们采用的运行平台是 visual C+6.0,该平台是由Visual C+6.0由Microsoft开发, 它不仅是一个C+编译器，而且是一个基于Windows操作系统的可视化集成开发环境（integrated development environment，IDE）。Visual C+6.0由许多组件组成，包括编辑器、调试器以及程序向导AppWizard、类向导Class Wizard等开发工具。Visual C+已成为专业程序员进行软件开发的首选工具。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用有很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。Visual C+6.0以拥有“语法高亮”，自动编译功能以及高级除错功能而著称。比如，它允许用户进行远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及创建预编译头文件(stdafx.h)、最小重建功能及累加连结(link)著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件计划上尤其显著。3 总体设计与模块分析3.1抽象数据类型定义有向网节点结构体类型typedef structchar name10 ;int number; char introduce100;vertex;3.2主程序模块的整体流程1、进入主函数，调用init，map和menu函数。2、选择“s”，调用shortestpath函数，并同时调用floyd和way函数。并返回调用menu函数。3、选择“i”，调用information函数。并返回调用menu函数。4、选择“e”，退出。3.3各模块调用和函数关系如下4 程序的主要功能实现4.1 main()主函数是程序执行的入口，主函数用于使用者便于使用者选择使用导航系统的功能int main()/*主函数*/char i;printf(ttt欢迎使用蚌埠学院校园导航系统nn);init();map();/*输出地图，提示使用者*/while (1)i=menu();switch(i)case s:shortestpath();break;case i:information();break;case e:printf(nnntttt谢谢使用!n);return 0;default :printf(输入错误！n);break; 4.2赋值init函数init函数主要用于初始化校园平面图中的地点信息void init()/初始化信息函数int i,j;/对平面图中的各个地点信息进行输入，运用strcpy函数ver1.number =1;strcpy(,重行楼);strcpy(roduce,教师办公场所n);ver2.number =2;strcpy(,B教学楼);strcpy(roduce,日常上课，学习知识的地方n);ver3.number =3;strcpy(,北操场);strcpy(roduce,假草，球门，尽情施展脚法的好地方n);ver4.number =4;strcpy(,西大门);strcpy(roduce,学生外出的常用通道n);ver5.number =5;strcpy(,图书馆);strcpy(roduce,查阅资料，努力学习的理想之所n);ver6.number =6;strcpy(,第一食堂);strcpy(roduce,校内最好的食堂n);ver7.number =7;strcpy(,行政楼);strcpy(roduce,行政机构n);ver8.number =8;strcpy(,南操场);strcpy(roduce,以男生为主的真草操场n);ver9.number =9;strcpy(,学生公寓);strcpy(roduce,学生休息生活场所n);ver10.number =10;strcpy(,体育馆);strcpy(roduce,学校的室内体育馆，遮风挡雨的理想运动场所n);ver11.number =11;strcpy(,高知公寓);strcpy(roduce,校职工的住宿地n); for(i=1;i=Num;i+)/*对存储距离的距离矩阵取值进行初始化，全定义为最大*/ for(j=1;j=Num;j+) edgeij=Maxedge; for(i=1,j=1;i=Num,j=Num;i+,j+)/对存储距离的矩阵的取值进行正确赋值，由于我校均来回可达，故对路径正反同时赋值edgeij=0;edge12=edge21=90;edge14=edge41=110;edge23=edge32=80;edge25=edge52=150;edge36=edge63=130;edge45=edge54=200;edge47=edge74=70;edge56=edge65=160;edge58=edge85=300;edge69=edge96=60;edge78=edge87=80;edge710=edge107=120;edge89=edge98=50;edge810=edge108=30;edge911=edge119=40;edge1011=edge1110=30; 4.3输出蚌埠学院校园导航平面图的map函数map函数用于显示蚌埠学院校园导航平面图，给使用程序者以直观认识void map()printf(tt蚌埠学院校园导航平面图(括号内为相对应的数字编号)n);printf(nn);printf(t 重行楼(1)B教学楼(2)北操场(3)n);printf(t | | |n);printf(t 西大门(4)一图书馆(5)第一食堂(6)n);printf(t | | |n);printf(t 行政楼(7) 南操场(8)学生公寓(9) n);printf(t | | | n);printf(t - 体育馆(10)高知公寓(11)n);4.4菜单menu函数char menu()/*菜单函数*/char i;printf(输入“s”以查询最短路径n);printf(输入“i”以查询信息n);printf(输入“e”以退出程序n);printf(请输入对应的英文小写字母，谢谢：nt);scanf(%s,&i);return i; 4.5输出地点信息的information函数当使用者选择显示地点信息功能时将调用此函数实现该功能void information()/*输出简介函数*/int i;while(1) printf(请输入查询地点的编号：nt); scanf(%d,&i);if(i=1)printf(n名称：%sn#简介：%sn,,roduce);return;elseprintf(输入有误！);return; 4.6最短路径floyd函数floyd算法说明：对于从vi到vj的弧，进行n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，则比较vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比较后，最后求得的必是从顶点vi到顶点vj的最短路径。void floyd()/*弗洛伊德算法*/int pNumNumNum;int i=1,j=1,k=1,l=1,m=1;for(i=1;i=Num;i+)for(j=1;j=Num;j+)shortestij=edgeij;pathij=0;for(k=1;k=Num;k+)for(i=1;i=Num;i+)for(j=1;j(shortestik+shortestkj)shortestij=(shortestik+shortestkj);pathij=pathji=k; 4.7输出路径way函数way函数用于输出最短路径函数void way(int i,int j)/*最短路径的输出*/int k=0,a=i,b=j;if(shortestij!=Maxedge)printf(n从%s到%s的最短路径为:n,,);printf(%s,);while(pathij!=0)k=pathij;while(pathik!=0)k=pathik;printf(-到-%s,);i=k;printf(-到-%s;n, );printf(n最短距离为：%d米。n,shortestab);printf(n数据均为测试数据，与实际有误差，敬请谅解.nn);elseprintf(从%s不能到达%s。, , ); 4.8调用floyd和way的最短路径shortestpath算法寻找最短路径void shortestpath()int i=0,j=0;while(1)printf(请输入要查询的两点的编号：（以空格间隔）);scanf(%d%d,&i,&j);if(i0&j0)floyd();way(i,j);return; 5系统测试5.1系统运行后主界面在visual中运行系统源代码5.2查询最短路径输入s ，查询重行楼到第一食堂的距离再次输入s ，查询重行楼到图书馆的距离5.3查询地点信息输入i，查询图书馆（5）的信息再次输入i，查寻教学楼（2）的信息6结论 使我们加深对数据结构这一课程所学内容的进一步理解与巩固 通过完成课程设计，逐渐培养自己的编程能力和团队合作能力； 培养给出题目后，构建框架，用计算机解决的能力； 通过调试程序积累调试C程序设计的经验；致谢 这次数据结构的课程设计是基于c语言面向过程设计语言设计的校园导航系统，让我们对软件编程语言学习也有了更深刻的认识，只有打下良好的基础才会学以致用，才会发挥出作用。在本次课程设计过程中遇到了许多困难，前期做出的系统效果不符合要求，用c语言编写的程序也出现问题，令人头疼不已，后来在经过查找相关资料，在老师同学的帮助下，终于改正了错误。完成这次课程设计任务，让我深刻的认识是程序设计对于我们专业的重要性，我们对程序设计语言的学习还是不够精通，有了这次综合实训的体会，我一定会利用课余时间更深的了解程序设计语言知识。认识来源于实践，实践是认识的动力和最终目的，实践是检验真理的唯一标准，所以这个课程设计对我们的作用是非常大的。经过近一个月的制作，过程曲折可谓一波三折，点点滴滴无不令我回味无穷。 首先，对待任何工作，都要全力以赴，不能畏首畏尾。通过综合实训，我深有体会。然更重要的是，在责任心的驱使下，如何采用何种方法更省时省力，解决问题的方案很多，永远坚信“方向总比努力重要”，首先分析课题任务本身，就拿课程设计来说，课题有了，关键是往哪个方向着手。怎样去查找相关资料等等，寻找突破口充分的解决好问题。 没有经过实践永远都不会知道结果是怎样的，当实践的结果证实了你要得到的结论时那种心情真是不知如何表达。通过本次课程设计，我真正感受到了那种快乐和喜悦！并且懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会服务，从而提高自己的实际动手能力和独立思考的能力。 在此我非常要感谢的是我的指导老师姚保峰老师，感谢姚老师的细心认真的指导，教会我许多原来不知道的知识。这次课程设计能够顺利的完成，当然有我个人的努力，但同时也离不开指导老师的答疑解惑和同学的互帮互助。参考文献1美 Gary Bronson 著，刘勇译Programming Development and Design Using C+, Second Edition（C+程序开发与设计，第2版）北京：人民邮电出版社，20022王萍C+面向对象程序设计北京：清华大学出版社20023罗建军等C+程序设计教程（第2版）北京：高等教育出版社，2004 4谭浩强C+程序设计北京：清华大学出版社20045黄维通Visual C+面向对象与可视化程序设计（第2版）北京：清华大学出版社，20076张基温C+程序设计基础北京：高等教育出版社，20017刁成嘉面向对象C+程序设计北京：机械工业出版社，20048郑莉等C+语言程序设计（第2版）北京：清华大学出版社，2001附录源程序代码及必要注释。#include#include#define Num 11/*测试使用十一个地点，直接定义*/#define Maxedge 32760/*最大距离*/typedef struct/*定义对各个地点信息存储的结构体类型*/char name10 ;int number; char introduce100;vertex;vertex verNum;/*定义结构体数组*/int edgeNumNum;int shortestNumNum; int pathNumNum; void map()/*蚌埠学院校园导航平面图，给使用程序者以直观认识*/printf(tt蚌埠学院校园导航平面图(括号内为相对应的数字编号)n);printf(nn);printf(t 重行楼(1)B教学楼(2)北操场(3)n);printf(t | | |n);printf(t 西大门(4)一图书馆(5)第一食堂(6)n);printf(t | | |n);printf(t 行政楼(7) 南操场(8)学生公寓(9) n);printf(t | | | n);printf(t - 体育馆(10)高知公寓(11)n);void init()/初始化信息函数int i,j;/对平面图中的各个地点信息进行输入，运用strcpy函数ver1.number =1;strcpy(,重行楼);strcpy(roduce,办公场所n);ver2.number =2;strcpy(,B教学楼);strcpy(roduce,日常上课，学习知识的地方n);ver3.number =3;strcpy(,北操场);strcpy(roduce,假草，球门，尽情施展脚法的好地方n);ver4.number =4;strcpy(,西大门);strcpy(roduce,学生外出的常用通道n);ver5.number =5;strcpy(,图书馆);strcpy(roduce,查阅资料，努力学习的理想之所n);ver6.number =6;strcpy(,第一食堂);strcpy(roduce,校内最好的食堂n);ver7.number =7;strcpy(,行政楼);strcpy(roduce,行政机构n);ver8.number =8;strcpy(,南操场);strcpy(roduce,以男生为主的真草操场n);ver9.number =9;strcpy(,学生公寓);strcpy(roduce,学生休息生活场所n);ver10.number =10;strcpy(,体育馆);strcpy(roduce,学校的室内体育馆，遮风挡雨的理想运动场所n);ver11.number =11;strcpy(,高知公寓);strcpy(roduce,校职工的住宿地n); for(i=1;i=Num;i+)/*对存储距离的距离矩阵取值进行初始化，全定义为最大*/ for(j=1;j=Num;j+) edgeij=Maxedge; for(i=1,j=1;i=Num,j=Num;i+,j+)/对存储距离的矩阵的取值进行正确赋值，由于我校均来回可达，故对路径正反同时赋值edgeij=0;edge12=edge21=90;edge14=edge41=110;edge23=edge32=80;edge25=edge52=150;edge36=edge63=130;edge45=edge54=200;edge47=edge74=70;edge56=edge65=160;edge58=edge85=300;edge69=edge96=60;edge78=edge87=80;edge710=edge107=120;edge89=edge98=50;edge810=edge108=30;edge911=edge119=40;edge1011=edge1110=30;char menu()/*菜单函数*/char i;printf(输入“s”以查询最短路径n);printf(输入“i”以查询信息n);printf(输入“e”以退出程序n);printf(请输入对应的英文小写字母，谢谢：nt);scanf(%s,&i);return i;void information()/*输出简介函数*/int i;while(1) printf(请输入查询地