大整数乘法

作者：童燕群 | 发布日期：一月 3, 2013 | 阅读次数（4,938） | 评论 |

新浪微博 QQ空间

很长时间都没写过代码了，试着写了这个常见的题目。整体思路：采用整形链表记录大整数的每一位，然后分别遍历乘数和被乘数的每一位，将每两个数字的乘积累加到结果的相应位上面。针对大整数类型，重载输入和输出流，重载乘法。

输出部分实现不是特别好。用STL的容器实现链表也许会简单的多。重载乘法的实现不合常理，本应该返回一个新的对象，为了简单起见，直接返回了新对象的指针；在计算乘法结果时使用了一个递归，理论上来说有可能深度过大，导致栈溢出；另外对于指针和应用的使用不规范。

具体代码：

/*
    main.cpp
*/
#include "utils.h"
#include <iostream>
#include <string>

using std::cin;
using std::cout;
using std::endl;
using std::string;

int main(int argc, char** argv)
{
    try
    {
        BigInt* pright = new BigInt;
        pright->data = 9;
        pright->next = new BigInt;
        pright->next->data = 9;
        pright->next->next = new BigInt;
        pright->next->next->data = 9;
        cout << "right is: " << *pright << endl;

        BigInt* pleft = new BigInt;
        pleft->data = 9;
        pleft->next = new BigInt;
        pleft->next->data = 9;
        pleft->next->next = new BigInt;
        pleft->next->next->data = 9;
        cout << "left is: " << *pleft << endl;

        BigInt* res = (*pleft) * (*pright);
        cout << "the result is: " << *res << endl;

        BigInt abc;
        cout << "pleas input the left num: ";
        cin >> abc;

        BigInt def;
        cout << "pleas input the right num: ";
        cin >> def;

        res = abc * def;
        cout << "the result is: " << *res << endl;
    }
    catch (string e)
    {
        cout << e;
        return -1;
    }

    return 0;
}


/*
    utils.h
*/
#ifndef __UTILS_MY__
#define __UTILS_MY__

#include <iostream>

#include "bigint.h"

using std::istream;
using std::ostream;

BigInt* operator* (BigInt& plhs, BigInt& prhs);

istream& operator>> (istream& in, BigInt& n);

ostream& operator<< (ostream& out, BigInt& n);

#endif




/*
    utils.cpp
*/
#include <string>
#include "utils.h"

using std::string;
using std::cout;

/*
*    d 的取值范围 [0, 9]
*/
BigInt* Addonenum (BigInt* pnum, unsigned char d)
{
    if (d > 9 || d == 0)
    {
        return pnum;
    }

    if (!pnum)
    {
        pnum = new BigInt;
        pnum->data = d;
        return pnum;
    }

    d += pnum->data;
    if (d > 9)
    {
        pnum->next = Addonenum(pnum->next, d / 10);
    }
    pnum->data = d % 10;

    return pnum;
}

BigInt* operator* (BigInt& plhs, BigInt& prhs)
{
    BigInt* preshead = new BigInt;
    if (plhs.iszero() || prhs.iszero())
    {
        return preshead;
    }

    if ((plhs.isneg() && !prhs.isneg()) || (!plhs.isneg() && prhs.isneg()))
    {
        preshead->bneg = true;
    }

    BigInt* presnumpos1 = preshead;
    BigInt* presnumpos2 = preshead;
    BigInt* plhsnum = &plhs;

    unsigned char d = 0;
    while (plhsnum)
    {
        presnumpos1 = presnumpos2;
        BigInt* prhsnum = &prhs;
        while (prhsnum)
        {
            d = prhsnum->data * plhsnum->data;
            presnumpos1 = Addonenum(presnumpos1, d % 10);
            presnumpos1->next = Addonenum(presnumpos1->next, d / 10);
            presnumpos1 = presnumpos1->next;
            prhsnum = prhsnum->next;
        }
        plhsnum = plhsnum->next;
        presnumpos2 = presnumpos2->next;
    }

    return preshead;
}

istream& operator>> (istream& in, BigInt& n)
{
    BigInt* pn = &n;
    BigInt* prenode = pn;
    string src;
    in >> src;

    string::reverse_iterator itrbegin = src.rbegin();
    string::reverse_iterator itrend = src.rend();

    if (src.at(0) == '-')
    {
        n.bneg = true;
        itrend--;
    }
    else if (src.at(0) == '+')
    {
        itrend--;
    }

    for (string::reverse_iterator it = itrbegin; it != itrend; it++)
    {
        if (*it > '9' || *it < '0')
        {
            throw "input num error: " + src + "!";
        }

        if (!pn)
        {
            // new node;
            pn = prenode->next = new BigInt;
            prenode = pn;
        }
        pn->data = *it - '0';
        pn = pn->next;
    }

    return in;
}

ostream& operator<< (ostream& out, BigInt& n)
{
    BigInt* pn = &n;

    string outstr;
    BigInt* prev = NULL;
    BigInt* pout = NULL;

    while (pn)
    {
        pout = new BigInt;
        pout->data = pn->data;

        if (prev)
        {
            pout->next = prev;
        }
        prev = pout;

        pn = pn->next;
    }

    if (n.isneg())
    {
        outstr += '-';
    }

    while (pout)
    {
        outstr += (char)(pout->data + '0');
        pout = pout->next;
    }

    return out << outstr;
}

/*
    bitint.h
*/

#ifndef __BIGINT__
#define __BIGINT__

struct BigInt 
{
public:
    unsigned char data;
    BigInt* next;
    bool bneg;
    BigInt()
    {
        next = NULL;
        bneg = false;
        data = 0;
    }

    ~BigInt()
    {
        if (next)
        {
            delete next;
            next = NULL;
        }
    }

    bool iszero()
    {
        BigInt* pn = this;
        while (pn && pn->data != 0)
        {
            return false;
            pn = pn->next;
        }

        return true;
    }

    bool isneg()
    {
        if (iszero())
        {
            return false;
        }

        return bneg;
    }
};

#endif

相关阅读：

新浪微博 QQ空间

| 1 分2 分3 分4 分5 分 (4.83分 - 6票) Loading ... Loading ... | 这篇文章归档在：C/C++, 算法数据结构. | 永久链接：链接 | 评论（0） |

评论

邮箱地址不会被泄露， 标记为 * 的项目必填。

8 - 2 = *



You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <img alt="" src="" class=""> <pre class=""> <q cite=""> <s> <strike> <strong>

返回顶部