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

°希作先生丶

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

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. 
    
11. 
    
12.    hugeNumber h1;
    
13.    hugeNumber h2;
    
14.    h1.add_Node_in_list(1);
    
15.    h2.add_Node_in_list(1);
    
16. 
    
17. 
    
18. 
    
19. 
    
20.    for(int i = 0;i < 1000;i++)
    
21.    {
    
22.        h1 += &h2;
    
23.        h2 += &h1;
    
24.        system("pause");
    
25.        cout<<i+1<<"-"<<h1.Tostring()<<i+2<<h2.Tostring()<<endl;
    
26. 
    
27. 
    
28.    }
    
29. 
    
30. 
    
31.     /*
    
32.     unsigned int nFibonacci[1000];
    
33.     nFibonacci[0] = 1;
    
34.     nFibonacci[1] = 1;
    
35.     cout<<"1."<<nFibonacci[0]<<endl;
    
36.     cout<<"2."<<nFibonacci[1]<<endl;
    
37.     for(int i = 2;i < 1000;i++)
    
38.     {
    
39.         nFibonacci[i] = nFibonacci[i-1]+nFibonacci[i-2];
    
40.         cout<<i+1<<"."<<nFibonacci[i]<<endl;
    
41.         getch();
    
42.     }
    
43.     */
    
44.     return 0;
    
45. }
    

复制代码

类的定义:

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.         hgNumNode* hgLast;//链表尾节点
    
23.         bool add_Node_in_list(unsigned int values);//添加一个新节点到链表中
    
24.         void cleanList();//清空链表
    
25.         void reset_self(unsigned int values);//清空链表并重设第一个节点的值
    
26.         void remove_zero_end();//删除值为0的节点
    
27.         void remove_zero_end(hgNumNode* parent);
    
28.         void operator +=(hugeNumber* afterNum);//重载+=
    
29.         string Tostring();
    
30.         string Tostring(hgNumNode* heads);
    
31. 
    
32.     protected:
    
33. 
    
34.     private:
    
35. };
    
36. 
    
37. #endif // HUGENUMBER_H

复制代码

类的实现:

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

复制代码

最佳答案

月排行榜 / 总排行榜

Croper

2019-4-23 12:34:37

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

1. void hugeNumber::reset_self(unsigned int tar)
   
2. {
   
3.     cleanList();
   
4.     hgNumNode* newNode= new hgNumNode(tar);
   
5.     this->hgHead = newNode;
   
6.     this->hgLast = newNode;
   
7.     this->length++;
   
8. }
   
9. void hugeNumber::remove_zero_end()
   
10. {
    
11.     if(this->hgHead == nullptr)
    
12.         return;
    
13.     remove_zero_end(this->hgHead);
    
14. 
    
15. }

复制代码

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

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

复制代码

还有

1. void hugeNumber::cleanList()
   
2. {
   
3.     hgNumNode* delNode = this->hgHead;
   
4.     while(delNode != nullptr)//不能再对象析构中调用delete删除相同对象,这样会导致无限调用析构的死循环递归
   
5.     {
   
6.          delete delNode;
   
7.          delNode = delNode->next;
   
8.     }
   
9.     this->length = 0;
   
10.     this->hgHead = nullptr;
    
11.     this->hgLast = nullptr;
    
12. 
    
13. 
    
14. }

复制代码

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

1. void hugeNumber::cleanList()
   
2. {
   
3.         hgNumNode* delNode = this->hgHead;
   
4.         while (delNode != nullptr)//不能再对象析构中调用delete删除相同对象,这样会导致无限调用析构的死循环递归
   
5.         {
   
6.                 hgNumNode* next = delNode->next;
   
7.                 delete delNode;
   
8.                 delNode = next;
   
9.         }
   
10.         this->length = 0;
    
11.         this->hgHead = nullptr;
    
12.         this->hgLast = nullptr;
    
13. 
    
14. 
    
15. }

复制代码

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

跳转到最佳答案楼层

Croper

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

1. void hugeNumber::reset_self(unsigned int tar)
   
2. {
   
3.     cleanList();
   
4.     hgNumNode* newNode= new hgNumNode(tar);
   
5.     this->hgHead = newNode;
   
6.     this->hgLast = newNode;
   
7.     this->length++;
   
8. }
   
