[已解决]C++关于使用链表实现大数求和的问题

°希作先生丶

具体是这样的，我编写了两个大数存储的类用于计算斐波那契数列，并设置了两个大数变量h1 h2 分别赋值1 但是在重载了+=之后发现在一次循环里用h1 += &h2完全没有问题，但是接着用h2 += &h1时候就会莫名的抛异常退出，异常是：terminate called after throwing an instance of
下面附上代码

#include <iostream>
#include <conio.h>
#include "hugeNumber.h"
#include <cstdlib>
using namespace std;

int main()
{



   hugeNumber h1;
   hugeNumber h2;
   h1.add_Node_in_list(1);
   h2.add_Node_in_list(1);




   for(int i = 0;i < 1000;i++)
   {
       h1 += &h2;
       h2 += &h1;
       system("pause");
       cout<<i+1<<"-"<<h1.Tostring()<<i+2<<h2.Tostring()<<endl;


   }


    /*
    unsigned int nFibonacci[1000];
    nFibonacci[0] = 1;
    nFibonacci[1] = 1;
    cout<<"1."<<nFibonacci[0]<<endl;
    cout<<"2."<<nFibonacci[1]<<endl;
    for(int i = 2;i < 1000;i++)
    {
        nFibonacci[i] = nFibonacci[i-1]+nFibonacci[i-2];
        cout<<i+1<<"."<<nFibonacci[i]<<endl;
        getch();
    }
    */
    return 0;
}

类的定义:

#ifndef HUGENUMBER_H
#define HUGENUMBER_H
#define max_num 0xffffffff
#include <iostream>
using namespace std;
class hgNumNode
{
   public:
     unsigned int value32;//存储32位无符号整形
     hgNumNode* next;//链表指针
     hgNumNode(unsigned int values){this->value32 = values;this->next=nullptr;}
     virtual ~hgNumNode(){};//尽量给缺省实现的虚函数加上函数体否则可能会出现undefined reference to `vtable for
};

class hugeNumber
{
    public:
        hugeNumber();
        virtual ~hugeNumber();
        hgNumNode* hgHead;//链表头节点
        int length;//链表长度
        hgNumNode* hgLast;//链表尾节点
        bool add_Node_in_list(unsigned int values);//添加一个新节点到链表中
        void cleanList();//清空链表
        void reset_self(unsigned int values);//清空链表并重设第一个节点的值
        void remove_zero_end();//删除值为0的节点
        void remove_zero_end(hgNumNode* parent);
        void operator +=(hugeNumber* afterNum);//重载+=
        string Tostring();
        string Tostring(hgNumNode* heads);

    protected:

    private:
};

#endif // HUGENUMBER_H

类的实现:

#include "hugeNumber.h"
#include <cstdio>

hugeNumber::hugeNumber()
{
    this->hgHead = nullptr;
    this->length = 0;
    this->hgLast = nullptr;
}

hugeNumber::~hugeNumber()
{
    cleanList();
}

bool hugeNumber::add_Node_in_list(unsigned int values)
{
    hgNumNode* addNode = new hgNumNode(values);
    if(this->length == 0)
    {
        this->hgHead =addNode;
        this->hgLast =addNode;
        this->length= 1;
        return true;
    }
    this->hgLast->next=addNode;
    this->hgLast = addNode;
    this->length++;
    return true;
}

void hugeNumber::cleanList()
{
    hgNumNode* delNode = this->hgHead;
    while(delNode != nullptr)//不能再对象析构中调用delete删除相同对象,这样会导致无限调用析构的死循环递归
    {
         delete delNode;
         delNode = delNode->next;
    }
    this->length = 0;
    this->hgHead = nullptr;
    this->hgLast = nullptr;


}

void hugeNumber::reset_self(unsigned int tar)
{
    cleanList();
    hgNumNode* newNode= new hgNumNode(tar);
    this->hgHead = newNode;
    this->hgLast = newNode;
    this->length++;
}
void hugeNumber::remove_zero_end()
{
    if(this->hgHead == nullptr)
        return;
    remove_zero_end(this->hgHead);

}

void hugeNumber::remove_zero_end(hgNumNode* parent)
{
    if(parent == nullptr)
        return;
    else
        remove_zero_end(parent->next);
    if(parent->value32 == 0)
    {
        delete parent;
        parent= nullptr;
        this->length--;
    }


}

void hugeNumber::operator+=(hugeNumber* afterNum)
{
    cout<<"begin"<<endl;
    if(this->length == afterNum->length)
    {
        this->add_Node_in_list(0);

    }
    else if(this->length < afterNum->length)
    {
        for(int i = this->length;i < afterNum->length;i++)
            this->add_Node_in_list(0);

    }
    this->add_Node_in_list(0);
    this->add_Node_in_list(0);

    hgNumNode* h1 = this->hgHead;
    hgNumNode* h2 = afterNum->hgHead;

    while(true)
    {
        if(h1 == nullptr)
            break;
        if(h2 == nullptr)
            break;
        if(max_num - h1->value32 < h2->value32)
            h1->next->value32+=1;
        h1->value32 += h2->value32;
        cout<<"now-values-"<<h1->value32<<endl;
        h1 = h1->next;
        h2 = h2->next;
        remove_zero_end();


    }
    cout<<"end"<<endl;

}

