C Soma de valores usando Lista Duplamente Encadeada em C.

[Luc4s M0ur4]

Olá, estou criando um programa para uma matéria da  Universidade onde esse programa recebe dois strings de números decimais gigantes inserido pelo usuário  e mostra a soma desses números em uma terceira lista( as outras duas estão recebendo os valores) em uma Lista Duplamente Encadeada em C. Portanto estou com  uma grande dificuldade de fazer algumas funções desse programa como a Generate ( onde gera uma lista a partir de uma string de números decimais como citado anteriormente, e que recebe um parâmetro Char para esses números) , Sum ( função na qual recebe esses valores e faz a soma deles) e a função Destroy( que faz a destruição  de uma lista ou mais ).

 

LDouble.h

#ifndef DUPLAMENTE_LISTA
#define DUPLAMENTE_LISTA

typedef struct double_linked TDList;
typedef struct no TNo;

TDList* TDList_create();
void TDList_destroy(TDList*);
TDList* TDList_generate(char*);
/**
 * Gera uma lista a partir de uma string de numeros decimais. 
 * Retorna uma lista duplamente encadeada representando a sequencia. 
 * @return: TDList*
 * @param: char* o numero como uma cadeia de caracteres. Ex.: "1234567897987987"
 **/

TDList* TDList_sum(TDList*, TDList*);
/**
 * Toma duas listas duplamente como parametro, representando inteiros gigantes e gera uma terceira lista
 * sendo um outro numero possivelmente gigante representando a soma. 
 * @param: ponteiros para listas duplamente encadeada representando dois numeros inteiros positivos possivelmente gigantes.
 * @return: retorna o ponteiro para uma lista duplamente encadeada representando outro numero possivelmente gigante 
 * (resultado da soma dos dois numeros de parametro)
 **/

void TDList_print(TDList*);
/*
 * Imprime a lista duplamente encadeada como sendo um numero inteiro gigante.
 * Os numeros deverao ser impressos um ao lado do outro sem espaco e com um \n no final da lista.
 * @param: ponteiro para lista duplamente encadeada que representa um numero inteiro positivo.
 */

#endif

 

LDouble.c

#include <stdlib.h>
#include <stdio.h>
#include "LDouble.h"
  
struct no{
  int info;
  struct no *prox, *ant;
};

struct no* TNo_createnfill(int info){
  struct no* novo = (struct no*) malloc(sizeof(struct no));
  if(novo){
    novo->info = info;
    novo->prox = NULL;
    novo->ant = NULL;
  }
  return novo;
}
struct double_linked{
  struct no *inicio;
  struct no *fim;
};

TDList* TDList_create(){
  TDList* nova = (TDList*) malloc(sizeof(TDList));
  if(nova){
    nova->inicio = NULL;
    nova->fim = NULL;
  }
  return nova;
}
TDList* TDList_sum(TDList* list){
  //Função com dificuldade para fezar.
}

TDList* TDList_generate(char*){
  //Função com dificuldade para fezar.
}

void TDList_destroy(TDList* list){
  //Função com dificuldade para fezar.
  
}

void TDList_print(TDList* list){
  if(list){
    struct no* aux = list->inicio;
    while(aux){
      printf("%d", aux->info);
      aux = aux->prox;
    }
    puts("");
  }
}

 

main.c

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include "LDouble.h"
/**
 * Problema: representacao de inteiros gigantes usando lista duplamente encadeada.
 * Para testar: ./a.out 123123123 123123123123121
*/

int main(int argc, char* argv[]){
  if(argc>2){
    TDList* num1 = TDList_generate(argv[1]);
    TDList* num2 = TDList_generate(argv[2]);
    TDList* sum = TDList_sum(num1, num2);
    TDList_print(sum);
    TDList_destroy(num1);
    TDList_destroy(num1);
    TDList_destroy(sum);
  }
  return 0;
}

 

A seguir a questão, caso estejam com alguma dúvida relacionado ao que falei acima.

 

E agradeço muito a ajuda de quem me ajudar.

[arfneto]

Acho que sua primeira preocupação deve ser separar o lance da lista ligada do resto do problema, do fato de que nesse caso está usando a lista para somar dois números. A lista é apenas um container e manter as coisas separadas vai fazer seu programa ficar muito mais fácil.

 

Escreva (e teste) separadamente

[arfneto]

Uma vez resolvida a parte da lista, a soma usa o algoritmo do ensino fundamental (primário): alinha os valores pela direita e soma. Passou de 10 "vai um" e tal. Nada mais.

 

Como o simples é somar a partir das unidades use os ponteiros a partir do fim da lista. E seja esperto e GUARDE na lista esses ponteiros....

 

Veja esse exemplo
 

typedef struct no_
{
    void*      item;
    struct no_* proxima;
    struct no_* anterior;

}   Node;  // um no

