数据结构课程设计交通咨询系统.docx

《数据结构课程设计交通咨询系统.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计交通咨询系统.docx（29页珍藏版）》请在三一文库上搜索。

1、海前N科冬陇课程设计报告课程名称数据结构课程设计课题名称交通咨询系统专业通信工程班级通信1001班学号姓名指导教师 田娟秀胡瑛曹籁2012年 7 月 6日湖南工程学院课程设计任务书课程名称数据结构课 题交通咨询系统专业班级 通信1001班学生姓名学 号指导老师 田娟秀胡瑛曹籁审 批 田娟秀任务书下达日期2012年 7月1日1.1 任务书课题六：交通咨询系统：在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通 费用，而且对里程和所需时间等问题也很感兴趣。对于这样一个人们关心的问题，可用 一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。图中顶点表示城 市，边表示

2、城市之间的交通关系。设计一个交通咨询系统，能让旅客咨询从任一个城市 顶点到达另外一个城市顶点之间的最短路径(里程)的问题。要求完成以下功能：(a)以图中顶点表示湖南省各市(至少包括8个以上的城市)，存放城市名称、代号、 简介等信息，以边表示路径，存放路径长度等有关信息，先建立交通网络图的存储结构；(b)为用户提供图中任何城市有关信息的查询；(c)为用户提供任意城市的交通查询，即查询任意两个城市之间的一条最短路径。(d)为用户提供指定城市的交通查询，即查询指定城市到其他城市之间的最短路 径。选做内容：(1)提供图的编辑功能：增、删城市；增删路径；修改已有信息等；(2)交通图的仿真界面。1.2 选

