用C语言利用链表计算大数乘法

实现大数乘法可以使用链表来存储每一位数字，具体实现步骤如下：

1. 定义链表结构体，包含一个int类型的数据域和指向下一个节点的指针域。

typedef struct node {
    int data;
    struct node *next;
} Node;

2. 定义两个字符串，分别存储要相乘的两个大数。

char num1[] = "123456789";
char num2[] = "987654321";

3. 将两个字符串转化为链表，将每一位数字存储到链表中。

Node *num1List = NULL;
Node *num2List = NULL;

for (int i = strlen(num1) - 1; i >= 0; i--) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = num1[i] - '0';
    newNode->next = num1List;
    num1List = newNode;
}

for (int i = strlen(num2) - 1; i >= 0; i--) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = num2[i] - '0';
    newNode->next = num2List;
    num2List = newNode;
}

4. 定义一个新的链表，用来存储计算结果。

Node *resultList = NULL;

5. 从链表num2List的最低位开始，依次将每一位与链表num1List中的每一位相乘，将计算结果相加得到最终结果。具体实现过程如下：

Node *num2Node = num2List;
int shift = 0; // 用于记录当前位数，也就是需要在结果中加上的0的个数

while (num2Node != NULL) {
    Node *num1Node = num1List;
    int carry = 0; // 用于记录进位
    Node *tempResultList = NULL;

    // 在结果中加上shift个0
    for (int i = 0; i < shift; i++) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = 0;
        newNode->next = tempResultList;
        tempResultList = newNode;
    }

    while (num1Node != NULL) {
        int tempResult = num1Node->data * num2Node->data + carry;
        carry = tempResult / 10;

        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = tempResult % 10;
        newNode->next = tempResultList;
        tempResultList = newNode;

        num1Node = num1Node->next;
    }

    // 如果还有进位，需要将进位加到结果的最高位
    if (carry > 0) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = carry;
        newNode->next = tempResultList;
        tempResultList = newNode;
    }

    // 将tempResultList中的结果与resultList相加
    Node *tempNode = tempResultList;
    Node *resultNode = resultList;
    carry = 0;

    while (tempNode != NULL || carry > 0) {
        int tempData1 = resultNode == NULL ? 0 : resultNode->data;
        int tempData2 = tempNode == NULL ? 0 : tempNode->data;
        int tempResult = tempData1 + tempData2 + carry;
        carry = tempResult / 10;

        if (resultNode == NULL) {
            Node *newNode = (Node *)malloc(sizeof(Node));
            newNode->data = tempResult % 10;
            newNode->next = NULL;
            resultList = newNode;
            resultNode = resultList;
        } else {
            resultNode->data = tempResult % 10;

            if (resultNode->next == NULL && (tempNode != NULL || carry > 0)) {
                Node *newNode = (Node *)malloc(sizeof(Node));
                newNode->data = 0;
                newNode->next = NULL;
                resultNode->next = newNode;
            }

            resultNode = resultNode->next;
        }

        tempNode = tempNode == NULL ? NULL : tempNode->next;
    }

    shift++;
    num2Node = num2Node->next;
}

6. 将计算结果从链表中取出，输出到控制台。

Node *tempNode = resultList;

while (tempNode != NULL) {
    printf("%d", tempNode->data);
    tempNode = tempNode->next;
}

printf("\n");

完整代码如下：

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

typedef struct node {
    int data;
    struct node *next;
} Node;

int main() {
    char num1[] = "123456789";
    char num2[] = "987654321";

    Node *num1List = NULL;
    Node *num2List = NULL;

    for (int i = strlen(num1) - 1; i >= 0; i--) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = num1[i] - '0';
        newNode->next = num1List;
        num1List = newNode;
    }

    for (int i = strlen(num2) - 1; i >= 0; i--) {
        Node *newNode = (Node *)malloc(sizeof(Node));
        newNode->data = num2[i] - '0';
        newNode->next = num2List;
        num2List = newNode;
    }

    Node *resultList = NULL;

    Node *num2Node = num2List;
    int shift = 0;

    while (num2Node != NULL) {
        Node *num1Node = num1List;
        int carry = 0;
        Node *tempResultList = NULL;

        for (int i = 0; i < shift; i++) {
            Node *newNode = (Node *)malloc(sizeof(Node));
            newNode->data = 0;
            newNode->next = tempResultList;
            tempResultList = newNode;
        }

        while (num1Node != NULL) {
            int tempResult = num1Node->data * num2Node->data + carry;
            carry = tempResult / 10;

            Node *newNode = (Node *)malloc(sizeof(Node));
            newNode->data = tempResult % 10;
            newNode->next = tempResultList;
            tempResultList = newNode;

            num1Node = num1Node->next;
        }

        if (carry > 0) {
            Node *newNode = (Node *)malloc(sizeof(Node));
            newNode->data = carry;
            newNode->next = tempResultList;
            tempResultList = newNode;
        }

        Node *tempNode = tempResultList;
        Node *resultNode = resultList;
        carry = 0;

        while (tempNode != NULL || carry > 0) {
            int tempData1 = resultNode == NULL ? 0 : resultNode->data;
            int tempData2 = tempNode == NULL ? 0 : tempNode->data;
            int tempResult = tempData1 + tempData2 + carry;
            carry = tempResult / 10;

            if (resultNode == NULL) {
                Node *newNode = (Node *)malloc(sizeof(Node));
                newNode->data = tempResult % 10;
                newNode->next = NULL;
                resultList = newNode;
                resultNode = resultList;
            } else {
                resultNode->data = tempResult % 10;

                if (resultNode->next == NULL && (tempNode != NULL || carry > 0)) {
                    Node *newNode = (Node *)malloc(sizeof(Node));
                    newNode->data = 0;
                    newNode->next = NULL;
                    resultNode->next = newNode;
                }

                resultNode = resultNode->next;
            }

            tempNode = tempNode == NULL ? NULL : tempNode->next;
        }

        shift++;
        num2Node = num2Node->next;
    }

    Node *tempNode = resultList;

    while (tempNode != NULL) {
        printf("%d", tempNode->data);
        tempNode = tempNode->next;
    }

    printf("\n");

    return 0;
}