终极数据结构课程设计模板.doc

《终极数据结构课程设计模板.doc》由会员分享，可在线阅读，更多相关《终极数据结构课程设计模板.doc（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、河南城建学院课程设计报告书专 业：计算机科学与技术 课程设计名称：数据结构课程设计题 目：校园导航问题班 级：学 号：姓 名：谌文娟同 组 人 员：许化宇指 导 老 师：王永皎、赵军民、陈秋红、张延红完 成 时 间：2014年2月27日摘要校园导航要求每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径(最短路径)。要用“邻接矩阵”来存储各点间的距离，然后用 floyd算法求出最短路径。所以采用工程思想，将系统共分以下五个模块：节点数据结构类型、创建导航图函数、最短路径导航函数、查询函数声明、主菜单。关键词：数据结构；算法设计目录目录第一章开发环境和开发工具11.

2、1 C语言简介.11.2 开发背景21.3 开发环境2第二章 算法思想32.1 系统需求分析32.2 系统总体设计42.2.1 系统设计目标42.2.2 开发设计思想42.2.3 系统功能模块设计42.3 算法思想描述4第三章算法实现63.1 数据结构63.2 程序模块83.3 各模块之间的调用关系93.4 源程序代码10第四章测试与分析164.1 测试数据选择164.2 测试结果分析20总 结21心得体会21参考文献22第一章 开发环境和开发工具1.1 C/C+简介计算机诞生初期,人们要使用计算机必须用机器语言或汇编语言编写程序世界上第一种计算机高级语言诞生于1954年,它是FORTRAN语

3、言先后出现了多种计算机高级语言其中使用最广泛影响最大的当推BASIC语言和C语言它是一种使用非常广泛的计算机编程语言。C+是一种静态数据类型检查的、支持多重编程范式的通用程序设计语言。它支持过程化程序设计、数据抽象、面向对象程序设计、制作图标等等泛型程序设计等多种程序设计风格。C+是由AT&T Bell(贝尔)实验室的Bjarne Stroustrup博士及其同事于20世纪80年代初在C语言的基础上开发成功的C+保留了C语言原有的所有优点,增加了面向对象的机制C+是由C发展而来的,与C兼容用C语言写的程序基本上可以不加修改地用于C+从C+的名字可以看出它是C的超越和集中C+既可用于面向过程的结

4、构化程序设计,又可用于面向对象的程序设计,是一种功能强大的混合型的程序设计语言C+支持面向过程的程序设计，也支持基于对象的程序设计，又支持面向对象的程序设计。以后我们将介绍基于对象的程序设计。包括类和对象的概念、类的机制和声明、类对象的定义与使用等。这是面向对象的程序设计的基础。基于对象就是基于类。与面向过程的程序不同，基于对象的程序是以类和对象为基础的，程序的操作是围绕对象进行的。在此基础上利用了继承机制和多态性，就成为面向对象的程序设计(有时不细分基于对象程序设计和面向对象程序设计，而把二者合称为面向对象的程序设计)。1.2 开发背景 随着科学技术的不断发展，计算机科学日渐成熟，其强大的功

5、能已为人们所深刻认识，它己进入人类社会的各个领域并发挥着越来越重要的作用。采用计算机进行信息化管理已成为人们出行重要的工具，而信息管理的全面自动化、信息化则是其中重要的组成部分。信息管理的好坏对于出行者来说至关重要。因此，本文所研究的信息系统具有一定的使用价值和现实意义。1.3 开发环境本文所采用的开发环境：Windows2000以上操作系统 Visual C+6.0以上编译环境第二章 算法思想2.1 系统需求分析此次课程设计的主要内容是校园导航系统，所谓系统其实也不尽然，只不过是个小小的提示，为来访的客人提供各种信息查询服务。主要包括：查看学校的全景图各个景点的简介查看某一景点到其它所有景点