9. void hugeNumber::remove_zero_end()
   
10. {
    
11.     if(this->hgHead == nullptr)
    
12.         return;
    
13.     remove_zero_end(this->hgHead);
    
14. 
    
15. }

复制代码

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

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

复制代码

还有

1. void hugeNumber::cleanList()
   
2. {
   
3.     hgNumNode* delNode = this->hgHead;
   
4.     while(delNode != nullptr)//不能再对象析构中调用delete删除相同对象,这样会导致无限调用析构的死循环递归
   
5.     {
   
6.          delete delNode;
   
7.          delNode = delNode->next;
   
8.     }
   
9.     this->length = 0;
   
10.     this->hgHead = nullptr;
    
11.     this->hgLast = nullptr;
    
12. 
    
13. 
    
14. }

复制代码

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

1. void hugeNumber::cleanList()
   
2. {
   
3.         hgNumNode* delNode = this->hgHead;
   
4.         while (delNode != nullptr)//不能再对象析构中调用delete删除相同对象,这样会导致无限调用析构的死循环递归
   
5.         {
   
6.                 hgNumNode* next = delNode->next;
   
7.                 delete delNode;
   
8.                 delNode = next;
   
9.         }
   
10.         this->length = 0;
    
11.         this->hgHead = nullptr;
    
12.         this->hgLast = nullptr;
    
13. 
    
14. 
    
15. }

复制代码

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

°希作先生丶

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

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

Croper

1. #ifndef HUGENUMBER_H
   
2. #define HUGENUMBER_H
   
3. #define max_num 0xffffffff
   
4. 
   
5. #include <iostream>
   
6. #include <sstream>
   
7. #include <iomanip>
   
8. 
   
9. class hugeNumber {
   
10. private:
    
11.         struct Node {
    
12.                 unsigned int val;
    
13.                 Node* pre;
    
14.                 Node* next;
    
15.                 Node(unsigned int val0=0) :pre(this), next(this), val(val0) {};
    
16. 
    
17.                 Node* insert_back(unsigned val0 = 0);
    
18.                 ~Node();
    
19.         };
    
20. 
    
21.         Node* _myhead;
    
22.         int _mysize;
    
23. 
    
24.         void remove_zero_end();
    
25.         bool SumOverflow(unsigned int num1, unsigned int num2, unsigned int a);
    
26. public:
    
27.         hugeNumber();
    
28.         hugeNumber(unsigned int val0);
    
29.         hugeNumber(const hugeNumber&);
    
30.         hugeNumber(hugeNumber&&);
    
31.         ~hugeNumber();
    
32. 
    
33.         int size() const;
    
34.         void clear();
    
35. 
    
36.         hugeNumber&  operator=(unsigned int val0);
    
37.         hugeNumber& operator+=(const hugeNumber& num1);
    
38. 
    
39.         std::string to_string() const;
    
40. };

复制代码

1. #include "hugeNumber.h"
   
2. 
   
3. inline hugeNumber::Node * hugeNumber::Node::insert_back(unsigned val0) {
   
4.         Node* tmp = next;
   
5.         next = new Node(val0);
   
6.         next->pre = this;
   
7.         next->next = tmp;
   
8.         if (tmp != nullptr) {
   
9.                 tmp->pre = next;
   
10.         }
    
11. 
    
12.         return next;
    
13. }
    
14. 
    
15. inline hugeNumber::Node::~Node() {
    
16.         if (pre != nullptr) pre->next = next;
    
17.         if (next != nullptr) next->pre = pre;
    
18. }
    
19. 
    
20. inline void hugeNumber::remove_zero_end() {
    
21.         while (_myhead->pre != _myhead && _myhead->pre->val == 0) {
    
22.                 delete _myhead->pre;
    
23.                 _mysize--;
    
24.         }
    
25. }
    
26. 
    
27. inline bool hugeNumber::SumOverflow(unsigned int num1, unsigned int num2, unsigned int a) {
    
28.         if (a > 1) {
    
29.                 std::cerr << "Error: illegal a";
    
30.                 return false;
    
31.         }
    
32. 
    
33.         if (a == 0) {
    
34.                 return max_num - num1 < num2;
    
35.         }
    
36. 
    
37.         if (num1 == max_num || num2 == max_num) return true;
    
38.         return max_num - num1 < num2 + 1;
    
39. }
    
