查找

查找表

是由同一类型数据元素构成的集合。比方说成绩表

查找

给定一定的数据，返回一个关键字

关键字

标识数据元素某一项的值

主关键字

唯一的标识某个记录的关键字，比方说是准考证

次关键字

以识别若干记录的关键字是次关键字

分类

静态查找表

仅作为 查询 或者 检索的查找表

动态查找表

做插入/删除操作的查找表

评价指标

平均查找长度ASL,即关键字的平均比较次数，也称为平均查找长度

顺序表的查找

顺序查找法

经典方法

比较传统的查找方式，从前往后一一遍历进行查找，时间复杂度O(N)，平均查找长度(N + 1)/2

int find(int a[],int n,int key)
{
    for(int i=0;i<n;i++)
        if(a[i]==key)//key为需要查找的值
            return i;
    return -1;
}

哨兵法

该方法仅适用于下标从1开始的

int find(int a[],int n,int key)//无需考虑范围
{
    a[0]=key;
    int i=n;
    while(a[i]!=key)
        i--;
    return i;
}

顺序查找法的时间复杂度为O(N)，平均查找长度为$$\frac{n+1}{2}$$

折半查找（二分查找）

仅适用于有序的线性表，且必须为顺序存储

假设线性表中的元素的排列顺序是已递增的顺序进行排列的

查找方式：

  • 在线性表中取中间位置进行比较，如果与中间位置的值相等，那么返回
  • 如果不相等，则与中间的数据进行比较
  • 如果中间的元素大于需要查找的元素的值，则在左半边查找
  • 如果中间的元素小于需要查找的元素的值，则在右半边查找
  • 重复以上过程，如果未找到，则另返回其他值
int find(int a[],int n,int key)
{
    int low=0,height=n-1;//low为开始区间位置(上界），height为结束区间的位置（下界）
    while(low<=height)
    {
        int mid=(height+low)/2;
        if(a[mid]<key)
        {
            low=mid+1;
        }
        else if(a[mid]>key)
        {
            height=mid-1;
        }
        else
            return mid;
    }
    return -1;
}

递归写法

int find(int a[],int low,int height,int key)
{
    if(low>height)
        return -1;
    mid=(low+height)/2;
    if(a[mid]==key)
        return mid;
    else if(a[mid]<key)
        find(a,mid+1,height,key);
    else if(a[mid]>key)
        find(a,low,mid-1,key);
}

时间复杂度为$$ O(logN)$$，最多比较$$log_2N+1$$次，平均查找长度为$$log_2(n+1)-1$$

线性表的分块查找法（索引）

条件

  • 将表分成几块，整个表都有序或者分块有序（块内元素不一定有序）
  • 建立索引表
  • 先确定待查的元素所在的块（顺序查找或者二分查找），再从快内查找（顺序查找）

优点

  • 插入删除比较容易，无需大量移动

缺点

  • 需要建立一个索引表空间进行运算

适用情况

  • 既要快速查找，又要经常动态变化

树表的查找

当表的插入删除时要进行很多的操作，比如插入、删除等，为了维护表的有序性，需要移动许多记录。

所以，可以改用动态查找表，即几种特殊的树，表的结构在查找过程中生成，对于查找的定值key若存在，则返回，若不存在，则插入关键字key

常见的特殊的树

  • **二叉排序树 **
  • **平衡二叉树 **
  • 红黑树
  • B-树
  • B+树
  • 键树

二叉排序树

又被称为**二叉搜索树 **、**二叉查找树 **

二叉排序树可以是**空树 **

性质

  • 若其左子树非空，则左子树上的结点的值都小于根节点的值
  • 若其右子树非空，则右子树上的结点的值都大于等于根节点的值
  • 其左右子树也是一棵二叉排序树
  • 二叉排序树的中序遍历序列是呈递增排序

查找

二叉排序树的查找和二分查找类似

  • 首先，将需要查找的值与根节点比较
  • 如果比根节点小，则在左子树查找
  • 如果比根节点大，则在右子树查找
  • 如果与根节点相等就返回
  • 重复以上过程

存储结构

typedef struct
{
    int data;
    struct tree *lChild,rChild;
}tree;

递归查找

