c++ - 在二叉搜索树上没有得到输出，有什么方法可以帮助我找到我在 C++ 中的错误吗？
问题描述
我的地图.h
////////////
/* This is your h file. DO NOT edit it!
*
* TODO 1: implement the MyMap-related functions in MyMap.hpp
* TODO 2: implement the get_letter_frequency() functionin MyMap.hpp
* TODO 3: implement the get_identity function in MyMap.hpp
* TODO 4: thoroughly test your MyMap class to ensure proper functional
behaviors
*/
#ifndef MYMAP_H
#define MYMAP_H
#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include "Dictionary.h"
#include "TreeNode.h"
using std::cout;
using std::endl;
using std::cerr;
using std::cin;
/*
* Same as before
*/
void get_identity(std::string &my_id);
template <typename K, typename V>
class MyMap: public Dictionary<K, V>
{
private:
TreeNode<MyPair<K, V>> *root = nullptr;
V & at_helper(TreeNode<MyPair<K, V>> *&rt, const K &key);
int size_helper(TreeNode<MyPair<K, V>> *rt) const;
void clear_helper(TreeNode<MyPair<K, V>> *&rt);
void insert_helper(TreeNode<MyPair<K, V>> *&rt,
const MyPair<K, V> &init_pair);
TreeNode<MyPair<K, V>> * get_min(TreeNode<MyPair<K, V>> *rt);
void erase_helper(TreeNode<MyPair<K, V>> *&rt, const K &key);
MyPair<K, V> * find_helper(TreeNode<MyPair<K, V>> *rt,
const K &key) const;
void print_helper(TreeNode<MyPair<K, V>> *rt, std::string indent) const;
int count_helper(TreeNode<MyPair<K, V>> *rt, const K &key) const;
// This is a helper function for the copy constructor and operator=
// It should recursively clone the whole tree, by using new to make a
// new tree node, whose left and right children are clones of the left
// and right children...
// Take inspiration from the recursive "count" function presented in
// class for counting the number of nodes in a binary tree
TreeNode<MyPair<K, V>> * clone(const TreeNode<MyPair<K, V>> *rt);
public:
MyMap();
~MyMap();
MyMap(const MyMap<K, V> &source);
MyMap<K, V> & operator=(const MyMap<K, V> &source);
V & at(const K &key);
V & operator[](const K &key);
bool empty() const;
int size() const;
void clear();
void insert(const MyPair<K, V> &init_pair);
void erase(const K &key);
MyPair<K, V> * find(const K &key) const;
void print() const;
int count(const K &key) const;
};
// Should accept a text file (for example a book) via std in (standard input),
// for example: ./yourprogram < sample_input.txt
// Should build a dictionary of the counts of the characters in that file
// Do not add newlines (\n) to the dictionary (they'll mess up print, so ignore
// them)
void get_letter_frequency(MyMap<char, int> &in_tree);
#include "MyMap.hpp"
#endif
我的地图.hpp
/* Define all your MyMap-related functions here, including the get_identity
function
* You do not need to include MyMap.h in this hpp header file. It includes
this file at the bottom.
*/
using namespace std;
void get_identity(std::string &my_id)
{
my_id = "tjb994";
}
template <typename K, typename V>
MyMap<K, V>::MyMap(){
TreeNode<MyPair<K, V>> *root = nullptr;
}
template <typename K, typename V>
MyMap<K, V>::~MyMap(){
clear_helper(root);
}
template <typename K, typename V>
MyMap<K, V>::MyMap(const MyMap<K, V> &source){
if(source.root == NULL)
{
this->root = NULL;
}
else{
this->root = clone(source.root);
}
}
template <typename K, typename V>
MyMap<K, V> & MyMap<K, V>::operator=(const MyMap<K, V> &source){
clear();
if(source.root == NULL)
{
this->root = NULL;
}
else{
this->root = clone(source.root);
}
return *this;
}
template <typename K, typename V>
V & MyMap<K, V>::at(const K &key){
return at_helper(root, key);
}
template <typename K, typename V>
V & MyMap<K, V>::operator[](const K &key){
if(find_helper(root, key) == NULL)
{
MyPair<K, V> tempnode(key);
insert_helper(root, tempnode);
return at_helper(root, key);
}
else
{
return at_helper(root, key);
}
}
template <typename K, typename V>
bool MyMap<K, V>::empty() const{
if(size_helper(root) != 0)
{
return false;
}
else
{
return true;
}
}
template <typename K, typename V>
int MyMap<K, V>::size() const{
return size_helper(root);
}
template <typename K, typename V>
void MyMap<K, V>::clear(){
clear_helper(root);
root = NULL;
}
template <typename K, typename V>
void MyMap<K, V>::insert(const MyPair<K, V> &init_pair){
insert_helper(root, init_pair);
}
template <typename K, typename V>
void MyMap<K, V>::erase(const K &key){
erase_helper(root, key);
}
template <typename K, typename V>
MyPair<K, V> * MyMap<K, V>::find(const K &key) const{
MyPair<K, V> *tempPair = find_helper(root, key);
if(tempPair != NULL){
return tempPair;
}
else{
throw std::out_of_range ("MyMap:at");
}
}
template <typename K, typename V>
void MyMap<K, V>::print() const{
print_helper(root, " ");
}
template <typename K, typename V>
int MyMap<K, V>::count(const K &key) const{
return count_helper(root, key);
}
template <typename K, typename V>
V & MyMap<K, V>::at_helper(TreeNode<MyPair<K, V>> *&rt, const K &key)
{
if(key < rt->data.first)
{
return at_helper(rt->left, key);
}
else if(key > rt->data.first){
return at_helper(rt->right, key);
}
else if(key == rt->data.first)
{
return rt->data.second;
}
else
{
throw std::out_of_range ("MyMap:a");
}
}
template <typename K, typename V>
int MyMap<K, V>::size_helper(TreeNode<MyPair<K, V>> *rt) const
{
static int size = 0;
//Count the number of elements. I chose to do this as a post order traversal
if(rt == NULL)
return 0;
size += size_helper(rt->left);
size += size_helper(rt->right);
size++;
return size;
}
template <typename K, typename V>
void MyMap<K, V>::clear_helper(TreeNode<MyPair<K, V>> *&rt)
{
//Traverse the tree and delete the nodes post order.
if(rt == NULL){
return;
}
clear_helper(rt->left);
clear_helper(rt->right);
delete rt;
}
template <typename K, typename V>
void MyMap<K, V>::insert_helper(TreeNode<MyPair<K, V>> *&rt, const MyPair<K, V> &init_pair)
{
if(rt == NULL)
{
rt = new TreeNode<MyPair<K,V>>(init_pair,NULL,NULL);
}
else if (rt->data.first > init_pair.first)
{
insert_helper(rt->left,init_pair);
}
else
{
insert_helper(rt->right,init_pair);
}
}
template <typename K, typename V>
TreeNode<MyPair<K, V>> * MyMap<K, V>::get_min(TreeNode<MyPair<K, V>> *rt)
{
if(rt->left == NULL)
{
return rt;
}
else{
return get_min(rt->left);
}
}
template <typename K, typename V>
void MyMap<K, V>::erase_helper(TreeNode<MyPair<K, V>> *&rt, const K &key)
{
if(rt == NULL)
{
return;
}
if(key < rt->data.first)
{
erase_helper(rt->left, key);
}
else if(key > rt->data.first)
{
erase_helper(rt->right, key);
}
else{
TreeNode<MyPair<K, V>> *temp_1 = rt;
if(rt->left == NULL)
{
rt = rt->right;
}
else if(rt->right == NULL)
{
rt = rt->left;
}
else{
TreeNode<MyPair<K, V>> *temp_2 = get_min(rt->right);
rt->data.first = temp_2->data.first;
rt->data.second = temp_2->data.second;
//Find the minimum and keep note of it's parent node
TreeNode<MyPair<K, V>> *iter = rt->right;
while(iter->left!= NULL){
if(iter->left->left != NULL){
iter = iter->left;
}
}
if(rt->right == iter)
{
rt->right = iter->right;
}
else{
if(temp_2->right != NULL)
{
iter->left = temp_2->right;
}
}
delete temp_2;
}
delete temp_1;
}
}
template <typename K, typename V>
MyPair<K, V> * MyMap<K, V>::find_helper(TreeNode<MyPair<K, V>> *rt, const K &key) const
{
if(rt == NULL)
{
return NULL;
}
if(key < rt->data.first)
{
return find_helper(rt->left, key);
}
else if(key > rt->data.first)
{
return find_helper(rt->right, key);
}
else
{
return &(rt->data);
}
}
template <typename K, typename V>
void MyMap<K, V>::print_helper(TreeNode<MyPair<K, V>> *rt, std::string indent) const
{
if(rt == NULL)
{
cout << indent << "[empty]" << endl;
return;
}
else
{
print_helper(rt->right, indent);
cout << rt->data.first << rt->data.second << endl;
print_helper(rt->left, indent);
}
}
template <typename K, typename V>
int MyMap<K, V>::count_helper(TreeNode<MyPair<K, V>> *rt, const K &key) const
{
if(rt == NULL)
return 0;
if(key < rt->data.first)
{
return count_helper(rt->left, key);
}
else if(key > rt->data.first)
{
return count_helper(rt->right, key);
}
else
{
return 1;
}
}
template <typename K, typename V>
TreeNode<MyPair<K, V>> * MyMap<K, V>::clone(const TreeNode<MyPair<K, V>> *rt)
{
if(rt == NULL){
return NULL;
}
MyPair<K, V> tempPair(rt->data.first, rt->data.second);
TreeNode<MyPair<K, V>> * thisNode = new TreeNode<MyPair<K, V>>(tempPair, clone(rt->left), clone(rt->right));
return thisNode;
}
//
//template <typename K, typename V>
//void get_letter_frequency(MyMap<char, int> &in_tree)
//{
// std::string letter;
// getline(cin, letter);
//
//
//
//}
主程序：
#include "MyMap.h"
int main()
{
MyMap<int, std::string> map_obj;
map_obj.insert(MyPair<int, std::string>(3, "h"));
map_obj[54].push_back('w');
map_obj[34] = "x";
map_obj[54] = "x";
map_obj[154] = "p";
map_obj[73] = "w";
map_obj[5] = "a";
map_obj[36] = "x";
map_obj[32] = "x";
map_obj[84] = "x";
map_obj.at(34) = "y";
const MyPair<int, std::string> *temp = map_obj.find(34);
cout << temp->first << " " << temp->second << endl;
map_obj.erase(34);
cout << (map_obj.find(34) == nullptr) << endl;
MyMap<int, std::string> map_obj2(map_obj);
MyMap<int, std::string> map_obj3;
map_obj3 = map_obj2 = map_obj;
cout << "==== printing tree ====" << endl;
map_obj2.print();
cout << "==== done printing tree ====" << endl;
cout << "Size is: " << map_obj2.size() << endl;
cout << "Count for 32 is: " << map_obj2.count(32) << endl << endl;
map_obj.clear();
cout << "==== printing tree ====" << endl;
map_obj.print();
cout << "==== done printing tree ====" << endl;
cout << "Size is: " << map_obj.size() << endl;
cout << "Count for 57 is: " << map_obj.count(57) << endl;
try
{
map_obj.at(34) = "k";
}
catch(const std::out_of_range &e)
{
cout << e.what();
}
//MyMap<char, int> new_tree;
//get_letter_frequency(new_tree); (commented out until function is complete)
// new_tree.print();
return 0;
}
字典.h
/* Abstract dictionary class to inherit when implementing your BST MyMap class
* It uses the TreeNode class to contain a MyPair object as its data element
* DO NOT edit this file.
*/
#ifndef DICTIONARY_H
#define DICTIONARY_H
#include "MyPair.h"
template <typename K, typename V>
class Dictionary
{
public:
// Should only update, but NOT insert
// Should throw std::out_of_range exception
virtual V & at(const K &key) = 0;
// Updates or inserts
virtual V & operator[](const K &key) = 0;
virtual bool empty() const = 0;
virtual int size() const = 0;
virtual void clear() = 0;
virtual void insert(const MyPair<K, V> &init_pair) = 0;
// Removes by key
virtual void erase(const K &key) = 0;
// Not exactly like the std:: version, but similar.
virtual MyPair<K, V> * find(const K &key) const = 0;
// Not actually like the std:: version; backwards in order traversal
// print
// See the print function example in class presentation
virtual void print() const = 0;
virtual int count(const K &key) const = 0;
};
#endif
我的配对.h
/* Declaration of MyPair, which resembles std::pair
* Use this as the element to store in your TreeNode.
* DO NOT edit this file.
* After this assignment (e.g., pa07 and beyond) you can use std::pair
* https://en.cppreference.com/w/cpp/utility/pair
*/
#ifndef MYPAIR_H
#define MYPAIR_H
template <typename K, typename V>
struct MyPair
{
K first;
V second;
MyPair(){}
MyPair(const K &key): first(key) {}
MyPair(const K &key, const V &value): first(key), second(value) {}
};
#endif
树节点.h
/* Use it as the node in the BST MyMap
* DO NOT edit this file.
*/
#ifndef TREENODE_H
#define TREENODE_H
template <typename T>
struct TreeNode
{
T data;
TreeNode *left;
TreeNode *right;
TreeNode(const T &x, TreeNode *lc, TreeNode *rc):data(x), left(lc),
right(rc) {}
};
#endif
在我的主程序中，它会一直运行，直到出现 insert() 函数，然后它不再给出输出，只有黑屏，返回值为 3359359859，这表明我在 MyMap.hpp 中定义的函数之一出错. 几天来我一直在寻找错误，但我无法确定出了什么问题。有人能指出我正确的方向吗？我假设一个构造函数，operator[]，或者我的 operator=( 函数中的错误可能是可能的。
解决方案
推荐阅读
- python - 不可腌制的并行作业库
- javascript - 捕获是否选择了文本
- mysql - 无法在 openshift 4 online realse 上安装 mysql
- postgresql - 无法将应用程序连接到运行 postgresql 的 IIS 服务器
- ssh - Terraform/GCP：未将 ssh 密钥添加到元数据中
- xamarin.android - 在从 App Center 导出的 Application Insights 中查看 Android 活动之间的转换
- c# - 使用 NewtonSoft 反序列化 JSON
- c# - 为什么数据绑定在 UserControl 上不起作用？
- linux - 如何解决此无法在 Linux 中运行的 Codeigniter 3 中查看登录页面的问题
- magento - Magento 1 仪表板聊天在升级到 1.9.4.1 后不起作用