并查集实验

用双亲表示法实现并查集的并和查的功能

头文件

#pragma once
struct Elem {
	char data;
	int parent;//结点用双亲表示法
};
class UnionFind
{
public:
	UnionFind(char ch[], int n);//每个元素构成一个子集
	~UnionFind() {};//析构函数
	int ufind(char x);//查找元素x所在子树的根结点
	void Union(char x, char y);//合并元素x,y所在的子集
private:
	Elem elem[100];//双亲表示法存储
	int length;//集合的元素个数
};

源文件

#include "UnionFind.h"

int UnionFind::ufind(char x) {
	int i;
	for (i = 0; i < length; i++) {
		if (elem[i].data == x)break;
	}
	while (elem[i].parent != -1) {
		i = elem[i].parent;
	}
	return i;
}

UnionFind::UnionFind(char ch[],int n) {
	//子集即所在树的根节点
	for (int i = 0; i < n; i++) {
		elem[i].data = ch[i];
		elem[i].parent = -1;
	}
	length = n;
}

void UnionFind::Union(char x,char y) {
	//查找两个元素分别属于的子集（即根节点）,进行合并
	int vex1 = ufind(x);
	int vex2 = ufind(y);
	if (vex1 != vex2)
		elem[vex2].parent = vex1;
}

测序程序

#include<iostream>
using namespace std;
#include"UnionFind.h"

int main() {
	char ch[] = "ILOVE";
	UnionFind uf(ch, 10);
	cout <<"O所在的集合："<< uf.ufind('O') << endl;
	//合并
	uf.Union('L', 'O');
	cout << "合并后，O所在的集合：" << uf.ufind('O') << endl;
}

测试结果