《数据结构课程设计》实习报告——最小生成树

《《数据结构课程设计》实习报告——最小生成树》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构实习报告题目：最小生成树问题一、需求分析1、若要在n个城市间建设通信网络，只需要架设条线路即可。要想用最低的经济代价建设这个通信网，可以用网的最小生成树来解决。2、用存储边的数组表示的无向网来表示n个城市间的通信线路，利用克鲁斯尔算法求网的最小生成树，定义数据类型MFSet,用來构造生成树过程中的连通分量。最后以文本形式输出生成树各边及他们的权值。3、测试数据：mincstree.txt文件数据读入(见附件)。为实现上述程序功能，需要两个抽象数据类型：无向网和等价类。1、无向网的抽象数据类型定义为：ADTMGraph{数据对象

2、：V是具有相同特性的数据元素的集合，称为顶点集。数据关系：R={VR}VR二{vv,w〉

3、v,wWV,表示荣v到w的弧}基本操作：intLocateVex(MGraphG,charu)操作结果：若G屮存在顶点u,则返回该顶点在图屮位置;否则返回・1voidCreateAN(MGraph&G)操作结果：构造无向网G)2、等价类的抽彖数据类型定义为：ADTMFSet{数据对彖：设S是MFSet型的集合，则它由n(n〉0)个子集Si(i=2,...,n)构成。数据关系：SluS2U...USn=SSi属于S(i=2,...,n)基

4、本操作：voidlnitMfset(MFSet&S,MGraphG)操作结果：初始化等价类intfind_mfset(MFSet&S,inti)操作结果：查找i属于所在集合并返回intis_mfset(MFSet&S,intvi,intvj)操作结果：判断ij是否屈于一个集合，是返回1,否则返回0intmin_mfset(MFSet&S,inti,intj)操作结杲：和并ij所在的两个集合}3、程序基本模块：(1)、无向网构造模块：构造网中顶点和边的信息(2)、等价类构造模块：将各个顶点看做等价类，并初始化(1)、求最小生成树模块：m

5、inspantree(G,S)用快速排序方法将存放边的数组按边的权值从小到大排列为有序数组；ecnum计连通分量个数，初始值为网中边数；while(ecnum>l){取当前权值最小的边；if(边的两个端点不在一个等价类屮){合并这两个等价类；输出这条边的信息：ecnum-;}}(2)、主程序模块voidmain(){创建MGraph,MFSet对象；构造无向网G；初始化MFSet类型对彖S；求最小生成树；}三、详细设计#include#include#include#inelude

6、stream.h>#defineMAX_VERTEX_NUM30//最大顶点个数structVertexType//顶点类型{charvex;intparent;}；structArcCellType//边的类型{intadj;//权值intvi,vj;〃端点}；structMGraph〃无向图结构{VertexTypevexs[MAX_VERTEX_NUM];//顶点向量ArcCellTypearcs[MAX_VERTEX_NUM*(MAX_VERTEX_NUM-1)/2+1];//存储边的数组intvexnum,arcnum;//

7、图的当前顶点数和弧数}；structMFSet//等价类结构VertexTypenodes[MAX_VERTEX_NUM];intr,n;//根的位置和结点数}；voidInitMfset(MFSet&S,MGraphG){//初始化等价类inti;S.n=G.vexnum;for(i=0;i

8、exs[i].vex)returni;return-1;}voidCreateAN(MGraph&G){//构造无向网Gintijkw;charva,vb;FILE*graphlist;graph!ist=fopenCrnincstree.txTTT');fscanf(graphlist,H%d",&G.vexnum);fscanf(graphlist/%d,&Garcnum);for(i=0;i

9、=G.arcnum;++k)fscanf(graphlist/%s%s%(T；&va，&vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);Garcs[k]