《数据结构与算法分析》课程实验报告六图

于立伟

1025人浏览 · 2025-07-06 00:16:53

于立伟 · 2025-07-06 00:16:53 发布

目录

三、实验内容（实验方案、实验步骤、设计思路）

一、实验目的及要求

1.实验目的

1）掌握无向图和有向图的概念、抽象数据类型和特点，掌握无向图和有向图的链式存储结构的存储思想及其程序实现，掌握无向图和有向图对应存储结构的基本操作。

2）掌握无向图的初始化、创建、深度优先遍历、广度优先遍历等算法实现。

3）掌握有向图的初始化、创建、深度优先遍历、广度优先遍历等算法实现。

2.实验要求

1）熟悉无向图和有向图的链式储存结构。

2）上机过程中要遵守实验室的各项规章制度,爱护实验设备，保持环境卫生。

3）本课程的实验过程中，不得进行游戏、上网等操作。

二、实验环境（工具、配置等）

1.硬件要求：笔记本电脑一台。

2.软件要求：Windows11操作系统，编译环境Dev-Cpp。

3.数据结构与算法分析，使用C++语言。

三、实验内容（实验方案、实验步骤、设计思路）

1.实验方案

结合课本中算法知识以及老师上课所讲知识进行灵活运用，编写代码实现无向图和有向图的相关功能并进行测试和相应的修改和完善。

2.实验步骤

1）认真分析课本上无向图和有向图相关功能的算法，将书上的伪代码翻译成C++语言的源代码进行测试。

2）认真学习老师上课所讲知识，将知识运用到实践中，对自己的代码进行修改与完善。

3）成功通过代码对无向图和有向图的相关功能进行实现。

4）完成图的实验报告并进行提交。

3.设计思路

1）定义无向图的基本结构类型。

2）对无向图实现链式存储并进行无向图的相关操作。

3）通过函数实现对无向图的初始化、创建等基本功能。

4）通过创建后的无向图完成对无向图的深度优先遍历、广度优先遍历等高级操作。

5）有向图的相关功能的实现如上无向图的实现过程相似。

6）通过主函数调用各函数进行功能的实现。

四、实验结果与分析

1.使用Dev-Cpp编写无向图，并编译运行进行相关功能的实现，如图4-1：

图4-1 无向图相关功能实现的输出结果

2.使用Dev-Cpp编写有向图，并编译运行进行相关功能的实现，如图4-2：

图4-2 有向图相关功能实现的输出结果

1、实验分析

1）编译错误：“error C2057: expected constant expression”

解决方法：定义数组时数组长度为变量，将常量改为变量即可。

2）编译错误：“error C2078: too many initializers”

解决方法：数组初始化时初始值的个数大于数组长度，将数组长度扩大即可。

3）编译错误：”error C2086: 'xxx' : redefinition“

解决方法：变量名、数组名重名，将变量名或数组名中的一个进行修改即可。

4）编译错误：“error C2100: illegal indirection”

解决方法：对非指针变量使用“*”运算，将其变量修改为指针即可。

5）出现的问题：内存分配未成功。

解决方法：使用内存之前先检查指针是否为空（NULL）。

6）出现的问题：内存虽然分配成功，但是还没有初始化就进行了使用。

解决方法：在创建后数组之后，要进行赋初值，即使是零也不能省略。

7）出现的问题：未释放空间，造成内存泄露。

解决方法：动态开辟的内存要让申请和释放进行配对。

8）出现的问题截图：

解决方法：由于setw()函数是头文件<iomanip>中的，所以在代码头部加入头文件#include<iomanip>后错误消失。

9）出现的问题截图：

解决方法：在编写代码时由于少打了一个右括号而导致错误，将代码中的右括号补全后错误消失。

10）出现的问题截图：

解决方法：由于编写代码时少写了一个;所致，添加;后错误消失。

11）出现的问题截图：

解决方法：由于在书写代码时时常存在中英文互换的情况，所以在使用一些符号时会出现错误，在写分号时将英文版写成了中文版所致，改正后错误消失。

12）出现的问题截图：

