大整数乘法

新浪微博 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>

返回顶部