C++链表实现的一个大数运算问题！
其实已经发过一个帖子了- =不过又出现了一些新的问题，基本思路就是用节点存储一个无符号的32位整形，然后串成链表来表示大数，这个程序再跑到第24轮的时候会出一个看不懂的异常（terminate called after throwing an instance of 'St9bad_alloc' what():std::bad_alloc）- =然后终止问题基本已经锁定在remove_zero_end()函数里，因为不调用它就可以正常运行- =不过会浪费大量的内存,这是一个递归的删除函数，用来从表尾开始删除值为0的节点。真的是搞不懂为什么啊，求大神指点。
remove_zero_end代码：
void hugeNumber::remove_zero_end()
{
if(this->hgHead == nullptr)
return;
remove_zero_end(hgHead);
}
void hugeNumber::remove_zero_end(hgNumNode* parent)
{
hgNumNode* nextNode = parent->next;
if(nextNode == nullptr)
return;
else if(nextNode->next != nullptr)
remove_zero_end(nextNode);
if(nextNode->value32 == 0)
{
delete nextNode;
parent->next = nullptr;
this->length--;
}
}
全部代码如下：#include <iostream>
#include <conio.h>
#include "hugeNumber.h"
#include <cstdlib>
using namespace std;
int main()
{
hugeNumber h1;
hugeNumber h2;
h1.reset_self(1);
h2.reset_self(1);
for(int i = 0;i < 1000;i++)
{
h1 += &h2;
h2 += &h1;
//h2 += &h1;
cout<<"h1.length:"<<h1.length<<"h2.length:"<<h2.length<<endl;
cout<<"h1."<<i+1<<"."<<h1.Tostring()<<""<<"h2."<<i+2<<"."<<h2.Tostring()<<endl;
system("pause");
}
/*
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;//链表长度
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>
#include <cstdlib>
hugeNumber::hugeNumber()
{
this->hgHead = nullptr;
this->length = 0;
}
hugeNumber::~hugeNumber()
{
cleanList();
}
bool hugeNumber::add_Node_in_list(unsigned int values)
{
hgNumNode* addNode = new hgNumNode(values);
hgNumNode* findNode =this->hgHead;
addNode->next = nullptr;
if(this->length == 0)
{
this->hgHead =addNode;
this->length= 1;
return true;
}
while(findNode->next != nullptr)findNode = findNode->next;
findNode->next = addNode;
this->length++;
return true;
}
void hugeNumber::cleanList()
{
hgNumNode* delNode = this->hgHead;
hgNumNode* nextNode = nullptr;
while(delNode != nullptr)//不能再对象析构中调用delete删除相同对象,这样会导致无限调用析构的死循环递归
{
nextNode = delNode->next;
delete delNode;
delNode = nextNode;
}
this->length = 0;
this->hgHead = nullptr;
}
void hugeNumber::reset_self(unsigned int tar)
{
cleanList();
hgNumNode* newNode= new hgNumNode(tar);
this->hgHead = newNode;
this->hgHead->next= nullptr;
this->length++;
}
void hugeNumber::remove_zero_end()
{
if(this->hgHead == nullptr)
return;
remove_zero_end(hgHead);
}
void hugeNumber::remove_zero_end(hgNumNode* parent)
{
hgNumNode* nextNode = parent->next;
if(nextNode == nullptr)
return;
else if(nextNode->next != nullptr)
remove_zero_end(nextNode);
if(nextNode->value32 == 0)
{
delete nextNode;
parent->next = nullptr;
this->length--;
}
}
void hugeNumber::operator+=(hugeNumber* afterNum)
{
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;
h1 = h1->next;
h2 = h2->next;
remove_zero_end();
//cout<<this->Tostring()<<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 19:12
所以我的解答你是根本没看么。。问题都给你指出来改好了
。。结果你又改回去又重新来提。。。看不懂
没有啊大佬，你说那几点我都改了，顺便还把那个基本没啥用尾节点指针给去掉了啊。。 °希作先生丶 发表于 2019-4-23 19:46
没有啊大佬，你说那几点我都改了，顺便还把那个基本没啥用尾节点指针给去掉了啊。。
删除的时候重新建了个中间的交换节点，然后直接把尾节点给去掉了，因为我感觉再递归里不好确认它到底该指哪。真的没有无视你的意思啊 不好意思，我没看清。。。
void hugeNumber::operator+=(hugeNumber* afterNum)
{
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;
h1 = h1->next;
h2 = h2->next;
remove_zero_end();
//cout<<this->Tostring()<<endl;
}
}
把remove_zero_end丢出来
void hugeNumber::operator+=(hugeNumber* afterNum)
{
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;
h1 = h1->next;
h2 = h2->next;
//cout<<this->Tostring()<<endl;
}
remove_zero_end();
} Croper 发表于 2019-4-23 20:12
不好意思，我没看清。。。
把remove_zero_end丢出来
哦！成功了，感谢大佬无私的帮助~
页:
[1]