40. 
    
41. inline hugeNumber::hugeNumber() {
    
42.         _myhead = new Node;
    
43.         _mysize = 0;
    
44. }
    
45. 
    
46. inline hugeNumber::hugeNumber(unsigned int val0) :hugeNumber() {
    
47.         if (val0 == 0) return;
    
48.         _myhead->insert_back(val0);
    
49.         _mysize = 1;
    
50. }
    
51. 
    
52. hugeNumber::hugeNumber(const hugeNumber & num0):hugeNumber()
    
53. {
    
54.         _mysize = num0._mysize;
    
55.         for (Node *p = num0._myhead->pre; p != num0._myhead; p = p->pre) {
    
56.                 _myhead->insert_back(p->val);
    
57.         }
    
58. }
    
59. 
    
60. hugeNumber::hugeNumber(hugeNumber && num0)
    
61. {
    
62.         auto tmp = _myhead;
    
63.         _myhead = num0._myhead;
    
64.         num0._myhead = tmp;
    
65. }
    
66. 
    
67. inline hugeNumber::~hugeNumber() {
    
68.         Node* p = _myhead->next;
    
69.         while (p != _myhead) {
    
70.                 Node* tmp = p->next;
    
71.                 delete p;
    
72.                 p = tmp;
    
73.         }
    
74.         delete _myhead;
    
75. }
    
76. 
    
77. inline int hugeNumber::size() const {
    
78.         return _mysize;
    
79. }
    
80. 
    
81. inline void hugeNumber::clear() {
    
82.         Node* p = _myhead->next;
    
83.         while (p != _myhead) {
    
84.                 Node* tmp = p->next;
    
85.                 delete p;
    
86.                 p = tmp;
    
87.         }
    
88.         _mysize = 0;
    
89. }
    
90. 
    
91. 
    
92. 
    
93. 
    
94. hugeNumber&  hugeNumber::operator=(unsigned int val0) {
    
95.         clear();
    
96.         if (val0 == 0) return *this;
    
97.         _myhead->insert_back(val0);
    
98.         _mysize = 1;
    
99.         return *this;
    
100. }
     
101. 
     
102. hugeNumber& hugeNumber::operator+=(const hugeNumber& num1) {
     
103.         unsigned int a = 0;
     
104.         Node* p1 = _myhead->next, *p2 = num1._myhead->next;
     
105.         while (p1 != _myhead || p2 != num1._myhead) {
     
106.                 int next_a = SumOverflow(p1->val, p2->val, a);
     
107.                 p1->val = p1->val + p2->val + a;
     
108.                 a = next_a;
     
109. 
     
110.                 p1 = p1->next;
     
111.                 if (p2 != num1._myhead) {
     
112.                         p2 = p2->next;
     
113.                         if (p2 != num1._myhead && p1 == _myhead) {
     
114.                                 p1 = _myhead->pre->insert_back(0);
     
115.                                 ++_mysize;
     
116.                         }
     
117.                 }
     
118.         }
     
119.         if (a != 0) {
     
120.                 _myhead->pre->insert_back(a);
     
121.                 ++_mysize;
     
122.         }
     
123. 
     
124.         return *this;
     
125. }
     
126. 
     
127. inline std::string hugeNumber::to_string() const {
     
128.         if (_mysize == 0) return "0x0(0)";
     
129.         if (_mysize >1) {
     
130.                 int a = 4;
     
131.         }
     
132.         std::stringstream hex, dec;
     
133.         hex << std::setbase(16) << std::setw(8) << std::setfill('0');
     
134.         Node* p = _myhead->pre;
     
135.         while (p != _myhead) {
     
136.                 hex << p->val;
     
137.                 dec << "-" << p->val;
     
138.                 p = p->pre;
     
139.         }
     
140.         std::string szhex = hex.str();
     
141.         while (szhex[0] == '0') {
     
142.                 szhex.erase(szhex.begin());
     
143.         }
     
144.         szhex = "0x" + szhex;
     
145. 
     
146.         std::string szdec = dec.str();
     
147.         szdec.erase(szdec.begin());
     
148. 
     
149.         return szhex + "(" + szdec + ")";
     
150. }
     

复制代码