数据结构最小生成树课程设计.docx

目录
一、课题描述： 2
二、需求分析 3
三、总体结构设计 4
四、各子模块设计 5
五、编程设计 8
六、测试结果 12
七、总结 14
八、参考文献 15
附 录 16

一、课题描述：
设计一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。图中任一对城市都是连通的，用公路把所有城市联系起来，设计可使得工程的总造价最少。

二、需求分析
根据课设题目要求，拟将整体程序分为三大模块。此三个模块相互独立，没有嵌套调用的情况，以下是三个模块的大体分析：
1. 建立一个图，其存储方式可以采用邻接矩阵形式，需要定义两个数组，一个存储城市，一个存储公路，存储公路的数组表明城市间的连通关系和公路的造价；。
2. 利用kruskal算法求城市地图的最小生成树
3. 按父亲结点和子女结点集的形式输出生成树中各条边（公路）以及它们的权值（造价），公路总造价最小值。

三、总体结构设计
功能模块图

无
向
图
的
建
立

最
小
生
成
树
的
求
解

按父
结点
和子
女结
点集
的形
式输
出，
求最
小值,

四、各子模块设计
1.无向图的建立（初始化）

printf(“\n请输入城市的信息”)
n=1
G->arc[i][j].adj=G->arc[j][i].adj=0
j++
i++
j=1
j<=G->vexnum
i<=G->vexnum
Int i,j,n,h,m,k
i=1

N

Y

N

Y

n<=G->vexnum
scanf(“%s”,vex[n].name);
n++

N

Y

2.用kruskal算法求最小生成树
sort(edges,G)
i=1
找公路和公路的造价
j++
i++
j=i+1
j<=G->vexnum
i<G->vexnum
Int i,j,n,m
i=1

N

Y

Y
N

Y

Y

i<=G->vexnum
parent[i]=0;
i++

N

Y

3.用冒泡法排序
printf(“\n公路造价排序为：”)
i=1
公路造价排序
j++
i++
j=i+1
j<=G->vexnum
i<G->vexnum
int i,j;
i=1

N

Y

N

Y

N
i<=G->vexnum
printf(“<%s,%s> %d\n”,vex…);
i++

Y

五、编程设计
存储结构

该函数包含三个结构体，即存储城市、存储公路和存储图的结构体，其结构体分别如下所示：
1.顶点和边的存储表示
用字符串name表示城市信息，num表示城市的序号。
struct node{
char name[10];
int num;
}vex[20];
用整型begin和end表示公路的起点和终点，weight表示公路的造价。
typedef struct
{
int begin;
int end;
int weight;
}edge;
2.图的邻接矩阵存储表示
用整型adj表示城市间的关系，weight表示公路的造价。
typedef struct
{
int adj;
int weight;
}AdjMatrix[MAX][MAX];
用arc表示邻接矩阵，vexnum和arcnum表示图当前的城市数和公路数。
typedef struct
{
AdjMatrix arc;
int vexnum, arcnum;
}MGraph;

时间复杂度0(n^2)

算法描述

