Để hiểu rõ hơn về khái niệm này, trước tiên chúng ta hãy tìm hiểu tất cả các nội dung cơ bản bắt buộc phải có.
danh sách được 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 ghi chú chứa hai phần dữ liệu han và các liên kết đến nút tiếp theo.
Đ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 ^ 2 - 4x + 7
Trong Danh sách liên kết đa thức , các hệ số và số mũ của đa thức được xác định là nút dữ liệu của danh sách.
Để thêm hai đa thức được lưu trữ dưới dạng danh sách liên kết. Chúng ta cần thêm 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 chứa 3 thành viên, giá trị hệ số liên kết đến nút tiếp theo.
một danh sách được liên kết được sử dụng để lưu trữ Đa thức trông giống như -
Đa thức:4x 7 + 12x 2 + 45
Đây là cách một danh sách liên kết được biểu diễn đa thức trông như thế nào.
Thêm hai đa thức được biểu diễn bằng một danh sách liên kết. Chúng tôi kiểm tra các giá trị tại giá trị lũy thừa của nút. Đối với các giá trị giống nhau của số mũ, chúng tôi sẽ thêm các hệ số.
Ví dụ,
Input : p1= 13x8 + 7x5 + 32x2 + 54 p2= 3x12 + 17x5 + 3x3 + 98 Output : 3x12 + 13x8 + 24x5 + 3x3 + 32x2 + 152
Giải thích - Với tất cả lũy thừa, chúng ta sẽ kiểm tra các hệ số của các số mũ có cùng giá trị của các số mũ 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.
Step 1: loop around all values of linked list and follow step 2& 3. Step 2: if the value of a node’s exponent. is greater copy this node to result node and head towards the next node. Step 3: if the values of both node’s exponent is same add the coefficients and then copy the added value with node to the result. Step 4: Print the resultant node.
Ví dụ
#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("polynomial 1: ");
printpoly(p1);
printf("\npolynomial 2: ");
printpoly(p2);
result = (struct Node *)malloc(sizeof(struct Node));
polyadd(p1, p2, result);
printf("\npolynomial after adding p1 and p2 : ");
printpoly(result);
return 0;
} Đầu ra
polynomial 1: 41x^7 + 12x^5 + 65x^0 polynomial 2: 21x^5 + 15x^2 polynomial after adding p1 and p2 : 41x^7 + 33x^5 + 15x^2 + 65x^0