武汉市公共交通指引系统应用与开发课程设计.doc

武汉工程大学
计算机科学与工程学院

综合设计报告

设计名称： 应用软件综合设计
设计题目： 武汉市公共交通指引系统应用与开发
学生学号： 1205080311
专业班级： 2012级计算机工程3班
学生姓名： 卢文聪
学生成绩：
指导教师（职称）： 庄朋（讲师）
完成时间： 14年12月15日 至 14年12 月26日

武汉工程大学计算机科学与工程学院 制

说明：
1、报告中的第一、二、三项由指导教师在综合设计开始前填写并发给每个学生；四、五两项（中英文摘要）由学生在完成综合设计后填写。
2、学生成绩由指导教师根据学生的设计情况给出各项分值及总评成绩。
3、指导教师评语一栏由指导教师就学生在整个综合设计期间的表现、设计完成情况、报告的质量及答辩等方面，给出客观、全面的评价。
4、所有学生必须参加综合设计的答辩环节。凡不参加答辩者，其成绩一律按不及格处理。答辩小组成员应由2人及以上教师组成。
5、报告正文字数一般应不少于5000字，也可由指导教师根据本门综合设计的情况另行规定。
6、平时表现成绩低于6分的学生，其综合设计成绩按不及格处理。
7、此表格式为武汉工程大学计算机科学与工程学院提供的基本格式（适用于学院各类综合设计），各教研室可根据本门综合设计的特点及内容做适当的调整，并上报学院批准。

答辩记录表

学生姓名： 学号： 班级： 12计算机工程1班
答辩地点： 计算机工程专业机房
答辩内容记录：

答辩成绩
合计
分值
各项分值
评分标准
实际得分
合计得分
备注
25
10
在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。

15
在规定时间内能准确、完整、流利地回答教师所提出的问题。

答辩小组成员（签字）：

2014 年 12 月 26 日

成绩评定表

学生姓名： 学号： 班级：
类别
合计
分值
各项分值
评分标准
实际得分
合计得分
备注
平时表现
10
10
按时参加综合设计，无旷课、迟到、早退、违反实验室纪律等情况。

完成情况
30
20
按设计任务书的要求完成了全部任务，能完整演示其设计内容，符合要求。

10
能对其设计内容进行详细、完整的介绍，并能就指导教师提出的问题进行正确的回答。

报告质量
35
10
报告文字通顺，内容翔实，论述充分、完整，立论正确，结构严谨合理；报告字数符合相关要求，工整规范，整齐划一。

5
课题背景介绍清楚，综述分析充分。

5
设计方案合理、可行，论证严谨，逻辑性强，具有说服力。

5
符号统一；图表完备、符合规范要求。

5
能对整个设计过程进行全面的总结，得出有价值的结论或结果。

5
参考文献数量在3篇以上，格式符合要求，在正文中正确引用。

答辩情况
25
10
在规定时间内能就所设计的内容进行阐述，言简意明，重点突出，论点正确，条理清晰。

15
在规定时间内能准确、完整、流利地回答教师所提出的问题。

总评成绩

指导教师评语

指导教师： （签字） 日期： 2014 年 12 月 26 日

一、综合设计目的、条件、任务和内容要求：
《算法与数据结构》在计算机科学中是一门核心专业基础课，在整个计算机课程体系中处于承上启下的核心地位，它一方面扩展和深化在离散数学、程序设计语言等课程学到的基本技术和方法，一方面为进一步学习其它专业课奠定坚实的理论与实践基础。课程的主要任务是学习数据的逻辑结构，存储结构以及相关的算法设计。《应用软件综合设计》是计算机科学与技术专业学生的一门实践课程，是学习完数据结构课程后的课程设计，本课程的目的是使学生学会分析待加工处理数据的特性，以便选择适当的逻辑结构、存储结构以及进行相应的算法设计。在教给学生数据结构选择和算法设计的同时，培养学生的抽象思维能力、逻辑推理能力和形式化思维方法，增强分析问题和解决问题的能力。
武汉市公共交通指引系统是一个可以方便广大市民乘车的一个系统，有着较大的现实意义。本综合设计的任务是：设计并开发一个简化版的武汉市公共交通指引系统，使学生掌握Dijkstra算法培养学生利用C++语言编写程序以及调试程序的能力，运用数据结构知识解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。
内容：分两个层次
层次一：显示一条最短路径（经过站数最少的路线），如果有两条以上最短路线，则按换乘次数排序显示。显示每一条路线时，不仅要显示应搭乘的车次，还要显示应搭乘站的站名。
层次二：显示一条最省时路线（换乘车次数最少的路线），如果有两条以上最省时路线，则按经过站数排序显示。

