本科课程【数据结构与算法】实验5 - 广度优先搜索、二叉排序树的构造

文章目录

一、实验目的二、实验内容

1. 实验任务2. 程序设计三、实验环境源代码（C++实现）

图的广度优先搜索二叉排序树BFS的构造

大家好，我是【1+1=王】，热爱java的计算机（人工智能）渣硕研究生在读。
如果你也对java、人工智能等技术感兴趣，欢迎关注，抱团交流进大厂！！！
Good better best, never let it rest, until good is better, and better best.

近期会把自己本科阶段的一些课程设计、实验报告等分享出来，供大家参考，希望对大家有帮助。

博客更新至专栏【课程设计实验报告】：https://blog.csdn.net/weixin_43598687/category_11640051.html

一、实验目的

掌握图的邻接表存储结构实现图的广度优先搜索掌握二叉排序树的链式存储结构实现二叉排序树的构造二、实验内容 1. 实验任务

（1）建立一个无向连通图，用广度优先搜索（BFS）遍历
（2）输入一串数字，建立二叉排序树

2. 程序设计

1）数据输入（输入哪些数据、个数、类型、来源、输入方式）
无向图的顶点数据（data）char字符型；
无向图的边关系（v1,v2）int 整型；
各边的权值（w）int 整型

二叉树的结点关键数（key）int整型

2）数据存储（输入数据在内存中的存储）
采用new方法动态分配空间，以邻接表存储

采用new 动态分配空间，储存在*BinSearchTree中
3）数据处理（说明处理步骤。若不是非常简单，需要绘制流程图）

①建立邻接表储存无向图
输入总顶点数和总边数；
建立顶点表（依次输入点的信息存入顶点表中，使每个表头节点的指针域初始化NULL）
创建邻接表（依次输入每条边依附的两个顶点，确定两个顶点的序号i和j，建立边节点，将此边节点分别插入到vi和vj对应的两个边链表的头部）
②BFS广度优先遍历
从某一顶点出发，首先依次访问该顶点的所有邻接节点，再依次访问该节点邻接节点的所有临街节点，直到所有节点被访问

①输入第一个数为根节点，之后输入的数如果小则做为左孩子（lchild）,大则做为右孩子直到输入为-1，结束构造
②在二叉树中查找关键数key时，若二叉树T=NULL，查找失败；
若key=T->data.key，查找成功；
若keydata.key，则查找T所在节点的左子树；
若key>T->data.key，则查找T所在节点的右子树

4）数据输出（贴图：程序运行结果截图。图幅大小适当，不能太大）

三、实验环境

操作系统：WINDOWS 10开发工具：VC++ 2013实验设备：PC 源代码（C++实现）图的广度优先搜索

#include
#include 
using namespace std;

#define MaxVerNum 100
#define MAX_QUEUE_LENGTH 100
bool visited[MaxVerNum];

typedef char VertexType;

typedef struct VNode
{
	VertexType data;
	ArcNode * firstarc;
}VNode,AdjList[MaxVerNum];

typedef struct ArcNode
{
	int adjvex;
	struct ArcNode * nextarc;
	int info;
}ArcNode;

typedef struct
{
	AdjList vertices;
	int vexnum, arcnum;
}ALGraph;

#define MAX_QUEUE_LENGTH 64 	// 队列最大长度

// 环形队列
typedef struct Queue{
	int buffer[MAX_QUEUE_LENGTH];	// 队列缓冲区
	int begin;		// 开始位置
	int end;		// 结束位置
	int length;		// 队列长度
}Queue;

void CreateALGraph(ALGraph &G);
int LocateVex(ALGraph G, VertexType v);
int NextAdjVex(ALGraph G, int u, int w);

void InitQueue(Queue* pQ);
int EnQueue(Queue* pQ, int Elem);
int DeQueue(Queue* pQ);
int QueueEmpty(Queue* pQ);

void BFS(ALGraph G, int v);

int main()
{
	int n;
	cin >> n;
	ALGraph graph;
	CreateALGraph(graph);
	BFS(graph, n);

	system("pause");
	return 0;
}


void CreateALGraph(ALGraph &G)
{
	int i, j, k;
	VertexType v1, v2;
	cout << "输入顶点数和边数：" << endl;
	cin >> G.vexnum >> G.arcnum;
	cout << "输入顶点数据：" << endl;
	for (i = 0; i < G.vexnum; i++)
	{
		cin >> G.vertices[i].data;
		G.vertices[i].firstarc = NULL;
	}
	cout << "输入各边关系：" << endl;
	for (k = 0; k < G.arcnum; k++)
	{
		cin >> v1 >> v2;
		i = LocateVex(G, v1);
		j = LocateVex(G, v2);

		ArcNode *p1 = new ArcNode;
		p1->adjvex = j;
		p1->nextarc = G.vertices[i].firstarc;
		G.vertices[i].firstarc = p1;
		ArcNode *p2 = new ArcNode;
		p1->adjvex = i;
		p1->nextarc = G.vertices[j].firstarc;
		G.vertices[j].firstarc = p2;
	}
}

