软件技术学院
游戏算法实践报告
姓 名
专 业 数字媒体艺术 班 级
指导教师
2012年 1 月 6 日
地铁建设问题
1、问题的定义与描述
1.1、问题定义：地铁建设问题
1.2、问题描述：某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线，使程客可以沿地铁到达各个辖区，并使总的建设费用最小。
图1-1 各区距离图
2、关键技术
2.1 从包含各辖区的地图文件中读入辖区名称和各辖区间的距离。
2.2 根据读入的各辖区的距离信息，计算出应该建设哪些辖区间的地铁路线。 2.3 输出应该建设的地铁路线及所需建设的总里程信息。
3、数据的组织
3.1 数据结构定义：
本课程设计使用的数据结构是无向图，无向图采用邻接矩阵作为存储结构。 3.2数据定义：
3.2.1、站点（顶点）结构定义：
3.3、数据类型定义：
（1）在计算的过程中除要读取数（用字符数组表示，设其最大长度不超过50）外，还要读入各顶点的边的权值(权值设一默认最大值为60000计算需要，当两地没有可建路线时) 。同时还要输出汉字表示的路段，有用字符串。故定义头文件、常量、顶点数及权值数据类型如下：
#include"stdio.h" #include"string.h"
#define MAXVEX 50 /*顶点数最大值*/
#define MAXWEIGHT 60000 /*若顶点间无路径，则以此最大值表示不通*/ typedef int weight;
（2）每一个顶点由顶点号（初始从0开始）和站点名称组成。顶点号为整型，顶点名称则为字符数组。顶点总体定义为结构体类型。
/*顶点（站点）的数据类型*/ typedef struct{ int no;
char name[100]; }DataType;
（3）定义邻接矩阵，邻接边由weight 型的二维数组，顶点为DataType 类型，记录总顶点数的vexs 。
typedef struct{ weight arcs[MAXVEX][MAXVEX]; DataType data[MAXVEX]; int vexs;
}MGraph,*AdjMatrix;
（4）在定义一DataType 类型的数组，用来存放顶点的信息（顶点号和顶点名称），然后定义一long 类型的用来存放各铁路的权值，这两个数组用来创建邻接距阵时为邻接矩阵赋值。
DataType d[];
/*存放路段信息的数组*/ int m[][MAXVEX];
4、分析与实现
4.1 总体设计：
图4-1 总流程图
4.2函数原型定义：
4.2.1 void CreateGraph(AdjMatrix g,DataType vex[],int a[][MAXVEX],int n); /*初始化并创建邻接矩阵的函数*/ 参数：
① “AdjMatrix g”此参数用来传递在主函数已定义的邻接矩阵的地址。 ② “DataType vex[]”传递给函数顶点信息。 ③ “int a[][MAXVEX]”用来传递给函数邻接边（连接路段长度）信息的数组参数。 ④“int n”用来传递顶点个数的参数。
4.2.2 void DispGraph(AdjMatrix g); /*输出显示各已创建好的邻接矩阵站点及其相关邻接路段的信息*/ 参数：
① “AdjMatrix g”此参数用来传递已创建好的邻接矩阵的地址。 4.2.3 void Prim(AdjMatrix g,int v,long *a);
/*函数原型：普里姆算法，求修建最短铁路长度，并输出最短路径，返回值为最短路径的长度。*/
参数：
① “AdjMatrix g”此参数用来传递在主函数已定义的邻接矩阵的地址。 ② “int v”用来传递起始顶点。 4.3详细设计：
（5）以（4）中的两个数组为参数，调用CreateGraph 函数。创建邻接矩阵。
void CreateGraph(AdjMatrix g,DataType vex[],int a[][MAXVEX],int n)/*创建邻接矩阵函数*/
{
int i,j;
g->vexs=n;/* 为总顶点数赋值*/
for(i=0;i
{
g->data[i]=vex[i]; for(j=0;j
g->arcs[i][j]=a[i][j]; } }
(6)定义DispGraph 函数，用来检查一下，创建的邻接矩阵是否正确，并输出显示所有顶点和邻接边。
void DispGraph(AdjMatrix g)/* 输出所有路段及顶点信息的函数*/ {
int i,j;
/*输出各顶点的信息*/
printf("-------------------------------- 站 点 ---------------------------------------\n\n");
for(i=0;ivexs;i++)
{printf("%s ",g->data[i].name);}
/*输出各路段的信息*/
printf("\n\n--------------------------- 各 路 线 长 -----------------------------------\n\n");
for(i=0;ivexs;i++) {printf("\n\n");
for(j=0;jvexs;j++) {
if(g->arcs[i][j]
printf("%s%s:%d\n",g->data[i].name,g->data[j].name,g->arcs[i][j]);
} } }
（7）定义Prim 函数，用普里姆算法求出最小生成数，即最短地铁路线。然后直接输出这些路线。并且在main 函数中传递已定义的long 型totallon 变量地地，存放需要建设地铁的各路段总长度并且累加。
void Prim(AdjMatrix g,int v,long *a)/*普里姆算法求最短路径*/ {
weight lowcost[MAXVEX]; /* 存放计算过程中的最短路径*/ int uset[MAXVEX]; /*用来标记是否已被访问的标记*/ int i,j,MinEdge,MinWeight,k;
for(i=0;ivexs;i++) /*初始化最小权值*/ {
lowcost[i]=g->arcs[v][i];
uset[i]=1; }
uset[v]=0; /* 把起始点放到最小生成树中*/ printf("\n起始点:%s\n",g->data[v].name); for(i=1;ivexs;i++) {
MinWeight=MAXWEIGHT; /*初始化最小权值*/ for(j=0;jvexs;j++) {
if(uset[j]&&lowcost[j]
MinEdge=j; /*权值最小边的弧尾顶点*/ } }
for(j=0;jvexs;j++) /*寻找权值最小边的弧头顶点*/ if(g->arcs[j][MinEdge]==MinWeight) k=j;
printf("%s%s段 >>路长:\t \n",g->data[k].name,g->data[MinEdge].name,MinWeight);/*输出最短路线*/
*a+=MinWeight;
uset[MinEdge]=0; /*权值最小的边加入最小生成树*/ v=MinEdge;
for(j=0;jvexs;j++) /*更新最小权值*/ if(uset[j]&&g->arcs[v][j]arcs[v][j]; } }
%dm
软件技术学院
游戏算法实践报告
姓 名
专 业 数字媒体艺术 班 级
指导教师
2012年 1 月 6 日
地铁建设问题
1、问题的定义与描述
1.1、问题定义：地铁建设问题
1.2、问题描述：某城市要在其各个辖区之间修建地铁来加快经济发展，但由于建设地铁的费用昂贵，因此需要合理安排地铁的建设路线，使程客可以沿地铁到达各个辖区，并使总的建设费用最小。
图1-1 各区距离图
2、关键技术
2.1 从包含各辖区的地图文件中读入辖区名称和各辖区间的距离。
2.2 根据读入的各辖区的距离信息，计算出应该建设哪些辖区间的地铁路线。 2.3 输出应该建设的地铁路线及所需建设的总里程信息。
3、数据的组织
3.1 数据结构定义：
本课程设计使用的数据结构是无向图，无向图采用邻接矩阵作为存储结构。 3.2数据定义：
3.2.1、站点（顶点）结构定义：
3.3、数据类型定义：
（1）在计算的过程中除要读取数（用字符数组表示，设其最大长度不超过50）外，还要读入各顶点的边的权值(权值设一默认最大值为60000计算需要，当两地没有可建路线时) 。同时还要输出汉字表示的路段，有用字符串。故定义头文件、常量、顶点数及权值数据类型如下：
#include"stdio.h" #include"string.h"
#define MAXVEX 50 /*顶点数最大值*/
#define MAXWEIGHT 60000 /*若顶点间无路径，则以此最大值表示不通*/ typedef int weight;
（2）每一个顶点由顶点号（初始从0开始）和站点名称组成。顶点号为整型，顶点名称则为字符数组。顶点总体定义为结构体类型。
/*顶点（站点）的数据类型*/ typedef struct{ int no;
char name[100]; }DataType;
（3）定义邻接矩阵，邻接边由weight 型的二维数组，顶点为DataType 类型，记录总顶点数的vexs 。
typedef struct{ weight arcs[MAXVEX][MAXVEX]; DataType data[MAXVEX]; int vexs;
}MGraph,*AdjMatrix;
（4）在定义一DataType 类型的数组，用来存放顶点的信息（顶点号和顶点名称），然后定义一long 类型的用来存放各铁路的权值，这两个数组用来创建邻接距阵时为邻接矩阵赋值。
DataType d[];
/*存放路段信息的数组*/ int m[][MAXVEX];
4、分析与实现
4.1 总体设计：
图4-1 总流程图
4.2函数原型定义：
4.2.1 void CreateGraph(AdjMatrix g,DataType vex[],int a[][MAXVEX],int n); /*初始化并创建邻接矩阵的函数*/ 参数：
① “AdjMatrix g”此参数用来传递在主函数已定义的邻接矩阵的地址。 ② “DataType vex[]”传递给函数顶点信息。 ③ “int a[][MAXVEX]”用来传递给函数邻接边（连接路段长度）信息的数组参数。 ④“int n”用来传递顶点个数的参数。
4.2.2 void DispGraph(AdjMatrix g); /*输出显示各已创建好的邻接矩阵站点及其相关邻接路段的信息*/ 参数：
① “AdjMatrix g”此参数用来传递已创建好的邻接矩阵的地址。 4.2.3 void Prim(AdjMatrix g,int v,long *a);
/*函数原型：普里姆算法，求修建最短铁路长度，并输出最短路径，返回值为最短路径的长度。*/
参数：
① “AdjMatrix g”此参数用来传递在主函数已定义的邻接矩阵的地址。 ② “int v”用来传递起始顶点。 4.3详细设计：
（5）以（4）中的两个数组为参数，调用CreateGraph 函数。创建邻接矩阵。
void CreateGraph(AdjMatrix g,DataType vex[],int a[][MAXVEX],int n)/*创建邻接矩阵函数*/
{
int i,j;
g->vexs=n;/* 为总顶点数赋值*/
for(i=0;i
{
g->data[i]=vex[i]; for(j=0;j
g->arcs[i][j]=a[i][j]; } }
(6)定义DispGraph 函数，用来检查一下，创建的邻接矩阵是否正确，并输出显示所有顶点和邻接边。
void DispGraph(AdjMatrix g)/* 输出所有路段及顶点信息的函数*/ {
int i,j;
/*输出各顶点的信息*/
printf("-------------------------------- 站 点 ---------------------------------------\n\n");
for(i=0;ivexs;i++)
{printf("%s ",g->data[i].name);}
/*输出各路段的信息*/
printf("\n\n--------------------------- 各 路 线 长 -----------------------------------\n\n");
for(i=0;ivexs;i++) {printf("\n\n");
for(j=0;jvexs;j++) {
if(g->arcs[i][j]
printf("%s%s:%d\n",g->data[i].name,g->data[j].name,g->arcs[i][j]);
} } }
（7）定义Prim 函数，用普里姆算法求出最小生成数，即最短地铁路线。然后直接输出这些路线。并且在main 函数中传递已定义的long 型totallon 变量地地，存放需要建设地铁的各路段总长度并且累加。
void Prim(AdjMatrix g,int v,long *a)/*普里姆算法求最短路径*/ {
weight lowcost[MAXVEX]; /* 存放计算过程中的最短路径*/ int uset[MAXVEX]; /*用来标记是否已被访问的标记*/ int i,j,MinEdge,MinWeight,k;
for(i=0;ivexs;i++) /*初始化最小权值*/ {
lowcost[i]=g->arcs[v][i];
uset[i]=1; }
uset[v]=0; /* 把起始点放到最小生成树中*/ printf("\n起始点:%s\n",g->data[v].name); for(i=1;ivexs;i++) {
MinWeight=MAXWEIGHT; /*初始化最小权值*/ for(j=0;jvexs;j++) {
if(uset[j]&&lowcost[j]
MinEdge=j; /*权值最小边的弧尾顶点*/ } }
for(j=0;jvexs;j++) /*寻找权值最小边的弧头顶点*/ if(g->arcs[j][MinEdge]==MinWeight) k=j;
printf("%s%s段 >>路长:\t \n",g->data[k].name,g->data[MinEdge].name,MinWeight);/*输出最短路线*/
*a+=MinWeight;
uset[MinEdge]=0; /*权值最小的边加入最小生成树*/ v=MinEdge;
for(j=0;jvexs;j++) /*更新最小权值*/ if(uset[j]&&g->arcs[v][j]arcs[v][j]; } }
%dm