《数据结构实验图的基本操作.pdf》由会员分享，可在线阅读，更多相关《数据结构实验图的基本操作.pdf（19页珍藏版）》请在三一文库上搜索。
1、浙江大学城市学院实验报告 课程名称数据结构 实验项目名称实验十三 /十四图的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期2014/06/09 一. 实验目的和要求 1、掌握图的主要存储结构。 2、学会对几种常见的图的存储结构进行基本操作。 二. 实验内容 1、 图的邻接矩阵定义及实现： 建立头文件 test13_AdjM.h，在该文件中定义图的邻接矩阵存储结构，并编 写图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。 同时建立一个验证操作实现的主函数文件test13.cpp （以下图为例），编译并调 试程序，直到正确运行。 2、图的邻接表的定义及实现： 建立
2、头文件 test13_AdjL.h，在该文件中定义图的邻接表存储结构，并编写 图的初始化、建立图、输出图、输出图的每个顶点的度等基本操作实现函数。同 时在主函数文件 test13.cpp中调用这些函数进行验证（以下图为例） 。 0 1 2 4 6 5 3 3、填写实验报告，实验报告文件取名为report13.doc。 4、上传实验报告文件report13.doc到 BB 。 注: 下载 p256_GraphMatrix.cpp( 邻接矩阵 )和 p258_GraphAdjoin.cpp( 邻接表 )源程序，读懂程序完成空缺部分 代码。 三. 函数的功能说明及算法思路 （包括每个函数的功能说明，
3、及一些重要函数的算法实现思路） 四. 实验结果与分析 （包括运行结果截图、结果分析等） 01 2 34 五. 心得体会 程序比较难写，但是可以通过之前的一些程序来找到一些规律 （记录实验感受、 上机过程中遇到的困难及解决办法、遗留的问题、 意见和建 议等。） 【附录 -源程序】 256: /p-255 图的存储结构以数组邻接矩阵表示, 构造图的算法。 #include #include #include #include typedef char VertexType; /顶点的名称为字符 const int MaxVertexNum=10; /图的最大顶点数 const int MaxEdg
4、eNum=100; /边数的最大值 typedef int WeightType; /权值的类型 const WeightType MaxValue=32767; / 权值的无穷大表示 typedef VertexType VexlistMaxVertexNum; /顶点信息，定点名称 typedef WeightType AdjMatrixMaxVertexNumMaxVertexNum; / 邻接矩阵 typedef enumDG,DN,AG,AN GraphKind; / 有向图 ,有向网 ,无向图 ,无向网 typedef struct Vexlist vexs; / 顶点数据元素 A
5、djMatrix arcs; / 二维数组作邻接矩阵 int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志 MGraph; void CreateGraph(MGraph char v, w; G.kind=kd; /图的种类 printf(“ 输入要构造的图的顶点数和弧数：n“); scanf(“%d,%d“, getchar();/过滤回车 printf(“ 依次输入图的顶点名称ABCD.等等： n“); for (i=0; i头顶点名，权值输入数据 :如 A-B,23 n“); else printf(“ 按照： 尾顶点名 -
6、头顶点名输入数据 :A-Bn“); for (k=0; k%c,%d“, / 输入弧的两个定点及该弧的权重 else scanf(“%c-%c“, getchar(); for(i=0;i头顶点名，权值输入数据 :如 A-B,23 a-b,5 a-c,8 c-b,7 a-d,4 d-c,3 输出邻接矩阵 | 5 | 8 | 4 | | | | | | 7 | | | | | 3 | | Press any key to continue */ void PrintMGraph(MGraph switch(G.kind) case DG: for (i=0; i头顶点名输入数据 :如 A-B a
7、-b a-c a-d c-b d-c */ #include #include #include #include typedef char VertexType; /顶点的名称为字符 const int MaxVertexNum =10; /图的最大顶点数 const int MaxEdgeNum =100; /边数的最大值 typedef int WeightType; /权值的类型 const WeightType MaxValue =32767; /权值的无穷大表示 typedef VertexType Vexlist MaxVertexNum; / 顶点信息，定点名称 /邻接矩阵 t
8、ypedef enum DG,DN,AG,AN GraphKind; / 有向图 ,有向网 ,无向图 ,无向网 struct EdgeNode /链表边结点，表示弧 int adjvex; /存放与头结点顶点有关的另一个顶点在邻接表(数组) 中的下标。 EdgeNode *next; /指向链表下一个结点 WeightType info; / 权重值，或为该弧相关信息 ; typedef struct VNode /邻接表，表示顶点 VertexType data; / 顶点数据，顶点名称 EdgeNode *firstarc; / 指向边结点链表第一个结点 VNode, AdjListMax
9、VertexNum; typedef struct AdjList vertices; int vexnum, arcnum; / 图的当前顶点数和弧数 GraphKind kind; / 图的种类标志 ALGraph; void CreateGraph_DG(ALGraph int i,j,k; char v,w; G.kind=DG; /图的种类 printf(“ 输入要构造的有向图的顶点数和弧数：n“); scanf(“%d,%d“, getchar();/过滤回车 printf(“ 依次输入图的顶点名称ABCD. 等等： n“); for (i=0; i头顶点名输入数据 :如 A-B
10、n“); for (k=0; k%c“, getchar(); for(i=0;iadjvex=j; /置入弧尾顶点号 p-info =MaxValue; /图的权值默认为无穷大 p-next=G.verticesi.firstarc; /插入链表 G.verticesi.firstarc=p; / void CreateGraph_DN(ALGraph int i,j,k; char v,w; WeightType q; G.kind=DN; /图的种类 printf(“ 输入要构造的有向网的顶点数和弧数：n“); scanf(“%d,%d“, getchar();/过滤回车 printf(
11、“ 依次输入图的顶点名称ABCD. 等等： n“); for (i=0; i头顶点名 ,权值输入数据 :如 A-B,8 n“); for (k=0; k%c,%d“, getchar(); for(i=0;iadjvex=j; /置入弧尾顶点号 p-info =q; /图的权值默认为无穷大 p-next=G.verticesi.firstarc; /插入链表 G.verticesi.firstarc=p; void CreateGraph_AG(ALGraph int i,j,k; char v,w; G.kind=AG; /图的种类 printf(“ 输入要构造的有向图的顶点数和弧数：n“)
12、; scanf(“%d,%d“, getchar();/过滤回车 printf(“ 依次输入图的顶点名称ABCD. 等等： n“); for (i=0; i头顶点名输入数据 :如 A-B n“); for (k=0; k%c“, getchar(); for(i=0;iadjvex=j; /置入弧尾顶点号 p-info =MaxValue; /图的权值默认为无穷大 p-next=G.verticesi.firstarc; /插入链表 G.verticesi.firstarc=p; /无向图和网的边结点依附于i,j 两个顶点 ,两方均应添加边 p=(EdgeNode *)malloc(sizeo
13、f(EdgeNode);/申请弧结点 p-adjvex=i; /置入弧尾顶点号 p-info =MaxValue; /图的权值默认为无穷大 p-next=G.verticesj.firstarc; /插入链表 G.verticesj.firstarc=p; / void CreateGraph_AN(ALGraph int i,j,k; char v,w; WeightType q; G.kind=AN; /图的种类 printf(“ 输入要构造的无向网的顶点数和弧数：n“); scanf(“%d,%d“, getchar();/过滤回车 printf(“ 依次输入图的顶点名称ABCD. 等等
14、： n“); for (i=0; iadjvex=j; /置入弧尾顶点号 p-info =q; /图的权值默认为无穷大 p-next=G.verticesi.firstarc; /插入链表 G.verticesi.firstarc=p; /无向图和网的边结点依附于i,j 两个顶点 ,两方均应添加边 p=(EdgeNode *)malloc(sizeof(EdgeNode);/申请弧结点 p-adjvex=i; /置入弧尾顶点号 p-info =q; /图的权值默认为无穷大 p-next=G.verticesj.firstarc; /插入链表 G.verticesj.firstarc=p; vo
15、id dfsAdjoin(ALGraph G ,int i,bool *visited) / 深度优先搜索 p266 coutadjvex; if(visitedj=false) dfsAdjoin(G,j,visited); p=p-next ; void bfsAdjoin(ALGraph G ,int i,bool *visited) / 广度优先搜索 p268 const int MSize=30; int qMSize=0; int front=0,rear=0; coutadjvex; if(!visitedj) coutnext; /*完成函数 * void countdig(A
16、LGraph G) /请完成计算图的入度或初度 if(G.kind=DG|G.kind=DN) /计算有向图或网的个顶点的入度与初度 int outD,inD; EdgeNode *p,*k; int i,j; for(i=0;inext) outD+; for(j=0;jnext) if(G.verticesk-adjvex.data=G .verticesi.data) inD+; printf(“%c ：出度是 %d,入度是 %dn“,G.verticesi.data,outD,inD); else / 计算无向图或网的度 int Du; EdgeNode *p,*k; int i,j;
17、 for(i=0;inext) Du+; printf(“%c ：度是 %dn“,G.verticesi.data,Du); void PrintALGraph(ALGraph int i; for (i=0; i“,i,G.verticesi.data); else printf(“%d | %c “,i,G.verticesi.data); p=G.verticesi.firstarc; /输出依附上面顶点的各条边 while(p) printf(“ %d “,p-adjvex); /另一顶点序号 if(p-info!=MaxValue) /若有权重输出，网 printf(“| %d“,p
18、-info ); if(p-next!=NULL) /输出指针 printf(“ -“); else printf(“ “); p=p-next; /下一条边 printf(“n“); void main() ALGraph G; int k; printf(“ 请选择图的种类： 0:有向图 ,1:有向网 ,2:无向图 ,3:无向网 . 请选择：“); scanf(“%d“, switch(k) /DG,DN,AG,AN case 0: printf(“ 构造有向图 n“); CreateGraph_DG(G); / 采用邻接表，构造有向图 break; case 1: printf(“ 构造
19、有向网 n“); CreateGraph_DN(G); / 采用邻接表，构造有向网 break; case 2: printf(“ 构造无向图 n“); CreateGraph_AG(G); / 采用邻接表，构造无向图 break; case 3: printf(“ 构造无向网 n“); CreateGraph_AN(G); / 采用邻接表，构造无向网 break; PrintALGraph(G); / 打印图的邻接表 /下面完成图的邻接表结构的深度优先和广度优先搜索 bool visitedMaxVertexNum; int i; cout“邻接表存储的图 G，深度优先搜索序列： “; fo
20、r(i=0;iG.vexnum ;i+) visitedi=false; /初始化 visited 数组 for(i=0;iG.vexnum;i+) if(visitedi=false) dfsAdjoin(G,i,visited); /深度优先搜索 coutendl; cout“邻接表存储的图 G，广度优先搜索序列： “; for(i=0;iG.vexnum ;i+) visitedi=false; /初始化 visited 数组 for(i=0;iG.vexnum;i+) if(visitedi=false) bfsAdjoin(G,i,visited); /广度优先搜索 coutendl; cout“度“endl; countdig(G);