实验十三图的基本操作—邻接表存储结构.doc

浙江大学城市学院实验报告课程名称 数据结构基础 实验项目名称 实验十三 图的基本操作邻接表存储结构 学生姓名 专业班级 学号 实验成绩 指导老师（签名 ） 日期 2015-1-15 一. 实验目的和要求1、掌握图的存储结构：邻接表。2、学会对图的存储结构进行基本操作。二. 实验内容1、图的邻接表的定义及实现：建立头文件AdjLink.h，在该文件中定义图的邻接表存储结构，并编写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同时在主函数文件test5_2.cpp中调用这些函数进行验证。2、选做：编写图的深度优先遍历函数与广度优先遍历函数，要求把这两个函数添加到头文件AdjLink.h中，并在主函数文件test5_2.cpp中添加相应语句进行测试。3、填写实验报告，实验报告文件取名为report13.doc。4、上传实验报告文件report13.doc及源程序文件test5_2.cpp、AdjLink.h到Ftp服务器上自己的文件夹下。三. 函数的功能说明及算法思路 （包括每个函数的功能说明，及一些重要函数的算法实现思路）邻接表表示法的C语言描述：typedef struct Node int adjvex; / 邻接点的位置WeightType weight; /权值域，根据需要设立struct Node *next; / 指向下一条边（弧） edgenode; / 边结点typedef edgenode *adjlist MaxVertexNum ;/定义图的邻接表结构类型（没包含顶点信息）typedef structvexlist vexs; /顶点数据元素adjlist List; /边结点int n; /顶点数int k1,k2; /k1为有无向，k2为有无权Adjlist;const int MaxVertexNum = 10; /*图的最大顶点数*/const int MaxEdgeNum = 100; /*图的最大边数*/const int MaxValue = 10000; /*无穷大的具体值*/typedef int WeightType; /*定义权的类型*/typedef char VertexType;typedef VertexType vexlistMaxVertexNum; /*定义顶点数组类型*/抽象数据类型：ADT Graph is Data: 一个邻接表，存储类型用adjlist表示 Operations: void InitAdjoin(adjlist GL)/初始化函数 void CreateAdjoin(adjlist GL,int n,char *s,int k1,int k2) /建立邻接表函数 void PrintAdjoin( adjlist GL, int n, int k1, int k2) /把邻接表表示的图用顶点集和边集的形式输出的算法 void PrintDegree(vexlist V,adjlist GL,int n,int k1) /输出图的每个顶点的度 void dfsAdjoin(adjlist GL,int i,int n,bool *visited)/深度优先遍历函数 void bfsAdjoin(adjlist GL,int i,int n, bool *visited)/广度优先遍历end度的算法（PrintDegree）：建立一个数组存放所以顶点的度，若为无向图，根据边缘结点的指针数组计算该结点的度；若为有向图，查找所有边缘结点的邻接点域，当前结点的度为该节点对应的度+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,ElemType item)/ 入队列ElemType OutQueue(Queue &Q) / 出队列end Queue四. 实验结果与分析（包括运行结果截图、结果分析等）无向无权图：有向无权图：无向有权图：有向有权图：五. 心得体会该邻接表与上一个实验邻接矩阵差不多，做起来比较简单，只是将度的算法比较麻烦。【附录-源程序】test5_2.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; /*定义顶点数组类型*/#include AdjLink.h void main()Adjlist GL;/邻接表int i;coutGL.n;cout请输入图的顶点集合(如:abc)endl;for(i=0; iGL.vexsi;coutGL.k1GL.k2;bool *visited=new boolGL.n; /定义并动态分配标志数组InitAdjoin(GL.List);couta;CreateAdjoin(GL.List,GL.n,a,GL.k1,GL.k2);PrintDegree(GL.vexs,GL.List,GL.n,GL.k1);cout按图的邻接表得到的深度优先遍历序列:endl;for(i=0;iGL.n;i+) visitedi=false;dfsAdjoin(GL.List,0,GL.n,visited);coutendl;cout按图的邻接表得到的广度优先遍历序列:endl;for(i=0;iGL.n;i+) visitedi=false;bfsAdjoin(GL.List,0,GL.n,visited);coutendl;PrintAdjoin(GL.List,GL.n,GL.k1,GL.k2);AdjLink.h：typedef struct Node int adjvex; / 邻接点的位置WeightType weight; /权值域，根据需要设立struct Node *next; / 指向下一条边（弧） edgenode; / 边结点typedef edgenode *adjlist MaxVertexNum ;/定义图的邻接表结构类型（没包含顶点信息）typedef structvexlist vexs; /顶点数据元素adjlist List; /边结点int n; /顶点数int k1,k2; /k1为有无向，k2为有无权Adjlist;void InitAdjoin(adjlist GL)/初始化函数int i;for(i=0;iMaxVertexNum;i+)GLi = NULL;void CreateAdjoin(adjlist GL,int n,char *s,int k1,int k2)/建立邻接表函数 / n为顶点数。 k1=0 代表无向图否则为有向图, / k2 =0 代表无权图否则为带权图。 / s存放边集，如：3,8,6，(2,3),(1,0),(2,0)istrstream sin(s);char c1,c2,c3;int i, j;WeightType w;edgenode *p; /将指向新申请的边结点sinc1; /读入第一个字符 if(k2=0) / 建立无权图do sinc1ic2jc3;p = (edgenode *) malloc(sizeof(edgenode);p-adjvex=j; p-weight=1; /插入边结点p-next = GLi; GLi = p;if (k1=0) /对无向图，需再插入一个边结点p = (edgenode *) malloc(sizeof(edgenode);p-adjvex=i; p-weight=1; p-next = GLj; GLj = p;sinc1; /读入, 或 while ( c1=,);else / 建立有权图do sinc1ic2jc3w; p = (edgenode *) malloc(sizeof(edgenode); p-adjvex=j; p-weight=w; /插入边结点 p-next = GLi; GLi = p; if (k1=0) /对无向图，需再插入一个边结点p = (edgenode *) malloc(sizeof(edgenode); p-adjvex=i; p-weight=w; p-next = GLj; GLj = p;sinc1; /读入, 或 while ( c1=, );void PrintAdjoin( adjlist GL, int n, int k1, int k2)/把邻接表表示的图用顶点集和边集的形式输出的算法 / k1=0 代表无向图否则为有向图, / k2 =0 代表无权图否则为带权图int i, j;edgenode *p;cout V= ; /准备输出顶点集for (i=0; in-1; i+)couti,; coutn-1endl; cout E= ; /准备输出边集for (i=0; iadjvex;if(k1=0) /无向图if (ij) cout(i,j),;else /有向图couti,jnext;else /带权图p=GLi;while(p)j=p-adjvex;if(k1=0) /无向图if (ij)cout(i,j)weight,;else /有向图couti,jweightnext; /for coutendl;void PrintDegree(vexlist V,adjlist GL,int n,int k1) /输出图的每个顶点的度int i,j;int *d=new intn;/存放结点的度的数组edgenode *p,*q;for(i=0;inext;if(k1)for(j=0;jadjvex=i)di+;q=q-next;coutVi的度为diendl;delete d; /*=选作部分=*/typedef char ElemType;struct QueueElemType *queue;int front,rear;int MaxSize;void InitQueue(Queue &Q) /初始化循环队列QQ.MaxSize=10;Q.queue=(ElemType *)malloc(sizeof(ElemType)*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) /原队列尾部内容向后移for(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.fr