数据结构课程设计-最小生成树问题

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

1、安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称《数据结构》课题名称最小生成树问题专业计算机科学与技术班级10计本2班学号姓名联系方式指导教师2011年12月30日“最小生成树问题”课程设计题目:编制一个求出N个顶点图的最小生成树程序一需求分析:(1)在n个城市间建设通信网络，只需要架设n-1条线路即可。以最低的代价建设这个通信网，即求图的最小生成树。(2)利用克鲁斯卡尔算法求网的最小生成树。(3)利用自定义的队列结构存放连通分量。(4)以文本形式输出最小生成树中的各条边及它们的权值。输出格式为(inta,intb,

2、intn),其中a，b为顶点序号,n为ab边的权；(5)程序运行流程:1)提示输入顶点数目；2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树；3)输出最小生成树并且退出；(6)测试数据:9二概要设计:1.表示边的类定义和接口:classMyArc{public:intm_beginVex;intm_endVex;intm_weight;MyArc(intbeginVex,intendVex,intweight);MyArc(){}//重载运算符inlinebooloperator<(constMyArc&

3、arc){returnm_weight(constMyArc&arc){returnm_weight>arc.m_weight;}};2.用邻接矩阵表示的图类的定义和接口:classGraph{private:intm_vexnum;intm_arcnum;int*m_pmatrix;public:~Graph();Grap

4、h(intvexnum);Graph(intvexnum,int*pmatrix);voidinsert(MyArcarc);//连通arc边boolbound(intx);//判断顶点x是否已与其它顶点连通};3.自定义队列，用于存放连通图，或按权排列后的边:classMyQueues{public:listm_list;MyQueues(){}voidinsert(constMyArc&arc);//按权值大小排序插入voidInsertGraph(constGraph&graph);//将图的连通分量插

5、入队列MyArcpop();//出队列};4.本程序的结构1)主程序模块:voidmain(){申明边权值矩阵数组并用随机函数初始化；创建图；调用克鲁斯卡尔算法函数；输出边的权值矩阵，最小生成树中的各条边及它们的权值退出；}2)带权的边类模块---实现带权边的存储和运算。邻接矩阵类模块---实现图的状态记录和相关操作。自定义队列类模块---实现边的按权存贮和相关操作。3)核心kruskal算法模块---用克鲁斯卡尔算法求出最小生成树各模块调用关系:三详细设计#include#include

6、.h>//产生随机数组用#include//同上//#include"basic.h"//所用到的自定义数据结构定义和实现文件usingnamespacestd;#include/*MyStack堆栈类的结构[01...curlen...size][栈底(bottom)...prt...]*/#defineBASESIZE64//默认堆栈数组空间大小（8*8）,可以自扩充templateclassMyStack{private:Type*bottom;//元素存放的动态数组

7、intsize,ptr;//堆栈大小和当前栈顶元素索引public://构造函数MyStack(){bottom=newType[BASESIZE];ptr=-1;size=BASESIZE;};//析构函数~MyStack(){delete[]bottom;};//清栈还原inlinevoidclear(){if(bottom!=NULL)delete[]bottom;bottom=newType[size];ptr=-1;};//判栈空inlineboolIsEmpty(){if(ptr==-1)returntrue;

8、elsereturnfalse;}//入栈intpush(Typee);//出栈intpop(Type&e);//获得栈顶元素inttop(Type&e);intsettop(Typee);//用callback函数对栈从低向上遍历voidtraverse(voidcallback(Type*),Typ