typedef struct 
{
    char*     nome;
    unsigned  quantos;
    unsigned  maximo;
    Node*     inicio;
    Node*     fim;

}   Lista;

 

A lista é uma lista de Node, mas tem um total de nós e um ponteiro para o início e para o fim. É disso que você precisa. A menos que queira ficar guardando ponteiros pra todo lado na hora de somar. Em item estariam os dígitos dos números, claro. E pode trocar o void* item por char digito

 

Há muitos exemplos de lista aqui no forum. Eu por exemplo já postei muitos e pode pesquisar no conteúdo

[João Pedro Cunha]

@arfneto  Estou com o mesmo exercicio pra resolver, não consegui entender muito bem as suas orientações ! Será que é pedir muito, seu auxilio na resolução do problema ? obrigado desde já !

 

[arfneto]

@João Pedro Cunha E o que você não entendeu muito bem? Entendeu o exemplo?

[João Pedro Cunha]

@arfneto  Entendi, porém sou muito leigo no assunto ainda ! Eu tenho um codigo fonte aqui que ja ta meio caminho andado, so preciso implementar uma função de soma e de destruir, so que eu não faço ideia de como fazer a parte de alinhar os valores pela direita e somar. Passou de 10 "vai um"

[arfneto]

Não há meio caminho em programas  É como aquela barra de progresso que para nos 99%: pode durar a vida toda lá.
 

33 minutos atrás, João Pedro Cunha disse:

como fazer a parte de alinhar os valores pela direita e somar. Passou de 10 "vai um"

 

Então deve ter lido essa parte e se entendeu o código que eu postei...
 

Em 18/04/2021 às 11:35, arfneto disse:

Uma vez resolvida a parte da lista, a soma usa o algoritmo do ensino fundamental (primário): alinha os valores pela direita e soma. Passou de 10 "vai um" e tal. Nada mais.

 

Como o simples é somar a partir das unidades use os ponteiros a partir do fim da lista

 

Pois é: 
 

typedef struct 
{
    char*     nome;
    unsigned  quantos;
    unsigned  maximo;
    Node*     inicio;
    Node*     fim;

}   Lista;

 

Notou a variável fim?  Isso alinha os valores pela direita. que é onde eles terminam.

 

O lance do "vai um" é como somar no papel...

 

 Esse não é o forum de aritmética mas...

 

EXEMPLO

 

1 2 3
6 7 8 +

ao somar 8 e 3 marca 1 para a unidade e 10 vai para a próxima soma

ao soar 7 + 2 + 1 que tinha sobrado são 100 então fica o zero e vão 100 para a proxima soma

1 2 3
6 7 8 +

  0 1

ao somar 6 + 1 + 1 que tinha sobrado são 800 então tem o total

1 2 3
6 7 8 +

8 0 1

 

 

[João Pedro Cunha]

@arfneto sigo sem entender... n tenho ideia de como usar a variavel fim e nem como somar os números atraves de codigos! mas obrigado pela atenção.

[arfneto]

@João Pedro Cunha Deve imaginar que fim aponta para o fim da lista e inicio para o inicio da lista...

 

Entendeu que cada número vai ser representado por uma lista e viu a soma que te mostrei passo a passo, incluido o lance do "vai um"?

 

Não sei o que dizer. 

 

Se um numero era 130 e o outro era 1... A primeira lista termina no 0 e a segunda no 1. Dá pra ver que eles estão alinhados à direita, no popular pelas unidades, que é o que você fazia quando somava no ensino fundamental:

 

1 3 0
    1  +
______________

 

ou não?

[João Pedro Cunha]

a soma esclareceu um pouco a ideia, mas como eu chego ate o fim da lista ??

Ex : 123123123 + 123123123123121

Como eu somaria o Nesimo numero de uma lista com o mesmo Nesimo numero da outra lista ??

[arfneto]

@João Pedro Cunha João, cada elemento da lista é claro um dígito.

 

Você chega ao final quando chega ao último.... Veja os exemplos que te mostrei.

 

Se você tem 130 chega ao final com o 1, claro. E como sabe que é o final? Porque não tem nenhum antes.... Para que usar exemplos de 15 dígitos?

 

49 minutos atrás, João Pedro Cunha disse:

Como eu somaria o Nesimo numero de uma lista com o mesmo Nesimo numero da outra lista ??

 

De volta ao exemplo do ensino fundamental, você alinha os números pela direita,. como eu te mostrei no desenho e como se fazia na escola e no papel.

 

Você soma os caras um a um a partir das unidades, ou não? Não exatamente o n-ésimo porque não se sabe o tamanho deles. Apenas soma dígito a dígito como no ensino primário.

 

1 3 0 9 
      2 +
__________


    1
1 3 0 9
      2 +
__________
1 3 1 1

 

Se um dos números acabou e não tem o "vai um" --- o tal carry bit --- a conta acabou.... É só isso