联盟查找 - 快速查找

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); 
    } 
} 

，因为它应该是程序没有运行。当我尝试执行union(4,3)，然后执行union(3,8)时，只有arr[3]更改其值，而不是arr[4]。此外，我不知道为什么我不得不使用getchar（该程序一直没有结束）。

Answer 1

这条线：

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

相当于：

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

和测试电流id对于i与电流id对于p。

问题是，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]; 
    } 
}