解决方法：在调用函数时由于需要在函数中传参，而往往参数不止一个，各个参数之间需要用英文逗号进行分隔，而到最后一个参数时则不需要再用逗号分隔，正是由于这样才导致错误，所以将最后一个参数后多加的一个逗号删除后错误消失。

13）出现的问题截图：

解决方法：由于在调用函数时需要在函数中传参，而往往参数不止一个，需要将参数传入函数之中，此处便是由于参数传入不完全所导致的，将需要的参数个数传入后错误消失。

14）出现的问题截图：

解决方法：由于使用cout时有以下两种“cout<<” ”<<endl;”和“cout<<” “;”，第一种是输出以后直接换行，而第二种是输出后继续在末端进行输出，而导致此错误的便是由于第一种使用时未加endl后直接使用，添加后错误消失。

15）出现的问题截图：

解决方法：由于在使用if语句时需要在if后的圆括号内填入判断条件，正是由于这样所致，在if后的圆括号内填入判断条件后错误消失。

16）出现的问题截图：

解决方法：由于在C++中每一个变量需要先声明后使用，而在编写代码时由于未声明变量p而导致错误，在函数内声明后错误消失。

17）出现的问题截图：

解决方法：由于在实现二叉树遍历的过程中，使用了栈进行了相关的操作，但是没有加入栈的头文件，所以在运行过程中出现了错误，加入头文件<stack>后错误消失。

18）出现的问题截图：

解决方法：由于函数的返回类型是int类型的，所以在函数内必须要返回一个值，如果不需要返回值则直接设置为void类型即可。

19）出现的问题截图：

解决方法：由于void函数不需要返回值，所以将返回类型改为基本数据类型即可。

20）出现的问题截图：

解决方法：Bi为一个指针，因此在使用时应该用->进行相关变量的调用，而不是用.进行调用。

21）出现的问题截图：

解决方法：在使用一些变量时一定是先声明后使用，而在此处未声明前就使用了变量front。

22）出现的问题截图：

解决方法：在头文件处的using namespace std后面的分号未加所导致，进行修改后错误消失。

2、心得体会

1）定义指针之后必须赋值，然后才可以引用。

2）指针赋初值时a.在定义指针的同时进行初始化赋值b.在定义之后单独使用赋值语句。

3）任何类型的指针都可以赋值给void类型的指针变量。

4）用new申请内存之后，因立即检查指针值是否为NULL，防止使用指针值为NULL的内存。

5）避免数字或指针的下标越界，特别要当心发生“多1”或者“少1”操作。

6）动态内存的申请与释放必须配对，防止内存泄漏。

7）用delete释放内存之后，立即将指针设置为NULL，防止“野指针”。

8）在编写代码时切记符号的正确使用，特别时在中英文转换时，由于自己的一个粗心导致中英文混用而出错。

9）在编写代码时如果需要使用一些头文件内的信息，在使用前一定要加头文件。

10）在进行无向图和有向图的数据输入时两者是不一样的，首先无向图里的连线叫边，而有向图里的连线叫弧，在对有向图进行数据输入时起点是非箭头的端点信息，终点是箭头的指向端点信息，如果端点信息只有入或者出时根据相关信息对其进行置空操作。对无向图进行数据输入时进行一层一层按顺序输入，最好按从左往右、从上往下、从小到大的顺序进行输入，这样在输入第二层和后续层次信息时在尾部要放入上一层与之建立联系的顶点信息，并将下一个链接域置空即可。

11）无向图和有向图的存入方式是不同的。

五、附源程序

无向图的相关操作的实现代码（无向图的初始化、创建、深度优先遍历、广度优先遍历等基本操作）

#include <iostream>
#include <iomanip>

#define MAXVERTEXNUMBER 100//顶点的最大数量
enum BOOL {FALSE, TRUE};
BOOL V[MAXVERTEXNUMBER];//标志访问数组
using namespace std;

//无向图边的结构体
typedef struct ArcNode {
	int adjvex;//该边所指向的顶点的位置
	struct ArcNode *nextarc;//指向下一条边的指针
} ArcNode;

