Dados dos polinomios representados por una lista enlazada. Escribe una función que sume estas listas significa sumar los coeficientes que tienen las mismas potencias variables.
Ejemplo:
Input:
1st number = 5x2 + 4x1 + 2x0
2nd number = -5x1 - 5x0
Output:
5x2-1x1-3x0
Input:
1st number = 5x3 + 4x2 + 2x0
2nd number = 5x^1 - 5x^0
Output:
5x3 + 4x2 + 5x1 - 3x0
Implementación:
CPP
// C++ program for addition of two polynomials
// using Linked Lists
#include <bits/stdc++.h>
using namespace std;
// Node structure containing power and coefficient of
// variable
struct Node {
int coeff;
int pow;
struct Node* next;
};
// Function to create new node
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;
}
}
// Function Adding two polynomial numbers
void polyadd(struct Node* poly1, struct Node* poly2,
struct Node* poly)
{
while (poly1->next && poly2->next) {
// If power of 1st polynomial is greater then 2nd,
// then store 1st as it is and move its pointer
if (poly1->pow > poly2->pow) {
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1 = poly1->next;
}
// If power of 2nd polynomial is greater then 1st,
// then store 2nd as it is and move its pointer
else if (poly1->pow < poly2->pow) {
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
// If power of both polynomial numbers is same then
// add their coefficients
else {
poly->pow = poly1->pow;
poly->coeff = poly1->coeff + poly2->coeff;
poly1 = poly1->next;
poly2 = poly2->next;
}
// Dynamically create new node
poly->next
= (struct Node*)malloc(sizeof(struct Node));
poly = poly->next;
poly->next = NULL;
}
while (poly1->next || poly2->next) {
if (poly1->next) {
poly->pow = poly1->pow;
poly->coeff = poly1->coeff;
poly1 = poly1->next;
}
if (poly2->next) {
poly->pow = poly2->pow;
poly->coeff = poly2->coeff;
poly2 = poly2->next;
}
poly->next
= (struct Node*)malloc(sizeof(struct Node));
poly = poly->next;
poly->next = NULL;
}
}
// Display Linked list
void show(struct Node* node)
{
while (node->next != NULL) {
printf("%dx^%d", node->coeff, node->pow);
node = node->next;
if (node->coeff >= 0) {
if (node->next != NULL)
printf("+");
}
}
}
// Driver code
int main()
{
struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
// Create first list of 5x^2 + 4x^1 + 2x^0
create_node(5, 2, &poly1);
create_node(4, 1, &poly1);
create_node(2, 0, &poly1);
// Create second list of -5x^1 - 5x^0
create_node(-5, 1, &poly2);
create_node(-5, 0, &poly2);
printf("1st Number: ");
show(poly1);
printf("\n2nd Number: ");
show(poly2);
poly = (struct Node*)malloc(sizeof(struct Node));
// Function add two polynomial numbers
polyadd(poly1, poly2, poly);
// Display resultant List
printf("\nAdded polynomial: ");
show(poly);
return 0;
}
Java
import java.io.*;
import java.util.Scanner;
class Polynomial {
public static Node addPolynomial(Node p1, Node p2)
{
Node a = p1, b = p2, newHead = new Node(0, 0),
c = newHead;
while (a != null || b != null) {
if (a == null) {
c.next = b;
break;
}
else if (b == null) {
c.next = a;
break;
}
else if (a.pow == b.pow) {
c.next = new Node(a.coeff + b.coeff, a.pow);
a = a.next;
b = b.next;
}
else if (a.pow > b.pow) {
c.next = new Node(a.coeff, a.pow);
a = a.next;
}
else if (a.pow < b.pow) {
c.next = new Node(b.coeff, b.pow);
b = b.next;
}
c = c.next;
}
return newHead.next;
}
}
// Utilities for Linked List Nodes
class Node {
int coeff;
int pow;
Node next;
Node(int a, int b)
{
coeff = a;
pow = b;
next = null;
}
}
//Linked List main class
class LinkedList {
public static void main(String args[])
{
Node start1 = null, cur1 = null, start2 = null,
cur2 = null;
int[] list1_coeff = { 5, 4, 2 };
int[] list1_pow = { 2, 1, 0 };
int n = list1_coeff.length;
int i = 0;
while (n-- > 0) {
int a = list1_coeff[i];
int b = list1_pow[i];
Node ptr = new Node(a, b);
if (start1 == null) {
start1 = ptr;
cur1 = ptr;
}
else {
cur1.next = ptr;
cur1 = ptr;
}
i++;
}
int[] list2_coeff = { -5, -5 };
int[] list2_pow = { 1, 0 };
n = list2_coeff.length;
i = 0;
while (n-- > 0) {
int a = list2_coeff[i];
int b = list2_pow[i];
Node ptr = new Node(a, b);
if (start2 == null) {
start2 = ptr;
cur2 = ptr;
}
else {
cur2.next = ptr;
cur2 = ptr;
}
i++;
}
Polynomial obj = new Polynomial();
Node sum = obj.addPolynomial(start1, start2);
Node trav = sum;
while (trav != null) {
System.out.print(trav.coeff + "x^" + trav.pow);
if (trav.next != null)
System.out.print(" + ");
trav = trav.next;
}
System.out.println();
}
}
C#
// C# code to implement the approach
using System;
// Utilities for Linked List Nodes
class Node {
public int coeff;
public int pow;
public Node next;
public Node(int a, int b)
{
coeff = a;
pow = b;
next = null;
}
}
// Polynomial class
class Polynomial {
public Node addPolynomial(Node p1, Node p2)
{
Node a = p1, b = p2, newHead = new Node(0, 0),
c = newHead;
while (a != null || b != null) {
if (a == null) {
c.next = b;
break;
}
else if (b == null) {
c.next = a;
break;
}
else if (a.pow == b.pow) {
c.next = new Node(a.coeff + b.coeff, a.pow);
a = a.next;
b = b.next;
}
else if (a.pow > b.pow) {
c.next = new Node(a.coeff, a.pow);
a = a.next;
}
else if (a.pow < b.pow) {
c.next = new Node(b.coeff, b.pow);
b = b.next;
}
c = c.next;
}
return newHead.next;
}
}
//Linked List main class
class LinkedList {
public static void Main(string[] args)
{
Node start1 = null, cur1 = null, start2 = null,
cur2 = null;
int[] list1_coeff = { 5, 4, 2 };
int[] list1_pow = { 2, 1, 0 };
int n = list1_coeff.Length;
int i = 0;
while (n-- > 0) {
int a = list1_coeff[i];
int b = list1_pow[i];
Node ptr = new Node(a, b);
if (start1 == null) {
start1 = ptr;
cur1 = ptr;
}
else {
cur1.next = ptr;
cur1 = ptr;
}
i++;
}
int[] list2_coeff = { -5, -5 };
int[] list2_pow = { 1, 0 };
n = list2_coeff.Length;
i = 0;
while (n-- > 0) {
int a = list2_coeff[i];
int b = list2_pow[i];
Node ptr = new Node(a, b);
if (start2 == null) {
start2 = ptr;
cur2 = ptr;
}
else {
cur2.next = ptr;
cur2 = ptr;
}
i++;
}
Polynomial obj = new Polynomial();
Node sum = obj.addPolynomial(start1, start2);
Node trav = sum;
while (trav != null) {
Console.Write(trav.coeff + "x^" + trav.pow);
if (trav.next != null)
Console.Write(" + ");
trav = trav.next;
}
Console.WriteLine();
}
}
// This code is contributed by phasing17
Producción
1st Number: 5x^2+4x^1+2x^0 2nd Number: -5x^1-5x^0 Added polynomial: 5x^2-1x^1-3x^0
Complejidad de tiempo: O(m + n) donde m y n son el número de Nodes en la primera y segunda lista respectivamente.
Versión simple y concisa del enfoque anterior:
Mantendremos un puntero anterior que apuntará al último Node de la lista enlazada resultante. Modificaremos los mismos Nodes dados en lugar de crear otros nuevos. El siguiente código le proporcionará más información.
Gracias Nakshatra Chhillar por sugerir esta simplificación y contribuir con el código:
Implementación:
C++
#include <bits/stdc++.h>
using namespace std;
/* Link list Node */
struct Node {
int coeff;
int pow;
struct Node* next;
Node(int c, int p)
{
coeff = c;
pow = p;
next = NULL;
}
};
void append(struct Node** head_ref, struct Node** tail_ref,
int new_data, int new_data1)
{
struct Node* new_node = new Node(new_data, new_data1);
if (*head_ref == NULL)
*head_ref = new_node;
else
(*tail_ref)->next = new_node;
*tail_ref = new_node;
}
void printList(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d %d ", temp->coeff, temp->pow);
temp = temp->next;
}
}
Node* addPolynomial(Node* p1, Node* p2);
void create_node(int x, int y, struct Node** temp)
{
struct Node *r, *z;
z = *temp;
if (z == NULL) {
r = new Node(x, y);
*temp = r;
r->next = NULL;
}
else {
r->next = new Node(x, y);
r = r->next;
r->next = NULL;
}
}
/* Structure of Node used
struct Node
{
int coeff;
int pow;
struct Node* next;
Node(int c, int p){
coeff = c;
pow = p;
next = NULL;
}
};
*/
// 1st Number: 5x^2+4x^1+2x^0
// 2nd Number: -5x^1-5x^0
class Solution {
public:
/* The below method print the required sum of polynomial
p1 and p2 as specified in output */
Node* addPolynomial(Node* p1, Node* p2)
{
Node* res = new Node(
0, 0); // dummy node ...head of resultant list
Node* prev
= res; // pointer to last node of resultant list
// like Merge procedure :
while (p1 != NULL and p2 != NULL) {
if (p1->pow < p2->pow) {
prev->next = p2;
prev = p2;
p2 = p2->next;
}
else if (p1->pow > p2->pow) {
prev->next = p1;
prev = p1;
p1 = p1->next;
}
else {
p1->coeff = p1->coeff + p2->coeff;
prev->next = p1;
prev = p1;
p1 = p1->next;
p2 = p2->next;
}
}
if (p1 != NULL) {
prev->next = p1;
}
if (p2 != NULL) {
prev->next = p2;
}
return res->next;
}
};
int main()
{
struct Node *poly1 = NULL, *poly2 = NULL, *poly = NULL;
struct Node *tail1 = NULL, *tail2 = NULL;
// 1st Number: 5x^2+4x^1+2x^0
append(&poly1, &tail1, 5, 2);
append(&poly1, &tail1, 4, 1);
append(&poly1, &tail1, 2, 0);
// 2nd Number: -5x^1-5x^0
append(&poly2, &tail2, -5, 1);
append(&poly2, &tail2, -5, 0);
Solution obj;
Node* sum = obj.addPolynomial(poly1, poly2);
for (Node* ptr = sum; ptr; ptr = ptr->next) {
// printing polynomial
cout << ptr->coeff << "x^" << ptr->pow;
if (ptr->next)
cout << " + ";
}
cout << endl;
}
// contributed by Nakshatra Chhillar
Producción
5x^2 + -1x^1 + -3x^0
Complejidad de tiempo: O(m + n) donde m y n son el número de Nodes en la primera y segunda lista respectivamente.
Complejidad espacial: O(1) no se han creado Nodes adicionales
Método recursivo:
Algoritmo:
- Si ambos números son nulos, entonces regresa
- de lo contrario, si compara la potencia, si es igual, agregue los coeficientes y llame recursivamente a addPolynomials en los siguientes elementos de ambos números.
- de lo contrario, si la potencia del primer número es mayor, imprima el elemento actual del primer número y llame recursivamente a addPolynomial en el siguiente elemento del primer número y el elemento actual del segundo número.
- de lo contrario, imprima el elemento actual del segundo número y llame recursivamente a addPolynomial en el elemento actual del primer número y el siguiente elemento del segundo número.
Implementación:
C++
// Program to add two polynomials represented
// in linkedlist using recursion
#include<iostream>
using namespace std;
class Node{
public:
int coeff,power;
Node *next;
Node(int coeff, int power){
this->coeff = coeff;
this->power = power;
this->next = NULL;
}
};
void addPolynomials(Node *head1, Node *head2){
if(head1==NULL && head2==NULL)
return;
else if(head1->power == head2->power){
cout<<" "<<head1->coeff + head2->coeff<<"x^"<<head1->power<<" ";
addPolynomials(head1->next,head2->next);
}
else if(head1->power > head2->power){
cout<<" "<<head1->coeff<<"x^"<<head1->power<<" ";
addPolynomials(head1->next,head2);
}
else{
cout<<" "<<head2->coeff<<"x^"<<head2->power<<" ";
addPolynomials(head1,head2->next);
}
}
void insert(Node *head, int coeff, int power){
Node *new_node = new Node(coeff,power);
while(head->next!=NULL){
head = head->next;
}
head->next = new_node;
}
void printList(Node *head){
cout<<"Linked List"<<endl;
while(head!=NULL){
cout<<" "<<head->coeff<<"x"<<"^"<<head->power;
head = head->next;
}
}
int main(){
Node *head=new Node(5,2);
insert(head,4,1);
Node *head2 = new Node(6,2);
insert(head2,4,1);
printList(head);
cout<<endl;
printList(head2);
cout<<endl<<"Addition:"<<endl;
addPolynomials(head,head2);
return 0;
}
//This code is contributed by Akshita Patel
Javascript
<script>
// JavaScript Program to add two polynomials
// represented in linkedlist using recursion
class Node{
constructor(coeff, power){
this.coeff = coeff;
this.power = power;
this.next = null;
}
}
function addPolynomials(head1, head2){
document.write(head1.power, head2.power)
if(head1==null && head2==null)
return;
else if(head1.power == head2.power){
document.write(` ${head1.coeff + head2.coeff}x^${head1.power} `);
addPolynomials(head1.next, head2.next);
}
else if(head1.power > head2.power){
document.write(` ${head1.coeff}x^${head1.power} `);
addPolynomials(head1.next, head2);
}
else{
document.write(` ${head2.coeff}x^${head2.power} `);
addPolynomials(head1, head2.next);
}
}
function insert(head, coeff, power){
let new_node = new Node(coeff,power);
while(head.next!=null){
head = head.next;
}
head.next = new_node;
}
function printList(head){
document.write("Linked List","</br>");
while(head != null){
document.write(` ${head.coeff}x^${head.power}`);
head = head.next;
}
}
// driver code
let head = new Node(5,2);
insert(head,4,1);
let head2 = new Node(6,2);
insert(head2,4,1);
printList(head);
document.write("</br>");
printList(head2);
document.write("</br>");
document.write("Addition:");
document.write("</br>");
addPolynomials(head,head2);
// This code is contributed by shinjanpatra
</script>
Producción
Linked List 5x^2 4x^1 Linked List 6x^2 4x^1 Addition: 11x^2 8x^1
Complejidad de tiempo: O(m + n) donde m y n son el número de Nodes en la primera y segunda lista respectivamente.
Artículo Relacionado: Suma dos números polinómicos usando Arrays
Este artículo es una contribución de Akash Gupta y Akshita Patel ; mejorado por Nakshatra Chhillar . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA