课程设计实例模板.doc

校园导游咨询数学与计算机学院课程设计说明书课 程 名 称: 数据结构-课程设计 课 程 代 码: 8404181 题 目: XXXXXXXXXXXX 年级/专业/班: 2009级信科X班 学 生 姓 名: 学 号: 开 始 时 间: 2011 年 12 月 xx 日完 成 时 间: 2011 年 12 月 xx 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日目 录摘要11 引言22系统分析52.1功能需求122.1.1总体要求142.1.2本人所做模块152.2数据需求163详细设计与实现173.1设计思路183.2 编码203.3 实现结果214 系统测试224.1设计测试数据234.2 测试结果及分析25总结27致谢28参考文献29附录30- 18 -摘 要设计学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径长度等相关信息。为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。为来访客人提供图中任意景点相关信息的查询。关键词：景点信息，最短路径，任意1 引 言 1. 1问题的提出以前的操作系统等系统软件主要是由汇编语言编写的（包括操作系统在内）。由于汇编语言依赖于计算机硬件，程序的可读性和可移植性都比较差。为了提高可读性和可移植性，最好改用高级语言，但一般高级语言难以实现汇编语言的某些功能（汇编语言可以直接对硬件进行操作，例如，对内存地址的操作、位操作等）。人们设想能否找到一种既具有一般高级语言特性，又具有低级语言特性的语言，集它们的优点于一身。于是，语言就在这种情况下应运而生了。1.2 C语言C语言既有高级语言的特点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。1.3 C语言发展过程1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本可移植的C语言编译程序。1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著The C Programming Language，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。1.4任务与分析 任务是一个最短路径的查找问题，校园的各景点可以看成是一个图中的点，而路径则是一个图中的各条边，将校园景点和之间的路径看成是一个图就行了。现实中路径是有长度的，所以应该是带权图，权值就是路径的长度。2 设计方案 2. 1整体设计方案 此课题是研究最短路径的问题，以帮助游客找到最短的路径到达想到达的景点。还可以为游客提供各景点的相关信息，供游客了解。因此实际需要设计的服务就是两种：景点信息查询和最短路径查询；为了直观和方便，画出流程图如下图1：提供的服务 查询景点信息退出该系统两景点间的最短路径最短路径景点信息否是继续服务 图1 程序总的流程图流程图很直观的描述了整个程序服务过程。 2.1.1查询景点信息模块设计方案游客要查询某个景点信息，那就需要知道他想查询的景点是什么。这需要游客增加在、手动输入景点名称或代号。通过游客输入的信息计算机就可以进行相关的查找，最简单的方法就是遍历，根据游客输入的信息遍历所有景点，找到相应的信息就输出来供游客浏览了；我们就要用相应的程序去实现这个过程,这才是我们最后的目的。/包含头文件#include#include 其中#include是中止程序进程的函数exit(0)的原形;#define INT_MAX 10000 /最大距离#define n 10 /景点数景点数和最大距离是可以确定的，所有我们先将它们定义了，以后如果要改也方便的多。/定义全局变量int costnn;/边距离int shortestnn;/两点间的最短距离int pathnn;/经过的景点这些全局变量都是各函数要用到的，为了减少函数参数的数量和参数变化带来了不便，定义成全局最好。/自定义函数原型说明void introduce();int shortestdistance(); /查询两景点的最短距离void floyed(); /求最短路径长度void output(int i,int j); /打印最短路径及长度/景点介绍void introduce()int a; printf(您想查询哪个景点的详细信息?请输入景点编号:); scanf(%d,&a); getchar(); printf(n); switch(a)case 1: printf(1:学校大门nn旧校门已拆，新校门还在建设中！nn);break; case 2: printf(2:体育馆nn学生上体育课及运动的场地，设有篮球场，跆拳道馆等众多活动场地，各种体育器材众多！nn);break; case 3: printf(3:求是广场nn校园内最大的广场，中央屹立着国旗。nn);break; case 4: printf(4:明德广场nn进学校时候看到的第一个广场，位于三教！nn);break; case 5:printf(5:一教nn学校的教学楼之一，拥有很古老的历史了！nn);break; case 6:printf(6:二教nn学校的教学楼之一，是数学与计算机学院的所在地。nn);break; case 7: printf(7:三教nn学校行政办公的主楼。nn);break; case 8: printf(8:图书馆nn学校信息资源中心，内设大量的自习室。nn);break; case 9: printf(9:四教nn学校的主教学楼之一，外国语学院所在地！nnn);break; case 10:printf(10:一食堂nn学校的第一食堂，口碑最好！nn);break; default:printf(景点编号输入错误！请输入重新输入！nn);getchar();/没有的话，在输入错误信息后会造成异常！break; 经过一个个的比较，很容易就可以找到对应的景点的信息，并提供给用户；这样，需要实现的第一个功能就很轻松的完成了。2.1.2寻找最短路径设计方案 要完成最短路径到查找，有很多种方法可以实现。例如Dijkstra和floyed，其他到算法还有很多，只是都不事很熟悉，用得比较多都假设这两种来，这里为采用都是floyed算法来查找最短路径。要查找最短路径自然就需要最短要查找都两点是哪两点了，做这里也就是景点的编号。输入后可以用floyed找出它们之间都最短路径，然后通过打印函数输出就能够提供给用户了。有了分析，下一步自然就是完成它的程序了，不能用程序描述出来那在好也没有用的。采用floyed算法来完成最短路径的计算告知用户路径和距离：先由用户输入他想查找的两条路径，告诉计算机让计算机去计算；/要查找的两景点的最短距离int shortestdistance()int i,j; printf(请输入要查询的两个景点的编号(1-10的数字编号并用,间隔):); scanf(%d,%d,&i,&j);getchar();if(in|in|j0) /如果输入的景点不存在，则输出错误信息printf(nn对不起，你输入的信息有误！nn);getchar();getchar();elsefloyed();output(i,j);return 1;/shortestdistance计算机根据用户输入的信息开始计算两个景点之间的最短距离，并计算出最短距离所经过的所有景点：/用floyed算法求两个景点的最短路径void floyed()int i,j,k; for(i=1;i=n;i+) /初始化最短路径和最短路径上点j的前驱景点for(j=1;j=n;j+) shortestij=costij;pathij=0; for(k=1;k=n;k+) /floyed算法主程序for(i=1;i=n;i+) for(j=1;j(shortestik+shortestkj) /用path记录从i到j的最短路径上点j的前驱景点的序号shortestij=shortestik+shortestkj;pathij=k;pathji=k; /floyed计算机计算出了对短距离和知道了应该走的景点，那就需要告诉用户了，这才是用户需要知道的，输出计算机得到的信息就可以了：/ 打印两个景点的路径及最短距离 void output(int i,int j)int a,b; /起点和终点a=i; b=j;printf(您要查询的两景点间最短路径是:nn); /输出路径if(shortestij!=INT_MAX)if(ij) printf(%d,b);while(pathij!=0)/ 把i到j的路径上所有经过的景点按逆序打印出来printf(-%d,pathij);if(ij)j=pathij; else i=pathji;printf(%d)最短距离是:%d米nn,a,b,shortestab);printf(按回车键继续！);else printf(%d,a);while(pathij!=0)/ 把i到j的路径上所有经过的景点按顺序打印出来printf(-%d,pathij);if(i%d,b);printf(nn); printf(%d-%d)最短距离是:%5d米nn,a,b,shortestab);printf(“按回车键继续!”); elseprintf(输入错误！不存在此路！nn);printf(n);/output到此为止，所有功能已经分别实现了，通过执行各个函数，就可以完成相应的功能。现在唯一需要做的就是找个函数来将他们“集中起来”，用来组合在一起，才能让它们互相配合，一起工作。这个任务当然是由main()来完成了：void main() int i,j; char k; for(i=0;i=n;i+)for(j=0;j=n;j+)costij=INT_MAX; cost12=cost21=50; /定义各点之间的距离 数组是从1开始的cost23=cost32=100;cost24=cost42=200;cost34=cost43=150;cost14=cost41=250;cost25=cost52=50;cost510=cost105=100;cost56=cost65=150;cost67=cost76=100;cost78=cost87=300;cost79=cost97=200;cost89=cost98=400;cost11=cost22=cost33=cost44=cost55=0; /起点和终点都是同一个地方时自然就没有距离了cost66=cost77=cost88=cost99=cost1010=0;while(1)printf( _n);printf(| 欢迎使用学校导游咨询系统! |n);printf(| |n); printf(| 1.景点信息查询请按 i 键. |n); printf(| 2.景点最短路径查询请按 s 键. |n); printf(| 3.退出系统请按 e 键. |n);printf( _n); printf(学校景点列表:n); printf(1:学校大门t); printf(2:体育馆t);printf(3:求是广场t);printf(4:明德广场t);printf(5:一教tt);printf(6:二教tt);printf(7:三教tt);printf(8:图书馆t);printf(9:四教tt);printf(10:一食堂tn);printf(请选择服务(i,s,e):);scanf(%c,&k); printf(nn);switch(k) case i:case I:printf(进入景点信息查询.nn);introduce();break; case s:case S:printf(进入最短路径查询.nn);shortestdistance();getchar();break; case e:case E:exit(0); /程序中止执行default:printf(输入信息错误！n请重新选择服务！n);getchar();/同样，没有时，输入错误信息也会造成异常！break; /main在main（）里，对各景点之间的直接距离进行了定义，现实中一样。因为学校里各个景点时不会移动的，所以距离也就是固定了的。然后通过一个友好的容易操作的界面面向用户，这样即使用户对计算机一窍不通，也能够轻松的使用者个校园导游咨询系统了。为了使用户能够在进行了一项操作之后还能进行另外的操作，例如：在查询了景点信息后还可以查询最短路径。所以让程序一直执行，直到用户输入退出的信息后才中止程序，这样做程序显得更人性化些！到此，整个程序也就完成了。3程序演示：对于所有执行过程，通过图片最好说明问题了：程序开始如 图2 所示：图2学校的10个景点列表，并提示用户选择需要的服务；选择“景点信息查询”服务时，如图3所示：图3输入了服务代号i ，然后系统提示用户输入想查询的景点的编号，这里我们输入8,查询图书馆的信息，如图4 所示：图4立刻显示了图书馆的信息,并让用户选择服务。在看一下“景点最短路径查询”服务，输入s 即可，如图5 所示：图5例如我们想查询图书馆到学校大门的距离，于是我们按照提示输入：8,1后回车，立即图书馆到学校大门之间的距离和需要经过的地方就显示给我们如图6 所示：图6并友好的提示我们按回车键可以继续操作。按下回车后就又会到了初始界面，这样我们又可以继续选择需要的服务了，如果没有什么需要知道的了，那么按 e 键就可以退出了，如图7 所示：图7整个操作过程就是这样，很简单。结 论 课程设计做完了，一个多星期的时间花在了上面，刚看题目还觉得没有什么问题，可是这正做了才知道问题大了。细节等各方