BigIn——超大型整数的实现——链表法

大家好，欢迎来到IT知识分享网。

Big Int——超越longint大小的整形

1 / 头文件 bigint.h

#ifndef _bigint_h #define _bigint_h #include <string> class NUM { 
    public: int num; NUM* next; }; class BigInt { 
    friend BigInt operator+(const BigInt& n1, const BigInt& n2); friend BigInt operator*(const BigInt& n1, const BigInt& n2); friend BigInt add_two_positive_nums(const BigInt& n1, const BigInt& n2); friend BigInt add_two_differnt_nums(const BigInt& big, const BigInt& small); friend BigInt MUL(const BigInt& n1, const BigInt& n2); friend BigInt mulREC(NUM *p1, const NUM *p2, int counter); public: /* * Constructor: BigInt * Usage: BigInt big(str); * ----------------------- * Creates a new BigInt from a string of decimal digits, * which may begin with a minus sign to indicate a negative value. */ BigInt(); BigInt(std::string str); BigInt(const BigInt &primary); /* * Destructor: ~BigInt * ------------------- * Frees the memory used by a BigInt when it goes out of scope. */ ~BigInt(); /* * Method: toString * Usage: string str = bigint.toString(); * -------------------------------------- * Converts a BigInt object to the corresponding string. */ BigInt& operator=(const BigInt& primary); std::string toString() const; private: NUM* head; char sign; }; BigInt operator+(const BigInt& n1, const BigInt& n2); BigInt operator*(const BigInt& n1, const BigInt& n2); BigInt add_two_positive_nums(const BigInt& n1, const BigInt& n2); BigInt add_two_differnt_nums(const BigInt& big, const BigInt& small); int point_out_Who_is_bigger(const BigInt& n1, const BigInt& n2); BigInt MUL(const BigInt& n1, const BigInt& n2); BigInt mulREC(NUM *p1, const NUM *p2, int counter); #endif 

2 / 实现文件 bigint.cpp

