一．實習目的
通過實習，了解并初步掌握設計、實現較大系統的完整過程，包括系統分析、編碼設計、系統集成、以及調試分析，熟練掌握數據結構的選擇、設計、實現以及操作方法，為進一步的應用開發打好基礎。

二．問題描述
設計、實現一個全國大城市間的交通咨詢程序，為旅客提供三種最優決策方案：（1）時間最短（2）費用最小（3）中轉次數最少。

三．需求分析
      該程序所做的工作的是模擬全國交通咨詢，為旅客提供三種最優決策的交通咨詢。此程序規定：

（1）       在程序中輸入城市名稱時，需輸入10個字母以內的字母串；輸入列車或飛機編號時需輸入一個整型數據；輸入列車或飛機的費用時需輸入一個實型數據；輸入列車或飛機開始時間和到達時間時均需輸入兩個整型數據（以hh：mm的形式）；在選擇功能時，應輸入與所選功能對應的一個整型數據。

（2）      程序的輸出信息主要是：最快需要多少時間才能到達，或最少需要多少旅費才能到達，或最少需要多少次中轉到達，并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到何地。

（3）      程序的功能包括：提供對城市信息的編輯，提供列車時刻表和飛機航班表的編輯，提供三種最優決策：最快到達、最省錢到達、最少中轉次數到達。   

四．概要設計
·         系統用到的抽象數據類型定義：

1．ADT Graph{

   數據對象V：一個集合，該集合中的所有元素具有相同的特性

   數據關系R：R={VR}

               VR={<x,y>|P(x,y)^(x,y屬于V)}

   基本操作：

（1）       initgraph(&G)；

（2）       CreateGraph(&G)；

（3）       EnterVertex(&G)；

（4）       DeleteVertex(&G)；

（5）       EnterplaneArc(&G)；

（6）       DeleteplanArc(&G)；

（7）       EntertrainArc(&G)；

（8）       DeletetrainArc(&G)；

}ADT Graph

        2．ADT LinkQueue{

           數據元素：可以是任意類型的數據，但必須屬于同一個數據對象

           關系：隊列中數據元素之間是線性關系。

           基本操作：

（1）       InitQueue(&Q)；

（2）       IsEmpty(&Q)；

（3）       EnterQueue(&Q,x)；

（4）       DeleteQueue(&Q,&y)；

           }ADT LinkQueue

        3．ADT TimeTree{

           數據對象D：一個集合，該集合中的所有元素具有相同的特性

           數據關系R：若D為空，則為空樹。若D中僅含有一個數據元素，則R為空集，否則R={H}，H為如下二元關系：

（1）       在D中存在唯一的稱為根的數據元素root，它在關系H中沒有前驅

（2）       除root以外，D中每個結點在關系H下有且僅有一個前驅。

             基本操作：

（1）       CreateTimeTree(p,i,j,&Q,infolist arcs)；

（2）       CopyTimeTree(p,q)；

（3）       VisitTimeTree(p)；

}ADT TimeTree

 

·         系統中子程序及功能要求：

1．Administer(ALGraph *G)：提供管理員管理城市交通系統的界面，通過該子程序可調用其他管理交通系統的子程序。

2．initgraph(ALGraph *G)：初始化交通系統的子程序

3．createcityfile( )：創建城市文件的子程序

4．createplanefile( )：創建航班文件的子程序

5．createtrainfile( )：創建列車時刻表文件的子程序

6．LocateVertex(ALGraph *G,char *v)：提供城市名在城市交通系統中相應的編號

7．CreateGraph(ALGraph *G)：創建城市交通系統

8．cityedit(ALGraph *G)：提供城市編輯功能

9．EnterVertex(ALGraph *G)：提供在城市交通系統中加入城市的功能

10．DeleteVertex(ALGraph *G)：提供在城市交通系統中刪除城市的功

                              能

11．flightedit(ALGraph *G)：提供航班編輯功能

12．EnterplaneArc(ALGraph *G)：提供在城市交通系統中加入航班的功

                              能

