数据结构课程设计文档模板.doc

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

1、课程设计报告课程名称： 数据结构 设计题目： 公路收费模拟系统 院 部： 专 业： 组 别： 第2组 起止日期: 指导教师: 计算机与信息工程学院二一二年制课程设计题目公路收费模拟系统组长学号班级系别专业组员指导教师课程设计目的掌握数据结构的基本理论和基本方法；培养学生的编程能力、协作能力以及撰写文档的能力。课程设计环境Window XP，Microsoft Visual C+ 6.0。课程设计任务根据实际问题，构造相应的数据结构，设计解决问题的算法，以及撰写规范的文档。课程设计工作进度计划序号起止日期工作内容分工情况14月9日至4月15日选题所有的组员根据所选的题目查找资料，讨论思路24月1

2、6日至4月22日讨论解题思路34月23日至5月20日编码及单元测试45月21日至6月11日集成测试56月12日至6月28日撰写文档指导教师签字： 年 月 日系（教研室）审核意见： 系（教研室）主任签字： 年 月 日课程设计任务书目录1.引言12 .需求分析12.1课程设计题目12.2课程设计内容12.3课程设计要求12.4课程设计思想12.5软硬件运行环境13 概要设计13.1课程设计的流程图13.2主要的数据结构23.3算法分析24 详细设计34.1绘出计算机程序框图34.2程序的实现34.2.1预编命令，定义结构体和全局变量34.2.2从文件中读入图的结构44.2.3显示出收费站的结构54

3、.2.4弗洛伊德算法54.2.5求最短路径的长度64.2.6判断车型函数64.2.7计算路费的函数74.2.8结束函数84.2.9菜单函数84.2.10主体函数84.3数据存储格式95 调试分析与调试结果说明95.1 系统调试分析95.2 调试结果105.2.1开始界面105.2.2显示收费站的结构105.2.3显示最短路径115.2.4显示站与站之间的费用115.2.5退出系统116 课程设计总结与体会127 致谢128 参考文献121.引言 高速公路传统的收费方式以手工收费为主，这种传统的收费方式效率低、出错率高，管理人员无法及时的看到收费报表，无法及时了解一线收费人员的收费情况。随着高速

4、公路的快速发展，收费站数目的不断增加，传统的收费方式已经不能够满足现实的需要，基于此，设计与实现一个简单而高效的模拟公路收费系统2 .需求分析2.1课程设计题目 公路收费模拟系统。2.2课程设计内容设计一个包含不少于10个收费站的高速公路网，公路里程和每公里的费用自行设定，编写程序模拟公路收费。2.3课程设计要求选择合适的数据存储结构；（注：数据的输入以文件输入的方式）输入上高速公路时所进的收费站和下高速公路时所出的收费站，系统能够自动计算两地之间的应收费用。2.4课程设计思想首先用无向图来模拟公路的收费站，各个收费站就相当于图的结点，站与站之间的距离就相当于弧的长度，利用图的邻接矩阵来存储高

5、速公路收费站的模型，用Floyd算法来求收费站之间的最短路径；建立好文本文件来存储站点名称以及两个邻接站点之间的距离；通过构建并存储图的结构、求最短路径、显示最短路径、求任意站与站之间距离、计算路径长度、退出系统以及显示主菜单等子函数来达到课程设计要求。2.5软硬件运行环境Window XP，Microsoft Visual C+ 6.0。3 概要设计理解题意查找资料算法分析编写程序运行调试3.1课程设计的流程图 图3-1 课程设计的流程图 3.2主要的数据结构抽象数据类型图的定义如下：ADT Graph 数据对象V：V是具有相同特性数据元素的集合，称为顶点集。 数据关系R： R=VR VR=

6、（v，w）| v , wV, (v , w)表示v和w之间存在路径基本操作P：CreatGraph(&G, V, VR)初始条件： V是图的顶点集，VR是图中边的集合。操作结果： 按定义(V, VR) 构造图G。Show(&G)初始条件：图G已存在。操作结果：显示图G中的所有路径关系。3.3算法分析1. 定义结构体Algraph：定义一个既简单又符合题目设计要求的结构体，采用邻接矩阵来作为图的存储结构；2. 构建图的结构（creatgraph函数）：首先, 建立文本文件，利用程序打开文件，从文件中读取图的信息，把图的基本信息存入邻接矩阵中，然后关闭文件。借助邻接矩阵就容易判断出任意两个点之间是

