Tổng các nút của một danh sách liên kết đơn trong chương trình C

Danh sách liên kết đơn là cấu trúc dữ liệu trong đó một phần tử có hai phần, một là giá trị và phần còn lại là liên kết đến phần tử tiếp theo. Vì vậy, để tìm tổng của tất cả các phần tử của danh sách được liên kết đơn lẻ, chúng ta phải điều hướng đến từng nút của danh sách được liên kết và thêm giá trị của phần tử vào một biến tổng.

Ví dụ

Suppose we have a linked list: 2 -> 27 -> 32 -> 1 -> 5
sum = 2 + 27 + 32 + 1 + 5 = 67.

Điều này có thể được thực hiện bằng hai phương pháp:

Phương pháp 1 - Sử dụng vòng lặp lặp qua tất cả các giá trị của danh sách liên kết và tìm tổng.

Vòng lặp chạy cho đến cuối danh sách liên kết, tức là khi con trỏ của một phần tử trỏ đến null, vòng lặp này sẽ chạy và tìm tổng các giá trị của mỗi phần tử.

Ví dụ

#include <iostream>
using namespace std;
struct Node {
   int data;
   struct Node* next;
};
void push(struct Node** nodeH, int nodeval) {
   struct Node* new_node = new Node;
   new_node->data = nodeval;
   new_node->next = (*nodeH);
   (*nodeH) = new_node;
}
int main() {
   struct Node* head = NULL;
   int sum = 0;
   push(&head, 95);
   push(&head, 60);
   push(&head, 87);
   push(&head, 6);
   push(&head, 12);
   struct Node* ptr = head;
   while (ptr != NULL) {
      sum += ptr->data;
      ptr = ptr->next;
   }
   cout << "Sum of nodes = "<< sum;
   return 0;
}

Đầu ra

Sum of nodes = 260

Phương pháp 2 - Sử dụng hàm đệ quy tự gọi cho đến khi danh sách liên kết có phần tử. Hàm đệ quy gọi lại chính nó nhiều lần. Lệnh gọi hàm đệ quy gửi các giá trị nút tiếp theo dưới dạng tham số cùng với vị trí địa chỉ tổng.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node* next;
};
void push(struct Node** head_ref, int new_data) {
   struct Node* new_node = new Node;
   new_node->data = new_data;
   new_node->next = (*head_ref);
   (*head_ref) = new_node;
}
void nodesum(struct Node* head, int* sum) {
   if (!head)
      return;
   nodesum(head->next, sum);
   *sum = *sum + head->data;
}
int main() {
   struct Node* head = NULL;
   int sum= 0;
   push(&head, 95);
   push(&head, 60);
   push(&head, 87);
   push(&head, 6);
   push(&head, 12);
   nodesum(head,&sum);
   cout << "Sum of nodes = "<<sum;
   return 0;
}

Đầu ra

Sum of nodes = 260