数据结构图的实现.doc

实验7 无向图一、 问题描述创建一个无向图，实现图的深度优先遍历和广度优先遍历等功能。二、 需求分析1、 简述程序的基本功能本程序可以直接进行对图中元素的输入、输出、插入顶点、删除顶点、插入边、删除边、寻找邻接点以及深度优先遍历和广度优先遍历等功能。2、 输入的形式和输入值的范围提供了一个功能选择界面，可以输入09进行功能的选择。3、 输出的形式用户选择1选项时，程序会输出图的顶点数目和边的数目以及各条边顶点及权值；用户选择2选项时，程序会提示输入创建图的顶点数和边数，然后逐个输入顶点，以及各条边；用户选择3选项时，程序会提示输入顶点，然后输出该顶点的第一个邻接顶点；用户选择4选项时，程序会提示输入顶点以及当前的邻接顶点，然后输出该顶点的下一个邻接顶点；用户选择5选项时，程序会提示输入所要插入边的顶点以及权重；用户选择6选项时，程序会提示输入所要插入的顶点；用户选择7选项时，程序会提示输入所要删除的边的两个顶点；用户选择8选项时，程序会提示输入所要删除的顶点用户选择9选项时，程序提示输入遍历的起始顶点，然后输出深度遍历的结果；用户选择0选项时，程序提示输入遍历的起始顶点，然后输出广度遍历的结果；用户选择q选项时，程序结束。4、 测试数据要求1） 、选择选项时，不论输入几个字符，只读取第一个字符；2） 、选择选项时，输入的字符不能过多，若输入过多的字符就会出现异常；3） 、输入顶点时，每个元素只能是一个字符，输入多个字符会出错；4） 、在查找、插入、删除顶点或边时，会有容错提示；5） 、在查找和删除顶点或边时，若没有此元素，会给出提示；三、 概要设计1、 抽象数据类型在该程序中，定义了一个类模板template class Graph，在该类中有*Vertices、*Edge、numEdges、numVertices和maxVertices五个私有成员分别表示该类的顶点集、边集、现有边数、现有顶点数和顶点最大数目；自己定义了构造函数Graph(int size)和析构函数Graph()，还有对图进行输入、输出、查找邻接点、插入顶点或边、删除顶点或边以及两种遍历等操作的函数；并在主函数中对该类模板进行实例化。2、 主程序流程及模块调用关系提示输入错误i0=其它值令flag=falsei0=q广度遍历i0=0Y结束N开始赋值a=true输出主菜单输入选项i的值a=true?创建char类型数组插入边插入顶点删除边删除顶点深度遍历i0=5i0=6i0=7i0=8i0=9输出无向图顶点的第一个邻接顶点顶点的下一个邻接顶点输入无向图i0=1i0=2i0=3i0=4四、 详细设计（要求主要变量和语句加注释）1、 抽象数据类型的实现： Graph.h文件的实现：#include#includeSeqQueue.hconst int maxWeight=100;templateclass Graphfriend istream& operator(istream& in,Graph&G);friend ostream& operator(ostream& out,Graph&G);public:Graph(int size);Graph();bool IsEmpty()if(numEdges=0)return true;else return false;bool IsFull()if(numVertices=maxVertices*(maxVertices-1)/2)return true;else return false;int NumberOfVertices()return numVertices;int NumberOfEdges()return numEdges;T getValue(int i)return i=0&i=numVertices?Verticesi:NULL;E getWeight(int v1,int v2)return v1!=-1&v2!=-1?Edgev1v2:0;int getFirstNeighbor(int v);int getNextNeighbor(int v,int w);bool insertVertex(T vertex);bool insertEdges(int v1,int v2,E cost);bool removeVertex(int v);bool removeEdges(int v1,int v2);int getVertexPos(T vertex)for(int i=0;inumVertices;i+)if(Verticesi=vertex)return i;return -1;private:T *Vertices;E *Edge;int maxVertices;int numEdges;int numVertices;templateGraph:Graph(int size)int i;maxVertices=size;numEdges=0;numVertices=0;Vertices=new TmaxVertices;Edge=new E*size;for(i=0;imaxVertices;i+)Edgei=new Esize;for(i=0;imaxVertices;i+)for(int j=0;jmaxVertices;j+)Edgeij=(i=j)?0:maxWeight;templateGraph:Graph()delete Vertices;for(int i=0;imaxVertices;i+)deleteEdgei;delete Edge;templateint Graph:getFirstNeighbor(int v)if(v!=-1)for(int vol=0;vol0&EdgevvolmaxWeight)return vol;return -1;templateint Graph:getNextNeighbor(int v,int w)if(v!=-1&w!=-1)for(int vol=w+1;vol0&EdgevvolmaxWeight)return vol;return -1;templatebool Graph:insertVertex(T vertex)if(numVertices=maxVertices)cout空间已满，插入顶点失败！endl;return false;else for(int i=0;inumVertices;i+)if(Verticesi=vertex)cout已有此顶点，插入失败！endl;return false;VerticesnumVertices+=vertex;cout插入成功！endl;return true;templatebool Graph:removeVertex(int v)int i;if(vnumVertices)cout无此顶点，删除失败！endl;return false;if(numVertices=1)cout仅剩一个顶点，不能删除！endl;return false;Verticesv=VerticesnumVertices-1;for(i=0;i0&EdgeivmaxWeight)numEdges-;for(i=0;inumVertices;i+)Edgeiv=EdgeinumVertices;numVertices-;for(i=0;inumVertices;i+)Edgevi=EdgenumVerticesi;cout删除顶点成功！endl;return true;templatebool Graph:insertEdges(int v1,int v2,E cost)if(v1-1&v1-1&v2numVertices&Edgev1v2=maxWeight)Edgev1v2=cost;Edgev2v1=cost;numEdges+;cout插入边成功！endl;return true;else cout顶点或权重出错，无法插入！endl;return false;templatebool Graph:removeEdges(int v1,int v2)if(v1-1&v1-1&v20&Edgev1v2maxWeight)Edgev1v2=Edgev2v1=maxWeight;numEdges-;cout删除边成功！endl;return true;else cout顶点或权重出错，无法删除！endl; return false;templateistream& operator(istream& in,Graph&G)int i,j,k,m,n;T e1,e2;E weight;coutnm;for(i=0;in;i+)cout输入第i+1e1;G.insertVertex(e1);i=0;while(im)cout输入第i+1e1e2weight;j=G.getVertexPos(e1);k=G.getVertexPos(e2);if(j=-1|k=-1)cout边两端点信息有误，重新输入！endl;elseG.insertEdges(j,k,weight);i+;return in;templateostream& operator(ostream& out,Graph&G)int i,j,m,n;T e1,e2;E w;n=G.NumberOfVertices();m=G.NumberOfEdges();outn,mendl;for(i=0;in;i+)for(j=i;j0&wmaxWeight)e1=G.getValue(i);e2=G.getValue(j);out(e1,e2,w)endl;return out;templatevoid DFS(Graph&G,T&v)int i,loc,n=G.NumberOfVertices();bool *visited=new booln;for(i=0;in;i+)visitedi=false;loc=G.getVertexPos(v);DFS(G,loc,visited);deletevisited;templatevoid DFS(Graph&G,int v,bool visited)coutG.getValue(v);visitedv=true;int w=G.getFirstNeighbor(v);while(w!=-1)if(visitedw!=true)DFS(G,w,visited);w=G.getNextNeighbor(v,w);templatevoid BFS(Graph&G,T&v)int i,w,loc,n=G.NumberOfVertices();bool *visited=new booln;for(i=0;in;i+)visitedi=false;loc=G.getVertexPos(v);coutG.getValue(loc);visitedloc=true;SeqQueueQ(n);Q.EnQueue(loc);while(!Q.IsEmpty()Q.DeQueue(loc);w=G.getFirstNeighbor(loc);while(w!=-1)if(visitedw!=true)coutG.getValue(w);visitedw=true;Q.EnQueue(w);w=G.getNextNeighbor(loc,w);deletevisited;2、现所用到的顺序表SeqQueue.h实现#includetemplateclass SeqQueuepublic:SeqQueue(int max);SeqQueue()deletem_element;bool EnQueue(R x);bool DeQueue(R &x);bool IsEmpty()return length=0?true:false;bool IsFull()return length=maxsize?true:false;private:int length,maxsize,first;R *m_element;templateSeqQueue:SeqQueue(int max=0)first=0;maxsize=max;length=0;m_element=new Rmax;templatebool SeqQueue:EnQueue(R x)if(IsFull()return false;m_element(first+length)%maxsize=x;length+;return true;templatebool SeqQueue:DeQueue(R &x)if(IsEmpty()return false;x=m_elementfirst;first=(first+1)%maxsize;length-;return true;3、 主程序的实现#include#include Graph.hvoid main()char i20;bool flag=true;int num=20,cost=2,m,n;Graph G1(num);char v,w,v1,v2;while(flag)coutendl;cout*endl;cout 1 输出无向图 2 输入无向图endl;cout 3 顶点的第一个邻接顶点 4 顶点的下一个邻接顶点 endl;cout 5 插入边 6 插入顶点 endl;cout 7 删除边 8 删除顶点endl;cout 9 深度遍历 0 广度遍历endl;cout q 退出endl;cout*endlendl;couti;switch(i0)case 1:coutG1;break;case 3:coutv; m=G1.getVertexPos(v); n=G1.getFirstNeighbor(m); if(n=-1)cout该顶点无邻接顶点。endl; else coutG1.getValue(n);break;case 4:coutv; coutw; m=G1.getVertexPos(v); n=G1.getVertexPos(w); n=G1.getNextNeighbor(m,n); if(n=-1)cout该顶点无下一个邻接顶点。endl; else coutG1.getValue(n);break;case 5:coutv1v2cost; m=G1.getVertexPos(v1); n=G1.getVertexPos(v2); G1.insertEdges(m,n,cost);break;case 6:coutv; G1.insertVertex(v);break;case 7:coutv1v2; m=G1.getVertexPos(v1);n=G1.getVertexPos(v2); G1.removeEdges(m,n);break;case 8:coutv; m=G1.getVertexPos(v); G1.removeVertex(m);break;case 9:coutv; DFS(G1,v);break;case 0:coutv; BFS(G1,v);break;case q:flag=false;break;default:c