6、的最短路径查询任意两个景点之间的最短路径。 一些约定： 对于功能的输入形式是没什么要求的，主要就是根据菜单的提示输入相应的数字选择相应的功能；对于功能的输入形式的要求也比较简单，要查询某一景点的简介直接输入其对应的编号即可；对于功能的输入形式的要求同功能；对于功能只需要输入想要查看的起始景点的编号即可；对于功能只需要输入起始景点和目的景点的编号即可。此程序在输入形式上都没什么特殊的要求只是一些简单的数字就可以搞定一切。 功能就是输出由字符构成的一幅简易图，形式比较单一；景点的简介方面输出景点的简单信息就可以了；要查询最短路径的话输出的自然是从起始景点到目的地的最短路径中所途经的各个景点及距离。

7、 本程序所能达到的功能就是前面所提到的中的功能。2.2 系统总体设计2.2.1 系统设计目标 景点显示（显示景点的编号、名称以及简介） 最短路径求解（求一点到所有点之间的路径及长短，求始终两点之间的路径及长短） 景点查找（有选择的查找你所想了解的景点）2.2.2 开发设计思想 基于以上系统设计目标，本文在开发校园导航系统时遵循了以下开发设计思想: 采用现有的软硬件环境及先进的管理系统开发方案，从而达到充分利用现有资源，提高系统开发水平和应用效果的目的。尽量达到操作过程中的直观、方便、实用、安全等要求。系统采用模块化程序设计方法，既便于系统功能的各种组合和修改，又便于未参与开发的技术维护人员补充

8、、维护。系统应具备数据库维护功能，及时根据用户需求进行数据的添加、删除、修改、备份等操作。2.2.3 系统功能模块设计 采用工程思想，将系统共分以下五个模块：节点数据结构类型、创建导航图函数、最短路径导航函数、查询函数声明、主菜单。2.3 算法思想描述本课程设计的内容为设计学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。如图1,图中已标出主要路线，各路线的长度如图1中所示。显然要解决这一问题要用“邻接矩阵”来存储各点间的距离，然后用Dijkstra求出最短路径。 3塑胶操场北门行政楼体育馆 1 2 4教学区

9、教学区操场 5 6 7教学区 南门10喷泉广场 9 8服务区15 山顶操场图书馆 11 12 宿舍楼 13 西门 14 图一第三章 算法实现3.1 数据结构1.节点数据结构类型#define Num 15/*景点个数*/#define Maxedge 5000/*定义路径的无穷大*/typedef struct char name14 ; /*定义景点名称*/ int number;/*景点编号*/ char introduce100;/*景点描述*/vertex;/*定义顶点类型*/vertex verNum; /* 存放顶点的一维数组，数组地领个单元没有用 */int edgeNumNum

