大学铺设校园光纤网络。假设有个学院和办公楼，只需要铺设条光缆通道。采用最小生成树的算法，给出个最佳铺设方案。设计要求设计基于最小生成树的校园光缆铺设程序。采用图结构并集树等数据结构。可以随机文件及人工输入数据。采用克鲁斯卡尔算法设计最小代价生成树可以采用堆排序算法选择权值最小的边。采用并集树完成树边的查询和合并。其它完善性或扩展性功能。指导教师签字年月日课题概述课题任务课题原理克鲁斯卡尔算法堆排序并集树相关知识需求分析课题调研用户需求分析方案设计总体功能设计数据结构设计函数原型设计主算法设计用户界面设计输入输出设计方案实现开发环境与工具程序设计关键技术个人设计实现刘诚阳设计实现姚伟设计实现杜宇设计实现测试与调试个人测试刘诚阳测试姚伟测试杜宇测试组装与系统测试系统运行课题总结课题评价团队协作个人设计小结刘诚阳设计小结姚伟设计小结杜宇设计小结附录课题任务分工课题程序设计分工课题报告分工课题设计文档课程设计报告电子版源程序代码，工程与可执行文件屏幕演示录像文件使用手册运行环境说明操作说明课题概述课题任务问题描述东北大学铺设校园光纤网络。假设有个学院和办公楼，只需要铺设条光缆通道。采用最小生成树的算法，给出个最佳铺设方案。设计要求设计基于最小生成树的校园光缆铺设程序。采用图结构并集树等数据结构。可以随机文件及人工输入数据。采用克鲁斯卡尔算法设计最小代价生成树可以采用堆排序算法选择权值最小的边。采用并集树完成树边的查询和合并。其它完善性或扩展性功能。课题原理克鲁斯卡尔算法假设，是个含有个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为先构造个只含个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是个含有棵树的个森林。之后，从网的边集中选取条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成棵树反之，若该条边的两个顶点已落在同棵树上，则不可取，而应该取下条权值最小的边再试之。依次类推，直至森林中只有棵树，也即子图中含有条边为止。通过克鲁斯卡尔算法求最小生成树的过程如下图将边按权重排序，选取最小的边继续选取权重最小的边继续选取，但选取的边不能构成回路完成图克鲁斯卡尔算法选取最小生成树克鲁斯卡尔算法的时间复杂度为为网中边的数目，适合于求边稀疏的网的最小生成树。堆排序堆的定义个元素的序列，当且仅当满足下列关系之时，称之为堆。情形且最大化堆或大顶堆其中，向下取整。堆排序利用了大顶堆或小顶堆堆顶记录的关键字最大或最小这特征，使得在当前无序区中选取最大或最小关键字的记录变得简单。本次课程设计中，采用的是小顶堆实现。用小顶堆排序的基本思想先将初始文件建成个小顶堆，此堆为初始的无序区再将关键字最小的记录即堆顶和无序区的最后个记录交换，由此得到新的无序区和有序区，且满足由于交换后新的根可能违反堆性质，故应将当前无序区调整为堆。然后再次将中关键字最小的记录和该区间的最后个记录交换，由此得到新的无序区和有序区，且仍满足关系，同样要将调整为堆。直到无序区只有个元素为止。小顶堆排序算法的基本操作建堆建堆是不断调整堆的过程，从处开始调整，直到第个节点，此处是堆中元素的个数。建堆的过程是线性的过程，从到处直调用调整堆的过程，相当于其中表示节点的深度，表示节点的个数，这是个求和的过程，结果是线性的。调整堆调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点和它的孩子节点选出三者最小或者最大者，如果最小大值不是节点而是它的个孩子节点，那边交互节点和该节点，然后再调用调整堆过程，这是个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是的操作，因为是沿着深度方向进行调整的。堆排序堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出般是与最后个节点进行交换，将前面个节点继续进行堆调整的过程，然后再将根节点取出，这样直到所有节点都取出。因为建堆的时间复杂度是调用次调整堆的时间复杂度是，调用了次，所以堆排序的时间复杂度是。并集树以集合为基础的抽象数据类型可以用多种实现方法，如用位向量表示集合或用有序表表示集合等。如何高效地实现以集合为基础的抽象数据类型，则取决于该集合的大小以及对此集合所进行的操作。根据集合数据类型所需要的查找和归并操作的特点，我们可以利用树形结构表示集合，从而快速高效地实现集合等价类间的运算。相关知识基本数据结构知识。包括图的基本存储结构，克鲁斯卡尔算法，堆排序算法，并集树的概念和基本操作等。的类及实现。程序设计采用的类进行封装，核心程序和算法使用代码编写。界面设计。使用进行可视化编程的相关知识。需求分析课题调研光纤网络是利用光在玻璃或塑料制成的纤维中的全反射原理而达成的光传导工具接到公司或家或机房。光线传输具有频带宽损耗低重量轻抗干扰强保真度高和性能可靠等优点，而且材料费用也在逐年下降。本课程设计以东北大学铺设校园光纤网络为背景，通过调查研究，编写计算最小铺设费用的程序来求解问题。经过对东北大学的教学馆和办公楼分布调研，选取标志性的建筑作为研究对象，可以将建筑物抽象成顶点，各个建筑物之间的直线距离为边的权重，构造出图模型，设计程序计算最小铺设方案。汉卿会堂建筑馆机电馆图书馆信息馆采矿馆冶金馆综合楼大成楼教学馆逸夫楼图东北大学主要建筑的抽象无向图用户需求分析经过实际的调研，本程序需要满足用户的以下需求输入规范的数据，可以计算得出正确的结果，即最小铺设方案。程序应该具有演示功能，并且可以进行调试。具有良好的健壮性，对于数据要有甄别能力。具有友好的人机交互界面，输入数据和输出数据要显示在界面上，最好能够通过图形演示，使生成方案更加目了然。程序要具有键盘输入随机输入和文件输入三种输入方式，并且能够将计算方案保存到系统磁盘中，即生成文本文件。程序要具有适当的操作提示，以及防止用户操作的避免措施。具有应用程序文件，用户可以双击运行直接使用。方案设计总体功能设计程序主要由以下几个功能模块组成输入功能输出功能生成文件功能计算最小铺设方案功能和图形显示功能。其中，输入功能包括文件输入随机输入和键盘输入三种输入方式输出功能包括将基本信息输出到操作界面的显示框内，以及将计算信息输出到显示框内生成文件功能是将计算所得的最小花费方案生成文本文件存储计算最小铺设方案功能是通过克鲁斯卡尔算法堆排序算法等系列核心算法对输入数据进行处理分析，从而生成最小花费方案图形显示功能通过定位画点与连线，实现数据的图形化，使计算结果更加目了然。程序的主要功能如图所示校园光纤铺设输入功能生成文件功能图形显示功能计算最小花费功能输出数据功能文件输入随机输入键盘输入图校园光线网络铺设功能图数据结构设计边类的设计。考虑到本程序是用来计算最小花费铺设方案的，即用来求图的最小生成树，因此采用边类的存储结构，边类中含有该边连接的两个顶点以及该边的权重。结构设计如下图边设计的类图图类的设计。图类中含有结点数边数和边的地址信息，以及最短路径的地址信息。图图类设计类图函数原型设计程序的函数原型设计和功能如表所示。表校园光纤铺设程序的函数原型和功能设计表函数原型功能描述交换图中的两条边，键盘输入数据，个接个输入随机生成数据，个接个生成从文件读取数据输出数据到文本文件克鲁斯卡尔算法，计算图的最小生成树检验重复输入的函数，阻止输入重复的数据计算文本中数据的行数，辅助于文件读取将图中的顶点进行映射，辅助于画图，堆调整函数，用于堆排序的调整建堆函数，生成小顶堆堆排序算法，对无序数据进行堆排序并集树的查找，并集树的合并判断边是否在同集合图形界面，键盘输入的确定按钮，读取数据建立图图形界面，输入位置信息的按钮，并调用画笔绘制图形图形界面，调用克鲁斯卡尔算法的按钮，并将计算信息传到编辑框内图形界面，键盘输入按钮，开启键盘输入模式图形界面，文件输入按钮，开启文件输入模式，将文件数据读入图形界面，随机输入按钮，调用随机生成函数，读入随机数据图形界面，初始化程序图形界面，调用文本生成函数，输出数据主算法设计本程序所使用的核心算法是克鲁斯卡尔算法。具体实现过程为首先按照各个边的权重建立初始小顶堆，然后每循环次堆排序算法就可以找到条最小权重的边，随后将该边传递给并集树进行判断，看它所关联的顶点是否属于同个联通分量中，若不是则将其存入输出集合中。循环处理直到输出集合中包含的边数为顶点数减或者遍历完整个图为止。若找到了最小生成树，则输出，若没有找到，则该图不连通。算法设计如图所示。开始建初始小顶堆输出集中的边小于结点数且存在未遍历的边输出集合中的边数等于结点数堆排序交换次当前权重最小边的两顶点不在同个联通分量中把此边加入输出集合查找下条边图连通，找到最小生成树图不连通，未找到最小生成树结束结束是否是否是否图克鲁斯卡尔算法设计流程图用户界面设计经过多方面的考虑，本程序决定采用可视化编程，实现图形界面，为用户提供可视化的操作，确保了良好的人机交互功能，并且使得处理结果更加直观明确。可视化图形界面的外观设计如图所示。图校园光纤铺设程序用户操作界面图主界面的类设计为自动生成，如图所示。，