计算机科学与技术学院课程设计成绩单

课程名称：数据结构                               指导教师：   张凯

优秀：90分~100分 良好：80分~89分 中等：70~79分 及格：60~69分 不及格0分~59分                                   

 武汉科技大学计算机科学与技术学院制表

 

计算机科学与技术学院     

课程设计报告

课程名称：  数据结构  

专    业：               

班    级：     级     班   

学    号：               

姓    名：                 

指导老师：                 

题目一火车票务系统的设计与实现

1.1设计要求

        设计一个火车票务系统，并完成如下功能：

列车记录包含6项：车次、始发站、终点站、发车时间、到站时间、票价

Z38、 武昌、  北京西、21:06   、07:01    、272

（1）列车信息录入：输入列车基本信息。

（2）列车信息删除：删除车次信息。(列车线路停运)

（3）列车信息修改：修改车次信息。（列车时间、票价等信息有变动）

（4）列车信息输出：根据格式对齐输出列车信息。

（5）列车信息查询：可根据车次号、始发站、终点站查询满足条件的列车信息。

（6）列车信息排序：可根据票价对列车信息进行排序并输出。

1.2 概要设计

1. 系统功能设计

   本系统设置了6个子功能菜单，6个子功能的设计描述如下。

（1）       录入列车信息。可以一次输入多个列车信息，该功能由InputData()函数实现。

（2）       删除列车信息。由于有些列车线路问题可能停运，则可根据列车号删除该列车信息。该功能由Delete_CheCi()函数实现。

（3）       修改列车信息。可根据车次号选择所要修改的列车信息，修改内容包括：发车时间、到站时间、票价。该功能由Update_CheCi()函数实现。

（4）       查询列车信息。可根据车次号、始发站、终点站查询满足条件的列车信息，该功能分别由Search_CheCi()函数、Search_ShiFaZhan()函数和Search_ZhongDianZhan()函数实现。

（5）       显示列车信息。可以查看该系统中的所有列车信息记录。该功能由Display()函数实现。

（6）       排序列车信息。可根据票价对列车信息进行从小到大排序并输出，该功能由QuickSort()函数实现。

1.3 模块设计

  1. 系统子程序及功能设计

     (1)void InputData(SqList &L);                                 //录入列车信息

(2)int Check_CheCi(SqList &L,KeyType *CheCi,int n);           //车次输入格式与唯一性校验

(3)int Search_CheCi(SqList &L,char num[]);                     //按车次查找信息

(4)int Search_ShiFaZhan(SqList &L,char num[]);                //按始发站查找信息

(5)int Search_ZhongDianZhan(SqList &L,char num[]);            //按终点站查找信息

(6)int Delete_CheCi(SqList &L,char num[]);                    //按车次删除信息

(7)int Update_CheCi(SqList &L,char num[]);                    //按车次修改信息

(8)int Partition(SqList &L,int low,int high);

(9)void QSort(SqList &L,int low,int high);

(10)void QuickSort(SqList &L);                               //按票价对列车信息从小到大排序

(11)void Display(SqList L);                                    //根据格式对齐输出列车信息

(12)int Prompt();                                             //显示主菜单函数

(13)void main();                                             //主函数

  2. 函数之间的调用关系图

     图中数字是各函数的编号：

    

1.4详细设计

   1. 数据类型定义

    typedef struct

{//列车信息描述

           char start_station[8];                //始发站

           char end_station[8];                  //终点站

           char departure_time[6];               //发车时间

           char arrival_time[6];                 //到站时间

           int  price;                           //票价

}InfoType;

typedef struct

{

           KeyType train_num[keylen];           //车次

           InfoType others;

}RecType;

typedef struct

{

           RecType r[MaxSpace];                //静态链表

           int length;                         //表长

}SqList;

  2. 系统主要子程序详细设计

(1)列车信息的录入和列车号格式与唯一性的判别函数：

   //录入列车信息

void InputData(SqList &L)