二、进度安排：
第16周(12.15-12.16) ： 学生熟悉课题的任务和要求，查阅相关文献和资料，并做好编码准备

第16周 (12.17-12.19) ：程序编码、调试

第17周 (12.22-12.25) ：程序编码、调试和测试，书写报告

第17周 (12.26)： 答辩、检查、验收、递交设计报告

三、应收集资料及主要参考文献：
[1]谭浩强.C程序设计（第三版）. 北京: 清华大学出版社,2005.
[2]谭浩强.C程序设计题解与上机指导.北京：清华大学出版社,2005.
[3]谭浩强.C程序设计教程.北京：清华大学出版社,2007.
[4]谭浩强.C++程序设计.北京：清华大学出版社，2004.
[5]李春葆.数据结构教程（第4版）[M].北京：清华大学出版社，2014.
[6]李春葆.数据结构教程与上机实验指导（第4版）[M].北京：清华大学出版社，2014.

四、摘要：
数据结构是计算机科学与技术专业的一门必修的、重要的专业基础课，是计算机程序设计的重要理论技术基础。通过数据结构科的学习，不仅可以使同学们掌握数据结构的基本特性、数据的逻辑结构和数据的存储结构及典型算法和使用方法，而且能够训练学生运用数据结构和算法进行具体应用问题的程序设计。主要内容包括算法计算法分析、面向对象程序设计与C++、线性表、栈和队列、串、数组和广义表、树、图、查找、排序、递归和文件等内容。作为计算机专业的学生，应该努力学好各种计算机语言，培养编程创新的能力。
运用数据结构的知识编写一个武汉的公交系统武汉市公共交通指引系统是一个可以方便广大市民乘车的一个系统，有着较大的现实意义。本综合设计的任务是：设计并开发一个简化版的武汉市公共交通指引系统，使学生掌握Dijkstra算法培养学生利用C++语言编写程序以及调试程序的能力，运用数据结构知识解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。
在此次课程设计中，我设计的内容是图的相关操作，采用图的邻接矩阵存储，即用一维数组存储图中顶点的信息，用二维数组存储图中边的信息（即各顶点之间的邻接关系）。 邻接表存储结构是基于顺序存储与链接存储相结合的存储方法，基本思想是：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有顶点的边表的头指针和存储顶点信息的一维数组构成了顶点表。
关键词：数据结构；Dijkstra算法；程序设计

五、Abstract：
Data structure in computer science and technology professional a compulsory,an important professional basic course, is an important theoretical and technical foundation of computer program design. Through the data structure of learning,can not only make students grasp the basic characteristics of the data structure,the logic structure and data storage structure of data and the typical algorithm and method of use, but also can train students to use the data structure and algorithm of program design for application problems. The main contents includeanalysis, object oriented programming and C++, linear list, stack and queue, strings,  arrays and generalized list, tree, graph, searching, sorting, recursive andfile content calculation algorithm. As a computer professional students,  should try to learn  all kinds of computer programming language, cultivating the ability ofinnovation.
Using the data structure knowledge of the preparation of transit system in WuhanCity public traffic guidance system a Wuhan is a convenient public bus of a system, is of great significance. The comprehensive design task is to: Wuhan City public traffic guidance system to design and develop a simplified version of the Dijkstra algorithm, to enable students to master the cultivation of students' ability to use the language of C++ to program and debug the program, the ability to use the data structure of knowledge to solve practical problems, to lay a solidfoundation for subsequent computer professional courses.
In this course design, I design the content is related to the operation of the graph, using the graph adjacency matrix storage, namely using vertex one-dimensional array storage in the graph information, a two-dimensional array of storage mapedge information (i.e. each vertex adjacency relationship between). Adjacency list storage structure is the storage method of sequential storage and storage based on the combination of link, the basic idea is: for each vertex VI of graph,  alladjacent to the vertices of VI chain into a single linked list, called the vertex VIedge table (for directed graph is called a side table, a one-dimensional array) all the vertices of the edge table head pointer and memory vertex information forms a vertex table.
Keywords：Data structure；Dijkstra algorithm；Program design

