[已解决]C++链表实现的一个大数运算问题！

°希作先生丶

其实已经发过一个帖子了- =不过又出现了一些新的问题，基本思路就是用节点存储一个无符号的32位整形，然后串成链表来表示大数，这个程序再跑到第24轮的时候会出一个看不懂的异常（terminate called after throwing an instance of 'St9bad_alloc' what():  std::bad_alloc）- =然后终止
问题基本已经锁定在remove_zero_end()函数里，因为不调用它就可以正常运行- =不过会浪费大量的内存,这是一个递归的删除函数，用来从表尾开始删除值为0的节点。真的是搞不懂为什么啊，求大神指点。
remove_zero_end代码：

1. void hugeNumber::remove_zero_end()
   
2. {
   
3. 
   
4.     if(this->hgHead == nullptr)
   
5.         return;
   
6.     remove_zero_end(hgHead);
   
7. 
   
8. 
   
9. }
   
10. 
    
11. void hugeNumber::remove_zero_end(hgNumNode* parent)
    
12. {
    
13.     hgNumNode* nextNode = parent->next;
    
14.     if(nextNode == nullptr)
    
15.         return;
    
16.     else if(nextNode->next != nullptr)
    
17.         remove_zero_end(nextNode);
    
18.     if(nextNode->value32 == 0)
    
19.     {
    
20.         delete nextNode;
    
21.         parent->next = nullptr;
    
22.         this->length--;
    
23.     }
    
24. 
    
25. 
    
26. }

复制代码

全部代码如下：

1. #include <iostream>
   
2. #include <conio.h>
   
3. #include "hugeNumber.h"
   
4. #include <cstdlib>
   
5. using namespace std;
   
6. 
   
7. int main()
   
8. {
   
9. 
   
10.    hugeNumber h1;
    
11.    hugeNumber h2;
    
12.    h1.reset_self(1);
    
13.    h2.reset_self(1);
    
14. 
    
15. 
    
16. 
    
17. 
    
18.    for(int i = 0;i < 1000;i++)
    
19.    {
    
20.        h1 += &h2;
    
21.        h2 += &h1;
    
22.        //h2 += &h1;
    
23.        cout<<"h1.length:"<<h1.length<<"  h2.length:"<<h2.length<<endl;
    
24.        cout<<"h1."<<i+1<<"."<<h1.Tostring()<<"  "<<"h2."<<i+2<<"."<<h2.Tostring()<<endl;
    
25.        system("pause");
    
26. 
    
27.    }
    
28. 
    
29. 
    
30.     /*
    
31.     unsigned int nFibonacci[1000];
    
32.     nFibonacci[0] = 1;
    
33.     nFibonacci[1] = 1;
    
34.     cout<<"1."<<nFibonacci[0]<<endl;
    
35.     cout<<"2."<<nFibonacci[1]<<endl;
    
36.     for(int i = 2;i < 1000;i++)
    
37.     {
    
38.         nFibonacci[i] = nFibonacci[i-1]+nFibonacci[i-2];
    
39.         cout<<i+1<<"."<<nFibonacci[i]<<endl;
    
40.         getch();
    
41.     }
    
42.     */
    
43.     return 0;
    
44. }

复制代码

类定义:

1. #ifndef HUGENUMBER_H
   
2. #define HUGENUMBER_H
   
3. #define max_num 0xffffffff
   
4. #include <iostream>
   
5. using namespace std;
   
6. class hgNumNode
   
7. {
   
8.    public:
   
9.      unsigned int value32;//存储32位无符号整形
   
10.      hgNumNode* next;//链表指针
    
11.      hgNumNode(unsigned int values){this->value32 = values;this->next=nullptr;}
    
12.      virtual ~hgNumNode(){};//尽量给缺省实现的虚函数加上函数体否则可能会出现undefined reference to `vtable for
    
13. };
    
14. 
    
15. class hugeNumber
    
16. {
    
17.     public:
    
18.         hugeNumber();
    
19.         virtual ~hugeNumber();
    
20.         hgNumNode* hgHead;//链表头节点
    
21.         int length;//链表长度
    
22.         bool add_Node_in_list(unsigned int values);//添加一个新节点到链表中
    
23.         void cleanList();//清空链表
    
24.         void reset_self(unsigned int values);//清空链表并重设第一个节点的值
    
25.         void remove_zero_end();//删除值为0的节点
    
26.         void remove_zero_end(hgNumNode* parent);
    
27.         void operator +=(hugeNumber* afterNum);//重载+=
    
28.         string Tostring();
    
29.         string Tostring(hgNumNode* heads);
    
30. 
    
31.     protected:
    
32. 
    
33.     private:
    
34. };
    
35. 
    
36. #endif // HUGENUMBER_H

复制代码

类的实现:

1. #include "hugeNumber.h"
   
2. #include <cstdio>
   
3. #include <cstdlib>
   
4. 
   
5. hugeNumber::hugeNumber()
   
6. {
   
7.     this->hgHead = nullptr;
   
8.     this->length = 0;
   
9. }
   
