题目要求：
- 实验目的
掌握在线等价类的使用，要求使用模拟指针实现。
- 实验内容
- 使用模拟指针实现本实验。
- 输入一个1-9的正整数n，代表要创建n个元素，例如输入5，则代表创建一个1,2,3,4,5组成的元素表。
- 再输入一个大于0正整数r，代表后面要输入r个等价关系。
- 分行输入r个等价关系，格式如(1,2)。
- 分行输出所有等价类，一个等价类的元素由小到大依次输出。例如等价类(1,3,5,2,4)，输出时排序输出(1,2,3,4,5)。
- 如果输出不是由小到大顺序输出，解决办法很多，可以创建一个n*n的数组，一行存放一个等价类，将所有等价类放入数组，对数组每一行元素进行排序，输出数组所有元素。
算法核心思想分析：
模拟指针定义
该实验要求实现在线等价类，且用到模拟指针。首先要来明确模拟指针是什么，模拟指针就是指针数组，其本质就是一个数组其元素是伪指针，其逻辑结构和指针、链表是一样的，就是在物理结构上采用数组去实现，主要应用在早期没有指针的语言当中，如VB语言。
结构体定义
知道这个之后我们就可以写出模拟指针的数据结构了，包含一个next指向下一个元素的下标，equiClass表示该元素所在的类。当然为了查找的方便我们让数组的下标来表示该节点元素的值，如a【1】表示该节点值为1。
类合并的思想
在合并的时候有一个相当重要的思想：我们合并unite（a,b）本质就是合并a所在的类以及b所在的类，而两者的类又是通过模拟指针实现的，所以逻辑上把这两个类合并就是把两个类的逻辑链表进行合并。那么问题就简单了，等价类的合并就是对两个链表执行合并，这里涉及到另外一个问题就是要保持合并后的链表仍然有序，所以我们的合并就应该采用双指针并进的方式，由此保证整体有序。这里还有一个关键点就是既然是对两个链表操作合并，我们的操作对象自然就要是a，b两个元素对应的链表的头结点，而不是这两个数本身。我们要从其头节点开始操作，才能保证整个链表都被操作了。
如何找模拟指针类链表的头结点
下一个重要思想：头结点所在的下标就是类值本身。例如3在2类里面，我只需要find（3）得到其所在类，然后把这个类值作为下标代入得到的就是这个2类的头结点。保证这个原理实现的关键在于每次都将大的类值改变为小的类，例如2类3类合并，就是把3类集体改为2类，并插入2类的链表中。所以每一个存在的类，其头结点都是下标为这个类数的结点
代码及分析如下：
#include<iostream> using namespace std; struct equiNode{//等价结点类 int equiClass;//该节点对应data所属的类 int size;//该节点的值由下标表示而不用data原因在于查找方便。此处size表面所在类的元素个数 int next;//该类中下一个节点位置，按照元素从小到大的下一个节点 }; class equiNodeArray{//模拟指针本质是由伪指针构成的数组 private: equiNode* nodeArray; public: equiNodeArray(int num){ nodeArray=new equiNode[num+1];//由于我们要有num个元素，且元素从下标第一个开始放，所以要多一个位 for(int i=0;i<=num;i++){//注意！这个要<=num，因为下标0处不放元素 nodeArray[i].equiClass=i; nodeArray[i].size=1; nodeArray[i].next=-1;//这里选择写-1而不是0，主要是为了逻辑上体现找不到。用0可能有的题会不行（如果那个题从0下标开始存），当然本题数从1开始，故都可以。 } } void unite(int a,int b){ int aClass=nodeArray[a].equiClass; int bClass=nodeArray[b].equiClass;//这两个类需要合并，所以所有的操作对象都应该从aclass和bclass开始.这两个数是这两个链表的头 if(aClass==bClass)//同一类不需要合并 return; else{//不同类需要合并处理 if(aClass>bClass){//一般情况（1，2）小的类在前，若是（2，1）则将其变为（1，2）效果相同 unite(b,a);//这里选择直接将ab调换重新调用函数 } else{ //具体的合并操作————对equiClass的处理，对next处理 int i=0; for(i=bClass;nodeArray[i].next!=-1;i=nodeArray[i].next){//找到b元素所在类的第一个元素，然后再向下遍历修改，不能是i=b nodeArray[i].equiClass=aClass;//处理方式就是循环遍历然后一一修改 } nodeArray[i].equiClass=aClass; nodeArray[aClass].size+=nodeArray[bClass].size; while(nodeArray[aClass].next!=-1&&bClass!=-1){//两个逻辑链表都没到最后,前面需要next是因为要插入，后面不用插入所以可以直接到最后 if(nodeArray[aClass].next>bClass){//将b这个元素链接到a这个元素后面，并且把b的next元素保存到变量b中用于下一轮循环 int tem=nodeArray[bClass].next; nodeArray[bClass].next=nodeArray[aClass].next; nodeArray[aClass].next=bClass; aClass=nodeArray[aClass].next; bClass=tem; } else{ aClass=nodeArray[aClass].next; } } if(nodeArray[aClass].next==-1){//此时退出while就是因为aclass的最后一个已经没有bclass大了，所以不用再判断，直接连接就可以 nodeArray[aClass].next=bClass; } //若是不满足这个代表bclass的链表已经全部放到aclass链表中了，所以到这里整体合并就完成了 } } } int find(int element){//给元素值返回该值对应的类 return nodeArray[element].equiClass; } void printEquiClass(int n){//打印所有的类 for(int i=1;i<=n;i++){ if(i==nodeArray[i].equiClass){//说明是一个新类的起点，开始打印。否则说明在其他类中，不用打印 int t=i; cout<<'('<<t;//这里必须选择先输出一个t然后进入循环，而不能选择在循环中输出。因为当只有一个元素时，这个next判断肯定不会通过，此时也要有输出 while(nodeArray[t].next!=-1){ cout<<','<<nodeArray[t].next; t=nodeArray[t].next; } cout<<')'<<endl; } } } }; int main(){ int num,equinum=0; cout<<"Input"<<endl; cin>>num>>equinum; equiNodeArray a(num); char t=' '; int x,y=0; for(int i=0;i<equinum;i++){ cin>>t>>x>>t>>y>>t; a.unite(x,y); } cout<<"Output"<<endl; a.printEquiClass(num); cout<<"End"<<endl; return 0; }