10、; /* 存放路径的长度 */int shortestNumNum; /*定义全局变量存储最小路径*/int pathNumNum; /*定义存储路径*/2.创建导航图函数void init()int i,j;函数描述：主要将每个节点进行命名、每个顶点到其他所有定点的路径值用邻接矩阵进行存储。例如：ver1.number =1;strcpy(ver1.name,北门);strcpy(ver1.introduce,河南城建北门，面朝北);作用：使1号定点命名为“北门”；描述为“河南城建北门，面朝北”；3.最短路径导航函数void floyd()int i=1,j=1,k=1,l=1;for(i=

11、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;函数描述，用floyd算法通过图的权值矩阵求出图中的每两点间的最短路径矩阵。还引入一个后继节点矩阵path来记录两点间的最短路径。5.主菜单char show1()描述;显示导航图中的所有导航节点，能够快速方便的对各个地点进行导航。先执行main函数。3.

12、2 程序模块 开始 输入始末景点显示路径信息输入景点序号显示景点介绍显示各个景点之间的距离显示学校介绍返回退出查询景点路径查询景点信息查询各景点间距结束学校简介3.3 各模块之间的调用关系造图函数（）Main（）主菜单Show1（）最短路径函数Shortestpath（）输出函数 图二3.4 源程序代码 #include #include#define Num 15/*景点个数*/#define Maxedge 5000/*typedef struct char name14 ; /*景点名称*/ int number; /*景点编号*/ char introduce100; /*景点描述*/

13、vertex; /*定义顶点的类型*/vertex verNum; /*图中的顶点，即为景点 */int edgeNumNum; /*图中的边*/ int shortestNumNum; /*景点间最短距离*/ int pathNumNum; void show1()/*主菜单*/printf(ttt*河南城建学院平面图*nn); printf(t 塑胶操场n); printf(t 北门 行政楼 体育馆n); printf(t n); printf(t 教 教 操场n); printf(t 学 学 教 n); printf(t 区 区 学南门n); printf(t 区 n); printf(

14、t 喷泉广场 n); printf(t服 n); printf(t务 山 顶 图书馆n); printf(t区 操 场n); printf(t宿舍楼n); printf(t n); printf(t 西门nn); void show2()/*景点编号*/int i=1;for(i=1;i=Num;i+)printf(%d,%st,i,veri.name);printf(nn);void init()int i,j;ver1.number =1;strcpy(ver1.name,北门);strcpy(ver1.introduce,河南城建北门，面朝北);ver2.number =2;strcpy

15、(ver2.name,行政楼);strcpy(ver2.introduce,总办公楼);ver3.number =3;strcpy(ver3.name,塑胶操场);strcpy(ver3.introduce,四百米跑道，足球场，办运动会的主要场地);ver4.number =4;strcpy(ver4.name,体育馆);strcpy(ver4.introduce,有羽毛球场，篮球场，为校方一些篮球赛提供场所，还有乒乓球室);ver5.number =5;strcpy(ver5.name,教学区);strcpy(ver5.introduce,包括二号楼，三号楼，四号楼);ver6.number

16、 =6;strcpy(ver6.name,教学区);strcpy(ver6.introduce,五号教学楼，六号教学楼，七号教学楼);ver7.number =7;strcpy(ver7.name,操场);strcpy(ver7.introduce,网球场，篮球场，学生上课的主要场所，军训会操演练);ver8.number =8;strcpy(ver8.name,教学区);strcpy(ver8.introduce,八号楼，九号楼，十号楼);ver9.number =9;strcpy(ver9.name,喷泉广场);strcpy(ver9.introduce,迎新的时候开启喷泉，小型汇演场所)

17、;ver10.number =10;strcpy(ver10.name,南门);strcpy(ver10.introduce,河南城建南门，面朝南);ver11.number =11;strcpy(ver11.name,山顶操场);strcpy(ver11.introduce,学生晨练、晨读经常去的地方); ver12.number =12;strcpy(ver12.name,图书馆);strcpy(ver12.introduce,同学借还书，还有自习); ver13.number =13;strcpy(ver13.name,宿舍楼);strcpy(ver13.introduce,供学生住宿)

18、;ver14.number =14;strcpy(ver14.name,西门);strcpy(ver14.introduce,河南城建西门，面朝西); ver15.number =15;strcpy(ver15.name,服务区);strcpy(ver15.introduce,老师和学生购物的地方);for(i=1;i=Num;i+) for(j=1;j=Num;j+) edgeij=Maxedge; for(i=1;i=Num;i+)edgeii=0;edge12=edge21=50;edge15=edge51=80; edge19=edge91=300; edge111=edge111=3

19、70;edge115=edge151=500;edge23=edge32=100;edge24=edge42=150;edge26=edge62=10;edge47=edge74=10;edge78=edge87=40;edge710=edge107=50;edge89=edge98=100;edge812=edge128=100;edge912=edge129=10;edge1112=edge1211=50; edge1113=edge1311=20;edge1115=edge1511=50; edge1315=edge1513=30; edge1314=edge1413=30;char s

20、how3()/*查询菜单*/char i;printf(信息查询请输入a.n);printf(最短路径查询请输入b.n);printf(退出系统请输入c.n);printf(你的选择：);scanf(%s,&i);return i;void information()int i;while(1)system(cls);show1();show2();printf(请输入查询地点的编号：);scanf(%d,&i);if(i=1)printf(名称：%sn简介：%sn,veri.name,veri.introduce);return;elseprintf(输入有误！);void floyd()/

21、*造图函数*/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(shortestik+shortestkj)shortestij=(shortestik+shortestkj);pathij=pathji=k; /*记录经过的路径*/void show4(int i,int j)/*输出函数*/int k=0,a=i,b=j;if(shortestij!=Maxedge)printf(从%s到%s

22、的最短路径为: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(最短距离为：%d米。n,shortestab);elseprintf(从%s不能到达%s。,veri.name ,verj.name );void shortestpath()/*最短路径函数*/int i=0,j=0;while(1)system(cls);show1();sho

23、w2();printf(请输入要查询的两点的编号：（以空格间隔）);scanf(%d%d,&i,&j);if(i0&j0)floyd();show4(i,j);return;int main()/*主函数*/char i;printf(nnnnnnttWELCOME TO HENAN CHENGJIAN UNIVERSITY!nnn);printf(ttt n);printf(ttt n);printf(ttt 祝你健康快乐！ n);printf(ttt 每天都是 n);printf(ttt 星期天 ！ n);printf(ttt n);printf(ttt n);printf(ttt n);

24、printf(ttt n);printf(nn);init();system(pause);while (1)system(cls);show1();show2();i=show3();switch(i)case a:information();break;case b:shortestpath();break;case c:system(cls);/*清屏操作*/printf(nnnnnnnnnttttGOODBYE!nnnttO(_)OttO(_)Onnnnnnnnn); system(pause);exit(0);default :printf(输入错误！n);break;system(

25、pause);第四章 测试与分析4.1 测试数据选择图4.1.1导航系统开启图4.1.2任意键进入主菜单图4.1.3图4.1.4输入a进入信息查询，并选择景点5 图4.1.5图4.1.6选择b进入最短路径查询，并选择1到10 图4.1.7图4.1.8选择c退出校园导航系统 4.2 测试结果分析设计过程中遇到的问题，调试过程中难免会遇见这样或者那样的问题，一个很低级的错误就是在字符串的赋值上居然还会出错，当时确实有点慌了，等冷静下来一想才把问题想明白，字符串的赋值必须用strcpy函数。看来基本功还是相当的重要的。 剩下的就是最主要的问题也可以说是99%的问题，都在弗洛伊德算法上了，弗洛伊德算法

26、是我们重点学习的一个算法当时学习时就感觉很吃力，不过当时也确实弄明白了，只可惜都过去好长一段时间了所以有所遗忘，算法确实是按照书上所写的抄到了程序中。最短路径确实也存到了数组shortestij中，可是在输出相应的景点名称时总不能输出正确，感觉是很不可思议的问题，后来才明白数组中的存储是按照一定的顺序存储的但是并不一定是路径中所途经的景点的顺序，所以最后选择在求最短路径过程中将其输出。总 结在今后的工作、学习中我将认真总结经验教训，努力使自己成为一名技术过硬、工作严谨、思维活跃的工程人员，为提高人们的生活质量做出更大的贡献。这次程序的推荐路径就能设计还有许多不足，比如校园导航还可以有很多改进的

27、地方，如果有更多更符合人性化，还有各个景点的信息介绍不够详细，程序从整体上看比较繁琐，多数用了for循环语句，如果能用多一些递归函数会显得比较简洁，因为程序是借鉴网上的一些例子，运用的是弗洛伊德算法，运算效率比起Dijkstra算法效率更高。心得体会这个程序在设计过程中运用了不同的函数，在做课程设计的时候我也遇到了一些自己不明白的问题，通过查找教科书，上网查找资料，合同组成员进行探讨分析，找出比较符合我们心意的代码，积极探索语言知识，勇于发现问题，并及时解决问题。通过对程序的进一步了解，让我明白课本上的知识我虽然并不太感兴趣，但是不管在任何程序设计中，一个大的程序都需要小的语言知识结合起来共同运用的。在今后的学习过程中，一定要认真学好C语言这门课程，同时通过对这次作业的完成，加深了我对C语言知识的认识和巩固，知道了在进行语言编程的时候只有带着问题反复实践，才能更熟练的掌握和运用。因此在课余时间多学习和研究C语言对我自己本生来说是有一定的提高的。多学习课本以外的知识，充分扩大知识面，不断充实自己，不断提高。参考文献上网查找数据结构（c语言版）清华大学出版社