数据结构课程设计报告 (2).doc

1、目录一、引言 二、设计目的与任务 1课程设计的目的2课程设计的任务三、设计方案 1需求分析 2概要设计 3详细设计 4程序清单四、调试分析五、测试结果六、附录七、工作环境八、参考文献 数据结构课程设计 最小生成树问题一、引言数据结构是计算机科学与技术专业和信息系统专业的必修课之一，是一门综合的专业技术课。本课程较系统的介绍了软件开发过程中常用的数据结构及相应的实现算法。如线性表、栈、队列、树和二叉树，图、检索和排列等，并对性能进行分析和比较，内容非常丰富。本课程设计我们要解决的是最小生成树问题。要用到图的相关数据结构和最小生成树的克鲁斯卡尔算法，以及存储图的边和点的邻接矩阵。本课程设计要解决的

2、问题是构造连通图的最小生成树我们首先要做的是都造一个邻接表，用以存储图，然后我们要想好怎样利用克鲁斯卡尔算法构造最小生成树，把这个算法写入主程序，调试好程序，最后完成报告。二、设计目的与任务1课程设计的目的本课程设计是为了了解并掌握数据结构及算法的设计方法，具备初步的独立分析和设计能力；初步掌握软件开发过程的相关步骤；提高运用所学理论知识独立分析和解决问题的能力；训练用系统的观点和软件开发的一般规范进行软件开发。2课程设计的任务问题描述：若要在n个城市之间建设通信网络，只需架设n1条线路即可。如何以最低的经济代价建设这个通信网，是一个最小生成树的问题。三、设计方案1需求分析（1） 利用克鲁斯卡

3、尔算法求最小生成树；（2） 实现教科书6.5节中抽象数据类型MFSet。以此表示构造生成树过程中的连通分量。（3） 以文本形式输出生成树中各条边以及它们的权值。2概要设计1） 抽象数据类型（ADT）如下：ADT GRAPH数据对象V：V是具有相同特性的数据元素的集合，成为顶点集。数据关系R： R=VR VR=|v,wV且P(v,w),表示从v到w的弧，谓词P（v，w）定义了弧的意义或信息 基本操作P： CreateGraph(&G,V,VR) 初始条件：v是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 DestroyGraph(&G) 初始条件：图G存在。 操作结果：

4、销毁图G LocateVex(G,u) 初始条件：图G存在，u和G中定点有相同特征。 操作结果：若图G中存在顶点u，则返回顶点在图中的位置；否则返回其他信息。 GetVex(G,v) 初始条件：图G存在，v是G中某个顶点。 操作结果：返回v的值。 PutVex(&G,v,value). 初始条件：图G存在。 操作结果：对v赋值value。2） 存储结构 typedef structint begin;int end;int weight;edge;typedef structint adj;int weight;AdjMatrixMAXMAX;typedef structAdjMatrix a

5、rc;int vexnum, arcnum;MGraph;3） 流程图开始键入给定图的边数和顶点数逐个输入任意两顶点间的弧的权值调用克鲁斯卡尔算法输出生成树的各边及相应权值结束3详细设计 在该函数中主要有6段代码块，分别是图的构建代码，对权值排序的代码，交换权值代码，最小生成树代码，找尾代码，主函数代码。6段代码分别实现不同的功能，共同满足了课题所需要实现的功能。1） 主函数代码int main(void)/主函数MGraph *G;G = (MGraph*)malloc(sizeof(MGraph);if (G = NULL)printf(memory allcation failed,go

6、odbye);exit(1);CreatGraph(G);MiniSpanTree(G);system(pause);return 0;2） 图的构建代码 void CreatGraph(MGraph *G)/构件图int i, j,n, m;printf(请输入边数和顶点数:);scanf(%d %d,&G-arcnum,&G-vexnum);for (i = 1; i vexnum; i+)/初始化图for ( j = 1; j vexnum; j+)G-arcij.adj = G-arcji.adj = 0;for ( i = 1; i arcnum; i+)/输入边和权值printf(

7、n请输入有边的2个顶点);scanf(%d %d,&n,&m);while(n G-vexnum | m G-vexnum)printf(输入的数字不符合要求 请重新输入:);scanf(%d%d,&n,&m);G-arcnm.adj = G-arcmn.adj = 1;getchar();printf(n请输入%d与%d之间的权值:, n, m);scanf(%d,&G-arcnm.weight);printf(邻接矩阵为:n);for ( i = 1; i vexnum; i+)for ( j = 1; j vexnum; j+)printf(%d ,G-arcij.adj);printf

8、(n);3） 对权值排序的代码void sort(edge edges,MGraph *G)/对权值进行排序int i, j;for ( i = 1; i arcnum; i+)for ( j = i + 1; j arcnum; j+)if (edgesi.weight edgesj.weight)Swapn(edges, i, j);printf(权排序之后的为:n);for (i = 1; i arcnum; i+)printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);4） 交换权值代码void Swapn(edge *edges,i

9、nt i, int j)/交换权值 以及头和尾int temp;temp = edgesi.begin;edgesi.begin = edgesj.begin;edgesj.begin = temp;temp = edgesi.end;edgesi.end = edgesj.end;edgesj.end = temp;temp = edgesi.weight;edgesi.weight = edgesj.weight;edgesj.weight = temp;5） 最小生成树代码void MiniSpanTree(MGraph *G)/生成最小生成树int i, j, n, m;int k =

