下载文档原格式
数据结构实验报告目的要求１．掌握图的存储思想及其存储实现..２．掌握图的深度、广度优先遍历算法思想及其程序实现..３．掌握图的常见应用算法的思想及其程序实现..实验内容１．键盘输入数据;建立一个有向图的邻接表..２．输出该邻接表..3．在有向图的邻接表的基础上计算各顶点的度;并输出..4．以有向图的邻接表为基础实现输出它的拓扑排序序列..5．采用邻接表存储实现无向图的深度优先递归遍历..6．采用邻接表存储实现无向图的广度优先遍历..7．在主函数中设计一个简单的菜单;分别调试上述算法..源程序：主程序的头文件：队列#include <stdio.h>#include <stdlib.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -2typedef int QElemType;typedef struct QNode{ //队的操作QElemType data;struct QNode *next;}QNode;*QueuePtr;typedef struct {QueuePtr front;QueuePtr rear;}LinkQueue;void InitQueueLinkQueue &Q{ //初始化队列Q.front =Q.rear =QueuePtrmallocsizeofQNode;ifQ.front exitOVERFLOW; //存储分配失败Q.front ->next =NULL;}int EnQueueLinkQueue &Q;QElemType e //插入元素e为Q的新的队尾元素{QueuePtr p;p=QueuePtrmallocsizeofQNode;ifp exitOVERFLOW;p->data=e;p->next=NULL;Q.rear->next=p;Q.rear =p;return OK;}int DeQueueLinkQueue &Q;QElemType &e //删除Q的队头元素;用e返回其值{ ifQ.front ==Q.rear return ERROR;QueuePtr p;p=Q.front ->next;e=p->data;Q.front->next=p->next ;ifQ.rear==p Q.rear =Q.front ;freep;return OK;}主程序：#include <stdio.h>#include<stdlib.h>#include"duilie.h"#define TRUE 1#define FALSE 0#define Status int#define MAX_VERTEX_NUM 8 /*顶点最大个数*/#define VertexType char /*顶点元素类型*/enum BOOlean {False;True};BOOlean visitedMAX_VERTEX_NUM; //全局变量——访问标志数组typedef struct ArcNode{int adjvex;struct ArcNode *nextarc;int weight; /*边的权*/}ArcNode; /*表结点*/typedef struct VNode{ int degree;indegree;/*顶点的度;入度*/V ertexType data;ArcNode *firstarc;}VNode/*头结点*/;AdjListMAX_VERTEX_NUM;typedef struct{ AdjList vertices;int vexnum;arcnum;/*顶点的实际数;边的实际数*/}ALGraph;//建立图的邻接表void creat_linkALGraph *G{ int i;j;ArcNode *s;printf"请依次输入顶点数、边数：";scanf"%d%d";&G->vexnum;&G->arcnum;for i=0;i<G->vexnum;i++{ G->verticesi.data='A'+i;G->verticesi.firstarc=NULL;}for i=0;i<G->vexnum;{ printf"请输入顶点的数组坐标若退出;请输入-1：";scanf"%d";&i;ifi==-1 break;printf"请输入顶点所指向下一个顶点的数组坐标：";scanf"%d";&j;s=ArcNode *mallocsizeofArcNode;s->adjvex=j;s->nextarc=G->verticesi.firstarc;G->verticesi.firstarc=s;}}// 输出邻接表void visitALGraph G{ int i;ArcNode *p;printf"%4s%6s%18s\n";"NO";"data";"adjvexs of arcs";for i=0;i<G.vexnum;i++{printf"%4d%5c ";i;G.verticesi.data;forp=G.verticesi.firstarc;p;p=p->nextarcprintf"%3d";p->adjvex;printf"\n";}}// 计算各顶点的度及入度void cacuALGraph *G{ArcNode *p;int i;for i=0;i<G->vexnum;i++{G->verticesi.degree=0;G->verticesi.indegree=0;}//度与初度初始化为零for i=0;i<G->vexnum;i++forp=G->verticesi.firstarc;p;p=p->nextarc{G->verticesi.degree++;G->verticesp->adjvex.degree++;G->verticesp->adjvex.indegree++;}}void print_degreeALGraph G{int i;printf"\n Nom data degree indegree\n";for i=0;i<G.vexnum;i++printf"\n%4d%5c%7d%8d";i;G.verticesi.data;G.verticesi.degree;G.verticesi.indegree;printf"\n";}// 拓扑排序Status TopologiSortALGraph G{int i;count;top=0;stack50;ArcNode *p;cacu&G;print_degreeG;printf"\nTopologiSort is \n";fori=0;i<G.vexnum;i++ifG.verticesi.indegree stacktop++=i;count=0;whiletop=0{i=stack--top;if count==0 printf"%c";G.verticesi.data;else printf"-->%c";G.verticesi.data;count++;forp=G.verticesi.firstarc;p;p=p->nextarcif --G.verticesp->adjvex.indegreestacktop++=p->adjvex;}if count<G.vexnumreturnFALSE; else returnTRUE;}//在图G中寻找第v个顶点的第一个邻接顶点int FirstAdjVexALGraph G;int v{ifG.verticesv.firstarc return 0;else returnG.verticesv.firstarc->adjvex;}//在图G中寻找第v个顶点的相对于u的下一个邻接顶点int NextAdjVexALGraph G;int v;int u{ArcNode *p;p=G.verticesv.firstarc;whilep->adjvex=u p=p->nextarc; //在顶点v的弧链中找到顶点u ifp->nextarc==NULL return 0; //若已是最后一个顶点;返回0else returnp->nextarc->adjvex; //返回下一个邻接顶点的序号}//采用邻接表存储实现无向图的深度优先递归遍历void DFSALGraph G;int i{ int w;visitedi=True; //访问第i个顶点printf"%d->";i;forw=FirstAdjVexG;i;w;w=NextAdjVexG;i;wifvisitedw DFSG;w; //对尚未访问的邻接顶点w调用DFS}void DFSTraverseALGraph G{ int i;printf"DFSTraverse:";fori=0;i<G.vexnum;i++ visitedi=False; //访问标志数组初始化fori=0;i<G.vexnum;i++ifvisitedi DFSG;i; //对尚未访问的顶点调用DFS}//按广度优先非递归的遍历图G;使用辅助队列Q和访问标志数组visited void BFSTraverseALGraph G{int i;u;w;LinkQueue Q;printf"BFSTreverse:";fori=0;i<G.vexnum;i++ visitedi=False; //访问标志数组初始化InitQueueQ; //初始化队列fori=0;i<G.vexnum;i++ifvisitedi{visitedi=True; //访问顶点iprintf"%d->";i;EnQueueQ;i; //将序号i入队列whileQ.front ==Q.rear //若队列不空;继续{DeQueueQ;u; //将队头元素出队列并置为uforw=FirstAdjVexG;u;w;w=NextAdjV exG;u;wifvisitedw //对u的尚未访问的邻接顶点w进行访问并入队列{ visitedw=True;printf"%d->";w;EnQueueQ;w;}}}}void main{ALGraph G;int select;printf" 图的有关操作实验\n ";do{printf"\n1 创建一个有向图的邻接表 2 输出该邻接表\n";printf"3.输出该有向图的度和入度 4.输出该有向图拓扑排序序列\n";printf"5.创建一个无向图的邻接表 6.深度优先递归遍历该无向图\n";printf"7.广度优先遍历该无向图0.退出\n";printf"请输入选择：";scanf"%d";&select;switchselect{case 1:printf"\n创建一个有向图的邻接表：\n";creat_link&G;break;case 2:printf"\n输出该邻接表：\n";visitG;break;case 3:printf"\n输出该有向图的度和入度：\n";cacu&G;print_degreeG;break;case 4:printf"\n输出该有向图拓扑排序序列：\n";ifTopologiSortGprintf"Toposort is not success";break;case 5:printf"\n创建一个无向图的邻接表: \n";creat_link&G;break;case 6:printf"\n深度优先递归遍历该无向图: \n";DFSTraverseG;break;case 7:printf"\n广度优先遍历该无向图：\n";BFSTraverseG;break;case 0:break;default:printf"输入选项错误重新输入\n";}}whileselect;}运行结果截图：1.主菜单界面：2.创建一个有向图的领接表3.输出该邻接表4. 在有向图的邻接表的基础上计算各顶点的度;并输出..5. 输出它的拓扑排序序列6. 输出所建无向图的邻接表7. 深度优先递归遍历该无向图8. 广度优先遍历该无向图说明：本实验用的有向图是课本182页图7.28;无向图为课本168页图a实验总结这次的图的操作实验;与树的操作类似;但又比树复杂;包含更多的存储结构和遍历方法的操作;而且图的遍历需要沿着弧进行;以便输出弧上的信息..本实验中图的遍历采用邻接表的存储结构;在输入图的信息时;首先要画出图的邻接表信息..图有两种遍历的形式;一种为深度优先搜索;另一种为广度优先搜索..由于能力有限;没能实现图的深度非递归优先搜索;而是实现了图的深度递归优先搜索..本实验基本完成了图的操作;也学到了很多关于图的知识和算法..。
数据结构.图及应用数据结构是计算机科学中非常重要的一个概念，它是一种以特定方式组织和存储数据的方法。
图是数据结构中的一种类型，它由节点（或顶点）和连接这些节点的边组成。
图结构是一种非常灵活和强大的数据结构，它在计算机科学中有着广泛的应用。
在本文中，我将介绍图的数据结构及其应用，并探讨图在实际中的应用场景和作用。
首先，让我们来了解一下图的基本概念和特点。
图由节点和边组成，节点可以是任何类型的数据，比如数字、字符、对象等。
边则是节点之间的连接关系，它可以是有向的或者无向的。
图结构可以分为有向图和无向图两种类型，有向图的边有方向，而无向图的边没有方向。
图结构还可以是带权图，这种图的边上带有权重，表示了节点之间的关联程度或者距离。
图的数据结构可以使用多种方式来实现，比如邻接矩阵、邻接表、关联矩阵等。
邻接矩阵是使用二维数组来表示图的边关系，它的优点是可以快速地判断任意两个节点之间是否有边，但缺点是对于稀疏图来说会浪费大量的空间。
邻接表则是使用链表或数组来表示节点之间的连接关系，它的优点是节省空间，但查找任意两个节点之间是否有边需要遍历链表或数组。
图的数据结构在计算机科学中有着广泛的应用。
其中最直观的一个应用就是在地图导航系统中。
地图可以被表示成一个图结构，节点代表地点，边代表道路或路径。
利用图的数据结构，我们可以很容易地找到两个地点之间的最短路径，或者进行路线规划。
比如我们要从一个地方到另一个地方，我们可以利用图的搜索算法（比如深度优先搜索或者广度优先搜索）来找到最短路径或者规划出一条合适的路线。
另一个图的应用是在社交网络分析中。
社交网络可以被看做是一个图结构，其中节点代表用户，边代表用户之间的关系（比如好友关系）。
利用图的数据结构，我们可以进行社交网络的分析，比如查找两个用户之间的关系链，或者进行用户群体的聚类分析。
图的算法在社交网络中有着很广泛的应用，比如社区发现算法、影响力传播模型等。
此外，图的数据结构还可以用于解决一些复杂的优化问题。
数据结构图的应用实验原理1. 引言数据结构是计算机科学中的核心概念之一，它是用来组织和存储数据的一种方式。
在软件开发过程中，合理的数据结构设计可以极大地提高程序的性能和可维护性。
数据结构图是一种图形化的表示方式，它可以帮助我们分析和理解各种数据结构的关系和特性。
2. 实验目的本实验旨在通过实际应用的方式，深入理解数据结构图的原理和应用。
具体目的包括： - 掌握数据结构图的基本定义和特性 - 理解数据结构图在实际问题中的应用 - 学会使用数据结构图对复杂问题进行分析和解决3. 实验步骤1.选择适当的数据结构图工具：在进行数据结构图实验之前，我们需要选择一种合适的工具来绘制和表示数据结构图。
常见的数据结构图工具包括UML工具、流程图工具等，根据实验要求选择最合适的工具进行操作。
2.定义数据结构图：根据实际问题需求，确定所需的数据结构和相关关系，包括数据结构的类型、属性和操作等。
使用选定的工具，绘制数据结构图并对其进行命名。
3.分析数据结构图：对于给定的数据结构图，我们需要仔细分析其特性和关系。
可以通过观察图中的节点和边的连接方式，了解数据结构之间的层次关系和组织方式。
4.进行实验操作：根据实验要求，对数据结构图进行相关操作和计算。
可以使用图算法来解决具体问题，或者通过图的遍历来分析图中的各个节点和边的特性。
5.结果分析和总结：根据实验操作的结果，对实验过程和结果进行分析和总结。
比较实际结果与预期结果的差异，找出原因并提出改进建议。
4. 实验示例为了更好地理解数据结构图的应用实验原理，以下是一个简单的示例：假设有一家公司，需要管理公司内部的职员信息。
公司中的职员分为不同的部门，每个部门有若干个职位，每个职位对应一个或多个职员。
我们可以使用数据结构图来表示公司职员信息的组织结构。
1.定义数据结构图：根据公司内部的组织结构，我们可以定义如下的数据结构图：–节点1：公司（Company）•属性：公司名称–节点2：部门（Department）•属性：部门名称–节点3：职位（Position）•属性：职位名称–节点4：职员（Employee）•属性：职员姓名2.建立节点之间的关系：根据公司职员信息的实际关系，我们可以建立如下的节点之间的关系：–公司节点与部门节点之间的关系是一对多的关系–部门节点与职位节点之间的关系是一对多的关系–职位节点与职员节点之间的关系是一对多的关系3.实验操作：根据定义的数据结构图，我们可以进行各种实验操作，如：–查找某个职员所在的部门和职位–统计某个部门的职员数量–查找某个职员的上级领导4.结果分析和总结：通过实验操作，我们可以得到实际的结果，并进行分析和总结。
数据结构图的实验报告数据结构图的实验报告引言：数据结构图是计算机科学中重要的概念之一。
它是一种用图形表示数据元素之间关系的数据结构，广泛应用于算法设计、程序开发和系统优化等领域。
本实验报告旨在介绍数据结构图的基本原理、实验过程和结果分析。
一、实验目的本次实验的主要目的是掌握数据结构图的基本概念和操作方法，以及通过实验验证其在解决实际问题中的有效性。
具体而言，我们将通过构建一个社交网络关系图，实现对用户关系的管理和分析。
二、实验方法1. 确定数据结构在本次实验中，我们选择了无向图作为数据结构图的基础。
无向图由顶点集和边集组成，每条边连接两个顶点，且没有方向性。
2. 数据输入为了模拟真实的社交网络，我们首先需要输入一组用户的基本信息，如姓名、年龄、性别等。
然后，根据用户之间的关系建立边，表示用户之间的交流和联系。
3. 数据操作基于构建好的数据结构图，我们可以进行多种操作，如添加用户、删除用户、查询用户关系等。
这些操作将通过图的遍历、搜索和排序等算法实现。
三、实验过程1. 数据输入我们首先创建一个空的无向图，并通过用户输入的方式逐步添加用户和用户关系。
例如，我们可以输入用户A和用户B的姓名、年龄和性别，并建立一条边连接这两个用户。
2. 数据操作在构建好数据结构图后，我们可以进行多种操作。
例如，我们可以通过深度优先搜索算法遍历整个图，查找与某个用户具有特定关系的用户。
我们也可以通过广度优先搜索算法计算某个用户的社交网络影响力，即与该用户直接或间接相连的其他用户数量。
3. 结果分析通过实验，我们可以观察到数据结构图在管理和分析用户关系方面的优势。
它能够快速地找到用户之间的关系，帮助我们了解用户的社交网络结构和影响力。
同时，数据结构图也为我们提供了一种可视化的方式来展示用户之间的关系，使得分析更加直观和易于理解。
四、实验结果通过实验，我们成功构建了一个社交网络关系图，并实现了多种数据操作。
我们可以根据用户的姓名、年龄和性别等信息进行查询，也可以根据用户之间的关系进行遍历和排序。
数据结构实验报告--图
数据结构实验报告--图
1、实验目的
本实验主要旨在通过实践操作，深入理解图这种数据结构的基本概念、性质和基本操作，掌握图的存储结构与常见算法。
2、实验环境
本次实验使用编程语言C++，在Windows平台下进行开发和运行。
3、实验内容
3.1 图的定义与基本概念
在本章中，我们将介绍图的基本概念，包括有向图与无向图、顶点与边、度与入度出度、连通性等。
3.2 图的存储结构
在本章中，我们将介绍图的几种存储结构，包括邻接矩阵、邻接表和十字链表，以及它们的优缺点和适用场景。
3.3 图的遍历
在本章中，我们将介绍图的两种常用的遍历算法，即深度优先搜索（DFS）和广度优先搜索（BFS），并分别给出它们的实现代码和应用场景。
3.4 最短路径
在本章中，我们将介绍图的最短路径问题，包括单源最短路径和全源最短路径。
我们将使用Dijkstra算法和Floyd-Warshall算法来解决这些问题，并给出它们的实现代码和应用场景。
3.5 最小树
在本章中，我们将介绍图的最小树问题，即找到一棵树使得树上的边的权值之和最小。
我们将使用Prim算法和Kruskal算法来解决这个问题，并给出它们的实现代码和应用场景。
4、实验步骤和结果
在本章中，我们将详细介绍实验的具体步骤，并给出实验结果的详细分析和说明。
5、实验总结
在本章中，我们将对整个实验进行总结，总结实验中遇到的问题、解决方案和经验教训。
6、附件
本实验报告所涉及的附件包括实验代码和运行结果的截图。
7、法律名词及注释
本文所涉及的法律名词和注释详见附件中的相关文件。
实验题目：图的应用一、实验目的和任务1 掌握图的邻接表和邻接矩阵存储；2 掌握图的拓扑排序算法；二、实验内容及原理1以下两项内容选做一项。
2 请按照书中介绍的拓扑排序算法，完成P303页第5题。
3 给定某一个图，完成其深度优先搜索遍历和广度优先搜索遍历，每种遍历都必须在邻接矩阵和邻接表中完成。
四、实验数据及程序代码#include <iostream.h>#include <stdlib.h>#include <strstrea.h>#include <string.h>#include <stdio.h>const int MaxVertexNum=10;typedef int WeightType;struct edgenode{int adjvex;WeightType weight;edgenode*next;};typedef edgenode *adjlist[MaxVertexNum];void InitAdjoin(adjlist GL)//初始化{for(int i=0;i<MaxVertexNum;i++)GL[i]=NULL;}void CreatAdjoin(adjlist GL,int n,char*s,int k1,int k2)//生成邻接表{istrstream sin(s);char c1,c2,c3;WeightType w;edgenode*p;sin>>c1;if(k2==0){do{sin>>c1>>i>>c2>>j>>c3;p=new edgenode;p->adjvex=j;p->weight=1;p->next=GL[i];GL[i]=p;if(k1==0){p=new edgenode;p->adjvex=i;p->weight=1;p->next=GL[j];GL[j]=p;}sin>>c1;}while(c1==',');}else{do{sin>>c1>>i>>c2>>j>>c3>>w;p=new edgenode;p->adjvex=j;p->weight=w;p->next=GL[i];GL[i]=p;if(k1==0){p=new edgenode;p->adjvex=i;p->weight=w;p->next=GL[j];GL[j]=p;}sin>>c1;}while(c1==',');}}void PrintAdjion(adjlist GL, int n,int k1, int k2) {edgenode*p;cout<<"V={";for(i=0; i<n-1; i++) cout<<i<<',';cout<<n-1<<'}'<<endl;cout<<"E={";for(i=0;i<n;i++){if(k2==0){p=GL[i];while(p){j=p->adjvex;if(k1==0){if(i<j) cout<<'('<<i<<','<<j<<')'<<',';}elsecout<<'<'<<i<<","<<j<<'>'<<',';p=p->next;}}else{p=GL[i];while(p){j=p->adjvex;if(k1==0){if(i<j) cout<<'('<<i<<','<<j<<')'<<p->weight<<',';}elsecout<<'<'<<i<<','<<j<<'>'<<p->weight<<',';p=p->next;}}}cout<<'}'<<endl;}void Toposort(adjlist GL , int n){int i,j,k,top,m=0;edgenode*p;int*d=new int[n];for(i=0;i<n;i++) d[i]=0;for(i=0;i<n;i++){p=GL[i];while(p!=NULL){j=p->adjvex;d[i]++;p=p->next;//cout<<j;}}top=-1;for(i=0;i<n;i++)if(d[i]==0){d[i]=top; top=i;}while(top!=-1){j=top;top=d[top];cout<<j<<' ';m++;p=GL[j];while(p!=NULL){k=p->adjvex;d[k]--;if(d[k]==0){d[k]=top;top=k;}p=p->next;}}cout<<endl;cout<<top<<endl;cout<<m<<endl;cout<<n<<endl;if(m<n) cout<<"The network has a cycle!"<<endl;delete []d;}void main(){int n,k1,k2;cout<<"输入待处理图的顶点数:";cin>>n;cout<<"输入图的有无向和有无权选择（0为无，非0为有）:";cin>>k1>>k2;adjlist gl;InitAdjoin(gl);cout<<"输入图的边集:";FILE *p;p=fopen("d:\\1.txt","r+");char *a=new char[100];while (!feof(p)){fscanf(p,"%s ",a);cout<<a;}cout<<endl;//cin>>a;CreatAdjoin(gl,n,a,k1,k2);Toposort(gl,n);}五、实验数据分析及处理六、实验结论与感悟（或讨论）图的邻接矩阵，邻接表和边集数组表示各有利弊，具体运用时，要根据图的稠密和稀疏程度以及算法的要求进行选择。
数据结构图实验报告数据结构图实验报告引言：数据结构是计算机科学中非常重要的一个概念，它用于存储和组织数据，使得数据的操作更加高效和方便。
图是一种常见的数据结构，它由节点和边组成，用于表示各种实际问题中的关系和连接。
本实验旨在通过实际操作，深入理解图的基本概念和常见操作。
实验目的：1. 理解图的基本概念和特性；2. 掌握图的存储结构和基本操作；3. 实现图的遍历算法；4. 分析图的应用场景。
实验过程：1. 图的存储结构：在本次实验中，我们选择邻接矩阵来存储图。
邻接矩阵是一个二维数组，其中行和列分别表示图中的节点，数组元素表示节点之间的边的关系。
具体而言，如果节点i和节点j之间存在边，则邻接矩阵中的第i行第j列元素为1；否则为0。
2. 图的基本操作：在实验中，我们实现了以下几个图的基本操作：- 添加节点：通过向邻接矩阵中添加一行一列，并设置对应的边的关系，来添加一个节点；- 添加边：通过修改邻接矩阵中对应元素的值，来添加一条边；- 删除节点：通过删除邻接矩阵中对应行和列，并更新其他节点的索引，来删除一个节点；- 删除边：通过修改邻接矩阵中对应元素的值，来删除一条边；- 查找节点：通过遍历邻接矩阵，找到对应节点的索引；- 查找边：通过遍历邻接矩阵，找到对应边的关系。
3. 图的遍历算法：在实验中，我们实现了深度优先搜索（DFS）和广度优先搜索（BFS）两种图的遍历算法。
DFS通过递归的方式，先访问当前节点，再依次访问相邻节点，直到所有节点都被访问。
BFS则通过队列的方式，先访问当前节点，再依次访问当前节点的相邻节点，直到所有节点都被访问。
实验结果：通过实验，我们成功实现了图的存储结构和基本操作，并且正确实现了DFS和BFS两种遍历算法。
我们对不同规模的图进行了测试，并分析了算法的时间复杂度。
实验结果表明，邻接矩阵的存储结构在添加和删除节点时的时间复杂度较高，而在查找节点和边时的时间复杂度较低。
DFS和BFS的时间复杂度都为O(V+E)，其中V表示节点数，E表示边数。
图形数据结构实验1. 实验目的通过本实验，使学生掌握图这种数据结构的基本概念和基本算法，提高编程能力，为后续课程学习和实际应用打下基础。
2. 实验环境•编程语言：Java•开发工具：Eclipse/IntelliJ IDEA•硬件环境：计算机3. 实验内容3.1 实验原理图是一种复杂的数据结构，用于表示元素之间的相互关系。
图由顶点（节点）集合和边集合组成。
图的表示方法有邻接矩阵和邻接表两种。
3.2 实验任务1.实现图的邻接矩阵表示法；2.实现图的邻接表表示法；3.实现图的深度优先搜索（DFS）算法；4.实现图的广度优先搜索（BFS）算法；5.实现图的最短路径算法（如Dijkstra算法）。
4. 实验步骤4.1 创建图类首先，创建一个图类，包含顶点（节点）和边的基本操作。
```javaclass Graph {private int numVertices; // 顶点数量private int[][] adjMatrix; // 邻接矩阵public Graph(int numVertices) {this.numVertices = numVertices;adjMatrix = new int[numVertices][numVertices]; // 省略其他方法...4.2 邻接矩阵表示法实现邻接矩阵的初始化、添加边、删除边等操作。
```java// 初始化邻接矩阵public void initAdjMatrix() {for (int i = 0; i < numVertices; i++) {for (int j = 0; j < numVertices; j++) {if (i == j) {adjMatrix[i][j] = 0;} else {adjMatrix[i][j] = INFINITY;public void addEdge(int v1, int v2) {adjMatrix[v1][v2] = 1;adjMatrix[v2][v1] = 1;public void removeEdge(int v1, int v2) {adjMatrix[v1][v2] = INFINITY;adjMatrix[v2][v1] = INFINITY;// 省略其他方法…4.3 邻接表表示法实现邻接表的初始化、添加边、删除边等操作。
哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：图形结构及其应用实验题目：图型结构的建立与遍历目录：目录： (2)一、实验目的 (3)二、实验要求及实验环境 (3)1.实验内容： (3)2.实验要求： (3)3.实验环境 (3)三、设计思想 (4)1．逻辑设计 (4)(1)邻接矩阵 (4)(2)邻接表 (4)(3)队列 (5)(4)队列堆栈 (5)2．物理设计 (6)(1)数据读入 (6)(2)广度优先搜索 (9)(3)深度优先搜索——递归实现 (12)(4)深度优先搜索——非递归实现 (14)四、测试结果 (17)初始化与图的读入 (17)展示邻接表读入结果 (17)展示邻接矩阵读入结果 (18)初始提示 (18)提示输入指令： (18)非法输入 (19)广度优先搜索 (19)深度优先搜索：二层选择 (19)-递归深度优先搜索 (20)-非递归深度优先搜索 (20)展示：二层选择 (20)-展示邻接表读入结果（同前） (20)-展示邻接矩阵读入结果（同前） (20)退出及退出确认 (21)五、系统不足与经验体会 (21)六、附录： (21)源代码：main.cpp (21)输入 (21)输出 (21)一、实验目的通过实现图形结构，掌握逻辑结构、储存结构及其应用。
二、实验要求及实验环境1.实验内容：树型结构的建立与遍历：图的遍历（搜索）算法是图型结构算法的基础，本实验要求编写程序演示图的存储结构的建立和遍历（搜索）过程。
2.实验要求：(1)能够建立（有向和无向）图的邻接矩阵和邻接表存储结构(2)能够在邻接矩阵和邻接表存储结构上对（有向和无向）图进行深度优先（递归和非递归都要求）和广度优先搜索(3)能够存储和显示相应的搜索结果（深度优先或广度优先生成森林（或生成树）、深度优先或广度优先序列和编号）(4)以文件形式输入图的顶点和边，并显示相应的结果。
要求顶点不少于10个，边不少于13个(5)软件功能结构安排合理，界面友好，便于使用3.实验环境Microsoft Windows7, Code：：Blocks 10.05三、设计思想1．逻辑设计(1)邻接矩阵一个|V|×|V|的二维数组AM，满足：AM[i][j]= 1，<i,j>是有向图的边0，<i,j>不是有向图的边(2)邻接表数据成员：基本操作：插入边：对图中的新有向边<i,j>，令i,节点对应链表插入一个j 广度优先搜索深度优先搜索（递归）深度优先搜索（非递归）(3)队列数据成员：头结点：指向队首，以方便操作。
基本操作：入队：将一个元素插入队首出队：从队尾取出一个元素(4)队列堆栈数据成员：头结点：每个头结点指向一个队列，只有堆栈顶层的头节点对应的队列才能进行出队、入队操作。
基本操作：入栈：头结点压入堆栈出栈：弹出头节点，对头节点对应队列进行操作2．物理设计(1)数据读入有向图以边序列的形式从文件输入，共有17个顶点，30条边：I.邻接表单元：邻接表的基本单位。
每个单位包含结点序号和下一单元的指针。
邻接表：包含一个单元数组和布尔数组。
单元数组中，每个单元代表单元序号对应的结点；每个单元都是一个链表的表头；这一链表储存的是头结点可到达的结点。
布尔数组中，每个元素代表其序号对应的结点，用于记录每个结点是否已被读取。
操作——增加边：对新的有向边<a,b>，将b插入邻接表中a作为头结点的链表。
II.邻接矩阵由于只是一个二维数组，因此其内容可在程序内直接调用、修改。
需要进行初始化。
III.读入函数为了方便，本程序同时将图读入邻接矩阵和邻接表。
(2)广度优先搜索I.邻接表上的广度优先搜索由于广度优先搜索要多次发起搜索，所以采用主从函数形式：Master：对布尔数组和搜索顺序数组进行初始化，并调用Servant进行广度优先搜索。
对每个未被从函数访问的结点，调用从函数，以其为根结点进行广度优先搜索。
把广度优先搜索结果输出到文件。
Servant：以输入结点为根结点，进行广度优先搜索。
将输入结点标记为已读，同时建立队列。
建立队列，以根据根结点为最初元素，每次出队一个元素，把这一结点可达而又未读过的结点添加到队列中，如此循环，直到队列清空。
II.邻接矩阵上的广度优先搜索沿用主从函数形式。
原理类似。
区别主要在于，每次读取根结点的可达点，依据的是邻接矩阵。
(3)深度优先搜索——递归实现I.邻接表实现Master：初始化相关记录数组，并启动从函数。
Servant：II.邻接矩阵实现Master：Servant：(4)深度优先搜索——非递归实现I.邻接表实现此处不使用真正的堆栈进行实现，而仅仅建立一个队列头结点数组。
对每个未被读取的结点，建立一个队列头结点“栈”，而将结点加入栈最底层的头节点对应的队列，然后开始下列循环：从栈最上层的头节点对应的队列中，取出队尾元素，并将向栈中压入一个新的队列头结点，将取出的其所有可达点加入队列中；如果发现队列已空而栈未空，则可以弹出栈顶队列头结点，从队列中取出一个元素，继续进行上述操作；如果队列、栈都已空，结束循环。
II.邻接矩阵实现原理与邻接表类似，只是读取数据时利用的是邻接矩阵而非邻接表。
四、测试结果初始化与图的读入展示邻接表读入结果展示邻接矩阵读入结果（节点个数过多，而窗口无法拉宽，故形成如此效果）初始提示提示输入指令：非法输入广度优先搜索深度优先搜索：二层选择-递归深度优先搜索-非递归深度优先搜索展示：二层选择-展示邻接表读入结果（同前）-展示邻接矩阵读入结果（同前）退出及退出确认五、系统不足与经验体会1.未建立图的生成树与生成森林；2.输出中，广度优先搜索队列、深度优先搜索队列（递归法）都没有体现图中存在两个连通分量；3.未实现对有向图的处理，事实上，对任意有向图，只要将每一条无向边分别用相反的两条有向边替换，就可以把有向图转换为无向图；4.运行程序时必须预先知道有向图图的节点、有向边的数目。
六、附录：源代码：main.cpp输入原图：Graph.txt输出图的矩阵储存：AjMatrix.txt图的邻接链表储存：AjList.txt广度优先搜索列表：ALBFSList.txt深度优先搜索列表（递归方式）：ALDFSRList.txt深度优先搜索列表（非递归方式）：ALDFSE.txtAjList.txt AjMatrix.txt ALBFSList.txt ALDFSRList.txt ALDSFE.txt Graph.txt main.cpp#include <iostream>#include <fstream>using namespace std;const int V_CARD = 17;const int E_CARD = 30;typedef int indx;struct ALUnit{indx numb;ALUnit *next;};class AjList{public:AjList(){indx i = 0;for(i = 0;i < V_CARD;i ++){unit[i].numb = 0;unit[i].next = NULL;read[i] = 0;}};~AjList(){indx i = 0;ALUnit *CurrUnit = NULL, *NextUnit = NULL;for(i = 0;i < V_CARD;i ++){CurrUnit = unit[i].next;delete &unit[i];while(CurrUnit != NULL){NextUnit = CurrUnit->next;delete CurrUnit;CurrUnit = NextUnit;}}};void InAL(indx InV0, indx InV1);void DisplayAL();void ALBFS_M();void ALBFS_S(indx CurrNode);void ALDFSR_M();void ALDFSR_S(indx CurrNode);void ALDFSE();private:ALUnit unit[V_CARD];bool read[V_CARD];int BFSList[V_CARD];indx BFSIndx;int DFSRList[V_CARD];indx DFSRIndx;};AjList AL;int AM[V_CARD][V_CARD];bool AMRead[V_CARD];void AMInnitial();void ReadGraph();void Selection();struct QNode{indx data;QNode *next;};class Queue{public:Queue(){head = new(QNode);head->data = 0;head->next = NULL;};~Queue(){if(head->next == NULL){delete head;}else{QNode* curr;do{curr = head->next;head->next = curr->next;delete curr;}while(head->next != NULL);delete head;}};void QIn(indx InData);indx QOut();bool IsEmpty(){if(head->next == NULL)return 1;else return 0;}void Display();private:QNode* head;};void Selection();void AMBFS_M();void AMBFS_S(indx CurrNode);void ALBFS();void AMDFSR_M();void AMDFSR_S(indx CurrNode);void AMDFSE();void AMDisplay();int main(){cout << "Hello world!" << endl;AMInnitial();cout << "Graph Innitialized." << endl;ReadGraph();cout << "Graph Loaded." << endl;cout << "Graph of Kirov_Tujin." << endl << "Orders:" << endl<< "B. Breadth first Search." << endl<< "D. Deepth first Search." << endl<< "P. Graph Display." << endl<< "Q. Quit the program." << endl;Selection();return 0;}void Selection(){bool Selecting = 1;char Order = 0;while(Selecting){cout << "Input your Order." << endl;cin >> Order;switch (Order){case 'B':{cout << "Breadth first Search." << endl;AMBFS_M();cout << "AMBFS Finished." << endl;AL.ALBFS_M();break;}case 'D':{cout << "Depth first Search." << endl<< ">R.Recursive Depth first Search." << endl<< ">E.Excursive Depth first Search." << endl;cout << ">Depth first Search:Input your Order." << endl;cin >> Order;switch (Order){case 'R':{cout << ">Recursive Depth first Search." << endl;AMDFSR_M();AL.ALDFSR_M();break;}case 'E':{cout << ">Excursive Depth first Search." << endl;AMDFSE();AL.ALDFSE();break;}}break;}case 'P':{cout << "Display." << endl// << ">M.Display Adjacency Matrix." << endl<< ">L.Display Adjacency List." << endl;cout << ">Display:Input your Order." << endl;cin >> Order;switch (Order){case 'M':{cout << ">M.Display Adjacency Matrix." << endl;AMDisplay();break;}case 'L':{cout << ">L.Display Adjacency List." << endl;AL.DisplayAL();break;}}break;cout << "Displaying." << endl;AL.DisplayAL();break;}case 'Q':{cout << "Quit?('Y' to Quit.)" << endl;cin >> Order;if(Order == 'Y'){Selecting = 0;}break;}default :{cout << "Illegal Input." << endl;}}}cout << "Selection ended." << endl;return;}void Queue :: QIn(indx InData){QNode* InNode = new(QNode);InNode->data = InData;InNode->next = head->next;head->next = InNode;return;}indx Queue :: QOut(){QNode *curr, *tran, *form;form = NULL;curr = head;tran = curr->next;while(tran != NULL){form = curr;curr = tran;tran = curr->next;}if(form == NULL){cout << "Empty List." << endl;return NULL;}indx OutData;OutData = curr->data;delete curr;form->next = NULL;return OutData;}void Queue :: Display(){QNode *curr, *tran;curr = head;tran = curr->next;while(tran != NULL){cout << curr->data;curr = tran;tran = curr->next;}cout << curr->data << endl;return;}void AjList :: InAL(indx InV0, indx InV1){ALUnit *InUnit = new(ALUnit);InUnit->numb = InV1;InUnit->next = NULL;ALUnit *CurrUnit = NULL, *NextUnit = NULL;CurrUnit = &unit[InV0];NextUnit = CurrUnit->next;while(NextUnit != NULL){CurrUnit = NextUnit;NextUnit = CurrUnit->next;}CurrUnit->next = InUnit;return;}void AjList :: DisplayAL(){indx i = 0;ofstream Out_File("AjList.txt");ALUnit *CurrUnit = NULL, *NextUnit = NULL;for(i = 0;i < V_CARD;i ++){cout << i << "->";Out_File << i << "->";CurrUnit = &unit[i];NextUnit = CurrUnit->next;while(NextUnit != NULL){CurrUnit = NextUnit;NextUnit = CurrUnit->next;cout << CurrUnit->numb << ',';Out_File << CurrUnit->numb << ',';}cout << '#' << endl;Out_File << '#' << endl;}Out_File.close();return;}void AjList :: ALBFS_M(){int i = 0;for(i = 0;i < V_CARD;i ++){BFSList[i] = 0;read[i] = 0;}for(i = 0;i < V_CARD;i ++){if(read[i] == 0){ALBFS_S(i);cout << '#' << endl;}}// ofstream OUT_FILE("ALBFSList.txt");for(i = 0;i < V_CARD;i ++){OUT_FILE << BFSList[i] << ',';}OUT_FILE << '#';OUT_FILE.close();return;}void AjList :: ALBFS_S(indx CurrNode){cout << "ALBFS_Servant on." << endl;Queue Q1;Q1.QIn(CurrNode);read[CurrNode] = 1;cout << '>';while(Q1.IsEmpty() != 1){CurrNode = Q1.QOut();cout << CurrNode << '-';BFSList[BFSIndx] = CurrNode;BFSIndx++;ALUnit *NextPTR = NULL, *CurrPTR = NULL;CurrPTR = &unit[CurrNode];NextPTR = unit[CurrNode].next;while(NextPTR != NULL){CurrPTR = NextPTR;if(read[CurrPTR->numb] != 1){Q1.QIn(CurrPTR->numb);read[CurrPTR->numb] = 1;}NextPTR = CurrPTR->next;}}return;}void AjList :: ALDFSR_M(){cout << "ALDFSR_Master on." << endl;int i = 0;for(i = 0;i < V_CARD;i ++){DFSRList[i] = 0;read[i] = 0;}for(i = 0;i < V_CARD;i ++){if(read[i] == 0){cout << '>' << i;ALDFSR_S(i);cout << '#' << endl;}}// ofstream OUT_FILE("ALDFSRList.txt");for(i = 0;i < V_CARD;i ++){OUT_FILE << DFSRList[i] << ',';}OUT_FILE << '#';OUT_FILE.close();return;}void AjList :: ALDFSR_S(indx CurrNode){ALUnit *NextPTR = NULL, *CurrPTR = NULL;CurrPTR = &unit[CurrNode];NextPTR = unit[CurrNode].next;read[CurrNode] = 1;DFSRList[DFSRIndx] = CurrNode;DFSRIndx ++;while(NextPTR != NULL){CurrPTR = NextPTR;if(read[CurrPTR->numb] == 0){cout << '-' << CurrPTR->numb;ALDFSR_S(CurrPTR->numb);read[CurrPTR->numb] = 1;}NextPTR = CurrPTR->next;}return;}void AjList :: ALDFSE(){indx i = 0;for(i = 0;i < V_CARD;i ++){read[i] = 0;}ofstream OUT_File("ALDSFE.txt");for(i = 0;i < V_CARD;i ++){if(read[i] == 0){cout << '>';OUT_File << '>';Queue Q2[V_CARD];indx QFlag = 0;Q2[QFlag].QIn(i);indx CurrUnit;while((Q2[QFlag].IsEmpty() == 0)||(QFlag > 0)){if(Q2[QFlag].IsEmpty() == 0){CurrUnit = Q2[QFlag].QOut();if(read[CurrUnit] == 0){cout << CurrUnit << '-';OUT_File << CurrUnit << '-';read[CurrUnit] = 1;QFlag ++;ALUnit *CurrPTR = NULL, *NextPTR = NULL;CurrPTR = &unit[CurrUnit];NextPTR = CurrPTR->next;while(NextPTR != NULL){CurrPTR = NextPTR;if(read[CurrPTR->numb] == 0){Q2[QFlag].QIn(CurrPTR->numb);}NextPTR = CurrPTR->next;}}}else{QFlag--;}}cout << '#' << endl;OUT_File << '#' << endl;}}OUT_File.close();return;}void ReadGraph(){fstream InFile("Graph.txt");cout << "Read Graph:Graph opened." << endl;int i = 0;int CurrEdge[2];char space = 0;for(i = 0;i < E_CARD;i ++){InFile >> CurrEdge[0] >> space >> CurrEdge[1];AL.InAL(CurrEdge[0]-1,CurrEdge[1]-1);AM[CurrEdge[0]-1][CurrEdge[1]-1] = 1;}cout << "Read Graph:Graph loaded." << endl;AL.DisplayAL();ofstream Out_File_1_2("AjMatrix.txt");for(i = 0;i < V_CARD;i ++){for(int j = 0;j < V_CARD;j ++){cout << "\t" << AM[i][j];Out_File_1_2 << "\t" << AM[i][j];}cout << endl << endl;Out_File_1_2 << endl << endl;}Out_File_1_2.close();return;}void AMInnitial(){int i = 0, j = 0;for(i = 0;i < V_CARD;i ++){AMRead[i] = 0;for(j = 0;j <V_CARD;j ++){AM[i][j] = 0;}}return;}void AMBFS_M(){indx i = 0;for(i = 0;i < V_CARD;i ++){AMRead[i] = 0;}for(i = 0;i < V_CARD;i ++){if(AMRead[i] == 0){AMBFS_S(i);cout << '#' << endl;}}return;}void AMBFS_S(indx CurrNode){cout << "AMBFS_Servant on." << endl;Queue Q1;Q1.QIn(CurrNode);AMRead[CurrNode] = 1;cout << '>';while(Q1.IsEmpty() != 1){CurrNode = Q1.QOut();cout << CurrNode << '-';indx j = 0;for(j = 0;j < V_CARD;j ++){if((AM[CurrNode][j] == 1)&&(AMRead[j] == 0)){Q1.QIn(j);AMRead[j] = 1;}}}return;}void AMDFSR_M(){cout << "AMDFSR_Master on." << endl;indx i = 0;for(i = 0;i < V_CARD;i ++){AMRead[i] = 0;}for(i = 0;i < V_CARD;i ++){if(AMRead[i] == 0){cout << '>';AMDFSR_S(i);cout << '#' << endl;}}return;}void AMDFSR_S(indx CurrNode){AMRead[CurrNode] = 1;cout << CurrNode << '-';indx j = 0;for(j = 0;j < V_CARD;j ++){if((AM[CurrNode][j] == 1)&&(AMRead[j] == 0)){AMDFSR_S(j);AMRead[j] = 1;}}return;}void AMDFSE(){indx i = 0;for(i = 0;i < V_CARD;i ++){AMRead[i] = 0;}for(i = 0;i < V_CARD;i ++){if(AMRead[i] == 0){cout << '>';Queue Q2[V_CARD];indx QFlag = 0;Q2[QFlag].QIn(i);indx CurrUnit;while((Q2[QFlag].IsEmpty() == 0)||(QFlag > 0)){if(Q2[QFlag].IsEmpty() == 0){CurrUnit = Q2[QFlag].QOut();if(AMRead[CurrUnit] == 0){cout << CurrUnit << '-';AMRead[CurrUnit] = 1;QFlag ++;indx j = 0;for(j = 0;j < V_CARD;j ++){if((AMRead[j] == 0)&&(AM[CurrUnit][j] == 1)){Q2[QFlag].QIn(j);}}}}else{QFlag--;}}cout << '#' << endl;}}return;}void AMDisplay(){indx i = 0, j = 0;for(i = 0;i < V_CARD;i ++){for(j = 0;j < V_CARD;j ++){cout << "\t" << AM[i][j];}cout << endl << endl;}return;}。
