用C语言实现动态数组的大整数乘法

时间:2022-01-21 04:20:20

描述:

要求你用C语言实现两个数相乘,这两个数字的位数可能很大,而且还可能有不合法的输入。

具体做法:

首先,大整数乘法的主要部分要知道:
for (i = 0; i < lenA; i++)
for (j = 0; j < lenB; j++)
ans[i + j] += (int)(pA[i] - '0') * (int)(pB[j] - '0');

其次就是处理用户的输入了,这里我们给每个数字预分配1024个字节的空间,对于用户的输入我们采取逐个字符读入,直到碰到空格或者换行符。如果用户输入的字符多于1024,那么我们再调用realloc这个函数再次分配更多的空间。最后再扫一遍字符串验证字符串的合法性。大整数乘法就不多说了,先把两个数字反转过来,然后用上述代码计算出的ans数组,最后处理ans数组的进位和前导0。

代码:

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

#define MAX_LINE 1024

typedef char *string;

typedef enum {false, true} bool;

void swap_char(char *pa, char *pb)
{
    char tmp = *pa;
    *pa = *pb;
    *pb = tmp;
}

int main()
{
    // freopen("1.txt", "r", stdin);

    int i, j;
    int n, size;
    char c;
    string a = NULL, b = NULL;

    int *ans = NULL, lenAns = 0;

    while (true) {

        int la = 0, lb = 0;

        bool isOk;
        bool isFa, isFb;
        string pA = NULL, pB = NULL;
        int lenA, lenB;
        int up;

        size = MAX_LINE;
        if ((a = (string)malloc((size) * sizeof(char))) == NULL)
            exit(1);
        if ((b = (string)malloc((size) * sizeof(char))) == NULL) {
            free(a);
            a = NULL;
            exit(1);
        }

        while (!((c = getchar()) != ' ' && c != '\n'));

        n = 0;
        a[n++] = c;
        while ((c = getchar()) != ' ' && c != '\n') {
            a[n++] = c;
            if (n >= size) {
                if ((a = (string)realloc(a, (size * 2) * sizeof(char))) == NULL) {
                    free(a);
                    free(b);
                    a = b = NULL;
                    exit(1);
                }
                size  = _msize(a);
            }
        }
        a[n] = 0;
        la = n;
        n = 0;

        while (!((c = getchar()) != ' ' && c != '\n'));

        b[n++] = c;

        size = MAX_LINE;
        while ((c = getchar()) != ' ' && c != '\n') {
            b[n++] = c;
            if (n >= size)
                if ((b = (string)realloc(b, (size * 2) * sizeof(char))) == NULL) {
                    free(a);
                    free(b);
                    a = b = NULL;
                    exit(1);
                }
                size  = _msize(b);
        }
        b[n] = 0;
        lb = n;

        isOk = true;

        isFa = a[0] == '-' ? true : false;
        isFb = b[0] == '-' ? true : false;

        pA = isFa ? a + 1 : a;
        pB = isFb ? b + 1 : b;

        lenA = isFa ? la - 1 : la;
        lenB = isFb ? lb - 1 : lb;

        pA = pA[0] == '+' ? pA + 1 : pA;
        lenA = pA[0] == '+' ? lenA - 1 : lenA;
        pB = pB[0] == '+' ? pB + 1 : pB;
        lenB = pB[0] == '+' ? lenB - 1 : lenB;

        for (i = 0; i < lenA; i++)
            if (!isdigit(pA[i])) {
                puts("Please input again!");
                isOk = false;
                break;
            }
        if (!isOk) {
            free(a);
            free(b);
            a = b = NULL;
            continue;
        }
        for (i = 0; i < lenB; i++)
            if (!isdigit(pB[i])) {
                puts("Please input again!");
                isOk = false;
                break;
            }
        if (!isOk) {
            free(a);
            free(b);
            a = b = NULL;
            continue;
        }
        for (i = 0; i < lenA / 2; i++)
            swap_char(pA + i, pA + lenA - i - 1);
        for (i = 0; i < lenB / 2; i++)
            swap_char(pB + i, pB + lenB - i - 1);

        if ((ans = (int *)malloc((lenA + lenB + 10) * sizeof(int))) == NULL) {
            free(a);
            free(b);
            a = b = NULL;
            exit(1);
        }
        for (i = 0; i < lenA + lenB + 10; i++)
            ans[i] = 0;

        for (i = 0; i < lenA; i++)
            for (j = 0; j < lenB; j++)
                ans[i + j] += (int)(pA[i] - '0') * (int)(pB[j] - '0');

        up = 0;
        lenAns = lenA + lenB;
        for (i = 0; i < lenAns; i++) {
            int tmp = ans[i];
            ans[i] = (ans[i] + up) % 10;
            up = (tmp + up) / 10;
        }
        for (; lenAns > 0 && ans[lenAns - 1] == 0; lenAns--);

        if (lenAns == 0) {
            puts("0");
            continue;
        }
        for (; up != 0; lenAns++)
            ans[lenAns] = up % 10, up /= 10;
        if (!((isFa && isFb) || (!isFa && !isFb)))
            putchar('-');
        for (i = lenAns - 1; i >= 0; i--)
            printf("%d", ans[i]);
        putchar('\n');

        free(a);
        free(b);
        free(ans);
        a = b = NULL;
        ans = NULL;
    }
    return 0;
}