关于超大数相加的一个算法

麦田管理中心

/*这是两个超大数相加的算法，思路就是个位相加取余保存在一个结果栈中，然后个位相加的结果÷10结果赋值给carry，然后十位相加再加carry取余放到结果栈里，同理依次算下去，<u>如果需要全部源码请说一下，我马上贴出来（主要是想解决问题）*/

1. 
   
2. stack<int> addinglargenumber(stack<int> stack1,stack<int> stack2)
   
3. /*最高位放在栈的最下面,如果这两个形参被赋值为相同的实参，那么stack1和stack2共用一段内存，这个导致两个相同的数相加出错*/
   
4. {
   
5.         int carry = 0;
   
6.         stack<int> stacktmp = stack2;
   
7. /*stacktmp {head=0x00f6d448 {vacabulary=9 next=0x00f6d410 {vacabulary=8 next=0x00f6d3d8 {vacabulary=7 next=0x00f6d3a0 {...} ...} ...} ...} ...}*/
   
8. /*stack1 {head=0x00f6d448{vacabulary=9 next=0x00f6d410 {vacabulary=8 next=0x00f6d3d8 {vacabulary=7 next=0x00f6d3a0 {...} ...} ...} ...} ...}*/
   
9. //比较stack1和stacktmp的地址始终相同，导致pop（）函数运算出错
   
10.         stack<int> stack3;//存放大数的和
    
11.         int a = 0, b = 0;
    
12.         while (!stack1.isempty() && !stacktmp.isempty())
    
13.         {
    
14.                 a = stack1.topEI(); b = stacktmp.topEI();
    
15.                 stack3.push((stack1.pop() + stacktmp.pop()/*问题可能出现在这*/ + carry) % 10);
    
16.         /*掉用pop（）函数是因为共用内存所以出错*/               
    
17.                 carry = (a + b + carry) / 10;
    
18.         }
    
19.         if (stack1.isempty() && stacktmp.isempty())
    
20.         {
    
21.                 if (carry != 0)
    
22.                 {
    
23.                         stack3.push(carry);
    
24.                 }
    
25.         }
    
26.         else
    
27.         {
    
28.                 if (stack1.isempty())
    
29.                         while (!stacktmp.isempty())
    
30.                         {
    
31.                                 stack3.push((a = (stacktmp.pop() + carry)) % 10);
    
32.                                 carry = a / 10;
    
33.                         }
    
34.                 else
    
35.                 {
    
36.                         while (!stack1.isempty())
    
37.                         {
    
38.                                 stack3.push((a = (stack1.pop() + carry)) % 10);
    
39.                                 carry = a / 10;
    
40.                         }
    
41.                 }
    
42.         }
    
43.         return stack3;
    
44. }
    
45. template<class T>
    
46. T stack<T>::pop()
    
47. {
    
48. node<T> *tmp = head;
    
49. T a = head->vacabulary;//a的赋值有问题
    
50. head = head->next;//无法读取内存
    
51. delete tmp;
    
52. return a;
    
53. }
    
54. 
    
55. void main()
    
56. {
    
57. stack<int> s1, s2, s3;
    
58. for (int i = 0; i < 10; i++)
    
59.   s1.push(i);
    
60. s1.print();
    
61. s2 = s1;
    
62. s2.print();
    
63. s3 = addinglargenumber(s1, s1);
    
64. s3.print();
    
65. }

复制代码

麦田管理中心

问题我自己已经解决，有兴趣的同学可以运行一下

1. #include<iostream>
   
2. using namespace std;
   
3. template<class T>
   
4. class node
   
5. {
   
6. public:
   
7.         node(T a, node* b = 0, node* c = 0)
   
8.         {
   
9.                 vacabulary = a;
   
10.                 next = b;
    
11.                 pre = c;
    
12.         }
    
13.         T vacabulary;
    
14.         node *next, *pre;
    
15. };
    
16. template<class T>
    
17. class stack
    
