c - 两个链表相乘输出错误

Question

我正在尝试将两个链表相乘，并且我使用了基本的数学乘法概念。选取一个列表项，将其与其他链表项相乘，并将结果存储到另一个链表中。我已经成功地做到了这一点，并且正确的乘法也存储在结果链接列表中。但我在添加结果链表时遇到问题。每一步的总和都被正确计算，但在最后一步垃圾值取代了总和。如果我的逻辑错误，请帮助我。

int multiply(struct node *first, struct node *second)
{
    struct node *ans = NULL;
    struct node *head = NULL;
    struct node *rev_first = NULL;
    struct node *rev_second = NULL;
    int i, temp, mul, ten, carry=0, sum = 0;
    rev_first = reverse(first);
    rev_second = reverse(second);
    while(rev_first != NULL)
    {
        ten = 1;
        sum = 0;
        head = rev_second;
        while(head != NULL)
        {
            mul = (rev_first->data) * (head->data);
            carry = mul / 10;
            temp = mul % 10;
            sum = sum + (temp * ten);
            ten = ten * 10;
            head = head->next;
        }
        push(&ans, sum);
        rev_first = rev_first->next;
    }
    sum = 0;
    head = reverse(ans);
    for(mul = 1;head != NULL;(mul *= 10))
    {
        sum = sum + (mul * (head->data));
        head = head->next;
    }
    return sum;
}

Answer 1

我在您的代码中发现以下逻辑错误:

1. 您忘记在内部 while 循环开始之前将 carry 初始化为 0。
2. 在使用乘法计算项时，您忘记使用进位。
3. 您忘记在内部 while 循环结束后使用 carry。

这是更正后的函数。

int multiply(struct node *first, struct node *second)
{
    struct node *ans = NULL;
    struct node *head = NULL;
    struct node *rev_first = NULL;
    struct node *rev_second = NULL;
    int i, temp, mul, ten, carry=0, sum = 0;
    rev_first = reverse(first);
    rev_second = reverse(second);

    while(rev_first != NULL)
    {
        ten = 1;
        carry = 0;   // LINE ADDED
        sum = 0;
        head = rev_second;
        while(head != NULL)
        {
            mul = (rev_first->data) * (head->data) + carry; // Added carry.
            carry = mul / 10;
            temp = mul % 10;
            sum = sum + (temp * ten);
            ten = ten * 10;
            head = head->next;
        }

        // ADDED THIS IF BLOCK.
        // If there is any carry, use it.
        if ( carry > 0 )
        {
           sum += carry * ten;
        }

        push(&ans, sum);
        printList(ans);
        rev_first = rev_first->next;
    }

    sum = 0;
    head = reverse(ans);
    for(mul = 1;head != NULL;(mul *= 10))
    {
        sum = sum + (mul * (head->data));
        head = head->next;
    }
    return sum;
}

PS

以下函数有助于追踪问题。

void printList(struct node* list)
{
   for ( ; list != NULL; list = list->next )
   {
      printf("%d ", list->data);
   }
   printf("\n");
}