Sumar y restar Bigints usando listas vinculadas

Question

Ya casi termino con esta tarea, y me está matando. Esta es mi TERCERA publicación sobre tres secciones diferentes de esto, y estoy sinceramente avergonzado de que estoy luchando tanto con la tarea.

La tarea en sí es hacer un programa que realiza sumas y restas de enteros grandes utilizando listas vinculadas (y lentamente empiezo a odiar las listas vinculadas, fuera de Lisp). Todo parece estar funcionando ahora, salvo por la suma y la resta real. No estoy seguro de si se trata de las funciones aritméticas, porque estaban trabajando antes (pero nunca al 100%), pero no está de más consultar con la comunidad de S/O (normalmente no pediría tanto ayudar en una tarea porque prefiero resolver las cosas por mi cuenta, pero esta ha sido una semana horrible y agitada, y la fecha límite se acerca rápidamente).

Las funciones aritméticas que he escrito son las siguientes, ¿alguien me puede ayudar a elegir cuál es el problema?

/* 
* Function add 
* 
* @Paramater STRUCT* Integer 
* @Parameter STRUCT* Integer 
* 
* Takes two linked lists representing 
* big integers stored in reversed order, 
* and returns a linked list containing 
* the sum of the two integers. 
* 
* @Return STRUCT* Integer 
* 
* TODO Comment me 
*/ 
struct integer* add(struct integer *p, struct integer *q) 
{ 
    int carry = 0; 

    struct integer *sHead, *sCurr; 
    struct integer *pHead, *qHead; 

    pHead = p; 
    qHead = q; 

    sHead = NULL; 

    while(p) 
    { 
     sCurr = (struct integer*) malloc (sizeof(struct integer)); 
     sCurr->digit = p->digit + q->digit + carry; 
     sCurr->next = sHead; 
     sHead = sCurr; 

     carry = 0; 

     /* 
     * If the current digits sum to greater than 9, 
     * create a carry value and replace the current 
     * value with value mod 10. 
     */ 
     if(sCurr->digit > 9) 
     { 
      carry = 1; 
      sCurr->digit = sCurr->digit % 10; 
     } 

     /* 
     * If the most significant digits of the numbers 
     * sum to 10 or greater, create an extra node 
     * at the end of the sum list and assign it the 
     * value of 1. 
     */ 
     if(carry == 1 && sCurr->next == NULL) 
     { 
      struct integer *sCarry = (struct integer*) malloc (sizeof(struct integer)); 
      sCarry->digit = 1; 
      sCarry->next = NULL; 
      reverse(&sCurr); 
      sCurr->next = sCarry; 
      reverse(&sCurr); 
     } 

     p = p->next; 
     if(q->next) q = q->next; 
     else q->digit = 0; 
    } 

    return sHead; 
} 

---

/* 
* Function subtract 
* 
* @Parameter STRUCT* Integer 
* @Parameter STRUCT* Integer 
* 
* Takes two linked lists representing struct integers. 
* Traverses through the lists, subtracting each 
* digits from the subsequent nodes to form a new 
* struct integer, and then returns the newly formed 
* linked list. 
* 
* @Return STRUCT* Integer 
* 
* TODO Comment me 
*/ 
struct integer* subtract(struct integer *p, struct integer *q) 
{ 
    int borrow = 0; 

    struct integer *dHead, *dCurr; 
    struct integer *pHead, *qHead; 

    pHead = p; 
    qHead = q; 

    dHead = NULL; 

    while(p) 
    { 
     dCurr = (struct integer*) malloc (sizeof(struct integer)); 
     if(q) 
     { 
      dCurr->digit = p->digit - q->digit - borrow; 
     } 
     else 
     { 
      dCurr->digit = p->digit - borrow; 
     } 
     dCurr->next = dHead; 

     if(dCurr->digit < 0) 
     { 
      dCurr->digit += 10; 
      borrow = 1; 
     } 

     dHead = dCurr; 

     p = p->next; 
     if(q->next) q = q->next; 
    } 

    return dHead; 
} 

---

---

La salida de la muestra debe tener este aspecto:

8888888888 + 2222222222 = 11111111110 
10000000000 – 9999999999 = 1 
10000000000 – 9999999999 = 1 

pero en cambio, se ve así:

8888888888 + 2222222222 = 1111111110 
10000000000 - 9999999999 = 10000000001 
10000000000 - 9999999999 = 10000000001 

EDITAR El programa completo, en su forma actual a las 3:30 PM EST, está disponible here como referencia, o en caso de que estas funciones no sean el problema.

Answer 1

else q->digit = 0;
Está cambiando el argumento dentro de la función.

Intente cambiar sus funciones para aceptar const argumentos y recompilar.

struct integer* add(const struct integer *p, const struct integer *q) 
struct integer* subtract(const struct integer *p, const struct integer *q) 

Answer 2

La parte que lee

if(dCurr->next == NULL && carry == 1) 
{ 
    struct integer *dCarry = (struct integer*) malloc (sizeof(struct integer)); 
    dCarry->digit = -1; 
    dCarry->next = NULL; 
    dCurr->next = dCarry; 
} 

parece un poco fuera de lugar. Del código anterior, dCurr->next está configurado para ser los dígitos que ya hemos calculado en ciclos anteriores, por lo que solo es NULO en el primer dígito. Creo que en realidad querías marcar p->next.

Supongo que la condición len(p) >= len(q) se cumple para esta función. De lo contrario, tendrá que hacer algo sobre el manejo en el que no se mantenga (se agote p nodos antes de que se agoten los q nodos). También asumo que los dígitos están en la lista del dígito menos significativo al más significativo. De lo contrario, es posible que deba revertir pyq antes de procesarlos.

Otra cosa que no puedo entender es cómo manejas los números negativos. O incluso si se supone que debes manejarlos. No es fácil agregarlo a una estructura como esta, porque un enfoque ingenuo de agregar algo al final no funcionaría al restar: cuando q es negativo, se tomará todas las molestias de restar q de p, y luego descubrirá que deberías haber agregado en su lugar.

Answer 3

En la función compare() "caminar" p y luego intentar caminar de nuevo.

int compare(struct integer *p, struct integer *q) 
{ 
    /* ... */ 
    while(p) 
    { 
     pCount++; 
     p = p->next; 
    } 

p es ahora NULL

/* ... */ 
    while(p) 
    { 
     /* ... */ 
    } 

El bucle while nunca se agota.