{

       int i = ++L.length,flag = 1;

       char yn = 'y';

       printf("\n请依次录入列车信息数据（车次由1位大写字母和2位数字组成）：");

       while(yn == 'y'||yn == 'Y'){

              printf("\n车次  始发站  终点站  发车时间  到站时间  票价\n");

              scanf("%s%s%s%s%s%d",L.r[i].train_num,L.r[i].others.start_station,L.r[i].others.end_station,

                     L.r[i].others.departure_time,L.r[i].others.arrival_time,&L.r[i].others.price);

              fflush(stdin);                //清空输入缓冲区

              if(!Check_CheCi(L,L.r[i].train_num,i))    

              {

                     printf("\n错误信息：车次号须由一位大写字母和两位数字组成。\n");

                  flag = 0;

                     break;

        }

              if(Check_CheCi(L,L.r[i].train_num,i) == -1)

              {

                     printf("\n错误信息：车次号不唯一。\n");

                     flag = 0;

                     break;

              }

              ++i;

              ++L.length;

              printf("继续输入吗？y/n:");

              yn = getchar();

       }

       if(flag == 1)

       {

        printf("\n录入成功！\n");

           L.length--;

       }

       else{

              printf("\n录入失败！\n");

        L.length--;

       }

}

//车次输入格式与唯一性校验

int Check_CheCi(SqList &L,KeyType *CheCi,int n)

{

       int i;

       if(strlen(CheCi)!=3)  return 0;

       else if(CheCi[0]<'A'||CheCi[0]>'Z')  return 0;

       for( i = 1;i <= 2;i++)

              if(CheCi[i]<'0'||CheCi[i]>'9')  return 0;

       for( i =1;i<=L.length-1;i++)

              if(!strcmp(L.r[i].train_num,CheCi))

                     return -1;

       return 1;

}

(2)用快速排序法根据票价进行从小到大排序的函数如下：

//按票价对列车信息从小到大排序

int Partition(SqList &L,int low,int high){

       L.r[0] = L.r[low];

       int p = L.r[low].others.price;

       while(low < high)

       {

              while(low<high && L.r[high].others.price >= p)  --high;

              L.r[low] = L.r[high];

              while(low<high && L.r[low].others.price <=p)   ++low;

              L.r[high] = L.r[low];

       }

       L.r[low] = L.r[0];

       return low;

}

void QSort(SqList &L,int low,int high)

{

       int p;

       if(low<high)

       {

              p = Partition(L,low,high);

              QSort(L,low,p-1);

              QSort(L,p+1,high);

       }

}

void QuickSort(SqList &L)

{

       QSort(L,1,L.length);

}

1.5 测试分析

  1.系统运行主界面如下所示：

   

 2. 列车信息的录入

   在主菜单下，用户输入1并回车，然后按照提示输入列车信息，运行结果如下所示：

  

3.列车信息的删除

  在主菜单下，用户输入2并回车，然后按照提示输入要删除的列车号。运行结果如下：

 

4. 列车信息的显示

  在主菜单下，用户输入5并回车，可以查看所有的列车信息。运行结果如下：

 

5. 列车信息的修改

  在主菜单下，用户输入3并回车，按照要求输入所要修改的列车的列车号，可以修改发车时间、到站时间和票价。运行结果如下：

 

 

6. 列车信息的查询

   在主菜单下，用户输入4并回车，可以有三种方式查询：按车次号、按始发站和按终点站。运行结果如下：

 

7.列车信息的排列与输出

  在主菜单下，用户输入6并回车，则显示经过票价排序后的列车信息。运行结果如下：

 

1.6 小结

        本次列车票务系统设计中，数据结构类型用的是静态链表，当列车信息达到一定量时，在删除，录入等功能上，比动态链表要花费的时间多，而且一开始所分配的空间较大，在运行结束后才释放所有空间。不过，在排序上，用静态链表较有优势。

题目二  地铁建设问题

2.1 设计要求

    城市要在各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线，使乘客可以沿地铁到达各个辖区，并使总的建设费用最小。

（1）使用恰当的数据结构存储辖区名称和距离信息。

（2）根据读入的辖区距离信息，计算出应该建设哪些辖区的地铁路线。

（3）输出应该建设的路线，以及所需建设的总里程信息。

2.2 概要设计

 1.存储结构设计

     typedef struct ArcCell{

             VRType  adj;            //权值

}ArcCell,AdjMatrix[MaxVertexNum][MaxVertexNum];    //图的邻接矩阵类型

typedef struct Vexsinfo

{             //顶点信息

            int position;           //城市编号

            char  name[10];         //城市名称

}Vexsinfo;

typedef struct Mgraph

