数据结构课程设计

数据结构课程报告。

构造n个城市连接的最小生成树。

学号。姓名。

班级电子信息工程

电子工程系。

一．知识点：

常见的最小生成树算法主要有两种，一种是kruskal算法，一种是prim算法。两种算法使用的都是贪心原则。kruskal算法的基本思想是，先取出权值最小的边，查看这个边的两个端点是否与已经判断过的顶点产生环路，如果产生环路则放弃这条边，否则保存这条边，继续进行判断。

kruskal每次拿取的都是最小的一条边，可以使用数学推理方法证明能够生成一个最小生成树。

实现kruskal算法的思路是，先使用排序算法（我们使用的是快速排序）将边按照权重的大小进行排序，之后需要创建一个不相交集合（disjoint set）（不相交集合可以查看相关算法书，简单的说就是同一个集合中的元素由集合中的一个代表来表示，不相交集合主要包含三个操作，分别是makeset创建不相交集合，并将不相交集初始化，unionset将两个不相交集合并成一个不相交集，findset查询某个元素所在不相交集的代表元素），按照边从前向后的次序进行如下比较。如果边的两端调用findset后返回的结果不相等（说明这条边加入最小生成树中不会引起环路），那么就输出这条边（这条边一定最小生成树的一条边），否则（边的两端调用findset得到相等的返回结果，说明如果将边加入到最小生成树，那么将会产生环路）抛弃这条边。

prim算法的基本思想是，从某一个点出发，选择从这个点出发的权值最小的边，之后现在联通的顶点中已经有两个顶点，从这两个顶点出发，寻找这两个顶点之外且与这两个顶点构成边的顶点，取得这些边的最小权值边，以此类推。

prim算法需要一个堆来辅助执行。算法的思路是这样的，将未处理的顶点按照未处理顶点和已处理顶点的边的最小权值进行堆排序，每次从堆的顶部获取到未处理顶点到已处理顶点的最小边长后，将这个新加入点相关联的边判断是否可以更改堆中的点的权值（堆中点的权值是此未处理点与所有已处理点的最小连线的权值，因此，当有新的点加入到已处理点后，这个新的点很可能改变其他未处理点到已处理集合的最小权值边）。直到堆中无点为止。

二．设计思路及应用功能。

设计思路：城市间的距离网采用邻接矩阵表示，若两个城市之间不存在道路，则将相应边的权值设为自己定义的无穷大值10000。在屏幕上显示得到的最小生成树中包括了哪些城市间的道路，并显示得到的最小生成树距离。

在设计程序时通过数组直接对各个城市之间的信息进行设置，而不是手动输入。城市的个数也默认设置为6个，路的个数也只设置成10个，所以在程序运行时不需要输入城市的相关信息。

应用功能：一个地区的n个城市间的距离网，用prim算法或kruskal算法建立最小生成树，并计算得到城市间的最短距离。

3．概要设计。

本程序的主要内容是通过函数调用构建最小生成树，实现求的两个城市之间的最短路径，并通过函数调用打印出来最短路径所经过的顶点，所有本程序便定义了三个结构体，每个结构体的作用如下所示。

typedef char vertextype[7];

typedef char infoptr;

typedef int vrtype;

typedef enumgraphkind;

typedef struct

vrtype adj对于无权图，用1表示相邻，0表示不相邻，对于带权图，存储权值。

infoptr *info与弧或边的相关信息。

arcnode,adjmatrix[max][max];

typedef struct图的类型定义。

vertextype vex[max]; 用于存储顶点。

adjmatrix arc邻接矩阵、存储边或弧的信息。

int vexnum,arcnum; /顶点数和边（弧）的数目。

graphkind kind图的类型。

mgraph;

typedef struct

//添加一个存储网的行、列和权值的类型定义。

int row;

int col;

int weight;

gnode;

子程序的调用关系。

子程序**：

void creategraph(mgraph *n,gnode *value,int vnum,int arcnum,vertextype *ch)

int i,j,k;//创建邻接矩阵。

vertextype v1,v2;

n->vexnum=vnum;

n->arcnum=arcnum;

for(i=0;i strcpy(n->vex[i],ch[i]);

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

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

for(k=0;k

n->kind=dn;

void floyd(mgraph n,pathmatrix path,shortpathlength dist)//求出最短路径。

int u,v,w,i;

for(v=0;v<

for(w=0;w<

for(u=0;u<

for(v=0;v<

for(w=0;w<

if(dist[v][u]

void display(mgraph n)//打印出城市间的距离信息。

int i,j;

printf("有向网具有%d个顶点%d条弧，顶点依次是：",for(i=0;i<

printf("%s ",printf("有向网n各顶点之间的距离对应如下(10000表示路径无穷大)：");

for(i=0;i<

printf("\tv%d",i);

printf("");

for(i=0;i<

4．测试分析：

运行结果：5．课程总结。

在对构造n个城市连接的最小生成树程序的设计中，学会了在一个有n个的有向网中，如何构建最小生成树，以及如何构建邻接矩阵。

在程序的调试过程中，或者会出现整个程序全部无法运行，导致自己无法知道具体编程错误的地方在何处。错误一般是在子程序中，这就需要单独把子程序拿出来调试，或者加入中断标志，运行时观察程序运行到何处时会停止，然后就这样逐渐排除出现的错误。这是我在调试程序过程中的收获。

一开始只知道最小生成树有prim算法和kruskal算法，具体实现**方式不是很清楚，通过上网查资料，到图书馆查阅书籍，才慢慢清楚**需要怎么写，最后在vc上进行编写和调试程序，这使我对最小生成树的概念更加清晰了。

6．程序源**：

#include<>

#define infinity 10000

#define max 50

typedef char vertextype[7];

typedef char infoptr;

typedef int vrtype;

typedef int pathmatrix[max][max][max];

typedef int shortpathlength[max][max];

typedef enumgraphkind;

typedef struct

vrtype adj;

infoptr *info;

arcnode,adjmatrix[max][max];

typedef struct

vertextype vex[max];

adjmatrix arc;

int vexnum,arcnum;

graphkind kind;

mgraph;

typedef struct

int row;

int col;

int weight;

gnode;

void display(mgraph n)

int i,j;

printf("有向网具有%d个顶点%d条弧，顶点依次是：",for(i=0;i<

printf("%s ",printf("有向网n各顶点之间的距离对应如下(10000表示路径无穷大)：");

for(i=0;i<

printf("\tv%d",i);

printf("");

for(i=0;i<

void creategraph(mgraph *n,gnode *value,int vnum,int arcnum,vertextype *ch);

void displaygraph(mgraph n);

数据结构课程设计

数据结构课程设计

数据结构课程设计

数据结构课程设计

其他用户还读了