25.4.30数据结构|并查集 路径压缩

书接上回

上一节：数据结构|并查集

前言

（一）理论理解：

1、在QuickUnion快速合并的过程中，每次都要找根ID，而路径压缩让找根ID变得更加迅速直接。

2、路径压缩 针对的是findRootIndex()【查找根ID】进行的压缩。

3、需要实现的是：

在找根节点的过程中，记录这条路径上的所有信息，处理完事务后，恢复保存的节点信息，恢复父节点的关系

（二）使用宏定义

（没搞明白vscode怎么才能用下边的宏代换）

#ifndef、#else 和 #endif 是 C、C++ 等编程语言中的预处理指令，主要用于条件编译。

• #ifndef：这是 "if not defined" 的缩写，其作用是检查某个宏是否未被定义。要是该宏未定义，就会执行 #ifndef 和 #else（若存在）或者 #endif 之间的代码；反之，则跳过这些代码。
• #else：当 #ifndef 条件不满足时，也就是宏已经被定义，就会执行 #else 和 #endif 之间的代码。
• #endif：用于标志条件编译块的结束，和 #ifndef 配对使用。

一、路径压缩 --链栈

（一）理解：

            链栈（只需要维护栈顶指针），而链式队列（需要维护队头队尾），所以用链栈更好

对查找根ID函数进行操作：对于每一个节点，把他的索引放到栈里，记录了先后顺序

            

（二）代码：

/**************使用链栈实现路径压缩*******************///定义链栈结构
typedef struct setNode{int index;struct setNode*next ;
}setNode;
//入栈
static setNode *push(setNode *stack, int index){setNode *node = malloc(sizeof(setNode));node->index = index;node->next = stack;return node;
}
//出栈
static setNode *pop(setNode *stack, int *index){setNode *tmp = stack->next;*index = stack->index;stack=stack->next;free(tmp);return stack;  
}//找元素a的根ID
static int findrootindex(const QuickUnionSet * setQU,Element a){int curIndex = findIndex(setQU,a);if(curIndex == -1){return -1;}//栈顶指针setNode*path=NULL;//找根ID，(节点的父节点指向自己时找到根结点)等价于quickfind中的groupidwhile(setQU->parentID[curIndex] !=curIndex){path = push(path, curIndex);//入栈，传入栈顶指针，记录索引，指针移动curIndex = setQU->parentID[curIndex];}//找到了根ID，恢复记录的信息，把这些节点的父节点关系进行更新while(path){int pos;path = pop(path,&pos);setQU->parentID[pos] = curIndex;}return curIndex;
}

 （三）图解

因为有点绕，不太理解最后画了一下图，模拟了一遍，理解了

梳理代码时候写的：

题目：如下图示并查集，查找2的根结点

并查集的存储如下：

从2开始入栈，岀栈过程中，使节点点的父ID直接为根ID，即可实现路径压缩，一步即可找到根。

终于理解咯~~