图的基本操作.doc

哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构课程类型：必修实验项目名称：第三次实验实验题目：图的基本操作班级： 10803102学号：1080310225姓名：陈虞付设计成绩报告成绩指导老师1、 实验目的实现有向图、无向图的基本操作。2、 实验要求及实验环境实验要求：实现有向图、无向图的基本操作（建立连接表，邻接矩阵，深度优先搜索， 广度优先搜索等）。实验环境：windows平台、code：blocks集成开发环境。三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）1逻辑设计 主程序的流程：定义邻接表gl、bool型数组visited。程序开始时，先初始化邻 接表，然后提示图是否有向，输入选择，调用MainMenue()函数 到主菜单的选择界面，根据输入的选择调用相应的函数、实现相 应的逻辑功能。2 物理设计 程序功能：以文件方式方式输入的无/有向图，实现无/有向图的邻接表、邻接矩 阵求解及对图的深度优先遍历、广度优先遍历操作。 输入：将要求解的无/有向图按规则输入对应的文件 输出：通过主菜单的选择，按需实现对图的各种操作，显示结果并保存到相应的 文件中。 源程序说明： 头文件： graphics.h 函数实现：graphics.cpp 主函数： main.cpp 存放的文件说明： 无向图：graphics1.txt 存放格式为第一行存放图的顶点数n，边数b，下面每行存放两个相邻顶点：Vi,Vj 有向图：graphics2.txt 存放格式为第一行存放图的顶点数n，下面每行存放两个相邻顶点Vi-Vj：Vi,Vj 无向图邻接表：adjlist1.txt 有向图邻接表：adjlist2.txt 无向图邻接矩阵：adjmatrix1.txt 有向图邻接矩阵：adjmatrix2.txt所有抽象数据类型的定义如下：/定义邻接表的边节点类型 struct EdgeNode int adjvex; EdgeNode *next; ;/定义邻接表类型typedef EdgeNode *ADJLIST;各模块的具体实现程序是：Graphicscpp各模块的的功能及参数说明：graphics.h 如下：/对图操作的主菜单void MainMenue();/初始化邻接表void InitialAdjList(ADJLIST &GL, int n);/以文件方式输入图/bool InputGraphics();/建立图的邻接表void CreatAdjList(ADJLIST &GL, int &n, int m);/建立图的邻接矩阵void CreatAdjMatrix(ADJLIST &GL, int &n, int m);/从初始点出发深度优先搜索由邻接表GL表示的图void DFSAdjList(ADJLIST GL, bool *&visited, int i, int n);/从初始点出发广度优先搜索由邻接表GL表示的图void BFSAdjList(ADJLIST GL, bool *&visited, int i, int n);4、 测试结果1、 图是否有向的选择、主菜单界面：2、 建立邻接表的测试结果：3、 建立邻接矩阵的测试结果：4、 广度优先搜索的测试结果：5、 深度优先搜索的测试结果：6、 退出界面：5、 系统不足与经验体会系统不足：异常处理不够健壮，不能够用很形象的方式打印图的直观图。经验体会：通过这次实验使我对图有了比较深入的了解，熟悉了图的基本操 作，同时也感受到了看似简单的程序实现，真正做起来很费劲，有很多的 困难需要去克服。6、 附录：源代码（带注释）graphics.h 源代码如下：#ifndef GRAPHICS_H#define GRAPHICS_Hstruct EdgeNode int adjvex; EdgeNode *next;/定义邻接表的边节点类型/定义邻接表类型typedef EdgeNode *ADJLIST;/对图操作的主菜单void MainMenue();/初始化邻接表void InitialAdjList(ADJLIST &GL, int n);/以文件方式输入图/bool InputGraphics();/建立图的邻接表void CreatAdjList(ADJLIST &GL, int &n, int m);/建立图的邻接矩阵void CreatAdjMatrix(ADJLIST &GL, int &n, int m);/从初始点出发深度优先搜索由邻接表GL表示的图void DFSAdjList(ADJLIST GL, bool *&visited, int i, int n);/从初始点出发广度优先搜索由邻接表GL表示的图void BFSAdjList(ADJLIST GL, bool *&visited, int i, int n);#endifGraphics.cpp 源代码如下：#include #include #include #include #include graphics.h#define MAX_SIZE 100using namespace std;/部分函数原型声明void Check(int n, int &i, int &j);void InitialAdjList(ADJLIST &GL, int n);/全局变量,控制递归函数中提示符的输出int flag = 1;void MainMenue()/对图操作的主菜单 coutn*endl; cout* *endl; cout* 1.建立图的邻接表。 *endl; cout* 2.建立图的邻接矩阵。 *endl; cout* 3.深度优先遍历图。 *endl; cout* 4.广度优先遍历图。 *endl; cout* 5.退出。 *endl; cout* *endl; cout* fulme *endl;/* End of MainMuenue() */void InitialAdjList(ADJLIST &GL, int n)/初始化图的邻接表 GL = new EdgeNode*n; for (int i = 1; i = n; i+) GLi = NULL;/* End of InitialAdjlist() */void CreatAdjList(ADJLIST &GL, int &n, int m)/建立图的邻接表 FILE *in1; FILE *in2; FILE *out1; FILE *out2; int i; int j; int k; int b; char ch; int flag = 0; if (m = 0) /建立无向图的邻接表 if (in1 = fopen(graphics1.txt, rb) = NULL) cout打开 graphics1.txt 失败！endl; exit(1); if (out1 = fopen(adjlist1.txt, wb) = NULL) cout打开 adjlist1.txt 失败！endl; flag = 1; /读入顶点的个数, , 边数 fscanf(in1, %d, &n); fscanf(in1, %c, &ch); fscanf(in1, %d, &b); for (k = 0; k adjvex = j; p - next = GLi; GLi = p; /向序号为j的单链表的表头插入一个节点 p = new EdgeNode; p - adjvex = i; p - next = GLj; GLj = p; /输出邻接表,并保存到adjlist1.txt中 coutendln=endl; cout无向图的邻接表为：endl; for (i = 1; i = n; i+) EdgeNode *p = GLi; couti - 1 |V next) cout| adjvex; fprintf(out1, %s, |-|-|); fprintf(out1, %d, p - adjvex); cout|endl; fprintf(out1, %s, |); fprintf(out1, rn); if (flag) cout无向图的邻接表已保存到adjlist1.txt中endl; fclose(in1); fclose(out1); else if (m = 1) /建立有向图的邻接表 if (in2 = fopen(graphics2.txt, rb) = NULL) cout打开 graphics2.txt 失败！endl; exit(1); if (out2 = fopen(adjlist2.txt, wb) = NULL) cout打开 adjlist2.txt 失败！endl; flag = 1; /读入顶点的个数, , 边数 fscanf(in2, %d, &n); fscanf(in2, %c, &ch); fscanf(in2, %d, &b); for (k = 0; k adjvex = j; p - next = GLi; GLi = p; /输出图的邻接表 coutendln=endl; cout有向图的邻接表为：endl; for (i = 1; i = n; i+) EdgeNode *p = GLi; couti - 1 |V next) cout| adjvex; fprintf(out2, %s, |-|-|); fprintf(out2, %d, p - adjvex); cout|endl; fprintf(out2, %s, |); fprintf(out2, rn); if (flag) cout有向图的邻接表已保存到adjlist2.txtendl; fclose(in2); fclose(out2); /* End of CreatAdjList() */void CreatAdjMatrix(ADJLIST &GL, int &n, int m)/建立图的邻接矩阵 int matrixMAX_SIZE + 1MAX_SIZE + 1; FILE *in1; FILE *in2; FILE *out1; FILE *out2; int i; int j; int k; int b; char ch; int flag = 0; /初始化图的邻接矩阵 for (i = 1; i = MAX_SIZE; i+) for (j = 1; j = MAX_SIZE; j+) matrixij = 0; if (m = 0) /建立无向图的邻接矩阵 if (in1 = fopen(graphics1.txt, rb) = NULL) cout打开 graphics1.txt 失败！endl; exit(1); if (out1 = fopen(adjlmatrix1.txt, wb) = NULL) cout打开 adjmatrix1.txt 失败！endl; flag = 1; /读入顶点的个数, , 边数 fscanf(in1, %d, &n); fscanf(in1, %c, &ch); fscanf(in1, %d, &b); for (k = 0; k b; k+) fscanf(in1, %d, &i); fscanf(in1, %c, &ch); fscanf(in1, %d, &j); Check(n, i, j); matrixij = matrixji = 1; for (i = 1; i = b; i+) for (j = 1; j = n; j+) coutmatrixij ; fprintf(out1, %d , matrixij); coutendl; fprintf(out1, rn); cout无向图的邻接矩阵已保存到adjmatrix1.txt中！endl; else if (m = 1) /建立有向图的邻接矩阵 if (in2 = fopen(graphics2.txt, rb) = NULL) cout打开 graphics2.txt 失败！endl; exit(1); if (out2 = fopen(adjmatrix2.txt, wb) = NULL) cout打开 adjmatrix2.txt 失败！endl; flag = 1; /读入顶点的个数, , 边数 fscanf(in2, %d, &n); fscanf(in1, %c, &ch); fscanf(in1, %d, &b); for (k = 1; k = b; k+) fscanf(in2, %d, &i); fscanf(in2, %c, &ch); fscanf(in2, %d, &j); Check(n, i, j); matrixij = 1; for (i = 1; i = b; i+) for (j = 1; j = n; j+) coutmatrixij ; fprintf(out2, %d , matrixij); coutendl; fprintf(out2, rn); cout有向图已保存到adjmatrix2.txt中！endl; /* End of CreatAdjMatrix() */void DFSAdjList(ADJLIST GL, bool *&visited, int i, int n)/从初始点出发递归深度优先搜索邻接表GL表示的图 if (flag) flag = 0; coutn=endl; coutn图的深度优先遍历序列：endl; couti adjvex; /j为Vi的一个邻接点的序号 if (!visitedj) DFSAdjList(GL, visited, j, n); p = p - next; /* End of DFSAdjList() */void BFSAdjList(ADJLIST GL, bool *&visited, int i, int n)/从初始点开始广度优先搜索邻接表GL表示的图 int j; const int MaxLength = 100; /定义一个队列q, 其元素类型为整型 int qMaxLength = 0; /定义队首和对尾指针 int front = 0, rear = 0; coutn=endl; coutn图的广度优先遍历序列：endl; for (j = 1; j = n; j+) visitedj