ในปัญหานี้ เราได้รับรายการเชื่อมโยงแบบวงกลม งานของเราคือสร้างโปรแกรมเพื่อค้นหาผลรวม ของโหนดของรายการเชื่อมโยงแบบวงกลม
เราเพียงแค่ต้องเพิ่มค่าโหนดทั้งหมดของรายการที่เชื่อมโยง
คำจำกัดความที่สำคัญบางประการ
-
Linked List คือลำดับของโครงสร้างข้อมูลซึ่งเชื่อมต่อกันผ่านลิงก์
-
รายการที่เชื่อมโยงแบบวงกลมคือรูปแบบหนึ่งของรายการที่เชื่อมโยง โดยองค์ประกอบแรกชี้ไปที่องค์ประกอบสุดท้าย และองค์ประกอบสุดท้ายชี้ไปที่องค์ประกอบแรก ทั้งรายการที่เชื่อมโยงแบบเดี่ยวและรายการที่เชื่อมโยงแบบทวีคูณสามารถทำเป็นรายการที่เชื่อมโยงแบบวงกลมได้
ตอนนี้ มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ป้อนข้อมูล
14 -> 1 -> 7 -> 9 -> 2 -> 6
ผลผลิต
39
คำอธิบาย
sum = 14 + 1 + 7 + 9 + 2 + 6 = 39
เพื่อแก้ปัญหานี้ เราจะสำรวจรายการที่เชื่อมโยง และเพิ่มค่าของแต่ละโหนดให้กับตัวแปรผลรวม จากนั้นส่งคืนผลรวม เมื่อข้ามรายการทั้งหมดแล้ว
อัลกอริทึม
ขั้นตอนที่ 1 − เริ่มต้น sum =0 และ sumPointer =
ขั้นตอนที่ 2 − ทำในขณะที่ sumPointer !=หัว ทำ
ขั้นตอนที่ 2.1 − เพิ่มค่าของโหนดปัจจุบันไปยังผลรวม เช่น sum +=sumPointer → ค่า
ขั้นตอนที่ 2.2 − เพิ่มตัวชี้ไปยังโหนดถัดไป เช่น sumPointer =sumPointer → ถัดไป
ขั้นตอนที่ 3 − ผลตอบแทนรวม
ตัวอย่าง
โปรแกรมเพื่อแสดงวิธีแก้ปัญหา
#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;
} ผลลัพธ์
The sum of Circular linked list is 39
