课程设计报告课程名称数据结构课程设计课题名称交通咨询系统专业通信工程班级通信1001班学号姓名指导教师田娟秀胡瑛曹燚2012年7 月 6 日湖南工程学院课程设计任务书课程名称数据结构课题交通咨询系统专业班级通信1001班学生姓名学号指导老师田娟秀胡瑛曹燚审批田娟秀任务书下达日期2012 年7 月 1 日任务完成日期2012 年7 月 6 日1.1任务书课题六：交通咨询系统：在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也很感兴趣。
对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。
图中顶点表示城市，边表示城市之间的交通关系。
设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到达另外一个城市顶点之间的最短路径（里程）的问题。
要求完成以下功能：(a) 以图中顶点表示湖南省各市(至少包括8个以上的城市)，存放城市名称、代号、简介等信息，以边表示路径，存放路径长度等有关信息，先建立交通网络图的存储结构；(b) 为用户提供图中任何城市有关信息的查询；(c) 为用户提供任意城市的交通查询,即查询任意两个城市之间的一条最短路径。
(d) 为用户提供指定城市的交通查询，即查询指定城市到其他城市之间的最短路径。
选做内容：（1）提供图的编辑功能：增、删城市；增删路径；修改已有信息等；（2）交通图的仿真界面。
1.2 选题方案：所选题目根据学号确定，学号模6加1，即（学号%6+1）。
如你的学号为9，则所选题目号为：9%6+1＝（题目4）。
注意，所有的课题都要求用图形方式演示步骤和结果。
同学们可以自己针对数据结构课程中所讲算法来设计一个演示过程的算法。
1.3设计要求：1.3.1 课程设计报告规范（1）需求分析a.程序的功能。
b.输入输出的要求。
（2）概要设计a.程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。
b.课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。
（3）详细设计a.采用C语言定义相关的数据类型。
b．写出各模块的类C码算法。
c.画出各函数的调用关系图、主要函数的流程图。
（4）调试分析以及设计体会a.测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。
b.程序调试中遇到的问题以及解决问题的方法。
c.课程设计过程经验教训、心得体会。
（5）使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。
（6）书写格式a.设计报告要求用A4纸打印成册：b.一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。
（7）附录源程序清单（带注释）1.3.2 考核方式指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。
具体考核标准包含以下几个部分：（1）平时出勤（占10%）（2）系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）（3）程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）（4）设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。
（5）独立完成情况（占10%）。
1.3.3 课程验收要求（1）运行所设计的系统。
（2）回答有关问题。
（3）提交课程设计报告。
（4）提交软盘（源程序、设计报告文档）。
（5）依内容的创新程度，完善程序情况及对程序讲解情况打分。
2 进度安排第 20 周：星期一 8：00——12：00 上课星期一 14：30——18：30 上机星期二 14：30——18：30 上机星期三 8：00——12：00 上机附：课程设计报告装订顺序：封面、任务书、目录、正文、评分表、附件（A4大小的图纸及程序清单）。
正文的格式:一级标题用3号黑体,二级标题用四号宋体加粗,正文用小四号宋体;行距为22。
正文的内容:一、课题的主要功能；二、课题的功能模块的划分（要求画出模块图）；三、主要功能的实现（至少要有一个主要模块的流程图）；四、程序调试；五、总结；六、附件（所有程序的原代码，要求对程序写出必要的注释）。
正文总字数要求在5000字以上（不含程序原代码）。
目录一．需求分析 (7)1.1程序的功能 (7)1.2输入输出的要求 (7)二．概要设计 (7)2.1程序的模块组成 (7)2.2每个模块的功能 (8)2.3存储数据及其关系 (10)三．详细设计 (10)3.1采用C语言定义相关类型 (10)3.2写出各模块的类C码算法 (11)3.3调用关系图 (13)四．调试分析以及心得体会 (15)4.1测试数据 (15)4.2心得体会 (17)五．使用说明 (18)六．附录 (19)七．评分表 (24)一．需求分析1.1 程序的功能在交通网络非常发达的今天，人们出差、旅游或做其他出行时，不仅关心节省交通费用，而且对里程和所需时间等问题也很感兴趣。
对于这样一个人们关心的问题，可用一个图结构来表示交通网络系统，利用计算机建立一个交通咨询系统。
图中顶点表示城市，边表示城市之间的交通关系。
设计一个交通咨询系统，能让旅客咨询从任一个城市顶点到达另外一个城市顶点之间的最短路径（里程）的问题。
要求完成以下功能(a) 以图中顶点表示湖南省各市(至少包括8个以上的城市)，存放城市名称、代号、简介等信息，以边表示路径，存放路径长度等有关信息，先建立交通网络图的存储结构；(b) 为用户提供图中任何城市有关信息的查询；(c) 为用户提供任意城市的交通查询,即查询任意两个城市之间的一条最短路径。
(d) 为用户提供指定城市的交通查询，即查询指定城市到其他城市之间的最短路径。
选做内容：（1）提供图的编辑功能：增、删城市；增删路径；修改已有信息等；（2）交通图的仿真界面。
1.2 输入输出的要求在用户刚进入主界面后，系统就会提示输入建立交通网络的储存结构，输入顶点个数和和边数，随后会有系统进行提示输入顶点信息以及他们的权值，即I,j和w，依次根据边的信息个数进行输入。
随之进行的是查询页面，输入选择按钮进行功能查询选择。
如，选择1：表示的是查询任意两个城市之间的一条最短路径，选择2：表示的是查询指定城市到其他城市之间的最短路径，选择0：表示你将要退出程序查询系统。
二．概要设计2.1 程序的模块组成本程序主要有三个模块组成，他们分别是：邻接矩阵建立有向图，查询任意两个城市之间的一条最短路径，查询指定城市到其他城市之间的最短路径。
三个模块的概图：图 2.12.2 每个模块的功能邻接矩阵建立交通网络Y任意两个城市的 最短距离查询 两个指定城市的 最短距离查询用户进入系统交通网络构建结果，退出系统开始输入n,e 输入i,j,wk<=e,k+++结束N图 2.2.1查询指定城市到其他城市之间的最短路径开始输入顶点v狄克斯特拉算法输出路径,距离结束图 2.2.2查询任意两个城市之间的一条最短路径：开始输出路径,距离输入起点v，终点w结束调用弗洛伊德算法图2.2.32.3 存储数据及其关系比如下列五个数据之间的存储及其关系1 25 34图 2.3上图说明：上图各个节点之间会有一条或者两条边，当输入他们的信息时根据他们的方向进行有向图的存储。
并且每两个顶点之间（单向）都会有一个值w，即权值。
如顶点1和2之间可以设置他的权值是2，顶点2到顶点5的权值可以是3，顶点5到顶点2的权值可以是4，等等。
三．详细设计3.1 采用C语言定义相关类型1．定义一个，用来存储顶点信息。
typedef struct{VertexType vexs[MAX];Adjmatrix arcs[MAX][MAX];}MGraph;.. 2．定义一个Dijkstra函数void Dijkstra(MGraph *G,int v,int n);2．定义一个Floyd函数void Floyd(MGraph *G,int n);3.2 写出各模块的类C码算法邻接矩阵构造图结构函数数据类型定义：typedef struct{VertexType vexs[MAX];Adjmatrix arcs[MAX][MAX];}MGraph;void CreateMGraph(MGraph *G,int n,int e)//邻接矩阵构成有向图{int i,j,k,w;for(i=1;i<=n;i++)G->vexs[i]=(char)i;for(i=1;i<=n;i++)for(j=1;j<=n;j++)G->arcs[i][j]=IDF;printf("输入%d条边的i,j及w: \n",e);for(k=1;k<=e;k++){scanf("%d,%d,%d",&i,&j,&w);G->arcs[i][j]=w;}printf("有向图的存储结构建立完毕!\n");其中vexs[MAX]保存顶点信息，arcs[MAX][MAX]用于保存边与边之间的信息。
在构建时通过输入的边数i，j作为矩阵的行、列确定顶点的出度和入度。
用邻接矩阵方法存储图。
Dijkstra算法；基本思想：设G（V,E）是一个带权有向图，把图中的顶点集合V分成两组，第一组为已经求出的最短路径的顶点集合（用S表示，初始时S中只有一个原点，以后每求得一条最短路径就加入的集合S 中，知道全部顶点都加入到集合中），第二组，为其余未确定最短路径的顶点集合（用U 表示），按最短路径长度的递增次序依次把第二组的顶点就如S 中。
如果两个顶点之间有权值，并且各个路径的权值不同，就把最小的作为顶点与顶点的最短距离。
y x z 图 3.3.1如图所示 若x+y<z ，则最短的路径就是v=>k=>u 。
同理若x+y<z ，则最短的路径就是v=>u ，D [v1]=0;S[v1]=1; //原点编号放入s 中 for(i=2;i<n;i++) { min=IDF;for(w=1;w<=n;w++) if(!S[w]&&D [w]<min) { v=w;min=D [w];}S[v]=1; //修改顶点u 放入s 中 for(w=1;w<=n;w++) if(!S[w]&&(D [v]+G->arcs[v][w]<D [w])) { D [w]=D [v]+G->arcs[v][w]; P [w]=v;}}弗洛伊德算法：用邻接矩阵保存图存储后，另外需要存一个二维数组A 存放当前顶点之间的最短路径长度。