はじめに

2つのリスト（または配列）から共通する要素を求める問題は、よく出題される基本的なアルゴリズム問題です。C言語でこの問題を解く方法を紹介します。まず、リスト内の要素を比較し、共通する部分を抽出するアルゴリズムを考えます。

問題設定

2つの整数型リスト（または配列）があります。それぞれのリストには重複を許さない整数が格納されており、2つのリストに共通する整数を求めるプログラムを作成することが目的です。

例えば、次のような2つのリストが与えられたとしましょう。

            リスト1: [1, 2, 3, 4, 5]
            リスト2: [3, 4, 5, 6, 7]
        

この場合、共通する要素は 3, 4, 5 です。

アルゴリズムの説明

この問題を解くための基本的なアルゴリズムは、以下のステップで進めます。

• 1. 2つのリストを用意する。
• 2. リスト1の各要素に対して、リスト2にその要素が含まれているかを確認する。
• 3. 含まれていれば、その要素を結果として記録する。

効率性を考慮すると、リストのサイズが大きくなると処理時間が増加します。したがって、以下のように2重ループを使って各要素を比較します。

            for (i = 0; i < size1; i++) {
                for (j = 0; j < size2; j++) {
                    if (list1[i] == list2[j]) {
                        printf("%d ", list1[i]);
                    }
                }
            }
        

この方法は直感的ですが、リストのサイズが大きくなると計算量が増えてしまうため、改良が必要です。

実装方法

まず、リスト1とリスト2を配列として定義します。その後、上記のアルゴリズムに従って共通の要素を求めます。以下にその実装例を示します。

#include 

int main() {
    int list1[] = {1, 2, 3, 4, 5};
    int list2[] = {3, 4, 5, 6, 7};
    int size1 = sizeof(list1) / sizeof(list1[0]);
    int size2 = sizeof(list2) / sizeof(list2[0]);
    
    printf("共通の要素: ");
    for (int i = 0; i < size1; i++) {
        for (int j = 0; j < size2; j++) {
            if (list1[i] == list2[j]) {
                printf("%d ", list1[i]);
            }
        }
    }
    printf("\n");
    
    return 0;
}
        

このコードは、2つのリストを比較して共通の要素を標準出力に表示します。上記のリスト例の場合、出力は次のようになります。

共通の要素: 3 4 5 
        

例

さらに、異なる例で実行してみましょう。次のリストを考えます。

            リスト1: [10, 20, 30, 40]
            リスト2: [25, 30, 35, 40]
        

この場合、共通する要素は 30, 40 となります。プログラムを実行すると、次のような結果が得られます。

共通の要素: 30 40 
        

このように、異なる入力に対しても正しく共通の要素を求めることができます。

結論

今回は、C言語を使用して2つのリストから共通する要素を求めるプログラムを解説しました。最初の実装はシンプルで理解しやすいですが、リストが大きくなると効率的ではありません。今後の課題として、効率を改善するために、ハッシュテーブルを用いたアルゴリズムに改良することも考えられます。さらに、別の方法として、ソートしてから線形探索を行うアプローチも有効です。