校园导航课程设计

..-..-可修遍-数据构造课程设计课程名称数据构造课程设计题目名称校园导航系统专业班级2014级计算机科学与技术本学生杰隆焱高阳文利磊笪志鹏学号指导教师保峰...-可修遍-分工协作说明课题名称学生学号所做的工作校园导航系统杰隆焱全程参与课程设计各项工作，包括资料查阅，算法设计、程序调试、课程设计报告撰写等。高阳资料查阅、算法设计。文利算法设计、程序调试。磊算法设计、程序调试、课程设计报告排版。笪志鹏算法设计、课程设计报告撰写、课程设计报告排版。..学院计算机科学与技术系课程设计任务书课程数据构造班级14级计算机科学与技术指导教师保峰题目完成时间主要容要求完成以下功能：设计你的学校的平面图，至少包括8个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最正确路径〔最短路径〕。1〕根本要求：〔1〕设计校园平面图，在校园景点选8个左右景点。以图中顶点表示校园各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。〔2〕为来访客人提供图中任意景点相关信息的查询。〔3〕为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。2〕实现提示：一般情况下，校园的道路是双向通行的，可设计校园平面图是一个无向网。顶点和边均含有相关信息。设计报告要求1．封面：〔格式附后〕2．课程设计任务书3．课程设计报告：(1)工程研究背景与意义(2)需求分析：在该局部中表达，每个模块的功能要求；(3)概要设计：在此说明每个局部的算法设计说明〔可以是描述算法的流程图〕。(4)详细设计：各个算法实现的源程序、注释及程序说明。(5)调试分析：测试程序运行情况，遇到的问题及解决方法。(6)总结：可以包括课程设计过程中的收获、遇到问题、遇到问题解决问题过程的思考、程序调试能力的思考、对数据构造这门课程的思考等。说明：学生完成课程设计后，提交课程设计报告及程序，要求构造完整、语句通顺、说明清楚，文字不少于5000字，并装订成册。版面要求题目用黑体一号，段后距18磅〔或1行〕；一级标题用宋体三号，二级标题用宋体小三号，段前、段后距0.5行；正文用小四号宋体，行距为22磅；标题按"1〞、"1.1〞、"1.1.1〞、"⑴〞顺序编号。上机时间安排星期周次一二三四五六日第14周-第17周数据构造课程设计A505(7--8)数据构造课程设计A505(7--8)指导时间地点上机时间，多媒体技术实验室〔A505〕目录TOC\o"1-3"\h\u1引言11.1问题的提出11.2任务与功能简介11.2.1任务11.2.2功能简介12程序运行平台13总体设计与模块分析13.1抽象数据类型定义13.2主程序模块的整体流程13.3各模块调用和函数关系如下14程序的主要功能实现14.1main()——主函数14.2赋值init函数14.3输出学院校园导航平面图的map函数14.4菜单menu函数14.5输出地点信息的information函数14.7输出路径way函数14.8调用floyd和way的最短路径shortestpath算法15系统测试15.1系统运行后主界面15.2查询最短路径15.3查询地点信息1致1参考文献1附录1..1引言为了加深对"数据构造"这一课程所学容的进一步理解与稳固，我们这一组按课程设计要求完成了校园导航系统的设计。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程序运行平台本次课程设计我们采用的运行平台是visualC++6.0,该平台是由VisualC++6.0由Microsoft开发,它不仅是一个C++\t"baike.so./doc/_blank"编译器，而且是一个基于Windows操作系统的可视化集成开发环境〔integrateddevelopmentenvironment，IDE〕。VisualC++6.0由许多组件组成，包括\t"baike.so./doc/_blank"编辑器、调试器以及程序向导AppWizard、类向导ClassWizard等开发工具。VisualC++已成为专业程序员进展软件开发的首选工具。虽然微软公司推出了VisualC++.NET(VisualC++7.0)，但它的应用有很大的局限性，只适用于Windows2000,WindowsXP和WindowsNT4.0。所以实际中，更多的是以VisualC++6.0为平台。VisualC++6.0以拥有"语法高亮〞，自动编译功能以及高级除错功能而著称。比方，它允许用户进展远程调试，单步执行等。还有允许用户在调试期间重新编译被修改的代码，而不必重新启动正在调试的程序。其编译及创立预编译头文件(stdafx.h)、最小重建功能及累加连结(link)著称。这些特征明显缩短程序编辑、编译及连结的时间花费，在大型软件方案上尤其显著。3总体设计与模块分析3.1抽象数据类型定义有向网节点构造体类型typedefstruct{charname[10];intnumber;charintroduce[100];}vertex;3.2主程序模块的整体流程1、进入主函数，调用init，map和menu函数。2、选择"s〞，调用shortestpath函数，并同时调用floyd和way函数。并返回调用menu函数。3、选择"i〞，调用information函数。并返回调用menu函数。4、选择"e〞，退出。3.3各模块调用和函数关系如下主函数主函数shortestpathExitinformationseimainmaininitmapmenuexitinformationshortestpathfloydwaySei4程序的主要功能实现4.1main()——主函数是程序执行的入口，主函数用于使用者便于使用者选择使用导航系统的功能intmain()/*主函数*/{chari;printf("\t\t\t欢送使用学院校园导航系统\n\n");init();map();/*输出地图，提示使用者*/while(1) {i=menu();switch(i) {case's':shortestpath();break;case'i':information();break;case'e':printf("\n\n\n\t\t\t\t使用!\n");return0;default:printf("输入错误！\n");break; } }}4.2赋值init函数init函数主要用于初始化校园平面图中的地点信息voidinit()//初始化信息函数{inti,j;//对平面图中的各个地点信息进展输入，运用strcpy函数ver[1].number=1;strcpy(ver[1].name,"重行楼");strcpy(ver[1].introduce,"教师办公场所\n");ver[2].number=2;strcpy(ver[2].name,"B教学楼");strcpy(ver[2].introduce,"日常上课，学习知识的地方\n");ver[3].number=3;strcpy(ver[3].name,"北操场");strcpy(ver[3].introduce,"假草，球门，尽情施展脚法的好地方\n");ver[4].number=4;strcpy(ver[4].name,"西大门");strcpy(ver[4].introduce,"学生外出的常用通道\n");ver[5].number=5;strcpy(ver[5].name,"图书馆");strcpy(ver[5].introduce,"查阅资料，努力学习的理想之所\n");ver[6].number=6;strcpy(ver[6].name,"第一食堂");strcpy(ver[6].introduce,"校最好的食堂\n");ver[7].number=7;strcpy(ver[7].name,"行政楼");strcpy(ver[7].introduce,"行政机构\n");ver[8].number=8;strcpy(ver[8].name,"南操场");strcpy(ver[8].introduce,"以男生为主的真草操场\n");ver[9].number=9;strcpy(ver[9].name,"学生公寓");strcpy(ver[9].introduce,"学生休息生活场所\n");ver[10].number=10;strcpy(ver[10].name,"体育馆");strcpy(ver[10].introduce,"学校的室体育馆，遮风挡雨的理想运动场所\n");ver[11].number=11;strcpy(ver[11].name,"高知公寓");strcpy(ver[11].introduce,"校职工的住宿地\n");for(i=1;i<=Num;i++)/*对存储距离的距离矩阵取值进展初始化，全定义为最大*/{for(j=1;j<=Num;j++){edge[i][j]=Maxedge;}}for(i=1,j=1;i<=Num,j<=Num;i++,j++)//对存储距离的矩阵的取值进展正确赋值，由于我校均来回可达，故对路径正反同时赋值 {edge[i][j]=0; }edge[1][2]=edge[2][1]=90;edge[1][4]=edge[4][1]=110;edge[2][3]=edge[3][2]=80;edge[2][5]=edge[5][2]=150;edge[3][6]=edge[6][3]=130;edge[4][5]=edge[5][4]=200;edge[4][7]=edge[7][4]=70;edge[5][6]=edge[6][5]=160;edge[5][8]=edge[8][5]=300;edge[6][9]=edge[9][6]=60;edge[7][8]=edge[8][7]=80;edge[7][10]=edge[10][7]=120;edge[8][9]=edge[9][8]=50;edge[8][10]=edge[10][8]=30;edge[9][11]=edge[11][9]=40;edge[10][11]=edge[11][10]=30; }4.3输出学院校园导航平面图的map函数map函数用于显示学院校园导航平面图，给使用程序者以直观认识voidmap(){printf("\t\t学院校园导航平面图(括号为相对应的数字编号)\n");printf("\n\n");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函数charmenu()/*菜单函数*/{chari;printf("输入"s〞以查询最短路径\n");printf("输入"i〞以查询信息\n");printf("输入"e〞以退出程序\n");printf("请输入对应的英文小写字母，：\n\t");scanf("%s",&i);returni;}4.5输出地点信息的information函数当使用者选择显示地点信息功能时将调用此函数实现该功能voidinformation()/*输出简介函数*/{inti;while(1) {printf("请输入查询地点的编号：\n\t"); scanf("%d",&i);if(i<=Num&&i>=1) {printf("\n名称：%s\n#简介：%s\n",ver[i].name,ver[i].introduce);return; }else {printf("输入有误！");return;}}}4.6最短路径floyd函数floyd算法说明：对于从vi到vj的弧，进展n次试探：首先考虑路径vi,v0,vj是否存在，如果存在，那么比拟vi,vj和vi,v0,vj的路径长度，取较短者为从vi到vj的中间顶点的序号不大于0的最短路径。在路径上再增加一个顶点v1，依此类推，在经过n次比拟后，最后求得的必是从顶点vi到顶点vj的最短路径。voidfloyd()/*弗洛伊德算法*/{intp[Num][Num][Num];inti=1,j=1,k=1,l=1,m=1;for(i=1;i<=Num;i++) {for(j=1;j<=Num;j++) {shortest[i][j]=edge[i][j];path[i][j]=0; } }for(k=1;k<=Num;k++) {for(i=1;i<=Num;i++) {for(j=1;j<=Num;j++) {if(shortest[i][j]>(shortest[i][k]+shortest[k][j])) {shortest[i][j]=(shortest[i][k]+shortest[k][j]);path[i][j]=path[j][i]=k;}}}}}4.7输出路径way函数way函数用于输出最短路径函数voidway(inti,intj)/*最短路径的输出*/{intk=0,a=i,b=j;if(shortest[i][j]!=Maxedge) {printf("\n从%s到%s的最短路径为:\n",ver[i].name,ver[j].name);printf("%s",ver[i].name);while(path[i][j]!=0) {k=path[i][j];while(path[i][k]!=0) {k=path[i][k]; }printf("-到-%s",ver[k].name);i=k; }printf("-到-%s;\n",ver[j].name);printf("\n最短距离为：%d米。\n",shortest[a][b]);printf("\n数据均为测试数据，与实际有误差，敬请谅解.\n\n"); }elseprintf("从%s不能到达%s。",ver[i].name,ver[j].name);}4.8调用floyd和way的最短路径shortestpath算法寻找最短路径voidshortestpath(){inti=0,j=0;while(1) {printf("请输入要查询的两点的编号：〔以空格间隔〕");scanf("%d%d",&i,&j);if(i<=Num&&i>0&&j<=Num&&j>0) {floyd();way(i,j);return; }}}5系统测试5.1系统运行后主界面在visual中运行系统源代码5.2查询最短路径输入s，查询重行楼到第一食堂的距离再次输入s，查询重行楼到图书馆的距离5.3查询地点信息输入i，查询图书馆〔5〕的信息再次输入i，查寻教学楼〔2〕的信息6结论使我们加深对"数据构造"这一课程所学容的进一步理解与稳固通过完成课程设计，逐渐培养自己的编程能力和团队合作能力；培养给出题目后，构建框架，用计算机解决的能力；通过调试程序积累调试C程序设计的经历；致这次数据构造的课程设计是基于c语言面向过程设计语言设计的校园导航系统，让我们对软件编程语言学习也有了更深刻的认识，只有打下良好的根底才会学以致用，才会发挥出作用。在本次课程设计过程中遇到了许多困难，前期做出的系统效果不符合要求，用c语言编写的程序也出现问题，令人头疼不已，后来在经过查找相关资料，在教师同学的帮助下，终于改正了错误。完成这次课程设计任务，让我深刻的认识是程序设计对于我们专业的重要性，我们对程序设计语言的学习还是不够精通，有了这次综合实训的体会，我一定会利用课余时间更深的了解程序设计语言知识。认识来源于实践，实践是认识的动力和最终目的，实践是检验真理的唯一标准，所以这个课程设计对我们的作用是非常大的。经过近一个月的制作，过程曲折可谓一波三折，点点滴滴无不令我回味无穷。首先，对待任何工作，都要全力以赴，不能畏首畏尾。通过综合实训，我深有体会。然更重要的是，在责任心的驱使下，如何采用何种方法更省时省力，解决问题的方案很多，永远坚信"方向总比努力重要〞，首先分析课题任务本身，就拿课程设计来说，课题有了，关键是往哪个方向着手。怎样去查找相关资料等等，寻找突破口充分的解决好问题。没有经过实践永远都不会知道结果是怎样的，当实践的结果证实了你要得到的结论时那种心情真是不知如何表达。。通过本次课程设计，我真正感受到了那种快乐和喜悦！并且懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正为社会效劳，从而提高自己的实际动手能力和独立思考的能力。在此我非常要感的是我的指导教师保峰教师，感教师的细心认真的指导，教会我许多原来不知道的知识。这次课程设计能够顺利的完成，当然有我个人的努力，但同时也离不开指导教师的答疑解惑和同学的互帮互助。参考文献1．[美]GaryBronson著，勇译．ProgrammingDevelopmentandDesignUsingC++,SecondEdition〔C++程序开发与设计，第2版〕．：人民邮电，20022．王萍．C++面向对象程序设计．：清华大学．20023．罗建军等．C++程序设计教程〔第2版〕．：高等教育，20044．谭浩强．C++程序设计．：清华大学．20045．黄维通．VisualC++面向对象与可视化程序设计〔第2版〕．：清华大学，20076．基温．C++程序设计根底．：高等教育，20017．刁成嘉．面向对象C++程序设计．：机械工业，20048．莉等．C++语言程序设计〔第2版〕．：清华大学，2001附录源程序代码及必要注释。#include<stdio.h>#include<string.h>#defineNum11/*测试使用十一个地点，直接定义*/#defineMaxedge32760/*最大距离*/typedefstruct/*定义对各个地点信息存储的构造体类型*/{charname[10];intnumber;charintroduce[100];}vertex;vertexver[Num];/*定义构造体数组*/intedge[Num][Num];intshortest[Num][Num];intpath[Num][Num];voidmap()/*学院校园导航平面图，给使用程序者以直观认识*/{printf("\t\t学院校园导航平面图(括号为相对应的数字编号)\n");printf("\n\n");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");}voidinit()//初始化信息函数{inti,j;//对平面图中的各个地点信息进展输入，运用strcpy函数ver[1].number=1;strcpy(ver[1].name,"重行楼");strcpy(ver[1].introduce,"办公场所\n");ver[2].number=2;strcpy(ver[2].name,"B教学楼");strcpy(ver[2].introduce,"日常上课，学习知识的地方\n");ver[3].number=3;strcpy(ver[3].name,"北操场");strcpy(ver[3].introduce,"假草，球门，尽情施展脚法的好地方\n");ver[4].number=4;strcpy(ver[4].name,"西大门");strcpy(ver[4].introduce,"学生外出的常用通道\n");ver[5].number=5;strcpy(ver[5].name,"图书馆");strcpy(ver[5].introduce,"查阅资料，努力学习的理想之所\n");ver[6].number=6;strcpy(ver[6].name,"第一食堂");strcpy(ver[6].introduce,"校最好的食堂\n");ver[7].number=7;strcpy(ver[7].name,"行政楼");strcpy(ver[7].introduce,"行政机构\n");ver[8].number=8;strcpy(ver[8].name,"南操场");strcpy(ver[8].introduce,"以男生为主的真草操场\n");ver[9].number=9;strcpy(ver[9].name,"学生公寓");strcpy(ver[9].introduce,"学生休息生活场所\n");ver[10].number=10;strcpy(ver[10].name,"体育馆");strcpy(ver[10].introduce,"学校的室体育馆，遮风挡雨的理想运动场所\n");ver[11].number=11;strcpy(ver[11].name,"高知公寓");strcpy(ver[11].introduce,"校职工的住宿地\n");for(i=1;i<=Num;i++)/*对存储距离的距离矩阵取值进展初始化，全定义为最大*/{for(j=1;j<=Num;j++){edge[i][j]=Maxedge;}}for(i=1,j=1;i<=Num,j<=Num;i++,j++)//对存储距离的矩阵的取值进展正确赋值，由于我校均来回可达，故对路径正反同时赋值 {edge[i][j]=0; }edge[1][2]=edge[2][1]=90;edge[1][4]=edge[4][1]=110;edge[2][3]=edge[3][2]=80;edge[2][5]=edge[5][2]=150;edge[3][6]=edge[6][3]=130;edge[4][5]=edge[5][4]=200;edge[4][7]=edge[7][4]=70;edge[5][6]=edge[6][5]=160;edge[5][8]=edge[8][5]=300;edge[6][9]=edge[9][6]=60;edge[7][8]=edge[8][7]=80;edge[7][10]=edge[10][7]=120;edge[8][9]=edge[9][8]=50;edge[8][10]=edge[10][8]=30;edge[9][11]=edge[11][9]=40;edge[10][11]=edge[11][10]=30;}charmenu()/*菜单函数*/{chari;printf("输入"s〞以查询最短路径\n");printf("输入"i〞以查询信息\n");printf("输入"e〞以退出程序\n");printf("请输入对应的英文小写字母，：\n\t");scanf("%s",&i);returni;}voidinformation()/*输出简介函数*/{inti;while(1) {printf("请输入查询地点的编号：\n\t"); scanf("%d",&i);if(i<=Num&&i>=1) {printf("\n名称：%s\n#简介：%s\n",ver[i].name,ver[i].introd