# 两个超大正整数相减问题之链表实现

#include
using namespace std;
struct Node
{
int data;
Node *next;
};
Node *input();
Node *Sub(Node *p, Node *q);
void output(Node *h);
Node *insert(Node *u, int num);
Node *Minus(Node *p, Node *q);
int main()
{
Node *s1, *s2, *s3;
s1 = input();
s2 = input();
output(s1);
cout << " - ";
output(s2);
cout << " = ";
s3 = Sub(s1, s2);
output(s3);
cout << endl;
return 0;
}
Node *input()
{
struct Num
{
char fig;
Num *next;
};
char no;
no = getchar();
while (no != '\n')
{
Num *t = new Num;
t->fig = no;
no = getchar();
}
Node *p = new Node;
p->data = -1;
Node *tail = p;
while (h != NULL)
{
int digit = 0;
int item = 0;
for (; digit < 4 && h; digit++)
{
item += (h->fig - '0') * pow(10.0, digit);
h = h->next;
}
Node *q = new Node;
q->data = item;
tail->next = q;
tail = q;
}
tail->next = p;
return p;
}
/*在结点u之后添加一个值为num的结点*/
Node *insert(Node *u, int num)
{
Node *v = new Node;
v->data = num;
u->next = v;
u = v;
return u;
}
Node *Sub(Node *p, Node *q)
{	/*比较被减数和减数的大小关系*/
Node *pp = p, *qq = q;
while (pp->data != -1 && qq->data != -1)
{
pp = pp->next;
qq = qq->next;
}
if (pp->data == -1)	//被减数小于减数
{
cout << '-';
return Minus(q, p);
}
else if (pp->data == -1 && qq->data == -1)	//被减数和减数组数相等
{
Node *ppp = p, *qqq = q;
while (ppp->next->next->data == -1)	//此时qqq->next->next->data == -1
{
ppp = ppp->next;
qqq = qqq->next;
}	//此时ppp和qqq是分别是被减数和减数的第一组数
if (ppp->data < qqq->data)
{
cout << '-';
return Minus(q, p);
}
}
return Minus(p, q);
}
Node *Minus(Node *p, Node *q)	//计算被减数减去减数的值，其中被减数不小于减数
{
Node *pp, *qq;
pp = p->next;
qq = q->next;
Node *s = new Node;
s->data = -1;
Node *t = s;
int carry = 0, number = 0, total = 0;
while (qq->data != -1)	//减数组不为空
{
number = pp->data - qq->data + carry;
if (number < 0)
{
carry = -1;
number += 10000;
}
else
carry = 0;
t = insert(t, number);
pp = pp->next;
qq = qq->next;
}
/*考虑被减数可能剩下的部分*/
while (pp->data != -1)	// 因为被减数大于减数，所以carry可能为-1
{
number = pp->data + carry;
if (number < 0)
{
carry = -1;
number += 10000;
}
else
carry = 0;
t = insert(t, number);
pp = pp->next;
}
t->next = s;
return s;
}
void output(Node *h)
{
if (h->next->data != -1)
{
output(h->next);
if (h->next->next->data == -1)
cout << h->next->data;
else
{
int number = h->next->data;
cout << number / 1000;
number = number % 1000;
cout << number / 100;
number = number % 100;
cout << number / 10;
number = number % 10;
cout << number;
}
}
}