技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 大整数乘法

大整数乘法

浏览:1464次  出处信息

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

   输出部分实现不是特别好。用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

   

建议继续学习:

  1. 编写安全代码:再论整数类型转换    (阅读:2643)
  2. PHP操作MongoDB时的整数问题及对策    (阅读:1960)
  3. 小心 int 乘法溢出!    (阅读:1374)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1