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à:
4Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
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!
 và giải thuật){kind=link}