当前位置: 动力学知识库 > 问答 > 编程问答 >

c - Explaination of this code?

问题描述:

I'm Studying the Quick-Union algorithm but can't exactly understand this code:

 #include <stdio.h>

#define N 10000

main()

{

int i,p,t,id[N];

for (i = 0; i < N ; i++) id[i]= i;

while (scanf ("%d %d\n" , &p, &q) == 2)

{

for(i = p; i != id[i]; i = id[i]) ;

for (j = q; j != id[j]; j = id[j]) ;

if (i == j) continue;

id [i] = j ;

}

}

my main problem is the for loop. if the condition and the init are met, what does the increment statement do?

NOTICE: This is out of a textbook not my code!

网友答案:

This is an inline implementation of the union-find data structure. The union-find data structure represents disjoint sets as trees. It stores the parent of each node in the id array. Initially, every node is its own parent (forming a separate tree). This is, what the following line does:

for (i = 0; i < N ; i++) id[i]= i;

With the line

for(i = p; i != id[i]; i = id[i]) ; 

you traverse the tree, in which p is located, up to its root. The part i = id[i] changes the current node to the current node's parent.

The same is done for q. Finally, both trees are merged if they are not the same trees.

id [i] = j ;
网友答案:

First of all use return type for main function with int as per standard

for (i = 0; i < N ; i++) id[i]= i; This loop writes on to the array id[i] all the values from 0 to N.

    while (scanf ("%d %d\n" , &p, &q) == 2)
    {
     for(i = p; i != id[i]; i = id[i]) ; 

//In this loop it taking input from the user and checking the same if it is in the array id with the same index if the condition is true you will assign i with the value from the index.

//If condition is no met it will go to next loop

     for (j = q; j != id[j]; j = id[j]) ;

//same as above loop with different input. if (i == j) continue; id [i] = j ; }

网友答案:

here is an explanation, as I understand the code:

#include <stdio.h>

#define N (10000)

int main( void )
{
    int i;
    int p;
    int t;
    int id[N];

    // initialize array id[]
    for (i = 0; i < N ; i++)
    {
        id[i]= i;
    }

    /*
     * IMO:
     * bad idea to be asking for two integers without prompting the user
     * bad idea to use the two values without checking that they are in the range 0...(N-1)
     * this code performs nothing useful
     * the array id[] becomes more 'modified' the more numbers are entered
     * */

    // read two integers, if successful then
    while (scanf ("%d %d\n" , &p, &q) == 2)
    {
        // looping, searching array id[] to see if properly initialized/updated
        for(i = p; i != id[i]; i = id[i]) ;

        // looping, searching array id[] to see if properly initialized/updated
        for (j = q; j != id[j]; j = id[j]) ;

        // when same value extracted from array id[] for both inputs then
        // return to top of loop
        if (i == j) continue;

        // when not the same value, update array id[] with other value
        id [i] = j ;
    }
}
分享给朋友:
您可能感兴趣的文章:
随机阅读: