2013级数据结构实验代码7vc6可直接运行

《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