关于超大数相加的一个算法
本帖最后由 麦田管理中心 于 2016-1-22 11:30 编辑/*这是两个超大数相加的算法，思路就是个位相加取余保存在一个结果栈中，然后个位相加的结果÷10结果赋值给carry，然后十位相加再加carry取余放到结果栈里，同理依次算下去，<u>如果需要全部源码请说一下，我马上贴出来（主要是想解决问题）*/
stack<int> addinglargenumber(stack<int> stack1,stack<int> stack2)
/*最高位放在栈的最下面,如果这两个形参被赋值为相同的实参，那么stack1和stack2共用一段内存，这个导致两个相同的数相加出错*/
{
int carry = 0;
stack<int> stacktmp = stack2;
/*stacktmp {head=0x00f6d448 {vacabulary=9 next=0x00f6d410 {vacabulary=8 next=0x00f6d3d8 {vacabulary=7 next=0x00f6d3a0 {...} ...} ...} ...} ...}*/
/*stack1 {head=0x00f6d448{vacabulary=9 next=0x00f6d410 {vacabulary=8 next=0x00f6d3d8 {vacabulary=7 next=0x00f6d3a0 {...} ...} ...} ...} ...}*/
//比较stack1和stacktmp的地址始终相同，导致pop（）函数运算出错
stack<int> stack3;//存放大数的和
int a = 0, b = 0;
while (!stack1.isempty() && !stacktmp.isempty())
{
a = stack1.topEI(); b = stacktmp.topEI();
stack3.push((stack1.pop() + stacktmp.pop()/*问题可能出现在这*/ + carry) % 10);
/*掉用pop（）函数是因为共用内存所以出错*/
carry = (a + b + carry) / 10;
}
if (stack1.isempty() && stacktmp.isempty())
{
if (carry != 0)
{
stack3.push(carry);
}
}
else
{
if (stack1.isempty())
while (!stacktmp.isempty())
{
stack3.push((a = (stacktmp.pop() + carry)) % 10);
carry = a / 10;
}
else
{
while (!stack1.isempty())
{
stack3.push((a = (stack1.pop() + carry)) % 10);
carry = a / 10;
}
}
}
return stack3;
}
template<class T>
T stack<T>::pop()
{
node<T> *tmp = head;
T a = head->vacabulary;//a的赋值有问题
head = head->next;//无法读取内存
delete tmp;
return a;
}
void main()
{
stack<int> s1, s2, s3;
for (int i = 0; i < 10; i++)
s1.push(i);
s1.print();
s2 = s1;
s2.print();
s3 = addinglargenumber(s1, s1);
s3.print();
}
问题我自己已经解决，有兴趣的同学可以运行一下
#include<iostream>
using namespace std;
template<class T>
class node
{
public:
node(T a, node* b = 0, node* c = 0)
{
vacabulary = a;
next = b;
pre = c;
}
T vacabulary;
node *next, *pre;
};
template<class T>
class stack
{
public:
node<T> *head, *tail;
stack()
{
head = 0; tail = 0;
}
void push(T a);//将字符放在栈的顶部
void clear();//清空栈
int isempty();//判断栈是否为空，空就返回0
T pop();//弹出顶部的元素
T topEI();//获取顶部的元素，但不删除
void operator=(stack);//重载=运算符
void upsidedown();//颠倒栈的顺序
void print()
{
for (node<T>* tmp = head; tmp != NULL; tmp = tmp->next)
{
if (tmp->vacabulary > 9)
cout << char(tmp->vacabulary + 55);
else
cout << tmp->vacabulary;
}
cout << endl;
}
};
template<class T>
void stack<T>::push(T a)
{
node<T> *tmp;
if (head == NULL)
{
head = new node<T>(a, 0, 0);
tail = head;
}
else
{
if (head == tail)
{
tmp = new node<T>(a, head, 0);
head->pre = tmp;
head = tmp;
}
else
{
tmp = new node<T>(a, head, 0);
head->pre = tmp;
head = tmp;
}
}
}
template<class T>
void stack<T>::clear()
{
node<T> *tmp = head;
if (head == NULL)
{
cout << "清空完成" << endl;
}
else
{
if (head == tail)
{
delete head;
cout << "清空完成" << endl;
}
else
{
for (; head != NULL; head = tmp)
{
tmp = tmp->next;
delete head;
}
cout << "清空完成" << endl;
}
}
}
template<class T>
int stack<T>::isempty()
{
if (head == NULL)
return 1;
return 0;
}
template<class T>
T stack<T>::pop()
{
node<T> *tmp = head;
T a = head->vacabulary;
head = head->next;
delete tmp;
return a;
}
template<class T>
T stack<T>::topEI()
{
return head->vacabulary;
}
template<class T>
void stack<T>::operator=(stack<T> a)
{
node<T> *n;
n = a.tail;
this->clear();
while (n != NULL)
{
this->push(n->vacabulary);
n = n->pre;
}
}
template<class T>
void stack<T>::upsidedown()
{
stack<T> stack1;
stack1.operator=(*this);
this->clear();
while (!stack1.isempty())
{
this->push(stack1.pop());
}
stack1.clear();
}
/*这是两个超大数相加的算法，思路就是个位相加取余保存在一个结果栈中，然后个位相加的结果÷10结果赋值给carry，然后十位相加再加carry取余放到结果栈里，同理依次算下去*/
stack<int> addinglargenumber(stack<int> stack1,stack<int> stack2)
{
int carry = 0;
stack<int> stacktmp1;
stack<int> stacktmp2;
stacktmp1.operator=(stack1);
stacktmp2.operator=(stack2);//这样的赋值就成功了，如果直接写=好而不调用重载运算符，那就是stacktmp和stack2公用一段内存
stack<int> stack3;//存放大数的和
int a = 0, b = 0;
while (!stacktmp1.isempty() && !stacktmp2.isempty())
{
a = stacktmp1.topEI(); b = stacktmp2.topEI();
stack3.push((stacktmp1.pop() + stacktmp2.pop() + carry) % 10);
carry = (a + b + carry) / 10;
}
if (stacktmp1.isempty() && stacktmp2.isempty())
{
if (carry != 0)
{
stack3.push(carry);
}
}
else
{
if (stacktmp1.isempty())
while (!stacktmp2.isempty())
{
stack3.push((a = (stacktmp2.pop() + carry)) % 10);
carry = a / 10;
}
else
{
while (!stacktmp1.isempty())
{
stack3.push((a = (stacktmp1.pop() + carry)) % 10);
carry = a / 10;
}
}
}
return stack3;//个位放在结果栈的最下面
}
void multiplelargenumber()//两个超大数相乘
{
int i = 0;
int carry = 0;
stack<int> stack1;//两个因子
stack<int> stack2;
stack<int> stack3;//存放结果
stack<int> stack4;//临时存放stack1
char tmp;//临时储存用的
cout << "输入第1个数字(e代表结束)" << endl;
for (i = 0; 1; i++)
{
cin >> tmp;
if (tmp == 'e')
break;
}
i = 0;
while (tmp != 'e')
{
stack1.push((int)tmp - 48);//最高位放在栈的最下面
}
cout << "输入第2个数字(e代表结束)" << endl;
for (i = 0; 1; i++)
{
cin >> tmp;
if (tmp == 'e')
break;
}
i = 0;
while (tmp != 'e')
{
stack2.push((int)tmp - 48);//－48很重要，‘1’和1不一样。。//最高位放在栈的最下面
}
/**********以上为创建两个因子的栈************/
stack4 = stack1;
cout << "栈的个数" << i << endl;
int stacknum = i;
stack<int> *tmpp = new stack<int>;//创建的一系列栈用来求和,一共有i个栈
int a, b;
int j = 0;
i = 0;
for (; !stack2.isempty();)//用于计算求和栈，个位放在最下面
{
for (; !stack1.isempty();)
{
tmpp.push(((a = stack2.topEI())*(b = stack1.pop()) + carry) % 10);
carry = (((a*b) + carry) / 10);
}
stack2.pop();
stack1 = stack4;
i++;
if (i != stacknum)
{
for (j = 0; j < i; j++)
tmpp.push(0);
}
}
for (j = 0; j < stacknum; j++)//所有的求和栈颠倒顺序，用于最后一步求得积
{
tmpp.upsidedown();
tmpp.print();
}
stack3.operator=(tmpp);
stack<int> stacktmp;
for (j = 1; j < stacknum; j++)
{
stacktmp.operator=(addinglargenumber(stack3, tmpp));
stack3.clear();
stack3.operator=(stacktmp);
stacktmp.clear();
stack3.upsidedown();
}
stack3.upsidedown();
stack3.print();
}
void main()
{
multiplelargenumber();
}
页:
[1]