Trong bài toán này, chúng ta được cung cấp một danh sách liên kết vòng. Nhiệm vụ của chúng tôi là tạo một chương trình để tìm tổng số các nút của Danh sách được liên kết theo hình tròn.
Chúng tôi chỉ cần thêm tất cả các giá trị nút của danh sách được liên kết.
Một số định nghĩa quan trọng
-
Danh sách được Liên kết là một chuỗi các cấu trúc dữ liệu, được kết nối với nhau thông qua các liên kết.
-
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.
Bây giờ, hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào
14 -> 1 -> 7 -> 9 -> 2 -> 6
Đầu ra
39
Giải thích
sum = 14 + 1 + 7 + 9 + 2 + 6 = 39
Để giải quyết vấn đề này, chúng tôi sẽ duyệt qua danh sách được liên kết. Và thêm giá trị của mỗi nút vào một biến tổng. Sau đó, trả về tổng khi toàn bộ danh sách được duyệt qua.
Thuật toán
Bước 1 - Khởi tạo sum =0 và sumPointer =
Bước 2 - Do-while sumPointer! =Head. Làm
Bước 2.1 - Thêm giá trị của nút hiện tại vào tổng, tức là sum + =sumPointer → giá trị.
Bước 2.2 - Con trỏ tăng dần đến nút tiếp theo, tức là sumPointer =sumPointer → tiếp theo.
Bước 3 - Trả lại Tổng.
Ví dụ
Chương trình minh họa giải pháp,
#include <iostream>
using namespace std;
struct Node {
int data;
struct Node* next;
};
void pushNode(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 (*head_ref != NULL) {
while (temp->next != *head_ref)
temp = temp->next;
temp->next = ptr1;
}
else
ptr1->next = ptr1;
*head_ref = ptr1;
}
int CalcSumCirList(struct Node* head) {
struct Node* sumPointer = head;
int sum = 0;
if (head != NULL) {
do {
sumPointer = sumPointer->next;
sum += sumPointer->data;
}
while (sumPointer != head);
}
return sum;
}
int main(){
struct Node* head = NULL;
pushNode(&head, 4);
pushNode(&head, 7);
pushNode(&head, 12);
pushNode(&head, 1);
pushNode(&head, 9);
pushNode(&head, 6);
cout<<"The sum of Circular linked list is "<<CalcSumCirList(head);
return 0;
} Đầu ra
The sum of Circular linked list is 39