数据结构图的实验报告.doc
图的实验报告班级：电子091 学号：0908140620 姓名：何洁 编号：19（一）实验要求创建一个图。能够实现图的输入，插入顶点和边，利用队列进行深度和广度遍历。（二）需求分析功能：1，输入图的信息；2，插入一个顶点；3插入一个边；4，删除一个顶点；5，删除一个边；6，深度优先遍历；7，广度优先遍历；8退出。（三）概要设计本程序采用的是模板类，抽象数据类型有：T,E。类：template <class T,class E>class Graphmtx friend istream & operator>>(istream& in,Graphmtx<T, E>& G);friend ostream & operator<<(ostream& out, Graphmtx<T, E>& G);/输出public: Graphmtx(int sz=30, E max=0); /构造函数 Graphmtx () /析构函数 delete VerticesList; delete Edge; T getValue (int i) /取顶点 i 的值, i 不合理返回0 return i >= 0 && i <= numVertices ? VerticesListi : NULL; E getWeight (int v1, int v2) /取边(v1,v2)上权值 return v1 != -1 && v2 != -1 ? Edgev1v2 : 0; int NumberOfEdges()return numEdges; /返回当前边数int NumberOfVertices()return numVertices; /返回当前顶点 int getFirstNeighbor (int v); /取顶点 v 的第一个邻接顶点 int getNextNeighbor (int v, int w); /取 v 的邻接顶点 w 的下一邻接顶点 bool insertVertex (const T& vertex); /插入顶点vertex bool insertEdge (int v1, int v2, E cost); /插入边(v1, v2),权值为cost bool removeVertex (int v); /删去顶点 v 和所有与它相关联的边 bool removeEdge (int v1, int v2); /在图中删去边(v1,v2)int getVertexPos (T vertex) /给出顶点vertex在图中的位置 for (int i = 0; i < numVertices; i+) if (VerticesListi = vertex) return i; return -1; /int numVertexPos(T vertex);private:int maxVertices;int numEdges;int numVertices; T *VerticesList; /顶点表 E *Edge;/邻接矩阵const E maxWeight;（四）详细设计函数通过调用图类中的函数实现一些功能。头文件:#include<iostream.h>#include<assert.h>const int maxSize=50;const int DefaultVertices=30; /最大顶点数(=n)const int maxWeight=50;其中顺序队列的实现:template<class T>class SeqQueue/循环队列的类的定义public:SeqQueue(int sz=10); /构造函数SeqQueue()delete elements; /析构函数bool EnQueue(const T& x);/若队列不满，则将X进队，否则队溢出处理bool DeQueue(T& x);/若队列不为空，则函数返回TRUE及对头元素的值，否则返回FALSEvoid makeEmpty()front=rear=0;/置空操作：对头指针和队尾指针置0bool IsEmpty()constreturn(front=rear)?true:false;/判队列空否，若队列空，则函数返回TRUE，否则返回FALSEbool IsFull()constreturn(rear+1)%maxSize=front)?true:false;/判队列满否，若队列满，则函数返回TRUE，否则返回FALSEprotected:int rear,front; /对头和队尾指针T *elements; /存放队列元素的数组int maxSize; /队列最大可容纳元素个数;template<class T>SeqQueue<T>:SeqQueue(int sz):front(0),rear(0),maxSize(sz)/建立最大具有Maxsize个元素的空队列elements=new TmaxSize; /创建队列空间assert(elements!=NULL); /断言：动态存储分配成功与否 template<class T>bool SeqQueue<T>:EnQueue(const T& x)/若队列不满，则将元素X插入到该队列的队尾，否则出错处理if(IsFull()=true)return false; /队列满则插入失败，返回elementsrear=x; /按照队尾指针指示位置插入rear=(rear+1)%maxSize; /队尾指针加1return true; /插入成功template<class T>bool SeqQueue<T>:DeQueue(T& x)/若队列不空则函数推掉一个对头元素并返回TRUE，否则函数返回FALSEif(IsEmpty()=true)return false; /若队列空则删除失败，返回x=elementsfront;front=(front+1)%maxSize; /对头指针加1return true; /删除成功类的实现:template <class T, class E>Graphmtx<T, E>:Graphmtx(int sz, E max):maxWeight(max) /构造函数 maxVertices=sz; numVertices=0; numEdges=0;int i, j;VerticesList = new TmaxVertices; /创建顶点表 Edge = (int *) new int *maxVertices;for (i = 0; i < maxVertices; i+) Edgei = new intmaxVertices; /邻接矩阵 for (i = 0; i < maxVertices; i+) /矩阵初始化 for (j = 0; j < maxVertices; j+)Edgeij=(i=j)?0:maxWeight; template <class T, class E>int Graphmtx<T, E>:getFirstNeighbor (int v) /给出顶点位置为v的第一个邻接顶点的位置, /如果找不到, 则函数返回-1 if (v != -1) for (int col = 0; col < numVertices; col+) if (Edgevcol && Edgevcol < maxWeight) return col; return -1;template <class T, class E>int Graphmtx<T, E>:getNextNeighbor (int v, int w) /给出顶点 v 的某邻接顶点 w 的下一个邻接顶点 if (v != -1 && w != -1) for (int col = w+1; col < numVertices; col+) if (Edgevcol && Edgevcol < maxWeight) return col; return -1;界面：cout<<" ="<<endl;cout<<" |1、输入一个图 2、插入一个顶点| "<<endl;cout<<" |3、插入一个边 4、删除一个顶点|"<<endl;cout<<" |5、删除一个边 6、深度优先遍历|"<<endl;cout<<" |7、广度优先遍历 8、退出 |"<<endl;cout<<" ="<<endl;然后进入循环进行功能操作Case1中，输入一个图：其中有操作符的重载，使图的信息直接输入：template<class T,class E>istream& operator >> (istream& in,Graphmtx<T,E>& G)/通过从输入流in输入n个顶点信息和e条无向边的信息建立用邻接矩阵的图G。/邻接矩阵初始化的工作已经在构造函数中完成、int i,j,k,n,m;T e1,e2;E weight;in>>n>>m;for(i=0;i<n;i+)in>>e1;G.insertVertex(e1);i=0;while(i<m)in>>e1>>e2>>weight;j=G.getVertexPos(e1);k=G.getVertexPos(e2);if(j=-1|k=-1)cout<<"边两端信息有误，重新输入！"<<endl;elseG.insertEdge(j,k,weight);i+;return in; cout<<"请输入图的信息："<<endl; cin>>g1;cout<<endl; break;Case2中，是插入顶点，需要调用的函数有：template<class T,class E>bool Graphmtx<T,E>:insertVertex(const T& vertex) /插入顶点vertexif(numVertices=maxVertices)return false; /顶点表满，不插入VerticesListnumVertices+=vertex;return true;case 2: cout<<"请输入要插入的顶点：" cin>>v1; g1.insertVertex (v1); cout<<g1; cout<<"插入成功"<<endl; break;出现界面：Case3中，是实现插入边的操作，需要调用的函数有：template<class T,class E>bool Graphmtx<T,E>:insertEdge (int v1,int v2,E cost)/插入边(v1,v2),权值为costif(v1>-1&&v1<numVertices&&v2>-1&&v2<numVertices && Edgev1v2=maxWeight)Edgev1v2=Edgev2v1=cost; numEdges+;return true;else return false;然后执行调用：case 3: cout<<"请输入插入边的两个顶点的序号:" cin>>e1>>e2; cout<<endl; cout<<"请输入权值：" cin>>cost; g1.insertEdge (e1,e2,cost); cout<<g1; break;出现界面：Case 6是进行深度优先遍历：利用了队列，调用的函数有：template<class T, class E> void DFS(Graphmtx<T, E>& G, const T& v) /从顶点v出发对图G进行深度优先遍历的主过程 int i, loc,n; n=G.NumberOfVertices(); /顶点个数 bool *visited=new booln; /创建辅助数组 for (i = 0; i < n; i+) visited i = false; /辅助数组visited初始化loc = G.getVertexPos(v); DFS (G, loc, visited); /从顶点0开始深度优先搜索 delete visited; /释放visitedtemplate<class T, class E>void DFS(Graphmtx<T, E>& G, int v, bool visited) cout << G.getValue(v) << ; /访问顶点v visitedv = true; /作访问标记 int w = G.getFirstNeighbor (v); /第一个邻接顶点 while (w != -1) /若邻接顶点w存在 if ( !visitedw ) DFS(G, w, visited); /若w未访问过, 递归访问顶点w w = G.getNextNeighbor (v, w); /下一个邻接顶点 主函数中：case 6: cout<<"请输入一个顶点：" cin>>v1; cout<<"图的深度优先搜索为："<<endl; DFS(g1,v1); cout<<endl; break;界面出现：Case7是现实广度优先遍历的操作，也需要利用到队列，其函数体为：template <class T, class E> void BFS(Graphmtx<T, E>& G, const T& v) int i,w;int n = G.NumberOfVertices(); /图中顶点个数bool *visited = new booln; for (i = 0; i < n; i+) visitedi = false; int loc = G.getVertexPos (v);/取顶点号 cout << G.getValue (loc) << ; /访问顶点v visitedloc = true; /做已访问标记 SeqQueue<int> Q; Q.EnQueue (loc); /顶点进队列, 实现分层访问 while (!Q.IsEmpty() ) /循环, 访问所有结点 Q.DeQueue (loc); w = G.getFirstNeighbor (loc); /第一个邻接顶点 while (w != -1) /若邻接顶点w存在 if (!visitedw) /若未访问过 cout << G.getValue (w) << ;/访问 visitedw = true; Q.EnQueue (w); /顶点w进队列 w = G.getNextNeighbor (loc, w); /找顶点loc的下一个邻接顶点 /外层循环，判队列空否 delete visited;主函数中的调用：case 7: cout<<"请输入一个顶点：" cin>>v1; cout<<"图的广度优先搜索为："<<endl; BFS(g1,v1); cout<<endl; break;界面显示：Case4中式删除顶点的操作;函数的实现：template<class T,class E>bool Graphmtx<T,E>:removeVertex (int v)/删去顶点v和所有与它相关的边if(v<0|v>=numVertices)return false; if(numVertices=1)return false;int i,j;VerticesListv=VerticesListnumVertices-1;for(i=0;i<numVertices;i+)if(Edgeiv<0&&Edgeiv<maxWeight)numEdges-;for(i=0;i<numVertices;i+)Edgeiv=EdgeinumVertices-1;numVertices-;for(j=0;j<numVertices;j+)Edgevj=EdgenumVerticesj;return true;主函数中：case 4: cout<<"请输入要删除的顶点序号：" cin>>e1; g1.removeVertex(e1); cout<<g1; break;界面显示：Case5的操作是删除一条边：要调用的函数：template<class T,class E>bool Graphmtx<T,E>:removeEdge (int v1,int v2)/在图中删除边(v1,v2)if(v1>-1&&v1<numVertices&&v2>-1&&v2<numVertices&&Edgev1v2>0&&Edgev1v2<maxWeight)Edgev1v2=Edgev2v1=maxWeight;numEdges-;return true;else return false;在主函数中：case 5: cout<<"请输入要删除边的两个顶点序号：" cin>>e1>>e2; g1.removeEdge(e1,e2); cout<<g1; break;界面显示：Case8 的操作是退出case 8: return 0; break;界面显示：（五）调试与测试在调试过程中遇到很多问题，在定义变量的时候遇到一些问题，对于全局变量还是局部变量要区分一下。还有，对于出现某种错误，如函数重载等，都可以解决了。