string hugeNumber::Tostring()
{
    if(this->hgHead == nullptr)
        return "0";

    string ret = "0x"+Tostring(this->hgHead);
    return ret;
}

string hugeNumber::Tostring(hgNumNode* heads)
{
    string ret ="-";
    if(heads->next != nullptr)
    {
        ret+=Tostring(heads->next);
    }
    char temp[10];
    sprintf(temp,"%08x",heads->value32);
    ret.append(temp);
    return ret;
}

最佳答案

月排行榜 / 总排行榜

Croper

2019-4-23 12:34:37

调试代码比自己写代码累多了。。。
先说我找出来的问题吧

void hugeNumber::reset_self(unsigned int tar)
{
    cleanList();
    hgNumNode* newNode= new hgNumNode(tar);
    this->hgHead = newNode;
    this->hgLast = newNode;
    this->length++;
}
void hugeNumber::remove_zero_end()
{
    if(this->hgHead == nullptr)
        return;
    remove_zero_end(this->hgHead);

}

删除后，尾节点的next指针没有置nullptr，且hgLast指针没有修改，
最小的修改方案：

void hugeNumber::remove_zero_end()
{
        if (this->hgHead == nullptr)
                return;
        remove_zero_end(this->hgHead,this->hgLast);
        this->hgLast->next = nullptr;
}

bool hugeNumber::remove_zero_end(hgNumNode* parent,hgNumNode*& lastpointer)
{
        if (parent == nullptr) {
                lastpointer = nullptr;
                return true;
        }
        else {
                if (remove_zero_end(parent->next, lastpointer)) {
                        lastpointer = parent;
                }
        }
                
        
        if (parent->value32 == 0)
        {
                delete parent;
                parent = nullptr;
                this->length--;
                return true;
        }
        return false;
}

还有

void hugeNumber::cleanList()
{
    hgNumNode* delNode = this->hgHead;
    while(delNode != nullptr)//不能再对象析构中调用delete删除相同对象,这样会导致无限调用析构的死循环递归
    {
         delete delNode;
         delNode = delNode->next;
    }
    this->length = 0;
    this->hgHead = nullptr;
    this->hgLast = nullptr;


}

delete delNode后，再调用delNode会出现错误，建议改成

void hugeNumber::cleanList()
{
        hgNumNode* delNode = this->hgHead;
        while (delNode != nullptr)//不能再对象析构中调用delete删除相同对象,这样会导致无限调用析构的死循环递归
        {
                hgNumNode* next = delNode->next;
                delete delNode;
                delNode = next;
        }
        this->length = 0;
        this->hgHead = nullptr;
        this->hgLast = nullptr;


}

仍然有错误，我重新实现个大数类吧0 0,

跳转到最佳答案楼层

Croper

调试代码比自己写代码累多了。。。
先说我找出来的问题吧

void hugeNumber::reset_self(unsigned int tar)
{
    cleanList();
    hgNumNode* newNode= new hgNumNode(tar);
    this->hgHead = newNode;
    this->hgLast = newNode;
    this->length++;
}
void hugeNumber::remove_zero_end()
{
    if(this->hgHead == nullptr)
        return;
    remove_zero_end(this->hgHead);

}

删除后，尾节点的next指针没有置nullptr，且hgLast指针没有修改，
最小的修改方案：

void hugeNumber::remove_zero_end()
{
        if (this->hgHead == nullptr)
                return;
        remove_zero_end(this->hgHead,this->hgLast);
        this->hgLast->next = nullptr;
}

bool hugeNumber::remove_zero_end(hgNumNode* parent,hgNumNode*& lastpointer)
{
        if (parent == nullptr) {
                lastpointer = nullptr;
                return true;
        }
        else {
                if (remove_zero_end(parent->next, lastpointer)) {
                        lastpointer = parent;
                }
        }
                
        
        if (parent->value32 == 0)
        {
                delete parent;
                parent = nullptr;
                this->length--;
                return true;
        }
        return false;
}

还有

void hugeNumber::cleanList()
{
    hgNumNode* delNode = this->hgHead;
    while(delNode != nullptr)//不能再对象析构中调用delete删除相同对象,这样会导致无限调用析构的死循环递归
    {
         delete delNode;
         delNode = delNode->next;
    }
    this->length = 0;
    this->hgHead = nullptr;
    this->hgLast = nullptr;


}

delete delNode后，再调用delNode会出现错误，建议改成

void hugeNumber::cleanList()
{
        hgNumNode* delNode = this->hgHead;
        while (delNode != nullptr)//不能再对象析构中调用delete删除相同对象,这样会导致无限调用析构的死循环递归
        {
                hgNumNode* next = delNode->next;
                delete delNode;
                delNode = next;
        }
        this->length = 0;
        this->hgHead = nullptr;
        this->hgLast = nullptr;


}

仍然有错误，我重新实现个大数类吧0 0,

°希作先生丶

Croper 发表于 2019-4-23 12:34
调试代码比自己写代码累多了。。。
先说我找出来的问题吧