10. 
    
11. hugeNumber::~hugeNumber()
    
12. {
    
13.     cleanList();
    
14. }
    
15. 
    
16. bool hugeNumber::add_Node_in_list(unsigned int values)
    
17. {
    
18.     hgNumNode* addNode = new hgNumNode(values);
    
19.     hgNumNode* findNode =this->hgHead;
    
20.     addNode->next = nullptr;
    
21.     if(this->length == 0)
    
22.     {
    
23.         this->hgHead =addNode;
    
24.         this->length= 1;
    
25.         return true;
    
26.     }
    
27.     while(findNode->next != nullptr)findNode = findNode->next;
    
28.     findNode->next = addNode;
    
29. 
    
30.     this->length++;
    
31.     return true;
    
32. }
    
33. 
    
34. void hugeNumber::cleanList()
    
35. {
    
36.     hgNumNode* delNode = this->hgHead;
    
37.     hgNumNode* nextNode = nullptr;
    
38.     while(delNode != nullptr)//不能再对象析构中调用delete删除相同对象,这样会导致无限调用析构的死循环递归
    
39.     {
    
40.          nextNode = delNode->next;
    
41.          delete delNode;
    
42.          delNode = nextNode;
    
43.     }
    
44.     this->length = 0;
    
45.     this->hgHead = nullptr;
    
46. 
    
47. 
    
48. }
    
49. 
    
50. void hugeNumber::reset_self(unsigned int tar)
    
51. {
    
52.     cleanList();
    
53.     hgNumNode* newNode= new hgNumNode(tar);
    
54.     this->hgHead = newNode;
    
55.     this->hgHead->next= nullptr;
    
56.     this->length++;
    
57. }
    
58. void hugeNumber::remove_zero_end()
    
59. {
    
60. 
    
61.     if(this->hgHead == nullptr)
    
62.         return;
    
63.     remove_zero_end(hgHead);
    
64. 
    
65. 
    
66. }
    
67. 
    
68. void hugeNumber::remove_zero_end(hgNumNode* parent)
    
69. {
    
70.     hgNumNode* nextNode = parent->next;
    
71.     if(nextNode == nullptr)
    
72.         return;
    
73.     else if(nextNode->next != nullptr)
    
74.         remove_zero_end(nextNode);
    
75.     if(nextNode->value32 == 0)
    
76.     {
    
77.         delete nextNode;
    
78.         parent->next = nullptr;
    
79.         this->length--;
    
80.     }
    
81. 
    
82. 
    
83. }
    
84. 
    
85. void hugeNumber::operator+=(hugeNumber* afterNum)
    
86. {
    
87.        if(this->length < afterNum->length)
    
88.         {
    
89.             for(int i = this->length;i < afterNum->length;i++)
    
90.                 this->add_Node_in_list(0);
    
91. 
    
92.         }
    
93.        this->add_Node_in_list(0);
    
94.     //this->add_Node_in_list(0);
    
95. 
    
96.     hgNumNode* h1 = this->hgHead;
    
97.     hgNumNode* h2 = afterNum->hgHead;
    
98. 
    
99.     while(true)
    
100.     {
     
101.         if(h1 == nullptr)
     
102.             break;
     
103.         if(h2 == nullptr)
     
104.             break;
     
105.         if(max_num - h1->value32 < h2->value32)
     
106.             h1->next->value32+=1;
     
107.         h1->value32 += h2->value32;
     
108.         h1 = h1->next;
     
109.         h2 = h2->next;
     
110.         remove_zero_end();
     
111.         //cout<<this->Tostring()<<endl;
     
112. 
     
113.     }
     
114. 
     
115. }
     
116. 
     
117. string hugeNumber::Tostring()
     
118. {
     
119.     if(this->hgHead == nullptr)
     
120.         return "0";
     
121. 
     
122.     string ret = "0x"+Tostring(this->hgHead);
     
123.     return ret;
     
124. }
     
125. 
     
126. string hugeNumber::Tostring(hgNumNode* heads)
     
127. {
     
128.     string ret ="-";
     
129.     if(heads->next != nullptr)
     
130.     {
     
131.         ret+=Tostring(heads->next);
     
132.     }
     
133.     char temp[10];
     
134.     sprintf(temp,"%08x",heads->value32);
     
135.     ret.append(temp);
     
136.     return ret;
     
137. }

复制代码

最佳答案

月排行榜 / 总排行榜

Croper

2019-4-23 20:12:40

不好意思，我没看清。。。

1. void hugeNumber::operator+=(hugeNumber* afterNum)
   