13．DeleteplaneArc(ALGraph *G)：提供在城市交通系統中刪除航班的

                                功能

14：trainedit(ALGraph *G):提供列車車次的編輯功能

15．EntertrainArc(ALGraph *G)：提供在城市交通系統中加入列車車次

                              的功能

16．DeletetrainArc(ALGraph *G)：提供在城市交通系統中刪除列車車

                                次的功能

17．UserDemand(ALGraph G)：提供用戶咨詢的界面

18．DemandDispose(int n,ALGraph G)：通過該子程序調用其他咨詢子程序

19．InitQueue(LinkQueue *Q)：初始化隊列

20．EnterQueue(LinkQueue *Q,int x)：入隊操作

21．DeleteQueue(LinkQueue *Q,int *x)：出隊操作

22．IsEmpty(LinkQueue *Q)：隊列判空操作

23．TransferDispose(int k,infolist(*arcs)[MAX_VERTEX_NUM],

(*arcs)[MAX_VERTEX_NUM] ,ALGraph G,ALGraph G,int v0,int v1)

：提供最少中轉次數決策的功能

       24．MinExpenditure(infolist arcs,float *expenditure,

float *route)：提供兩個城市之間最少費用的功能

       25．ExpenditureDispose(int k, infolist (*arcs)[MAX_VERTEX_NUM]

,ALGraph G, int v0,int v1,float *D,int *final)

：提供最少費用決策的功能

       26．MinTime(infolist arcs,float *time,float *route)

           ：提供兩個城市之間最短時間的功能

       27．TimeTreeDispose(Node *head,infolist 

(*arcs)[MAX_VERTEX_NUM])

：提供兩個之間相隔一個以上城市的城市間的最短時間的功能

       28．CreateTimeTree(TimeTree p,int i,int j,

LinkQueue *Q,infolist(*arcs)[MAX_VERTEX_NUM])：創建時間樹

       29．CopyTimeTree(TimeTree p,TimeTree q)：復制時間樹

       30．VisitTimeTree(TimeTree p)：訪問時間樹

       31．DestoryTimeTree(TimeTree p)：銷毀時間樹

       32．TimeDispose(int k,infolist (*arcs)[MAX_VERTEX_NUM],

ALGraphG,int v0,int v1,float *D,int *final)

           ：提供最少時間決策的功能

       33：PrintGraph(ALGraph *G)：顯示整個城市交通系統 

 

·         各程序模塊之間的調用關系（子程序編號見上）：

        主函數可調用子程序1，17，33

        子程序1可調用子程序2，8，11，14

        子程序2可調用子程序3，4，5，7

        子程序7，12，13，15，16可調用子程序6

        子程序8可調用子程序9，10

        子程序11可調用子程序12，13

        子程序14可調用子程序15，16

        子程序17可調用子程序18

        子程序18可調用子程序23，25，32

        子程序23可調用子程序19，29，21，22

        子程序25可調用子程序24

        子程序32可調用子程序26，27

        子程序27可調用子程序28，30，31

        子程序28可調用子程序29

五．詳細設計
·         創建交通圖算法的偽碼描述如下：

                    int LocateVertex(ALGaph *G,char *v)/*找出城市名在圖中對應結

                                        點位置*/

                    {

                    for(k=0;k<圖G中的結點個數G->vexnum;k++)

 

                    if(第k個結點中的城市名與傳過來的城市名相同)

                       {

                          j=k;/*記錄位置*/

                               break;

                       }

                     }

                       返回k 的數值；

}

 

int  CreatGraph(ALGraph *G)