7、否有路径，并且可以存储弧的带权长度值。3. 显示收费站结构的（show函数）：在邻接矩阵中，判断两点之间的距离是否小于无穷大，小于无穷大，就说明该两点之间有路径，便能将收费站的结构输出。4. 求最短路径（floyd算法）：定义两个数组length和path，path用来存储路径，length用来保存两点之间的最短路径。求两点之间的最短路径，首先要判断这两点是否有路径可走，如果有，但那不一定是最短的路径，需要进行n次试探。若（vi，vk）和（vk，vj）分别是从vi到vk和从vk到vj的中间顶点的序号不大于k-1的最短路径，则将（vi，vk,vj）和已经得到的从vi到vj且中间顶点序号不大于k-

8、1的最短路径相比较，其较长度短者是从vi到vj的中间顶点的序号不大于k的最短路径。这样，经过n次的比较后，最后求得的必是从vi到vj的最短路径。按此方法，可以同时求得各对顶点之间的最短路径。5.求任意两点之间的最短路径（minist函数）：在调用floyd算法后，函数中有返回length的值，只要将任意两收费站在数组中的下标找到并带入到length中就可以输出两收费站之间的最短路径。6.求任意两收费站之间的收费(mmoney函数)：调用foyld函数求得各收费站之间的最短路径，输入车辆的类型，根据类型的不同，来计算路费。7.定义菜单函数（menu），采用分支函数，列举出菜单，可以任意选择程序的

9、功能，进入相应的函数，得到所需要的结果。4 详细设计4.1绘出计算机程序框图根据车类型来计算路费求任意两点之间的最短路径用flyod算法求最短路径利用邻接矩阵构建图的结构输出任意两点之间最短路径所经过的路径输出函数（输出图的结构）图4-1 程序框图4.2程序的实现4.2.1预编命令，定义结构体和全局变量/ 交通路费系统 / 2012年 6月17日 /# include#include# define M 100typedef int PathMM;typedef structchar vexM; /保存顶点信息int n; / 定义顶点数int edgesMM; /保存每条边的权值Algrap

