C++实现链表中可被给定数字k整除的最大和最小元素

链表是一种线性数据结构，其中元素通过指针链接。链表的每个元素或节点都包含数据部分和链接，或者可以说指向序列中下一个元素的指针。这些元素可以在内存中占据非连续的位置。

我们得到一个单链表，其中包含数据部分和指向下一个元素的链接。另一个输入是一个数字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, 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中，只有12和144能被4整除，其中12最小，144最大。

下面程序中使用的步骤如下

  • 创建一个链表节点。这里我们创建了一个名为SLLnode的类，它具有信息部分和下一个指针。

  • 创建一个链表。这里我们创建了一个名为SLList的类，其成员是SLLnode对象。因此，SLList由SLLnode组成。

  • 函数addtohead(int)将节点添加到此列表。

  • 为了向SLList添加元素，我们使用名为LIST的SLList对象调用addtohead(int)。

  • 创建SLList后，我们调用函数Divisible(SLLnode,int)，它接受列表的头和整数K作为两个输入参数。

  • 现在在Divisible函数内部，我们使用两个变量maxD和minD来存储链表中可被给定数字K整除的最大和最小元素。

  • maxD初始化为-1，minD初始化为9999。这被认为是输入所在的范围。

  • 在for循环内，我们从头开始遍历链表。为此，变量start指向头。

  • 将每个节点的信息部分与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;
}

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

输出

如果我们运行上面的代码，它将生成以下输出：

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

更新于：2020年8月14日

浏览量：136

开启您的职业生涯

完成课程后获得认证

开始学习
广告