Sumar los elementos de dos listas enlazadas en una tercera lista

publicado por: Anonymous

La idea es representar una suma de tres dígitos

   6  8  9  <---- valores de lista 1.
   5  7  4   <----- valores lista 2.
 -------------
 1 2  6  3   <------ valores lista 3.

Hasta ahora obtengo el resultado de la suma, pero tomando los valores de izquierda a derecha.

  6 8 9
  5 7 4
_________
1 4 6 1  ---> regresa el resultado de sumar ( 986 + 474 )

Ya intente ingresar los datos en orden contrario en las dos primeras listas y nada.

Les muestro el código:

#include "iostream"
using namespace std;

struct nodo
{
 int numero;
 struct nodo* sig;
 struct nodo* ant;  
};
typedef struct nodo*Lista;

void insertarValores(Lista &lista,int digito)
{
Lista nuevo;
nuevo = new(struct nodo);
nuevo ->numero=digito;
    if(lista==NULL){
        lista=nuevo;
        lista->sig=NULL;
        lista->ant=NULL;    
    }
    else
    {
        nuevo->sig=lista;
        nuevo->ant=lista->ant;
        lista->ant=nuevo;
        lista=nuevo;
    }   

}
void insertarFinal(Lista & lista,int digito)
{
 Lista nuevo,aux =lista;    
 nuevo = new(struct nodo);
 nuevo->numero=digito;
 nuevo->sig=NULL;
 if(aux==NULL)
 {
    lista=nuevo;
 }
 else
   {
       while(aux->sig!=NULL)
       aux=aux->sig;   
       aux->sig=nuevo;

   }

}

void mostrar(Lista lista)
{

Lista aux =new (struct nodo);

aux=lista;
cout<<"n";
    while(aux!=NULL){
    cout<<"   "<<aux->numero;
        aux=aux->sig;

    }   
}

void sumar(Lista &lista1,Lista &lista2,Lista &listaResultado)
 {
 Lista l1=lista1, l2=lista2;
  int acarreo=0;
   while (l1 != NULL && l2 != NULL)
  {
   int suma = l1->numero + l2->numero+acarreo;
   if(suma>=10)
     {
      insertarFinal(listaResultado, suma%10);
      acarreo=1;
     }
    else 
    {
    insertarFinal(listaResultado, suma%10);
    acarreo=0;  
    }
    l1 = l1->sig;
    l2 = l2->sig;
  }
  insertarFinal(listaResultado,acarreo);
}

int main(){
Lista arriba=NULL;
Lista abajo=NULL;
Lista resultado=NULL;
int L1,L2;
cout<<"Ingrese los valores a sumar de la lista 1 (arriba)"<<endl;
for(int i=0;i<3;i++)
{   cout<<"Lista 1.ntValor "<<i+1<<" ";
    cin>>L1;
    //insertarValores(arriba,L1);
    insertarFinal(arriba,L1);
    mostrar(arriba);
        cout<<"n";
}
system("cls");
cout<<"Ingrese los valores a sumar de la lista 2 (abajo)"<<endl;
for(int i=0;i<3;i++)
{   cout<<"Lista 2.ntValor "<<i+1<<" ";
    cin>>L2;
    //insertarValores(abajo,L2);
insertarFinal(abajo,L2);
mostrar(abajo);
cout<<"n";
}

system("cls");
mostrar(arriba); 
cout<<"n+ ";
mostrar(abajo);
cout<<"n___________________";

sumar(arriba,abajo,resultado);
mostrar(resultado);
}

solución

Veo que usas una lista doblemente enlazada así que no deberías tener problema alguno en recorrer los números de menos significativo a más significativo.

Propuesta

Yo te aconsejaría pasar la lista a número y después dejar que sea el sistema el que se encargue de los acarreos y desbordamientos; la función para pasar tu Lista a número sería:

int lista_a_numero(const Lista &lista)
{
    int resultado{}, arrastre{1};

    for (const nodo *actual = ultimo(lista); actual; actual = actual->ant)
    {
        resultado += (actual->numero * arrastre);
        arrastre *= 10;
    }

    return resultado;
}

Con esta función podrías transformar la lista en un número. Si te fijas, estoy usando una función para apuntar al último nodo de una lista, la cuál tiene este aspecto:

const nodo *ultimo(const nodo *actual)
{
    if (actual->sig)
        return ultimo(actual->sig);

    return actual;
}

Ahora sólo necesitas una función que haga la operación inversa para conseguir esto:

int valor1 = lista_a_numero(lista1);
int valor2 = lista_a_numero(lista2);
Lista listaSuma = numero_a_lista(valor1 + valor2);

La función para trasnformar de número a lista sería algo así:

Lista numero_a_lista(int numero)
{
    nodo *resultado = new nodo{numero % 10};
    numero /= 10;

    while (numero)
    {
        resultado = new nodo{numero % 10, resultado};
        resultado->sig->ant = resultado;
        numero /= 10;
    }

    return resultado;
}

Con esta propuesta el código quedaría así:

int main()
{
    Lista lista1 = numero_a_lista(689);
    Lista lista2 = numero_a_lista(574);

    int valor1 = lista_a_numero(lista1);
    int valor2 = lista_a_numero(lista2);
    Lista listaSuma = numero_a_lista(valor1 + valor2);

    std::cout << valor1 << " + " << valor2 << " = ";

    for (nodo *actual = listaSuma; actual; actual = actual->sig)
        std::cout << actual->numero;

    return 0;
}

[Cuya salida es]:

689 + 574 = 1263

Consejos

En C++ no es necesario anteponer struct para referirse a una estructura; así que tu nodo tendría este aspecto:

struct nodo
{
 int numero;
 nodo* sig;
 nodo* ant;
};

A partir de C++11 puedes usar la inicialización uniforme para dar valor a los miembros de tu estructura en el mismo sitio que se declaran, así te ahorras crear un constructor y te aseguras que obtienen valores controlados:

struct nodo
{
 int numero = 0;
 nodo* sig = nullptr;
 nodo* ant = nullptr;
};

Para crear alias de tipos, el typedef tiene una sintaxis confusa, a partir de C++11 puedes simplificar el alias con la instrucción using:

using Lista = nodo *;

Date cuenta que tampoco requiere el struct antes de nodo.

En cuanto a este alias, es una idea terrible, nefasta, horrible, inadecuada, impropia, ilógica y muchos otros calificativos negativos. Un nodo no es una Lista, conceptualmente son cosas distintas… es como si dijeras que una bujía es un coche; crea un objeto Lista no digas que un nodo es una Lista.

Usa const siempre no modifiques objetos, eso puede ayudar al compilador a realizar optimizaciones y hace que otros que lean el código conozcan tu intencionalidad:

// mostrar una lista no requiere modificarla
void mostrar(const Lista lista);
// no se requiere modificar lista1 ni lista2 para sumar
void sumar(const Lista &lista1, const Lista &lista2, Lista &listaResultado);
Respondido por: Anonymous

Leave a Reply

Your email address will not be published. Required fields are marked *