《实验12图的基本操作-邻接矩阵》由会员分享，可在线阅读，更多相关《实验12图的基本操作-邻接矩阵（10页珍藏版）》请在金锄头文库上搜索。
1、浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验十二 图的基本操作邻接矩阵存储结构 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 2015-1-8 一. 实验目的和要求1、掌握图的存储结构：邻接矩阵。2、学会对图的存储结构进行基本操作。二. 实验内容1、图的邻接矩阵定义及实现：建立头文件 AdjMatrix.h，在该文件中定义图的邻接矩阵存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时建立一个验证操作实现的主函数文件test5_1.cpp，编译并调试程序，直到正确运行。 2、选做：编写图的深度优先遍历函数与广度优先遍历函
2、数，要求把这两个函数添加到头文件 AdjMatrix.h 中，并在主函数文件 test5_1.cpp 中添加相应语句进行测试。3、填写实验报告，实验报告文件取名为 report12.doc。4、上传实验报告文件 report12.doc 及源程序文件 test5_1.cpp、AdjMatrix.h到 Ftp 服务器上自己的文件夹下。三. 函数的功能说明及算法思路（包括每个函数的功能说明，及一些重要函数的算法实现思路）邻接矩阵表示法的 C 语言描述：typedef structvexlist vexs; /顶点数据元素adjmatrix GA; /二维数组作邻接矩阵int n; /顶点数int
3、k1,k2; /k1 为有无向，k2 为有无权Graph;const int MaxVertexNum = 10; /*图的最大顶点数*/const int MaxEdgeNum = 100; /*图的最大边数*/const int MaxValue = 10000; /*无穷大的具体值*/typedef int WeightType; /*定义权的类型*/typedef char VertexType;typedef VertexType vexlistMaxVertexNum; /*定义顶点数组类型*/typedef int adjmatrixMaxVertexNumMaxVertexNu
4、m; /*定义邻接矩阵类型*/抽象数据类型：ADT Graph isData: Graph(V, E ) 其中： V = vi | 0=0, vi VertexType 是顶点的有穷集合；E = (x, y) | x, y V 或 E = | x, y V 是顶点之间关系的有穷集合，也叫做边集合。存储类型用 adjmatrix 表示 Operations:void InitMatrix( adjmatrix GA, int k)/初始化算法（假设顶点信息仅是序号）void CreateMatrix( adjmatrix GA, int n, char *s, int k1, int k2)/建
5、立图的邻接矩阵算法void PrintMatrix( adjmatrix GA, int n, int k1, int k2)/根据图的邻接矩阵输出图的顶点集和边集void PrintDegree(vexlist V,adjmatrix GA,int n,int k1)/计算各个顶点的度void dfsMatrix(adjmatrix GA,int i,int n,bool *visited)/深度优先遍历void bfsMatrix( adjmatrix GA,int i,int n,bool *visited)/广度优先遍历end度的算法：void PrintDegree(vexlist
6、V,adjmatrix GA,int n,int k1)数组 Vi存放所有顶点，根据边结点的指针数组计算该结点的度;若图是有向图，则查找所有边结点的邻接点域，如果是当前结点的位置，就将该结点对应的度+1 。队列：typedef char ElemType;struct QueueElemType *queue;int front,rear;int MaxSize;Operations:void InitQueue(Queue &Q) /初始化循环队列 Qint EmptyQueue(Queue Q)/判断队列是否为空，空返回 1，否则返回 0void EnQueue(Queue &Q,Elem
7、Type item)/ 入队列ElemType OutQueue(Queue &Q) / 出队列end Queue四. 实验结果与分析（包括运行结果截图、结果分析等）无向无权图：无向有权图：有向无权图：有向有权图：五. 心得体会（记录实验感受、上机过程中遇到的困难及解决办法、遗留的问题、意见和建议等。）在计算度的编程上出现了问题，计算 void PrintDegree(vexlist V,adjmatrix GA,int n,int k1)时，Vi是存放顶点的数组，但是在 main()函数里面忘记使用数组，结果编译是正确的但是输出来是一堆乱码。最后改了好久才想起来，在前面加上coutG.vex
8、si;【附录-源程序】test5_1.cpp：#include#include#include#include#includeconst int MaxVertexNum = 10; /*图的最大顶点数*/const int MaxEdgeNum = 100; /*图的最大边数*/const int MaxValue = 10000; /*无穷大的具体值*/typedef int WeightType; /*定义权的类型*/typedef char VertexType;typedef VertexType vexlistMaxVertexNum; /*定义顶点数组类型*/typedef in
9、t adjmatrixMaxVertexNumMaxVertexNum; /*定义邻接矩阵类型*/#include AdjMatrix.h void main()Graph G;/邻接矩阵int i;coutG.n;coutG.vexsi;coutG.k1G.k2;bool *visited=new boolG.n; /定义并动态分配标志数组InitMatrix(G.GA,G.k2);couta;CreateMatrix(G.GA,G.n,a,G.k1,G.k2);PrintDegree(G.vexs,G.GA,G.n,G.k1);coutc1; /读入第一个字符 if(k1=0 & k2=0
10、) /建立无向无权图dosinc1ic2jc3; /读入一条边，如 (2,5)GAij = GAji = 1; /相应的边元素置 1 sinc1; /读入, 或 if (c1=) break;while (1);else if (k1=0 & k2!=0) /建立无向带权图dosinc1ic2jc3w; /读入一条边，如 (2,5)8GAij = GAji = w;sinc1;if (c1=) break;while(1);else if (k1!=0 & k2=0) /建立有向无权图do sinc1ic2jc3;GAij = 1;sinc1;if (c1=) break;while(1);e
11、lse if (k1!=0 & k2!=0) /建立有向带权图do sinc1ic2jc3w;GAij = w;sinc1;if (c1=) break;while(1);void PrintMatrix( adjmatrix GA, int n, int k1, int k2)/根据图的邻接矩阵输出图的顶点集和边集/ k1=0 代表无向图否则为有向图, k2 =0 代表无权图否则为带权图int i, j;cout GAij,;coutendl; void PrintDegree(vexlist V,adjmatrix GA,int n,int k1)/计算各个顶点的度int i,j,d;fo
12、r(i=0;in;i+)d=0;for(j=0;jn;j+)if(GAij!=0&GAij!=MaxValue)d+;if(k1) /有向图for(j=0;jn;j+)if(GAji!=0&GAji!=MaxValue)d+;coutVi的度为dendl;/*=选作部分=*/typedef char ElemType;struct QueueElemType *queue;int front,rear;int MaxSize;void InitQueue(Queue &Q) /初始化循环队列 QQ.MaxSize=10;Q.queue=(ElemType *)malloc(sizeof(Ele
13、mType)*Q.MaxSize);Q.rear=Q.front=0;int EmptyQueue(Queue Q)/判断队列是否为空，空返回 1，否则返回 0return Q.front=Q.rear;void EnQueue(Queue &Q,ElemType item)/ 入队列if(Q.rear+1) % Q.MaxSize = Q.front)/若队列已满，重新分配 2 倍大的空间Q.queue=(ElemType *)realloc(Q.queue,2*Q.MaxSize*sizeof(ElemType);if(Q.rear != Q.MaxSize-1) /原队列尾部内容向后移f
14、or(int i=0; i=Q.rear; i+)Q.queuei+Q.MaxSize = Q.queuei;Q.rear=Q.rear+Q.MaxSize;Q.MaxSize=2*Q.MaxSize;/ 插入 itemQ.rear=(Q.rear+1)%Q.MaxSize;Q.queueQ.rear=item;ElemType OutQueue(Queue &Q) / 出队列if(Q.front=Q.rear) /若空队列，则结束运行cerr 队列已空，无法删除! endl;exit(1);/删除队头元素，并返回该元素Q.front=(Q.front +1)%Q.MaxSize;return Q.queueQ.front;void dfsMatrix(adjmatrix GA,int i,int n,bool *visited) /从 vi 出发进行 DFSint j;cout
