沈阳航空航天大学
课 程 设 计 报 告
课程设计名称：数据结构课程设计 课程设计题目：构造可以使n个城市连接的
最小生成树
沈阳航空航天大学课程设计报告
目 录
1 算法分析 .................................................................................................................... 1 1.1假设条件 ................................................................................................................. 1 1.2算法描述 ................................................................................................................. 1 1.2.1 城市间的距离网的存储结构 ....................................................................... 1 1.2.2 克鲁斯卡尔算法 ........................................................................................... 2 2 系统设计 .................................................................................................................... 2 2.1设计说明 ................................................................................................................. 2 2.2数据结构描述 ......................................................................................................... 4 2.3 MAIN(主函数） ....................................................................................................... 4 2.4 KRUSHAL(克鲁斯卡尔算法） ................................................................................. 5 2.5 JUDGE(判断是否为连通图) .................................................................................... 6 3 系统实现 .................................................................................................................... 8 3.1错误分析 ................................................................................................................. 8 3.2实现结论 ................................................................................................................. 8 参考文献 .......................................................................................................................... 9 附 录 .......................................................................................................................... 10
I
沈阳航空航天大学课程设计报告
1 算法分析
1.1假设条件
城市间的距离网采用邻接矩阵存储，最大为100100的邻接矩阵，并且输入两城市之间的距离（权值）。
输入的数据为无向图的顶点数和边的权值，顶点数为大于0小于100的整数，，还有邻接矩阵的值（起点和终点），都为非负整数。
输入数据判断是否能生成最小生成树。
1.2算法描述
1.2.1 城市间的距离网的存储结构
邻接矩阵存储方法（数组存储方法），利用两个数组来存储一个图，其构造原理比较简单。
对于具有n个顶点的图G=(V,E),定义一个具有n个元素的一维数组VERTEX[0..n-1]，将图中顶点的数据信息分别存入该数组的一个数组元素中。另外，定义一个二维数组A[0..n-1][0..n-1],该二维数组通常被称为邻接矩阵。若以顶点在VERTEX数组中的下标来代表一个顶点，则邻接矩阵中元素A[i][j]存放顶点i到顶点j之间的关系信息，有
1 当顶点i与顶点j之间有边时
A[i][j] = 0 当顶点i与顶点j之间无边时
对于网络，有
Wij 当顶点i与顶点j之间有边时，且边上的权值为Wij时
A[i][j] =
当顶点i与顶点j之间无边时
1
沈阳航空航天大学课程设计报告
1.2.2 克鲁斯卡尔算法
a. 设置计数器E，初值为0，记录已选中的边数。将所有边从小到大排序，存于p[ ]中。
b. 从p[ ]中选择一条权值最小的边，检查其加入到最小生成树中是否会构成回 路，若是，则此边不加入生成树；否则，加入到生成树中，计数器E累加1。 c. 从E中删除此最小边，转b继续执行，直到k=n-1, 算法结束 d. 判断是否构成回路的方法：
设置集合S，其中存放已加入到生成树中的边所连接的顶点集合，当一条新 的边要加入到生成树中时，检查此边所连接的两个顶点是否都已经在S中，若是， 则表示构成回路，否则，若有一个顶点不在S中 或者两个顶点都不在S中，则 不够成回路。
2 系统设计
2.1设计说明
该程序设计共包括五大模块：主程序模块，邻接矩阵建立模块，连通图判定模块，求最小生成树模块，退出模块。主程序中调用了其他所有四个模块，连通图的判定模块与求最小生成树模块都调用了邻接矩阵建立模块中建立的邻接矩阵。求最小生成树模块中包含了三个函数为初始化模块，判断回路模块，能够生成最小生成树边集合模块。函数模块关系如图2.1.1所示：
2
沈阳航空航天大学课程设计报告
主程序 输入城市信息 判断是否为求最小生退出 连通图 成树 初始化 判断是否构成将能够最小生回路 成树的边集合 打印输出最小生成树及代价
图2.1 函数模块关系图
3
沈阳航空航天大学课程设计报告
2.2数据结构描述
用n表示城市的个数，st表示起始城市，ed表示终点城市，dis表示两城市间的距离。下面是构成该结构体的源代码： typedef struct node
{
int st ;/*起点*/ int ed;/*终点*/ int dis ;/*距离*/
}node; node p[]； /*p[]数组用来储存
城市和城市间的信息*/
2.3 main(主函数）
功能：连接各个函数，确定他们的执行顺序和条件。
工作过程：主函数调用其他四个函数，分别为输入城市信息，判断是 否连通，生成最小生成树，退出。
4
沈阳航空航天大学课程设计报告
开始菜单1234输入城市信息判断是否连通生成最小生成树退出结束
图2.2 main(主函数）
2.4 krushal(克鲁斯卡尔算法）
功能：根据输入城市距离网利用此算法生成最小生成树。 工作过程：首先初始化数组，将所有边按从小到大的顺序
排好，再判断两点是否构成回路，最后打印边的起点，终点，权值，代价。
5
沈阳航空航天大学课程设计报告
开始初始化数组所有边按从大到小排序两点不构成回路打印边，权值，代价结束
图2.3 krushal(克鲁斯卡尔算法)
2.5 Judge(判断是否为连通图)
功能：判断输入的无向图是否为连通图。
参数含义：Graph G为之前建立好的无向图的邻接矩阵。
工作过程：首先初始化数组，找到最小的low[]的值，修改low[]值和 Close[]值判断。
6
沈阳航空航天大学课程设计报告
开始初始化数组找到最小的low[]的值修改low[]和close[]的值yAns<100000000n能构成最小生成树不能构成最小生成树结束 ……………………….
图2.4 Judge连通图判定函数
7
沈阳航空航天大学课程设计报告
3 系统实现
3.1错误分析
(1)错误现象：当输入错误数据比如邻接矩阵时，数据比较多，就容易输错，而且是无向图，在邻接矩阵中是对称的。
错误原因：程序中缺少对数据合法性的判断，且程序的实现对数据的范围是有规定的，当输入不合法的数据时，程序将不能正常执行。
解决方法：加入条件语句，对输入的数据的合法性进行判断，当数据是合法的，则允许下面的程序执行，否则输出提示信息。
(2)错误现象：程序给出的结果是输入数据不合法，而理论上单一的顶点也是连通图。
错误原因：还是程序对数据的限制导致的错误，编程时没有考虑到单一顶点的情况。
解决方法：增加一个判定语句，当输入的是单一顶点的无向图时，直接给出正确的结果。
(3)错误现象：程序运行时即便输入的图是连通图，但输出的结果却是此图不是连通图。
错误原因：单步跟踪发现，不能正常执行的原因是因为函数参数与全局变量中的参数冲突。
解决方法：改变了基本操作中的参数，使其与全局变量不冲突。
3.2实现结论
该程序实现了输入一个无向图，并将图存储在邻接矩阵中，判断该无向图是否是连通图，并能寻找到使之生成最小生成树的条件并且要求输出最小生成树的边和权值，最小生成树的代价。
8
沈阳航空航天大学课程设计报告 错误！未指定书
签。
参考文献
[1] 严蔚敏 吴伟民 ， 数据结构（C语言版）［M］. 北京：清华大学出版社，2006 [2] 张千帆 ， 数据结构与算法（C语言实现）[M] . 北京：科学出版社，2009 [3] 吕国英 ， 算法设计与分析 [M] . 北京：清华大学出版社，2006 [4] 徐宝文 李志 ，C程序设计语言[M] . 北京：机械工业出版社，2004 [5] 张长海 陈娟 ，C程序设计语言[M] . 北京：高等教育出版社，2004
9
沈阳航空航天大学课程设计报告
附 录
#include typedef struct node /*构造一个结构体，两个城市可以看成起点和终点，之间的道路可以看成一个边*/ { node p[1000],temp; int pre[1000],rank[1000];/*用于判断是否构成回路*/ int n=0,a[100][100];/*n表示城市个数，a[][]记录城市间权值*/ int menu( ) /*菜单函数*/ { } /*下面三个函数作用是检验当一条边添加进去，是否会产生回路*/ void set(int x)/*初始化*/ { } pre[x] = x; rank[x] = 0; int m; printf(\" 求最小生成树\\n\"); printf(\" ________________________________\\n\\n\"); printf(\" 1 输入城市之间的信息\\n\"); printf(\" 2 判断是否能构成一个最小生成树\\n\"); printf(\" 3 遍历所有城市生成最小生成树\\n\"); printf(\" 4 退出\\n\"); printf(\" ________________________________\\n\\n\"); printf(\" 请输入所选功能--4\\n\"); scanf(\"%d\",&m); return m; /*p记录城市信息*/ int st; /*起点*/ int ed; /*终点*/ int dis;/*距离*/ }node; 10 沈阳航空航天大学课程设计报告 int find(int x)/*找到这个点的祖先*/ { void Union(int x,int y)/*将这两个添加到一个集合里去*/ { x = find(x); y = find(y); if(rank[x] >= rank[y]) { pre[y] = x; rank[x] ++; else pre[y] = x; if(x != pre[x]) return pre[x]; pre[x] = find(pre[x]); } } } void Kruskal( ) { int ans = 0,i,j,k = 0; int index; int count = 0; { } for(i=1;i<=k;i++) { index=i; for(j=i+1;j<=k;j++) if(p[j].dis for(j = i + 1;j <= n;j ++) { } p[++k].st = i; p[k].ed = j; p[k].dis = a[i][j]; /*先把所有城市之间的路段看成一个边*/ set(i); /*记录打印边的条数*/ for(i = 1;i <= n;i ++) /*初始化数组pre[x],rank[x]*/ for(i = 1;i <= n;i ++) /*ans用来记录生成最小树的权总值*/ 11 沈阳航空航天大学课程设计报告 void create( ) { } /*显示生成的最小生成树*/ { if(n == 0) { } printf(\"遍历所有城市得到最小生成树为：\\n\\n\\n\"); printf(\"这里没有城市之间的信息\\n\"); return; int i,j; if(n != 0) { char str[100]; printf(\"是否要确定输入新的城市之间的信息? (y/n) ?\\n\"); scanf(\"%s\",str); if(strcmp(str,\"n\") == 0 ) } printf(\"请输入城市的个数:\\n\"); scanf(\"%d\",&n); printf(\"输入%d个城市的邻接矩阵:\\n\",n); for(i = 1;i <= n;i ++) { for(j = 1;j <= n;j ++) scanf(\"%d\",&a[i][j]); } return ; /*输入城市信息*/ } } for(i = 1;i <= k;i ++) { } printf(\"\遍历所有城市得到最小生成树的代价为: %d\\n\\n\",ans); if(find(p[i].st) != find(p[i].ed))/*如果这两点连接在一起不构成一个回路，则执行下 { } printf(\"\第%d条路段为：%d--%d,权值为%d\\n\",++ ans += p[i].dis; /*说明这条路段要用*/ 面操作*/ count,p[i].st,p[i].ed,p[i].dis);/*将这条边的起点、终点打印出来*/ Union(p[i].st,p[i].ed); void display( ) 12 沈阳航空航天大学课程设计报告 void judge( )/*判断是否能够生成最小生成树*/ */ int use[100]; use[1] = 1; for(i = 2;i <= n;i ++) { { int close[100],low[100],i,j,ans = 0;/*close[j]表示离j最近的顶点，low[j]表示离j最短的距离 Kruskal( ); } low[i] = a[1][i]; /*初始化*/ close[i] = 1; use[i] = 0; } for(i = 1;i < n;i ++) { int min = 100000000,k = 0; for(j = 2;j <= n;j ++) { if(use[j] == 0 && low[j] > a[k][j]) { low[j] = a[k][j]; /*修改low[]值和close[]值*/ close[j] = k; { if(use[j] == 0 && min > low[j])/*找到最小的low[]值，并记录*/ } { } min = low[j]; k = j; for(j = 2;j <= n;j ++) } ans += a[close[k]][k]; } if(ans >= 100000000) printf(\"不能构成最小生成树\\n\"); printf(\"能构成最小生成树\\n\"); } } else 13 沈阳航空航天大学课程设计报告 int main( ) /*主函数*/ { while(1) { switch( menu( ) ) { case 1:create( );break;/*输入城市信息*/ case 2:judge( );break;/*判断是否能够生成最小生成树*/ case 3:display( );break; case 4:exit( 0 ); } } return 0; } /*显示生成的最小生成树*/ 14 课程设计总结： 通过两周的数据结构课程实训，我不仅对图的概念有了一个新的认识，而且对算法和C语言有了更深的理解，在学习离散数学的时候，总觉得图是很抽象的东西，但是在学习了《数据结构》这门课后，我慢慢地体会到了其中的奥妙，图能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比如说权值、顶点个数等，这也是说明了想要把生活中的信息转化成到计算机中必须用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点之间的联系，图分为有向图和无向图，而无向图又是有向图在权值双向相等下的一种特例。在这次求可使构成n个城市的最小生成树的程序设计中，我采用了a[ i][ j]数组利用邻接矩阵方式来储存城市与城市间信息，再利用经典的克鲁斯克尔算法求得了最小生成树。 在这次课程设计中，我明白了编写一段代码，我们不仅要考虑它的可行性，更应该考虑它的算法复杂度，运行效率。做同一件事，一万个人有一万种做法，换而言之，一万个人写一段代码实现同一个功能可以得到一万段代码。由此，我们可以看出做一件事要精益求精，多加斟酌。 指导教师评语： 指导教师(签字)： 年 月 日 课程设计成绩 因篇幅问题不能全部显示，请点此查看更多更全内容