- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我正在尝试使用 VS 2019 作为我的 IDE 来实现红黑树。它似乎在 VS 中工作,但是当我尝试使用其他任何东西编译和运行时,只要多次调用我的插入函数,就会导致段错误。 (我尝试过在线编译器并将其发送给 friend )我被卡住了,因为我不知道从哪里开始尝试修复我的错误。我听说 VS 以不同的方式处理动态内存,但我不太确定。
下面是我的旋转、BST 插入和插入功能。
#include <iostream>
#include <vector>
// default constructor
// creates empty tree, root is nullptr
class NodeT
{
public:
// public variables
double key;
double value;
NodeT* left;
NodeT* right;
NodeT* parent;
bool isBlack;
// constructors
NodeT()
{
key = 0;
value = 0;
left = nullptr;
right = nullptr;
parent = nullptr;
isBlack = false;
}
NodeT(double keyset, double valueset, bool isBlackset)
{
key = keyset;
value = valueset;
left = nullptr;
right = nullptr;
parent = nullptr;
isBlack = isBlackset;
}
};
class RedBlackTree
{
public:
// default constructor, sets all to null
RedBlackTree();
// insert
// inserts the first parameter key, and value second parameter into the tree
// returns true if done, false if there are duplicates, dont insert
bool insert(double insert_key, double insert_value);
public:
NodeT* root;
void leftrotate(NodeT* to_rotate);
void rightrotate(NodeT* to_rotate);
bool bstinsert(NodeT* insert);
};
RedBlackTree::RedBlackTree()
{
root = nullptr;
}
void RedBlackTree::leftrotate(NodeT* to_rotate)
{
NodeT* new_parent = nullptr;
new_parent = to_rotate->right;
to_rotate->right = new_parent->left;
if (new_parent->left != nullptr)
{
new_parent->left->parent = to_rotate;
}
new_parent->parent = to_rotate->parent;
if (to_rotate->parent == nullptr)
{
root = new_parent;
}
else if (to_rotate == to_rotate->parent->left)
{
to_rotate->parent->left = new_parent;
}
else
{
to_rotate->parent->right = new_parent;
}
new_parent->left = to_rotate;
to_rotate->parent = new_parent;
}
void RedBlackTree::rightrotate(NodeT* to_rotate)
{
NodeT* new_parent = to_rotate->left;
to_rotate->left = new_parent->right;
if (new_parent->right != nullptr)
{
new_parent->right->parent = to_rotate;
}
new_parent->parent = to_rotate->parent;
if (to_rotate->parent == nullptr)
{
root = new_parent;
}
else if (to_rotate == to_rotate->parent->right)
{
to_rotate->parent->right = new_parent;
}
else
{
to_rotate->parent->left = new_parent;
}
new_parent->right = to_rotate;
to_rotate->parent = new_parent;
}
bool RedBlackTree::bstinsert(NodeT* insert)
{
NodeT* parent = root;
NodeT* search = root;
if (root == nullptr)
{
root = insert;
}
else
{
while (search != nullptr)
{
parent = search;
if (insert->key < parent->key)
{
search = parent->left;
}
else if (insert->key > parent->key)
{
search = parent->right;
}
else
{
return false;
}
}
if (insert->key < parent->key)
{
parent->left = insert;
insert->parent = parent;
return true;
}
else if(insert->key > parent->key)
{
parent->right = insert;
insert->parent = parent;
return true;
}
else
{
return false;
}
}
}
bool RedBlackTree::insert(double insert_key, double insert_value)
{
NodeT* y = nullptr;
NodeT* x = new NodeT(insert_key, insert_value, false);
bool dupe = bstinsert(x);
if (dupe == false)
{
return false;
}
while (x != root && x->parent->isBlack == false)
{
if (x->parent == x->parent->parent->left)
{
y = x->parent->parent->right;
if (y == nullptr || y->isBlack == true)
{
if (x == x->parent->right)
{
x = x->parent;
leftrotate(x);
}
x->parent->isBlack = true;
x->parent->parent->isBlack = false;
rightrotate(x->parent->parent);
}
else if (y->isBlack == false)
{
x->parent->isBlack = true;
y->isBlack = true;
x->parent->parent->isBlack = false;
x = x->parent->parent;
}
}
else
{
y = x->parent->parent->left;
if (y == nullptr || y->isBlack == true)
{
if (x == x->parent->left)
{
x = x->parent;
rightrotate(x);
}
x->parent->isBlack = true;
x->parent->parent->isBlack = false;
leftrotate(x->parent->parent);
}
else if (y->isBlack == false)
{
x->parent->isBlack = true;
y->isBlack = true;
x->parent->parent->isBlack = false;
x = x->parent->parent;
}
}
}
root->isBlack = true;
return true;
}
在 main 中调用它会导致段错误,除非在 VS 中:
int main()
{
RedBlackTree test;
test.insert(47, 1);
test.insert(32, 2);
}
感谢您抽时间阅读。任何帮助表示赞赏。
最佳答案
至少有一个错误会导致未定义的行为:RedBlackTree::bstinsert
函数在应该返回 bool
时未能返回值.
为了验证这是错误,在 bstinsert
结束之前的一行可以放置函数来验证这是一个错误。
bool RedBlackTree::bstinsert(NodeT* insert)
{
NodeT* parent = root;
NodeT* search = root;
if (root == nullptr)
{
root = insert;
}
else
{
while (search != nullptr)
{
parent = search;
if (insert->key < parent->key)
{
search = parent->left;
}
else if (insert->key > parent->key)
{
search = parent->right;
}
else
{
return false;
}
}
if (insert->key < parent->key)
{
parent->left = insert;
insert->parent = parent;
return true;
}
else if (insert->key > parent->key)
{
parent->right = insert;
insert->parent = parent;
return true;
}
else
{
return false;
}
}
std::cout << "This is undefined behavior\n"; // <-- add this line
}
你会看到
std::cout
将遇到一行以确认您是从
bstinsert
返回的不返回值。
warning C4715: 'RedBlackTree::bstinsert': not all control paths return a value
您不应该忽略此警告。
关于c++ - 为什么这段代码适用于 VS 而不是 gcc/g++?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63068101/
我在我的 Xcode 项目目录中输入了以下内容: keytool -genkey -v -keystore release.keystore -alias mykey -keyalg RSA \
假设我有一个像这样的 DataFrame(或 Series): Value 0 0.5 1 0.8 2 -0.2 3 None 4 None 5 None
我正在对一个 Pandas 系列进行相对繁重的应用。有什么方法可以返回一些打印反馈,说明每次调用函数时在函数内部进行打印还有多远? 最佳答案 您可以使用跟踪器包装您的函数。以下两个示例,一个基于完成的
我有一个 DataFrame,其中一列包含列表作为单元格内容,如下所示: import pandas as pd df = pd.DataFrame({ 'col_lists': [[1, 2
我想使用 Pandas df.apply 但仅限于某些行 作为一个例子,我想做这样的事情,但我的实际问题有点复杂: import pandas as pd import math z = pd.Dat
我有以下 Pandas 数据框 id dist ds 0 0 0 0 5 1 0 0 7 2 0 0
这发生在我尝试使用 Gradle 构建时。由于字符串是对象,因此似乎没有理由发生此错误: No signature of method: java.util.HashMap.getOrDefault(
您好,有人可以解释为什么在 remaining() 函数中的 Backbone 示例应用程序 ( http://backbonejs.org/examples/todos/index.html ) 中
我有两个域类:用户 class User { String username String password String email Date dateCreated
问题陈述: 一个 pandas dataframe 列系列,same_group 需要根据两个现有列 row 和 col 的值从 bool 值创建。如果两个值在字典 memberships 中具有相似
apporable 报告以下错误: error: unknown type name 'MKMapItem'; did you mean 'MKMapView'? MKMapItem* destina
我有一个带有地址列的大型 DataFrame: data addr 0 0.617964 IN,Krishnagiri,635115 1 0.635428 IN,Chennai
我有一个列表list,里面有这样的项目 ElementA: Number=1, Version=1 ElementB: Number=1, Version=2 ElementC: Number=1,
我正在编译我的源代码,它只是在没有运行应用程序的情况下终止。这是我得到的日志: Build/android-armeabi-debug/com.app4u.portaldorugby/PortalDo
我正在尝试根据另一个单元格的值更改单元格值(颜色“红色”或“绿色”)。我运行以下命令: df.loc[0, 'Colour'] = df.loc[0, 'Count'].apply(lambda x:
我想弄清楚如何使用 StateT结合两个 State基于对我的 Scalaz state monad examples 的评论的状态转换器回答。 看来我已经很接近了,但是在尝试申请 sequence
如果我已经为它绑定(bind)了集合,我该如何添加 RibbonLibrary 默认的快速访问项容器。当我从 UI 添加快速访问工具项时,它会抛出 Operation is not valid whi
在我学习期间Typoclassopedia我遇到了这个证明,但我不确定我的证明是否正确。问题是: One might imagine a variant of the interchange law
我是一名优秀的程序员,十分优秀!