课堂作业是要进行大整数的运算,写完没事发上来。。题目要求:用c++进行两个超大整数的算数运算,比如1111111111111111111111111111 + 11111111111111111111111111,用类来做。定义一个Integer的类用于取代平常所用的int类型,有如下几个要求:1) 为Integer定义两个构造函数,一个是只有一个int类型的参数的函数,一个是只有string类型的参数的函数2) 重载算术操作符: +, -, , /, %, +=, -=, =, /=, %=, ++, --3) 重载关系操作符: ==, !=, >, <, >=, <=4) 重载输出操作符: <<5) 重载负号需要注意的是,你编写的类需要支持混合类型表达式,当然,这里只需要支持整型(int)类型的混合模式操作。比如,假设i是Integer类型,需要支持以下两种操作:i + 2;2 + i;但是,复合赋值操作符的左操作数必须是Integer类型。以下为一些注意事项:1) 两个操作数的位数均不超过100,输入的数据全部正确,不需要处理非法输入。输入数据不采用科学计数法(也就是输入进来的就是一串数字,若为负整数,前面有'-',否则不加任何前缀)2) 要处理正负情况,但是除法跟取余操作保证两个操作数都为非负数。3) 假设 q = x / y, r = x % y,规定 x = q * y + r,任何数除以0的结果都为0。4) 重载的输出操作符完成的功能只是输出该数字(若为负数,则需要输出负号),不需要输出换行符。下面是代码:
1 //=============================================================
2 //* code: Big Integer
3 //=============================================================
4 #include<iostream>
5 #include<string>
6 #include<deque>
7 using namespace std;
8
9 class Integer{
10 public:
11 //========构造函数====================================
12 Integer(int = 0);
13 Integer(const string&);
14 Integer(const Integer&);
15
16 //========赋值操作符重载===============================
17 Integer& operator =(const Integer&);
18
19 //========算术操作符重载===============================
20 friend Integer operator+(const Integer&, const Integer&);
21 friend Integer operator-(const Integer&, const Integer&);
22 friend Integer operator*(const Integer&, const Integer&);
23 friend Integer operator/(const Integer&, const Integer&);
24 friend Integer operator&(const Integer&, const Integer&);
25
26 //========比较操作符重载===============================
27 friend const bool operator ==(const Integer&, const Integer&);
28 friend const bool operator !=(const Integer&, const Integer&);
29 friend const bool operator > (const Integer&, const Integer&);
30 friend const bool operator >=(const Integer&, const Integer&);
31 friend const bool operator < (const Integer&, const Integer&);
32 friend const bool operator <=(const Integer&, const Integer&);
33
34 //========符合赋值操作符重载===========================
35 Integer& operator +=(const Integer&);
36 Integer& operator -=(const Integer&);
37 Integer& operator *=(const Integer&);
38 Integer& operator /=(const Integer&);
39 Integer& operator %=(const Integer&);
40
41 //=========自增自减操作符重载==========================
42 Integer& operator ++();
43 Integer operator ++(int);//后置
44 Integer& operator --();
45 Integer operator --(int);//后置
46
47 //=========负号操作符重载==============================
48 Integer operator -()const;
49
50 //=========输出操作符重载==============================
51 friend ostream& operator <<(ostream&,const Integer&);
52
53 private:
54 int sign;//判断是正号还是负号
55 deque<int> data;
56
57 //==========减法=======================================
58 void subtract(const deque<int>& temp1, const deque<int>& temp2);
59
60 //==========加法=======================================
61 void add(const deque<int>& temp1, const deque<int>& temp2);
62
63 int cmpData(const deque<int>& temp1, const deque<int>& temp2) const;//比较数据绝对值的大小
64
65 deque<int> divide(const deque<int>& temp);
66 };
67
68
69 Integer::Integer(int i){
70 if (i == 0){
71 sign = 0;
72 return ;
73 }
74 if (i < 0){
75 sign = -1;
76 i = -i;
77 }
78 else
79 sign = 1;
80 while (i != 0){
81 data.push_back(i % 10);
82 i /= 10;
83 }
84 }
85
86 Integer::Integer(const string& str){
87 if (str[0] == '-')
88 sign = -1;
89 else
90 sign = 1;
91 for (int i = (str.size()) - 1;i > 0; i--){
92 data.push_back(str[i] - '0');
93 }
94 if(sign == 1)
95 data.push_back(str[0] - '0');
96 while (!data.empty()){
97 if (data.back() != 0){
98 break;
99 }
100 data.pop_back();
101 }
102 if (data.empty()){
103 sign = 0;
104 }
105 }
106
107 Integer::Integer(const Integer& temp){
108 data.clear();
109 sign = temp.sign;
110 data = temp.data;
111 }
112
113 Integer& Integer::operator =(const Integer& temp){
114 data.clear();
115 sign = temp.sign;
116 data = temp.data;
117 return *this;
118 }
119
120 const bool operator ==(const Integer& temp1, const Integer& temp2){
121 return ((temp1.data == temp2.data) && (temp1.sign == temp2.sign));
122 }
123
124 const bool operator !=(const Integer& temp1, const Integer& temp2){
125 return !(temp1 == temp2);
126 }
127
128 const bool operator > (const Integer& temp1, const Integer& temp2){
129 if(temp1.sign < temp2.sign)
130 return false;
131 if(temp1.sign > temp2.sign)
132 return true;
133 if(temp1.sign == -1){
134 if(temp1.data.size() < temp2.data.size())
135 return true;
136 if(temp1.data.size() > temp2.data.size())
137 return false;
138 for(int i = temp1.data.size() - 1;i >= 0;i--){
139 if(temp1.data[i] > temp2.data[i])
140 return false;
141 if(temp1.data[i] < temp2.data[i])
142 return true;
143 }
144 return false;
145 }
146 else if(temp1.sign == 1){
147 if(temp1.data.size() > temp2.data.size())
148 return true;
149 if(temp1.data.size() < temp2.data.size())
150 return false;
151 for(int i = temp1.data.size() - 1;i >= 0;i--){
152 if(temp1.data[i] < temp2.data[i])
153 return false;
154 if(temp1.data[i] > temp2.data[i])
155 return true;
156 }
157 return false;
158 }
159 return false;
160 }
161 const bool operator >=(const Integer& temp1, const Integer& temp2){
162 if(temp1 > temp2)
163 return true;
164 if(temp1 == temp2)
165 return true;
166 return false;
167 }
168 const bool operator < (const Integer& temp1, const Integer& temp2){
169 return !(temp1 >= temp2);
170 }
171 const bool operator <=(const Integer& temp1, const Integer& temp2){
172 return !(temp1 > temp2);
173 }
174
175
176 // 算术运算符 {
177 Integer operator +(const Integer& temp1, const Integer& temp2){
178 Integer temp(temp1);
179 temp += temp2;
180 return temp;
181 }
182
183 Integer operator -(const Integer& temp1, const Integer& temp2){
184 Integer temp(temp1);
185 temp -= temp2;
186 return temp;
187 }
188
189 Integer operator *(const Integer& temp1, const Integer& temp2){
190 Integer temp(temp1);
191 temp *= temp2;
192 return temp;
193 }
194 Integer operator /(const Integer& temp1, const Integer& temp2){
195 Integer temp(temp1);
196 temp /= temp2;
197 return temp;
198 }
199
200 Integer operator %(const Integer& temp1, const Integer& temp2){
201 Integer temp(temp1);
202 temp %= temp2;
203 return temp;
204 }
205
206 Integer Integer::operator -() const{
207 Integer temp = *this;
208 switch(temp.sign){
209 case -1:
210 temp.sign = 1;
211 break;
212 case 1:
213 temp.sign = -1;
214 break;
215 default:
216 break;
217 }
218 return temp;
219 }
220 Integer& Integer::operator +=(const Integer& temp){
221 if (temp.sign == 0)
222 return (*this);
223
224 if (sign == 0){
225 (*this) = temp;
226 return (*this);
227 }
228
229 if (sign == temp.sign){
230 add(deque<int>(data), temp.data);
231 return (*this);
232 }
233 if(sign != temp.sign){
234 if(cmpData((*this).data, temp.data) == -1){
235 subtract(temp.data, deque<int>(data));
236 sign = temp.sign;
237 return (*this);
238 }
239 else if(cmpData((*this).data, temp.data) == 1){
240 subtract( deque<int>(data),temp.data);
241 return (*this);
242 }
243 else{
244 sign = 0;
245 (*this).data.clear();
246 return (*this);
247 }
248 }
249 }
250
251 Integer& Integer::operator -=(const Integer& temp){
252 (*this) += (-temp);
253 return (*this);
254 }
255
256 Integer& Integer::operator *=(const Integer& temp_){
257 if(sign == 0 || temp_.sign == 0){
258 sign = 0;
259 data.clear();
260 return (*this);
261 }
262 Integer temp(1), temp1(1);
263 temp.data.clear();
264 int tmp, count = 0, sing1 = sign;
265 deque<int>::const_iterator iter1 = this->data.begin();
266 deque<int>::const_iterator iter2 = temp_.data.begin();
267 for(;iter1 != this->data.end();++iter1){
268 count++;
269 temp1.data.clear();
270 tmp = 0;
271 for(iter2 = temp_.data.begin();iter2 != temp_.data.end();++iter2){
272 temp1.data.push_back((*iter1) * (*iter2) + tmp);
273 tmp = data.back() / 10;
274 data.back() %= 10;
275 }
276 if(tmp != 0)
277 temp1.data.push_back(tmp);
278 for(int i = 1;i < count;i++){
279 temp1.data.push_front(0);
280 }
281 temp1.sign = 1;
282 temp += temp1;
283 }
284 (*this) = temp;
285 sign = sing1 * temp_.sign;
286 return (*this);
287 }
288
289
290 Integer& Integer::operator /=(const Integer& temp){
291 if (sign == 0 || temp.sign == 0){
292 sign = 0;
293 data.clear();
294 return *this;
295 }
296 if (cmpData(data, temp.data) == -1){
297 sign = 0;
298 data.clear();
299 return *this;
300 }
301
302 (*this).data = divide(temp.data);
303
304 while (!data.empty()){
305 if (data.back() != 0){
306 break;
307 }
308 data.pop_back();
309 }
310
311 if (data.empty()){
312 sign = 0;
313 }
314 return *this;
315 }
316
317 Integer& Integer::operator %=(const Integer& temp){
318 if(sign == 0 || temp.sign == 0){
319 return (*this);
320 }
321 if (cmpData(data, temp.data) == -1){
322 return (*this);
323 }
324 Integer temp1(1);
325 temp1.data.clear();
326 temp1 = (*this) / temp;
327 temp1 *= temp;
328 (*this) -= temp1;
329 return (*this);
330 }
331
332 Integer& Integer::operator ++( ){
333 *this += 1;
334 return *this;
335 }
336
337 Integer Integer::operator ++(int){
338 Integer tmp(*this);
339 ++(*this);
340 return tmp;
341 }
342
343 Integer& Integer::operator --( ){
344 *this -= 1;
345 return *this;
346 }
347
348 Integer Integer::operator --(int){
349 Integer tmp(*this);
350 --(*this);
351 return tmp;
352 }
353
354 ostream& operator <<(ostream& output,const Integer& temp){
355 if(temp.sign == 0){
356 output << 0;
357 return output;
358 }
359 if(temp.sign == -1)
360 output << "-";
361 deque<int>::const_reverse_iterator iter = temp.data.rbegin();
362 for(;iter != temp.data.rend();iter++)
363 output << *iter;
364 return output;
365 }
366
367 void Integer::add(const deque<int>& integer1, const deque<int>& integer2){
368 data.clear();
369 deque<int>::const_iterator iter1 = integer1.begin();
370 deque<int>::const_iterator iter2 = integer2.begin();
371
372 int tmp = 0;
373 for(; iter1 != integer1.end() && iter2 != integer2.end();iter1++,iter2++){
374 data.push_back(*iter1 + *iter2 + tmp);
375 tmp = data.back() / 10;
376 data.back() %= 10;
377 }
378 deque<int>::const_iterator iter = (iter1 == integer1.end() ? iter2 : iter1);
379 deque<int>::const_iterator iter_end = (iter1 == integer1.end() ? integer2.end() : integer1.end());
380
381 for(;iter != iter_end;iter++){
382 data.push_back(*iter + tmp);
383 tmp = data.back() / 10;
384 data.back() %= 10;
385 }
386 if(tmp != 0)
387 data.push_back(tmp);
388 }
389
390 void Integer::subtract(const deque<int>& integer1, const deque<int>& integer2){
391 data.clear();
392 deque<int>::const_iterator iter1 = integer1.begin();
393 deque<int>::const_iterator iter2 = integer2.begin();
394
395 int tmp = 0;
396 for(;iter2 != integer2.end();iter1++,iter2++){
397 if(((*iter1) - tmp) >= (*iter2)){
398 data.push_back((*iter1) - (*iter2) - tmp);
399 tmp = 0;
400 }
401 else{
402 data.push_back((*iter1) + 10 - (*iter2) - tmp);
403 tmp = 1;
404 }
405 }
406 deque<int>::const_iterator iter = (iter1 == integer1.end() ? iter2 : iter1);
407 deque<int>::const_iterator iter_end = (iter1 == integer1.end() ? integer2.end() : integer1.end());
408
409 for(;iter <= iter_end - 1;iter++){
410 if((*iter) - tmp >= 0){
411 data.push_back((*iter) - tmp);
412 tmp = 0;
413 }
414 else{
415 data.push_back((*iter) + 10 - tmp);
416 tmp = 1;
417 }
418 }
419
420 deque<int>::const_reverse_iterator iter3 = data.rbegin();
421 for(;iter3 != data.rend();){
422 if((*iter3) == 0){
423 data.pop_back();
424 iter3 = data.rbegin();
425 }
426 else{
427 break;
428 }
429 }
430 if(data.empty())
431 sign = 0;
432 }
433
434 //比较绝对值的大小
435 int Integer::cmpData(const deque<int>& temp1, const deque<int>& temp2) const{
436 if (temp1.size() < temp2.size())
437 return -1;
438 if (temp1.size() > temp2.size())
439 return 1;
440
441 deque<int>::const_iterator iter1 = temp1.end() - 1;
442 deque<int>::const_iterator iter2 = temp2.end() - 1;
443 for(int i = 0;i != temp1.size(),i != temp2.size();i++){
444 if((*(iter1 - i)) > (*(iter2 - i)))
445 return 1;
446 if((*(iter1 - i)) < (*(iter2 - i)))
447 return -1;
448 }
449 return 0;
450 }
451
452 deque<int> Integer::divide(const deque<int>& divisor)
453 {
454 deque<int> quotients;
455
456 if (cmpData(data, divisor) == -1)
457 {
458 return quotients;
459 }
460
461 Integer tmp;
462 tmp.sign = 1;
463 while (cmpData(tmp.data, divisor) == -1)
464 {
465 tmp.data.push_front(data.back());
466 data.pop_back();
467 }
468
469 quotients.push_front(0);
470 while (cmpData(tmp.data, divisor) != -1)
471 {
472 tmp.subtract(deque<int>(tmp.data), divisor);
473 quotients.front()++;
474 }
475
476 while (!data.empty())
477 {
478 tmp.data.push_front(data.back());
479 data.pop_back();
480 quotients.push_front(0);
481 while (cmpData(tmp.data, divisor) != -1)
482 {
483 tmp.subtract(deque<int>(tmp.data), divisor);
484 quotients.front()++;
485 }
486 }
487 data = tmp.data;
488 return quotients;
489 }
View Code
至于思想,都是列竖式的思想啦,看看代码列列竖式就看得出来了。。
原文链接: https://www.cnblogs.com/xiezhw3/archive/2013/05/17/3083629.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/88858
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!