C++关于使用链表实现大数求和的问题,C\C++交流,技术交流,鱼C论坛

°希作先生丶 发表于 2019-4-23 11:05:33

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;
nFibonacci = 1;
nFibonacci = 1;
cout<<"1."<<nFibonacci<<endl;
cout<<"2."<<nFibonacci<<endl;
for(int i = 2;i < 1000;i++)
{
   nFibonacci = nFibonacci+nFibonacci;
   cout<<i+1<<"."<<nFibonacci<<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;
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,

°希作先生丶 发表于 2019-4-23 14:17:37

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

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

Croper 发表于 2019-4-23 14:41:35

#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') {
szhex.erase(szhex.begin());
}
szhex = "0x" + szhex;

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

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

页: [1]

鱼C论坛's Archiver

C++关于使用链表实现大数求和的问题