用双向链表实现大数加减法

　　写了5个小时，C++面向对象的东西都不会写了。。。以后要多写C++少写python。。。关于读入字符串处理的那部分写得太挫就不放了。

#include "List.hpp"

List

  1 #pragma once
  2 #include <cstdio>
  3 #include <cassert>
  4 
  5 namespace kirai {
  6     template<class type> class List {
  7     private:
  8         typedef struct ListNode {
  9             type data;
 10             ListNode* pre;
 11             ListNode* next;
 12             ListNode() : data(data) { pre = NULL; next = NULL; }
 13             ListNode(const type& dd, ListNode*& pp, ListNode*& nn) :
 14                 data(dd), pre(pp), next(nn) {}
 15         }ListNode;
 16         ListNode* head;
 17     public:
 18         List() : head(new ListNode()) { head->pre = head->next = head; };
 19         int size() const;
 20         bool empty() const;
 21         void push_back(const type&);
 22         type last() const;
 23         void pop_back();
 24         void modifyLast(const type&);
 25         void insert(const type& ele, int idx);
 26         type get(int idx) const;
 27         type& operator [](int idx);
 28         type remove(int idx);
 29         void modify(const type& ele, int idx);
 30         int find(const type&) const;
 31         void clear();
 32         ~List() = default;
 33     };
 34 
 35     template<class type>
 36     int List<type>::size() const {
 37         int tot = 0;
 38         ListNode* p = head->next;
 39         while (p != head) {
 40             tot++;
 41             p = p->next;
 42         }
 43         return tot;
 44     }
 45 
 46     template<class type>
 47     bool List<type>::empty() const {
 48         return head == head->next ? 1 : 0;
 49     }
 50 
 51     template<class type>
 52     void List<type>::push_back(const type& element) {
 53         ListNode* p = new ListNode(element, head->pre, head);
 54         head->pre = head->pre->next = p;
 55     }
 56 
 57     template<class type>
 58     type List<type>::last() const {
 59         assert(!empty());
 60         return head->pre->data;
 61     }
 62 
 63     template<class type>
 64     void List<type>::pop_back() {
 65         assert(!empty());
 66         ListNode* p = head->pre->pre;
 67         delete head->pre;
 68         head->pre = p;
 69         p->next = head;
 70     }
 71 
 72     template<class type>
 73     void List<type>::modifyLast(const type& element) {
 74         assert(!empty());
 75         head->pre->data = element;
 76     }
 77 
 78     template<class type>
 79     void List<type>::insert(const type& element, int idx) {
 80         idx++;
 81         assert(idx > 0 && idx <= size() + 1);
 82         ListNode* p = head;
 83         while (idx--) p = p->next;
 84         ListNode* cur = new ListNode(element, p->pre, p);
 85         p->pre = p->pre->next = cur;
 86     }
 87 
 88     template<class type>
 89     type List<type>::get(int idx) const {
 90         idx++;
 91         assert(!empty() && idx > 0 && idx <= size());
 92         ListNode* p = head->next;
 93         while (--idx) p = p->next;
 94         return p->data;
 95     }
 96     template<class type>
 97     type& List<type>::operator [](int idx) {
 98         idx++;
 99         assert(!empty() && idx > 0 && idx <= size());
100         ListNode* p = head->next;
101         while (--idx) p = p->next;
102         return p->data;
103     }
104     template<class type>
105     type List<type>::remove(int idx) {
106         idx++;
107         assert(!empty() && idx > 0 && idx <= size());
108         ListNode* p = head->next;
109         while (--idx) p = p->next;
110         p->pre->next = p->next;
111         p->next->pre = p->pre;
112         type d = p->data;
113         delete p;
114         return d;
115     }
116 
117     template<class type>
118     void List<type>::modify(const type& ele, int idx) {
119         idx++;
120         assert(!empty() && idx > 0 && idx <= size());
121         ListNode* p = head->next;
122         while (--idx) p = p->next;
123         p->data = ele;
124     }
125 
126     template<class type>
127     int List<type>::find(const type& ele) const {
128         ListNode* p = head->next;
129         int idx = 0;
130         while (p != head) {
131             if (p->data == ele) return idx;
132             p = p->next;
133             idx++;
134         }
135         return -1;
136     }
137     template<class type>
138     void List<type>::clear() {
139         assert(!empty());
140     }
141 }

List.hpp

 1 #pragma once
 2 #include "lib/List"
 3 
 4 using kirai::List;
 5 
 6 #define positive 1
 7 #define negative 0
 8 
 9 class BigInteger {
10 public:
11     BigInteger() { _symbol = positive; }
12     BigInteger(const char*);
13     ~BigInteger() = default;
14     BigInteger add(const BigInteger&);
15     BigInteger sub(const BigInteger&);
16     bool symbol()const { return this->_symbol; }
17     void setSymbol(bool isPositive) { this->_symbol = isPositive; }
18     void setNum(List<short> s) { data = s; }
19     void show();
20     int cmp(const BigInteger&);
21     BigInteger addTwoPositive(const BigInteger&, const BigInteger&);
22     BigInteger bigSubSmall(const BigInteger&, const BigInteger&);
23     bool _symbol;
24     List<short> data;
25 };

