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

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

2、),其中a，b为顶点序号,n为ab边的权；(5)程序运行流程: 1)提示输入顶点数目； 2)接受输入，按照项目要求产生边权值的随机矩阵；然后求解最小生成树； 3)输出最小生成树并且退出；(6)测试数据:9二 概要设计:1.表示边的类定义和接口:class myarcpublic: int m_beginvex; int m_endvex; int m_weight; myarc(int beginvex,int endvex,int weight); myarc() /重载运算符 inline bool operator (const myarc& arc) return m_weight (

3、const myarc& arc) return m_weightarc.m_weight; ;2. 用邻接矩阵表示的图类的定义和接口:class graphprivate: int m_vexnum; int m_arcnum; int *m_pmatrix;public: graph(); graph(int vexnum); graph(int vexnum,int *pmatrix); void insert(myarc arc);/连通arc 边 bool bound(int x); /判断顶点x是否已与其它顶点连通;3. 自定义队列，用于存放连通图，或按权排列后的边:class m

4、yqueuespublic: list m_list; myqueues() void insert(const myarc& arc); /按权值大小排序插入 void insertgraph(const graph &graph); /将图的连通分量插入队列 myarc pop();/出队列;4.本程序的结构1)主程序模块:void main()申明边权值矩阵数组并用随机函数初始化；创建图；调用克鲁斯卡尔算法函数；输出边的权值矩阵，最小生成树中的各条边及它们的权值退出；2)带权的边类模块-实现带权边的存储和运算。邻接矩阵类模块-实现图的状态记录和相关操作。自定义队列类模块-实现边的按权存贮

5、和相关操作。3)核心kruskal算法模块-用克鲁斯卡尔算法求出最小生成树 各模块调用关系:三 详细设计#include#include/产生随机数组用#include /同上/#include basic.h /所用到的自定义数据结构定义和实现文件using namespace std;#include/*mystack 堆栈类的结构 0 1 . curlen . size 栈底(bottom) . prt . */#define basesize 64 /默认堆栈数组空间大小（8*8）,可以自扩充template class mystackprivate: type *bottom; /

6、元素存放的动态数组 int size,ptr; / 堆栈大小和当前栈顶元素索引public: /构造函数 mystack() bottom=new typebasesize;ptr=-1;size=basesize; ; /析构函数 mystack()delete bottom; /清栈还原 inline void clear() if(bottom!=null) delete bottom; bottom=new typesize; ptr=-1; ; /判栈空 inline bool isempty() if(ptr=-1) return true; else return false;

7、/入栈 int push(type e); /出栈 int pop(type &e); /获得栈顶元素 int top(type &e); int settop(type e); / 用callback函数对栈从低向上遍历 void traverse(void callback(type *),type *); private: inline int extent() int s=size; type *temp=new typesize; for(int i=0;is;i+) tempi=bottomi; size*=2; clear(); ptr=s+1; for(int i=0;is;i

8、+) bottomi=tempi; delete temp; return size; ;/*mystack的实现 */*压栈*/template int mystack:push(type e) / if(+ptr=size) extent(); bottomptr=e; return ptr; /*出栈*/template int mystack:pop(type &e) / if(ptr=-1) return -2;/栈空，返回 -2 ！ else e=bottomptr-; return ptr;/*获取栈顶元素*/template int mystack:top(type &e) /

9、 if(ptr=-1) return -1;/栈空,返回 -1 ！ else e=bottomptr; return ptr;/*设置栈定元素*/template int mystack:settop(type e) / if(ptr=-1) return -1;/栈空,返回 -1 ！ else bottomptr=e; return ptr;/*用callback函数对栈从低向上遍历*/template void mystack:traverse(void callback(type *),type *e) if(callback!=null) for(int i=0;i=ptr;i+) e

10、=&bottomi; callback(e); ; / /*mypoint 坐标结构 */typedef struct mypoint int x, y; *pmypoint;/*表示边的类*/class myarcpublic: int m_beginvex; int m_endvex; int m_weight; myarc(int beginvex,int endvex,int weight); myarc() bool operator (const myarc& arc) return m_weight (const myarc& arc) return m_weightarc.m_

11、weight; ;myarc:myarc(int beginvex,int endvex,int weight):m_beginvex(beginvex),m_endvex(endvex),m_weight(weight)/*用邻接矩阵表示的图类，可以带权，权不可以为0*/class graphpublic: int m_vexnum; int m_arcnum; int *m_pmatrix;public: graph(); graph(int vexnum); graph(int vexnum,int *pmatrix); void insert(myarc arc);/按权值大小排序插入