武汉工程大学计算机科学与工程学院 综合设计报告
目录
摘 要 II
Abstract III
第一章 课题背景 1
1.1 课题背景 1
1.2课题内容 1
第二章 设计简介及设计方案论述 4
2.1 设计简介 4
2.2问题分析 5
第三章 详细设计 6
3.1主要函数流程图 6
第四章 设计结果及分析 8
4.1 设计结果 8
总 结 9
致 谢 10
参考文献 11
附录 12

摘 要
数据结构是计算机科学与技术专业的一门必修的、重要的专业基础课，是计算机程序设计的重要理论技术基础。通过数据结构科的学习，不仅可以使同学们掌握数据结构的基本特性、数据的逻辑结构和数据的存储结构及典型算法和使用方法，而且能够训练学生运用数据结构和算法进行具体应用问题的程序设计。主要内容包括算法计算法分析、面向对象程序设计与C++、线性表、栈和队列、串、数组和广义表、树、图、查找、排序、递归和文件等内容。作为计算机专业的学生，应该努力学好各种计算机语言，培养编程创新的能力。
运用数据结构的知识编写一个武汉的公交系统武汉市公共交通指引系统是一个可以方便广大市民乘车的一个系统，有着较大的现实意义。本综合设计的任务是：设计并开发一个简化版的武汉市公共交通指引系统，使学生掌握Dijkstra算法培养学生利用C++语言编写程序以及调试程序的能力，运用数据结构知识解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。
在此次课程设计中，我设计的内容是图的相关操作，采用图的邻接矩阵存储，即用一维数组存储图中顶点的信息，用二维数组存储图中边的信息（即各顶点之间的邻接关系）。 邻接表存储结构是基于顺序存储与链接存储相结合的存储方法，基本思想是：对于图的每个顶点vi，将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表），所有顶点的边表的头指针和存储顶点信息的一维数组构成了顶点表。
关键词：数据结构；Dijkstra算法；程序设计

Abstract
Data structure in computer science and technology professional a compulsory,an important professional basic course, is an important theoretical and technical foundation of computer program design. Through the data structure of learning,can not only make students grasp the basic characteristics of the data structure,the logic structure and data storage structure of data and the typical algorithm and method of use, but also can train students to use the data structure and algorithm of program design for application problems. The main contents includeanalysis, object oriented programming and C++, linear list, stack and queue, strings,  arrays and generalized list, tree, graph, searching, sorting, recursive andfile content calculation algorithm. As a computer professional students,  should try to learn  all kinds of computer programming language, cultivating the ability ofinnovation.
Using the data structure knowledge of the preparation of transit system in WuhanCity public traffic guidance system a Wuhan is a convenient public bus of a system, is of great significance. The comprehensive design task is to: Wuhan City public traffic guidance system to design and develop a simplified version of the Dijkstra algorithm, to enable students to master the cultivation of students' ability to use the language of C++ to program and debug the program, the ability to use the data structure of knowledge to solve practical problems, to lay a solidfoundation for subsequent computer professional courses.
In this course design, I design the content is related to the operation of the graph, using the graph adjacency matrix storage, namely using vertex one-dimensional array storage in the graph information, a two-dimensional array of storage mapedge information (i.e. each vertex adjacency relationship between). Adjacency list storage structure is the storage method of sequential storage and storage based on the combination of link, the basic idea is: for each vertex VI of graph,  alladjacent to the vertices of VI chain into a single linked list, called the vertex VIedge table (for directed graph is called a side table, a one-dimensional array) all the vertices of the edge table head pointer and memory vertex information forms a vertex table.
Keywords：Data structure；Dijkstra algorithm；Program design