tree *search(tree *t,int key)
{
    if(!t||key==t->data)//如果t为空返回NULL，如果找到了，返回t
        return t;
    else if(key<t->data)//如果key小于这个根节点的值，则在其左子树查找
        search(t->lChild,key);
    else if(key>t->data)//如果key大于这个根节点的值，则在其左子树查找
        search(t->rChild,key);
}

另一种查找方式，可以保存双亲结点

bool search(tree *parent, tree *child, int key, tree **t)//parent存储双亲结点，child表示当前遍历的，t中保存双亲结点（当未找到需要查询的结点时）或者找到的结点
{
    if (child == NULL)
    {
        *t = parent;//表明此时未找到值，将它的双亲结点给t
        return false;
    }
    else if (key > child->data)
        search(child, child->r, key, t);
    else if (key < child->data)
        search(child, child->l, key, t);
    else if (key == child->data)
    {
        t = child;//表明此时已经找到了
        return true;
    }
}

插入

  • 若二叉树为空，则将作为根节点插入到空树中
  • 否则在其左右子树查找
    • 树中已有，不再插入
    • 树中没有
      • 按照如果比根节点小，则在左子树查找，如果比根节点大，则在右子树查找的规则进行查找某个叶子结点的左子树和右子树，直到为空
      • 将结点插入到为空的位置

插入的元素一定在叶子结点

bool create(tree **t, int key)
{
    tree *parent=NULL;//存储双亲结点
    if (!search(NULL, *t, key, &parent))//代表该点没有被插入
    {
        tree *p = (tree *)malloc(sizeof(tree));
        p->data = key;
        p->l = p->r = NULL;
        if (!parent)
        {
            *t = p;//代表没有双亲结点，此时为空树
        }
        else if (key > parent->data)//key的值大于此时其双亲结点的值，应插入到右侧
        {
            parent->r = p;
        }
        else if (key < parent->data)//key的值小于双亲结点的值，应插入到左侧
        {
            parent->l = p;
        }
        return true;
    }
    return false;
}

以上的search函数模型基于第二种

