数据结构课程设计-全国交通咨询模拟系统程序设计源代码.doc

数据结构课程设计-全国交通咨询模拟系统 程序设计 源代码一、程序界面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 stt1;int stt2;/*出发时间*/ int endt1;int endt2;/*到达时间*/ int waitt;/*等待时间*/ int allt;/*两站之间总耗时*/ int money;/*票价*/inf2车站信息数据结构定义：typedef struct ArcCellint ff;/*ff=1 表示两点有信息*/int adj;/*路程长度*/ inf two;/*火车信息* /ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;3图的数据结构定义typedef struct Mgraph char vexsMAX_VERTEX_NUMMAX_VERTEX_NUM;/*顶点名*/ AdjMatrix arcs;/* 车站信息*/ int vexsxMAX_VERTEX_NUM;/*该顶点的X坐标*/ int vexsyMAX_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次测试。首先将顶点v1加入，即看(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;vG,vexnum;+v)for (w=0;wG,vexnum;+w)Dvw=G.arcsvw;for (u=0;uG,vexnum;+u) Pvw=FALSE;if(DvwINFINITY)pvwv=TRUE;Pvww=TRUE; for (u=0;uG.vexnum;u+) /* 将顶点u从0到n-1逐个加入测试 */ for (v=0;vG.vexnum;v+) /* 求v到w间的最短路径 */for (w=0;wG.vexnum;w+) if (Dv+DwDvw) /*从v经u到w的一条路径更短 */ Dvw=Dv+Dw;for (i=0;iG,vexnum;+i) Pvw=Pv|Pw;在程序计算最短路线，最短时间，最少消费时使用的就是这个算法。C. 交通图的绘制问题1将DOS默认的字符模式改为图形模式由于DOS默认的显示形式为字符模式，因此要在DOS下画图必须将字符模式改为图形模式。绘图程序的第一步就是初始化图形硬件。这里的硬件指的是为显示图形所必备的显示适配器。用于设置计算机图形方式的函数叫作initgraph( )，它的原型如下：void far initgraph(int far *gdriver, int far *gmode, char far *driver_path)；initgraph( )的函数原型在graphics.h头文件中，它必须包含在C图形程序的开始处。该文件包括了所有绘图组成成分的数据结构、常量和函数原型定义。其中，在initgraph( )的函数原型中头两个参数是整型指针。它们分别存有视频适配器和模式的逻辑值。第三个参数指明C绘图驱动程序所存储的路径。指向驱动程序的路径名可以是全程路径名，如：initgraph(&driver, &mode, “c:tcbgi”)；如果BGI驱动程序就在当前目录下，您也可以这样调用initgraph( )：initgraph(&driver, &mode, “”)；这里路径名为空字符串。本程序使用DETECT宏来自动检测本机器最优的图形驱动方式。在程序的末尾使用closegraph( ) 函数，以关闭BGI系统并把显示器的视频方式恢复到调用initgraph( ) 以前的情况。本程序绘图部分主要程序：#include / 包含绘图头文件void main(void) / 主函数int gdriver = DETECT; / 使用自检的方式int gmode;initgraph(&gdriver, &gmode, “c:borlandcbgi”); / 初始化图形系统/ 此处为绘图代码进行绘图，下面有详细介绍closegraph(); / 关闭图形系统2本程序显示的交通图绘制方法详述A.读入信息后显示路线的主要程序段： for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+)/*用此循环将所有城市画出*/ setcolor(WHITE); circle(G.vexsx,G.vexsy,4);/*画出半径为4个像素的路线起始城市A*/ circle(G.vexsxj,G.vexsyj,4); /*画出半径为4个像素的路线结束城市B,为白色*/ setcolor(YELLOW); outtextxy(G.vexsx+5,G.vexsy-3,G.vexs); /*写出路线起始城市A城市名*/outtextxy(G.vexsxj+5,G.vexsyj-3,G.vexsj); /*写出路线结束城市B城市名,黄色*/ if(G.arcsj.ff=1)/*如果两城市间有信息*/ setcolor(WHITE); line(G.vexsx,G.vexsy,G.vexsxj,G.vexsyj); /*在两城市间画一条线，白色*/ B.求出最优路线后的路线绘制程序段if(DjINFINITY)/* Dj%s,G.arcsk.two.num,G.arcsk.two.stt1,G.arcsk.two.stt2,G.vexsk);/*在屏幕底部显示路线*/setcolor(GREEN); line(G.vexsx,G.vexsy,G.vexsxk,G.vexsyk);/*在路线图中将路线画出，为绿色*/i=k;k=pathkj;printf(No.%d,时间:%02d:%02d)-%s,G.arcsj.two.num,G.arcsj.two.stt1,G.arcsj.two.stt2,G.vexsj);setcolor(GREEN);line(G.vexsx,G.vexsy,G.vexsxj,G.vexsyj); /*将路线的最后一段画出 */t=0; return OK; C将屏幕坐标转化为城市坐标问题本程序利用函数void put_mouse_position(int *x,int *y)获得当前鼠标位置(X,Y),再将鼠标位置通过查城市信息（城市坐标）的方式转换为具体的城市。具体函数如下：int whichvex(int x,int y)/*求模法判断顶点函数whichv