//无向图的结构体
typedef struct {
	ArcNode *AdjList[MAXVERTEXNUMBER];//指向第一条依附该顶点的边的指针
	int vexnum;//无向图的当前顶点数
	int arcnum;//无向图的当前边数
} Graph;

//队列的结构体
typedef struct  {
	int data[MAXVERTEXNUMBER];//数据域
	int front;//队头元素
	int rear;//队尾元素
} SqQueue;

//创建无向图
void Creategraph(Graph &G) {
	int i, first, second;
	cout << "请输入无向图的顶点数目为：";
	cin >> G.vexnum;
	cout << "请输入无向图的边数量为：";
	cin >> G.arcnum;
	ArcNode *p;
	for (i = 1; i <= G.vexnum; i++) {
		G.AdjList[i] = NULL; //初始化指针数组
	}
	if (G.arcnum == 0) {
		cout << "此无向图无边！" << endl;
	} else {
		for (i = 1; i <= G.arcnum; i++) {
			cout << "请输入第" << i << "条边的第一个顶点为：";
			cin >> first;
			cout << "请输入第" << i << "条边的第二个顶点为：";
			cin >> second;
			p = new ArcNode; //生成一条边结点
			p->nextarc = G.AdjList[first]; //第一个顶点插入邻接表
			p->adjvex = second;
			G.AdjList[first] = p;
			{
				p = new ArcNode;
				p->nextarc = G.AdjList[second];//第二个顶点插入邻接表
				p->adjvex = first;
				G.AdjList[second] = p;
			}
		}
	}
}

//在无向图中寻找第i个顶点的第一个邻接顶点
int Firstadjvex(Graph &G, int i) {
	if (!G.AdjList[i])
		return 0;
	else
		return G.AdjList[i]->adjvex;
}

//在无向图中寻找第i个顶点相对于w的下一个邻接顶点
int Secondadjvex(Graph &G, int i, int w) {
	ArcNode *p;
	p = G.AdjList[i];
	while (p->adjvex != w)
		p = p->nextarc;
	if (p->nextarc == NULL) //到最后一个顶点时返回0
		return 0;
	else
		return p->nextarc->adjvex;//返回下一个邻接点的序号
}

//无向图的深度优先遍历
void DFS(Graph &G, int i) {
	int w;
	V[i] = TRUE; //访问第i个顶点
	cout << i << setw(5);
	for (w = Firstadjvex(G, i); w > 0; w = Secondadjvex(G, i, w)) {
		if (!V[w])
			DFS(G, w);
	}
}

void DFSTraverse(Graph &G) {
	int i;
	cout << "无向图的深度优先遍历结果为：" << endl;
	for (i = 1; i <= G.vexnum; i++) {
		V[i] = FALSE; //访问标志数组的初始化
	}
	for (i = 1; i <= G.vexnum; i++) {
		if (!V[i])
			DFS(G, i);
	}
}

//队列的初始化
void Initqueue(SqQueue &Q) {
	Q.front = Q.rear = 0;
}

//队列的判空
BOOL Emptyqueue(SqQueue &Q) {
	if (Q.front == Q.rear)
		return TRUE;
	else
		return FALSE;
}

//进行入队操作
BOOL Inqueue(SqQueue &Q, int i) {
	if ((Q.rear + 1) % MAXVERTEXNUMBER == Q.front)
		return FALSE;
	Q.data[Q.rear] = i;
	Q.rear = (Q.rear + 1) % MAXVERTEXNUMBER;
	return TRUE;
}

//进行出队操作
BOOL Outqueue(SqQueue &Q, int &i) {
	if (Q.front == Q.rear)
		return FALSE;
	i = Q.data[Q.front];
	Q.front = (Q.front + 1) % MAXVERTEXNUMBER;
	return TRUE;
}