10、 1;int parentM;edge edgesM;for ( i = 1; i vexnum; i+)for (j = i + 1; j vexnum; j+)if (G-arcij.adj = 1)edgesk.begin = i;edgesk.end = j;edgesk.weight = G-arcij.weight;k+;sort(edges, G);for (i = 1; i arcnum; i+)parenti = 0;printf(最小生成树为:n);for (i = 1; i arcnum; i+)/核心部分n = Find(parent, edgesi.begin);m

11、= Find(parent, edgesi.end);if (n != m)parentn = m;printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);6）找尾代码int Find(int *parent, int f)/找尾while ( parentf 0)f = parentf;return f; 4程序清单/*Name:最小生成树kruskal算法Author:Song ChangzhiDescription:生成最小生成树 Date: 2010-06-15 20:07Copyright:Song Changzhi*/#inclu

12、de#include#define M 20#define MAX 20typedef structint begin;int end;int weight;edge;typedef structint adj;int weight;AdjMatrixMAXMAX;typedef structAdjMatrix arc;int vexnum, arcnum;MGraph;void CreatGraph(MGraph *);/函数申明void sort(edge* ,MGraph *);void MiniSpanTree(MGraph *);int Find(int *, int );void

13、Swapn(edge *, int, int);void CreatGraph(MGraph *G)/构件图int i, j,n, m;printf(请输入边数和顶点数:);scanf(%d %d,&G-arcnum,&G-vexnum);for (i = 1; i vexnum; i+)/初始化图for ( j = 1; j vexnum; j+)G-arcij.adj = G-arcji.adj = 0;for ( i = 1; i arcnum; i+)/输入边和权值printf(n请输入有边的2个顶点);scanf(%d %d,&n,&m);while(n G-vexnum | m G

14、-vexnum)printf(输入的数字不符合要求 请重新输入:);scanf(%d%d,&n,&m);G-arcnm.adj = G-arcmn.adj = 1;getchar();printf(n请输入%d与%d之间的权值:, n, m);scanf(%d,&G-arcnm.weight);printf(邻接矩阵为:n);for ( i = 1; i vexnum; i+)for ( j = 1; j vexnum; j+)printf(%d ,G-arcij.adj);printf(n);void sort(edge edges,MGraph *G)/对权值进行排序int i, j;fo

15、r ( i = 1; i arcnum; i+)for ( j = i + 1; j arcnum; j+)if (edgesi.weight edgesj.weight)Swapn(edges, i, j);printf(权排序之后的为:n);for (i = 1; i arcnum; i+)printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);void Swapn(edge *edges,int i, int j)/交换权值 以及头和尾int temp;temp = edgesi.begin;edgesi.begin = edgesj.

16、begin;edgesj.begin = temp;temp = edgesi.end;edgesi.end = edgesj.end;edgesj.end = temp;temp = edgesi.weight;edgesi.weight = edgesj.weight;edgesj.weight = temp;void MiniSpanTree(MGraph *G)/生成最小生成树int i, j, n, m;int k = 1;int parentM;edge edgesM;for ( i = 1; i vexnum; i+)for (j = i + 1; j vexnum; j+)if

17、 (G-arcij.adj = 1)edgesk.begin = i;edgesk.end = j;edgesk.weight = G-arcij.weight;k+;sort(edges, G);for (i = 1; i arcnum; i+)parenti = 0;printf(最小生成树为:n);for (i = 1; i arcnum; i+)/核心部分n = Find(parent, edgesi.begin);m = Find(parent, edgesi.end);if (n != m)parentn = m;printf( %dn, edgesi.begin, edgesi.

18、end, edgesi.weight);int Find(int *parent, int f)/找尾while ( parentf 0)f = parentf;return f;int main(void)/主函数MGraph *G;G = (MGraph*)malloc(sizeof(MGraph);if (G = NULL)printf(memory allcation failed,goodbye);exit(1);CreatGraph(G);MiniSpanTree(G);system(pause);return 0;四、调试分析终于，在老师的耐心指导和同学的帮助下，我的课设任务完成

19、了。通过这次课程设计中遇到的许多问题，我收获颇多，下面就谈一谈我遇到的一个主要问题及相应的产生原因。问题：顶点名的类型识别。现象：当用字母表示顶点时，程序进入死循环。原因：顶点名称与顶点数属于同一数据类型即是int整形,当出现类型冲突时，程序不能识别就会发生冲突。五、测试结果当运行程序时，进入每一步都会有相应提示，这会对程序的使用者提供较大的便利。下面就是程序运行时的一些截图。1） 对给定的图运行程序 下面是给定的图运行程序2） 输入顶点数和边数后 3） 输入各边及其权值后 4） 运行结果 六、附录由于添加了如下两段代码：printf(邻接矩阵为:n);for ( i = 1; i vexnu

20、m; i+)for ( j = 1; j vexnum; j+)printf(%d ,G-arcij.adj);printf(n);printf(权排序之后的为:n);for (i = 1; i arcnum; i+)printf( %dn, edgesi.begin, edgesi.end, edgesi.weight);程序又可以将图的邻接矩阵和排序后的权值列出来，多实现了两个附加功能。这对于程序的使用者而言将能更直观更方便的理解有图到最小生成树的运算过程，有利于对克鲁斯卡尔算法的理解和掌握。七、工作环境编译环境：Dev-C+4.9.9.2文档书写工具:Microsoft Office Word2003 硬件环境：Intel(R) Core(TM)2 Duo CPUT5870 2.00Hz 2.00GB 内存八、参考文献数据结构（C语言版）严蔚敏 吴伟民编著 清华大学出版社 数据结构 严蔚敏（教学视频）数据结构算法实现及解析 高一凡 西安电子科技大学出版社 宋常志 2407080121 2010年6月15日