int LocateVex(ALGraph G, VertexType v)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		if (v == G.vertices[i].data)
			return i;
		return -1;
	}
}


void InitQueue(Queue* pQ)
{
	pQ->begin = pQ->end = 0;
	pQ->length = 0;
}


int EnQueue(Queue* pQ, int Elem)
{
	//
	// 队列满，入队失败。
	//
	if (MAX_QUEUE_LENGTH == pQ->length)
		return -1;

	pQ->buffer[pQ->end] = Elem;
	pQ->end = (pQ->end + 1) % MAX_QUEUE_LENGTH;
	pQ->length++;

	return Elem;
}


int DeQueue(Queue* pQ, int Elem)
{

	//
	// 队列空，出队失败
	//	
	if (QueueEmpty(pQ))
		return -1;

	Elem = pQ->buffer[pQ->begin];
	pQ->begin = (pQ->begin + 1) % MAX_QUEUE_LENGTH;
	pQ->length--;

	return Elem;
}


int QueueEmpty(Queue* pQ)
{
	return 0 == pQ->length ? 1 : 0;
}


void BFS(ALGraph G, int v)
{
	for (int i = 0; i < G.vexnum; i++)
	{
		visited[i] = false;
	}
	cout << v;
	visited[v] = true;
	Queue* Q;
	InitQueue(Q);
	EnQueue(Q, v);
	int u;
	while (!QueueEmpty(Q))
	{
		DeQueue(Q,u);
		for (int w = v; w >= 0; w = NextAdjVex(G, u, w))
		{
			if (!visited[w])
			{
				cout << w;
				visited[w] = true;
				EnQueue(Q, w);
			}
		}
	}
}


int NextAdjVex(ALGraph G, int u, int w)
{
	ArcNode *p;
	p->adjvex = u;
	w = p->nextarc->adjvex;
}

二叉排序树BFS的构造

#include

using namespace std;

typedef int KeyType;		// 关键码字段类型

typedef struct BinSearchNode{
	KeyType Key;						// 节点的关键码字段
	struct BinSearchNode* lchild;		// 左孩子指针
	struct BinSearchNode* rchild;		// 右孩子指针
}BinSearchNode, *BinSearchTree;

bool Tree_Search(BinSearchTree T, KeyType key);
BinSearchTree Tree_Insert(BinSearchTree T, int key);
BinSearchTree Create(BinSearchTree T);
void MiddleTravel(BinSearchTree);

int main()
{
	BinSearchTree pTree=NULL; // 二叉排序树指针
	Create(pTree);
	MiddleTravel(pTree);

	system("pause");
	return 0;
}

bool Tree_Search(BinSearchTree T, KeyType key)
{
	BinSearchTree p;
	p = T;
	while (p)
	{
		if (key == p->Key)
			return true;
		else
			p = (key < p->Key) ? (p->lchild) : (p->rchild);
	}
	return false;
}



BinSearchTree Tree_Insert(BinSearchTree T, int key)
{
	BinSearchTree p=T;
	BinSearchTree f=NULL, s;
	while (p != NULL)
	{
		f = p;
		if (key == p->Key)
			return T;
		p = (key < p->Key) ? (p->lchild) : (p->rchild);

	}
	s = new BinSearchNode;
	s->Key = key;
	s->lchild = NULL;
	s->rchild = NULL;
	if (T == NULL)
		return s;
	if (key < f->Key)
		f->lchild = s;
	else
		f->rchild = s;
	return T;
}

BinSearchTree Create(BinSearchTree T)
{
	KeyType key;
	T = NULL;
	cout << "输入节点关键数，以-1结束" << endl;
	cin >> key;
	while (key != -1)
	{
		Tree_Insert(T, key);
		cin >> key;
	}
	return T;
}

void MiddleTravel(BinSearchTree T)
{
	cout << "中序遍历为：";
	if (T != NULL)
	{
		MiddleTravel(T->lchild);
		cout << T->Key;
		MiddleTravel(T->rchild);
	}
}

博客更新至专栏【课程设计实验报告】：https://blog.csdn.net/weixin_43598687/category_11640051.html

本科课程【数据结构与算法】实验5 - 广度优先搜索、二叉排序树的构造

Java相关栏目本月热门文章