对于类,我们被要求创建一个二进制搜索树。一个小问题是我们的帮助器函数不是标头类的一部分,因此,当我尝试使用创建的帮助器函数添加到树或遍历树时,总是会出现分段错误,或者错误输出。标头类的代码只是为节点创建结构类]
struct MovieNode{
int ranking;
string title;
int year;
float rating;
MovieNode* left = NULL;
MovieNode* right = NULL;
MovieNode(int rank, string t, int y, float r) {
title = t;
ranking = rank;
year = y;
rating = r;
}
};
源代码文件包含头文件中的所有类以及为帮助完成任务而创建的帮助器函数。
#include "MovieTree.hpp"
#include <iostream>
#include <string>
#include <fstream>
#include <sstream>
using namespace std;
// MovieNode: node struct that will be stored in the MovieTree BST
MovieTree::MovieTree() {
this -> root = NULL;
}
MovieTree::~MovieTree() {
// delete every node and then set the root to NULL
}
我个人不知道析构函数是如何工作的。我的总是遇到分割错误。
// helper function to printMovieInventory()
void inorderTraverse(MovieNode* node) {
inorderTraverse(node -> left);
cout << "Movie: " << node -> title << " " << node -> rating << endl;
inorderTraverse(node -> right);
}
void MovieTree::printMovieInventory() {
// using inorder traversal
if (root == NULL) {
cout << "Tree is Empty. Cannot print" << endl;
}
else if (root != NULL) {
inorderTraverse(root);
}
}
此功能用于顺序遍历以打印所有电影及其等级。实际发生的是分段错误。
// helper function to addMovieNode()
void insert(MovieNode* root, int ranking, string title, int year, float rating) {
if (root == NULL) {
root = new MovieNode(ranking, title, year, rating);
}
if (title < root -> title) {
insert(root -> left, ranking, title, year, rating);
}
else if (title > root -> title) {
insert(root -> right, ranking, title, year, rating);
}
}
void MovieTree::addMovieNode(int ranking, string title, int year, float rating) {
if (root == NULL) {
root = new MovieNode(ranking, title, year, rating);
}
else if (root != NULL) {
insert(root, ranking, title, year, rating);
}
}
此功能最让我感到困惑。我见过的大多数将新节点插入树中的函数都需要一个指向节点Node* node
的指针,然后再指向该节点的数据。因此,每当我运行此函数时,它只会插入第一个节点(根),然后将其他任何东西都插入树中。
// helper function to findMovie()
MovieNode* compare(string title, MovieNode* root) {
if (root == NULL) {
return NULL;
}
else {
if (title.compare(root -> title) < 0) {
compare(title, root -> left);
}
else if (title.compare(root -> title) > 0) {
compare(title, root -> right);
}
else if (title.compare(root -> title) == 0) {
return root;
}
}
}
void MovieTree::findMovie(string title) {
if (root == NULL) {
cout << "Movie not found." << endl;
}
else {
MovieNode* foundMovie = compare(title, root);
if (foundMovie == NULL) {
cout << "Movie not found." << endl;
}
else {
cout << "Movie Info:" << endl;
cout << "==================" << endl;
cout << "Ranking:" << foundMovie -> ranking << endl;
cout << "Title :" << foundMovie -> title << endl;
cout << "Year :" << foundMovie -> year << endl;
cout << "rating :" << foundMovie -> rating << endl;
}
}
}
此功能是比较电影的标题,然后遍历树以查找与其匹配的电影。如果不在树中,则返回找不到电影。这将继续在等级,年份和排名中输出奇怪的值。即使未找到电影,它也会为其输出一些随机值。
// helper functino to queryMovies()
void preorderTraverse(MovieNode* node, int rating, int year) {
if (node -> rating >= rating && node -> year < year) {
cout << node -> title << "(" << node -> year << ") " << node -> rating << endl;
}
else {
preorderTraverse(node -> left, rating, year);
preorderTraverse(node -> right, rating, year);
}
}
void MovieTree::queryMovies(float rating, int year) {
if (root == NULL) {
cout << "Tree is Empty. Cannot query Movies" << endl;
}
else if (root != NULL) {
cout << "Movies that came out after " << year << " with rating at least " << rating << endl;
preorderTraverse(root, rating, year);
}
}
此功能与findMovie()
相似,不同之处在于它比较年份和等级,然后打印出该年份之后发行的,且等级大于或等于该等级的所有电影。它的执行顺序没有特定的顺序,因此我使用预排序遍历了树。同时也会出现细分错误。
// helper function to averageRating()
int average(MovieNode* node, int sum) {
sum += node -> rating;
average(node -> left, sum);
average(node -> right, sum);
return sum;
}
void MovieTree::averageRating() {
if (root == NULL) {
cout << "Average rating:0.0" << endl;
}
else if (root != NULL) {
int avg = 0;
avg += average(root, avg);
cout << "Average rating:" << avg << endl;
}
}
顾名思义,此函数将所有额定值相加,然后除以要获得平均值的节点数。我仍在研究此错误,因此我知道其中充满了错误。
// helper function to printLevelNodes()
void getLevel(MovieNode* node, int level) {
if (node != NULL) {
if (level == 0) {
cout << "Movie: " << node -> title << " " << node -> rating << endl;
}
else if (level != 0) {
getLevel(node -> left, level - 1);
getLevel(node -> right, level - 1);
}
}
}
// helper function to printLevelNodes()
int maxLevel(MovieNode* node) {
if (node == NULL) {
return 0;
}
else {
int leftD = maxLevel(node -> left);
int rightD = maxLevel(node -> right);
if (leftD > rightD) {
return (leftD + 1);
}
else {
return (rightD + 1);
}
}
}
void MovieTree::printLevelNodes(int level) {
int max = maxLevel(root);
if (level <= max) {
getLevel(root, level);
}
}
很有趣,最后一个功能是唯一起作用的功能。这对我来说是没有意义的,因为我彼此之间对辅助函数进行了建模,但是其中一些似乎不起作用。即使它们不是头文件的一部分,有没有办法从帮助函数访问树?如果没有,那么一些助手功能如何工作,而其他助手功能没有工作?
在[[顺序功能中有一些愚蠢的错误,然后是插入功能。 :(在这里关注我:
此功能用于顺序遍历以打印所有电影及其等级。实际发生的是分段错误。
分割错误的原因是您正在检查左右部分
即使它包含NULL
。在哪里,当左侧部分确实存在时,您应该只检查左侧部分,右侧部分也应相同。 更改:void inorderTraverse(MovieNode* node) {
if(node -> left)
inorderTraverse(node -> left);
cout << "Movie: " << node -> title << " " << node -> rating << endl;
if(node -> right)
inorderTraverse(node -> right);
}
此功能最让我感到困惑。我见过的大多数将新节点插入树中的函数都需要一个指向节点Node * node的指针,然后再指向该节点的数据。因此,每当我运行此函数时,它只会插入第一个节点(根),然后将其他任何东西都插入树中。由于要在精确位置添加节点,因此必须首先转到该位置。然后,只有您可以添加节点[或在正确位置进行引用]。
更改:
MovieNode * insert(MovieNode* root, int ranking, string title, int year, float rating) { if (root == NULL) { return new MovieNode(ranking, title, year, rating); } if (title < root -> title) { root->left = insert(root -> left, ranking, title, year, rating); } else if (title > root -> title) { root-> right = insert(root -> right, ranking, title, year, rating); } return root; } void MovieTree::addMovieNode(int ranking, string title, int year, float rating) { if (root == NULL) { root = new MovieNode(ranking, title, year, rating); } else if (root != NULL) { root = insert(root, ranking, title, year, rating); } }
现在,希望一切都好!如果在任何地方卡住或输出错误,请在此处ping。