山东大学数据结构实验四在线等价类

1、 使用5实现本实验。
2、 输入一个1-9的正整数n，代表要创建n个元素，例如输入5，则代表创建一个1,2,3,4,5组成的元素表。
3、 再输入一个大于0正整数m，代表后面要输入m个等价关系。
4、 分行输入m个等价关系，格式如(1,2)。
5、 分行输出所有等价类。

#include 
using namespace std;
//模拟指针的定义
//模拟指针可以理解为：在一个模拟空间中，
//存在一个指针数组，数组中的每个元素为指针类型，
//并且每个指针具有数据域和链接域（指向下一个数组中的指针）。


struct equivNode
{
	int equivClass;//元素类标识符
	int size;      //类的元素个数
	int next;      //类中指向下一个元素的指针
	//这好像是数组模拟链表，这样有一个很妙的地方，
	//所有类中的这个元素的下一个元素的值存在next中
};
class BingChaJi {
	//构造函数
public:
	BingChaJi(int numberOfElements)
	{
		n = numberOfElements;
		node = new equivNode[n + 1];//豪气，第0个不用

		for (int e = 0; e <= n; e++)
		{
			node[e].equivClass = e;//现在是自己和自己混
			node[e].next = 0;//因为第0类不用（原来不是豪气呀）链表中没有下一个节点就可以用0表示
			node[e].size = 1;//因为现在一个类的元素个数是1

		}

	}
	void unite(int class1, int class2)
	{
		int n1 = node[class1].equivClass;
		int n2 = node[class2].equivClass;
		//cout << n1 << " " << n2;
		
		if (n1 == n2)
		{
			return;
		}

		if (n1>n2)
		{
			int temp = n2;
			n2 = n1;
			n1 = temp;

		}
		//改变class2的equivClass值
		int k;
		for ( k = n2; node[k].next != 0; k = node[k].next)
		{
			node[k].equivClass = n1;
		}
		node[k].equivClass = n1;//漏网之鱼

		node[n1].size +=node[n2].size;


		int temp;
		if (!node[n1].next)
		{
			node[n1].next = n2;
			return;
		}
		while (node[n1].next&&n2)
		{
			if (node[n1].next < n2)
			{
				n1 = node[n1].next; 
			}
			else {
				temp = node[n2].next;
				node[n2].next = node[n1].next;
				node[n1].next = n2;
				n2 = temp;
				n1 = node[n1].next;                     
			}
		}
		
		if (n2)
		{
			node[n1].next = n2;
		}
		
		
	}

	//相比于上面的硬核这个显得舒服多了
	int find(int theElement)
	{
		//查找包含元素theElement的类
		return node[theElement].equivClass;
	}
	void print()
	{
		for (int i = 1; i <=n; i++)
		{
			
			if (node[i].equivClass == i)
			{
				int index=i;

				
				cout << "(" << i;
				while (node[index].next)
				{
					cout << "," << node[index].next;
					index = node[index].next;
				}
				cout << ")" << endl;
			}
		}
	}
private:
	//节点的数组，一个类的在一个“链表”里，不同的类在不同的“数组”元素中，应该是这样吧
	equivNode* node;
	int n;//元素的个数
};

int main()
{

	cout << "Input" << endl;
	int n;
	cin >> n;
	BingChaJi bing(n);
	int m;
	cin >> m;
	string s;
	int a, b;
	for (int i = 0; i < m; i++)
	{
		cin >> s;
		 a = s[1]-'0';
		 b = s[3]-'0';
		
		 bing.unite(a, b);
	}
	cout << "Output" << endl;
	bing.print();
	cout << "End" << endl;

	return 0;
}