เพื่อให้เข้าใจแนวคิดนี้ได้ดียิ่งขึ้น เรามาทบทวนพื้นฐานที่จำเป็นกันก่อน
Linked List เป็นโครงสร้างข้อมูลที่เก็บแต่ละองค์ประกอบเป็นออบเจ็กต์ในโหนดของรายการ ทุกโหนดประกอบด้วยสองส่วน ได้แก่ ข้อมูล (data) และลิงก์ไปยังโหนดถัดไป
พหุนาม (Polynomial) เป็นนิพจน์ทางคณิตศาสตร์ที่ประกอบด้วยตัวแปรและสัมประสิทธิ์ เช่น x² - 4x + 7
ใน Linked List ของพหุนาม สัมประสิทธิ์และเลขยกกำลังของพหุนามจะถูกกำหนดเป็นข้อมูลของโหนดในรายการ
สำหรับการบวกพหุนามสองตัวที่จัดเก็บเป็น Linked List เราต้องบวกสัมประสิทธิ์ของตัวแปรที่มีกำลังเท่ากัน ในโหนดของ Linked List จะมีสมาชิก 3 ตัว ได้แก่ ค่าสัมประสิทธิ์ ค่ากำลัง และลิงก์ไปยังโหนดถัดไป
Linked List ที่ใช้จัดเก็บพหุนามจะมีลักษณะดังนี้:
พหุนาม: 4x⁷ + 12x² + 45
นี่คือวิธีที่ Linked List แสดงพหุนาม
การบวกพหุนามสองตัวที่แสดงด้วย Linked List เราจะตรวจสอบค่าที่ค่าเลขยกกำลังของโหนด สำหรับค่าเลขยกกำลังที่เท่ากัน เราจะบวกสัมประสิทธิ์เข้าด้วยกัน
ตัวอย่าง:
Input: p1 = 13x⁸ + 7x⁵ + 32x² + 54
p2 = 3x¹² + 17x⁵ + 3x³ + 98
Output: 3x¹² + 13x⁸ + 24x⁵ + 3x³ + 32x² + 152
คำอธิบาย - สำหรับทุกกำลัง เราจะตรวจสอบสัมประสิทธิ์ของเลขยกกำลังที่มีค่าเท่ากันและบวกมันเข้าด้วยกัน จากนั้นส่งคืนพหุนามสุดท้าย
อัลกอริทึม
Input - พหุนาม p1 และ p2 ที่แสดงเป็น Linked List
ขั้นตอนที่ 1: วนลูปผ่านค่าทั้งหมดของ Linked List และทำตามขั้นตอนที่ 2 และ 3 ขั้นตอนที่ 2: หากค่าเลขยกกำลังของโหนดมากกว่า ให้คัดลอกโหนดนี้ไปยังโหนดผลลัพธ์และไปยังโหนดถัดไป ขั้นตอนที่ 3: หากค่าเลขยกกำลังของทั้งสองโหนดเท่ากัน ให้บวกสัมประสิทธิ์แล้วคัดลอกค่าที่บวกแล้วพร้อมโหนดไปยังผลลัพธ์ ขั้นตอนที่ 4: พิมพ์โหนดผลลัพธ์
ตัวอย่างโค้ด
#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;
}
ผลลัพธ์
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