2. {
   
3.        if(this->length < afterNum->length)
   
4.         {
   
5.             for(int i = this->length;i < afterNum->length;i++)
   
6.                 this->add_Node_in_list(0);
   
7. 
   
8.         }
   
9.        this->add_Node_in_list(0);
   
10.     //this->add_Node_in_list(0);
    
11. 
    
12.     hgNumNode* h1 = this->hgHead;
    
13.     hgNumNode* h2 = afterNum->hgHead;
    
14. 
    
15.     while(true)
    
16.     {
    
17.         if(h1 == nullptr)
    
18.             break;
    
19.         if(h2 == nullptr)
    
20.             break;
    
21.         if(max_num - h1->value32 < h2->value32)
    
22.             h1->next->value32+=1;
    
23.         h1->value32 += h2->value32;
    
24.         h1 = h1->next;
    
25.         h2 = h2->next;
    
26.         remove_zero_end();
    
27.         //cout<<this->Tostring()<<endl;
    
28. 
    
29.     }
    
30. 
    
31. }

复制代码

把remove_zero_end丢出来

1. void hugeNumber::operator+=(hugeNumber* afterNum)
   
2. {
   
3.        if(this->length < afterNum->length)
   
4.         {
   
5.             for(int i = this->length;i < afterNum->length;i++)
   
6.                 this->add_Node_in_list(0);
   
7. 
   
8.         }
   
9.        this->add_Node_in_list(0);
   
10.     //this->add_Node_in_list(0);
    
11. 
    
12.     hgNumNode* h1 = this->hgHead;
    
13.     hgNumNode* h2 = afterNum->hgHead;
    
14. 
    
15.     while(true)
    
16.     {
    
17.         if(h1 == nullptr)
    
18.             break;
    
19.         if(h2 == nullptr)
    
20.             break;
    
21.         if(max_num - h1->value32 < h2->value32)
    
22.             h1->next->value32+=1;
    
23.         h1->value32 += h2->value32;
    
24.         h1 = h1->next;
    
25.         h2 = h2->next;
    
26. 
    
27.         //cout<<this->Tostring()<<endl;
    
28. 
    
29.     }
    
30.     remove_zero_end();
    
31. }

复制代码

跳转到最佳答案楼层

Croper

所以我的解答你是根本没看么。。问题都给你指出来改好了
。。结果你又改回去又重新来提。。。看不懂

°希作先生丶

Croper 发表于 2019-4-23 19:12
所以我的解答你是根本没看么。。问题都给你指出来改好了
。。结果你又改回去又重新来提。。。看不懂

没有啊大佬，你说那几点我都改了，顺便还把那个基本没啥用尾节点指针给去掉了啊。。

°希作先生丶

°希作先生丶 发表于 2019-4-23 19:46
没有啊大佬，你说那几点我都改了，顺便还把那个基本没啥用尾节点指针给去掉了啊。。

删除的时候重新建了个中间的交换节点，然后直接把尾节点给去掉了，因为我感觉再递归里不好确认它到底该指哪。真的没有无视你的意思啊

Croper

不好意思，我没看清。。。

1. void hugeNumber::operator+=(hugeNumber* afterNum)
   
2. {
   
3.        if(this->length < afterNum->length)
   
4.         {
   
5.             for(int i = this->length;i < afterNum->length;i++)
   
6.                 this->add_Node_in_list(0);
   
7. 
   
8.         }
   
9.        this->add_Node_in_list(0);
   
10.     //this->add_Node_in_list(0);
    
11. 
    
12.     hgNumNode* h1 = this->hgHead;
    
13.     hgNumNode* h2 = afterNum->hgHead;
    
14. 
    
15.     while(true)
    
16.     {
    
17.         if(h1 == nullptr)
    
18.             break;
    
19.         if(h2 == nullptr)
    
20.             break;
    
21.         if(max_num - h1->value32 < h2->value32)
    
22.             h1->next->value32+=1;
    
23.         h1->value32 += h2->value32;
    
24.         h1 = h1->next;
    
25.         h2 = h2->next;
    
26.         remove_zero_end();
    
27.         //cout<<this->Tostring()<<endl;
    
28. 
    
29.     }
    
30. 
    
31. }

复制代码

把remove_zero_end丢出来

1. void hugeNumber::operator+=(hugeNumber* afterNum)
   
2. {
   
3.        if(this->length < afterNum->length)
   
4.         {
   
5.             for(int i = this->length;i < afterNum->length;i++)
   
6.                 this->add_Node_in_list(0);
   
7. 
   
8.         }
   
9.        this->add_Node_in_list(0);
   
10.     //this->add_Node_in_list(0);
    
11. 
    
12.     hgNumNode* h1 = this->hgHead;
    
13.     hgNumNode* h2 = afterNum->hgHead;
    
14. 
    
15.     while(true)
    
16.     {
    
17.         if(h1 == nullptr)
    
18.             break;
    
19.         if(h2 == nullptr)
    
20.             break;
    
21.         if(max_num - h1->value32 < h2->value32)
    
22.             h1->next->value32+=1;
    
23.         h1->value32 += h2->value32;
    
24.         h1 = h1->next;
    
25.         h2 = h2->next;
    
26. 
    
27.         //cout<<this->Tostring()<<endl;
    
28. 
    
29.     }
    
30.     remove_zero_end();
    
31. }

复制代码

°希作先生丶

Croper 发表于 2019-4-23 20:12
不好意思，我没看清。。。

把remove_zero_end丢出来

哦！成功了，感谢大佬无私的帮助~