C++の循環リンクリストでノードをカウントします

ノードを含む循環リンクリストが与えられ、タスクは循環リンクリストに存在するノードの数を計算することです。

循環リンクリストは、最初の要素が最後の要素を指し、最後の要素が最初の要素を指すリンクリストのバリエーションです。単一リンクリストと二重リンクリストの両方を循環リンクリストにすることができます。

以下のプログラムでは、単一リンクリストを循環リンクリストとして実装し、その中のノード数を計算しています。

例

Input − nodes-: 20, 1, 2, 3, 4, 5
Output − count of nodes are-: 6
Input − nodes-: 20, 1, 2, 3, 4, 5, 7, 8, 9, 12
Output − count of nodes are-: 10

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

• ノードが保持するアドレスとデータを含む、単一リンクリストの構造を作成します。

• データをノードに挿入するために使用されるpush（）関数を作成します。

• 最後のノードに、最初のノードのアドレスを格納して、単一リンクリストを循環リンクリストとして機能させます。

• 循環リンクリストに存在するノードの総数をカウントするカウント関数を作成します。

例

#include <stdio.h>
#include <stdlib.h>
/* Defining a node */
struct node {
   int data;
   struct node* next;
};
// Inserting node in Circular list
void push(struct node** head_ref, int data){
   struct node* ptr1 = (struct node*)malloc(sizeof(struct node));
   struct node* temp = *head_ref;
   ptr1->data = data;
   ptr1->next = *head_ref;
   // going to the last node to insert new element.
   if (*head_ref != NULL){
      while (temp->next != *head_ref){
         temp = temp->next;
      }
      temp->next = ptr1;
   } else{
      ptr1->next = ptr1; //for first node
   }
   *head_ref = ptr1;
}
// Function to count the number of nodes
int count_fun(struct node* head){
   struct node* temp = head;
   int result = 0;
   if (head != NULL){
      do {
         temp = temp->next;
         result++;
      } while (temp != head);
   }
   return result;
}
int main(){
   /* Initializing the list as empty */
   struct node* head = NULL;
   push(&head, 10);
   push(&head, 20);
   push(&head, 30);
   push(&head, 40);
   printf("count of nodes are: %d", count_fun(head));
   return 0;
}

出力

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

count of nodes are: 4