【C++】データセット内のモード（最頻値）を見つけるプログラム

これは、データセットの中からモード（最頻値）を求めるためのC++プログラムです。連結リストを使用して重複しないデータを管理し、各要素の出現回数をカウントすることで、最も多く出現した値を効率的に特定します。

アルゴリズム

開始
　　セットにデータを挿入する関数 insertinset() を定義する。
　　新しいノード（newnode）と一時ノード（t）を作成する。
　　newnode を使って、リストに挿入するノードを準備する。
　　head が NULL の場合は、
　　　　新しいノードを head に代入し、カウントを1増やす。
　　挿入の過程で挿入ソートを実行し、常にデータをソートされた状態に保つ。
　　newnode->data がセット内の既存の要素と一致する場合は、
　　　　該当要素のカウントを1増やすだけでよい。
終了

サンプルコード

#include <iostream>
using namespace std;
struct set // 変数を宣言するための構造体set
{
    int data;
    int cnt;
    set *n;
};
set* insertinset(set *head, int n) {
    set *newnode = new set; // 構造体setの変数を使用する
    set *t = new set;
    newnode->data = n;
    newnode->cnt = 0;
    newnode->n = NULL;
    if(head == NULL) {
        head = newnode;
        head->cnt++;
        return head;
    } else {
        t = head;
        if(newnode->data < head->data) {
            newnode->n = head;
            head = newnode;
            newnode->cnt++;
            return head;
        } else if(newnode->data == head->data) {
            head->cnt++;
            return head;
        }
        while(t->n!= NULL) {
            if(newnode->data == (t->n)->data) {
                (t->n)->cnt++;
                return head;
            }
            if(newnode->data < (t->n)->data)
                break;
            t=t->n;
        }
        newnode->n = t->n;
        t->n = newnode;
        newnode->cnt++;
        return head;
    }
}
int main() {
    int n, i, num, max = 0, c;
    set *head = new set;
    head = NULL;
    cout<<"\nEnter the number of data element to be sorted: ";
    cin>>n;
    for(i = 0; i < n; i++) {
        cout<<"Enter element "<<i+1<<": ";
        cin>>num;
        head = insertinset(head, num); // 関数を呼び出す
    }
    cout<<"\nSorted Distinct Data ";
    while(head != NULL) // headがNULLでない間
    {
        if(max < head->cnt) {
            c = head->data;
            max = head->cnt;
        }
        cout<<"->"<<head->data<<"("<<head->cnt<<")"; // データの出現回数を出力
        head = head->n;
    }
    cout<<"\nThe Mode of given data set is "<<c<<" and occurred "<<max<<" times.";
    return 0;
}

実行結果

Enter the number of data element to be sorted: 10
Enter element 1: 1
Enter element 2: 2
Enter element 3: 0
Enter element 4: 2
Enter element 5: 3
Enter element 6: 7
Enter element 7: 6
Enter element 8: 2
Enter element 9: 1
Enter element 10: 1
Sorted Distinct Data ->0(1)->1(3)->2(3)->3(1)->6(1)->7(1)
The Mode of given data set is 1 and occurred 3 times.

プログラムの解説

このプログラムは、以下の手順で動作します。

1. 構造体 set の定義： 各ノードはデータ値（data）、出現回数（cnt）、次のノードへのポインタ（n）を持っています。
2. insertinset() 関数： 新しいデータを挿入する際、挿入ソートの要領で適切な位置にノードを配置します。同じ値がすでに存在する場合は新しいノードを作らず、該当ノードのカウントを1増やすだけです。これにより、リストには重複しない値のみが常にソートされた状態で保持されます。
3. main() 関数： ユーザーからデータの個数と各要素を入力してもらい、その都度 insertinset() を呼び出します。その後、リストを先頭から走査して最大カウントを持つ要素（モード）を特定し、ソート済みの重複なしデータとともに結果を出力します。

上記の実行例では、10個のデータを入力すると、ソート済みの重複なしデータとそれぞれの出現回数が「->値(回数)」の形式で表示され、モードが「1」で3回出現したことがわかります。なお、複数の値が同率で最多出現となる場合は、先に走査された値が結果として表示される点に注意してください。