非常感谢回答，我找到错误了，错误是函数 void remove_zero_end(); 在对hgHead节点值为0的处理有问题，会把它直接赋nullptr，之后的调用就出问题了，非常感谢您的答疑。

Croper

#ifndef HUGENUMBER_H
#define HUGENUMBER_H
#define max_num 0xffffffff

#include <iostream>
#include <sstream>
#include <iomanip>

class hugeNumber {
private:
        struct Node {
                unsigned int val;
                Node* pre;
                Node* next;
                Node(unsigned int val0=0) :pre(this), next(this), val(val0) {};

                Node* insert_back(unsigned val0 = 0);
                ~Node();
        };

        Node* _myhead;
        int _mysize;

        void remove_zero_end();
        bool SumOverflow(unsigned int num1, unsigned int num2, unsigned int a);
public:
        hugeNumber();
        hugeNumber(unsigned int val0);
        hugeNumber(const hugeNumber&);
        hugeNumber(hugeNumber&&);
        ~hugeNumber();

        int size() const;
        void clear();

        hugeNumber&  operator=(unsigned int val0);
        hugeNumber& operator+=(const hugeNumber& num1);

        std::string to_string() const;
};

#include "hugeNumber.h"

inline hugeNumber::Node * hugeNumber::Node::insert_back(unsigned val0) {
        Node* tmp = next;
        next = new Node(val0);
        next->pre = this;
        next->next = tmp;
        if (tmp != nullptr) {
                tmp->pre = next;
        }

        return next;
}

inline hugeNumber::Node::~Node() {
        if (pre != nullptr) pre->next = next;
        if (next != nullptr) next->pre = pre;
}

inline void hugeNumber::remove_zero_end() {
        while (_myhead->pre != _myhead && _myhead->pre->val == 0) {
                delete _myhead->pre;
                _mysize--;
        }
}

inline bool hugeNumber::SumOverflow(unsigned int num1, unsigned int num2, unsigned int a) {
        if (a > 1) {
                std::cerr << "Error: illegal a";
                return false;
        }

        if (a == 0) {
                return max_num - num1 < num2;
        }

        if (num1 == max_num || num2 == max_num) return true;
        return max_num - num1 < num2 + 1;
}

inline hugeNumber::hugeNumber() {
        _myhead = new Node;
        _mysize = 0;
}

inline hugeNumber::hugeNumber(unsigned int val0) :hugeNumber() {
        if (val0 == 0) return;
        _myhead->insert_back(val0);
        _mysize = 1;
}

hugeNumber::hugeNumber(const hugeNumber & num0):hugeNumber()
{
        _mysize = num0._mysize;
        for (Node *p = num0._myhead->pre; p != num0._myhead; p = p->pre) {
                _myhead->insert_back(p->val);
        }
}

hugeNumber::hugeNumber(hugeNumber && num0)
{
        auto tmp = _myhead;
        _myhead = num0._myhead;
        num0._myhead = tmp;
}

inline hugeNumber::~hugeNumber() {
        Node* p = _myhead->next;
        while (p != _myhead) {
                Node* tmp = p->next;
                delete p;
                p = tmp;
        }
        delete _myhead;
}

inline int hugeNumber::size() const {
        return _mysize;
}

inline void hugeNumber::clear() {
        Node* p = _myhead->next;
        while (p != _myhead) {
                Node* tmp = p->next;
                delete p;
                p = tmp;
        }
        _mysize = 0;
}




hugeNumber&  hugeNumber::operator=(unsigned int val0) {
        clear();
        if (val0 == 0) return *this;
        _myhead->insert_back(val0);
        _mysize = 1;
        return *this;
}

hugeNumber& hugeNumber::operator+=(const hugeNumber& num1) {
        unsigned int a = 0;
        Node* p1 = _myhead->next, *p2 = num1._myhead->next;
        while (p1 != _myhead || p2 != num1._myhead) {
                int next_a = SumOverflow(p1->val, p2->val, a);
                p1->val = p1->val + p2->val + a;
                a = next_a;

                p1 = p1->next;
                if (p2 != num1._myhead) {
                        p2 = p2->next;
                        if (p2 != num1._myhead && p1 == _myhead) {
                                p1 = _myhead->pre->insert_back(0);
                                ++_mysize;
                        }
                }
        }
        if (a != 0) {
                _myhead->pre->insert_back(a);
                ++_mysize;
        }

        return *this;
}

inline std::string hugeNumber::to_string() const {
        if (_mysize == 0) return "0x0(0)";
        if (_mysize >1) {
                int a = 4;
        }
        std::stringstream hex, dec;
        hex << std::setbase(16) << std::setw(8) << std::setfill('0');
        Node* p = _myhead->pre;
        while (p != _myhead) {
                hex << p->val;
                dec << "-" << p->val;
                p = p->pre;
        }
        std::string szhex = hex.str();
        while (szhex[0] == '0') {
                szhex.erase(szhex.begin());
        }
        szhex = "0x" + szhex;

        std::string szdec = dec.str();
        szdec.erase(szdec.begin());

        return szhex + "(" + szdec + ")";
}