大整数乘法
很长时间都没写过代码了,试着写了这个常见的题目。整体思路:采用整形链表记录大整数的每一位,然后分别遍历乘数和被乘数的每一位,将每两个数字的乘积累加到结果的相应位上面。针对大整数类型,重载输入和输出流,重载乘法。
输出部分实现不是特别好。用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
建议继续学习:
扫一扫订阅我的微信号:IT技术博客大学习
- 作者:童燕群 来源: 忘我的追寻
- 标签: 乘法 整数
- 发布时间:2013-09-23 23:08:03
- [46] 界面设计速成
- [40] 视觉调整-设计师 vs. 逻辑
- [40] Oracle MTS模式下 进程地址与会话信
- [38] IOS安全–浅谈关于IOS加固的几种方法
- [37] android 开发入门
- [36] 如何拿下简短的域名
- [36] 程序员技术练级攻略
- [35] 【社会化设计】自我(self)部分――欢迎区
- [35] 图书馆的世界纪录
- [32] 读书笔记-壹百度:百度十年千倍的29条法则