数据结构课程设计- 全国交通咨询模拟系统程序设计源代码一、程序界面
A?关于程序
1.该程序以C语言为开发工具,运行该程序前请确保你地机器上已安装tc或turboc ,否则系统会提示:
BGI Error: Graphics not initialized (use 'initgraph'>
而无法使用该程序.遇到此情况请安装tc ,建议将其安装到C:目录下,以确保程序运行万无一失.
2.该软件完全支持鼠标,请放心使用.
3.该程序能将您输入地城市转换为象素坐标,显示在屏幕上,操作直观方便,选择城市时,用时标一点该城市即可,省去了输入地麻烦.如果您选择地两个城市间有路径地话,程序除了给您信息输出外,还会在地图上将此路径以不同颜色画出,更加直观.
4.该程序附带三个数据文件(num.txt,vex.txt,len.txt -- 此文件由系统默认>以供用户调试,用户还可自己创建文件,以备实验查询使用.
B. 程序地使用
用户打开程序,会看到命令行: FILE CHANGE SHORTWAY MAP HELP ABOUT QUIT CLRSCR
用户将鼠标放于某命令上会看到屏幕最下面有一行字在闪动,这是对命令地解释,如当鼠标访于FILE 上时其下解释"press this button to open/creat a file" , 当鼠标空闲时在下面显示:
"Please Enter Your Choice With Mouse Or Keyboard" , 提示用户进行命令选择.单机鼠标就会将某一功能打开从而进行某一操作
2.用户运行程序时请先打开FILE 菜单,该菜单有4 个命令选项:
[ 信息提示]
1.调用已存信息库文件(由用户提供>
2.创建新地信息库文件
3.调用演示信息库文件
4.退出程序
[ 请输入你地选择(1/2/3/4> ]
此时程序等待用户输入选择.输入正确后程序会自动打开地图由用户进行下一步操作
3.对于其他命令,用户可由显示于屏幕下面地提示进行相关操作
二.程序内部设计及数据结构
A. 数据地存放格式
1.火车信息数据结构定义:
typedef struct inf
{ int num 。/* 车次*/
int sttl。int stt2。/* 出发时间*/
int endt1 。int endt2。/*到达时间*/
int waitt 。/* 等待时间*/
int allt。/*两站之间总耗时*/
int money 。/*票价*/
}inf
2.车站信息数据结构定义:
typedef struct ArcCell
{
int ff。/*ff=1 表示两点有信息*/
int adj。/*路程长度*/
inf two。/*火车信息* /
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]
3.图地数据结构定义
typedef struct Mgraph
{ char vexs[MAX_VERTEX_NUM][MAX_VERTEX_NUM] 。
/*顶点名*/ AdjMatrix arcs 。/* 车站信息*/
int vexsx[MAX_VERTEX_NUM] 。/* 该顶点地X 坐标*/
int vexsy[MAX_VERTEX_NUM] 。/* 该顶点地Y 坐标*/
int vexnum,arcnum 。/* vexnum :顶点地数目,arcnum :路线数目*/
}Mgraph 。
4.基于以上数据结构地数据存储举例:
<以下为部分顶点信息)
wulumuqi 49 59<表示城市wulumuqi 在640X480 地屏幕中位于坐标49,59 处, 下同)
xining 97 155
lanzhou 121 174
<以下为部分路线信息)
wulumuqi lanzhou 1 1892 1001 1 0 12 0 10 670 150
<表示从城市wulumuqi 到城市lanzhou 有信息‘ 1,路'线长度为1892,车次为1001,从城市wulumuqi 开出时间
为1 : 00,到lanzhou站时间为12: 00,在lanzhou停留10分钟,总耗时670分钟<总耗时由系统自动计算出),车票报价150元.下同)
xining lanzhou 1 216 1002 9 0 12 5 5 190 50
xining xian 0 10000 10000 10000 10000 10000 10000 10000 10000 10000
<表示xining 与xian 两城市间无直达<直接相连)路线)
B. 求最优路径地算法
求最优路径地算法可以说是本程序地核心.本程序使用地是弗洛伊德<floyd )算法
1 、弗洛伊德算法地基本思想
设求顶点vi到vj间地最短路径,若vi到vj有弧,则弧上地权值是一条路径,但未必是最短路径,要经过n-1次测试.首先将顶点vi加入,即看(vi,v1>,(v1,vj>是否有路径,且比(vi,vj>低,如是,则用后两段路径代替,并称这是vi到vj中间顶点序号不大于1地最短路径.再将顶点v2加入,得到vi到vj中间顶点序号不大于2地最短路径.如此下去,直到vn加入,得到vi到vj中间顶点序号不大于n地最短路径,算法结束.
2、弗洛伊德<floyd )算法清单略述
void ShortestPath_FLOYD(MGraph G,PathMatrix &P[],DistanceMatrix &D>
{for (v=0 。 v
{D[v][w]=G.arcs[v][w] 。
for (u=0。u
if(D[v][w]
}
for (u=0。u
for (v=0。v
for (w=0 。w
if (D[v]+D[w]
{ D[v][w]=D[v]+D[w] 。
for (i=0 。i
P[v][w]=P[v]||P[w] 。
}
在程序计算最短路线,最短时间,最少消费时使用地就是这个算法.
C. 交通图地绘制问题
1 .将DOS 默认地字符模式改为图形模式
由于DOS 默认地显示形式为字符模式,因此要在DOS 下画图必须将字符模式改为图形模式.绘图程序地第一步就是初始化图形硬件.这里地硬件指地是为显示图形所必备地显示适配器.用于设置计算机图形方式地
函数叫作initgraph( >, 它地原型如下:
void far initgraph(int far *gdriver, int far *gmode, char far *driver_path> ;
initgraph( >地函数原型在graphics"头文件中,它必须包含在C图形程序地开始处.该文件包括了所有绘图组成成分地数据结构、常量和函数原型定义.
其中,在initgraph( >地函数原型中头两个参数是整型指针.它们分别存有视频适配器和模式地逻辑值.第三个参数指明C 绘图驱动程序所存储地路径.指向驱动程序地路径名可以是全程路径名,如:
initgraph(&driver, &mode, 如果 BGI 驱动程序就在当前目录下 ,您也可以这样调用 initgraph( > :
initgraph(&driver, &mode, ;“”>
这里路径名为空字符串 .本程序使用 DETECT 宏来自动检测本机器最优地图形驱动方式 .
在程序地末尾使用 closegraph( > 函数 ,以关闭 BGI 系统并把显示器地视频方式恢复到调用 initgraph( > 以前 地情况 .
本程序绘图部分主要程序:
#include
void main(void> // 主函数
{
int gdriver = DETECT 。 // 使用自检地方式
int gmode 。
initgraph(&gdriver, &gmode, “c: bgi ”。> // 初始化图形系统
// 此处为绘图代码进行绘图 ,下面有详细介绍
closegraph(>。 // 关闭图形系统
}
2.本程序显示地交通图绘制方法详述
A.读入信息后显示路线地主要程序段:
for(i=0 。 i
for(j=0 。 j
{ setcolor(WHITE> 。
circle(G.vexsx,G.vexsy,4> 。 /*画出半径为 4 个像素地路线起始城市 A*/
circle(G.vexsx[j],G.vexsy[j],4>。/*画出半径为4个像素地路线结束城市 B,为白色*/
setcolor(YELLOW> a ? ”
bcg:i