完整代码
/*
 * @Created by : SongXiaoxu
 * @Copyright © 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-04-02 19:17:17
 * @LastEditTime: 2021-04-05 22:05:23
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct
{
    int data;
    struct tree *l, *r;
} tree;
bool search(tree *parent, tree *child, int key, tree **t)//parent存储双亲结点，child表示当前遍历的，t中保存双亲结点（当未找到需要查询的结点时）或者找到的结点
{
    if (child == NULL)
    {
        *t = parent;//表明此时未找到值，将它的双亲结点给t
        return false;
    }
    else if (key > child->data)
        search(child, child->r, key, t);
    else if (key < child->data)
        search(child, child->l, key, t);
    else if (key == child->data)
    {
        t = child;//表明此时已经找到了
        return true;
    }
}
bool create(tree **t, int key)
{
    tree *parent=NULL;//存储双亲结点
    if (!search(NULL, *t, key, &parent))//代表该点没有被插入
    {
        tree *p = (tree *)malloc(sizeof(tree));
        p->data = key;
        p->l = p->r = NULL;
        if (!parent)
        {
            *t = p;//代表没有双亲结点，此时为空树
        }
        else if (key > parent->data)//key的值大于此时其双亲结点的值，应插入到右侧
        {
            parent->r = p;
        }
        else if (key < parent->data)//key的值小于双亲结点的值，应插入到左侧
        {
            parent->l = p;
        }
        return true;
    }
    return false;
}
void print(tree *t)
{
    if(t==NULL)
    {
        return ;
    }
    print(t->l);
    printf("%d->",t->data);
    print(t->r);
}
int main()
{
    tree *t = NULL;
    while (1)
    {
        puts("");
        puts("1----insert");
        puts("2----print");
        puts("3----find");
        puts("0----exit");
        int flag;
        scanf("%d",&flag);
        if (flag == 0)
            return 0;
        else if (flag == 1)
        {
            int key;
            printf("type in key:");
            scanf("%d",&key);
            if(create(&t,key))
            {
                puts("success");
            }
            else
                puts("errr");
        }
        else if(flag==2)
            print(t);
        else if(flag==3)
        {
            int key;
            tree *p=NULL;
            printf("type in key:");
            scanf("%d",&key);
            if(search(NULL, t, key, p))
                puts("find");
            else
                puts("NOT FIND");
        }
    }
    return 0;
}

二叉搜索树的删除结点

在删除时，不能把这个根所在的结点删除，只能删除这个结点，并且删除后还应保持该二叉树仍为二叉搜索树

  • 将删除这个结点后的二叉链表重新链接起来
  • 防止重新链接后的高度增加
删除的情况

  • 若删除的结点为叶子结点，则直接删除，无需考虑其他情况，即直接将其双亲结点的指针域置为空

  • 若删除的结点只有左子树或者右子树，直接用这个结点左子树或者右子树直接替换

  • 若删除的结点既有左子树又有右子树

    • 方法1，在其左子树上找到一个最大的结点，用来代替这个结点，此时最大结点为被删除的结点中序遍历的前驱节点

    • 方法2，使用右子树最小的结点进行替换，右子树最小的结点为被删除结点的中序遍历结点的后继结点

例如，下图

image-20210409181616794

遍历顺序

1->2->3->4->5->6->7->8->9

若要删除4，则用4的中序遍历前驱结点3替换

删除过程

  • 首先查找要被删除的key在树中是否存在（可以将查找是否存在的函数与删除函数结合在一起），若存在则进行以下步骤

  • 先判断是否存在左右子树（麻烦）

    • 如果同时存在左右子树，则寻找其左子树的最大元素（中序遍历的前驱）或者右子树的最小元素（中序遍历的后继），使用该元素进行覆盖当前要删除的元素的值，然后递归的删除左子树的最大元素或者右子树的最小元素
    • 如果只存在左子树，则用其左子树替换该结点，并释放掉该结点
    • 如果只存在右子树，则用其右子树替换该结点，并释放掉该结点

  • 如果没有左右子树，直接释放掉该结点，同时让其双亲结点指向空即可（比较繁琐）

  • 也可以使用更巧妙的方法

    • 如果同时存在左右子树，则寻找其左子树的最大元素或者右子树的最小元素，使用该元素进行覆盖当前要删除的元素的值，然后递归的删除左子树的最大元素或者右子树的最小元素
    • 判断左子树是否为空（即左子树不存在），让需要删除的结点指向其右子树（这样的话纵使其左右子树都为空，它的双亲结点可以指向空，无需进行多余的步骤让其双亲结点指向空）
    • 判断右子树是否为空（即右子树不存在），让需要删除的结点指向其左子树（这样的话纵使其左右子树都为空，它的双亲结点可以指向空，无需进行多余的步骤让其双亲结点指向空）
int maxLeftTreeValue(tree *t)//寻找左子树的最大值
{
    if (t->r == NULL)//左子树的最大值仅存在与它的右子树
        return t->data;
    maxLeftTreeValue(t->r);
}
tree *delete (tree **t, int key)
{
    if (!(*t))//表明未找到值
        puts("NOT FIND");
    else if (key > (*t)->data)//递归查找并修改右子树的值
        (*t)->r = delete (&((*t)->r), key);
    else if (key < (*t)->data)//递归查找并修改左子树的值
        (*t)->l = delete (&((*t)->l), key);
    else
    {
        if ((*t)->l && (*t)->r)//此时被删除的结点时双亲结点的情况（即既存在左孩子，又存在右孩子）
        {
            int max = maxLeftTreeValue((*t)->l);//查找左子树的最大值
            (*t)->data = max;//利用最大值替换该结点
            (*t)->l = delete (&(*t)->l, max);//将左子树的最大值的结点递归删除
            
        }
        else
        {
            tree *temp = *t;
            if (!(*t)->l)//判断左子树是否为空（即左子树不存在），让需要删除的结点指向其右子树（这样的话纵使其左右子树都为空，它的双亲结点可以指向空，无需进行多余的步骤让其双亲结点指向空）
                (*t) = (*t)->r;
            else if (!(*t)->r)//判断右子树是否为空（即右子树不存在），让需要删除的结点指向其左子树（这样的话纵使其左右子树都为空，它的双亲结点可以指向空，无需进行多余的步骤让其双亲结点指向空）
                (*t) = (*t)->l;
            free(temp);
        }
    }
    return *t;
}
完整代码
/*
 * @Created by : SongXiaoxu
 * @Copyright © 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-04-02 19:17:17
 * @LastEditTime: 2021-04-11 13:19:12
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct
{
    int data;
    struct tree *l, *r;
} tree;
bool search(tree *parent, tree *child, int key, tree **t) //parent存储双亲结点，child表示当前遍历的，t中保存双亲结点（当未找到需要查询的结点时）或者找到的结点
{
    if (child == NULL)
    {
        *t = parent; //表明此时未找到值，将它的双亲结点给t
        return false;
    }
    else if (key > child->data)
        search(child, child->r, key, t);
    else if (key < child->data)
        search(child, child->l, key, t);
    else if (key == child->data)
    {
        t = child; //表明此时已经找到了
        return true;
    }
}
bool create(tree **t, int key)
{
    tree *parent = NULL;                 //存储双亲结点
    if (!search(NULL, *t, key, &parent)) //代表该点没有被插入
    {
        tree *p = (tree *)malloc(sizeof(tree));
        p->data = key;
        p->l = p->r = NULL;
        if (!parent)
        {
            *t = p; //代表没有双亲结点，此时为空树
        }
        else if (key > parent->data) //key的值大于此时其双亲结点的值，应插入到右侧
        {
            parent->r = p;
        }
        else if (key < parent->data) //key的值小于双亲结点的值，应插入到左侧
        {
            parent->l = p;
        }
        return true;
    }
    return false;
}
void print(tree *t)
{
    if (t == NULL)
    {
        return;
    }
    print(t->l);
    printf("%d->", t->data);
    print(t->r);
}
int maxLeftTreeValue(tree *t)//寻找左子树的最大值
{
    if (t->r == NULL)//左子树的最大值仅存在与它的右子树
        return t->data;
    maxLeftTreeValue(t->r);
}
tree *delete (tree **t, int key)
{
    if (!(*t))//表明未找到值
        puts("NOT FIND");
    else if (key > (*t)->data)//递归查找并修改右子树的值
        (*t)->r = delete (&((*t)->r), key);
    else if (key < (*t)->data)//递归查找并修改左子树的值
        (*t)->l = delete (&((*t)->l), key);
    else
    {
        if ((*t)->l && (*t)->r)//此时被删除的结点时双亲结点的情况（即既存在左孩子，又存在右孩子）
        {
            int max = maxLeftTreeValue((*t)->l);//查找左子树的最大值
            (*t)->data = max;//利用最大值替换该结点
            (*t)->l = delete (&(*t)->l, max);//将左子树的最大值的结点递归删除
            
        }
        else
        {
            tree *temp = *t;
            if (!(*t)->l)//判断左子树是否为空（即左子树不存在），让需要删除的结点指向其右子树（这样的话纵使其左右子树都为空，它的双亲结点可以指向空，无需进行多余的步骤让其双亲结点指向空）
                (*t) = (*t)->r;
            else if (!(*t)->r)//判断右子树是否为空（即右子树不存在），让需要删除的结点指向其左子树（这样的话纵使其左右子树都为空，它的双亲结点可以指向空，无需进行多余的步骤让其双亲结点指向空）
                (*t) = (*t)->l;
            free(temp);
        }
    }
    return *t;
}

int main()
{
    tree *t = NULL;
    while (1)
    {
        puts("");
        puts("1----insert");
        puts("2----print");
        puts("3----find");
        puts("4----Delete");
        puts("0----exit");
        int flag;
        scanf("%d", &flag);
        if (flag == 0)
            return 0;
        else if (flag == 1)
        {
            int key;
            printf("type in key:");
            scanf("%d", &key);
            if (create(&t, key))
            {
                puts("success");
            }
            else
                puts("errr");
        }
        else if (flag == 2)
            print(t);
        else if (flag == 3)
        {
            int key;
            tree *p = NULL;
            printf("type in key:");
            scanf("%d", &key);
            if (search(NULL, t, key, p))
                puts("find");
            else
                puts("NOT FIND");
        }
        else if (flag == 4)
        {
            int key;
            printf("type in key:");
            scanf("%d", &key);
            delete (&t, key);
        }
    }
    return 0;
}

平衡二叉树

含有n个结点的二叉搜索树的平均查找长度与树的形态有关最好的查找时间复杂度为***logN***

如果一开始输入的树就是有序的，那么建立起的二叉树就会偏向一侧，此时时间复杂度为***O(N)***

让二叉搜索树排列成均衡的二叉树，可以提高查找效率，使得二叉搜索树排列比较均衡的二叉树称为二叉平衡树

定义

  • 平衡二叉树又被称为AVL树
  • 平衡二叉树是一个二叉搜索树
  • 一棵平衡二叉树或者空树都具备
    • 左子树和右子树的高度差的绝对值小于等于1，即不超过1
    • 左子树和右子树也是二叉平衡树
平衡因子

给每个结点外加一个数字，该数字存储左右子树的高度差

平衡因子=结点左子树的高度-结点右子树的高度，根据平衡二叉树的定义，平衡因子的值只能是-1 0 1，即绝对值小于等于1

平衡调整

当插入新的结点后失衡的结点不止一个时，失衡的结点为最小失衡子树的根节点

  • LL型

    • 插入的结点是插入到左子树的左子树上导致的失衡

  • LR型

    • 插入的结点是插入到左子树的右子树上导致的失衡

  • RL型

    • 插入的结点是插入到右子树的左子树上导致的失衡

  • RR型

    • 插入的结点是插入到右子树的右子树上导致的失衡

150

散列表（哈希表）

基本思想：记录存储位置和关键字之间的对应关系，使用hash()函数计算关键字应该存储的位置

hash为混杂、拼凑的意思

术语

  • 散列方法（杂凑法）：根据关键字计算存储位置，以此存放。查找时也是使用同一个函数到相同的位置查找比对
  • 散列函数：即转换函数，计算关键字存放位置的函数
  • 散列表：用以上方法构造的表就是散列表
  • 冲突：不同的关键字映射到同一位置，两个关键字不相同，但通过hash(key)运算后，两个地址相同
  • 同义词：具有相同函数值的多个关键字，即冲突的关键字的值

查找

可以直接通过下标进行查找，例如计算一个字符串中每个字符出现的次数，可以用数组进行存储，此方法也为哈希表

  • 优点：查找效率高，复杂度在O(1)
  • 缺点：空间效率低

散列函数

在散列表中冲突是不可避免的，可以想办法进行减少冲突，要做到

  • 所构造函数尽可能简单，提高转码速度
  • 所选函数通过关键字计算的地址，应该在散列地址上均匀分布，减少空间浪费
  • 可以根据冲突解决规则，高效的解决冲突

构造时，需要考虑的因素：

  • 执行速度
  • 关键字长度
  • 散列表大小
  • 关键字的分布情况
  • 查找频率

散列表的本质是以空间换时间

构造方法
  • 直接定址法
  • 数字分析法
  • 平方取中法
  • 折叠法
  • 除留余数法
  • 随机数法
直接定址法

现有一个集合{100, 200, 300, 400}，此时适合直接定址法

优点是使用线性函数进行取值，不会造成冲突，缺点是空间效率低

hash函数为

int hash(int key)
{
    return key / 100;
}
除留余数法

顾名思义，通过取余进行存储

int hash(int key, int num)
{
    return key % num;//key为关键字，num为需要被取余的数
}

设表长为m，取num <= m，且num为素数

解决冲突

  • 开放地址法（开地址法）
  • 链地址法（拉链法）
  • 再散列表法（双散列函数）
  • 建立一个公共溢出区
开地址法

思想：有冲突就去找下一个空的散列地址，只要散列表足够大，空的地址总会找到，以此将数据存入

寻找下一个方法的哈希函数

int hash(int key, int num)
{
    return hash % num;
}
结果为 (hash(key, num) + nextPlace) % num;

增值nextPlace的常用计算方法为：

  • 线性探测法

    即序列每次增加1，2，3....，m - 1

    /*
 * @Created by : SongXiaoxu
 * @Copyright © 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-05-21 16:48:04
 * @LastEditTime: 2021-06-01 18:44:18
 */