#include <cctype> #include "bigint.h" #include "error.h" using namespace std; BigInt::BigInt() { 
    sign = '+'; head = NULL; } BigInt::BigInt(string str) { 
    NUM *rear, *p; head = new NUM; rear = head; //---------------can we do it?----------------// if(str.length() == 0) { 
    cout << "We can't get your string!!!" << endl; head = NULL; return; } //---------------sign-----------------------// if(str[0] == '-') { 
    sign = '-'; str = str.substr(1); } if(str[0] == '+') { 
    sign = '+'; str = str.substr(1); } //删除0； if(str[0] >= 48 && str[0] <= 57) { 
    sign = '+'; if(str[0] == 48) { 
    int i = 0; for(;;i++) { 
    if(str[i] != '0') break; } str.erase(0,i); } } //----------------------legal----------------// for(int i = 1; i < str.length(); i++) { 
    if(str[i] < 48 || str[i] > 57) { 
    cout << "We can't get the big integer!!!" << endl; sign = '+'; head = NULL; return; } } for(int i = str.length() - 1; i >= 0; i--) { 
    int k = str[i] - 48; p = new NUM; p->num = k; rear->next = p; rear = p; } rear->next = NULL; } BigInt::BigInt(const BigInt &primary) { 
    if(primary.head == NULL) { 
    cout << "NO!" << endl; sign = '+'; head = NULL; return; } sign = primary.sign; NUM *rear, *p, *p_ptr = primary.head->next; head = new NUM; rear = head; while(p_ptr != NULL) { 
    p = new NUM; p->num = p_ptr->num; rear->next = p; rear = p; p_ptr = p_ptr->next; } rear->next = NULL; } BigInt::~BigInt() { 
    NUM *tmp = head->next, *p = head; while(tmp != NULL) { 
    delete p; p = tmp; tmp = p->next; } delete p; } BigInt& BigInt::operator=(const BigInt& primary) { 
    if(primary.head == NULL) { 
    cout << "NO!" << endl; sign = '+'; head = NULL; return *this; } if(head != NULL) { 
    this->~BigInt(); } sign = primary.sign; NUM *rear, *p, *p_ptr = primary.head->next; head = new NUM; rear = head; while(p_ptr != NULL) { 
    p = new NUM; p->num = p_ptr->num; rear->next = p; rear = p; p_ptr = p_ptr->next; } rear->next = NULL; return *this; } string BigInt::toString() const { 
    if(head == NULL) { 
    cout << "NO!" <<endl; return ""; } string str = ""; NUM *tmp = head->next->next, *p = head->next; char num; while(tmp != NULL) { 
    num = p->num + 48; str = num + str; p = tmp; tmp = p->next; } num = p->num + 48; str = num + str; if(sign == '-') str = sign + str; return str; } BigInt add_two_positive_nums(const BigInt& n1, const BigInt& n2) { 
    BigInt added; int to_next_level = 0; NUM *p1 = n1.head->next, *p2 = n2.head->next, *ptr, *rear; added.head = new NUM; rear = added.head; while(true) { 
    ptr = new NUM; if(p1 != NULL && p2 != NULL) { 
    ptr->num = (p1->num + p2->num + to_next_level) % 10; to_next_level = (p1->num + p2->num + to_next_level) / 10; rear->next = ptr; rear = ptr; p1 = p1->next; p2 = p2->next; } else if(p1 == NULL && p2 != NULL) { 
    ptr->num = (p2->num + to_next_level) % 10; to_next_level = (p2->num + to_next_level) / 10; rear->next = ptr; rear = ptr; p2 = p2->next; } else if(p1 != NULL && p2 == NULL) { 
    ptr->num = (p1->num + to_next_level) % 10; to_next_level = (p1->num + to_next_level) / 10; rear->next = ptr; rear = ptr; p1 = p1->next; } else break; } if(to_next_level != 0) { 
    ptr = new NUM; ptr->num = to_next_level; rear->next = ptr; rear = ptr; } rear->next = NULL; return added; } BigInt add_two_differnt_nums(const BigInt& big, const BigInt& small) { 
    BigInt added; int to_next_level = 0; NUM *p1 = big.head->next, *p2 = small.head->next, *ptr, *rear; added.head = new NUM; rear = added.head; while(true) { 
    ptr = new NUM; if(p2 != NULL) { 
    if(p1->num - to_next_level >= p2->num) { 
    ptr->num = (p1->num - to_next_level) - p2->num; to_next_level = 0; } if(p1->num - to_next_level < p2->num) { 
    ptr->num = (p1->num - to_next_level + 10) - p2->num; to_next_level = 1; } rear->next = ptr; rear = ptr; p1 = p1->next; p2 = p2->next; } else if(p2 == NULL && p1 != NULL) { 
    ptr->num = p1->num - to_next_level; to_next_level = 0; rear->next = ptr; rear = ptr; p1 = p1->next; } else break; } rear->next = NULL; return added; } BigInt operator+(const BigInt& n1, const BigInt& n2) { 
    if(n1.sign == '+' && n2.sign == '+') { 
    BigInt added = add_two_positive_nums(n1, n2); added.sign = '+'; return added; } else if(n1.sign == '-' && n2.sign == '-') { 
    BigInt added = add_two_positive_nums(n1, n2); added.sign = '-'; return added; } else { 
    BigInt added; int which = point_out_Who_is_bigger(n1, n2); if(which == 0) { 
    BigInt _0("0"); return _0; } if(n1.sign == '-') { 
    if(which == 1) { 
    added = add_two_differnt_nums(n1, n2); added.sign = '-'; } else if(which == 2) { 
    added = add_two_differnt_nums(n2, n1); added.sign = '+'; } } if(n2.sign == '-') { 
    if(which == 2) { 
    added = add_two_differnt_nums(n2, n1); added.sign = '-'; } else if(which == 1) { 
    added = add_two_differnt_nums(n1, n2); added.sign = '+'; } } return added; } } int point_out_Who_is_bigger(const BigInt& n1, const BigInt& n2) { 
    string k1, k2; if(n1.toString()[0] == '-') k1 = n1.toString().substr(1); else k1 = n1.toString(); if(n2.toString()[0] == '-') k2 = n2.toString().substr(1); else k2 = n2.toString(); if(k1.length() == k2.length()) { 
    if(k1 > k2) return 1; else if(k1 < k2) return 2; else return 0; } else if(k1.length() > k2.length()) return 1; else return 2; } BigInt operator*(const BigInt& n1, const BigInt& n2) { 
    BigInt multiplied; if(n1.sign == n2.sign || n1.toString() == "0" || n2.toString() == "0") { 
    multiplied = MUL(n1, n2); multiplied.sign = '+'; } else { 
    multiplied = MUL(n1, n2); multiplied.sign = '-'; } return multiplied; } BigInt MUL(const BigInt& n1, const BigInt& n2) { 
    NUM *p1 = n1.head->next, *p2 = n2.head->next; int counter = 0; return mulREC(p1, p2, counter); } BigInt mulREC(NUM *p1, const NUM *p2, int counter) { 
    if(p2 == NULL) { 
    BigInt record("0"); return record; } BigInt record; int to_next_level = 0; NUM *head, *ptr, *rear, *p1_sub = p1; head = new NUM; rear = head; for(int i = counter; i > 0; i--) { 
    ptr = new NUM; ptr->num = 0; rear->next = ptr; rear = ptr; } while(p1_sub != NULL) { 
    ptr = new NUM; ptr->num = (p1_sub->num * p2->num + to_next_level) % 10; to_next_level = (p1_sub->num * p2->num + to_next_level) / 10; rear->next = ptr; rear = ptr; p1_sub = p1_sub->next; } if(to_next_level != 0) { 
    ptr = new NUM; ptr->num = to_next_level; rear->next = ptr; rear = ptr; } rear->next = NULL; record.head = head; return record + mulREC(p1, p2->next, counter + 1); } 

3 / main函数 测试

#include <iostream> #include "console.h" #include "bigint.h" #include "strlib.h" using namespace std; BigInt fact(int n) { 
    BigInt result("1"); return result; } int main() { 
    cout<<"Let's test BigInt!"<<endl; BigInt testBigInt("000000000000000000000000000000000000000000"); cout<< testBigInt.toString() <<endl; BigInt a("-"); BigInt b("-0"); BigInt c; c = b; cout << (a + c).toString() << endl; cout << (a * b).toString() << endl; return 0; } 

4 / 测试结果：