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

安徽省巢湖学院计算机与信息工程学院课程设计报告课程名称 数据结构 课题名称 最小生成树问题 专业 计算机科学与技术 班级 10计本2班 学号10012121 姓名 联系方式 指导教师 20 11 年 12 月 30 日 “最小生成树问题”课程设计题目: 编制一个求出N个顶点图的最小生成树程序一 需求分析:(1)在n个城市间建设通信网络，只需要架设n-1条线路即可。以最低的代价建设这个通信网，即求图的最小生成树。 (2)利用克鲁斯卡尔算法求网的最小生成树。(3)利用自定义的队列结构存放连通分量。(4)以文本形式输出最小生成树中的各条边及它们的权值。输出格式为(int a,int b,int n),其中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<arc.m_weight; inline bool operator = (const MyArc& arc) return m_weight=arc.m_weight; inline bool operator > (const MyArc& arc) return m_weight>arc.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 MyQueuespublic: list<MyArc> m_list; MyQueues() void insert(const MyArc& arc); /按权值大小排序插入 void InsertGraph(const Graph &graph); /将图的连通分量插入队列 MyArc pop();/出队列;4.本程序的结构1)主程序模块:void main()申明边权值矩阵数组并用随机函数初始化；创建图；调用克鲁斯卡尔算法函数；输出边的权值矩阵，最小生成树中的各条边及它们的权值退出；2)带权的边类模块-实现带权边的存储和运算。邻接矩阵类模块-实现图的状态记录和相关操作。自定义队列类模块-实现边的按权存贮和相关操作。3)核心kruskal算法模块-用克鲁斯卡尔算法求出最小生成树 各模块调用关系:三 详细设计#include<iostream>#include<stdlib.h>/产生随机数组用#include<time.h> /同上/#include "basic.h" /所用到的自定义数据结构定义和实现文件using namespace std;#include<list>/*MyStack 堆栈类的结构 0 1 . curlen . size 栈底(bottom) . prt . */#define BASESIZE 64 /默认堆栈数组空间大小（8*8）,可以自扩充template <class Type> class MyStackprivate: Type *bottom; / 元素存放的动态数组 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; /入栈 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;i<s;i+) tempi=bottomi; size*=2; clear(); ptr=s+1; for(int i=0;i<s;i+) bottomi=tempi; delete temp; return size; ;/*MyStack的实现 */*压栈*/template <class Type> int MyStack<Type>:push(Type e) / if(+ptr=size) extent(); bottomptr=e; return ptr; /*出栈*/template <class Type> int MyStack<Type>:pop(Type &e) / if(ptr=-1) return -2;/栈空，返回 -2 ！ else e=bottomptr-; return ptr;/*获取栈顶元素*/template <class Type>int MyStack<Type>:top(Type &e) / if(ptr=-1) return -1;/栈空,返回 -1 ！ else e=bottomptr; return ptr;/*设置栈定元素*/template <class Type>int MyStack<Type>:settop(Type e) / if(ptr=-1) return -1;/栈空,返回 -1 ！ else bottomptr=e; return ptr;/*用callback函数对栈从低向上遍历*/template <class Type>void MyStack<Type>:traverse(void callback(Type *),Type *e) if(callback!=NULL) for(int i=0;i<=ptr;i+) e=&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<arc.m_weight; bool operator = (const MyArc& arc) return m_weight=arc.m_weight; bool operator > (const MyArc& arc) return m_weight>arc.m_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);/按权值大小排序插入 bool bound(int x); /判断顶点x是否已与其它顶点连通;/构造函数Graph:Graph(int vexnum) m_pmatrix=new intvexnum*vexnum; m_vexnum=vexnum;m_arcnum=0; for(int i=0;i<vexnum*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;i<m_vexnum*m_vexnum;+i) m_pmatrixi=pmatrixi;/测试 顶点x是否已与其他点连通bool Graph:bound(int x) for(int i=0;i<m_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_vexnum+arc.m_beginVex=arc.m_weight; +m_arcnum;Graph:Graph() delete m_pmatrix;/*自定义队列，用于存放连通图，或按权排列后的边*/class MyQueuespublic: list<MyArc> m_list; MyQueues() void insert(const MyArc& arc);/边按权值插入队列中合适位置, void InsertGraph(const Graph &graph);/将图的连通分量插入队列 MyArc pop();/边出队MyArc MyQueues:pop() MyArc arc=m_list.front(); m_list.pop_front(); return arc;/边按权值插入队列中合适位置,void MyQueues:insert(const MyArc& arc) list<MyArc>:iterator pos=m_list.begin(); while(pos!=m_list.end() if(*pos>arc) break; else +pos; m_list.insert(pos,arc);/将图的连通分量插入队列void MyQueues:InsertGraph(const Graph &graph) for(int i=0;i<graph.m_vexnum;+i) for(int j=i+1;j<graph.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,int *matrix); /用随机数组初始化matrix数组并且打印/*主函数*/void main()char i;cout<<"*"<<endl;cout<<”标题:最小生成树”<<endl;cout<<"班级:计本2班"<<endl;cout<<"姓名:张娟"<<endl;cout<<"学号:10012121 "<<endl;cout<<"*"<<endl; cout<<"请输入顶点数目:" cin>>i; int vex=i-'0' int *matrix=new intvex*vex; cout<<endl; SetMatrix(vex,matrix); Graph graph(vex,matrix),smtree(vex); kruskal(graph,smtree); SmallestTreeOutput(smtree); delete matrix;/用随机数组初始化matrix数组并且打印void SetMatrix(int vexnum,int *pmatrix) srand(unsigned)time(NULL); for(int i=0;i<vexnum;+i)/产生随机权值矩阵 for(int j=i;j<vexnum;+j) if(j=i) pmatrixi*vexnum+j=0; continue; int rnum=rand();rnum%=99;rnum+;/产生199的随机整数作为边的权值 pmatrixi*vexnum+j=rnum; pmatrixj*vexnum+i=rnum; cout<<"*随机产生的各边权值矩阵 顶点数为 "<<vexnum<<" *n" for( i=0;i<vexnum;+i)/输出随机权值矩阵 for(int j=0;j<vexnum;+j) cout<<pmatrixi*vexnum+j<<"t" cout<<endl; /判断连通边arc后 图graph 是否存在回路 bool IsCycle(Graph& graph, MyArc& arc) list<int> mylist; mylist.push_back(arc.m_beginVex); int *ps=new intgraph.m_vexnum; for(int i=0;i<graph.m_vexnum;+i) psi=0; while(!mylist.empty() int x=mylist.front(); psx=1; mylist.pop_front(); for(int i=0;i<graph.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; /边的个数 while(arcnum<graph.m_vexnum-1) myarc=arcqueues.pop(); if(!IsCycle(smtree,myarc) smtree.insert(myarc); +arcnum; /输出最小生成树void SmallestTreeOutput(const Graph& smtree) cout<<"最小生成树:"<<endl; for(int i=0;i<smtree.m_vexnum;+i)/输出最小树 for(int j=i+1;j<smtree.m_vexnum;+j) if(smtree.m_pmatrixi*smtree.m_vexnum+j) cout<<'('<<i<<','<<j<<','<<smtree.m_pmatrixi*smtree.m_vexnum+j<<')'<<endl;四 设计和调试分析1.在调试MyQueues类的时候，由于对数组的按行存储理解的不够好导致开始时未能获得正确的数据，经单步跟踪调试后发现下标超出范围，修正后即可正常运行。2.在本实验中，自定义了3个类，定义了基于它们的数据和操作，它们是本程序的实现基础。3.由于翻译核心算法 kruskal的时间复杂度与边的数目的函数有线性关系，同时IsCycle函数含有while和for循环，在顶点数目不多的时候，算法时间很快，适用于稀疏矩阵。 五.测试结果:如下图六. 附录文件base含有自定义的MyArc类，Graph类，MyQueues类。文件 SmallestTree.cpp 为本设计项目的主测试文件，含有main，kruskal算法函数和其他相关函数.