//无向图的广度优先搜索
void BFSTraverse(Graph &G) {
	int i, x, w;
	SqQueue Q;
	cout << "无向图的广度优先搜索结果为：" << endl;
	for (i = 1; i <= G.vexnum; i++) {
		V[i] = FALSE; //访问标志数组初始化
	}
	Initqueue(Q);
	for (i = 1; i <= G.vexnum; i++)
		if (!V[i]) {
			V[i] = TRUE;
			cout << i << setw(5);
			Inqueue(Q, i);
			while (!Emptyqueue(Q)) {
				Outqueue(Q, x);
				for (w = Firstadjvex(G, x); w > 0; w = Secondadjvex(G, x, w))
					if (!V[w]) {
						V[w] = TRUE;
						cout << w << setw(5);
						Inqueue(Q, w);
					}
			}
		}
}

int main() {
	//无向图的初始化
	Graph G;
	//无向图的创建
	cout << "进行无向图相关信息的输入！" << endl;
	cout << endl;
	Creategraph(G);
	cout << endl;
	//无向图的深度优先遍历
	DFSTraverse(G);
	cout << endl;
	//无向图的广度优先搜索
	BFSTraverse(G);
	return 0;
}

有向图的相关操作的实现代码（有向图的初始化、创建、深度优先遍历、广度优先遍历等基本操作）

#include <iostream>
#include <iomanip>
#define MAXVERTEXNUMBER 100//顶点的最大数量
#define ERROR -1
#define OK 1
using namespace std;

//有向图弧的结构体
typedef struct ArcNode {
	int adjvex;//该弧所指向的顶点的位置
	struct ArcNode *nextarc;//指向下一条弧的指针
	int *info;//该弧相关信息的指针
} ArcNode;

