【C言語】2つの配列の和集合を求めるプログラムの書き方と解説

和集合(union)とは、2つの集合に含まれるすべての要素を重複なくまとめたものです。C言語では、この和集合演算を配列を使って簡単に実装できます。本記事では、2つの整数型配列の和集合を求めるCプログラムを、アルゴリズムの考え方から実際の実行結果まで、初心者にもわかりやすく解説します。

和集合演算とは

たとえば、次のような2つの配列を考えてみましょう。

• 配列1 = {1, 2, 3, 4, 6}
• 配列2 = {1, 2, 5, 6, 7}

この2つの配列の和集合は、次のように表されます。

配列1 ∪ 配列2 = {1, 2, 3, 4, 6} ∪ {1, 2, 5, 6, 7}
= {1, 2, 3, 4, 5, 6, 7}

つまり、両方の配列に現れるすべての要素を集め、重複する値を1つにまとめた集合が和集合です。

和集合を求めるロジック

1. 2つの配列を1つに連結する

まず、配列aの全要素と配列bの全要素を、新しい配列uniに順番にコピーします。

for(i=0;i<size1;i++){
    uni[j]=a[i];
    j++;
}
for(i=0;i<size2;i++){
    uni[j]=b[i];
    j++;
}

2. 重複した要素を削除する

次に、連結した配列内の重複要素を取り除きます。各要素について、それ以降の要素と比較し、同じ値が見つかれば後ろの要素を前に詰めて削除していきます。

int removerepeated(int size,int a[]){
    int i,j,k;
    for(i=0;i<size;i++){
        for(j=i+1;j<size;){
            if(a[i]==a[j]){
                for(k=j;k<size;k++){
                    a[k]=a[k+1];
                }
                size--;
            }else{
                j++;
            }
        }
    }
    return(size);
}

完全なCプログラム

以下が、2つの配列に対して和集合演算を実行するCプログラムの全体像です。処理の流れは「入力 → 連結 → ソート → 重複削除 → 出力」となっています。

#include<stdio.h>
int removerepeated(int size,int a[]);
void sort(int size,int a[]);
main(){
    int i,size1,size2,size,j=0,k;
    printf("Enter size of an array1\n");
    scanf("%d",&size1);
    printf("Enter size of an array2\n");
    scanf("%d",&size2);
    int a[size1],b[size2],uni[size1+size2];
    printf("Enter numbers for array 1\n");
    for(i=0;i<size1;i++){
        scanf("%d",&a[i]);
    }
    printf("Enter numbers for array 2\n");
    for(i=0;i<size2;i++){
        scanf("%d",&b[i]);
    }
    /* 和集合の開始 */
    for(i=0;i<size1;i++){
        uni[j]=a[i];
        j++;
    }
    for(i=0;i<size2;i++){
        uni[j]=b[i];
        j++;
    }
    /* ソート */
    sort(size1+size2,uni);
    /* 重複要素の削除 */
    size=removerepeated(size1+size2,uni);
    printf("Array after Union \n");
    for(i=0;i<size;i++){
        printf("%d\n",uni[i]);
    }
}
int removerepeated(int size,int a[]){
    int i,j,k;
    for(i=0;i<size;i++){
        for(j=i+1;j<size;){
            if(a[i]==a[j]){
                for(k=j;k<size;k++){
                    a[k]=a[k+1];
                }
                size--;
            }else{
                j++;
            }
        }
    }
    return(size);
}
void sort(int size,int a[]){
    int i,j,temp;
    for(i=0;i<size;i++){
        for(j=i+1;j<size;j++){
            if(a[i]>a[j]){
                temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
}

実行結果

上記のプログラムをコンパイルして実行すると、次のような出力が得られます。配列1に{1, 2, 3, 4}、配列2に{3, 5, 6}を入力した場合、共通する「3」が1つにまとめられ、和集合として{1, 2, 3, 4, 5, 6}が出力されます。

Enter size of an array1
4
Enter size of an array2
3
Enter numbers for array 1
1
2
3
4
Enter numbers for array 2
3
5
6
Array after Union
1
2
3
4
5
6

補足：計算量と改良のポイント

このプログラムでは、ソートと重複削除のどちらも二重ループを使用しているため、計算量はO(n²)となります。そのため、要素数が多いデータを扱う場合は、標準ライブラリのqsort関数による高速なソートや、ハッシュテーブルを利用した重複管理を検討すると効率的です。

また、サンプルコードでは可変長配列(VLA)を使用しています。これはC99以降でサポートされる機能なので、古いコンパイラを使用する場合は注意が必要です。さらに、main関数は戻り値の型を明示して「int main(void)」と宣言し、最後に「return 0;」を返すのが現代的なC言語の作法として推奨されます。