一、程序界面

A．關于程序

1. 該程序以C語言為開發(fā)工具，運行該程序前請確保你的機器上已安裝tc或turboc ,否則系統(tǒng)會提示：

BGI Error: Graphics not initialized (use 'initgraph')
而無法使用該程序。遇到此情況請安裝tc ,建議將其安裝到C:目錄下,以確保程序運行萬無一失。

2. 該軟件完全支持鼠標，

3. 該程序能將您輸入的城市轉換為象素坐標，顯示在屏幕上，操作直觀方便，選擇城市時，用時標一點該城市即可，省去了輸入的麻煩。如果您選擇的兩個城市間有路徑的話，程序除了給您信息輸出外，還會在地圖上將此路徑以不同顏色畫出，更加直觀。

4. 該程序附帶三個數(shù)據(jù)文件(num.txt,vex.txt,len.txt --此文件由系統(tǒng)默認)以供用戶調(diào)試,用戶還可自己創(chuàng)建文件，以備實驗查詢使用.

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. 調(diào)用已存信息庫文件(由用戶提供)

2. 創(chuàng)建新的信息庫文件

3. 調(diào)用演示信息庫文件

4. 退出程序

 [  請輸入你的選擇(1/2/3/4)  ]

此時程序等待用戶輸入選擇.輸入正確后程序會自動打開地圖由用戶進行下一步操作.

3. 對于其他命令，用戶可由顯示于屏幕下面的提示進行相關操作.

二．程序內(nèi)部設計及數(shù)據(jù)結構

A.  數(shù)據(jù)的存放格式

1．火車信息數(shù)據(jù)結構定義：

typedef struct inf

{ int num;/*車次*/

  int stt1;int stt2;/*出發(fā)時間*/

  int endt1;int endt2;/*到達時間*/

  int waitt;/*等待時間*/

  int allt;/*兩站之間總耗時*/

  int money;/*票價*/

}inf

2．車站信息數(shù)據(jù)結構定義：

typedef struct ArcCell

{

int ff;/*ff=1 表示兩點有信息*/

int adj;/*路程長度*/   

inf two;/*火車信息* /

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

3．圖的數(shù)據(jù)結構定義

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：頂點的數(shù)目，arcnum：路線數(shù)目*/

}Mgraph;

4．基于以上數(shù)據(jù)結構的數(shù)據(jù)存儲舉例：

（以下為部分頂點信息）

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 到城市l(wèi)anzhou 有信息‘1’，路線長度為1892，車次為1001，從城市wulumuqi開出時間為1：00，到lanzhou站時間為12：00，在lanzhou 停留10分鐘，總耗時670分鐘（總耗時由系統(tǒng)自動計算出），車票報價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.   求最優(yōu)路徑的算法

求最優(yōu)路徑的算法可以說是本程序的核心。本程序使用的是弗洛伊德（floyd）算法

1、弗洛伊德算法的基本思想

設求頂點vi到vj間的最短路徑，若vi到vj有弧，則弧上的權值是一條路徑，但未必是最短路徑，要經(jīng)過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經(jīng)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下畫圖必須將字符模式改為圖形模式。繪圖程序的第一步就是初始化圖形硬件。這里的硬件指的是為顯示圖形所必備的顯示適配器。用于設置計算機圖形方式的函數(shù)叫作initgraph( )，它的原型如下：

void far initgraph(int far *gdriver, int far *gmode, char far *driver_path)；

initgraph( )的函數(shù)原型在graphics.h頭文件中，它必須包含在C圖形程序的開始處。該文件包括了所有繪圖組成成分的數(shù)據(jù)結構、常量和函數(shù)原型定義。

其中，在initgraph( )的函數(shù)原型中頭兩個參數(shù)是整型指針。它們分別存有視頻適配器和模式的邏輯值。第三個參數(shù)指明C繪圖驅(qū)動程序所存儲的路徑。指向驅(qū)動程序的路徑名可以是全程路徑名，如：

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

如果BGI驅(qū)動程序就在當前目錄下，您也可以這樣調(diào)用initgraph( )：

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

這里路徑名為空字符串。本程序使用DETECT宏來自動檢測本機器最優(yōu)的圖形驅(qū)動方式。

在程序的末尾使用closegraph( ) 函數(shù)，以關閉BGI系統(tǒng)并把顯示器的視頻方式恢復到調(diào)用initgraph( ) 以前的情況。

本程序繪圖部分主要程序：

#include <graphics.h> // 包含繪圖頭文件

void main(void) // 主函數(shù)

{

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

int gmode;

initgraph(&gdriver, &gmode, “c:\\borlandc\\bgi”); // 初始化圖形系統(tǒng)

// 此處為繪圖代碼進行繪圖，下面有詳細介紹

closegraph(); // 關閉圖形系統(tǒng)

}

2．本程序顯示的交通圖繪制方法詳述

A.讀入信息后顯示路線的主要程序段：

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

  for(j=0;j<G.vexnum;j++)/*用此循環(huán)將所有城市畫出*/

    { 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.求出最優(yōu)路線后的路線繪制程序段

{if(D[j]<INFINITY)/* D[j]<INFINITY 表示已找到最優(yōu)路徑*/

{ 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．將屏幕坐標轉化為城市坐標問題

本程序利用函數(shù)void put_mouse_position(int *x,int *y)獲得當前鼠標位置(X,Y),再將鼠標位置通過查城市信息（城市坐標）的方式轉換為具體的城市。具體函數(shù)如下：

int whichvex(int x,int y)/*******求模法判斷頂點函數(shù)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;

}