Programa C++ para sumar dos polinomios usando una lista enlazada

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

// 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 
        // than 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 
        // than 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("2nd Number: ");
    show(poly2);
  
    poly = (struct Node*)malloc(sizeof(struct Node));
  
    // Function add two polynomial 
    // numbers
    polyadd(poly1, poly2, poly);
  
    // Display resultant List
    printf("Added polynomial: ");
    show(poly);
  
    return 0;
}

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.
 

Método recursivo:

Algoritmo:

1. Si ambos números son nulos, entonces regresa
2. 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.
3. 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.
4. 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.

//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;
  }
}
  
// Driver code
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

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.

¡ Consulte el artículo completo sobre cómo sumar dos polinomios usando la lista enlazada para obtener más detalles!