数据结构_大整数处理

语言：C++

IDE：Xcode

实现方式：顺序数组

  每种程序设计语言都提供了一个整型类型用于处理整型数，如C++的int类型。但是当int类型占用4个字节时，所能表示的范围为-2³¹ ~ 2³¹-1。此范围之外的整数将无法处理。为了处理任意大的整数，需要一个新的工具。

  存储一个任意大的整数就是存储一个字符串。考虑到整数的运算都是从个位数开始，为此把大整数按照逆序存放。如1234被存储为”4321”。由于整数分为正整数和负整数，需要增加一个保存符号的数据成员。如下是大整数类LongLongInt的实现。程序只实现了+, -以及<<的重载。

由于本文字符串是由string类实现的，对于string类不熟的朋友可以参考：

C++中String类用法小结

---

#include <iostream>
#include <string>

using namespace std;

string add(const string , const string);
string sub(const string, const string);
bool Greater(const string, const string);

class LongLongInt
{
private:
    char sign;  //存储符号
    string num;
    
public:
    LongLongInt(string n = "");
    //由于LongLongInt类的成员变量没有指针，所以不需要拷贝构造和赋值运算符重载
    //LongLongInt(const LongLongInt& other);
    //LongLongInt& operator=(const LongLongInt& rhs);
    ~LongLongInt(){}
    
    friend LongLongInt operator+(const LongLongInt& lhs, const LongLongInt& rhs);
    friend LongLongInt operator-(const LongLongInt& lhs, const LongLongInt& rhs);
    friend ostream& operator<<(ostream& os, const LongLongInt& rhs);
};

LongLongInt::LongLongInt(string n)
{
    if(n[0] == '-')
        sign = '-';
    else
        sign = '+';
    
    long Len = n.length();
    //防止将符号存入字符串中
    for(long i = Len; i > 0 && n[i-1]!='-'&&n[i-1]!='+'; --i) 
        num.push_back(n[i-1]); //倒序存入
    
}

LongLongInt operator+(const LongLongInt& lhs, const LongLongInt& rhs)
{
    LongLongInt temp;
    
    if(lhs.sign == rhs.sign)
    {
        temp.sign = lhs.sign;
        temp.num = add(lhs.num, rhs.num);
    }
    else if ( Greater(lhs.num, rhs.num) )
    {
        temp.sign = lhs.sign;
        temp.num = sub(lhs.num, rhs.num);
    }
    else
    {
        temp.sign = rhs.sign;
        temp.num = sub(rhs.num, lhs.num);
    }
    
    return temp;
}

LongLongInt operator-(const LongLongInt& lhs, const LongLongInt& rhs)
{
    LongLongInt temp(rhs);
    
    if(temp.sign == '+')
        temp.sign = '-';
    else
        temp.sign = '+';
    
    
    return lhs + temp;
}

ostream& operator<<(ostream& os, const LongLongInt& rhs)
{
    long Len = rhs.num.length();
    if(rhs.sign == '-')
        os << rhs.sign;
    
    for(long i = Len; i > 0; --i)
    {
        os << rhs.num[i-1];
    }
    os << endl;
    return os;
}



string add(const string lhs, const string rhs)
{
    unsigned long len1 = lhs.size();
    unsigned long len2 = rhs.size();
    
    long minLen = (len1 > len2 ? len2 : len1);
    int carry = 0; //进位
    int result;
    
    string str; //存放运算结果
    int i;
    
    for(i = 0; i < minLen; ++i)
    {
        result = (lhs[i] - '0') + (rhs[i] - '0') + carry;
        str.push_back(result % 10 + '0');
        carry = result/10;
    }
    
    for(; i < len1; ++i)
    {
        result = (lhs[i] - '0') + carry;
        str.push_back(result % 10 + '0');
        carry = result/10;
    }
    
    for(; i < len2; ++i)
    {
        result = (rhs[i] - '0') + carry;
        str.push_back(result % 10 + '0');
        carry = result/10;
    }
    
    if(carry != 0)
        str.push_back(carry + '0');
    
    return str;
}

string sub(const string lhs, const string rhs)
{
    unsigned long len1 = lhs.size();
    unsigned long len2 = rhs.size();
    
    int minus = 0;   //借位
    
    string str;
    int result = 0;
    
    int i;
    for(i = 0; i < len2; ++i)
    {
        result = lhs[i] - rhs[i] - minus;
        minus = 0;
        if(result < 0)
        {
            result += 10;
            minus++;
        }
        else
            minus = 0;
        
        str.push_back(result + '0');
        result = 0;
    }
    
    for(; i < len1; ++i)
    {
        result = lhs[i] - '0' - minus;
        minus = 0;
        if(result < 0)
        {
            result += 10;
            minus++;
        }
        else
            minus = 0;
        
        str.push_back(result + '0');
        result = 0;
        
    }
    
    
    //删除可能出现的多余的0
    string::iterator itr_start = str.begin();
    string::iterator itr_end = str.end()-1;   
    //str.end()指向的是str中末尾元素的下一个地址
    while(*itr_end == '0' && itr_end != itr_start)
    {
        str.pop_back();
        --itr_end;
    }
    
    return str;
}

bool Greater(const string lhs, const string rhs)
{
    long len1 = lhs.length();
    long len2 = rhs.length();
    
    if(len1 > len2)
        return true;
    if(len1 < len2)
        return false;
    
    for(int i = 0; i < len1; ++i)
    {
        if(lhs[i] > rhs[i])
            return true;
        if(lhs[i] < rhs[i])
            return false;
    }
    
    return true;
}

赏

谢谢你请我吃糖果