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

//本程序使用long long类型，所以输入输出均可以使用scanf和printf

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

struct Node{
int digit;
struct Node *next;
};

typedef struct Node node;

void print_num(node *head)//输出链表表示的大整数
{
node *p = head->next;
while(p != NULL){
printf("%d", p->digit);
p = p->next;
}
printf("\n");
}

node * create_num(int n)//生成n位随机大整数
{
node *head = (node*)malloc(sizeof(node));
head->next = NULL;

srand((unsigned int)time(NULL));
for(int i = 1;i <= n;i++){
node *p = (node*)malloc(sizeof(node));
if(i == 1) p->digit = rand()%9+1;//第一位不能为0
else p->digit = rand()%10;
p->next = head->next;
head->next = p;
}
return head;
}

int get_len(node *head)//获取链表长度
{
node *p = head->next;
int len = 0;
while(p != NULL){
len++;
p = p->next;
}
return len;
}

void pad_zero(node *head, int n)//在链表左侧补n个0，使其长度为n
{
for(int i = 1;i <= n;i++){
node *p = (node*)malloc(sizeof(node));
p->digit = 0;
p->next = head->next;
head->next = p;
}
}

node * add(node *a, node *b)//链表表示的大整数加法
{
node *head = (node*)malloc(sizeof(node));
head->next = NULL;

node *p1 = a->next, *p2 = b->next;
int carry = 0;
while(p1 != NULL && p2 != NULL){
node *p = (node*)malloc(sizeof(node));
p->digit = p1->digit + p2->digit + carry;
carry = p->digit / 10;
p->digit %= 10;
p->next = head->next;
head->next = p;
p1 = p1->next;
p2 = p2->next;
}
while(p1 != NULL){
node *p = (node*)malloc(sizeof(node));
p->digit = p1->digit + carry;
carry = p->digit / 10;
p->digit %= 10;
p->next = head->next;
head->next = p;
p1 = p1->next;
}
while(p2 != NULL){
node *p = (node*)malloc(sizeof(node));
p->digit = p2->digit + carry;
carry = p->digit / 10;
p->digit %= 10;
p->next = head->next;
head->next = p;
p2 = p2->next;
}
if(carry != 0){
node *p = (node*)malloc(sizeof(node));
p->digit = carry;
p->next = head->next;
head->next = p;
}
return head;
}

node * sub(node *a, node *b)//链表表示的大整数减法
{
node *head = (node*)malloc(sizeof(node));
head->next = NULL;

node *p1 = a->next, *p2 = b->next;
int borrow = 0;
while(p1 != NULL && p2 != NULL){
node *p = (node*)malloc(sizeof(node));
int tmp = p1->digit - p2->digit - borrow;
borrow = 0;
if(tmp < 0){
tmp += 10;
borrow = 1;
}
p->digit = tmp;
p->next = head->next;
head->next = p;
p1 = p1->next;
p2 = p2->next;
}
while(p1 != NULL){
node *p = (node*)malloc(sizeof(node));
int tmp = p1->digit - borrow;
borrow = 0;
if(tmp < 0){
tmp += 10;
borrow = 1;
}
p->digit = tmp;
p->next = head->next;
head->next = p;
p1 = p1->next;
}
if(borrow != 0){
printf("Error: a < b\n");
return NULL;
}
return head;
}

int main()
{
node *a, *b, *c;
int n = rand()%50+1;//生成1-50位随机整数
a = create_num(n);
b = create_num(n);

printf("a = ");
print_num(a);
printf("b = ");
print_num(b);

if(get_len(a) > get_len(b)) pad_zero(b, get_len(a)-get_len(b));
else pad_zero(a, get_len(b)-get_len(a));

printf("a+b = ");
c = add(a, b);
print_num(c);
printf("a-b = ");
c = sub(a, b);
if(c != NULL) print_num(c);

return 0;
}