全国交通咨询模拟.txt

全国交通咨询模拟 一、程序界面 A．关于程序 B. 程序的使用 ...

一、程序界面

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;/*票价*/

}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次测试。首先将顶点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;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.h头文件中，它必须包含在C图形程序的开始处。该文件包括了所有绘图组成成分的数据结构、常量和函数原型定义。

其中，在initgraph( )的函数原型中头两个参数是整型指针。它们分别存有视频适配器和模式的逻辑值。第三个参数指明C绘图驱动程序所存储的路径。指向驱动程序的路径名可以是全程路径名，如：

initgraph(&driver, &mode, “c:\\tc\\bgi”)；

如果BGI驱动程序就在当前目录下，您也可以这样调用initgraph( )：

initgraph(&driver, &mode, “”)；

这里路径名为空字符串。本程序使用DETECT宏来自动检测本机器最优的图形驱动方式。

在程序的末尾使用closegraph( ) 函数，以关闭BGI系统并把显示器的视频方式恢复到调用initgraph( ) 以前的情况。

本程序绘图部分主要程序：

#include <graphics.h> // 包含绘图头文件

void main(void) // 主函数

{

int gdriver = DETECT; // 使用自检的方式

int gmode;

initgraph(&gdriver, &gmode, “c:\\borlandc\\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);

     outtextxy(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);

while(k!=j)

{printf("(No.%d,时间:%02d:%02d)->%s",G.arcs[k].two.num,G.arcs[k].two.stt1,

G.arcs[k].two.stt2,G.vexs[k]);/*在屏幕底部显示路线*/

setcolor(GREEN);

                                       line(G.vexsx,G.vexsy,G.vexsx[k],G.vexsy[k]);/*在路线图中将路线画出，为绿色*/

i=k;

k=path[k][j];

}

printf("(No.%d,时间:%02d:%02d)->%s",G.arcs[j].two.num,G.arcs[j].two.stt1,

G.arcs[j].two.stt2,G.vexs[j]);

setcolor(GREEN);

line(G.vexsx,G.vexsy,G.vexsx[j],G.vexsy[j]); /*将路线的最后一段画出 */

t=0; return OK;                                                                                                      

}}

C．将屏幕坐标转化为城市坐标问题

本程序利用函数void put_mouse_position(int *x,int *y)获得当前鼠标位置(X,Y),再将鼠标位置通过查城市信息（城市坐标）的方式转换为具体的城市。具体函数如下：

int whichvex(int x,int y)/*******求模法判断顶点函数whichvex(x,y,G)*****/

{ int i,pos,a,b,c,d;

  pos=-1;/*pos=-1表示点取的位置没有城市*/

  for(i=0;i<G.vexnum;i++)

  {c=G.vexsx-x;

   d=G.vexsy-y;/*查找城市*/

   a=abs(c);

   b=abs(d);

   if(!(a<=5&&b<=5))

   continue;

   if(a<=5&&b<=5)pos=i; /*如果点取坐标与该城市真实坐标相差小于5个像素，就认为点取了该城市*/

  }

  return pos;

}