12、 bool bound(int x); /判断顶点x是否已与其它顶点连通;/构造函数graph:graph(int vexnum) m_pmatrix=new intvexnum*vexnum; m_vexnum=vexnum;m_arcnum=0; for(int i=0;ivexnum*vexnum;+i) m_pmatrixi=0;/构造函数graph:graph(int vexnum,int *pmatrix) m_vexnum=vexnum; / m_arcnum=arcnum; m_pmatrix=new intm_vexnum*m_vexnum; for(int i=0;im_v

13、exnum*m_vexnum;+i) m_pmatrixi=pmatrixi;/测试 顶点x是否已与其他点连通bool graph:bound(int x) for(int i=0;im_vexnum;+i) if(m_pmatrixx+i*m_vexnum!=0) return true; return false;/在邻接表中连通 arc表示的边，并且设置权void graph:insert(myarc arc) m_pmatrixarc.m_beginvex*m_vexnum+arc.m_endvex=arc.m_weight; m_pmatrixarc.m_endvex*m_vexnu

14、m+arc.m_beginvex=arc.m_weight; +m_arcnum;graph:graph() delete m_pmatrix;/*自定义队列，用于存放连通图，或按权排列后的边*/class myqueuespublic: list m_list; myqueues() void insert(const myarc& arc);/边按权值插入队列中合适位置, void insertgraph(const graph &graph);/将图的连通分量插入队列 myarc pop();/边出队myarc myqueues:pop() myarc arc=m_list.front(

15、); m_list.pop_front(); return arc;/边按权值插入队列中合适位置,void myqueues:insert(const myarc& arc) list:iterator pos=m_list.begin(); while(pos!=m_list.end() if(*posarc) break; else +pos; m_list.insert(pos,arc);/将图的连通分量插入队列void myqueues:insertgraph(const graph &graph) for(int i=0;igraph.m_vexnum;+i) for(int j=i

16、+1;jgraph.m_vexnum;+j) if(graph.m_pmatrixi*graph.m_vexnum+j) insert(myarc(i,j,graph.m_pmatrixi*graph.m_vexnum+j); bool iscycle(graph &graph,myarc& arc); /判断是否构成回路void kruskal(const graph& graph,graph& smtree);/克鲁斯卡尔算法void smallesttreeoutput(const graph& smtree); /输出最小生成树 void setmatrix(int vexnum,in

17、t *matrix); /用随机数组初始化matrix数组并且打印/*主函数*/void main()char i;cout*endl;cout”标题:最小生成树”endl;cout班级:计本2班endl;cout姓名:张娟endl;cout学号:10012121 endl;cout*endl; couti; int vex=i-0; int *matrix=new intvex*vex; coutendl; setmatrix(vex,matrix); graph graph(vex,matrix),smtree(vex); kruskal(graph,smtree); smallesttr

18、eeoutput(smtree); delete matrix;/用随机数组初始化matrix数组并且打印void setmatrix(int vexnum,int *pmatrix) srand(unsigned)time(null); for(int i=0;ivexnum;+i)/产生随机权值矩阵 for(int j=i;jvexnum;+j) if(j=i) pmatrixi*vexnum+j=0; continue; int rnum=rand();rnum%=99;rnum+;/产生199的随机整数作为边的权值 pmatrixi*vexnum+j=rnum; pmatrixj*ve

19、xnum+i=rnum; cout*随机产生的各边权值矩阵 顶点数为 vexnum *n; for( i=0;ivexnum;+i)/输出随机权值矩阵 for(int j=0;jvexnum;+j) coutpmatrixi*vexnum+jt; coutendl; /判断连通边arc后 图graph 是否存在回路 bool iscycle(graph& graph, myarc& arc) list mylist; mylist.push_back(arc.m_beginvex); int *ps=new intgraph.m_vexnum; for(int i=0;igraph.m_vex

20、num;+i) psi=0; while(!mylist.empty() int x=mylist.front(); psx=1; mylist.pop_front(); for(int i=0;igraph.m_vexnum;+i) if(graph.m_pmatrixi+x*graph.m_vexnum!=0) if(i=arc.m_endvex) return true; if(psi!=1) mylist.push_back(i); delete ps; return false;/克鲁斯卡尔算法void kruskal(const graph& graph,graph& smtree) myqueues arcqueues;/保存从小到大排列的边 arcqueues.insertgraph(graph); myarc myarc;/arc表示边的类型 int arcnum=0;