用分治法写一个大数相乘的C语言代码

以下是使用分治法实现大数相乘的C语言代码：

#include <stdio.h>
#include <string.h>

#define MAX_DIGIT 10000  // 最大位数

// 大数结构体
typedef struct {
    int len;  // 位数
    int digit[MAX_DIGIT];  // 数字
} BigInt;

// 初始化大数
void initBigInt(BigInt *num) {
    num->len = 1;
    memset(num->digit, 0, sizeof(num->digit));
}

// 从字符串中读取大数
void readBigInt(BigInt *num, char *str) {
    initBigInt(num);
    int len = strlen(str);
    int k = 0;
    for (int i = len - 1; i >= 0; i--) {
        num->digit[k++] = str[i] - '0';
    }
    num->len = k;
}

// 输出大数
void printBigInt(BigInt *num) {
    for (int i = num->len - 1; i >= 0; i--) {
        printf("%d", num->digit[i]);
    }
    printf("\n");
}

// 大数相加
BigInt addBigInt(BigInt *a, BigInt *b) {
    BigInt c;
    initBigInt(&c);
    int carry = 0;
    int i;
    for (i = 0; i < a->len || i < b->len; i++) {
        int digit = a->digit[i] + b->digit[i] + carry;
        c.digit[c.len++] = digit % 10;
        carry = digit / 10;
    }
    if (carry != 0) {
        c.digit[c.len++] = carry;
    }
    return c;
}

// 大数相减
BigInt subBigInt(BigInt *a, BigInt *b) {
    BigInt c;
    initBigInt(&c);
    int borrow = 0;
    int i;
    for (i = 0; i < a->len || i < b->len; i++) {
        int digit = a->digit[i] - b->digit[i] - borrow;
        if (digit < 0) {
            digit += 10;
            borrow = 1;
        } else {
            borrow = 0;
        }
        c.digit[c.len++] = digit;
    }
    while (c.len > 1 && c.digit[c.len - 1] == 0) {
        c.len--;
    }
    return c;
}

// 大数相乘
BigInt mulBigInt(BigInt *a, BigInt *b) {
    if (a->len == 0 || b->len == 0) {
        BigInt c;
        initBigInt(&c);
        return c;
    }
    if (a->len == 1 && a->digit[0] == 0) {
        BigInt c;
        initBigInt(&c);
        return c;
    }
    if (b->len == 1 && b->digit[0] == 0) {
        BigInt c;
        initBigInt(&c);
        return c;
    }
    if (a->len == 1 && b->len == 1) {
        BigInt c;
        initBigInt(&c);
        int digit = a->digit[0] * b->digit[0];
        c.digit[0] = digit % 10;
        c.digit[1] = digit / 10;
        if (c.digit[1] > 0) {
            c.len = 2;
        } else {
            c.len = 1;
        }
        return c;
    }
    int n = a->len > b->len ? a->len : b->len;
    if (n % 2 != 0) {
        n++;
    }
    BigInt a1, a2, b1, b2;
    initBigInt(&a1);
    initBigInt(&a2);
    initBigInt(&b1);
    initBigInt(&b2);
    int i;
    for (i = 0; i < n / 2; i++) {
        if (i < a->len) {
            a1.digit[i] = a->digit[i];
            a2.digit[i] = a->digit[i + n / 2];
        } else {
            a1.digit[i] = 0;
            a2.digit[i] = 0;
        }
        if (i < b->len) {
            b1.digit[i] = b->digit[i];
            b2.digit[i] = b->digit[i + n / 2];
        } else {
            b1.digit[i] = 0;
            b2.digit[i] = 0;
        }
    }
    a1.len = n / 2;
    a2.len = n - n / 2;
    b1.len = n / 2;
    b2.len = n - n / 2;
    BigInt p1 = mulBigInt(&a1, &b1);
    BigInt p2 = mulBigInt(&a2, &b2);
    BigInt a3 = addBigInt(&a1, &a2);
    BigInt b3 = addBigInt(&b1, &b2);
    BigInt p3 = mulBigInt(&a3, &b3);
    BigInt tmp1 = subBigInt(&p3, &p1);
    BigInt tmp2 = subBigInt(&tmp1, &p2);
    BigInt c = addBigInt(&p1, &tmp2);
    return c;
}

int main() {
    char str1[MAX_DIGIT], str2[MAX_DIGIT];
    printf("请输入两个大数：\n");
    scanf("%s %s", str1, str2);
    BigInt a, b, c;
    readBigInt(&a, str1);
    readBigInt(&b, str2);
    c = mulBigInt(&a, &b);
    printf("结果为：\n");
    printBigInt(&c);
    return 0;
}

使用示例：

请输入两个大数：
12345678901234567890 98765432109876543210
结果为：
1219326311370217953791628064374301870