链表系列之单链表——使用单链表实现大整数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <stack>
using namespace std;

typedef struct node
{
	int data;
	node *next;
}Node, *LinkList;
//建立链表
Node* createList(const int a[], int n)
{
	Node *head, *endPtr;
	head = endPtr = NULL;
	
	for(int i=0;i<n;i++)
	{
		Node *temp = new Node;
		temp->data = a[i];
		temp->next = NULL;

		if(i==0)
		{
			head = endPtr = temp;
		}
		else
		{
			endPtr->next = temp;
			endPtr = temp;
		}
	}

	return head;
}
/*从尾到头打印链表，要求不修改链表结构*/
//使用栈适配器
void PrintListReversing(LinkList pHead)
{
	stack<Node*> nodes;
	Node* pNode = pHead;
	
	if(pNode==NULL)
		return;

	while(pNode!=NULL)   //将节点依次入栈
	{
		nodes.push(pNode);
		pNode = pNode->next;
	}

	while(!nodes.empty())   //出栈
	{
		pNode = nodes.top();   //读取栈顶元素
		cout<<pNode->data;
		nodes.pop();   //删除栈顶元素
	}
}
//大数相加
Node *ListAdd(Node* L1, Node* L2)
{
	if(L1==NULL)
		return L2;
	if(L2==NULL)
		return L1;

	Node *ptr1 = L1, *ptr2 = L2, *ResultPtr=NULL, *TmpPtr=NULL;
	int carry = 0;

	Node *p_node = new Node();
	p_node->data = (L1->data+L2->data)%10;
	p_node->next = NULL;
	carry = (L1->data+L2->data)/10;
	ResultPtr = TmpPtr = p_node;
	TmpPtr->next = NULL;
	L1 = L1->next;
	L2 = L2->next;

	while(L1 && L2)
	{
		Node *pNode = new Node();
		TmpPtr->next = pNode;

		int tmp = L1->data+L2->data+carry;
		carry = tmp/10;
		pNode->data = tmp%10;
		pNode->next = NULL;

		TmpPtr = TmpPtr->next;
		L1 = L1->next;
		L2 = L2->next;
	}

	while(L1)
	{
		Node *pNode = new Node();
		TmpPtr->next = pNode;

		int tmp = L1->data+carry;
		carry = tmp/10;
		pNode->data = tmp%10;
		pNode->next = NULL;

		TmpPtr = TmpPtr->next;
		L1 = L1->next;
	}
	while(L2)
	{
		Node *pNode = new Node();
		TmpPtr->next = pNode;

		int tmp = L2->data+carry;
		carry = tmp/10;
		pNode->data = tmp%10;
		pNode->next = NULL;

		TmpPtr = TmpPtr->next;
		L2 = L2->next;
	}

	if(carry)
	{
		Node *pNode = new Node();
		TmpPtr->next = pNode;

		pNode->data = carry;
		pNode->next = NULL;
	}

	return ResultPtr;
}

int main()
{
	int a[] = {1,9,9};  //991
	int b[] = {9,8,5,6,6,2,8};   //8266589
	Node *L1 = createList(a,3), *L2 = createList(b,7), *L3 = NULL;

	L3 = ListAdd(L1,L2);

	PrintListReversing(L1);
	cout<<"+";
	PrintListReversing(L2);
	cout<<"=";
	PrintListReversing(L3);
	cout<<endl;

	return 1;
}