该算法是建立一个带权的无向图，并用Kruskal算法求该图的最小生成树，用父结点和子女结点集的形式输出最小生成树。
1.无向带权图的建立
图的存储结构如上所示，;用adj是否为1判断两城市间是否有公路，adj为1时表示有公路，反之没有公路，vexnum和arcnum分别表示城市数和公路数，name和num分别表示城市信息和城市序号，建图的算法如下所示：
void CreatGraph(MGraph *G)
{
int i, j,n,h,m,k;
char u[MAX],v[MAX];
printf("请输入公路数和城市数:");
scanf("%d %d",&G->arcnum,&G->vexnum)
for (i = 1; i <= G->vexnum; i++)//初始化图
{
for ( j = 1; j <= G->vexnum; j++)
{
G->arc[i][j].adj = G->arc[j][i].adj = 0;
}
}
printf("\n请输入城市的信息:");
for(n=1;n<=G->vexnum;n++)
{
scanf("%s",vex[n].name);
vex[n].num=n;
}
for ( i = 1; i <= G->arcnum; i++)
{
printf("\n请输入有公路的2个城市:");
scanf("%s",v);
scanf("%s",u);
for ( k= 1; k <= G->vexnum; k++)
{
if(strcmp(v,vex[k].name)==0)
{m=vex[k].num;}
if(strcmp(u,vex[k].name)==0)
{h=vex[k].num;}
}
G->arc[m][h].adj = G->arc[h][m].adj = 1;
getchar();
printf("\n请输入%s与%s之间的公路造价:",vex[m].name, vex[h].name);
scanf("%d",&G->arc[m][h].weight);
}
printf("邻接矩阵为:\n");
for ( i = 1; i <= G->vexnum; i++)
{
for ( j = 1; j <= G->vexnum; j++)
{
printf("%d ",G->arc[i][j].adj);
}
printf("\n");
}
}
2. Kruskal算法
克鲁斯卡尔算法：假设连通网N=（V，{E}），则令最小生成树的起始状态为只有n个顶点而无边的非连通图T=（V，{}），图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加到T中，否则舍去此边而选择下一条代价最小的边。以此类推，直至T中所有的顶点都在同一连通分量上为止。算法代码如下所示：
void MiniSpanTree(MGraph *G)
{
int i, j, n, m;
int k = 1;
int parent[M];
edge edges[M];

for ( i = 1; i < G->vexnum; i++)
{
for (j = i + 1; j <= G->vexnum; j++)
{
if (G->arc[i][j].adj == 1)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G->arc[i][j].weight;
k++;
}

}
}
sort(edges, G);
for (i = 1; i <= G->arcnum; i++)
{
parent[i] = 0;
}
printf("最小生成树为:\n");
for (i = 1; i <= G->arcnum; i++)
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)
{
parent[n] = m;
printf("<< %s, %s >> %d\n", vex[edges[i].begin].name, vex[edges[i].end].name, edges[i].weight);
Mincost+=edges[i].weight;
}
}
printf("使各城市间公路总造价的最小费用为：Mincost=%d\n",Mincost);
}
int Find(int *parent, int f)
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}
3．用冒泡法对公路造价按从小到大的顺序排列
void sort(edge edges[] ,MGraph *G)
{
int i, j;
int temp;
for ( i = 1; i < G->arcnum; i++)
{
for ( j = i+1; j <=G->arcnum; j++)
{
if (edges[i].weight > edges[j].weight)
{
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
}
}
六、测试结果

城市间公路及其造价的输出结果

邻接矩阵输出结果

造价排序运行结果

最小生成树的输出结果以及公路总造价最小值

七、总结
经过一周不懈的努力我们终于完成了课程设计。通过这次课程设计，既巩固了以前学过的C语言的知识，体会到C语言超强的逻辑性，能够熟练使用VC++的编译环境，也对这两门课程有了新的认识，他们既有联系，又相互区别，要灵活应用。
利用了课本所学的最小成生树，完成了这一课题，深刻的体会到它的实用性，也发现我们对于C语言和数据结构还有很多地方不知道。程序设计是脑力劳动和体力劳动相结合的，没有平时基础的训练是不会写出高效的算法，今后仍需要努力学习。
课让我尝到了学习的快乐，成功的喜悦。要完成一项任务或把东西学好就必须有足够的信心，持久的耐心，有面对困难无所畏惧的精神，这对我日后的学习和生活产生了深远一个影响。

八、参考文献
[1] 严蔚敏，吴伟民.数据结构[M].北京：清华大学出版社，2007.
[2] 张长海，陈娟.C程序设计[M].北京：高等教育出版社，2004.
[3] 谭浩强.C程序设计[M].北京：清华大学出版社，2005.
[4]陈杰.计算机专业课程设计中的需求分析[J].集美大学学报，2009.
[5]高一凡. 数据结构算法实现及解析[M ]. 西安:西安电子科技大学出版社, 2002.

附 录
程序代码
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#define M 20
#define MAX 20
struct node{
char name[10];
int num;
}vex[20];
typedef struct
{
int begin;
int end;
int weight;
}edge;
typedef struct
{
int adj;
int weight;
}AdjMatrix[MAX][MAX];
typedef struct
{
AdjMatrix arc;
int vexnum, arcnum;
}MGraph;

void CreatGraph(MGraph *);
void MiniSpanTree(MGraph *);
void sort(edge* ,MGraph *);
int Find(int *, int );

void CreatGraph(MGraph *G)
{
int i, j,n,h,m,k;
char u[MAX],v[MAX];
printf("请输入公路数和城市数:");
scanf("%d %d",&G->arcnum,&G->vexnum);

for (i = 1; i <= G->vexnum; i++)//初始化图
{
for ( j = 1; j <= G->vexnum; j++)
{
G->arc[i][j].adj = G->arc[j][i].adj = 0;
}
}
printf("\n请输入城市的信息:");
for(n=1;n<=G->vexnum;n++)
{
scanf("%s",vex[n].name);
vex[n].num=n;
}
for ( i = 1; i <= G->arcnum; i++)
{
printf("\n请输入有公路的2个城市:");
scanf("%s",v);
scanf("%s",u);
for ( k= 1; k <= G->vexnum; k++)
{
if(strcmp(v,vex[k].name)==0)
{m=vex[k].num;}
if(strcmp(u,vex[k].name)==0)
{h=vex[k].num;}
}

G->arc[m][h].adj = G->arc[h][m].adj = 1;
getchar();
printf("\n请输入%s与%s之间的公路造价:",vex[m].name, vex[h].name);
scanf("%d",&G->arc[m][h].weight);
}

printf("邻接矩阵为:\n");
for ( i = 1; i <= G->vexnum; i++)
{
for ( j = 1; j <= G->vexnum; j++)
{
printf("%d ",G->arc[i][j].adj);
}
printf("\n");
}
}
void sort(edge edges[] ,MGraph *G)//对公路造价进行排序
{
int i, j;
int temp;
for ( i = 1; i < G->arcnum; i++)
{
for ( j = i+1; j <=G->arcnum; j++)
{
if (edges[i].weight > edges[j].weight)
{
temp = edges[i].begin;
edges[i].begin = edges[j].begin;
edges[j].begin = temp;
temp = edges[i].end;
edges[i].end = edges[j].end;
edges[j].end = temp;
temp = edges[i].weight;
edges[i].weight = edges[j].weight;
edges[j].weight = temp;
}
}
}

printf("造价排序之后的为:\n");
for (i = 1; i <=G->arcnum; i++)
{
printf("<< %s, %s >> %d\n", vex[edges[i].begin].name, vex[edges[i].end].name, edges[i].weight);
}
}

void MiniSpanTree(MGraph *G)
{
int i, j, n, m,Mincost=0;
int k = 1;
int parent[M];
edge edges[M];

for ( i = 1; i < G->vexnum; i++)
{
for (j = i + 1; j <= G->vexnum; j++)
{
if (G->arc[i][j].adj == 1)
{
edges[k].begin = i;
edges[k].end = j;
edges[k].weight = G->arc[i][j].weight;
k++;
}

}
}

sort(edges, G);
for (i = 1; i <= G->arcnum; i++)
{
parent[i] = 0; //初始化，没有边关系。
}
printf("最小生成树为:\n");
for (i = 1; i <= G->arcnum; i++)
{
n = Find(parent, edges[i].begin);
m = Find(parent, edges[i].end);
if (n != m)
{
parent[n] = m;
printf("<< %s, %s >> %d\n", vex[edges[i].begin].name, vex[edges[i].end].name, edges[i].weight);
Mincost+=edges[i].weight;
}
}
printf("使各城市间公路总造价的最小费用为：Mincost=%d\n",Mincost);
}
int Find(int *parent, int f)
{
while ( parent[f] > 0)
{
f = parent[f];
}
return f;
}

void main()
{
MGraph *G;
char p;
G = (MGraph*)malloc(sizeof(MGraph));
CreatGraph(G);
MiniSpanTree(G);
scanf("%s",&p);
if(p=='out'){
exit(0);
}
}

21