書接上回

上一節：數據結構|并查集

前言

（一）理論理解：

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，即可實現路徑壓縮，一步即可找到根。

終于理解咯~~