下载文档原格式
图的基本操作实验报告图的基本操作实验报告引言：图是一种常见的数据结构，广泛应用于计算机科学和其他领域。
本实验报告旨在介绍图的基本操作，包括创建图、添加节点和边、遍历图等，并通过实验验证这些操作的正确性和效率。
实验目的：1. 了解图的基本概念和术语；2. 掌握图的创建和修改操作；3. 熟悉图的遍历算法；4. 分析图的操作的时间复杂度。
实验过程：1. 创建图首先，我们需要创建一个图对象。
图可以用邻接矩阵或邻接表来表示。
在本实验中，我们选择使用邻接表来表示图。
通过遍历输入的节点和边信息，我们可以创建一个包含所有节点和边的图。
2. 添加节点和边在创建图对象后，我们可以通过添加节点和边来构建图的结构。
通过输入节点的标识符和边的起始和结束节点，我们可以在图中添加新的节点和边。
添加节点和边的操作可以通过修改邻接表来实现，将节点和边的信息存储在对应的链表中。
3. 遍历图遍历图是图操作中常用的操作之一。
通过遍历图，我们可以访问图中的所有节点和边。
在本实验中，我们选择使用深度优先搜索（DFS）算法来遍历图。
DFS算法通过递归的方式遍历图中的节点，先访问当前节点，然后再递归地访问与当前节点相邻的节点。
4. 分析时间复杂度在实验过程中，我们记录了图的操作所花费的时间，并分析了它们的时间复杂度。
通过对比不同规模的图的操作时间，我们可以评估图操作的效率和可扩展性。
实验结果：通过实验，我们成功创建了一个图对象，并添加了多个节点和边。
我们还通过DFS算法遍历了图，并记录了遍历的顺序。
实验结果表明，我们的图操作实现正确，并且在不同规模的图上都能够高效地工作。
讨论与结论：本实验报告介绍了图的基本操作，并通过实验验证了这些操作的正确性和效率。
通过实验，我们了解到图是一种重要的数据结构，可以用于解决许多实际问题。
同时，我们还深入分析了图操作的时间复杂度，为后续的图算法设计和优化提供了参考。
总结：通过本次实验，我们对图的基本操作有了更深入的了解。
图的基本操作与应用图是一种重要的数据结构，广泛应用于计算机科学和相关领域。
本文将介绍图的基本操作和常见的应用场景，通过详细讲解来帮助读者更好地理解和应用图。
一、图的定义和表示图是由节点（顶点）和边组成的集合。
节点表示实体，边表示节点之间的关系。
图可以用以下方式进行表示：邻接矩阵和邻接表。
1. 邻接矩阵：用二维数组表示图的连接关系，其中数组元素a[i][j]表示节点i到节点j是否存在一条边。
2. 邻接表：使用链表或数组的方式表示节点的连接关系。
每个节点对应一个链表，链表中存储与该节点相连接的其他节点。
二、图的基本操作1. 添加节点：图中可以通过添加节点来增加实体。
添加节点时，需要更新相应的连接关系，即在邻接矩阵或邻接表中添加对应的行或节点。
2. 添加边：向图中添加边可以表示节点之间的关系。
在邻接矩阵中，将对应的元素设置为1。
在邻接表中，将对应的节点添加到该节点的链表中。
3. 删除节点：从图中删除节点时，需要将与该节点相关的边一并删除。
删除节点后，对应的行或链表也需要进行相应的调整。
4. 删除边：删除边可以断开节点之间的关系。
在邻接矩阵中，将对应的元素设置为0。
在邻接表中，删除对应的节点。
三、图的应用场景1. 社交网络分析：图可以用于分析社交网络中的关系，如朋友关系、粉丝关系等。
可以通过图的遍历算法，寻找潜在的朋友或影响力人物。
2. 路径规划：图可以表示地理空间中的路径，如导航系统中的道路网络。
可以使用图的最短路径算法，如Dijkstra算法或A*算法，来计算最优路径。
3. 组织架构图：图可以用于表示组织或公司的架构，帮助人们更好地理解不同部门之间的关系和沟通路径。
4. 网络流量分析：图可以用于分析网络中的流量，如网络路由、数据传输等。
可以通过图的最大流算法，如Ford-Fulkerson算法，来优化网络流量分配和传输效率。
5. 数据库关系图：图可以用于表示数据库中的关系表，帮助人们理解和查询表之间的关系，如主外键关系等。
中原工学院《数据结构》实验报告学院：计算机学院专业：计算机科学与技术班级：计科112姓名：康岩岩学号：201100814220 指导老师：高艳霞2012-11-22实验五图的基本操作一、实验目的1、使学生可以巩固所学的有关图的基本知识。
2、熟练掌握图的存储结构。
3、熟练掌握图的两种遍历算法。
二、实验内容[问题描述]对给定图，实现图的深度优先遍历和广度优先遍历。
[基本要求]以邻接表为存储结构，实现连通无向图的深度优先和广度优先遍历。
以用户指定的结点为起点，分别输出每种遍历下的结点访问序列。
【测试数据】由学生依据软件工程的测试技术自己确定。
三、实验前的准备工作1、掌握图的相关概念。
2、掌握图的逻辑结构和存储结构。
3、掌握图的两种遍历算法的实现。
四、实验报告要求1、实验报告要按照实验报告格式规范书写。
2、实验上要写出多批测试数据的运行结果。
3、结合运行结果，对程序进行分析。
【设计思路】【代码整理】#include "stdafx.h"#include <iostream>#include <malloc.h>using namespace std;typedef int Status;#define OK 1#define ERROR 0#define OVERFLOW -1#define MAX_SIZE 20typedef enum{DG,DN,UDG,UDN}Kind;typedef struct ArcNode{int adjvex; //顶点位置struct ArcNode *nextarc; //下一条弧int *info; //弧信息};typedef struct{char info[10]; //顶点信息ArcNode *fistarc; //指向第一条弧}VNode,AdjList[MAX_SIZE];typedef struct{AdjList vertices;int vexnum,arcnum; //顶点数，弧数int kind; //图的种类，此为无向图}ALGraph;//这是队列的节点，仅用于广度优先搜索typedef struct Node{int num;struct Node* next;};//队列的头和尾typedef struct{Node * front;Node *rear;}PreBit;int LocateV ex(ALGraph G,char info[]);//定位顶点的位置Status addArcNode(ALGraph &G,int adjvex); //图中加入弧Status CreatGraph(ALGraph&G);//创建图的邻接表Status DFSTraverse(ALGraph G);//深度优先搜索Status BFSTraverse(ALGraph G);//广度优先搜索Status DFS(ALGraph G,int v);//深度优先搜索中的数据读取函数，用于递归bool visited[MAX_SIZE]; // 访问标志数组//初始化队列Status init_q(PreBit&P_B){P_B.front=P_B.rear=(Node*)malloc(sizeof(Node));if(!P_B.front){exit(OVERFLOW);}P_B.front->next=NULL;}//将数据入队Status en_q(PreBit & P_B,int num){Node *p=(Node*)malloc(sizeof(Node));if(!p){exit(OVERFLOW);}p->num=num;p->next=NULL;P_B.rear->next=p;P_B.rear=p;return OK;}//出队Status de_q(PreBit & P_B){if(P_B.front==P_B.rear){return ERROR;}Node* p=P_B.front->next;P_B.front->next=p->next;if(P_B.rear==p){P_B.rear=P_B.front;}free(p);return OK;}Status CreatGraph(ALGraph&G){cout<<"请输入顶点数目和弧数目"<<endl;cin>>G.vexnum>>G.arcnum;//依次输入顶点信息for(int i=0;i<G.vexnum;i++){cout<<"请输入顶点名称"<<endl;cin>>G.vertices[i].info;G.vertices[i].fistarc=NULL;}//依次输入弧信息for(int k=1;k<=G.arcnum;k++){char v1[10],v2[10]; //用于表示顶点名称的字符数组int i,j; //表示两个顶点的位置BACK: //返回点cout<<"请输入第"<<k<<"条弧的两个顶点"<<endl;cin>>v1>>v2;i=LocateV ex(G,v1); //得到顶点v1的位置j=LocateV ex(G,v2); //得到顶点v2的位置if(i==-1||j==-1){ //头信息不存在则返回重输cout<<"不存在该节点!"<<endl;goto BACK; //跳到BACK 返回点}addArcNode(G,i); //将弧的顶点信息插入表中addArcNode(G,j);}return OK;}//倒序插入弧的顶点信息Status addArcNode(ALGraph &G,int adjvex){ArcNode *p; //弧节点指针p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=adjvex;p->nextarc=G.vertices[adjvex].fistarc;//指向头结点的第一条弧G.vertices[adjvex].fistarc=p; //头结点的第一条弧指向p，即将p作为头结点的第一条弧return OK;}//定位顶点的位置int LocateV ex(ALGraph G,char info[]){for(int i=0;i<G.vexnum;i++){if(strcmp(G.vertices[i].info,info)==0){ //头结点名称与传入的信息相等，证明该头节点存在return i; //此时返回位置}}return -1;}//深度优先搜索Status DFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int i;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;i=LocateV ex(G,v1);if(i==-1){cout<<"不存在该节点!"<<endl;goto BACK;}DFS(G,i);return OK;}//深度优先搜索递归访问图Status DFS(ALGraph G,int v){visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息ArcNode *p;p=G.vertices[v].fistarc; //向头节点第一条while(p) //当弧存在{if(!visited[p->adjvex]){DFS(G,p->adjvex); //递归读取}p=p->nextarc;}return OK;}//广度优先搜索Status BFSTraverse(ALGraph G){for(int v=0;v<G.vexnum;v++){visited[v]=false;}char v1[10];int v;BACK:cout<<"请输入首先访问的顶点"<<endl;cin>>v1;v=LocateV ex(G,v1);if(v==-1){cout<<"不存在该节点!"<<endl;goto BACK;}PreBit P_B;init_q(P_B);ArcNode *p;visited[v]=true;cout<<G.vertices[v].info<<" ";//输出信息en_q(P_B,v); //将头位置v入队while(P_B.front!=P_B.rear){//当队列不为空时，对其进行访问int w=P_B.front->next->num;//读出顶点位置de_q(P_B);//顶点已经访问过，将其出队列p=G.vertices[w].fistarc;//得到与顶点相关的第一条弧while(p){if(!visited[p->adjvex]){en_q(P_B,p->adjvex);//将弧入队，但不读取，只是将其放在队尾}p=p->nextarc;}}return OK;}int _tmain(int argc, _TCHAR* argv[]){ALGraph G;CreatGraph(G);cout<<"深度优先搜索图:"<<endl;DFSTraverse(G);cout<<endl;cout<<"广度优先搜索图:"<<endl;BFSTraverse(G);cout<<endl;system("pause");return 0;}。
武 夷 学 院课程设计报告课程名称： 数据结构设计题目： 图的基本操作及应用 学生班级： 学生姓名： 指导教师：完成日期：2012.5.30数学与计算机系课程设计项目研究报告目录第 1 章项目简介 (3)1.1 项目名称 (3)1.2 开发人员 (3)1.3 指导教师 (3)第 2 章项目研究意义 (3)2.1 课程设计概述 (3)第3章课程设计项目进度表 (4)第4 章课程设计任务分配表 (5)第5 章达到的效果 (6)图5—1 6 5．2 图的数据类型定义表 (7)第6 章源程序 (17)第7 章附录 (28)（1）图的基本操作及应用 (28)（2）二叉树的遍历 (29)第8 章设计心得 (29)第9 章参考文献 (30)第 1 章项目简介1.1 项目名称（1）图的基本操作及应用（2）二叉树的遍历1.2 开发人员1.3 指导教师第 2 章项目研究意义2.1 课程设计概述（1）图是一种比树更为复杂的一些的非线性结构。
在图状结构中，任意两个结点之间都可能具有邻接关系，也就是在图的数据元素之间存在多对多的关系。
所以图状结构可以描述任意结点之间的关系，例如各种线性结构和树形结构，这些都可以看做图这种结构的特例。
于是，从某种意义上讲，图应该是一种最基本的数据结构。
图是一种应用极为广泛的数据结构。
比如，在供电网络分析、交通运输管理、市政管线铺设、工作进度安排等诸多方面，都常采用图状结构来模拟各种复杂的数据对象。
当前，它的应用已经渗透到了计算机科学、社会科学、人文科学、工程技术等各个领域。
本设计基于图的结构，创建一个无向图，基于设计要求，我们对要求进行编号，让用户可以自由选择操作，我们可以将各个顶点的数据域储存所需的信息，可以用深度遍历或者广度遍历对信息进行访问，也可以删除顶点的数据。
这对于很多操作系统都是很需要的。
1本程序的功能是对任意二叉树进行递归前序遍历和后序遍历 用栈实现非递归的前序、和后序遍历 还有对树的层序遍历以及树与二叉树的转换。
图的操作C语言课程设计一、教学目标本课程的教学目标是使学生掌握图的操作的基本概念、原理和方法，能够运用C语言实现图的基本操作，如建立图、查找顶点、边的相关操作等。
通过本课程的学习，使学生具备以下知识目标：1.理解图的基本概念，如顶点、边、度、相邻顶点等。
2.掌握图的存储结构，如邻接矩阵、邻接表等。
3.熟悉图的基本操作，如添加和删除顶点、边，查找顶点、边的相关操作等。
4.能够使用C语言实现图的基本操作。
5.能够运用图的操作解决实际问题，如最短路径问题、最小生成树问题等。
情感态度价值观目标：1.培养学生的团队合作意识，通过实验和项目使学生学会与他人合作解决问题。
2.培养学生的创新思维，鼓励学生尝试新的方法解决问题。
3.培养学生对计算机科学的兴趣，激发学生继续学习计算机科学的热情。
二、教学内容本课程的教学内容主要包括图的基本概念、图的存储结构、图的基本操作以及图的应用。
具体安排如下：1.图的基本概念：介绍图的定义、顶点、边、度等基本概念。
2.图的存储结构：介绍邻接矩阵、邻接表等图的存储方式。
3.图的基本操作：介绍添加和删除顶点、边，查找顶点、边的相关操作等。
4.图的应用：介绍图的应用场景，如最短路径问题、最小生成树问题等。
三、教学方法为了激发学生的学习兴趣和主动性，本课程将采用多种教学方法，如讲授法、讨论法、案例分析法、实验法等。
1.讲授法：通过讲解图的基本概念、原理和方法，使学生掌握图的基础知识。
2.讨论法：通过分组讨论，使学生深入理解图的操作和应用。
3.案例分析法：通过分析实际案例，使学生学会运用图的操作解决实际问题。
4.实验法：通过上机实验，使学生动手实现图的操作，巩固所学知识。
四、教学资源为了支持教学内容和教学方法的实施，丰富学生的学习体验，我们将选择和准备以下教学资源：1.教材：《C语言程序设计》2.参考书：《数据结构与算法》3.多媒体资料：PPT课件、教学视频等4.实验设备：计算机、网络等以上教学资源将帮助学生更好地学习图的操作，提高学生的编程能力和解决问题的能力。
工程制图CAD操作基础一、制图基本操作程序：1、建立图形界线：菜单中“格式”—图形界线—空格-输数字“X，Y”—空格---“Z”—空格—“E”---空格。
2、建立图层图层是透明的电子纸张，点开图层特性管理器，图层的属性：线型，线宽，线的颜色。
新建图层，可删除，打√为当前图层。
名称单击可修改。
菜单中“格式”—线型—“显示细节”—更改“全局比例因子”---一般为20—50注：当前对象缩放比例—不改，1）、图层关闭后图形不可见，但能绘制不可打印。
2）、图层锁定后，图形可见，不能编辑，可打印。
3）、图层冻结后不可见，不可绘制，不能编辑，不可打印。
3、操作必须在英文状态才能操作。
4、使用坐标确定点1）、绝对直角坐标（X，Y）2）、相对直角坐标（@X,Y）相对坐标是相对上一点而言，闭会—C—空格，二、常用的命令：1、画直线：L—空格—输数值—空格，2、偏移：O—空格---输偏移数值—空格---选对象—往偏移方向点。
封闭图形可整体偏移，针对封闭图形只偏移单线：XL—空格—O—空格3、对象捕捉F3，栅格F7，正交F8，捕捉F9、极轴F10，对象追综F114、修剪：TR 修剪必须是两根相交线才能操作。
TR—空格—选择1）、TR—空格—选择—空格—剪哪选哪2）、TR—空格—选择边界对象3）、TR—空格—空格--剪哪选哪4)、TR—空格—空格—按住shift—选择延伸的对象5）、TR--空格—空格—F--空格（快速修剪）一次最多可修两条。
6）、TR--空格—空格—E--空格--E—空格（假设延伸修剪）5、延伸：EX--空格—空格—延伸谁就点谁延长线：可点击线，光标拖动蓝块线条延长6、镜像：（对象性复制）mi--空格—选择对象--空格—指定对象线的一点—F8---是否—是选Y或N （Y是删除原图，N是保留原图）7、移动：m-空格—选定对象点—右击对象捕捉—打开中点—点击---空格8、旒转： RORO--空格—选择对象—旒转中心—点下一点或输180度—空格9、复制：CO--空格—选择对象---空格三、常用的操作：1、垂足、延伸、中点、交点、端点等单右击捕捉对象—设置—打开选择，一般画图要关闭捕捉。
图像基础操作方法包括
图像基础操作方法包括：
1. 图像读取：从硬盘上读取图像文件，并将其加载到内存中，以便进行后续处理。
2. 图像显示：将加载到内存中的图像显示在屏幕上，让用户可以观看图像内容。
3. 图像保存：将处理过的图像保存到硬盘上的文件中，以便后续使用或分享。
4. 图像复制：将一幅图像的内容复制到另一幅图像中，用于图像的叠加或合成。
5. 图像裁剪：根据指定的坐标和尺寸，在图像中选取某个区域，获取感兴趣的图像部分。
6. 图像缩放：调整图像的尺寸大小，可以放大或缩小图像，改变图像的显示效果。
7. 图像旋转：将图像绕某个中心点进行旋转，可以按照不同角度进行顺时针或逆时针旋转。
8. 图像灰度化：将彩色图像转换为灰度图像，降低图像的维度，方便后续处理。
9. 图像二值化：将灰度图像转换为二值图像，根据阈值将像素值转化为黑色或白色。
10. 图像平滑：对图像进行平滑处理，减少图像的噪声或纹理，提升图像的质量。
11. 图像锐化：增强图像的边缘和细节，使图像的轮廓更加清晰和鲜明。
12. 图像滤波：应用不同滤波器对图像进行处理，如高斯滤波、中值滤波等，改变图像的频域特征。
13. 图像边缘检测：提取图像中的边缘信息，用于图像分割和物体识别。
14. 图像配准：将多幅图像进行校准和对齐，以便进行图像融合和信息提取。
15. 图像变换：对图像进行几何变换，如平移、缩放、旋转等，改变图像的位置和形状。
这些方法是进行图像处理和分析的基础操作，常用于计算机视觉、图像识别、医学影像等领域。
哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构课程类型：必修实验项目名称：第三次实验实验题目：图的基本操作班级：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;}。
