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

#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;
	Num *head = NULL;
	no = getchar();
	while (no != '\n')
	{
		Num *t = new Num;
		t->fig = no;
		t->next = head;
		head = t;
		no = getchar();
	}
	Node *p = new Node;
	p->data = -1;
	Node *tail = p;
	Num *h = head;
	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;
		}
	}
}

你可能感兴趣的