长整数相加

// test18.cpp : Defines the entry point for the console application.
//

#include 
"stdafx.h"
#include
<iostream>
#include
<string>
#include
<list>
using namespace std;

class BigInt{
    friend istream
& operator>>(istream&, BigInt&);
    friend ostream
& operator<<(ostream&, BigInt&);
    friend BigInt
& operator+(BigInt&, BigInt&);
private:
    list
<int> intLst;
};

/**长整数加法
基本思路是利用反向迭代器(加法是从地位到高位)实现链表并归
BigInt& operator+(a,b)
    while(rIterA!=a.intLst.rend && rIterB!=a.intLst.rend)
        c->intLst.push_front((*rIterA+*rIterB+carry)%10); 注意是push_front,从头结点处入链表
        if(*rIterA+*rIterB+carry>=10) carry=1 计算是否有进位
        else carry=0
        rIterA++, rIterB++
    while(rIterA!=a.intLst.rend)
        c->intLst.push(*rIterA++ + carry)
        carry=0;
    while(rIterB!=b.intLst.rend)
        c->intLst.push(*rIterB++ +carry)
        carry=0
    return *c
*/
BigInt
& operator+(BigInt& a, BigInt& b){
    
int carry=0;//进位标志
    list<int>::reverse_iterator rIterA=a.intLst.rbegin();
    list
<int>::reverse_iterator rIterB=b.intLst.rbegin();

    BigInt
* c=new BigInt();
    
while(rIterA!=a.intLst.rend() && rIterB!=b.intLst.rend()){
        c
->intLst.push_front((*rIterA+*rIterB+carry)%10);
        
if((*rIterA+*rIterB+carry)>=10)
            carry
=1;
        
else
            carry
=0;
        rIterA
++, rIterB++;
    }
    
while(rIterA!=a.intLst.rend()){
        c
->intLst.push_front(*rIterA++ + carry);//如99+123最高位百位还要进位一次
        carry=0;
    }
    
while(rIterB!=b.intLst.rend()){
        c
->intLst.push_front(*rIterB++ +carry);
        carry
=0;
    }
    
return *c;
}

istream
& operator>>(istream& in, BigInt& bint){
    
string str;
    
in>>str;
    
for(string::iterator iter=str.begin(); iter!=str.end(); iter++){
        bint.intLst.push_back(
*iter-'0'); //*iter是stirng中每个char对应的ASCII码
    }
    
return in;
}

ostream
& operator<<(ostream& out, BigInt& bint){
    
for(list<int>::iterator iter=bint.intLst.begin();iter!=bint.intLst.end();iter++)
        
out<<*iter;
    
out<<endl;
    
return out;
}

int main(){
    BigInt
* a=new BigInt();
    BigInt
* b=new BigInt();
    cout
<<"cin>>A: ";
    cin
>>*a;
    cout
<<"cin>>B: ";
    cin
>>*b;
    BigInt c
=*a+*b;
    cout
<<c;
    system(
"pause");
}

输入输出如下;
cin>>A: 3434685897609608780
cin>>B: 1234234236535634764376
1237668922433244373156

posted on 2008-10-25 12:48 deep2 阅读(1789) 评论(4)  编辑 收藏 引用 所属分类: 链表

评论

# re: 长整数相加 2008-10-25 16:44 金山毒霸2008

在底层的系统运算还真是常用到这个。  回复  更多评论   

# re: 长整数相加 2008-10-26 16:06 春天

while(rIterA!=a.intLst.rend()){
c->intLst.push_front(*rIterA++ + carry);//如99+123最高位百位还要进位一次
carry=0;
}
while(rIterB!=b.intLst.rend()){
c->intLst.push_front(*rIterB++ +carry);
carry=0;
}
你考虑了最高位还会进一位,没有考虑再进n位;如果999999+5,试下。  回复  更多评论   

# re: 长整数相加 2008-10-31 11:09 合工大

不错,不小心路过。想问下,你是合工大的?  回复  更多评论   

# re: 长整数相加 2008-11-01 12:03 春天

不是的,我是安徽人。好多同学在合工大。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