关于超大数相加的一个算法

麦田管理中心

/*这是两个超大数相加的算法，思路就是个位相加取余保存在一个结果栈中，然后个位相加的结果÷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[1000];//临时储存用的
        cout << "输入第1个数字(e代表结束)" << endl;
        for (i = 0; 1; i++)
        {
                cin >> tmp[i];
                if (tmp[i] == 'e')
                        break;
        }
        i = 0;
        while (tmp[i] != 'e')
        {
                stack1.push((int)tmp[i++] - 48);//最高位放在栈的最下面
        }

        cout << "输入第2个数字(e代表结束)" << endl;
        for (i = 0; 1; i++)
        {
                cin >> tmp[i];
                if (tmp[i] == 'e')
                        break;
        }
        i = 0;
        while (tmp[i] != 'e')
        {
                stack2.push((int)tmp[i++] - 48);//－48很重要，‘1’和1不一样。。//最高位放在栈的最下面
        }
        /**********以上为创建两个因子的栈************/
        stack4 = stack1;
        cout << "栈的个数" << i << endl;
        int stacknum = i;
        stack<int> *tmpp = new stack<int>[i];//创建的一系列栈用来求和,一共有i个栈
        int a, b;
        int j = 0;
        i = 0;
        for (; !stack2.isempty();)//用于计算求和栈，个位放在最下面
        {
                for (; !stack1.isempty();)
                {
                        tmpp[i].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[i].push(0);
                }
        }
        for (j = 0; j < stacknum; j++)//所有的求和栈颠倒顺序，用于最后一步求得积
        {
                tmpp[j].upsidedown();
                tmpp[j].print();
        }
        stack3.operator=(tmpp[0]);
        stack<int> stacktmp;
        for (j = 1; j < stacknum; j++)
        {
                stacktmp.operator=(addinglargenumber(stack3, tmpp[j]));
                stack3.clear();
                stack3.operator=(stacktmp);
                stacktmp.clear();
                stack3.upsidedown();
        }
        stack3.upsidedown();
        stack3.print();
}
void main()
{
        multiplelargenumber();
}