【C++】連結リスト内で指定した数Kで割り切れる最大要素と最小要素を求める方法

連結リストとは

連結リスト(リンクリスト)は、要素同士がポインタで連結された線形データ構造です。各要素(ノード)は「データ部分」と「次の要素を指すリンク(ポインタ)」を持ち、メモリ上の連続していない場所に配置されることもあります。

本記事では、データ部分と次ノードへのリンクを持つ片方向連結リストと、整数Kが与えられます。目的は、連結リスト内の要素のうち「Kで割り切れる」要素の最大値と最小値を見つけることです。線形連結リストは一方向にしか走査できないため、ヘッド(先頭)ノードから順に各ノードを訪問し、そのデータ部分がKで割り切れるかどうかを判定します。現在のノードの値が、それまでに見つかった最大値・最小値よりも適していれば、変数MaxD(最大値)・MinD(最小値)を更新していきます。

入力例1

SList : 5-->2-->10-->12-->3-->20-->7、K=5

出力例1

Kで割り切れる最大要素 : 20
Kで割り切れる最小要素 : 5

解説 − ヘッドノードから順に走査し、各ノードのデータをKで割って、余りが0(完全に割り切れる)かどうかを確認します。

この例では、5・10・20だけが5で割り切れ、そのうち最小は5、最大は20です。

入力例2

SList : 12-->2-->5-->18-->3-->144-->7、K=4

出力例2

Kで割り切れる最大要素 : 144
Kで割り切れる最小要素 : 12

解説 − 同様にヘッドノードから走査し、各ノードのデータがKで割り切れるか(余りが0か)を確認します。

この例では、12と144だけが4で割り切れ、そのうち最小は12、最大は144です。

プログラムのアプローチ

• 連結リストのノードを作成します。ここでは、データ部(info)と次ノードへのポインタ(next)を持つクラスSLLnodeを定義しています。
• 連結リスト本体を作成します。SLLnodeオブジェクトをメンバーに持つクラスSLListを定義し、SLListはSLLnodeによって構成されます。
• 関数addtohead(int)は、リストの先頭に新しいノードを追加します。
• SLListオブジェクトLISTに対してaddtohead(int)を呼び出すことで、リストへ要素を追加していきます。
• リストの構築が完了したら、先頭ノードと整数Kを引数に取る関数Divisible(SLLnode*, int)を呼び出します。
• Divisible関数内では、Kで割り切れる最大値・最小値を格納するための変数maxDとminDを用意します。
• maxDは-1、minDは9999で初期化します。これは入力値がこの範囲内にあると想定した初期値です。
• forループで、先頭ノードから連結リストを走査します。変数startが現在のノードを指します。
• 各ノードのinfoとmaxD・minDを比較しながら、Kで割り切れるかどうかを判定します。現在のノードの値がKで割り切れ、かつminDより小さければ、minDを現在の値で更新します。
• 現在のノードの値がKで割り切れ、かつmaxDより大きければ、maxDを現在の値で更新します。
• 最後に、minDとmaxDに求まった結果を出力します。

なお、リスト内にKで割り切れる要素がひとつも存在しない場合は、maxD=-1・minD=9999のままとなるため、実用上は「該当する要素なし」の判定処理を追加しておくとより安全です。

サンプルコード

以下は、上記のアルゴリズムをC++で実装した例です。最新の標準C++環境でそのままコンパイルできるよう、ヘッダや入出力の記述を現代的なスタイルに整理しています。

#include <iostream>
using namespace std;

// 連結リストのノード
class SLLnode {
public:
    int info;          // データ部分
    SLLnode *next;     // 次ノードへのポインタ
    SLLnode(int el, SLLnode *ptr = 0) {
        info = el;
        next = ptr;
    }
};

// 連結リスト本体
class SLList {
public:
    SLLnode *head;
    SLList() { head = 0; }
    void addtohead(int);
};

// 先頭にノードを追加
void SLList::addtohead(int el) {
    head = new SLLnode(el, head);
}

// Kで割り切れる最大値・最小値を求める
void Divisible(SLLnode* head, int K) {
    int minD = 9999;
    int maxD = -1;
    SLLnode* start = head;
    for (; start != NULL; start = start->next) {
        if ((start->info < minD) && (start->info % K == 0))
            minD = start->info;
        if ((start->info > maxD) && (start->info % K == 0))
            maxD = start->info;
    }
    cout << "Kで割り切れる最大要素: " << maxD << endl;
    cout << "Kで割り切れる最小要素: " << minD << endl;
}

// ドライバーコード
int main() {
    // 空のリストから開始
    SLList LIST;
    LIST.addtohead(50);
    LIST.addtohead(21);
    LIST.addtohead(32);
    LIST.addtohead(45);
    LIST.addtohead(11);
    LIST.addtohead(23);
    LIST.addtohead(90);
    LIST.addtohead(56);

    int K = 5;
    Divisible(LIST.head, K);
    return 0;
}

出力結果

上記のコードを実行すると、以下の出力が得られます −

Kで割り切れる最大要素: 90
Kで割り切れる最小要素: 45

addtoheadは常に先頭へ挿入するため、リストの実際の並びは 56→90→23→11→45→32→21→50 となります。このうち5で割り切れるのは90・45・50であり、最大値は90、最小値は45です。計算量はリストを一度走査するだけなので、要素数をNとするとO(N)で効率的に求められます。