{

       if(打開城市文件，文件指針返回值為空）

           {

              輸出錯誤文件信息；

           程序返回值為0；

            }

       while(文件不為空）

         {

           將文件指針所指的字符串讀到城市名數組 city[i]中；

          i++;

          }

     關閉文件；

     j=0;

     while(j<城市個數）

     {

     將 city[i] 中的內容復制到圖的結構體的結點數組中;

     圖的結構體其他項負初值;

     j++;

     }

     G->vexnum=i;

    打開航班信息文件"plane.txt";

    將文件中的內容以塊為單位讀到緩沖區數組a中；

    關閉文件；]

    a的計數變量k=0;

    弧的計數變量 arc_num=0;

    while(k<信息個數)

    { 

    調用函數 LocateVertex(G,a[k].vt)得到起始結點的位置 i；

    調用函數 LocateVertex(G,a[k].vt)得到起始結點的位置 j；

    q=G->vertices[i].planfirstarc;

    m=0;

    while(q!=NULL)

   {

     if( 弧 q中的鄰接頂點與j相等）

      {

         將數組a[i] 中的內容都復制到弧q中；

        m=1;

        break;

      }

      q=q->nextarc;

     if(m=0);

     {

     開辟一個弧結點；

     將數組a[i]中的內容都復制到新的弧結點中；

     將弧結點連接到適當的位置中去；

     arc_num++;

    }

      k++;

}

 G->planarcnum=arc_num;

 

    打開列車信息文件"plane.txt";

    將文件中的內容以塊為單位讀到緩沖區數組a中；

    關閉文件；]

    a的計數變量k=0;

    弧的計數變量 arc_num=0;

    while(k<信息個數)

    { 

    調用函數 LocateVertex(G,a[k].vt)得到起始結點的位置 i；

    調用函數 LocateVertex(G,a[k].vt)得到起始結點的位置 j；

    q=G->vertices[i].trainfirstarc;

    m=0;

    while(q!=NULL)

   {

     if( 弧 q中的鄰接頂點與j相等）

      {

         將數組a[i] 中的內容都復制到弧q中；

        m=1;

        break;

      }

      q=q->nextarc;

     if(m=0);

     {

     開辟一個弧結點；

     將數組a[i]中的內容都復制到新的弧結點中；

     將弧結點連接到適當的位置中去；

     arc_num++;

    }

      k++;

    }

 G->trainarcnum=arc_num;

返回；

}

 

·         創建航班算法的偽碼描述如下：

                creatplanefile()

        {while(flag)      /*flag為標志位,初值為1*/

         {  提示“輸入航班信息”；

輸入航班code;

            輸入航班的出發城市vt;

                   輸入航班的到達城市vh;

            輸入機票價格money;

輸入航班的出發時間bt;

輸入航班的到達時間at;

a.[count].co=code;          /* a 為程序頭部定義的結構體*/   

strcpy(a.[count].vt,vt);

strcpy(a.[count].vh,vh);

a.[count].bt=bt;

a.[count].at=at;

a.[count].mo=money;

計數值count+1;

提示“是否要繼續輸入航班信息：”；

scanf(“%d”,&flag);

}

 

if(航班文件不能以讀寫形式打開)

提示“無法打開文件”；

將計數值count寫入航班車文件；

for(i=0;i<count;i++)

   if(無法將a[i]寫入航班文件)

       提示“文件無法寫入”；

關閉航班文件；

}

·         刪除城市結點算法的偽碼描述如下：

       DeleteVertex(ALGraph *G)  /* G是程序頭部定義的結構體*/

       {

        提示“輸入刪除城市名”；

        gets(城市名：v);

        提示“是否確定要刪除（Y/N）“；

        c=getchar();

        if(c==’Y’||c==’y’)

        {n=0;                 /*0是記數標志，控制循環次數*/

while(n<圖G表頭接點總個數&&圖G的存儲城市名與v不同)

          /*G表頭結點總個數比實際大1*/

  記數值n+1;

 if(n = =圖G表頭結點總個數)

   提示“無法找到此城市“；

else 

{

      i=LocateVertex(G,v);

/*利用G函數找到此城市名所處在G中位置*/

刪除從此結點出發的所有航班弧；

刪除從此結點出發的所有列車弧；

for(j=i;j<圖G表頭結點總個數-1；j++)

將G第j個結點的信息依前移1位；

將G第j個結點的信息制空；

/*以下是刪除所有指向此結點的航班弧*/

for(k=0;k<圖G表頭記點總個數-1；k++)

{p指向圖G中k結點的第一條飛機弧；

 while（p！=NULL）

 {  if（該弧指向的頂點位置（p->adjvex ）>i）

      {將該弧指向頂點位置-1；

       q=p；

       p指向下一條飛機弧；

      }

    else if（該弧指向的頂點位置（p->adjvex ）= = i）

      {if（p指向圖G中k結點的第一條飛機弧）

          { m=p；

           將圖G中k結點的第二條飛機弧改為第一弧；

            p指向下一條飛機弧；

            釋放（m）；

           }

        else 

           {  將p的下一條弧賦給q的下一條弧；

              m=p；

              p指向下一條飛機弧；

              釋放（q）；

            }

        }     

    else

     {q=p；

      p指向下一條飛機弧；

     }

}

}

   

/*以下是刪除所有指向此結點的列車弧*/

for(k=0;k<圖G表頭記點總個數-1；k++)

{p指向圖G中k結點的第一條列車弧；

 while（p！=NULL）

 {  if（該弧指向的頂點位置（p->adjvex ）>i）

      {將該弧指向頂點位置-1；

       q=p；

       p指向下一條列車弧；

      }

    else if（該弧指向的頂點位置（p->adjvex ）==i）

      {if（p指向圖G中k結點的第一條列車弧）

          { m=p；

           將圖G中k結點的第二條列車弧改為第一弧；

            p指向下一條列車弧；

            釋放（m）；

           }

        else 

           {  將p的下一條弧賦給q的下一條弧；

              m=p；

              p指向下一條列車弧；

              釋放（q）；

            }

        }     

    else

     {q=p；

      p指向下一條列車弧；

     }

}

}

}

圖G表頭結點總個數-1；

}

else return；

             }

 

·         求城市v0，v1之間的最少費用算法的偽碼描述如下：

        ExpenditureDispose( )

{for(v=0；v<城市個數；v++)

         {城市v還未求得最少費用；

          *(D+v)=城市v0到v的最少費用；

          將城市v的路徑設置為空；

          if(*(D+v)<INFINITY)

           將城市v0和v加入到城市v的路徑中；

         }

         城市v0到城市v0的最少費用為0；

         城市v0設為已求得最少費用；

         for(i=1；i<城市個數；v++)

         {m=INFINITY;

          for(w=0；w<城市個數；w++)

           if(城市w未求得最少費用)

            if(*(D+w)<m)

            {v=w;

             m=*(D+w);

            }

if(v等于v1)

{根據城市v的路徑輸出從城市v0到城市v1所需經過的城市及路線；

 輸出最少費用*(D+v1)；

  返回；

}

else

{將城市v設為已求得最少費用；

 for(w=0；<G.vexnum；w++)

  if(城市w未求得最少費用并且從城市v到w有路徑)

  {求出從城市v到城市w的最少費用及路線；

   if(*(D+w)>m+城市v到w的最少費用)

   {*(D+w)=m+城市v到w的最少費用；

    將城市w的路徑改成城市v的路徑并在最后加入城市w；

   }

}

         }

         輸出沒有列車或飛機從城市v0到v1；

        }

 

·         最少中轉次數算法的偽碼描述如下：

求城市v0到城市v1的最少中轉次數

TransferDispose( )

{for(v=0；v<G.vexnum；v++)

 {城市v設為未訪問；

  城市v的路徑設為空；

 }

 將城市v0設為已訪問；

 將城市v0入隊；

 while(隊列不空)

 {隊首城市v出隊；

  w為與城市v相連的第一個城市；

  while(w存在)

  {if(城市w未訪問)

{將城市w設為已訪問；

    將城市w的路徑改為城市v的路徑并在最后加入城市w；

    if(w等于v1)

    {根據城市w的路徑輸出從城市v0到城市v1所需經過的城市及路線；

     返回；

    }

    將城市w入隊；

   }

  w等于城市v相連的下一個城市；