交通咨询.txt

提供对城市信息的编辑

一．实习目的
通过实习，了解并初步掌握设计、实现较大系统的完整过程，包括系统分析、编码设计、系统集成、以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。

二．问题描述
设计、实现一个全国大城市间的交通咨询程序，为旅客提供三种最优决策方案：（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相连的下一个城市；