#include <stdio.h>
#define listLength 11 //表长是11，而11又是小于等于11的一个素数
int hash(int key)
{
    return key % listLength;
}
void find(int key, int *hashList)
{
    int pos = hash(key);
    int stopPos = pos - 1 < 0 ? listLength - 1 : pos - 1; //作为循环终止条件判断，因为需要查找到整个哈希表
    while (hashList[pos] != key && pos != stopPos)//遍历哈希表，查看是否在表内
    {
        pos = (pos + 1) % listLength;
    }
    if (hashList[pos] == key)
        puts("OK");
    else
        puts("NO");
}
int main()
{
    int a[9] = {47, 7, 29, 11, 16, 92, 22, 8, 3};
    int hashList[11];
    for (int i = 0; i < 11; i++)
        hashList[i] = -1;       //-1代表没有在其中
    for (int i = 0; i < 9; i++) //将数组a放入到哈希表中
    {
        int pos = hash(a[i]); //取哈希表的下标
        while (hashList[pos] != -1)//此处没有被占用
        {
            pos = (pos + 1) % listLength;
        }
        hashList[pos] = a[i];
    }
    for (int i = 0; i < 11; i++)
    {
        printf("%d ", hashList[i]);
    }
    puts("");
    find(33, hashList);
    return 0;
}

  • 二次探测法

    冲突位置每次增加1的平方，-1的平方，2的平方，-2的平方，....，-q的平方

    pos = hash(key);
