c - 联合查找 - 快速查找

Question

我刚开始普林斯顿算法课程，并尝试在 C 中实现一个非常基本的快速查找算法，如下所示 -

#include <stdio.h>

void find(int *, int, int);
void unite(int *, int, int);

int main() {
    int arr[10], i, n1, n2, opt;
    char ch;

    for (i = 0; i < 10; i++)
        arr[i] = i;

    do {
        printf("1. Find\n2. Union\n");
        scanf("%d", &opt);
        if (opt == 1) {
            scanf("%d,%d", &n1, &n2);
            find(arr, n1, n2);
        }
        if (opt == 2) {
            scanf("%d,%d", &n1, &n2);
            unite(arr, n1, n2);
        }
        for (i = 0; i < 10; i++)
            printf("%d  ", arr[i]);
        printf("Continue? (Y/N)");
        getchar();
        scanf("%c", &ch);
    } while (ch == 'Y');
}

void find(int *id, int p, int q) {
    if ((*(id + p)) == (*(id + q)))
        printf("Connected\n");
}

void unite(int *id, int p, int q) {
    int i;
    for (i = 0; i < 10; i++) {
        if ((*(id + i)) == (*(id + p)))
            *(id + i) = *(id + q);
    }
}

该程序没有按预期运行。当我尝试做 aunion(4,3)然后 aunion(3,8)时，只会arr[3]改变它的值而不是arr[4]。另外，我不确定为什么我必须使用getchar（程序没有它就一直结束）。

Answer 1

这一行：

if((*(id+i))==(*(id+p)))

相当于：

if (id[i] == id[p])

并用 p 的当前 id 测试 i 的当前 id。

问题是 id[p] 可能已经改成了 id[q]！

因此，当您尝试将所有 3 变为 8 时，在我们将 arr[3] 更改为 8 之后，从那时起我们只是将 8 变为 8。

而是尝试存储 p 的当前 id，并针对它进行测试：

void unite(int *id, int p, int q)
{
    int i;
    int id_to_change = id[p];
    for(i=0;i<10;i++)
    {
        if(id[i] == id_to_change)
            id[i] = id[q];
    }
}