大数乘法

大数相乘，首先考虑简单的情况，就是一个大数乘以一个相对较小的数，假设都是正整数；
这里我用链表来表示大数，首指针指向最低位，比如123456 用链表就表示成 head->6->5->4->3->2->1
做完乘法后再将链表逆序，就可以打印了（或者不逆序用递归打印也行）
当然用数组表示大数也可以，但是扩容不方便。

#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 *h, int n)
{
    node *p;
    node *q;
    _type v;

    /* multiply without carry */
    for (p=h; p != NULL; p=p->next) {
        p->val *= n;
    }

    /* carry */
    for (p=h,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=h; 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 h;
}

其他辅助代码

/*
 * reverse a list
 * */
node * reverse(node *h)
{
    node *p,*q,*tmp;

    for (p=h,q=NULL; p != NULL; p=tmp) {
        tmp = p->next;
        p->next = q;
        q = p;
    }
    return q;
}


/* 打印大数 */
void print_val(node *h)
{
    node *p;

    for (p=h; p!=NULL; p=p->next) {
        printf("%d", p->val);
    }
    printf("\n");
}


/* 从字符串生成一个大数 (逆序) */
node *init(char *str)
{
    node *h,*p;
    
    h = NULL;
    while (*str) {
        if ((p=(node *)malloc(sizeof(node))) == NULL) exit(1);
        p->next = h;
        h = p;
        p->val = *str - '0'; /* base above 10 need further process */
        str ++;
    }
    return h;
}

测试
int main()
{
    char *str = "12345678";
    node *h;

    h = init(str);
    h = mul(h, 45);
    h = reverse(h);
    print_val(h);
    return 0;
}