用C++用链表实现大整数加减法操作： 32 位机器直接操作的数据最大为 32 个 bit，若超过 32bit，则需要单独设计算法。在这 里，可以用链表每个结点存储大整数的每一位的十进制数字，则可以进行大整数的算数运算， 该实验仅实现加减法操作。 要求: 1， 随机产生 2 个 1~50 位的数字串，并存储到 2 个链表中。 2， 进行加法或减法操作，结果存储到新的链表中。 3， 打印运算结果。

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

#define MAX_DIGIT 50

// 链表节点
typedef struct Node {
int digit; // 数字
struct Node *next; // 指向下一个节点
} Node;

// 随机生成 n 位数
Node *gen_num(int n) {
Node *head = NULL, *tail = NULL;
int i;
// 最高位随机生成，不能是 0，保证数字不会以 0 开头
int digit = rand() % 9 + 1;
head = tail = (Node *) malloc(sizeof(Node));
head->digit = digit;
head->next = NULL;
// 随机生成剩下的 n-1 位数
for (i = 1; i < n; i++) {
tail->next = (Node *) malloc(sizeof(Node));
tail = tail->next;
tail->digit = rand() % 10;
tail->next = NULL;
}
return head;
}

// 打印数字
void print_num(Node *num) {
while (num) {
printf("%d", num->digit);
num = num->next;
}
printf("\n");
}

// 链表求长度
int len(Node *num) {
int cnt = 0;
while (num) {
cnt++;
num = num->next;
}
return cnt;
}

// 将链表转换成数组
int *to_array(Node *num, int *size) {
int len = 0, i;
int *array;
Node *p;
// 求出链表长度
len = 0;
p = num;
while (p) {
len++;
p = p->next;
}
// 创建数组并将链表中的数字复制到数组中
array = (int *) malloc(len * sizeof(int));
p = num;
for (i = 0; i < len; i++) {
array[i] = p->digit;
p = p->next;
}
// 返回数组大小
*size = len;
return array;
}

// 将数组转换成链表
Node *to_list(int *array, int size) {
Node *head = NULL, *tail = NULL;
int i;
// 创建头结点
head = tail = (Node *) malloc(sizeof(Node));
head->digit = array[0];
head->next = NULL;
// 向链表中添加数字
for (i = 1; i < size; i++) {
tail->next = (Node *) malloc(sizeof(Node));
tail = tail->next;
tail->digit = array[i];
tail->next = NULL;
}
return head;
}

// 大整数加法
Node *add(Node *num1, Node *num2) {
int carry = 0, sum;
Node *head = NULL, *tail = NULL;
while (num1 || num2) {
sum = carry;
if (num1) {
sum += num1->digit;
num1 = num1->next;
}
if (num2) {
sum += num2->digit;
num2 = num2->next;
}
carry = sum / 10;
sum %= 10;
if (head == NULL) {
head = tail = (Node *) malloc(sizeof(Node));
head->digit = sum;
head->next = NULL;
} else {
tail->next = (Node *) malloc(sizeof(Node));
tail = tail->next;
tail->digit = sum;
tail->next = NULL;
}
}
if (carry) {
tail->next = (Node *) malloc(sizeof(Node));
tail = tail->next;
tail->digit = carry;
tail->next = NULL;
}
return head;
}

// 比较两个数字的大小，如果 num1 < num2，则返回 -1；如果 num1 == num2，则返回 0；如果 num1 > num2，则返回 1
int cmp(Node *num1, Node *num2) {
int len1 = len(num1), len2 = len(num2);
if (len1 < len2) {
return -1;
} else if (len1 > len2) {
return 1;
} else {
while (num1 && num2) {
if (num1->digit < num2->digit) {
return -1;
} else if (num1->digit > num2->digit) {
return 1;
} else {
num1 = num1->next;
num2 = num2->next;
}
}
return 0;
}
}

// 大整数减法
Node *sub(Node *num1, Node *num2) {
int borrow = 0, diff;
Node *head = NULL, *tail = NULL;
int cmp_result = cmp(num1, num2);
if (cmp_result == 0) { // num1 == num2
head = (Node *) malloc(sizeof(Node));
head->digit = 0;
head->next = NULL;
return head;
}
if (cmp_result == -1) { // num1 < num2，交换 num1 和 num2
Node *tmp = num1;
num1 = num2;
num2 = tmp;
}
while (num1) {
diff = borrow + num1->digit;
if (num2) {
diff -= num2->digit;
num2 = num2->next;
}
borrow = 0;
if (diff < 0) {
borrow = -1;
diff += 10;
}
if (head == NULL) {
head = tail = (Node *) malloc(sizeof(Node));
head->digit = diff;
head->next = NULL;
} else {
tail->next = (Node *) malloc(sizeof(Node));
tail = tail->next;
tail->digit = diff;
tail->next = NULL;
}
num1 = num1->next;
}
// 移除前导 0
while (head->next && head->digit == 0) {
Node *tmp = head;
head = head->next;
free(tmp);
}
return head;
}

int main() {
srand(time(NULL));
Node *num1, *num2, *sum, *diff;
int size1, size2, *array1, *array2;
// 随机生成两个数字串
size1 = rand() % MAX_DIGIT + 1;
size2 = rand() % MAX_DIGIT + 1;
num1 = gen_num(size1);
num2 = gen_num(size2);
// 打印数字串
printf("num1 = ");
print_num(num1);
printf("num2 = ");
print_num(num2);
// 大整数加法
sum = add(num1, num2);
printf("sum = ");
print_num(sum);
// 大整数减法
diff = sub(num1, num2);
printf("diff = ");
print_num(diff);
// 释放内存
while (num1) {
Node *tmp = num1;
num1 = num1->next;
free(tmp);
}
while (num2) {
Node *tmp = num2;
num2 = num2->next;
free(tmp);
}
while (sum) {
Node *tmp = sum;
sum = sum->next;
free(tmp);
}
while (diff) {
Node *tmp = diff;
diff = diff->next;
free(tmp);
}
return 0;
}