18. {
    
19. public:
    
20.         node<T> *head, *tail;
    
21.         stack()
    
22.         {
    
23.                 head = 0; tail = 0;
    
24.         }
    
25.         void push(T a);//将字符放在栈的顶部
    
26.         void clear();//清空栈
    
27.         int isempty();//判断栈是否为空，空就返回0
    
28.         T pop();//弹出顶部的元素
    
29.         T topEI();//获取顶部的元素，但不删除
    
30.         void operator=(stack);//重载=运算符
    
31.         void upsidedown();//颠倒栈的顺序
    
32.         void print()
    
33.         {
    
34.                 for (node<T>* tmp = head; tmp != NULL; tmp = tmp->next)
    
35.                 {
    
36.                         if (tmp->vacabulary > 9)
    
37.                                 cout << char(tmp->vacabulary + 55);
    
38.                         else
    
39.                                 cout << tmp->vacabulary;
    
40.                 }
    
41.                 cout << endl;
    
42.         }
    
43. };
    
44. template<class T>
    
45. void stack<T>::push(T a)
    
46. {
    
47.         node<T> *tmp;
    
48.         if (head == NULL)
    
49.         {
    
50.                 head = new node<T>(a, 0, 0);
    
51.                 tail = head;
    
52.         }
    
53.         else
    
54.         {
    
55.                 if (head == tail)
    
56.                 {
    
57.                         tmp = new node<T>(a, head, 0);
    
58.                         head->pre = tmp;
    
59.                         head = tmp;
    
60.                 }
    
61.                 else
    
62.                 {
    
63.                         tmp = new node<T>(a, head, 0);
    
64.                         head->pre = tmp;
    
65.                         head = tmp;
    
66.                 }
    
67.         }
    
68. }
    
69. template<class T>
    
70. void stack<T>::clear()
    
71. {
    
72.         node<T> *tmp = head;
    
73.         if (head == NULL)
    
74.         {
    
75.                 cout << "清空完成" << endl;
    
76.         }
    
77.         else
    
78.         {
    
79.                 if (head == tail)
    
80.                 {
    
81.                         delete head;
    
82.                         cout << "清空完成" << endl;
    
83.                 }
    
84.                 else
    
85.                 {
    
86.                         for (; head != NULL; head = tmp)
    
87.                         {
    
88.                                 tmp = tmp->next;
    
89.                                 delete head;
    
90.                         }
    
91.                         cout << "清空完成" << endl;
    
92.                 }
    
93.         }
    
94. }
    
95. template<class T>
    
96. int stack<T>::isempty()
    
97. {
    
98.         if (head == NULL)
    
99.                 return 1;
    
100.         return 0;
     
101. }
     
102. template<class T>
     
103. T stack<T>::pop()
     
104. {
     
105.         node<T> *tmp = head;
     
106.         T a = head->vacabulary;
     
107.         head = head->next;
     
108.         delete tmp;
     
109.         return a;
     
110. }
     
111. template<class T>
     
112. T stack<T>::topEI()
     
113. {
     
114.         return head->vacabulary;
     
115. }
     
116. 
     
117. template<class T>
     
118. void stack<T>::operator=(stack<T> a)
     
119. {
     
120.         node<T> *n;
     
121.         n = a.tail;
     
122.         this->clear();
     
123.         while (n != NULL)
     
124.         {
     
125.                 this->push(n->vacabulary);
     
126.                 n = n->pre;
     
127.         }
     
128. }
     
129. template<class T>
     
130. void stack<T>::upsidedown()
     
131. {
     
132.         stack<T> stack1;
     
133.         stack1.operator=(*this);
     
134.         this->clear();
     
135.         while (!stack1.isempty())
     
136.         {
     
137.                 this->push(stack1.pop());
     
138.         }
     
139.         stack1.clear();
     
140. }
     
141. /*这是两个超大数相加的算法，思路就是个位相加取余保存在一个结果栈中，然后个位相加的结果÷10结果赋值给carry，然后十位相加再加carry取余放到结果栈里，同理依次算下去*/
     
142. stack<int> addinglargenumber(stack<int> stack1,stack<int> stack2)
     
