1、 二二 一一 届届 课课 程程 设设 计计 论论 文文 算法与数据结构算法与数据结构 二一年六月二一年六月 目录目录 一、引言一、引言 二、设计目的与任务二、设计目的与任务 1课程设计的目的 2课程设计的任务 三三、设计方案设计方案 1需求分析 2概要设计 3详细设计 4程序清单 四四、调试分析调试分析 五五、测试结果测试结果 六六、附附录录 七七、工作环境工作环境 八八、参考文献参考文献 数据结构课程设计数据结构课程设计 最小生成树问题最小生成树问题 一一、引言引言 数据结构是计算机科学与技术专业和信息系统专业的必修课之一，是一 门综合的专业技术课。 本课程较系统的介绍了软件开发过程中常用的
2、数据结构及 相应的实现算法。如线性表、栈、队列、树和二叉树，图、检索和排列等，并对 性能进行分析和比较，内容非常丰富。 本课程设计我们要解决的是最小生成树问题。要用到图的相关数据结构和最 小生成树的克鲁斯卡尔算法，以及存储图的边和点的邻接矩阵。 本课程设计要解决的问题是构造连通图的最小生成树我们首先要做的是都 造一个邻接表，用以存储图，然后我们要想好怎样利用克鲁斯卡尔算法构造最小 生成树，把这个算法写入主程序，调试好程序，最后完成报告。 二二、设计目的与任务设计目的与任务 1 1课程设计的目的课程设计的目的 本课程设计是为了了解并掌握数据结构及算法的设计方法，具备初步的独立 分析和设计能力；初
3、步掌握软件开发过程的相关步骤；提高运用所学理论知识独 立分析和解决问题的能力； 训练用系统的观点和软件开发的一般规范进行软件开 发。 2 2课程设计的任务课程设计的任务 问题描述：若要在 n 个城市之间建设通信网络，只需架设 n1 条线路即可。 如何以最低的经济代价建设这个通信网，是一个最小生成树的问题。 三三、设计方案设计方案 1 1需求分析需求分析 （1） 利用克鲁斯卡尔算法求最小生成树； （2） 实现教科书 6.5 节中抽象数据类型 MFSet。以此表示构造生成树过程中 的连通分量。 （3） 以文本形式输出生成树中各条边以及它们的权值。 2 2概要设计概要设计 1）抽象数据类型（ADT）
4、如下： ADT GRAPHADT GRAPH 数据对象数据对象 V V：V 是具有相同特性的数据元素的集合，成为顶点集。 数据关系数据关系 R R： R=VR VR=|v,wV 且 P(v,w),表示从 v 到 w 的弧， 谓词 P（v，w）定义了弧的意义或信息 基本操作基本操作 P P： CreateGraph( int end; int weight; edge; typedef struct int adj; int weight; AdjMatrixMAXMAX; typedef struct AdjMatrix arc; int vexnum, arcnum; MGraph; 3）流
5、程图 3 3详细设计详细设计 在该函数中主要有 6 段代码块，分别是图的构建代码，对权值排序的代码， 交换权值代码，最小生成树代码，找尾代码，主函数代码。6 段代码分别实现不 同的功能，共同满足了课题所需要实现的功能。 1 1） 主函数代码主函数代码 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; 2 2） 图的构建代码图的构建代码 void CreatGraph(MGraph *G)/构件图 开始 键入给定图的边数和顶点数 逐个输入任意两顶点间的弧的权值 调用克鲁斯卡尔算法 输出生成树的各边及相应权值 结束 int i, j,n, m; printf(“请输入边数和顶点数:“
