《中南大学信息科学与工程学院》
课程设计报告
专 业： 电子信息工程 班 级： 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.汽车南站
152路
14.高叶塘——15.桃子湖——16.湖南大学——17.靳江路口——18.南郊公园——5.铁道学院——6.林科大——7.井湾子南——8.湖南女大——9.省植物园——10.汽车南站
63路
19.汽车西站——20.湖南财专——14.高叶塘——15.桃子湖路口——16.湖南大学——17.靳江路口——18.南郊公园——21.丁家垅——5.铁道学院——22.潇湘晨
3
报——23.香樟路——24.雨花区北——25.火车南站
124路
26.柑子园——27.修业学校——28.义茶亭——2.东塘北——3.中附一院——4.橘园桥北——5.铁道学院——22.潇湘晨报——23.香樟路——29.雨花区西——24.雨花区北——25.火车南站
145路
30.贾谊故居——27.修业学校——31.燕子岭——32.东塘西——3.中附一院——4.橘园桥北——5.铁道学院——6.林科大——33.韶山南路——34.新韶路口——35.汽车南站
502路
36.汽车东站——37.血液中心——38.长沙海关——39.橘园桥北——5.铁道学院——6.林科大——7.井湾子南——8.湖南女大——9.省植物园——10.汽车南站
17路
40.汽车西站——41.瓜瓢山——42.王家湾——43.阳光一百——18.南郊公园——5.铁道学院——6.林科大——7.井湾子南——8.湖南女大——9.省植物园——10.汽车南站
4