- 15 -
第一章 课题背景
1.1 课题背景
在科技日新月异的今天，电脑成为人的生活中不可缺少的一部分。作为计算机专业的学生，应该充分利用所学知识，把实际问题转移到电脑上去，通过电脑的编程，使复杂问题简单化，深奥问题浅显化，抽象问题具体化。在非数值计算中，处理对象已从简单数值发展到具有一定结构的数据，这就需要讨论如何有效的组织计算机的存储，并在此基础上有效的实现对象的运算，数据结构就是研究与解决这些问题的重要基础。在结构上呈积木式，注重实践应用、各种常用数据结构的介绍从实际出发，避免抽象的理论论述和复杂的公式推导，在典型的算法介绍中深入浅出、简洁明了。结合上机能够提高编程能力和程序调试能力。通常用图来表示一些问题或概念，如集成电路设计、城市交通道路规划、作业调度等。图和树一样，是一种非线性数据结构。研究两顶点之间是否相连的关系，在图中，结点之间的关系是任意的，任意两个元素之间都有可能相关。图结构提供了简单的方式来描述一个问题、系统或状况。数据结构是计算机科学与技术专业的一门必修的、重要的专业基础课，是计算机程序设计的重要理论技术基础。通过数据结构科的学习，不仅可以使同学们掌握数据结构的基本特性、数据的逻辑结构和数据的存储结构及典型算法和使用方法，而且能够训练学生运用数据结构和算法进行具体应用问题的程序设计。主要内容包括算法计算法分析、面向对象程序设计与C++、线性表、栈和队列、串、数组和广义表、树、图、查找、排序、递归和文件等内容。作为计算机专业的学生，应该努力学好各种计算机语言，培养编程创新的能力。
1.2课题内容
武汉市公共交通指引系统是一个可以方便广大市民乘车的一个系统，有着较大的现实意义。本综合设计的任务是：设计并开发一个简化版的武汉市公共交通指引系统，使学生掌握Dijkstra算法培养学生利用C++语言编写程序以及调试程序的能力，运用数据结构知识解决实际问题的能力，为后续计算机专业课程的学习打下坚实的基础。
一、目的：
对应数据结构课程所学的基本原理和方法，学习图状结构求最短路径的算法，将理论知识运用于实际。
二、任务：
请根据图1.3和表1.2，设计一个武汉市交通导引系统。用户输入起点站和目标站，系统显示起点站到目标站的最短路径。

表1-2 车站表

图1.3 路线图

三、要求：
提示用户输入起点站和目标站
系统向用户显示一条最短路径（经过站数最少的路线），如果有两条以上最短路线，则按换乘次数排序显示。
显示每一条路线时，不仅要显示应搭乘的车次，还要显示应搭乘站的站名。

第二章 设计简介及设计方案论述
2.1 设计简介
先分析整个系统的构成，然后可以很清晰的看到要想构造和完成这一个系统，必须要先把公交线路的图输入成一个数据结构，构造完公交线路的图之后，再来完成最短线路的查找，然后我们就用Dijkstra算法去查找最短线路，这样子就可以得到了从一个顶点到其他顶点的距离和线路，在基于Dijkstra算法之上，从那么多个顶点中筛选所需要的终点站，便可以得到从起点站到终点站的一条最短路劲和长度，与公交线路匹配得出公交线路。
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
算法本身并不是按照我们的思维习惯——求解从原点到第一个点的最短路径，再到第二个点的最短路径，直至最后求解完成到第n个点的最短路径，而是求解从原点出发的各有向路径的从小到大的排列，但是算法最终确实得到了从原点到图中其余各点的最短路径，可以说这是个副产品，对于算法的终结条件也应该以求得了原点到图中其余各点的最短路径为宜。清楚了算法的这种巧妙构思后，理解算法本身就不是难题了。
Dijkstra算法是用来求任意两个顶点之间的最短路径。在该实验中，我们用邻接矩阵来存储图。在该程序中设置一个二维数组来存储任意两个顶点之间的边的权值。用户可以将任意一个图的信息通过键盘输入，让后在输入要查找的两个顶点，程序可以自动求出这两个顶点之间的最短路径。
2.2问题分析
（1）地图录入：建立有向图的数据结构录入到系统中去。
（2）寻找最短路劲：通过Dijkstra算法寻找一个站点到另一个站点的最短路劲。
（3）寻找公交线路：把得到的最短路劲与公交线路对比得到其适合的线路。
（4）输出：把所得到的结果输出到屏幕上

第三章 详细设计
3.1主要函数流程图
（1）主函数如流程图3.1
开始

输入起点站，终点站

构造最短路劲

匹配公交路线

结束

图3.1 流程图

（2）Dijkstra算法流程如流程图3.2：
图3.2 流程图

第四章 设计结果及分析
4.1 设计结果
（1）输出结果如结果图4.1

图4.1 结果图

总 结
课程设计是对我们综合能力的考察。通过这个程序，我们可以更加深刻的了解图，更深层次的了解了数据结构。不仅仅对于书本知识的熟悉，更是数据结构的实践性进展。
理论结合实践，既能使学生学习高级编程语言的知识、编程技术和基本算法，又能掌握程序设计的思想和方法，更具备利用计算机求解实际问题的能力，能灵活运用高级语言进行程序设计。课程设计前，要查阅资料了解相关要求和步骤，做好准备工作，定好设计思想。 在做课程设计过程中要注意积累经验,把出现的错误写到一处,然后对每一条进行总结，为以后数据结构的深入学习打下基础。

