欢迎来到天天文库
浏览记录
ID:6139147
大小:261.00 KB
页数:26页
时间:2018-01-04
《2013级数据结构实验代码7vc6可直接运行》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、一、实验目的掌握图的基本概念,描述方法;遍历方法。二、实验内容1、创建图类。二叉树的存储结构使用邻接矩阵或链表。2、提供操作:遍历、BFS、DFS3、对建立好的图,执行上述各操作。4、输出生成树。1、 输出最小生成树。三、最小生成树的思想(1)、2个for循环都是从2开始的,因为一般我们默认开始就把第一个节点加入生成树,因此之后不需要再次寻找它。(2)、lowcost[i]记录的是以节点i为终点的最小边权值。初始化时因为默认把第一个节点加入生成树,因此lowcost[i]=graph[1][i],即最小边权值就是各节点到1号节点的边权值中最小的。(3)mst[i
2、]记录的是lowcost[i]对应的起点,这样有起点,有终点,即可唯 一确定一条边了。初始化时mst[i]=1,即每条边都是从1号节点出发。四、程序代码 #includeusingnamespacestd;//队列templateclassNode{ public: Node(){} virtual~Node(){} Tdata; Node*link; };templateclassLinkedQueue{public: LinkedQueue(); virtual~LinkedQueue(); b
3、oolIsEmpty()const{return((front)?false:true);} LinkedQueue&Add(constT&x); LinkedQueue&Delete(T&x);public: Node*front; Node*rear; };templateLinkedQueue::LinkedQueue(){ front=rear=0;}templateLinkedQueue::~LinkedQueue(){ Node*next; while(front) {
4、 next=front->link; deletefront; front=next; }}templateLinkedQueue&LinkedQueue::Add(constT&x){ Node*p=newNode; p->data=x; p->link=0; if(front) rear->link=p; elsefront=p; rear=p; return*this;}templateLinkedQueue&LinkedQueue::Delete(T&x){ if(Is
5、Empty()) { return*this; } x=front->data; Node*p=front; front=front->link; deletep; return*this;}//加权有向图templateclassAdjacencyWDigraph{public: AdjacencyWDigraph(intVertices=10,TnoEdge=0); virtual~AdjacencyWDigraph(){Delete2DArray(a,n+1);} boolExist(inti,intj)const; intEd
6、ges()const{returne;} intVertices()const{returnn;} AdjacencyWDigraph&Add(inti,intj,constT&w); AdjacencyWDigraph&Delete(inti,intj); intOutDegree(inti)const; intInDegree(inti)const; voidMake2DArray(T**&x,introws,intcols); voidDelete2DArray(T**&x,introws); //遍历 voidInitializePos(
7、){pos=newint[n+1];} voidDeactivatePos(){delete[]pos;} intBegin(inti); intNextVertex(inti); //宽度优先搜索 voidBFS(intv,intreach[],intlabel); //深度优先搜索 voidDFS(intv,intreach[],intlabel); voiddfs(intv,intreach[],intlabel); public: TNoEdge; intn; inte; T**a; int*pos; };templateAdjacenc
8、yWDigraph
此文档下载收益归作者所有