3、题方案：所选题目根据学号确定，学号模 6加1,即(学号6+如你的学号为9,则 所选题目号为：9%6+ (题目4)。注意，所有的课题都要求用图形方式演示步骤 和结果。同学们可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法。1.3 设计要求：1.3.1 课程设计报告规范(1)需求分析a.程序的功能。b.输入输出的要求。(2)概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模 块的功能。b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。(3)详细设计a.采用C语言定义相关的数据类型。b.写出各模块的类C码算法。c

4、.画出各函数的调用关系图、主要函数的流程图。(4)调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果 和含有错误的输入及输出结果。b.程序调试中遇到的问题以及解决问题的方法。c.课程设计过程经验教训、心得体会。(5)使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。(6)书写格式a.设计报告要求用A4纸打印成册：b. 一级标题用3号黑体，二级标题用四号宋体加粗，正文用小四号宋体；行距为22。(7)附录源程序清单(带注释)1.3.2考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新 精神和设计报告等进行综

5、合考评，并按优秀、良好、中等、及格和不及格五个等级给出 每位同学的课程设计成绩。具体考核标准包含以下几个部分：(1)平时出勤(占10%(2)系统需求分析、功能设计、数据结构设计及程序总体结构合理与否(占 10%(3)程序能否完整、准确地运行，个人能否独立、熟练地调试程序(占 40%(4)设计报告(占30%注意：不得抄袭他人的报告(或给他人抄袭)，一旦发现，成绩为零分。(5)独立完成情况(占10%。（1）运行所设计的系统。（2）回答有关问题。（3）提交课程设计报告。（4）提交软盘（源程序、设计报告文档）。（5）依内容的创新程度，完善程序情况及对程序讲解情况打分2进度安排第20周：星期一 8 :

6、0012: 00 上课星期一 14 : 3018: 30 上机 星期二14 : 3018: 30 上机 星期三8 : 0012: 00 上机附：课程设计报告装订顺序：封面、任务书、目录、正文、评分表、附件（A4大小的图纸及程序清单）正文的格式：一级标题用3号黑体，二级标题用四号宋体加粗，正文用小四号宋体；行距为22。正文的内容：一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。正文总字数要求在 5000字以上（不含程序原代码）。51 . 需求分析 7

7、1.1 程序的功能 71.2 输入输出的要求 72 .概要设计 72.1 程序的模块组成 72.2 每个模块的功能 82.3 存储数据及其关系 103 .详细设计 103.1 采用C语言定义相关类型 103.2 写出各模块的类C码算法113.3 调用关系图134 .调试分析以及心得体会 154.1 测试数据 154.2 心得体会 17五使用说明186 . 附录 197 .评分表 2427一.需求分析1.1 程序的功能在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通 费用，而且对里程和所需时间等问题也很感兴趣。对于这样一个人们关心的问题，可用 一个图结构来表示交通网络系统

8、，利用计算机建立一个交通咨询系统。图中顶点表示城 市，边表示城市之间的交通关系。设计一个交通咨询系统，能让旅客咨询从任一个城市 顶点到达另外一个城市顶点之间的最短路径(里程)的问题。要求完成以下功能(a)以图中顶点表示湖南省各市(至少包括8个以上的城市)，存放城市名称、代号、 简介等信息，以边表示路径，存放路径长度等有关信息，先建立交通网络图的存储结构；(b)为用户提供图中任何城市有关信息的查询；(c)为用户提供任意城市的交通查询，即查询任意两个城市之间的一条最短路径。(d)为用户提供指定城市的交通查询，即查询指定城市到其他城市之间的最短路 径。选做内容：(1)提供图的编辑功能：增、删城市；增

9、删路径；修改已有信息等；(2)交通图的仿真界面。1.2 输入输出的要求在用户刚进入主界面后，系统就会提示输入建立交通网络的储存结构，输入顶点个 数和和边数，随后会有系统进行提示输入顶点信息以及他们的权值，即 I,j和w,依次 根据边的信息个数进行输入。随之进行的是查询页面，输入选择按钮进行功能查询选择。 如，选择1:表示的是查询任意两个城市之间的一条最短路径，选择 2:表示的是查询 指定城市到其他城市之间的最短路径，选择 0:表示你将要退出程序查询系统。二.概要设计2.1 程序的模块组成本程序主要有三个模块组成，他们分别是：邻接矩阵建立有向图，查询任意两 个城市之间的一条最短路径，查询指定城市

10、到其他城市之间的最短路径。三个模块的概图:图2.12.2每个模块的功能邻接矩阵建立交通网络图 2.2.1查询指定城市到其他城市之间的最短路径图 2.2.2查询任意两个城市之间的一条最短路径:图 2.2.32.3存储数据及其关系比如下列五个数据之间的存储及其关系图2.3上图说明：上图各个节点之间会有一条或者两条边，当输入他们的信息时根据他们的方向进行有向图的存储。并且每两个顶点之间（单向）都会有一个值 w,即 权值。如顶点1和2之间可以设置他的权值是2,顶点2到顶点5的权值可以是3, 顶点5到顶点2的权值可以是4,等等。三.详细设计3.1 采用C语言定义相关类型1 .定义一个，用来存储顶点信息。

11、typedef structVertexType vexsMAX;Adjmatrix arcsMAXMAX;MGraph;,.2.定义一个 Dijkstra函数void Dijkstra(MGraph *G ,int v,int n);2 .定义一个Floyd函数void Floyd(MGraph *G ,int n);3.2 写出各模块的类C码算法邻接矩阵构造图结构函数数据类型定义：typedef structVertexType vexsMAX;Adjmatrix arcsMAXMAX;MGraph;void CreateMGraph(MGraph *G,int n,int e)邻接矩阵构

12、成有向图int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=IDF;printf(输入%d 条边的 i,j 及 w: n,e);for(k=1;karcsij=w;printf(有向图的存储结构建立完毕！n);其中vexsMAX保存顶点信息，arcsMAXMAX用于保存边与边之间的信 息。在构建时通过输入的边数i, j作为矩阵的行、列确定顶点的出度和入度。用 邻接矩阵方法存储图。Dijkstra 算法；基本思想：设G (V,E)是一个带权有向图，把图中的顶点集合 V分成两组, 第一组为已经求出的最短路径的顶点集合

13、(用S表示，初始时S中只有一个原点, 以后每求得一条最短路径就加入的集合 S中，知道全部顶点都加入到集合中)，第二组，为其余未确定最短路径的顶点集合（用 U表示），按最短路径长度的递 增次序依次把第二组的顶点就如 S中。如果两个顶点之间有权值，并且各个路径的权值不同,如图所示 若x+yk=u。同理若x+yu,D v1=0;Sv1=1;/原点编号放入s中for(i=2;in;i+) min=IDF;for(w=1;w=n;w+)if(!Sw&D wmin)v=w;min=D w;Sv=1; 修改顶点u放入s中for(w=1;warcsvwarcsvw;P w=v；弗洛伊德算法:用邻接矩阵保存图存

14、储后，另外需要存一个二维数组A存放当前顶点之间的最短路径长度。分量Aij表示当前顶点i到j的最短路径长度。弗洛伊德算法的基本 思维是递推产生一个矩阵序列 A。，A1, A2,.Ak,An,其中Ak皿表示从顶点到 vi到顶点vj的路径上所经过的顶点编号不大于 k的最短路径长度。Aij=costijA(k+1)ij=minAkij,Aki+1k+1+Akk+1j弗洛伊德主要算法，若 Akij已求出，顶点i到顶点k+1的路径长度为Akik+1, 顶点路径长度为 Akij,顶点k+1到顶点j的路径长度为Akk+1j,如果此时 Akik+1+Akk+1j卜 Akij,则将原来的顶点i到顶点j的路径改为顶

15、点，否则不 需要修改顶点i至”的路径。Aki,j图 3.3.2若 Akik+1+Akk+1 j Akij,修改路径过程：for(k=1;k=n;k+)for(i=1;i=n;i+)for(j=1;j=n;j+) if(Dik+Dkj1长度=0, 1=2长度=3, 1=3长度=3+3=8, 1=4长度=3+6=9;和下图完 全一致图 4.4.33 .为保证结果正确换一个顶点进行：如图 4.4.4 ,计算可知结果正确路径1-4-22324-2植入顶点8 鹿径长度S&MMMMM 卜图 4.4.44,查询一个顶点到另一个顶点的最短路径：如图 4.4.5 ,经计算：可知结 果正确。图 4.4.55.选择

16、0进行退出程序的操作。如下图4.4.6MM- 1 MiM Mi M：苴一杳询城市/ |b的路径一MICJCX1 .查询一个城市到所有城市困曩短路隹2 .查询任意的两个城市之间的鲁短路楼请噂崔工踏着选择:目送出:0结束录最短路径,再见？Press any key to continue.图 4.4.64.2 心得体会“平时不好干，遇事只能看，经过这几天的数据结构的课程设计对这句话这 真的别有一番的体会。“成功只属于有准备的人”，真的，这几天的课程设计让你不得不 想起这句话。俗话说“厚积薄发”，前期的积累，说不定什么时候就能够用上。这次就 是这样，前期没有积累足够的知识储备，以至于拿到课程设计的任

17、务书时感觉无所适从， 不知道从何下手，真是一一老虎吃刺猬，无从下口。所以，在第一次上课时就什么都没 有做，就那样在实验室里干看着别人在热热火火的搞自己的课程设计。于是乎自己只能 看书，把自己以前丢失的都补回来。这为自己的不学习，导致这次的课设变得如此的艰难。当别人都已经快答辩了，我 的程序还只有那可怜的几行，无独有偶，也就是这样，我一度准备放弃，心想就直接从 网上拷贝一个就行了。可是，许三多的一句话敲醒了我，不抛弃，不放弃，对，不能放 弃。就这样。我坚持了下去，开始从各个方面入手，查书，查资料，一旬一句的敲，一 点一点的写，不会的问老师，请教同学。终于功夫不负有心人。临到答辩结束的我赶上 了末

18、班车。顺利的通过了答辩，抹掉分数的高低吧。还是有小小的成就感的。通过这次的课程设计我有懂得了好多数据结构的知识，以前上课没有听的，不知道 的，这次都有所了解了，像有向图的构建，弗洛伊德算法，迪克斯特拉算法。这些知识 从曾经的听说到现在的了解，进了一大步。不但如此，这次的课设也是我感觉到了数据 结构的强大与神奇。渐渐的爱上他了。不仅让我了解了数据结构更加深了对它与 C语言 的联系的理解。课设已经结束了。真心的感谢我们的田老师，这么大热的天，当其他老师都在空调 房里舒服时，她还是冒着火烈的太阳，赶过来给我们指导。想让我们学到更多的知识。 在这里，深情的说一句：老师，您辛苦了，谢谢您。同样感谢另外两

19、个老师的知道。谢 谢你们。五.使用说明第一步：运行程序。进入主界面。进一步提示输入图中的顶点，边数。* D:Progr5nn FilesVisual Studio MyProjwDebugwvv.exe网络图的存i, j, w根据自第二步：输入边之后按回车，进入图的构建。依次输入各个边的的信息, 己所设的图的不同进行设置。WFUTJUHT110-U IF输入舒顶点.边数44输入彝边的士 刀及记12 3,343 4 6,15存向图的存储结构建立完毕，* 赤第三步：进入程序查询区域。有选择 1或2或0分别表示你所选择的查询不同方式。(1)选择1表示查询一个顶点至其他所有顶点的最短路径。会提示用户进

20、行查 询定点的选择。系统将会显示你要查询的最短路径。(2)选择2表示查询任意两个点之间的最短路径，输入用户所要查询的起点和终点就会显示你要查询的最短路径。(3)选择0表示用户将要退出系统wyml.- 丁1卜r一F*查询城市之间的路径*1 .查询一不城市到所有城市普暮短路任 .2 .查询任意的两个城市之间的霰短路桂事选择：1 or 2：5：组退出:D 淖录最短路径.再见，t*ess any key to continue.六.附录#include#include#define MAX 100#define IDF 32767/最大顶点数typedef char VertexType;typede

21、f int Adjmatrix;typedef struct/设置数组保存顶点信息VertexType vexsMAX;Adjmatrix arcsMAXMAX;MGraph;int D1MAX,P1MAX;int DMAXMAX,PMAXMAX;void CreateMGraph(MGraph *G,int n,int e); 建立图的存储结构void Dijkstra(MGraph *G ,int v1,int n);狄克特求最短路径void Floyd(MGraph *G,int n);弗洛伊德算法void main() MGraph *G;int m,n,e,v,w,k;int xz=

22、1;G=(MGraph *)malloc(sizeof(MGraph);printf(* 欢迎进入交通咨询系统*n);printf(交通网络图的存储结构n);printf(输入图中顶点，边数n, e:); scanf(%d %d”,&n,&e);CreateMGraph(Gn,e);while(xz!=0) printf(* 下一步*n);printf(*查询城市之间的路径 *n)；printf（1.查询一个城市到所有城市的最短路径n）;printf（2.查询任意的两个城市之间的最短路径n）;printf(请选择：1 or 2:n );printf(选择:0 退出：);scanf(%d,&xz

23、);if(xz=2)Floyd(G,n); /调用费洛伊德算法 printf(输入起点，终点：v,w:); scanf(%d %d,&v,&w);k=Pvw;/k保存最短路径长度if(k=0)printf(顶点 至ij %d 无路径!n,v,w);else printf(从顶点%d到的最短路径是：%d,v,w,v);while(k!=w)printf(-%d,k);/输入后继结点继续找下一个顶点k=Pkw;printf(-%d,w); / 输出终点printf(路径长度：dn,Dvw);elseif(xz=1)printf(输入顶点 v:);scanf(%d,&v);Dijkstra(G,v,

24、n);调用狄克斯特拉算法printf(结束求最短路径，再见！ n);void CreateMGraph(MGraph *G,int n,int e)邻接矩阵构成有向图int i,j,k,w；for(i=1;ivexsi=(char)i;for(i=1;i=n;i+)for(j=1;jarcsij=IDF;printf(输入 %d 条边的 i,j 及 w: n,e);for(k=1;karcsij=w;printf(有向图的存储结构建立完毕！n);void Dijkstra(MGraph *G,int v1,int n)/狄克特斯求最短路径用于求某一顶点到其他顶点 的路径及长度int D2MAX

25、,P2MAX;int v,i,w,min;int SIDF;for (v=1;varcsv1v;if(D2MIDF)/路径初始化P2v=v1;elseP2M=0;D2v1=0;Sv1=1;原点编号放入s中for(i=2;in;i+)min=IDF;for(w=1;w=n;w+)if(!Sw&D2wmin)v=w;min=D2w;Sv=1; 修改顶点u放入s中for(w=1;warcsvwarcsvw;P2w=v;printf(路径长度路径n);for(i=1;i=n;i+)/循环输出至其他每个顶点的路径printf(%8d,D2i);printf(%8d,i); v=P2i;while(v!=

26、0)printf(-%d,v);v=P2v;printf(n);void Floyd(MGraph *G,int n) 费洛伊德算法int i,j,k,v,w;for(i=1;i=n;i+)/设置路径长度d和路径path的初值for(j=1;jarcs皿!=IDF) Pij=j； elsePij=0；D皿产G-arcsi皿 for(k=1;k=n;k+) for(i=1;i=n;i+)for(j=1;j=n;j+) if(Dik+DkjD皿) Dij=Dik+Dkj; 修改长度Pij=Pik;七.评分表计算机与通信学院课程设计评分表课程名称：项目评价设计方案的合理性与创造性设计与调试结果设计说明书的质量答辩陈述与回答问题情况课程设计周表现情况综合成绩教师签名：日 期：（注：1.此页附在课程设计报告之后；2.综合成绩按优、良、中、及格和不及格五级评定。）25