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

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

2、录第一章开发环境和开发工具11.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+简介计算机诞生初期,人们要使用计算机必须用机器语言或汇编语言编写程序世界上第一种计算机高级语言诞生于

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

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

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

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

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

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

9、 4教学区教学区操场 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 edgeN

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

11、d()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;函数描述，用floyd算法通过图的权值矩阵求出图中的每两点间的最短路径矩阵。还引入一个后继节点矩阵path来

12、记录两点间的最短路径。5.主菜单char show1()描述;显示导航图中的所有导航节点，能够快速方便的对各个地点进行导航。先执行main函数。3.2 程序模块 开始 输入始末景点显示路径信息输入景点序号显示景点介绍显示各个景点之间的距离显示学校介绍返回退出查询景点路径查询景点信息查询各景点间距结束学校简介3.3 各模块之间的调用关系造图函数（）Main（）主菜单Show1（）最短路径函数Shortestpath（）输出函数 图二3.4 源程序代码 #include <stdio.h>#include<string.h>#define Num 15/*景点个数*/#de

13、fine Maxedge 5000/*typedef struct char name14 ; /*景点名称*/ int number; /*景点编号*/ char introduce100; /*景点描述*/vertex; /*定义顶点的类型*/vertex verNum; /*图中的顶点，即为景点 */int edgeNumNum; /*图中的边*/ int shortestNumNum; /*景点间最短距离*/ int pathNumNum; void show1()/*主菜单*/printf("ttt*河南城建学院平面图*nn"); printf("t 塑

14、胶操场n"); printf("t 北门 行政楼 体育馆n"); printf("t n"); printf("t 教 教 操场n"); printf("t 学 学 教 n"); printf("t 区 区 学南门n"); printf("t 区 n"); printf("t 喷泉广场 n"); printf("t服 n"); printf("t务 山 顶 图书馆n"); printf("t区 操

15、 场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,);printf("nn");void init()int i,j;ver1.number =1;strcpy(,"北门");strcpy(roduce,"河南

16、城建北门，面朝北");ver2.number =2;strcpy(,"行政楼");strcpy(roduce,"总办公楼");ver3.number =3;strcpy(,"塑胶操场");strcpy(roduce,"四百米跑道，足球场，办运动会的主要场地");ver4.number =4;strcpy(,"体育馆");strcpy(roduce,"有羽毛球场，篮球场，为校方

17、一些篮球赛提供场所，还有乒乓球室");ver5.number =5;strcpy(,"教学区");strcpy(roduce,"包括二号楼，三号楼，四号楼");ver6.number =6;strcpy(,"教学区");strcpy(roduce,"五号教学楼，六号教学楼，七号教学楼");ver7.number =7;strcpy(,"操场");strcpy(roduce,"

18、网球场，篮球场，学生上课的主要场所，军训会操演练");ver8.number =8;strcpy(,"教学区");strcpy(roduce,"八号楼，九号楼，十号楼");ver9.number =9;strcpy(,"喷泉广场");strcpy(roduce,"迎新的时候开启喷泉，小型汇演场所");ver10.number =10;strcpy(,"南门");strcpy(rod

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

20、roduce,"供学生住宿");ver14.number =14;strcpy(,"西门");strcpy(roduce,"河南城建西门，面朝西"); ver15.number =15;strcpy(,"服务区");strcpy(roduce,"老师和学生购物的地方");for(i=1;i<=Num;i+) for(j=1;j<=Num;j+) edgeij=Maxedge; for(i=1;i<=Nu

21、m;i+)edgeii=0;edge12=edge21=50;edge15=edge51=80; edge19=edge91=300; edge111=edge111=370;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; edge111

22、3=edge1311=20;edge1115=edge1511=50; edge1315=edge1513=30; edge1314=edge1413=30;char show3()/*查询菜单*/char i;printf("信息查询请输入a.n");printf("最短路径查询请输入b.n");printf("退出系统请输入c.n");printf("你的选择：");scanf("%s",&i);return i;void information()int i;while(1)sys

23、tem("cls");show1();show2();printf("请输入查询地点的编号：");scanf("%d",&i);if(i<=Num&&i>=1)printf("名称：%sn简介：%sn",,roduce);return;elseprintf("输入有误！");void floyd()/*造图函数*/int i=1,j=1,k=1,l=1;for(i=1;i<=Num;i+)for(j=1;j<=Nu

24、m;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 show4(int i,int j)/*输出函数*/int k=0,a=i,b=j;if(shortestij!=Maxedge)printf("从%s到%s的最短路径为:n"

25、;,,);printf("%s",);while(pathij!=0)k=pathij;while(pathik!=0)k=pathik;printf("-%s",);i=k;printf("-%s;n", );printf("最短距离为：%d米。n",shortestab);elseprintf("从%s不能到达%s。", , );void shortestpath()

26、/*最短路径函数*/int i=0,j=0;while(1)system("cls");show1();show2();printf("请输入要查询的两点的编号：（以空格间隔）");scanf("%d%d",&i,&j);if(i<=Num&&i>0&&j<=Num&&j>0)floyd();show4(i,j);return;int main()/*主函数*/char i;printf("nnnnnnttWELCOME TO HENAN

27、 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");printf("ttt n");printf("n

28、n");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("pause");第四章 测试与分析4.1 测试数据选择导航系统开启任意键进入主菜单输入a进入信息查询，并选择景点5选择b进入最短路径查询，并选择1到10选择c退出校