实现Karatsuba乘法C语言代码

下面是实现Karatsuba乘法的C语言代码，同样使用了递归的方法：

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

// 去除字符串前导0
void removeLeadingZeros(char* str) {
    int i = 0;
    while (str[i] == '0') {
        i++;
    }
    if (i == strlen(str)) {
        str[0] = '0';
        str[1] = '\0';
    } else {
        memmove(str, str + i, strlen(str) - i + 1);
    }
}

// Karatsuba乘法
char* karatsuba(const char* num1, const char* num2) {
    int len1 = strlen(num1);
    int len2 = strlen(num2);
    if (len1 == 0 || len2 == 0) {
        char* res = (char*)malloc(2 * sizeof(char));
        res[0] = '0';
        res[1] = '\0';
        return res;
    }
    if (len1 == 1 || len2 == 1) {
        int res = atoi(num1) * atoi(num2);
        char* str = (char*)malloc(12 * sizeof(char)); // 最多11位数
        sprintf(str, "%d", res);
        return str;
    }
    int n = (len1 > len2 ? len1 : len2);
    if (n % 2 != 0) {
        n++;
    }
    char* x1 = (char*)malloc((n/2 + 1) * sizeof(char));
    char* x0 = (char*)malloc((n/2 + 1) * sizeof(char));
    char* y1 = (char*)malloc((n/2 + 1) * sizeof(char));
    char* y0 = (char*)malloc((n/2 + 1) * sizeof(char));
    strncpy(x1, num1, len1 - n/2);
    x1[len1 - n/2] = '\0';
    strncpy(x0, num1 + len1 - n/2, n/2);
    x0[n/2] = '\0';
    strncpy(y1, num2, len2 - n/2);
    y1[len2 - n/2] = '\0';
    strncpy(y0, num2 + len2 - n/2, n/2);
    y0[n/2] = '\0';

    char* z2 = karatsuba(x1, y1);
    char* z0 = karatsuba(x0, y0);
    char* x1x0 = (char*)malloc((n/2 + 1 + 1) * sizeof(char));
    sprintf(x1x0, "%d", atoi(x1) + atoi(x0));
    char* y1y0 = (char*)malloc((n/2 + 1 + 1) * sizeof(char));
    sprintf(y1y0, "%d", atoi(y1) + atoi(y0));
    char* z1 = karatsuba(x1x0, y1y0);
    z1 = (char*)realloc(z1, (2 * n + 1) * sizeof(char));
    int lenz1 = strlen(z1);
    int i;
    for (i = 0; i < lenz1; i++) {
        z1[i] -= '0';
    }
    for (i = 0; i < n; i++) {
        z1[i] += (i < lenz1 ? z1[i] + '0' : '0');
    }
    z1[n] = '\0';
    removeLeadingZeros(z1);
    z2 = (char*)realloc(z2, (2 * n + 1) * sizeof(char));
    z0 = (char*)realloc(z0, (n + 1) * sizeof(char));
    lenz1 = strlen(z1);
    int lenz2 = strlen(z2);
    for (i = 0; i < n; i++) {
        z2[i] = (i < lenz2 ? z2[i] : '0');
        z0[i] = (i < strlen(z0) ? z0[i] : '0');
    }
    z2[n] = '\0';
    z0[n] = '\0';
    char* res = (char*)malloc((2 * n + 1) * sizeof(char));
    int carry = 0;
    for (i = n - 1; i >= 0; i--) {
        int sum = z2[i] + z1[i] + z0[i] - '0' - '0' - carry;
        res[i+1] = sum % 10 + '0';
        carry = sum / 10;
    }
    res[0] = carry + '0';
    removeLeadingZeros(res);
    free(x1);
    free(x0);
    free(y1);
    free(y0);
    free(x1x0);
    free(y1y0);
    free(z2);
    free(z0);
    free(z1);
    return res;
}

int main() {
    char num1[] = "123456789";
    char num2[] = "987654321";
    char* res = karatsuba(num1, num2);
    printf("%s\n", res);
    free(res);
    return 0;
}

需要注意的是，在计算``z1``时，需要递归调用``karatsuba``函数，而最后的结果需要去除前导0。此外，为了防止溢出，数组长度需要额外加1。