数据结构课程设计- 全国交通咨询模拟系统程序设计源代码一、程序界面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 。
/*票价*/}inf2．车站信息数据结构定义：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 155lanzhou 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 50xining 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<G,vexnum。
++v> for (w=0 。
w<G,vexnum 。
++w>{D[v][w]=G.arcs[v][w] 。
for (u=0。
u<G,vexnum。
++u> P[v][w]=FALSE 。
if(D[v][w]<INFINITY>{p[v][w][v]=TRUE 。
P[v][w][w]=TRUE 。
}}for (u=0。
u<G.vexnum。
u++> /*将顶点u从0到n-1逐个加入测试*/for (v=0。
v<G.vexnum。
v++> /* 求v 到w 间地最短路径*/for (w=0 。
w<G.vexnum 。
w++>if (D[v]+D[w]<D[v][w]> /* 从v 经u 到w 地一条路径更短*/{ D[v][w]=D[v]+D[w] 。
for (i=0 。
i<G,vexnum 。
++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 <graphics.h> // 包含绘图头文件void main(void> // 主函数{int gdriver = DETECT 。
// 使用自检地方式int gmode 。
initgraph(&gdriver, &gmode, “c: bgi ”。
> // 初始化图形系统// 此处为绘图代码进行绘图 ,下面有详细介绍closegraph(>。
// 关闭图形系统}2．本程序显示地交通图绘制方法详述A.读入信息后显示路线地主要程序段：for(i=0 。
i<G.vexnum 。
i++>for(j=0 。
j<G.vexnum 。
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:iouttextxy(G.vexsx+5,G.vexsy-3,G.vexs> 。
/* 写出路线起始城市A 城市名*/outtextxy(G.vexsx[j]+5,G.vexsy[j]-3,G.vexs[j]> 。
/*写出路线结束城市B 城市名,黄色*/if(G.arcs[j].ff==1>/* 如果两城市间有信息*/{setcolor(WHITE> 。
line(G.vexsx,G.vexsy,G.vexsx[j],G.vexsy[j]> 。
/* 在两城市间画一条线, 白色*/}}B.求出最优路线后地路线绘制程序段{if(D[j]<INFINITY>/* D[j]<INFINITY 表示已找到最优路径*/{ printf(" 里程:%d km",D[j]> 。
k=path[j] 。
if(k!=-1>{printf("\n 最短路线：(图中绿色>">。
printf("\n%s",G.vexs>。