哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构课程类型：必修实验项目名称：第三次实验实验题目：图的基本操作班级：10803102学号：1080310225姓名：陈虞付一、实验目的实现有向图、无向图的基本操作。

二、实验要求及实验环境实验要求：实现有向图、无向图的基本操作（建立连接表，邻接矩阵，深度优先搜索，广度优先搜索等）。

实验环境： windows 平台、 code ：： blocks 集成开发环境。

三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）1．逻辑设计主程序的流程：定义邻接表 gl 、bool 型数组 visited[] 。

程序开始时，先初始化邻接表，然后提示图是否有向，输入选择，调用 MainMenue（）函数到主菜单的选择界面，根据输入的选择调用相应的函数、实现相应的逻辑功能。

2．物理设计程序功能：以文件方式方式输入的无 / 有向图，实现无 / 有向图的邻接表、邻接矩阵求解及对图的深度优先遍历、广度优先遍历操作。

输入：将要求解的无 / 有向图按规则输入对应的文件输出：通过主菜单的选择，按需实现对图的各种操作，显示结果并保存到相应的文件中。

源程序说明：头文件： graphics.h函数实现： graphics.cpp主函数： main.cpp存放的文件说明：无向图： graphics1.txt存放格式为第一行存放图的顶点数有向图： graphics2.txt 存放格式为第一行存放图的顶点数无向图邻接表： adjlist1.txt有向图邻接表： adjlist2.txt无向图邻接矩阵： adjmatrix1.txt 有向图邻接矩阵： adjmatrix2.txt 所有抽象数据类型的定义如下：// 定义邻接表的边节点类型struct EdgeNode n ，边数b ，下面每行存放两个相邻顶点：Vi,Vj n ，下面每行存放两个相邻顶点Vi-->Vj ：Vi,Vjint 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);四、测试结果1、图是否有向的选择、主菜单界面:2、建立邻接表的测试结果:3、建立邻接矩阵的测试结果:10 10 00 1&1 01 0» 1a0 sa& 01»9@a1aaaa& 0a aa 0» 0» 0U B1 10 0& 11 Ua aa Ho 00 0a 0a ao 0» 09 3aa999181&&a98@»a19a& 0a aa 0» 0» 0a 0o 00 0& 0& Ua a& H& 00 0a 1a ao 0» 01 3aa999a81@»aB&9a&888 _［阵已保存到孔町mat vi_xla984、广度优先搜索的测试结果:「建立图的邻2盧立图的勺遷尿5 •退出v阵oo o表矩图图亠克更请输入你的选择；3图朗广度优先遍历序列；1 5 20 6 423 I? 7 14 9 12 135、深度优先搜索的测试结果:8»U9aaaB119a80 3 -txt0 a0 00 a中!*HCiHf图的探度优先遍历序列：1 5 20 6 423 1? 7 11 ? 12 136、退出界面:五、系统不足与经验体会系统不足：异常处理不够健壮，不能够用很形象的方式打印图的直观图。

经验体会：通过这次实验使我对图有了比较深入的了解，熟悉了图的基本操作，同时也感受到了看似简单的程序实现，真正做起来很费劲，有很多的 困难需要去克服。

六、 附录：源代码(带注释) graphics.h 源代码如下：#ifndef GRAPHICS_H #define GRAPHICS_Hstruct EdgeNode{WM-M-W M-H MM ««M*|l£3OO£JCl£aCJOCjCJft)Cf Ul line XJHltXMKitMLJCJWM ■:KHLHJW3 1 •建立图的邻援表。

2 •建立图苗邻摟矩阵。

乳深 乳广 5 •退出*遍历图。

遍历图。

情输入你的选择;4 "表矩图图 fe極历历的的先先图®立V度度岀建建棵广退£ ulme 冬5'pocecs returned 1 C0xl> execution tine : 24.146 £ f rees anu keu tocontinuie.MMQM12 2 4 5-Mint 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 <iostream>#include <stdio.h>#include <stdlib.h>#include <stdio.h>#include "graphics.h"#define MAX_SIZE 100 using namespace std;// 部分函数原型声明void Check(int n, int &i, int &j);void InitialAdjList(ADJLIST &GL, int n);// 全局变量 ,控制递归函数中提示符的输出 int flag = 1; void MainMenue()// 对图操作的主菜单}/* End of MainMuenue() */ voidInitialAdjList(ADJLIST &GL, int n)// 初始化图的邻接表cout<<"\n *************************************** "<<endl; cout<<"** cout<<"** cout<<"** cout<<"** cout<<"** cout<<"** cout<<"****"<<endl; 1.建立图的邻接表。

**"<<endl ;2.建立图的邻接矩阵。

**"<<endl ;3.深度优先遍历图。

**"<<endl ; 4.广度优先遍历图。

**"<<endl ; 5.退出。

