Chào ace, bài này chúng ta sẽ tìm hiểu về Đếm số lượng các nodes trong danh sách liên kết vòng trong series tự học về cấu trúc dữ liệu(CTDL) và giải thuật, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, độ phức tạp, ứng dụng của nó, code ví dụ…) về nó thông qua các phần sau.

Trong bài học này chúng ta sẽ tìm hiểu về cách để đếm số lượng các nodes bên trong một danh sách liên kết vòng

Xét ví dụ được minh họa bởi hình sau:

Ta có thể thấy rằng, danh sách liên kết vòng trong hình trên có 5 nodes

Để có thể đếm được số lượng nodes ở trong danh sách liên kết vòng, chúng ta chỉ cần duyệt qua toàn bộ danh sách, trong khi duyệt chúng ta vẫn lưu lại số lượng các nodes đã duyệt qua

Ví dụ đếm số lượng nodes trong danh sách liên kết vòng được viết bằng ngôn ngữ C/C++:


// C program to count number of nodes in 
// a circular linked list. 
#include <stdio.h> 
#include <stdlib.h> 
  
/* structure for a node */
struct Node { 
    int data; 
    struct Node* next; 
}; 
  
/* Function to insert a node at the beginning 
   of a Circular linked 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; 
  
    /* If the linked list is not NULL then set 
       the next of last node */
    if (*head_ref != NULL) { 
        while (temp->next != *head_ref) 
            temp = temp->next; 
        temp->next = ptr1; 
    } else
        ptr1->next = ptr1; /*For the first node */
  
    *head_ref = ptr1; 
} 
  
/* Function to print nodes in a given Circular 
   linked list */
int countNodes(struct Node* head) 
{ 
    struct Node* temp = head; 
    int result = 0; 
    if (head != NULL) { 
        do { 
            temp = temp->next; 
            result++; 
        } while (temp != head); 
    } 
  
    return result; 
} 
  
/* Driver program to test above functions */
int main() 
{ 
    /* Initialize lists as empty */
    struct Node* head = NULL; 
    push(&head, 12); 
    push(&head, 56); 
    push(&head, 2); 
    push(&head, 11); 
  
    printf("%d", countNodes(head)); 
  
    return 0; 
} 

Sau đây là ví dụ được viết bằng ngôn ngữ Java:

// Java program to count number of nodes in  
// a circular linked list.  
class GFG 
{ 
  
/* ure for a node */
static class Node 
{  
    int data;  
    Node next;  
};  
  
/* Function to insert a node at the beginning  
of a Circular linked list */
static Node push( Node head_ref, int data)  
{  
    Node ptr1 = new Node();  
    Node temp = head_ref;  
    ptr1.data = data;  
    ptr1.next = head_ref;  
  
    /* If linked list is not null then set  
    the next of last node */
    if (head_ref != null) 
    {  
        while (temp.next != head_ref)  
            temp = temp.next;  
        temp.next = ptr1;  
    } else
        ptr1.next = ptr1; /*For the first node */
  
    head_ref = ptr1; 
    return head_ref; 
}  
  
/* Function to print nodes in a given Circular  
linked list */
static int countNodes( Node head)  
{  
    Node temp = head;  
    int result = 0;  
    if (head != null) 
    {  
        do 
        {  
            temp = temp.next;  
            result++;  
        } while (temp != head);  
    }  
  
    return result;  
}  
  
/* Driver program to test above functions */
public static void main(String args[]) 
{  
    /* Initialize lists as empty */
    Node head = null;  
    head = push(head, 12);  
    head = push(head, 56);  
    head = push(head, 2);  
    head = push(head, 11);  
  
    System.out.printf("%d", countNodes(head));  
} 
}  

Và tiếp theo là ví dụ được minh họa bằng Python3:

# Python3 program to count number of nodes in 
# a circular linked list. 
  
# structure for a node 
class Node:  
    def __init__(self, data):  
        self.data = data  
        self.next = None
  
# Function to insert a node at the beginning 
# of a Circular linked list */ 
def push(head_ref,data): 
  
    ptr1 = Node(0) 
    temp = head_ref 
    ptr1.data = data 
    ptr1.next = head_ref 
  
    # If the linked list is not None then set 
    # the next of last node  
    if (head_ref != None) : 
        while (temp.next != head_ref): 
            temp = temp.next
        temp.next = ptr1 
    else: 
        ptr1.next = ptr1 #For the first node */ 
  
    head_ref = ptr1 
    return head_ref 
  
# Function to print nodes  
# in a given Circular linked list  
def countNodes(head): 
  
    temp = head 
    result = 0
    if (head != None) : 
        while True : 
            temp = temp.next
            result = result + 1
            if (temp == head): 
                break
      
    return result 
  
# Driver Code  
if __name__=='__main__':  
  
    # Initialize lists as empty */ 
    head = None
    head = push(head, 12) 
    head = push(head, 56) 
    head = push(head, 2) 
    head = push(head, 11) 
  
    print( countNodes(head)) 

Khi sử dụng ngôn ngữ C#, chúng ta sẽ viết code như sau:

// C# program to count number of nodes in  
// a circular linked list.  
using System; 
  
class GFG  
{  
  
/* structure for a node */
public class Node  
{  
    public int data;  
    public Node next;  
};  
  
/* Function to insert a node at the beginning  
of a Circular linked list */
static Node push( Node head_ref, int data)  
{  
    Node ptr1 = new Node();  
    Node temp = head_ref;  
    ptr1.data = data;  
    ptr1.next = head_ref;  
  
    /* If linked list is not null then set  
    the next of last node */
    if (head_ref != null)  
    {  
        while (temp.next != head_ref)  
            temp = temp.next;  
        temp.next = ptr1;  
    } else
        ptr1.next = ptr1; /*For the first node */
  
    head_ref = ptr1;  
    return head_ref;  
}  
  
/* Function to print nodes in a given Circular  
linked list */
static int countNodes( Node head)  
{  
    Node temp = head;  
    int result = 0;  
    if (head != null)  
    {  
        do
        {  
            temp = temp.next;  
            result++;  
        } while (temp != head);  
    }  
  
    return result;  
}  
  
/* Driver code */
public static void Main(String []args)  
{  
    /* Initialize lists as empty */
    Node head = null;  
    head = push(head, 12);  
    head = push(head, 56);  
    head = push(head, 2);  
    head = push(head, 11);  
  
    Console.Write( countNodes(head));  
}  
}  

Kết quả in ra là:

4

Nguồn và Tài liệu tiếng anh tham khảo:

Tài liệu từ cafedev:

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:

Chào thân ái và quyết thắng!

Bạn thấy chất lượng bài viết này tốt không?

Thả 1->5 ❤️ để đánh giá chất lượng bài viết.

Xếp hạng 0 / 5. Số lượng đánh giá 0

Hãy đánh giá để ủng hộ và giúp chúng tôi cải thiện bài viết tốt hơn cho bạn!

Chúng tôi xin lỗi vì bài viết chưa được chất lượng. Chúng tôi sẽ cải thiện nó sớm nhất!

Hãy gửi phản hồi của bạn cho chúng tôi

Tại sao bài viết này lại không chất lượng?

Đăng ký kênh youtube để ủng hộ Cafedev nha các bạn, Thanks you!