地铁建设问题

课程设计报告书

课程名称              数据结构               

设计题目            题目建设问题             

专业班级            软件11-02                

学    号                         

姓    名                              

指导教师              唐晓亮                 

2013 年 1月20日

目录

1.设计时间    2

2.设计目的    2

3.设计任务    2

4.设计内容    2

4.1需求分析    2

4.2总体设计    2

4.2.1主函数流程图    2

4.3详细设计    3

4.3.2函数调用关系    3

4.3.3主要模块的算法描述    3

4.4测试与分析    3

4.4.1测试    3

4.4.2分析    4

4.5附录    4

5.总结与展望    7

参考文献    8

成绩评定    8

1 设计时间

2012年1月5日

2 设计目的

设计各辖区之间最短地铁，使修建费用最少

3设计任务

某城市要在各个辖区之间修建地铁，由于地铁建设费用昂贵，因此需要合理安排地铁建设线路，使市民可以沿地铁到达各个辖区，并使总费用最小。

4 设计内容 

(1)输入各个辖区名称和各辖区间直接距离（地铁铺设费用与距离成正比）。

(2)根据辖区距离信息，计算出应该在哪些辖区建立地铁线路。

(3)输出应该建设的地铁线路及所需建设总里程。

4.1总体设计

4.2需求分析

（1）本程序设计计算城市内各辖区间修建地铁的最短路程。

（2）运行时，输入辖区的名称，各辖区之间用空格键隔开，以#输入结束。

（3）输入各辖区间距离时，先输入两辖区名称，再输入距离。

（4）最后计算最短距离来得出最少费用。

4.3详细设计

P163采用邻接矩阵存储构造无向图

P175普利姆算法生成最小树

4.4测试与分析

4.4.1测试

4.4.2分析

调试时，在输入数据时，再输完数据后要再次按下空格键，再输入结束符号才会结束本次输入进入下一个输入。

且不能输入与本次输入无关的数据或者超出本次输入的数据，否则显示错误，将重新输入。

4.5 附录

#include  

#include  

#include  

#include 

#define INFINITY  10000

#define M 20 

typedef struct{ 

  char    V[M][10];  

  int R[M][M]; 

  int vexnum; 

}Graph; 

int locatevex(Graph *g,char a[10])

{

   int i;

   for(i=0;ivexnum;i++)

   {

     if(strcmp(a,g->V[i])==0)

        return i; 

   }

  if(i==g->vexnum)

    return -1; 

}

int creatgraph(Graph *g)

{

  int i=0,j,m,k,p;

  char a[10],b[10];

  printf("请输入所有的辖区，以#为输入结束标志\\n");

  scanf("%s",g->V[i]);

  while(strcmp("#",g->V[i])!=0)

  {

     i++;

     scanf("%s",g->V[i]);

  }

  g->vexnum=i;

  for(i=0;ivexnum;i++)

   for(j=0;jvexnum;j++)    

     g->R[i][j]=INFINITY;

  printf("请输入辖区和辖区之间的路程，以##为结束标志\\n");

  scanf("%s%s%d",a,b,&m);

  while(strcmp("##",a)!=0 || strcmp("##",b)!=0 || m!=0)

  {

    k=locatevex(g,a);  p=locatevex(g,b);

    if(k==-1)

    {

      printf("没有%s这个辖区\\n",a);

      return 0;

    }

    if(p==-1)

    {

      printf("没有%s这个辖区\\n",b);

      return 0;

    }

    g->R[k][p]=g->R[p][k]=m;

    scanf("%s%s%d",a,b,&m);

  }

  return 1;

}

struct tree      //构造最小生成树//

  {

    int weizhi;

    int lowcost;

  };

int minimun(struct tree *a,Graph g)

{

  int i,k,m=0;

  for(i=0;i  {

    if(m==0 && a[i].lowcost!=0)

    {

      m=1;

      k=i;

    }

    if(m==1 && a[i].lowcost!=0)

    {

      if(a[i].lowcost          k=i;

    }

  }

  return k;

}

void MiniSpanTree_PRIM(Graph g,char a[10])

{

 struct tree closedge[M];

  int i,j,m,k,money=0;

  k=locatevex(&g,a);

  if(k==-1)

  {

     printf("没有%s这个辖区，无法求解\\n",a);

     return 0;

  }

  for(i=0;i  {

    if(i!=k)

    {

     closedge[i].lowcost=g.R[k][i];

     closedge[i].weizhi=k;

    }

 }

 closedge[k].lowcost=0;

 for(i=1;i {

   k=minimun(closedge,g);

   money+=closedge[k].lowcost;

   printf("%d:%s  %s %d\\n",i,g.V[  closedge[k].weizhi ],g.V[k],closedge[k].lowcost);

   closedge[k].lowcost=0;

   for(j=0;j   {

     if(g.R[k][j]     {

       closedge[j].weizhi=k;

       closedge[j].lowcost=g.R[k][j];

     }

   }

 }

 printf("总费用为：%d\\n",money);

}

void main()

{

  int i,j,k;

  Graph g;

  char a[10];

  printf("请选择功能： 1（铁路建设）  0（退出）\\n");

  scanf("%d",&k);

  while(k)

  {

      i=creatgraph(&g);

      if(i)

      {

        printf("请输入从哪里开始：");

        scanf("%s",a);

        MiniSpanTree_PRIM(g,a);

      }

      printf("请选择功能： 1（铁路建设）  0（退出）\\n");

      scanf("%d",&k);

  }

}

5 总结与展望

本程序，本次编译涉及数据结构最小生成树以及图的构造等编译。先要构造结构体，在定义时应要注意尽量将赋值空间增大，以防止调试时输入数据超出运算范围。再进行函数的编译调用，构造无向图用邻接矩阵进行存储，这些编译代码，书上都有介绍，但不可尽抄，书上的只是一个模板，根据程序设计任务将变量进行修改，构造图之后，运用最小生成树原理，用普利姆算法对整个程序变量进行编译，最后进入主函数，就直接调用函数进行运算输入的数据，输出运算结果。

这次程序的编译让我对图的遍历理解的更加深入，最小生成树问题不仅可以运算本次程序对地铁建造最少费用问题，更可以运用于一系列的最短距离等问题，解决甚多复杂问题！极其具有实用性！

参考文献

[1] 屈辉立,陈可明,石武信.JSP网站编程教程[M].第1版, 北京:北京希望电子出版社,2005                          

[2] 白勇.用B/S模式构建在线考试系统[J],重庆电力高等专科学校学报,2003,10(4): 100～130. 

[3] 严蔚敏，吴伟民编著，数据结构。—北京：清华大学出版社，2007

[4]