pos2 = pos;
list = 1;//初始化序列
int flag = 1;//用于正负号的标记
while(hashList[pos]!=空)
{
    pos = (pos2 + list * list * flag) % 数组长度;
    list = list > 0 ? -1 * list : -1 * list + 1;
    flag *= -1;
}
hashList[pos] = key;

  • 伪随机探测法

    增量是一个伪随机数

链地址法（拉链法）

基本思想：将具有相同散列地址的记录给串成一个单链表，m个散列地址就有m个单链表

  • 计算key的地址，查看该区域是否有值
    • 如果有值，通过单链表进行插入
    • 如果没有直接插入
  • 查找，计算出地址
    • 查看地址下的值是否相同，如果相同返回true
    • 如果不同，先遍历单链表，如果相同，返回true，如果没有找到，返回false
/*
 * @Created by : SongXiaoxu
 * @Copyright © 2021年 by: 宋晓旭. All rights reserved
 * @Date: 2021-06-02 09:37:11
 * @LastEditTime: 2021-06-02 09:51:40
 */
#include <stdio.h>
#include <stdlib.h>
#define maxLength 11
typedef struct hashList
{
    int data;
    struct hashList *next;
} hashList;
int hash(int key)
{
    return key % maxLength;
}
void insert(int key, hashList *h) //插入函数，使用的是单链表
{
    int pos = hash(key);
    if (h[pos].data == -1)
    {
        h[pos].data = key;
    }
    else //头插法
    {
        hashList *p = (hashList *)(malloc(sizeof(hashList)));
        p->data = key;
        p->next = h[pos].next;
        h[pos].next = p;
    }
}
int find(int key, hashList *h)
{
    int pos = hash(key);
    if (h[pos].data == key)
    {
        return 1; //找到
    }
    else
    {
        for (hashList *p = h[pos].next; h != NULL; h = h->next)
        {
            if (p->data == key)
                return 1;
        }
    }
    return -1; //未找到
}
int main()
{
    hashList h[maxLength];
    for (int i = 0; i < maxLength; i++) //初始化哈希表
    {
        h[i].data = -1;
        h[i].next = NULL;
    }
    int a[15] = {0, 1, 2, 3, 4, 445, 6, 7, 8, 9, 10, 11, 12, 13, 14};
    for (int i = 0; i < 15; i++)
    {
        insert(a[i], h);
    }
    for (int i = 0; i < 3; i++)
    {
        int n;
        printf("please input one of integer number：");
        scanf("%d", &n);
        if (find(n, h) == 1)
            puts("ok");
        else
            puts("no");
    }
    return 0;
}

优点：非同义词不会冲突，不会出现聚集现象，适合表长不确定时使用

散列表的查找效率取决于散列函数以及处理冲突的方法

并查集

用树来表示集合，每个树根为整棵树的集合编号，每个集合有两个域，一个是数据域，一个是父节点域，可用整型表示，父节点域用来存储父节点的下标

作用

  1. 合并两个集合
  2. 查询两个元素是否在一个集合中

判断

判断是否为树根if(p[x]==x)

合并

将两个集合合并到一块时，只需要让其中一棵树的根节点变为另外一棵树的根节点的孩子

集合编号

while(p[x]!=x)
    x=p[x];

find函数

//非递归
int find(int x)
{
    while(p[x]!=x)
        x=p[x];
    return x;
}

//递归
int find(int x)
{
    if(x!=p[x])
        x=find(p[x]);
    return x;
}
//递归优化
int find(int x)
{
    if(x!=p[x])
        p[x]=find(p[x]);
    return p[x];
}

int find(int x)
{
    if(x==p[x])
        return p[x];
    return p[x]=find(p[x]);
}

Q.E.D.

念念不忘，必有回响。