Để hiểu rõ hơn khái niệm này, hãy ôn lại các kiến thức cơ bản cần thiết.
Danh sách liên kết (Linked List)
Danh sách liên kết là một cấu trúc dữ liệu lưu trữ mỗi phần tử như một đối tượng trong một nút của danh sách. Mỗi nút chứa hai phần: dữ liệu và liên kết đến nút tiếp theo.
Đa thức (Polynomial)
Đa thức là một biểu thức toán học bao gồm các biến và hệ số. Ví dụ: x² - 4x + 7
Danh sách liên kết đa thức
Trong danh sách liên kết đa thức, các hệ số và số mũ của đa thức được định nghĩa làm dữ liệu của nút.
Để cộng hai đa thức được lưu trữ dưới dạng danh sách liên kết, ta cần cộng các hệ số của các biến có cùng lũy thừa. Trong một nút danh sách liên kết có 3 thành phần: giá trị hệ số, số mũ và liên kết đến nút tiếp theo.
Một danh sách liên kết dùng để lưu trữ đa thức trông như sau:
Đa thức: 4x⁷ + 12x² + 45
Đây là cách một danh sách liên kết biểu diễn đa thức.
Cộng hai đa thức biểu diễn bằng danh sách liên kết
Ta kiểm tra giá trị tại số mũ của nút. Đối với các giá trị số mũ giống nhau, ta sẽ cộng các hệ số.
Ví dụ
Input: p1 = 13x⁸ + 7x⁵ + 32x² + 54 p2 = 3x¹² + 17x⁵ + 3x³ + 98 Output: 3x¹² + 13x⁸ + 24x⁵ + 3x³ + 32x² + 152
Giải thích – Với mọi lũy thừa, ta kiểm tra các hệ số của các số mũ có cùng giá trị và cộng chúng. Trả về đa thức cuối cùng.
Thuật toán
Đầu vào – Đa thức p1 và p2 được biểu diễn dưới dạng danh sách liên kết.
Bước 1: Lặp qua tất cả các giá trị của danh sách liên kết và thực hiện bước 2 & 3. Bước 2: Nếu giá trị số mũ của nút lớn hơn, sao chép nút này vào nút kết quả và chuyển đến nút tiếp theo. Bước 3: Nếu giá trị số mũ của cả hai nút giống nhau, cộng các hệ số và sao chép giá trị cộng với nút vào kết quả. Bước 4: In nút kết quả.
Ví dụ mã C++
#include <bits/stdc++.h>
using namespace std;
struct Node {
int coeff;
int pow;
struct Node *next;
};
void create_node(int x, int y, struct Node **temp) {
struct Node *r, *z;
z = *temp;
if (z == NULL) {
r = (struct Node*)malloc(sizeof(struct Node));
r->coeff = x;
r->pow = y;
*temp = r;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
} else {
r->coeff = x;
r->pow = y;
r->next = (struct Node*)malloc(sizeof(struct Node));
r = r->next;
r->next = NULL;
}
}
void polyadd(struct Node *p1, struct Node *p2, struct Node *result) {
while (p1->next && p2->next) {
if (p1->pow > p2->pow) {
result->pow = p1->pow;
result->coeff = p1->coeff;
p1 = p1->next;
} else if (p1->pow < p2->pow) {
result->pow = p2->pow;
result->coeff = p2->coeff;
p2 = p2->next;
} else {
result->pow = p1->pow;
result->coeff = p1->coeff + p2->coeff;
p1 = p1->next;
p2 = p2->next;
}
result->next = (struct Node *)malloc(sizeof(struct Node));
result = result->next;
result->next = NULL;
}
while (p1->next || p2->next) {
if (p1->next) {
result->pow = p1->pow;
result->coeff = p1->coeff;
p1 = p1->next;
}
if (p2->next) {
result->pow = p2->pow;
result->coeff = p2->coeff;
p2 = p2->next;
}
result->next = (struct Node *)malloc(sizeof(struct Node));
result = result->next;
result->next = NULL;
}
}
void printpoly(struct Node *node) {
while (node->next != NULL) {
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if (node->next != NULL)
printf(" + ");
}
}
int main() {
struct Node *p1 = NULL, *p2 = NULL, *result = NULL;
create_node(41, 7, &p1);
create_node(12, 5, &p1);
create_node(65, 0, &p1);
create_node(21, 5, &p2);
create_node(15, 2, &p2);
printf("Đa thức 1: ");
printpoly(p1);
printf("\nĐa thức 2: ");
printpoly(p2);
result = (struct Node *)malloc(sizeof(struct Node));
polyadd(p1, p2, result);
printf("\nĐa thức sau khi cộng p1 và p2: ");
printpoly(result);
return 0;
} Kết quả
Đa thức 1: 41x^7 + 12x^5 + 65x^0 Đa thức 2: 21x^5 + 15x^2 Đa thức sau khi cộng p1 và p2: 41x^7 + 33x^5 + 15x^2 + 65x^0