//有向图的顶点结构体
typedef struct VNode {
	int data;//顶点信息
	ArcNode *firstarc;//指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAXVERTEXNUMBER];

//有向图的结构体
typedef struct {
	AdjList vertices;//顶点
	int vexnum;//有向图的当前顶点数
	int arcnum;//有向图的当前弧数
} ALGraph;

//队列的结构体
struct SqQueue {
	int *base;//动态分配存储空间
	int front;//头指针
	int rear;//尾指针
};

//确定有向图中v在G中的位置（顶点在G.vertices中的序号）
int Locatevex(ALGraph &G, int v) {
	for (int i = 0; i < G.vexnum; i++) {
		if (G.vertices[i].data == v)
			return i;
	}
	return ERROR;
}

//有向图G的存储结构（邻接表）
void Creategraph(ALGraph &G) {
	int sv, tv, i, j; //有向图弧的始点和终点
	cout << "请输入有向图的顶点数目为：";
	cin >> G.vexnum;
	cout << endl;
	cout << "请输入有向图的弧数量为：";
	cin >> G.arcnum;
	cout << endl;
	//构造顶点的数组
	for (int k = 0; k < G.vexnum; k++) {
		cout << "请输入有向图的第" << k + 1 << "个顶点信息为";
		//输入顶点信息
		cin >> G.vertices[k].data;
		//初始化链表的头指针为空
		G.vertices[k].firstarc = NULL;
	}
	cout << endl;
	cout << "请输入有向图的弧的相关信息！" << endl;
	for (int k = 0; k < G.arcnum; k++) {
		cout << "请输入第" << k + 1 << "条弧的始点为：";
		cin >> sv;
		cout << "请输入第" << k + 1 << "条弧的终点为：";
		cin >> tv;
		cout << endl;
		//sv在G中的位置
		i = Locatevex(G, sv);
		//tv在G中的位置
		j = Locatevex(G, tv);
		ArcNode *p;
		p = new ArcNode;
		if (!p) {
			cout << "动态创建失败！" << endl;
		}
		p->adjvex = j; //给弧结点赋邻接点的位置
		//头插法
		p->nextarc = G.vertices[i].firstarc; //将tv结点插入到第i个单链表中
		p->info = NULL;
		G.vertices[i].firstarc = p;
	}
}

//有向图的深度优先搜索
void DFS(ALGraph &G, int v, int V[]) {
	int w;//v的下一个邻接点的位置
	ArcNode *p;
	cout << G.vertices[v].data << setw(5);
	V[v] = 1;
	p = G.vertices[v].firstarc;
	if (p != NULL) {
		w = p->adjvex;
		if (V[w] == 0) { //w未被访问
			DFS(G, w, V);
		} else {
			//访问v的下一个邻接点，并判断该邻接点是否存在
			p = p->nextarc;
			if (p != NULL)
				w = p->adjvex;
		}
	}
}

void DFSTraverse(ALGraph &G) {
	int v, V[MAXVERTEXNUMBER];
	for (v = 0; v < G.vexnum; v++) {
		V[v] = 0;
	}
	for (v = 0; v < G.vexnum; v++) {
		if (V[v] == 0) {
			DFS(G, v, V);
		}
	}
}

//构建一个辅助队列
int Initqueue(SqQueue &Q) {
	//构建一个空队列
	Q.base = new int[MAXVERTEXNUMBER];
	if (!Q.base) {
		cout << "内存开辟失败！" << endl;
		return ERROR;
	}
	Q.front = Q.rear = 0;
	return OK;
}

//队列中元素的插入
int Inqueue(SqQueue &Q, int x) {
	//判满
	if ((Q.rear + 1) % MAXVERTEXNUMBER == Q.front) {
		cout << "该队列已满，请重新创建！" << endl;
		return ERROR;
	}
	Q.base[Q.rear] = x;
	Q.rear = (Q.rear + 1) % MAXVERTEXNUMBER;
	return OK;
}

//队列的判空
int Emptyqueue(SqQueue &Q) {
	if (Q.front == Q.rear)
		return 1;
	else
		return 0;
}

//队列元素的出队
int Outqueue(SqQueue &Q, int x) {
	if (Emptyqueue(Q)) {
		cout << "该队列为空，无元素可以出队！" << endl;
		return ERROR;
	}
	x = Q.base[Q.front];
	Q.front = (Q.front + 1) % MAXVERTEXNUMBER;
	return x;
}

//有向图的广度优先搜索
void BFS(ALGraph G, int v, int V[], SqQueue &Q) {
	int x, w;
	ArcNode *p;
	cout << G.vertices[v].data << setw(5);
	V[v] = 1;
	Inqueue(Q, v); //v的入队
	while (!Emptyqueue(Q)) {
		Outqueue(Q, x); //队头元素出队
		p = G.vertices[v].firstarc;
		if (p != NULL) {
			w = p->adjvex;
		}
		for (; p != NULL;) {
			if (V[w] == 0) {
				cout << G.vertices[w].data << setw(5);
				V[w] = 1;
				Inqueue(Q, w); //元素入队
			}
			p = p->nextarc;
			if (p != NULL)
				w = p->adjvex;
		}
	}
}

void BFSTraverse(ALGraph G) {
	SqQueue Q;
	int v, V[MAXVERTEXNUMBER];
	for (v = 0; v < G.vexnum; v++) {
		V[v] = 0; //初始化访问标志
	}
	Initqueue(Q);//辅助队列
	for (v = 0; v < G.vexnum; v++) {
		if (V[v] == 0) { //v未访问
			BFS(G, v, V, Q);
		}
	}
}

int main() {
	//有向图的初始化
	ALGraph G;
	//有向图的创建
	cout << "进行有向图的相关信息的输入！" << endl;
	cout << endl;
	Creategraph(G);
	cout << endl;
	//有向图的深度优先搜索
	cout << "有向图的深度优先搜索为：" << endl;
	DFSTraverse(G);
	cout << endl;
	//有向图的广度优先搜索
	cout << "有向图的广度优先搜索为：" << endl;
	BFSTraverse(G);
	return 0;
}

乐奇 Rokid 开放社区

更多推荐

从对话到行动：用 AIUI 构建「意图驱动」的隐形界面——「言值」AI 表达教练开发实录

我观察到一个现象：身边准备面试和答辩的人，练表达的方式几乎只有三种——看面经、背稿子、对着手机录像回看。练习的时候，你可以低头看屏幕。面试时，你要看着对方的眼睛；答辩时，你要看着评委；路演时，你要站定、看着观众；即兴发言时，你连手机都来不及掏。只要一低头，眼神、体态、气场全散了；而双手被手机占住，练习本身也就失真了。更麻烦的是反馈。练完之后，大多数人只知道「我好像说得不太好」，但不知道下一句该怎么