C++で指定された数kで割り切れるリンクリストの最大要素と最小要素

リンクリストは、要素がポインタを介してリンクされている線形データ構造です。リンクリストの各要素またはノードには、データ部分とリンクがあります。または、次の要素へのポインタを順番に言うことができます。要素は、メモリ内で連続していない場所を取ることができます。

データ部分と次の要素へのリンクがある単一リンクリストが与えられます。もう1つの入力は数値Kです。タスクは、数値Kで割り切れるリンクリストの最大要素と最小要素を見つけることです。線形リンクリストは、一方向にのみ移動できます。各ノードで、データ部分の分割可能性をKで確認します。その数がこれまでに見つかった最大値または最小値である場合は、MaxDとMinDの値を更新します。

入力

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

出力

Maximum element which is divisible by K : 20
Maximum element which is divisible by K : 5

説明 −ヘッドノードからトラバースし、データ部分をKで分割し続け、完全に分割可能かどうか、つまり余りが0になるかどうかを確認します。

5、10、および20のみが5で割り切れます。そのうち、5が最小で、20が最大です。

入力

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

出力

Maximum element which is divisible by K : 144
Maximum element which is divisible by K : 12

説明 −ヘッドノードからトラバースし、データ部分をKで分割し続け、完全に分割可能かどうか、つまり余りが0になるかどうかを確認します。

12と144のみが4で割り切れますが、そのうち12が最小で、144が最大です。

以下のプログラムで使用されているアプローチは次のとおりです

• リンクリストノードを作成します。ここでは、情報部分と次のポインタを持つクラスSLLnodeを作成しました。

• リンクリストを作成します。ここでは、SLLnodeオブジェクトをメンバーとして持つクラスSLListを作成しました。したがって、SLListはSLLノードで構成されます。

• 関数addtohead（int）は、このリストにノードを追加しています。

• SLListに要素を追加するために、LISTという名前のSLListオブジェクトを使用してaddtohead（int）を呼び出しています。

• SLListが作成されたら、関数Divisible（SLLnode、int）を呼び出します。この関数は、リストの先頭と整数Kの2つの入力パラメーターを取ります。

• ここで、Divisible内で、2つの変数maxDとminDを使用して、指定された数値Kで割り切れるリンクリストのMaximum要素とMinimum要素を格納します。

• maxDは-1で初期化され、minDは9999で初期化されます。これは、入力が存在する範囲と見なされます。

• forループの内側では、リンクリストを先頭からトラバースします。この変数の開始は頭を指しています。

• 各ノードの情報部分をmaxDおよびminDと比較し、それをKで除算します。現在のノードの情報が分割可能で、minD未満の場合は、minDを現在の情報部分で更新します。

• 現在のノードの情報がKで割り切れ、maxDより大きい場合は、maxDを現在の情報部分で更新します。

• 得られた結果をminDとmaxDで印刷します。

例

#include<iostream.h>
#include<process.h>
#include<conio.h>
class SLLnode{
   public:
   int info;
   SLLnode *next;
   SLLnode(int e1,SLLnode *ptr=0){
      info=e1;
      next=ptr;
   }
};
class SLList{
   public:
   SLLnode *head;
   SLList()
   { head=0; }
   void addtohead(int); };
   void SLList::addtohead(int el)
   { head=new SLLnode(el,head); }
   void Divisible(SLLnode* head, int K){
      int minD=9999;
      int maxD=-1;
      SLLnode* start=head;
      for(start;start->next!=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 << "Max Element divisible by K: " << maxD << endl;
      cout << "Min Element divisible by K: " << minD;
}
// Driver Code
int main(){
   clrscr();
   // Start with empty list
   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);
   getch();
   return 0;
}

出力

上記のコードを実行すると、次の出力が生成されます-

Max Element divisible by K: 90
Min Element divisible by K: 45