数据结构课设报告

《中南大学信息科学与工程学院》

课程设计报告

专 业： 电子信息工程 班 级： 1002 姓 名： 程广俊 学 号： 0909101116 指导教师： 李登

完成日期： 2012年7月

目录

1、问题描述 ............................................................................................................................. 2 2、基本要求 ............................................................................................................................. 2

2.1.1 ................................................................................................................................... 2 2.1.2 ................................................................................................................................... 2 2.1.3 ................................................................................................................................... 2 2.1.4 ................................................................................................................................... 2 2.1.5 ................................................................................................................................... 2 2.2 ...................................................................................................................................... 2 3、数据结构的设计 ................................................................................................................. 3

3.1路线查找和选择 ......................................................................................................... 3 3.2程序的编写 ................................................................................................................. 6 4、软件模块结构 ..................................................................................................................... 8 5、程序设计思想 ..................................................................................................................... 8 6、程序流程图 ......................................................................................................................... 9 7、源程序 ............................................................................................................................... 10 8、调试分析 ........................................................................................................................... 27 9、测试数据 ........................................................................................................................... 27 10、用户使用手册 ................................................................................................................. 28 11、心得体会 ......................................................................................................................... 30

11.1经验体会 ................................................................................................................. 30 11.2这次的课程设计让我体会到了三点： ................................................................. 30 11.3编程体会 ................................................................................................................. 30

1

1、问题描述

已知某市每条公共路线及沿途所经站名，试设计一个问路程序，用户可以在任一车站通过终端询问知道：

是否有公共汽车到达指定的目的地?

若有，告诉乘车路线。如需中途换车，应指示再那里换车

2、基本要求

2.1.1自己提出一个公共汽车路线图，可以在网上搜索现实城市公交路线图（如长沙市的），至少要有7条公交线路，每条线路至少要有7个公共汽车站。

2.1.2数据结构：将公共汽车路线图看成是一个有向图，选择合适的数据结构，除了反映顶点(站)之间的邻接关系外，还应反映途经的路线号。注意，两站之间可能存在往返两个方向，每个方向又可能对应多个路线号。

2.1.3算法：按选定的数据结构设计相应的算法。注意，当从乘车站到目的站存在多种乘车路线时，必须确定路线选取标准。例如，要求换车次数最少等。 数据结构可以采用链接结构： structNODE {

char* stname;

struct NODE* link; };

struct NODE hdtp[MAX+1]； 数据结构也可以采用顺序结构： struct NODE{ int go,back; };

struct NODE a[max+1,max+1]; 其中，a[I，j].go>0 表示第i条线路上，向站j 去方向的下一站号；a[i，j].back>0表示第i条线路上，站j回来的下一站号。若站j不在第i条线路上，a[i，j].go 和a[i，j].back 均为0。

2.1.4另外，还需建立两个数组；一个是线路序号和线路号“值”的对照表；另一个是站号和站名对照表。

2.1.5对所采用的算法进行算法分析

2.2假定顶点编号为1..n，数据结构采用连接结构。设置表头数组为head[1..n]，head[i]包含站i的名字和一指针，该指针指向i的所有邻接顶点组成的单链表。单链表中的每个结点包含3个域：一个站号域，两个指针域。一个指针指向i的下一个邻接顶点，另一个指针指向从i到该结点的所有线路号组成的链表。

struct LINENODE

2

{

int lineno;

struct LINENODE* next; };

struct STNODE {

int stno;

struct LINENODE* Link1,*Link2; };

如果按途经站数最少的原则来确定乘车路线，实际上是最短路径问题，则可以采用Djkstra算法或图的宽度优先搜索算法。在保证站数最少的前提下，如果存在多种乘车路线，则可以进一步挑选换车次数最少的路线。

3、数据结构的设计

3.1路线查找和选择

首先查找长沙市公交线路，选择八条公交线，并将这八条线所交 叉的站保留，再根据每站12站左右的标准进行删减，使得每站站数 合适，然后对每站进行编号，利用百度地图测距功能，测出每站之间 的距离，并四舍五入取整，这样即可得到估测的站点间的距离。

（本题所选的公交路线如下）： 7路

0.长沙火车站——1.窑岭南——2.东塘北——3.中附一院——4.橘园桥北——5.铁道学院——6.林科大——7.井湾子南——8.湖南女大——9.省植物园——10.汽车南站

107路

0.长沙火车站——11.人民路北——12.公交新村——13.汪家冲——4.橘园桥北——5.铁道学院——6.林科大——7.井湾子南——8.湖南女大——9.省植物园——10. …… 此处隐藏：3045字，全部文档内容请下载后查看。喜欢就下载吧 ……