校园导航系统数据结构课程设计.docx

软 件 学 院课程设计报告书课程名称 数据结构 设计题目 校园导航系统 专业班级 软件1001班 学 号 09 姓 名 李名扬 指导教师 徐娇月 2012 年 1 月目录1.设计时间 22.设计目的 23.设计任务 24.设计内容 2需求分析 2整体设计 3详细设计 4测试与分析12测试12分析13 附录145 总结与展望 206.参考文献 217.成绩评定 211 设计时间2012/01/03至2012/01/062 设计目的1加深对数据结构这一课程所学内容的进一步理解与巩固2通过完成课程设计，逐渐培养自己的编程能力；3培养给出题目后，构建框架，用计算机解决的能力；4通过调试程序积累调试C程序设计的经验； 3设计任务给出校园各主要建筑的名称信息及有线路联通的建筑之间的距离，利用校园导航系统计算出给定的起点到终点之间的最近距离及线路。4 设计内容 需求分析 1程序所能达到的功能： (1) map输出辽宁工程技术大学平面图。(2) init()按相应编号输入各个节点内容，对相应路径赋值的函数。(3) menu()菜单函数(4) information()输出简介的函数(5) way()最短路径的输出函数(6) shortestpath()调用弗洛伊德和最短路径输出的函数(7) main()主函数2输入的形式和输入值的范围：输入数字和字母： 字母：以s查询最短路径；以i查询信息；以e退出程序。 数字：从1到11输入。3输出的形式：从A到B得最短路径为： A-到-C-到-D-到-B 最短距离为：xxx米。4测试数据包括在正确的输入及输出结果及含有错误的输入及输出结果：当输入为：s 1 11 输出为：从浴池到静远楼的最短路径为： 浴池-到-B寝室楼-到-一食堂-到-综合楼-到-静远楼 最短距离为：180米。 数据均为测试数据，与实际有误差，敬请谅解。当输入为：i 1 输出为：名称：浴池 简介：洗澡，吃饭，超市，一应俱全当输入为：e 输出为：谢谢使用！当输入为：i 13 输出为：输入有误！请输入查询地点的编号： 总体设计1抽象数据类型定义有向网节点结构体类型typedef structchar name10 ;int number; char introduce100;vertex;2主程序模块的整体流程 1、进入主函数，调用init，map和menu函数。2、选择“s”，调用shortestpath函数，并同时调用floyd和way函数。并返回调用menu函数。3、选择“i”，调用information函数。并返回调用menu函数。4、选择“e”，退出。3.各模块调用关系如下：主函数shortestpathExitinformationsei详细设计1.有向网节点结构体类型定义：typedef structchar name10 ;int number; char introduce100;vertex;2. 主程序和其它主要函数伪码算法1）主程序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;2）赋值init函数void init()int i,j;/*从41到73行，对平面图中的各个地点信息进行输入，运用strcpy函数*/ver1.number =1;strcpy(ver1.name,"浴池");strcpy(ver1.introduce,"洗澡，吃饭，超市，一应具全n");ver2.number =2;strcpy(ver2.name,"老操场");strcpy(ver2.introduce,"怀念一下学长们的艰苦生活n");ver3.number =3;strcpy(ver3.name,"新体育场");strcpy(ver3.introduce,"假草，球门，尽情施展脚法的好地方n");ver4.number =4;strcpy(ver4.name,"B寝室楼");strcpy(ver4.introduce,"女寝，不解释n");ver5.number =5;strcpy(ver5.name,"一食堂");strcpy(ver5.introduce,"饭呐，不好吃n");ver6.number =6;strcpy(ver6.name,"综合楼");strcpy(ver6.introduce,"超市，有日用品，各种食品，还有各种营业厅，眼镜店，书店，水果店n");ver7.number =7;strcpy(ver7.name,"南大门");strcpy(ver7.introduce,"学校最宏伟的建筑，校友捐赠n");ver8.number =8;strcpy(ver8.name,"A寝室楼");strcpy(ver8.introduce,"男寝，我的家n");ver9.number =9;strcpy(ver9.name,"尔雅");strcpy(ver9.introduce,"教学楼，有我最爱的411，是基础教学部老师大展身手的地方n");ver10.number =10;strcpy(ver10.name,"耘慧楼");strcpy(ver10.introduce,"教学楼，各种上机实验的地方n");ver11.number =11;strcpy(ver11.name,"静远楼");strcpy(ver11.introduce,"教学楼，内涵图书馆，足够惊喜n"); for(i=1;i<=Num;i+)/*对存储距离的距离矩阵取值进行初始化，全定义为最大*/ for(j=1;j<=Num;j+) edgeij=Maxedge; for(i=1;i<=Num;i+)/*对存储距离的矩阵的取值进行正确赋值，由于我校均来回可达，顾对路径正反同时赋值*/edgeii=0;edge12=edge21=20;edge23=edge32=50;edge25=edge52=50;edge34=edge43=100;edge36=edge63=300;edge14=edge41=20;edge45=edge54=30;edge56=edge65=10;edge67=edge76=200;edge611=edge116=120;edge48=edge84=10;edge89=edge98=250;edge910=edge109=50;edge1011=edge1110=50;edge711=edge117=100;3）输出辽宁工程技术大学平面图的map函数void map()/*辽宁工程技术大学平面图，给使用程序者以直观认识*/printf("tt辽宁工程技术大学大学平面图(括号内为相对应的数字编号)nn");printf(" 浴池(1)老体育场(2)新体育场(3)n");printf(" | | | |n");printf(" | | | |n");printf(" B寝室楼(4)一食堂(5)综合楼(6)南大门(7)n");printf(" | |n");printf(" A寝室楼(8) |n");printf(" | |n");printf(" 尔雅楼(9)耘慧楼(10)静远楼(11)nn");4）菜单menu函数char menu()/*菜单函数*/char i;printf("输入“s”以查询最短路径n");printf("输入“i”以查询信息n");printf("输入“e”以退出程序n");printf("请输入对应的英文小写字母，谢谢：nt");scanf("%s",&i);return i;5）输出地点信息的information函数void information()/*输出简介函数*/int i;while(1) printf("请输入查询地点的编号：nt"); scanf("%d",&i);if(i<=Num&&i>=1)printf("n名称：%sn#简介：%sn",veri.name,veri.introduce);return;elseprintf("输入有误！");6）最短路径floyd函数void floyd()/*弗洛伊德算法*/int i=1,j=1,k=1,l=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<=Num;j+)if(shortestij>(shortestik+shortestkj)shortestij=(shortestik+shortestkj);pathij=pathji=k;7）输出路径way算法void way(int i,int j)/*最短路径的输出*/int k=0,a=i,b=j;if(shortestij!=Maxedge)printf("n%从%s到%s的最短路径为:n",veri.name,verj.name);printf("%s",veri.name);while(pathij!=0)k=pathij;while(pathik!=0)k=pathik;printf("-到-%s",verk.name);i=k;printf("-到-%s;n",verj.name );printf("n最短距离为：%d米。n",shortestab);printf("n数据均为测试数据，与实际有误差，敬请谅解.nn");elseprintf("从%s不能到达%s。",veri.name ,verj.name );8）调用floyd和way的最短路径shortestpath算法void shortestpath()/*寻找最短路径*/int i=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;3. 函数的调用关系exitexitmaininitmapmenuexitinformationshortestpathfloydwaySei测试与分析测试1）打开程序后，出现我校平面图和菜单选项，如图所示2）选“i”，查询对应地点的信息，如输入“3”，而后会继续输出菜单，如图所示3）选“s”，查询两点之间的信息，如输入“1 11”，而后会继续输出菜单，如图所示4）选“e”，推出程序，如图所示分析1.本次作业的核心是利用弗洛伊德算法计算给定有向网中两点最短距离；给出有向网中所要求点的信息。在调试过程中，除了简单语法错误外，就是对弗洛伊德算法的理解和实现，以及菜单的设置，这是我以前没有实现过的。出于简单化，并没有对有向图中各个点进行输入，而是在程序中直接赋值。2.在对各个功能操作的实现上，由于有弗洛伊德算法时间复杂度大多数是O(n3)，空间上增加了二维数组，空间复杂度为O(n+s)。 附录源程序代码及必要注释。#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辽宁工程技术大学大学平面图(括号内为相对应的数字编号)nn");printf(" 浴池(1)老体育场(2)新体育场(3)n");printf(" | | | |n");printf(" | | | |n");printf(" B寝室楼(4)一食堂(5)综合楼(6)南大门(7)n");printf(" | |n");printf(" A寝室楼(8) |n");printf(" | |n");printf(" 尔雅楼(9)耘慧楼(10)静远楼(11)nn"); void init()int i,j;/*从41到73行，对平面图中的各个地点信息进行输入，运用strcpy函数*/ver1.number =1;strcpy(ver1.name,"浴池");strcpy(ver1.introduce,"洗澡，吃饭，超市，一应具全n");ver2.number =2;strcpy(ver2.name,"老操场");strcpy(ver2.introduce,"怀念一下学长们的艰苦生活n");ver3.number =3;strcpy(ver3.name,"新体育场");strcpy(ver3.introduce,"假草，球门，尽情施展脚法的好地方n");ver4.number =4;strcpy(ver4.name,"B寝室楼");strcpy(ver4.introduce,"女寝，不解释n");ver5.number =5;strcpy(ver5.name,"一食堂");strcpy(ver5.introduce,"饭呐，不好吃n");ver6.number =6;strcpy(ver6.name,"综合楼");strcpy(ver6.introduce,"超市，有日用品，各种食品，还有各种营业厅，眼镜店，书店，水果店n");ver7.number =7;strcpy(ver7.name,"南大门");strcpy(ver7.introduce,"学校最宏伟的建筑，校友捐赠n");ver8.number =8;strcpy(ver8.name,"A寝室楼");strcpy(ver8.introduce,"男寝，我的家n");ver9.number =9;strcpy(ver9.name,"尔雅");strcpy(ver9.introduce,"教学楼，有我最爱的411，是基础教学部老师大展身手的地方n");ver10.number =10;strcpy(ver10.name,"耘慧楼");strcpy(ver10.introduce,"教学楼，各种上机实验的地方n");ver11.number =11;strcpy(ver11.name,"静远楼");strcpy(ver11.introduce,"教学楼，内涵图书馆，足够惊喜n"); for(i=1;i<=Num;i+)/*对存储距离的距离矩阵取值进行初始化，全定义为最大*/ for(j=1;j<=Num;j+) edgeij=Maxedge; for(i=1;i<=Num;i+)/*对存储距离的矩阵的取值进行正确赋值，由于我校均来回可达，顾对路径正反同时赋值*/edgeii=0;edge12=edge21=20;edge23=edge32=50;edge25=edge52=50;edge34=edge43=100;edge36=edge63=300;edge14=edge41=20;edge45=edge54=30;edge56=edge65=10;edge67=edge76=200;edge611=edge116=120;edge48=edge84=10;edge89=edge98=250;edge910=edge109=50;edge1011=edge1110=50;edge711=edge117=100;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("请输入查询地点的编号：nt"); scanf("%d",&i);if(i<=Num&&i>=1)printf("n名称：%sn#简介：%sn",veri.name,veri.introduce);return;elseprintf("输入有误！");void floyd()/*弗洛伊德算法*/int i=1,j=1,k=1,l=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<=Num;j+)if(shortestij>(shortestik+shortestkj)shortestij=(shortestik+shortestkj);pathij=pathji=k;void way(int i,int j)/*最短路径的输出*/int k=0,a=i,b=j;if(shortestij!=Maxedge)printf("n%从%s到%s的最短路径为:n",veri.name,verj.name);printf("%s",veri.name);while(pathij!=0)k=pathij;while(pathik!=0)k=pathik;printf("-到-%s",verk.name);i=k;printf("-到-%s;n",verj.name );printf("n最短距离为：%d米。n",shortestab);printf("n数据均为测试数据，与实际有误差，敬请谅解.nn");elseprintf("从%s不能到达%s。",veri.name ,verj.name );void shortestpath()/*寻找最短路径*/int i=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;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;5 总结与展望此次课程设计相对于我来说，难度较大，相对于这个学期写的那些小算法来说，这个课程设计能充分发挥出学习数据结构后的能力；而相对于之前做的设计性实验，又有了实际的应用，现实应用度增加。从接触C语言编程到现在，我就觉得：编程不是简简单单的写出程序，更多的是处理出现的语法和逻辑错误。在这次课程设计中，我深刻的体会到编程不是一种简单的事，编程不但需要耐心，更需要细心。编出大体的程序架构，花费了我的时间并不多，但我很多时间是用在调试和测试数据上！有些现在看着简单的语法错误，一时竟然无从下手。我想，这和我C语言基础薄弱有很大关系，以后要加强认识。 总的来说，这次课程设计，让我学了很多，总结了很多！参考文献1 严蔚敏，吴伟民.数据结构（C语言版）M. 北京 清华大学出版社，20072 谭浩强.C程序设计（第三版） M. 北京 清华大学出版社，20073 谭浩强.C程序设计题解与上机指导（第三版）M. 北京 清华大学出版社，20074 严蔚敏，吴伟民，米 宁.数据结构题集（C语言版）M. 北京 清华大学出版社，20075 互联网的相关信息和内容成绩评定成绩 教师签字