**"<<endl ;**"<<endl;******************** cout<<" 1************ fulme "<<endl;{GL = new EdgeNode*[n];for (int i = 1; i <= n; i++)GL[i] = 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 < b; k++){fscanf(in1, "%d", &i); fscanf(in1, "%c", &ch);fscanf(in1, "%d", &j);Check(n, i, j);// 向序号为 i 的单链表的表头插入一个边结点EdgeNode *p = new EdgeNode;p -> adjvex = j;p -> next = GL[i];GL[i] = p;// 向序号为 j 的单链表的表头插入一个节点p = new EdgeNode;p -> adjvex = i;p -> next = GL[j];GL[j] = p;}// 输出邻接表 ,并保存到 adjlist1.txt 中cout<<endl<<"\n====================="<<endl; cout<<" 无向图的邻接表为： "<<endl;for (i = 1; i <= n; i++){EdgeNode *p = GL[i];cout<<i - 1<<" |"<<"V"<<i;fprintf(out1, "%c", 'V');fprintf(out1, "%d", i);for (p = GL[i]; p != NULL; p = p -> next){cout<<"|-|->|"<<p -> adjvex;fprintf(out1, "%s", "|-|->|");fprintf(out1, "%d", p -> adjvex);}cout<<"|A|"<<e ndl;fprin tf(out1, "%s", "|A|");fprintf(out1, "\r\n");}if (flag)cout<<" 无向图的邻接表已保存到 adjlist1.txt中"<<e ndl;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 < b; k++){fscanf(in2, "%d", &i);fscanf(in2, "%c", &ch);fscanf(in2, "%d", &j);Check(n, i, j);// 向序列号为 i 的表头插入一个边节点EdgeNode *p = new EdgeNode;p -> adjvex = j;p -> next = GL[i];GL[i] = p;}// 输出图的邻接表cout<<endl<<"\n====================="<<endl; cout<<" 有向图的邻接表为： "<<endl;for (i = 1; i <= n; i++){EdgeNode *p = GL[i];cout<<i - 1<<" |"<<"V"<<i;fprintf(out2, "%c", 'V');fprintf(out2, "%d", i);for (p = GL[i]; p != NULL; p = p -> next) {cout<<"|-|->|"<<p -> adjvex;fprintf(out2, "%s", "|-|->|");fprintf(out2, "%d", p -> adjvex);}cout<<"|A|"<<e ndl;fprin tf(out2, "%s", "|A|");fprintf(out2, "\r\n");}if (flag)adjlist2.txt"<<endl;cout<<" 有向图的邻接表已保存到fclose(in2);fclose(out2);}}/* End of CreatAdjList() */void CreatAdjMatrix(ADJLIST &GL, int &n, int m)// 建立图的邻接矩阵{int matrix[MAX_SIZE + 1][MAX_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++){matrix[i][j] = 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);matrix[i][j] = matrix[j][i] = 1;}for (i = 1; i <= b; i++){for (j = 1; j <= n; j++){cout<<matrix[i][ j]<<' ';fprintf(out1, "%d ", matrix[i][j]);}cout<<endl;fprintf(out1, "\r\n");}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);matrix[i][j] = 1;}for (i = 1; i <= b; i++){for (j = 1; j <= n; j++){cout<<matrix[i][ j]<<' ';fprintf(out2, "%d ", matrix[i][j]);}cout<<endl;fprintf(out2, "\r\n");}cout<<" 有向图已保存到 adjmatrix2.txt 中！"<<endl;}/* End of CreatAdjMatrix() */void DFSAdjList(ADJLIST GL, bool *&visited, int i, intn)// 从初始点出发递归深度优先搜索邻接表 GL 表示的图{if (flag){flag = 0;cout<<"\n================================"<<endl;cout<<"\n 图的深度优先遍历序列： "<<endl;}cout<<i<<' ';visited[i] = true;EdgeNode *p = GL[i];while (p != NULL){int j = p -> adjvex; //j 为 Vi 的一个邻接点的序if (!visited[j])DFSAdjList(GL, visited, j, n);p = p -> next;}/* End of DFSAdjList() */void BFSAdjList(ADJLIST GL, bool *&visited, int i, intn) // 从初始点开始广度优先搜索邻接表 GL 表示的图{int j;const int MaxLength = 100;// 定义一个队列 q, 其元素类型为整型int q[MaxLength] = {0};// 定义队首和对尾指针int front = 0, rear = 0;cout<<"\n==============================="<<endl;cout<<"\n 图的广度优先遍历序列： "<<endl; for (j =1; j <= n; j++)visited[j] = false;cout<<i<<' ';// 访问 Vivisited[i] = true;q[++rear] = i;while (front != rear)// 当队列非空时进行循环处理{// 删除队首元素，第一次执行时 k 的值为 i front = (front + 1) % MaxLength;int k = q[front];// 取邻接表的表头指针EdgeNode *p = GL[k];while (p != NULL)// 依次搜索 Vk 的每个节点{//Vj 为 Vk 的一个邻接节点int j = p -> adjvex;if (!visited[j]){cout<<j<<' ';visited[j] = true;rear = (rear + 1) % MaxLength;q[rear] = j;}p = p -> next;}} cout<<endl;}/* End of BFSAdjList() */void Check(int n, int &i, int &j)// 检查输入的边序号是否越界，如越界择重输入{while (1){if (!(i >= 0 && j <= n && j >= 0 && j <= n)){cout<<"\n 输入有误！ "<<endl; exit(1);}break;}}/* End of Check() */main.cpp 源代码如下：#include <iostream>#include "graphics.h"#define MAX_SIZE 100using namespace std;int main(){int i;int n;int m; // 是否为有向图char ch;bool *visited = new bool[MAX_SIZE];ADJLIST gl;// 初始化邻接表InitialAdjList(gl, MAX_SIZE);cout<<"============================="<<endl;cout<<" 请选择图是否有向( 0 无 /1 有)： cin>>m;while (1){MainMenue();cout<<" 请输入你的选择： ";cin>>ch;switch (ch){case '1':CreatAdjList(gl, n, m);break;case '2':CreatAdjMatrix(gl, n, m);break;case '3':for (i = 1; i <= n; i++)visited[i] = false;DFSAdjList(gl, visited, 1, n);break;case '4':BFSAdjList(gl, visited, 1, n);break;case '5':exit(1);default:cout<<" 输入有误！ "<<endl;break;}}return 0;}。