致 谢
在浩瀚宇宙中，每个人都是渺小的。在计算机这个更新速度比光速还快的世界中，个人的力量实在太渺小了。这是我第一次接触计算机语言，书上的内容很精致，但是要利用书上所学的知识来让我们编写一个实际的程序实在是非常困难。在调试过程中屡调屡败的状态下，我急得想哭，就在这时，老师给了我热情的帮助，老师指导我调试程序，说哪些是错的，哪些是多余的，哪些是必要的，一个杂乱无章的程序被修改得有条不紊，很显然结果也是最最正确的。在此，我真诚的感谢帮助我的老师们，老师就是黑暗中的指明灯，没有老师的指导，就没有我们顺利的完成任务的喜悦。老师每天都来机房为我们指导，及时解决我们所面临的问题，老师的工作态度让我们佩服，老师的一流技术让我们信服，老师的无私奉献让我们折服。当然，同学们的帮助也是我前进的力量，也让我体会到真诚的友谊。团结就是力量，在老师、同学的帮助下，我顺利完成了此次的课程设计。也让我体会到了成功的来之不易，只有真正付出过才有满意的收获。在此，我诚心的对所有帮助过我的老师学长同学们说一句：谢谢！！

参考文献
[1]谭浩强.C程序设计（第三版）. 北京: 清华大学出版社,2005.
[2]谭浩强.C程序设计题解与上机指导.北京：清华大学出版社,2005.
[3]谭浩强.C程序设计教程.北京：清华大学出版社,2007.
[4]谭浩强.C++程序设计.北京：清华大学出版社，2004.
[5]李春葆.数据结构教程（第4版）[M].北京：清华大学出版社，2014.
[6]李春葆.数据结构教程与上机实验指导（第4版）[M].北京：清华大学出版社，2014.

附录
主要代码：
#include<stdio.h>
#include<malloc.h>
#include<string.h>
#include<stdlib.h>
#define MAXV 100
#define INF 32767
int dist[MAXV],path[MAXV],B[10],k1=0;
typedef struct
{
int no;
int info;
}VertexType;
typedef struct
{
int edges[MAXV][MAXV];
int n,e;
VertexType vexs[MAXV];
}MGraph;
void Ppath(int path[] , int i , int v )
{
int k;
k= path[i];
if(k==v) return;
Ppath(path , k , v);
printf("%d,",k+1);
}
void Ppath1(int path[] , int i , int v ,char* A1[30],int B[10])
{
int k;
k= path[i];
if(k==v) return;
Ppath1(path , k , v,A1,B);
printf("%s,",A1[k]);
B[k1]=k+1;
k1++;
}
void Dispath(int dist[] , int path[] , int s[], int n,int v)
{
int i;
for(i=0;i<n;i++)
{
if(s[i]==1)
{
printf("从%d到%d的最短路径长度为：%d\t",v+1,i+1,dist[i]);
printf("%d,",v+1);
Ppath(path,i,v);
printf("%d\n",i+1);
}
}

}
void Dijkstra(MGraph g,int v)
{

int s[MAXV];
int mindis,i,j,u;
for(i=0;i<g.n;i++)
{
dist[i]=g.edges[v][i];
s[i]=0;
if(g.edges[v][i]<INF)
path[i]=v;
else
path[i]=-1;
}
s[v]=1;path[v]=0;
for(i=0;i<g.n;i++)
{
mindis = INF;
u=-1;
for(j=0;j<g.n;j++)
if(s[j]==0&&dist[j]<mindis)
{
u=j;
mindis=dist[j];
}
s[u]=1;
for(j=0;j<g.n;j++)
if(s[j]==0)
if(g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j])
{
dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
Dispath(dist,path,s,g.n,v);
}
int change(char* Q1,char* A1[30])
{
for(int i=0;i<30;i++)
{
if(strcmp(Q1,A1[i])==0)
break;
}
return i;
}
void change2(int i, char* A1[30])
{
printf("%s\t",A1[i]);
}
int main()
{
int A[30][30] = {{0,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
{INF,0,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
{1,INF,0,1,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
{INF,1,1,0,INF,INF,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
{INF,INF,1,INF,0,1,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
{INF,INF,INF,INF,1,0,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF},
{INF,INF,INF,1,1,INF,0,1,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,INF,