二叉搜索树析构函数:free() 无效指针
Binary search tree destructor: free() invalid pointer
对于我当前的编程任务,我必须构建一个二叉搜索树并使用它按字母顺序从文件中插入单词,以制作索引列表。程序完整并正确输出;该程序的主要部分运行良好。但是当程序完成并调用析构函数时,它会崩溃并显示 error in ./concordancebst : free(): invalid pointer
。我不知道问题出在哪里,我的析构函数看起来可以正常工作,在线查看代码似乎也应该可以正常工作。我可能可以通过使用 std::unique_ptr
来解决这个问题,但从程序的范围来看它似乎有点矫枉过正(从我们没有涵盖智能指针的意义上来说也是矫枉过正,我们在class 涉及动态内存已通过手动处理allocating/deallocating)。
BST.h
#ifndef BST_H
#define BST_H
#include <string>
class BST {
public:
BST() { root = nullptr; }
~BST();
void insert(const std::string word);
int getCount(const std::string word);
int length();
friend std::ostream& operator << (std::ostream &out_s, BST b);
private:
struct Node {
std::string word;
int count;
Node *left;
Node *right;
Node() { word = ""; count = 0; left = nullptr; right = nullptr;}
~Node();
};
Node *root;
void RInsert(Node* &t, std::string word);
int countNodes(Node *p);
void print(Node *p, std::ostream &out_s);
};
#endif
BST.cpp
#include "BST.h"
#include <string>
#include <iostream>
#include <iomanip>
BST::Node::~Node() {
delete left;
delete right;
}
BST::~BST() {
delete root;
}
int BST::countNodes(Node *p) {
if(p == nullptr)
return 0;
else
return countNodes(p->left) + countNodes(p->right) + 1;
}
int BST::getCount(const std::string word) {
Node *p = root;
while(true) {
if(p == nullptr)
return 0;
else if(word.compare(p->word) < 0)
p = p->left;
else if(word.compare(p->word) == 0)
return p->count;
else
p = p->right;
}
}
int BST::length() {
return countNodes(root);
}
void BST::RInsert(Node* &t, std::string word) {
if(t == nullptr) {
t = new Node;
t->word = word;
t->left = nullptr;
t->right = nullptr;
t->count++;
}
else if(word.compare(t->word) == 0)
t->count++;
else if(word.compare(t->word) < 0)
RInsert(t->left, word);
else //word.compare(t->word > 0)
RInsert(t->right, word);
}
void BST::insert(const std::string word) {
RInsert(root, word);
}
void BST::print(Node *p, std::ostream &out_s) {
if(p != nullptr) {
print(p->left, out_s);
out_s << std::setw(13) << p->word << std::setw(10) << p->count << std::endl;
print(p->right, out_s);
}
}
std::ostream &operator << (std::ostream &out_s, BST b) {
out_s << std::setw(13) << "Word" << std::setw(10) << "Count" << std::endl;
out_s << "---------------------------------------------" << std::endl;
b.print(b.root, out_s);
out_s << "---------------------------------------------" << std::endl;
out_s << "The file contains " << b.length() << " distinct words." << std::endl;
return out_s;
}
std::ostream &operator << (std::ostream &out_s, BST b)
Pass by value^. b is copied.
由于BST
没有拷贝构造函数,调用默认的拷贝构造函数,不进行深拷贝。 b
包含源 BST
指针的副本,当 b
在 return 上从函数中销毁时,它会占用源的所有 Node
陪它到坟墓。
修复是双重的:
最直接,按引用传递。
std::ostream &operator << (std::ostream &out_s, BST & b)
间接地,此代码违反了 Rule of Three。 BST
和 BST::Node
需要安全使用复制构造函数和赋值运算符。
编辑
一个最小的测试用例应该是这样的:
#include <iostream>
#include "BST.h"
int main()
{
BST t;
t.insert("A");
std::cout << t << std::endl;
return 0;
}
对于我当前的编程任务,我必须构建一个二叉搜索树并使用它按字母顺序从文件中插入单词,以制作索引列表。程序完整并正确输出;该程序的主要部分运行良好。但是当程序完成并调用析构函数时,它会崩溃并显示 error in ./concordancebst : free(): invalid pointer
。我不知道问题出在哪里,我的析构函数看起来可以正常工作,在线查看代码似乎也应该可以正常工作。我可能可以通过使用 std::unique_ptr
来解决这个问题,但从程序的范围来看它似乎有点矫枉过正(从我们没有涵盖智能指针的意义上来说也是矫枉过正,我们在class 涉及动态内存已通过手动处理allocating/deallocating)。
BST.h
#ifndef BST_H
#define BST_H
#include <string>
class BST {
public:
BST() { root = nullptr; }
~BST();
void insert(const std::string word);
int getCount(const std::string word);
int length();
friend std::ostream& operator << (std::ostream &out_s, BST b);
private:
struct Node {
std::string word;
int count;
Node *left;
Node *right;
Node() { word = ""; count = 0; left = nullptr; right = nullptr;}
~Node();
};
Node *root;
void RInsert(Node* &t, std::string word);
int countNodes(Node *p);
void print(Node *p, std::ostream &out_s);
};
#endif
BST.cpp
#include "BST.h"
#include <string>
#include <iostream>
#include <iomanip>
BST::Node::~Node() {
delete left;
delete right;
}
BST::~BST() {
delete root;
}
int BST::countNodes(Node *p) {
if(p == nullptr)
return 0;
else
return countNodes(p->left) + countNodes(p->right) + 1;
}
int BST::getCount(const std::string word) {
Node *p = root;
while(true) {
if(p == nullptr)
return 0;
else if(word.compare(p->word) < 0)
p = p->left;
else if(word.compare(p->word) == 0)
return p->count;
else
p = p->right;
}
}
int BST::length() {
return countNodes(root);
}
void BST::RInsert(Node* &t, std::string word) {
if(t == nullptr) {
t = new Node;
t->word = word;
t->left = nullptr;
t->right = nullptr;
t->count++;
}
else if(word.compare(t->word) == 0)
t->count++;
else if(word.compare(t->word) < 0)
RInsert(t->left, word);
else //word.compare(t->word > 0)
RInsert(t->right, word);
}
void BST::insert(const std::string word) {
RInsert(root, word);
}
void BST::print(Node *p, std::ostream &out_s) {
if(p != nullptr) {
print(p->left, out_s);
out_s << std::setw(13) << p->word << std::setw(10) << p->count << std::endl;
print(p->right, out_s);
}
}
std::ostream &operator << (std::ostream &out_s, BST b) {
out_s << std::setw(13) << "Word" << std::setw(10) << "Count" << std::endl;
out_s << "---------------------------------------------" << std::endl;
b.print(b.root, out_s);
out_s << "---------------------------------------------" << std::endl;
out_s << "The file contains " << b.length() << " distinct words." << std::endl;
return out_s;
}
std::ostream &operator << (std::ostream &out_s, BST b)
Pass by value^. b is copied.
由于BST
没有拷贝构造函数,调用默认的拷贝构造函数,不进行深拷贝。 b
包含源 BST
指针的副本,当 b
在 return 上从函数中销毁时,它会占用源的所有 Node
陪它到坟墓。
修复是双重的:
最直接,按引用传递。
std::ostream &operator << (std::ostream &out_s, BST & b)
间接地,此代码违反了 Rule of Three。 BST
和 BST::Node
需要安全使用复制构造函数和赋值运算符。
编辑
一个最小的测试用例应该是这样的:
#include <iostream>
#include "BST.h"
int main()
{
BST t;
t.insert("A");
std::cout << t << std::endl;
return 0;
}