大数乘法(二)

前面做了大数跟一个相对小的数相乘，如果需要求两个大数相乘，那么把前面的代码稍稍修改即可完成

#include <stdio.h>

typedef int _type;
typedef struct node{
    _type val;
    struct node *next;
} node;

#define _SYSTEM 10

/*
 * A big num that is denoted by list, multiply by n (a small number)


 * 这里做了修改，把相乘的结果放到新的链表，新链表长度自动扩展


  * */
node *mul(node **head, node *h, int n)
{
    node **q;
    node *p;
    _type v;

    /* multiply without carry */
    for (q=head; h != NULL; h=h->next) {
        if (*q == NULL) {
            if ((*q=(node *)malloc(sizeof(node))) == NULL) exit(1);
            (*q)->val = 0;
            (*q)->next = NULL;
        }
        (*q)->val += (h->val * n);
        q = &((*q)->next);

    }
    /* carry */
    for (p=(*head),v=0; p != NULL; p=p->next) {
        p->val += v;
        v = p->val / _SYSTEM;
        p->val %= _SYSTEM;
    }
    /* need new node(s) to contain last carry */
    if (v) {
        for (p=(*head); p->next != NULL; p=p->next);
        while (v) {
            if ((p->next = (node *)malloc(sizeof(node))) == NULL) exit(1);
            p = p->next;
            p->next = NULL;
            p->val = v % _SYSTEM;
            v /= _SYSTEM;
        }
    }

    return (*head);
}

/*
 * multiply of two big number
 * */
node *multiply(node *h1, node *h2)
{
    node *p;
    node *head;
    node *q;

    head = NULL;
    q = NULL;
    for (p=h2; p != NULL; p=p->next) {
        if (p->val > 0)
            mul(&q, h1, p->val);
        if (head == NULL)
            head = q;
        q = q->next;
    }
    return head;
}

测试
int main()
{
    char *str1 = "12345678";
    char *str2 = "12345678";
    node *h1,*h2;
    node *h;

    h1 = init(str1);
    h2 = init(str2);
    h = multiply(h1, h2);
    h = reverse(h);
    print_val(h);
    return 0;
}