[数据结构与算法]数据结构，超出范围的极大整数相加

#include<iostream>
using namespace std;
typedef struct node
{
	int data;
	node* next;
}node;
class Operator
{
public:
	void Establish(node *&head,char a[], int n)//establishment of linked list(链表的建立)
	{
		//head insertion(用头插法)
		head = new node;
		head->next = NULL;
		
		for (int i = 0; i < n; ++i)
		{
			node* temp = new node;//temporary node is used to build linked list(临时结点用于链表的建立)
			temp->data = a[i] - '0';
			temp->next=head->next;
			head->next = temp;
		}
	}
	//because the insertion uses the head insertion method to insert ,resulting in the position of last bit ,so it is necessary to use the head insertion method to re insert it
	//因为用头插法插入，导致个位在最后一位的位置，所以要用头插法对其进行重新插入）

	void Overturn(node *&head)//used to filp linked list(用于链表的翻转)
	{
		//first ,define two pointers ,p,q.p to the first node ,q to the next node of p
		//首先定义两个结点p，q，p指向首结点，q指向p的下一个结点
		//make the data pointer to by the head empty and reinsert it;
		//令head指向的数据为空，对其进行重新插入
		node* p = head->next;
		node* q;
		head->next = NULL;
	
		while (p)
		{
			q = p->next;
			p->next=head->next;
			head->next = p;
			p = q;
		}
	}
	void Output(node*& head)
	{
		for (node* p = head->next; p; p = p->next)
			cout << p->data;
		cout << endl;
	}
	void Add(node*& L1, node*& L2, node*& L3)
	{
		L3 = new node;
		L3->next = NULL;
		node* p = L1->next;
		node* q = L2->next;
		int carry = 0;//when the number of added digits exceeds 10,one bit  forward is achieved(相加位数超过十时，实现向前移一位)
		while (p && q)
		{
			node* temp = new node;
			temp->data = (p->data + q->data + carry) % 10;
			carry = (p->data + q->data + carry) / 10;
			temp->next=L3->next;
			L3->next = temp;
			p = p->next;
			q = q->next;
		}
		//when jumping of the loop,only one linked list is empty ,copy the data of the non empty linked list
		//当跳出循环只有一条链表为空时，将不为空的链表复制下来
		if (p)q = p;//in this way ,we don't need to discuss which p or q is empty separately(这样就不用分开讨论p，q哪个为空)
		while (q)
		{
			node* temp = new node;
			temp->data = (q->data + carry) % 10;
			carry = (q->data + carry) / 10;
			temp->next = L3->next;
			L3->next = temp;
			q = q->next;
		}
		if (carry)
		{
			node* temp = new node;
			temp->data = carry;
			temp->next = L3->next;
			L3->next = temp;
		}
	}
};
int main()
{
	char a[10] = "987231556";
	char b[8] = "9854430";
	node* L1;
	node* L2;
	node* L3;
	Operator o;
	o.Establish(L1, a, 9);
	
	o.Establish(L2, b, 7);
	
	o.Add(L1, L2, L3);
	o.Overturn(L1);
	o.Overturn(L2);
	cout << "L1 ";

	o.Output(L1);
	cout<<endl << "L2 ";
	o.Output(L2);
	
	cout << endl << "相加得L3"<<endl;
	
	o.Output(L3);
}