如下内容，要求实现加、减运算，即能从键盘上输入两个大整数？该怎么解决？

Question

使用单链表实现不限大小的整数，每个结点存储一位数字。要求实现加、减运算，即能从键盘上输入两个大整数，比如：12345123451234512345和-11111111111111111111，则加的结果应为：01234012340123401234；减的结果应为：23456234562345623456。你的程序能运算并输出上述结果。要求：使用带表头结点的单链表实现，把符号位存在表头结点中。所以，你得先实现带表头结点的单链表，然后把每一个大数用一个链表来表示，再运算。

Answer 1

貌似写的太长了。。。= =
另外就是没有完全测试，说不定某种输入情况下不对了，如果不对请告诉我～

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

#define POS 0
#define NEG 1

typedef struct _node {
int value;
struct _node *next;
} list_node, *integer;

int greater(integer x, integer y) {
int ax = abs(x->value), ay = abs(y->value);
if (ax > ay) return 1;
if (ax < ay) return 0;

int res;
list_node *nx = x->next, *ny = y->next;
while (nx != 0) {
if (nx->value > ny->value) res = 1;
else if (nx->value < ny->value) res = 0;
nx = nx->next;
ny = ny->next;
}

return res;
}

int is_zero(integer n) {
return n->value == 1 && n->next->value == 0;
}

void free_node_list(list_node *start) {
list_node *node;
while (start) {
node = start;
start = start->next;
free(node);
}
}

void free_node(list_node *node) {
free(node);
}

list_node * make_node(int value) {
list_node *node = (list_node *) malloc(sizeof(list_node));
node->value = value;
node->next = 0;
return node;
}

integer negate(integer n) {
list_node *new_header;
if (is_zero(n))
new_header = make_node(0);
else
new_header = make_node(-(n->value));

new_header->next = n->next;
return new_header;
}

void mutable_negate(integer n) {
if (is_zero(n))
return;

n->value = -(n->value);
}

void insert_after(list_node *pos, list_node *new_node) {
list_node *temp_node = pos->next;
new_node->next = temp_node;
pos->next = new_node;
}

list_node * add_node(list_node *pos, int value) {
list_node *node = make_node(value);
pos->next = node;
return node;
}

void trim_trailing_zeros(integer i, int sign) {
list_node *start, *last = i, *node;
for (node = i->next; node != 0; node = node->next)
if (node->value != 0)
last = node;

start = last->next;
last->next = 0;

while (start) {
node = start;
start = start->next;
-- i->value;
free(node);
}

if (i->value == 0) {
i->next = make_node(0);
i->value = 1;
return;
}

if (sign == NEG) {
i->value = -i->value;
}
}

integer do_add(integer x, integer y) {
list_node *header = make_node(x->value);
list_node *nx = x->next, *ny = y->next, *last = header;
int sum, carry = 0;

while (ny != 0) {
sum = nx->value + ny->value + carry;
if (sum >= 10) {
sum -= 10;
carry = 1;
} else {
carry = 0;
}
last = add_node(last, sum);
nx = nx->next;
ny = ny->next;
}

while (nx != 0) {
sum = nx->value + carry;
if (sum >= 10) {
sum -= 10;
carry = 1;
} else {
carry = 0;
}
last = add_node(last, sum);
nx = nx->next;
}

if (carry != 0) {
add_node(last, 1);
++header->value;
}

return header;
}

integer do_subtract(integer x, integer y) {
list_node *header = make_node(x->value);
list_node *nx = x->next, *ny = y->next, *last = header;
int diff, borrow = 0;

while (ny != 0) {
diff = nx->value - ny->value - borrow;
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
last = add_node(last, diff);
nx = nx->next;
ny = ny->next;
}

while (nx != 0) {
diff = nx->value - borrow;
if (diff < 0) {
diff += 10;
borrow = 1;
} else {
borrow = 0;
}
last = add_node(last, diff);
nx = nx->next;
}

trim_trailing_zeros(header, POS);
return header;
}

integer add_positive(integer x, integer y) {
if (greater(x, y)) return do_add(x, y);
else return do_add(y, x);
}

integer subtract_positive(integer x, integer y) {
if (greater(x, y)) return do_subtract(x, y);
else {
integer res = do_subtract(y, x);
mutable_negate(res);
return res;
}
}

integer add(integer x, integer y) {
if (x->value > 0) {
if (y->value > 0) return add_positive(x, y);
else {
integer ny = negate(y);
integer res = subtract_positive(x, ny);
free_node(ny);
return res;
}
} else {
if (y->value > 0) {
integer nx = negate(x);
integer res = subtract_positive(y, nx);
free_node(nx);
return res;
}
else {
integer nx = negate(x), ny = negate(y);
integer res = add_positive(nx, ny);
mutable_negate(res);
free_node(nx);
free_node(ny);
return res;
}
}
}

integer subtract(integer x, integer y) {
if (x->value > 0) {
if (y->value > 0) return subtract_positive(x, y);
else {
integer ny = negate(y);
integer res = add_positive(x, ny);
free_node(ny);
return res;
}
} else {
if (y->value > 0) {
integer nx = negate(x);
integer res = add_positive(nx, y);
mutable_negate(res);
free_node(nx);
return res;
} else {
integer nx = negate(x), ny = negate(y);
integer res = subtract_positive(ny, nx);
free_node(nx);
free_node(ny);
return res;
}
}
}

integer read_integer() {
list_node *header = make_node(0);
int c, sign = 0;

while (!isdigit((c = getchar()))) {
if (c == '+') sign = POS;
if (c == '-') sign = NEG;
}

do {
insert_after(header, make_node(c - '0'));
++header->value;
} while (isdigit((c = getchar())));

trim_trailing_zeros(header, sign);
return header;
}

void print_integer(integer i) {
list_node *node = i->next;

if (i->value < 0) {
printf("-");
}

int length = abs(i->value);
char *string = (char *) malloc(length + 1) + length;

*string = '\0';
for ( ; node != 0; node = node->next)
*--string = node->value + '0';

printf("%s", string);
free(string);
}

int main() {

integer x, y, z, w;
x = read_integer();
y = read_integer();

z = add(x, y);
w = subtract(x, y);

print_integer(x);
printf(" + ");
print_integer(y);
printf(" = ");
print_integer(z);
printf("\n");

print_integer(x);
printf(" - ");
print_integer(y);
printf(" = ");
print_integer(w);
printf("\n");

free_node_list(x);
free_node_list(y);
free_node_list(z);
free_node_list(w);

return 0;
}