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

目录
一、课题描述: 2
二、需求分析 3
三、总体结构设计 4
四、各子模块设计 5
五、编程设计 8
六、测试结果 12
七、总结 14
八、参考文献 15
附录 16
一、课题描述:
设计一张城市地图,图中的顶点为城市,无向边代表两个城市间的连通关系,边上的权代表公路造价。图中任一对城市都是连通的,用公路把所有城市联系起来,设计可使得工程的总造价最少。
二、需求分析
根据课设题目要求,拟将整体程序分为三大模块。此三个模块相互独立,没有嵌套调用的情况,以下是三个模块的大体分析:
1. 建立一个图,其存储方式可以采用邻接矩阵形式,需要定义两个数组,一个存储城市,一个存储公路,存储公路的数组表明城市间的连通关系和公路的造价;。
2. 利用kruskal算法求城市地图的最小生成树
3. 按父亲结点和子女结点集的形式输出生成树中各条边(公路)以及它们的权值(造价),公路总造价最小值。
三、总体结构设计
功能模块图
无
向
图
的
建
立
最
小
生
成
树
的
求
解
按父
结点
和子
女结
点集
的形
式输
出,
求最
小值,
四、各子模块设计
(初始化)

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


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



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


五、编程设计
存储结构
该函数包含三个结构体,即存储城市、存储公路和存储图的结构体,其结构体分别如下所示:

用字符串name表示城市信息,num表示城市的序号。
struct node{
char name[10];
int num;
}vex[20];
用整型begin和end表示公路的起点和终点,weight表示公路的造价。
typedef struct
{
int begin;
int end;
int weight;
}edge;

用整型adj表示城市间的关系,weight表示公路的造价。
typedef struct
{
int adj;
int weight;
}AdjMatrix[MAX][MAX];
用arc表示邻接矩阵,um表示图当前的城市数和公路数。
typedef struct
{
AdjMatrix arc;
int vexnum, um;
}MGraph;
时间复杂度0(n^2)
算法描述
该算法是建立一个带权的无向图,并用Kruskal算法求该图的最小生成树,用父结点和子女结点集的形式输出最小生成树。

图的存储结构如上所示,;用adj是否为1判断两城市间是否有公路,adj为1时表示有公路,反之没有公路,um分别表示城市数和公路数,name和num分别表示城市信息和城市序号,建图的算法如下所示:
void CreatGraph(MGraph *G)
{
int i, j,n,h,m,k;
char u[MAX],v[MAX];
printf("请输入公路数和城市数:");
scanf("%d %d",&G->um,&G->vexnum)
for (i = 1; i <= G->vexnum; i++)//初始化图
{
for ( j = 1; j <= G->vexnum; j++)
{
G-