Trong bài toán này, ta được cho danh sách liên kết với nút chứa hai giá trị và con trỏ. Nhiệm vụ: tạo chương trình tìm tổng phần tử nhỏ hơn của mỗi nút trong danh sách liên kết.
Mỗi nút có hai giá trị X và Y. Chương trình tìm min(X, Y) của mỗi nút, cộng dồn để ra kết quả.
Đầu vào** –
(5,2)→(7,9)→(6,3)→(36,24)→(19,26)→null
Đầu ra** –
55
Giải thích** – Min của mỗi nút:
node1: min = 2 node2: min = 7 node3: min = 3 node4: min = 24 node5: min = 19 Tổng = 55
Giải pháp: duyệt danh sách, mỗi nút tính min(X,Y), cộng vào biến tổng, trả về tổng khi hết danh sách.
Thuật toán
Khởi tạo** – sum = 0
Bước 1** – Duyệt danh sách và thực hiện:
Bước 1.1** – Tìm min(head→X, head→Y).
Bước 1.2** – Cộng min vào sum.
Bước 2** – Trả về Sum.
Ví dụ
Chương trình minh họa:
#include <iostream>
using namespace std;
struct Node {
int X;
int Y;
Node* next;
};
void addNode(Node** head, int x, int y) {
Node* ptr = *head;
Node* temp = new Node();
temp->X = x;
temp->Y = y;
temp->next = NULL;
if (*head == NULL)
*head = temp;
else {
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = temp;
}
}
int findMinSum(Node* head) {
int sum = 0;
while (head != NULL) {
sum += min(head->X, head->Y);
head = head->next;
}
return sum;
}
int main() {
Node* head = NULL;
addNode(&head, 5, 2);
addNode(&head, 7, 9);
addNode(&head, 6, 3);
addNode(&head, 36, 24);
addNode(&head, 19, 26);
cout << "The sum of smaller elements of nodes in Linked List is " << findMinSum(head) << endl;
return 0;
}
Đầu ra
The sum of smaller elements of nodes in Linked List is 55