Đếm số nút trong danh sách liên kết tròn trong C ++

Chúng tôi được cung cấp một danh sách liên kết vòng tròn với các nút và nhiệm vụ là tính toán số lượng các nút có trong danh sách liên kết vòng tròn.

Danh sách liên kết hình tròn là một biến thể của danh sách được liên kết trong đó phần tử đầu tiên trỏ đến phần tử cuối cùng và phần tử cuối cùng trỏ đến phần tử đầu tiên. Cả Danh sách liên kết đơn và Danh sách được liên kết kép đều có thể được tạo thành một danh sách liên kết vòng tròn.

Trong chương trình dưới đây, chúng tôi đang triển khai một danh sách được liên kết đơn lẻ dưới dạng danh sách liên kết vòng tròn để tính toán số lượng các nút trong đó.

Ví dụ

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

Phương pháp tiếp cận được sử dụng trong chương trình dưới đây như sau -

• Tạo cấu trúc cho một danh sách được liên kết đơn lẻ bao gồm địa chỉ và dữ liệu do nút nắm giữ.

• Tạo một hàm push () sẽ được sử dụng để chèn dữ liệu vào nút.

• Trong nút cuối cùng, hãy lưu trữ địa chỉ của nút đầu tiên để tạo chức năng danh sách liên kết đơn lẻ như một danh sách liên kết vòng.

• Tạo một hàm đếm sẽ đếm tổng số nút có trong danh sách liên kết vòng.

Ví dụ

#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;
}

Đầu ra

Nếu chúng ta chạy đoạn mã trên, nó sẽ tạo ra kết quả sau -

count of nodes are: 4