10、h; /定义图的结构体/*定义全局变量*/int pathMM,lengthMM; /path保存最短路径的结点，length是保存最短路径距离Algraph G;4.2.2从文件中读入图的结构/*利用文件函数打开文本文件f4.txt，将收费站的名称先存储到结构体的数组中，关闭文本文件f4.txt,再打开文本文件f3.txt,将弧的信息存储到结构体的二维数组中，构建出收费站的基本结构*/void creatgraph(Algraph &G)int i,m,n,k;FILE *fp1,*fp2; /*定义文件名*/fp1 = fopen(f4.txt,r); /*r为读取文件*/if(fp1 =

11、 NULL) /*打开文件并判断文件是否存在*/printf(File open error!n);exit(0);i = 1;G.n = 0;while(!feof(fp1) /*从文件中读取信息并存入数组中*/G.n+; fscanf(fp1,%c,&G.vexi);i+;G.n-;if(fclose(fp1) /*关闭文件*/printf(Can not close the file!n);exit(0);for(int h = 1;h=G.n;h+) for(int j = 1;j=G.n;j+)G.edgeshj = 10000; /*给每条边附带权长度初值*/fp2=fopen(f

12、3.txt,r);if(fp2=NULL)printf(File open error!n);exit(0); while(!feof(fp2) fscanf(fp2,%d%d%d,&m,&n,&k); /*从文件中读取边的权值并存入二维数*/ G.edgesmn = k;G.edgesnm=k; if(fclose(fp1) printf(Can not close the file!n); /*关闭文件*/exit(0);4.2.3显示出收费站的结构/*利用函数输出构建的图的存储结构显示出每个站点的距离*/void show(Algraph G)int i,j; creatgraph(G)

13、;printf(请输出收费站的结构：n);for(i=1;i=G.n;i+)for(j=1;j=G.n;j+)if(G.edgesij!=10000&i!=j)printf( %c%c %dn,G.vexi,G.vexj,G.edgesij);4.2.4弗洛伊德算法/*首先将收费站之间的路径存储到length中，然后将有路径的收费站名称的下标存储到path中，再用三重循环往中间加点，分别将每两收费站之间的最短路径存储到length中 */void shortpath(Algraph &G,Path path,Path length) int i,j,k; for(i = 1;i=G.n;i+)

14、 for(j = 1;j=G.n;j+) if(i=j) G.edgesij=0;lengthij = G.edgesij; if(i=j) pathij = -1; else if(lengthij10000) pathij = i; /保存每条边的弧头 else pathij = -1; for(k=1;k=G.n;k+) for(i=1;i=G.n;i+) for(j=1;j=G.n;j+) if(lengthik+lengthkjlengthij) /*判断两点之间最短距离*/ lengthij=lengthik+lengthkj; pathij=pathkj; 4.2.5求最短路径的

15、长度/*先调用弗洛伊德算法，算法中有返回length的值，输入两个收费站的名称，即可求出两收费站之间的最短路径长度*/void minist(Algraph &G)int i,j;char ch1,ch2; creatgraph(G);int pathMM,lengthMM;shortpath(G,path,length); /调用函数求得各点之间的最短路径 printf(请输入两个收费站的名称:n);getchar();scanf(%c%c,&ch1,&ch2); for(i=0;iG.n;i+)if(G.vexi=ch1) /在数组中查找所输入的值break;for(j=0;jG.n;j+

16、)if(G.vexj=ch2)break;printf(收费站%c到收费站%c的最短路径长度为：n,ch1,ch2); printf(%d 公里,lengthij);return;4.2.6判断车型函数/*利用分支语句判断车辆类型，不同类型的车收费不同，并计算路费*/void Shape(int &money,Path length,int i,int j)char shape;printf(车辆类型(l,m,s)分别代表大，中，小):n);getchar(); shape=getchar();switch(shape) case l: money=15*lengthij; printf(该车

17、为大型车辆n);break; case m: money=10*lengthij; printf(该车为中型车辆n);break; case s: money=5*lengthij; printf(该车为小型车辆n);break;default: break;4.2.7计算路费的函数/*先调用弗洛伊德函数，输入两个收费站名称并判断车型，依据车型的大小来实现收费的计算，并输出计算的结果和所经过的路径*/void mmoney(Algraph &G)int i,j,money;char ch1,ch2;creatgraph(G);int pathMM,lengthMM;printf(大型车辆每公里

18、收费为15元/每公里n);printf(中型车辆每公里收费为10元/每公里n);printf(小型车辆每公里收费为5元/每公里n);printf(上高速的收费站(a/b/c)和下高速的收费站(a/b/c)：n);getchar();scanf(%c%c,&ch1,&ch2);for(i=0;iG.n;i+)if(G.vexi=ch1)break;for(j=0;jG.n;j+)if(G.vexj=ch2)break;shortpath(G,path,length); /调用弗洛伊德算法求各点之间的最短路径Shape(money,length,i,j); /根据车辆的类型来求得路费 printf

19、(输出经过的最短路径:); printf( %c ,G.vexj); while(pathij!=-1) printf(-%c,G.vexpathij); j = pathij;printf(n);printf(从%c收费站到%c收费站应缴费用为：%d元nn,ch1,ch2,money);4.2.8结束函数/*用此函数来退出交通收费模拟系统*/void end()printf(谢谢使用高速公路路费计费系统!n);exit(0);4.2.9菜单函数/*编写菜单函数，以便使用者方便运行使用,按1进入显示收费站结构函数，按2 进入显示最短路径函数，按3进入计算路费费用的函数，按4退出总的系统*/vo

20、id menu()Algraph G;int n; printf(nnnn); printf(tt*欢迎使用高速公路计费系统*n); printf(tt 主菜单 n); printf(tt *1.显示收费站的结构*n); printf(tt *2.显示最短路径*n); printf(tt *3.显示费用*n); printf(tt *4.退出系统*n); printf( 请输入数字选择操作类型:n); scanf(%d,&n); switch(n) case 1: show(G); break; case 2: minist(G); break; case 3: mmoney(G); brea

21、k; case 4: end(); break; default: break; 4.2.10主体函数/*主函数,利用无限循环可以进行连续的操作*/void main()while(1) menu(); 4.3数据存储格式图的顶点信息存储在文本文件f4.txt中，顶点序列为abcdefghjk；图的弧的信息存储在文本文件f3.txt中，具体弧的信息如下图所示： 1 2 101 3 5 1 6 41 1 9 31 1 10 20 2 3 13 2 5 29 2 10 213 4 83 6 9 4 5 15 4 9 45 4 7 385 6 9 5 8 37 5 9 346 7 77 8 4 7

22、10 89 8 9 11 9 10 19 图4-2 弧的信息存储5 调试分析与调试结果说明5.1 系统调试分析1. 本程序在求最短路径的问题上采用了弗洛伊德算法来解决，虽然迪杰斯特拉算法比该算法时间复杂度低，但在频繁查询时效率低，而弗洛伊德算法只要计算一次，即可求得每一对顶点之间的最短路径，虽然时间复杂度较高，但以后每次查询只要查表即可，会极大地提高查询的效率。综合各方面因素考虑，因此选择弗洛伊德算法来解决这个问题。2. 由于功能函数较多，在编写程序时将函数逐个添加完成的，就是说，每增加一个函数，进行一次编译运行，此函数通过了再写下一个函数。或许这种方法比较麻烦，但当有错误时只要针对新加函数进

23、行修改即可。同时，要充分利用软件所提供的调试功能确保程序准确的运行。5.2 调试结果5.2.1开始界面 图5-1 开始界面5.2.2显示收费站的结构图5-2 显示收费站的结构5.2.3显示最短路径 图5-3 显示最短路径5.2.4显示站与站之间的费用 图5-4 显示费用和路径5.2.5退出系统 图5-5 系统结束6 课程设计总结与体会本次课程设计，使大家对数据结构这门课程有了更深入的理解。数据结构是一门实践性较强的课程，为了学好这门课程，必须在掌握理论知识的同时，加强上机实践。要想把课程设计做的更好，就要学会参考一定的资料，吸取别人的经验，加强团队合作。在本课程设计中，我们明白了理论与实际应用

24、相结合的重要性，并提高了自己组织数据及编写大型程序的能力，培养了基本的、良好的程序设计技能，同时提高了我们的综合运用所学知识的能力。程序的编写需要有耐心，即使有些问题看起来很复杂，但一旦把问题分析透彻，把问题划分成一个一个小块，再逐个去解决，相当于总体解决大的问题，这样做起来不仅有条理也能使问题轻松的解决。通过这段时间的课程设计，大家都认识到数据结构是一门比较难的课程，需要多花时间上机练习。这次的程序训练培养了同学们实际分析问题、编程和动手能力以及掌握程序设计的基本技能，提高了大家根据生活中的问题来实践编程的能力。这次的课程设计使大家对于专业课的学习有了更加深刻的认识。认识到努力学好每门专业课

25、的重要性，让自己拥有更多的知识，只有这样才能解决更多的问题！ 总的来说，这次课程设计让大家获益匪浅，对数据结构这门课以及编程也有了进一步的理解和认识。7 致谢非常感谢指导老师耐心的指导大家，不仅在实验过程中帮助大家分析实验思想以及实验思路，在实验过程中给大家指出不足，帮大家调试错误，为大家成功的完成课程设计提供了很大的帮助；与此同时还要感谢各位组员的积极配合，按照实验思路，构造严谨的程序框架，并且各自都圆满完成自己负责的模块，最后大家共同整理出程序，然后一起进行调试分析，评估程序的严谨性，并且找出不足，完善实验内容，整理资料，编写文档。衷心的感谢指导老师与各位组员在这次课程设计中做出的贡献。8 参考文献1 何钦铭, 颜晖.C语言程序设计M. 北京：高等教育出版社，20082 严蔚敏, 吴伟民. 数据结构（C语言版）M.北京：清华大学出版社, 2011