- 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/
我是 Mercurial 的新手,并且不知何故仍处于评估过程中,所以这四个概念对我来说有点困惑。有些被提到等同于 Git 的 Staging/Index 概念,有些甚至比 Git 的 Staging
关闭。这个问题需要更多focused .它目前不接受答案。 想改善这个问题吗?更新问题,使其仅关注一个问题 editing this post . 6 个月前关闭。 Improve this ques
任何人都可以给我详细信息吗? 例如? #ID 是属性、特性、选择器还是 anchor ? 默认属性和默认属性是不同的东西吗? 这些都是标签还是元素? 我们将对此说些什么 这个 ..... 还有这些
关闭。这个问题需要更多focused .它目前不接受答案。 想改进这个问题吗? 更新问题,使其只关注一个问题 editing this post . 关闭 8 年前。 Improve this qu
我有一个由 Javascript 填充的下拉列表。 在决定加载时显示的默认值时,我意识到以下属性显示的值完全相同: innerText innerHTML label text textContent
我可以知道每个 Exec 之间有什么区别吗? , ExecWait , ExecShell , nsExec::Exec , nsExec::ExecToLog, nsExec::ExecToStac
当您处于版本 1 和版本 2 之间时,您会如何维护您的软件? 从我的角度来看,“补丁”、“修补程序”、“维护版本”、“服务包”等术语都很模糊,根据与您交谈的对象不同,定义也不同。 您如何称呼版本之间的
我刚刚发现在 ES6 中有一个新的数学方法:Math.trunc . 我在 MDN article 中阅读了它的描述。 , 听起来像使用 |0 . 此外,>0 , &-1 , ^0也做类似的事情(感谢
我想知道我的 StackPanel 所有项目的高度。 有什么区别: Height - 获取或设置元素的建议高度。 ActualHeight - 获取该元素的渲染高度。 (只读) ExtentHeigh
关闭。这个问题是off-topic .它目前不接受答案。 想改进这个问题吗? Update the question所以它是on-topic用于堆栈溢出。 关闭 9 年前。 Improve this
我对所有声称以某种方式阻止计算的内置 Mathematica 函数感到困惑:Unevaluated、Defer、Hold ,以及超过 6 个 Hold* 形式。 Mathematica 文档只是单独解
我什至不确定正确的术语,所以让我从我的目标开始:拥有一个简单的应用程序(“Data Doler”),它只会将大量数据从文件读取到内存中,然后提供服务将该数据切片到名为“Data Lapper”的单个多
我刚刚开始在我的项目中使用 Elasticsearch,我想像 sql 关键字一样搜索 '喜欢%' 做。 谁能解释一下 之间的区别通配符 , 前缀 , 查询字符串和 正则表达式 ? 哪个可以搜索最好性
由于我对任何主流浏览器(Firefox、Chrome、Opera)都不太满意,而且我尝试过的不太受欢迎的浏览器(近十几种)都没有,所以我决定 DIY 并制作一个网页我想要最好的浏览器。 主要目标是让它
我知道如何使用 Python 解析页面。我的问题是哪种方法是所有解析技术中最快的,其他方法的速度有多快? 我知道的解析技术有Xpath、DOM、BeautifulSoup,还有使用Python的fin
我试图从正在解析的命令行中找出哪个函数最适合将十进制、十六进制或八进制数转换为 int 最好——在不知道输入的情况下事先。 目标是使用一个函数来识别不同类型的输入并将其分配给它的整数 (int) 值,
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用资料或专业知识的支持,但这个问题可能会引发辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the
我们需要在我们的网站上显示酒吧、餐馆和剧院等各种场所的元信息(例如,地址、姓名)。 理想情况下,用户会输入地点名称以及邮政编码,我们会提供最接近的匹配项。 人们将哪些 API 用于类似的地理定位目的?
就目前而言,这个问题不适合我们的问答形式。我们希望答案得到事实、引用或专业知识的支持,但这个问题可能会引起辩论、争论、投票或扩展讨论。如果您觉得这个问题可以改进并可能重新打开,visit the he
我正在创建我的第一个 Web 应用程序,我真的很困惑应该使用什么技术。 我的应用程序需要看起来很严肃(像一个应用程序),它不需要很多色彩缤纷的图形界面。它只需要一个工具栏、一个标签栏、一个拆分面板(最
我是一名优秀的程序员,十分优秀!