BigInteger.h

  1 #include "BigInteger.h"
  2 #include <cassert>
  3 #include <iostream>
  4 #include <iomanip>
  5 
  6 #define positive 1
  7 #define negative 0
  8 
  9 int BigInteger::cmp(const BigInteger& A) {
 10     // 比较两个数的绝对值大小，如果this大返回1，A大返回-1，相等返回0
 11     int la = this->data.size();
 12     int lb = A.data.size();
 13     if (la > lb) return 1;
 14     if (la < lb) return -1;
 15     // 长度相等的时候，从高位比到低位
 16     for (int i = la - 1; i >= 0; i--) {
 17         if (this->data.get(i) > A.data.get(i)) return 1;
 18         if (this->data.get(i) < A.data.get(i)) return -1;
 19     }
 20     return 0;
 21 }
 22 
 23 BigInteger BigInteger::add(const BigInteger& B) {
 24     assert(!this->data.empty() && !B.data.empty());
 25     // 拷贝
 26     BigInteger ta = *this;
 27     BigInteger tb = B;
 28     BigInteger ans;
 29 
 30     // 全都是负数到时候，传入参数的时候做相加操作
 31     if (negative == this->symbol() && negative == B.symbol()) {
 32         ta.setSymbol(positive); tb.setSymbol(positive);
 33         ans = addTwoPositive(ta, tb);
 34         ans.setSymbol(negative);
 35     }
 36     // 全都是正数的时候，直接相加
 37     if (positive == this->symbol() && positive == B.symbol()) {
 38         ans = addTwoPositive(ta, tb);
 39         ans.setSymbol(positive);
 40     }
 41     // 一正一负的情况，比较一下绝对值大小
 42     else {
 43         int flag;
 44         // A正B负
 45         if (positive == this->symbol() && negative == B.symbol()) {
 46             flag = this->cmp(B);
 47             if (flag == 1) {    //相当于非负数减法
 48                 ta.setSymbol(positive); tb.setSymbol(positive);
 49                 ans = bigSubSmall(ta, tb);
 50                 ans.setSymbol(positive);
 51             }
 52             if (flag == 0) {    //直接返回0即可
 53                 ta.setSymbol(positive); tb.setSymbol(positive);
 54                 ans.data.push_back(0);
 55                 ans.setSymbol(positive);
 56             }
 57             if (flag == -1) {    //相当于负数的绝对值减正数，结果为负
 58                 ta.setSymbol(positive); tb.setSymbol(positive);
 59                 ans = bigSubSmall(tb, ta);
 60                 ans.setSymbol(negative);
 61             }
 62         }
 63         // A负B正
 64         if (negative == this->symbol() && positive == B.symbol()) {
 65             flag = this->cmp(B);
 66             if (flag == 1) {    //相当于负数的绝对值减正数，结果为负
 67                 ta.setSymbol(positive); tb.setSymbol(positive);
 68                 ans = bigSubSmall(ta, tb);
 69                 ans.setSymbol(negative);
 70             }
 71             if (flag == 0) {    //直接返回0即可
 72                 ta.setSymbol(positive); tb.setSymbol(positive);
 73                 ans.data.push_back(0);
 74                 ans.setSymbol(positive);
 75             }
 76             if (flag == -1) {    //相当于非负数减法
 77                 ta.setSymbol(positive); tb.setSymbol(positive);
 78                 ans = bigSubSmall(tb, ta);
 79                 ans.setSymbol(positive);
 80             }
 81         }
 82     }
 83     return ans;
 84 }
 85 
 86 BigInteger BigInteger::sub(const BigInteger& B) {
 87     assert(!this->data.empty() && !B.data.empty());
 88     // 拷贝
 89     BigInteger* A = const_cast<BigInteger*>(this);
 90     BigInteger ta = *this;
 91     BigInteger tb = B;
 92     BigInteger ans;
 93     
 94     // A正B负，做加法，结果为正
 95     if (positive == this->symbol() && negative == B.symbol()) {
 96         ta.setSymbol(positive); tb.setSymbol(positive);
 97         ans = addTwoPositive(ta, tb);
 98         ans.setSymbol(positive);
 99     }
100     // A负B正，做加法，结果为负
101     if (negative == this->symbol() && positive == B.symbol()) {
102         ta.setSymbol(positive); tb.setSymbol(positive);
103         ans = addTwoPositive(ta, tb);
104         ans.setSymbol(negative);
105     }
106     else {
107         int flag;
108         // 两个数都是正
109         if (positive == this->symbol() && positive == B.symbol()) {
110             flag = this->cmp(B);
111             if (flag == 1) {    //相当于大减小，结果为正
112                 ta.setSymbol(positive); tb.setSymbol(positive);
113                 ans = bigSubSmall(ta, tb);
114                 ans.setSymbol(positive);
115             }
116             if (flag == 0) {    //直接返回0即可
117                 ta.setSymbol(positive); tb.setSymbol(positive);
118                 ans.data.push_back(0);
119                 ans.setSymbol(positive);
120             }
121             if (flag == -1) {    //相当于小减大，反着减结果为负
122                 ta.setSymbol(positive); tb.setSymbol(positive);
123                 ans = bigSubSmall(tb, ta);
124                 ans.setSymbol(negative);
125             }
126         }
127         //两个数都是负
128         if (negative == this->symbol() && negative == B.symbol()) {
129             ta.setSymbol(positive); tb.setSymbol(positive);
130             flag = this->cmp(B);
131             if (flag == 1) {    //相当于大的减小的，结果为负
132                 ta.setSymbol(positive); tb.setSymbol(positive);
133                 ans = bigSubSmall(ta, tb);
134                 ans.setSymbol(negative);
135             }
136             if (flag == 0) {    //直接返回0即可
137                 ta.setSymbol(positive); tb.setSymbol(positive);
138                 ans.data.push_back(0);
139                 ans.setSymbol(positive);
140             }
141             if (flag == -1) {    //相当于小的减大的，结果为正
142                 ta.setSymbol(positive); tb.setSymbol(positive);
143                 ans = bigSubSmall(tb, ta);
144                 ans.setSymbol(positive);
145             }
146         }
147     }
148     return ans;
149 }
150 
151 // A + B 全正
152 BigInteger BigInteger::addTwoPositive(const BigInteger& A, const BigInteger& B) {
153     using namespace std;
154     BigInteger ans;
155     int la = A.data.size();
156     int lb = B.data.size();
157     int len = la < lb ? la : lb;
158     for (int i = 0; i < len; i++) {
159         ans.data.push_back(0);
160         ans.data[i] = A.data.get(i) + B.data.get(i);
161     }
162     for (int i = len; i < la; i++) {
163         ans.data.push_back(0);
164         ans.data[i] = A.data.get(i);
165     }
166     for (int i = len; i < lb; i++) {
167         ans.data.push_back(0);
168         ans.data[i] = A.data.get(i);
169     }
170     // 处理进位
171     len = la > lb ? la : lb;
172     bool up = 0;    // 进位标记
173     short cur;
174     for (int i = 0; i < len; i++) {
175         if (up == 1) {
176             ans.data[i] += cur;
177             up = 0;
178         }
179         if (ans.data.get(i) >= 10000) {
180             cur = ans.data[i] / 10000;
181             short tmp = ans.data[i] % 10000;
182             ans.data[i] = tmp;
183             up = 1;
184         }
185         else up = 0;
186     }
187     if (up) {    //最后一位还需要进位
188         while (cur) {
189             ans.data.push_back(cur);
190             cur /= 10000;
191         }
192     }
193     return ans;
194 
195 }
196 
197 // A - B (A > B) 全正
198 BigInteger BigInteger::bigSubSmall(const BigInteger& A, const BigInteger& B) {
199     BigInteger ans;
200     int la = A.data.size();
201     int lb = B.data.size();
202     int len = la < lb ? la : lb;
203     for (int i = 0; i < len; i++) {
204         ans.data.push_back(0);
205         ans.data[i] = A.data.get(i) - B.data.get(i);
206     }
207     for (int i = len; i < la; i++) {
208         ans.data.push_back(0);
209         ans.data[i] = A.data.get(i);
210     }
211     len = la > lb ? la : lb;
212     // 处理借位
213     bool down = 0;
214     for (int i = 0; i < len; i++) {
215         if (down == 1) {
216             ans.data[i] -= 1;
217             down = 0;
218         }
219         if (ans.data[i] < 0) {
220             ans.data[i] += 10000;
221             down = 1;
222         }
223         else down = 0;
224     }
225     return ans;
226 }
227 
228 void BigInteger::show() {
229     using namespace std;
230     int len = data.size();
231     if (this->symbol() == negative) {
232         cout << "-";
233     }
234     int flag = 0;
235     if (len == 1) {
236         cout << data[0] << endl;
237         return;
238     }
239     if (data[len - 1] != 0) {
240         flag = 1;
241         cout << data[len - 1] << ",";
242     }
243     if (len == 1) {
244         cout << endl;
245         return;
246     }
247     for (int i = len - 2; i > 0; i--) {
248         if (data[i] == 0 && !flag) continue;
249         if (data[i] > 0) flag = 1;
250         if (flag == 1) {
251             cout << data[i] << ",";
252             flag++;
253             continue;
254         }
255         if (flag == 2) cout << std::setw(4) << std::setfill('0') << data[i] << ",";
256     }
257     if (flag == 0) cout << data[0] << endl;
258     if (flag == 1 || flag == 2) cout << std::setw(4) << std::setfill('0') << data[0] << endl;
259 }

BigInteger.cpp