143. {
     
144.         int carry = 0;
     
145.         stack<int> stacktmp1;
     
146.         stack<int> stacktmp2;
     
147.         stacktmp1.operator=(stack1);
     
148.         stacktmp2.operator=(stack2);//这样的赋值就成功了，如果直接写=好而不调用重载运算符，那就是stacktmp和stack2公用一段内存
     
149.         stack<int> stack3;//存放大数的和
     
150.         int a = 0, b = 0;
     
151.         while (!stacktmp1.isempty() && !stacktmp2.isempty())
     
152.         {
     
153.                 a = stacktmp1.topEI(); b = stacktmp2.topEI();
     
154.                 stack3.push((stacktmp1.pop() + stacktmp2.pop() + carry) % 10);
     
155.                 carry = (a + b + carry) / 10;
     
156.         }
     
157.         if (stacktmp1.isempty() && stacktmp2.isempty())
     
158.         {
     
159.                 if (carry != 0)
     
160.                 {
     
161.                         stack3.push(carry);
     
162.                 }
     
163.         }
     
164.         else
     
165.         {
     
166.                 if (stacktmp1.isempty())
     
167.                         while (!stacktmp2.isempty())
     
168.                         {
     
169.                                 stack3.push((a = (stacktmp2.pop() + carry)) % 10);
     
170.                                 carry = a / 10;
     
171.                         }
     
172.                 else
     
173.                 {
     
174.                         while (!stacktmp1.isempty())
     
175.                         {
     
176.                                 stack3.push((a = (stacktmp1.pop() + carry)) % 10);
     
177.                                 carry = a / 10;
     
178.                         }
     
179.                 }
     
180.         }
     
181.         return stack3;//个位放在结果栈的最下面
     
182. }
     
183. 
     
184. void multiplelargenumber()//两个超大数相乘
     
185. {
     
186.         int i = 0;
     
187.         int carry = 0;
     
188.         stack<int> stack1;//两个因子
     
189.         stack<int> stack2;
     
190.         stack<int> stack3;//存放结果
     
191.         stack<int> stack4;//临时存放stack1
     
192.         char tmp[1000];//临时储存用的
     
193.         cout << "输入第1个数字(e代表结束)" << endl;
     
194.         for (i = 0; 1; i++)
     
195.         {
     
196.                 cin >> tmp[i];
     
197.                 if (tmp[i] == 'e')
     
198.                         break;
     
199.         }
     
200.         i = 0;
     
201.         while (tmp[i] != 'e')
     
202.         {
     
203.                 stack1.push((int)tmp[i++] - 48);//最高位放在栈的最下面
     
204.         }
     
205. 
     
206.         cout << "输入第2个数字(e代表结束)" << endl;
     
207.         for (i = 0; 1; i++)
     
208.         {
     
209.                 cin >> tmp[i];
     
210.                 if (tmp[i] == 'e')
     
211.                         break;
     
212.         }
     
213.         i = 0;
     
214.         while (tmp[i] != 'e')
     
215.         {
     
216.                 stack2.push((int)tmp[i++] - 48);//－48很重要，‘1’和1不一样。。//最高位放在栈的最下面
     
217.         }
     
218.         /**********以上为创建两个因子的栈************/
     
219.         stack4 = stack1;
     
220.         cout << "栈的个数" << i << endl;
     
221.         int stacknum = i;
     
222.         stack<int> *tmpp = new stack<int>[i];//创建的一系列栈用来求和,一共有i个栈
     
223.         int a, b;
     
224.         int j = 0;
     
225.         i = 0;
     
226.         for (; !stack2.isempty();)//用于计算求和栈，个位放在最下面
     
227.         {
     
228.                 for (; !stack1.isempty();)
     
229.                 {
     
230.                         tmpp[i].push(((a = stack2.topEI())*(b = stack1.pop()) + carry) % 10);
     
231.                         carry = (((a*b) + carry) / 10);
     
232.                 }
     
233.                 stack2.pop();
     
234.                 stack1 = stack4;
     
235.                 i++;
     
236.                 if (i != stacknum)
     
237.                 {
     
238.                         for (j = 0; j < i; j++)
     
239.                                 tmpp[i].push(0);
     
240.                 }
     
241.         }
     
242.         for (j = 0; j < stacknum; j++)//所有的求和栈颠倒顺序，用于最后一步求得积
     
243.         {
     
244.                 tmpp[j].upsidedown();
     
245.                 tmpp[j].print();
     
246.         }
     
247.         stack3.operator=(tmpp[0]);
     
248.         stack<int> stacktmp;
     
249.         for (j = 1; j < stacknum; j++)
     
250.         {
     
251.                 stacktmp.operator=(addinglargenumber(stack3, tmpp[j]));
     
252.                 stack3.clear();
     
253.                 stack3.operator=(stacktmp);
     
254.                 stacktmp.clear();
     
255.                 stack3.upsidedown();
     
256.         }
     
257.         stack3.upsidedown();
     
258.         stack3.print();
     
259. }
     
260. void main()
     
261. {
     
262.         multiplelargenumber();
     
263. }

复制代码