数据结构图的实验报告.doc

《数据结构图的实验报告.doc》由会员分享，可在线阅读，更多相关《数据结构图的实验报告.doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图的实验报告班级：电子091 学号：0908140620 姓名：何洁 编号：19（一）实验要求创建一个图。能够实现图的输入，插入顶点和边，利用队列进行深度和广度遍历。（二）需求分析功能：1，输入图的信息；2，插入一个顶点；3插入一个边；4，删除一个顶点；5，删除一个边；6，深度优先遍历；7，广度优先遍历；8退出。（三）概要设计本程序采用的是模板类，抽象数据类型有：T,E。类：template class Graphmtx friend istream & operator(istream& in,Graphmtx& G);friend ostream & operator(ostream& o

2、ut, Graphmtx& 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

3、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),权值为c

4、ost 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 num

5、Vertices; T *VerticesList; /顶点表 E *Edge;/邻接矩阵const E maxWeight;（四）详细设计函数通过调用图类中的函数实现一些功能。头文件:#include#includeconst int maxSize=50;const int DefaultVertices=30; /最大顶点数(=n)const int maxWeight=50;其中顺序队列的实现:templateclass SeqQueue/循环队列的类的定义public:SeqQueue(int sz=10); /构造函数SeqQueue()delete elements; /析构函数

6、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;/判队列满否，若队列满，则函数返回

7、TRUE，否则返回FALSEprotected:int rear,front; /对头和队尾指针T *elements; /存放队列元素的数组int maxSize; /队列最大可容纳元素个数;templateSeqQueue:SeqQueue(int sz):front(0),rear(0),maxSize(sz)/建立最大具有Maxsize个元素的空队列elements=new TmaxSize; /创建队列空间assert(elements!=NULL); /断言：动态存储分配成功与否 templatebool SeqQueue:EnQueue(const T& x)/若队列不满，则将元

8、素X插入到该队列的队尾，否则出错处理if(IsFull()=true)return false; /队列满则插入失败，返回elementsrear=x; /按照队尾指针指示位置插入rear=(rear+1)%maxSize; /队尾指针加1return true; /插入成功templatebool SeqQueue:DeQueue(T& x)/若队列不空则函数推掉一个对头元素并返回TRUE，否则函数返回FALSEif(IsEmpty()=true)return false; /若队列空则删除失败，返回x=elementsfront;front=(front+1)%maxSize; /对头指针

9、加1return true; /删除成功类的实现:template Graphmtx: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 maxVer

10、tices; i+) /矩阵初始化 for (j = 0; j maxVertices; j+)Edgeij=(i=j)?0:maxWeight; template int Graphmtx:getFirstNeighbor (int v) /给出顶点位置为v的第一个邻接顶点的位置, /如果找不到, 则函数返回-1 if (v != -1) for (int col = 0; col numVertices; col+) if (Edgevcol & Edgevcol maxWeight) return col; return -1;template int Graphmtx:getNextN

11、eighbor (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;cou

12、t =endl;然后进入循环进行功能操作Case1中，输入一个图：其中有操作符的重载，使图的信息直接输入：templateistream& operator (istream& in,Graphmtx& G)/通过从输入流in输入n个顶点信息和e条无向边的信息建立用邻接矩阵的图G。/邻接矩阵初始化的工作已经在构造函数中完成、int i,j,k,n,m;T e1,e2;E weight;innm;for(i=0;ie1;G.insertVertex(e1);i=0;while(ie1e2weight;j=G.getVertexPos(e1);k=G.getVertexPos(e2);if(j=-

13、1|k=-1)cout边两端信息有误，重新输入！endl;elseG.insertEdge(j,k,weight);i+;return in; cout请输入图的信息：g1;coutendl; break;Case2中，是插入顶点，需要调用的函数有：templatebool Graphmtx:insertVertex(const T& vertex) /插入顶点vertexif(numVertices=maxVertices)return false; /顶点表满，不插入VerticesListnumVertices+=vertex;return true;case 2: coutv1; g1

14、.insertVertex (v1); coutg1; cout插入成功endl; break;出现界面：Case3中，是实现插入边的操作，需要调用的函数有：templatebool Graphmtx:insertEdge (int v1,int v2,E cost)/插入边(v1,v2),权值为costif(v1-1&v1-1&v2numVertices & Edgev1v2=maxWeight)Edgev1v2=Edgev2v1=cost; numEdges+;return true;else return false;然后执行调用：case 3: coute1e2; coutendl;

15、coutcost; g1.insertEdge (e1,e2,cost); coutg1; break;出现界面：Case 6是进行深度优先遍历：利用了队列，调用的函数有：template void DFS(Graphmtx& 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.getVerte

16、xPos(v); DFS (G, loc, visited); /从顶点0开始深度优先搜索 delete visited; /释放visitedtemplatevoid DFS(Graphmtx& 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 =

17、G.getNextNeighbor (v, w); /下一个邻接顶点 主函数中：case 6: coutv1; cout图的深度优先搜索为：endl; DFS(g1,v1); coutendl; break;界面出现：Case7是现实广度优先遍历的操作，也需要利用到队列，其函数体为：template void BFS(Graphmtx& G, const T& v) int i,w;int n = G.NumberOfVertices(); /图中顶点个数bool *visited = new booln; for (i = 0; i n; i+) visitedi = false; int

18、loc = G.getVertexPos (v);/取顶点号 cout G.getValue (loc) ; /访问顶点v visitedloc = true; /做已访问标记 SeqQueue Q; Q.EnQueue (loc); /顶点进队列, 实现分层访问 while (!Q.IsEmpty() ) /循环, 访问所有结点 Q.DeQueue (loc); w = G.getFirstNeighbor (loc); /第一个邻接顶点 while (w != -1) /若邻接顶点w存在 if (!visitedw) /若未访问过 cout G.getValue (w) ;/访问 visi

19、tedw = true; Q.EnQueue (w); /顶点w进队列 w = G.getNextNeighbor (loc, w); /找顶点loc的下一个邻接顶点 /外层循环，判队列空否 delete visited;主函数中的调用：case 7: coutv1; cout图的广度优先搜索为：endl; BFS(g1,v1); coutendl; break;界面显示：Case4中式删除顶点的操作;函数的实现：templatebool Graphmtx:removeVertex (int v)/删去顶点v和所有与它相关的边if(v=numVertices)return false; if(

20、numVertices=1)return false;int i,j;VerticesListv=VerticesListnumVertices-1;for(i=0;inumVertices;i+)if(Edgeiv0&EdgeivmaxWeight)numEdges-;for(i=0;inumVertices;i+)Edgeiv=EdgeinumVertices-1;numVertices-;for(j=0;jnumVertices;j+)Edgevj=EdgenumVerticesj;return true;主函数中：case 4: coute1; g1.removeVertex(e1);

21、 coutg1; break;界面显示：Case5的操作是删除一条边：要调用的函数：templatebool Graphmtx:removeEdge (int v1,int v2)/在图中删除边(v1,v2)if(v1-1&v1-1&v20&Edgev1v2maxWeight)Edgev1v2=Edgev2v1=maxWeight;numEdges-;return true;else return false;在主函数中：case 5: coute1e2; g1.removeEdge(e1,e2); coutg1; break;界面显示：Case8 的操作是退出case 8: return 0; break;界面显示：（五）调试与测试在调试过程中遇到很多问题，在定义变量的时候遇到一些问题，对于全局变量还是局部变量要区分一下。还有，对于出现某种错误，如函数重载等，都可以解决了。