{            //图结构信息

             Vexsinfo vexs[MaxVertexNum];             //顶点向量

             AdjMatrix arcs;                          //邻接矩阵

             int      vexnum,arcnum;                  //图的当前顶点数和边数

}Mgraph;

2.3 模块设计

1. 系统子程序及功能设计

     (1)Mgraph initgraph();             //图的建立

     (2) int LocateVex(Mgraph G,int u);   //查找城市在图中的编号

     (3) int Minimum(Closedge C,Mgraph G);  //求出Closedge中的下一个结点：第k顶点

     (4) double MiniSpanTree_PRIM(Mgraph G,int u);  //用普里姆算法构造最小生成树

     (5) void main();             //主函数

2. 函数之间的调用关系图

  图中数字是各函数的编号：

 

2.4 详细设计

 1. 图的初始化

Mgraph initgraph()

{

       int i , j ;

       Mgraph c;

       c.vexnum = 11;                           //顶点个数

       c.arcnum = 16;                           //边的个数

       for(i = 0;i < c.vexnum;i++)              //依次设置顶点编号

              c.vexs[i].position = i;

       //依次输入顶点信息

       strcpy(c.vexs[0].name,"怀化区");  strcpy(c.vexs[1].name,"昌平区");

       strcpy(c.vexs[2].name,"顺义区");  strcpy(c.vexs[3].name,"平谷区");

       strcpy(c.vexs[4].name,"海淀区");  strcpy(c.vexs[5].name,"石景山区");

       strcpy(c.vexs[6].name,"同州区");  strcpy(c.vexs[7].name,"宣武区");

       strcpy(c.vexs[8].name,"房山区");  strcpy(c.vexs[9].name,"大兴区");

       strcpy(c.vexs[10].name,"宝坻区");

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

              for(j = 0;j < c.vexnum;j++)

                     c.arcs[i][j].adj = Infinity;    //先初始化图的邻接矩阵

       c.arcs[0][2].adj = 19.38;         c.arcs[1][2].adj = 36.81;

       c.arcs[2][3].adj = 44.43;         c.arcs[2][4].adj = 33.76;        

       c.arcs[4][5].adj = 13.89;         c.arcs[4][6].adj = 33.73;

       c.arcs[4][7].adj = 11.96;         c.arcs[5][6].adj = 49.49;

       c.arcs[5][7].adj = 23.01;         c.arcs[5][8].adj = 19.11;

       c.arcs[5][9].adj = 27.70;         c.arcs[6][7].adj = 28.86;

       c.arcs[6][10].adj = 55.79;        c.arcs[7][9].adj = 14.82;

       c.arcs[7][10].adj = 82.99;        c.arcs[8][9].adj = 19.52;

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

              for(j = 0;j < c.vexnum;j++)

                     c.arcs[j][i].adj = c.arcs[i][j].adj;

       return c;

}

2. 用普里姆算法构造最小生成树

double MiniSpanTree_PRIM(Mgraph G,int u)

{

       double s = 0;

       int k,i,j;

       Closedge close;

       k = LocateVex(G,u);

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

              if(j != k)

              {

                     close[j].adjvex = u;

                     close[j].lowcost = G.arcs[k][j].adj;

              }

       close[k].lowcost = 0;

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

       {

              k = Minimum(close,G);

              s = s + close[k].lowcost;

              printf("( %s----%4.2lf----%s )\n",G.vexs[close[k].adjvex].name,close[k].lowcost,G.vexs[k].name);

              close[k].lowcost = 0;

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

                     if(G.arcs[k][j].adj < close[j].lowcost)

                     {

                            close[j].adjvex = G.vexs[k].position;

                            close[j].lowcost = G.arcs[k][j].adj;

                     }

       }

       return s;

}

2.5 测试分析

   该程序运行后结果如下：

  

2.6 小结

    该程序完全是根据设计要求的问题所设计的，由于时间的缘故，其中并无增加其他功能。该程序用邻接矩阵表示法来存储辖区名称和距离信息，对于稀疏点的信息，用邻接表或是邻接多重表更为合适。求使乘客可以沿地铁到达各个辖区，并使总的建设费用最小这一问题，采用了普里姆算法。不过，由于所求问题中，顶点为11个，边数只有16条边，觉得用邻接表和克鲁斯卡尔算法更为合适。