2

集合論における AUB の一般的な意味とクイック検索アルゴリズムのユニオン操作を関連付けることができません。

Book(Algorithms in C++ Robert Sedgewick) は、和集合操作が「入力ペアごとに配列全体をスキャンする」ことを示しています(コードの 9 行目と 10 行目)。

基本的に、ノードqの値を、ノードpと同じ値を持つ他のすべてのノードにコピーしています。この操作を UNION と名付けたのはなぜですか?

コードは本から直接コピーされます。

#include <iostream>
const int N = 10000;
int main() {
int i, p, q, id[N];
for( i = 0; i < N; i++ ) id[i] = i;
while( cin >> p >> q ) {
    int t = id[p];
    if ( t = id[q] ) continue;              //quick find operation
    for ( i = 0; i < N; i++ )               //---> union why?
        if ( id[i] == t) id[i] = id[q];
    cout << " " << p << " " << q << endl;
}
}
4

2 に答える 2

1

サポートされている操作のセットを見てください。「すべての要素をリストする」ように要求する方法がなく、単に挿入、検索、結合する方法がない場合、これらの操作を使用して、要素の重複があるかどうかを判断する方法はありません。これにより、サポートされている操作がより効率的になりますが、(ユーザーが知る限り) セットのように動作します。

于 2012-02-10T15:40:12.607 に答える