- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
我有一个随机生成的测试程序,数据是随机生成的,然后将它们传递给类 Sorter 的类构造函数。然后Sorter会对数据进行排序,通过一个方法传回给main函数。我还实现了其他几种排序方法作为 Sorter 类的子类,它们工作得很好。所以我认为我的 Sorter 类没有问题。下面是我的测试程序在使用堆排序时的输出。
数据:
48 96 71 81 78 72 93 52 67 70
排序数据:
48 71 81 78 72 67 52 93 70 96
如您所见,经过以下代码后数据未排序。下面是代码。
public class HeapSort extends Sorter{
private int[] heap;
private int size;
public HeapSort(int[] data){
super(data);
}
public void sort(){
constructHeap();
for(int i = size - 1; i >= 0; i--){
numbers[i] = extractMax();
}
}
public void constructHeap(){
size = numbers.length;
heap = new int[size];
for(int j = 0; j < size; j++) heap[j] = numbers[j];
for(int i = size/2 - 1; i >= 0; i--){
fixHeap(i, heap[i]);
}
}
public int extractMax(){
int max = heap[0];
fixHeap(0, heap[--size]);
return max;
}
public void fixHeap(int pos, int key){
if(left(pos) > size) heap[pos] = key; // if current position is leaf
else{
int largest = pos;
int r = right(pos);
int l = left(pos);
if(r < size && heap[largest] < heap[r]) largest = r;
if(l < size && heap[largest] < heap[l]) largest = l;
if(largest == pos) heap[pos] = key;
else{
heap[pos] = heap[largest];
fixHeap(largest, key);
}
}
}
public int left(int i){return 2*i+1;}
public int right(int i){return 2*i+2;}
}
编辑:下面是调试后的代码。希望有人会觉得它有用。
public class HeapSort extends Sorter{
private int[] heap;
private int size;
public HeapSort(int[] data){
super(data);
}
public void sort(){
constructHeap();
for(int i = size - 1; i >= 0; i--){
numbers[i] = extractMax();
}
}
public void constructHeap(){
size = numbers.length;
heap = new int[size];
for(int j = 0; j < size; j++) heap[j] = numbers[j];
for(int i = size/2 - 1; i >= 0; i--){
fixHeap(i);
}
}
public int extractMax(){
int max = heap[0];
heap[0] = heap[--size];
fixHeap(0);
return max;
}
public void fixHeap(int pos){
if(left(pos) < size){ // if current position is not leaf
int largest = pos;
int r = right(pos);
int l = left(pos);
if(r < size && heap[largest] < heap[r]) largest = r;
if(l < size && heap[largest] < heap[l]) largest = l;
if(largest != pos){
exchange(pos, largest);
fixHeap(largest);
}
}
}
public int left(int i){return 2*i+1;}
public int right(int i){return 2*i+2;}
public void exchange(int a, int b){
int temp = heap[a];
heap[a] = heap[b];
heap[b] = temp;
}
}
最佳答案
我假设您有一个调试器,并且知道如何使用它。
在我看来,调试复杂代码的最佳方式就是我所说的“分而治之调试”。伪代码:
void debug(Time beforeTheBug, Time afterTheBug) {
do {
Time pivot = between(beforeTheBug, afterTheBug);
if (stateIsAsExceptedAt(pivot)) {
afterTheBug = pivot;
} else {
beforetheBug = pivot;
}
} while (amountOfCodeExecutedBetween(beforeTheBug, afterTheBug) is not trivial);
}
在你的例子中,我的第一个检查是输出。确实没有排序,所以bug在这个类。
我的下一个检查是在 constructHeap 之后是否满足堆不变量。当时heap
为[96, 48, 93, 81, 78, 72, 71, 52, 67, 70],所以不满足堆不变量(48不大于78) ,并且在构建堆期间出现错误。
查看 constructHeap() 没有发现有用的断点,因为第一个循环非常简单,而且不太可能出错,而第二个循环(调用 fixHeap)包含所有复杂性。
循环的第一次迭代没有发现任何改变,这是正确的,因为子树已经满足堆不变量。第二次迭代相同。
第三次迭代正确识别右 child 大于根,并交换两者。
第四次迭代发现没有任何变化,这是正确的。
所以它是包含问题的循环的最后一次迭代。两个 child 都比 parent 大。 fixHeap 正确地将较大的 child 移动到根中,并递归调用自身。该调用发现堆不变量得到满足,并返回。但返回后不满足不变量。
所以问题出在从检测堆不变性到返回的某个地方。检测检查:
if (r < size && heap[largest] < heap[r])
largest = r;
if (l < size && heap[largest] < heap[l])
largest = l;
其中 heap
是 [96, 96, 93, 81, 78, 72, 71, 52, 67, 70]。是的,96 大于 81 和 78。但实际上,heap[pos] == key
不应该吗?啊,这就是下一条语句的作用...
换句话说,我们在完成上一次更新之前检查堆不变量,然后完成该更新,这在这种情况下破坏了不变量......
关于java - 调试 HeapSort Java 代码,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19332634/
昨晚我因为这个问题脑子崩溃了。在确保没有来 self 的 eclipse 错误检查的明显错误之后,我开始调试我的程序。顺便说一下,我正在使用 Jre7。无论如何,每次我进入我的类调用(我们称之为“a”
(前言:我对 C/C++ 还很陌生,我真的不知道 native 代码中的调试实际上是如何工作的。) 一些消息来源说 gdb 和 lldb 可以调试 any program compiled to ma
我正在尝试从 Visual Studio 2012 外部调试 T4Scaffolding.Core Nuget 包。我使用的是安装了 Powershell 3.0 的 Powershell ISE,并
如何调试汇编代码?我在 Linux 上使用 gdb。我知道我可以看寄存器。有哪些调试汇编代码的方法? 最佳答案 您当然可以使用 breakpoints就像 C 或任何其他编译语言一样。 This ar
如何在每次通话时打印列表或 haskell 中的内容,例如: funct a list = funct (a + 1) (a : list) print list her
让我用我对 Makefiles 或 make 知之甚少的评论作为这个问题的前缀。 有一个非常大的项目,每晚自动构建。它以 Debug 和 Release 模式构建,Debug 用于 Valgrind
我正在创建一个计算每周工资的程序,那么任何加类工资都是该周正常工资的 1.5 倍。我的代码如下: #include int main() { double payrate; double h
我使用的是 Visual Studio 2010 Express Developer 版本。开发网站。我在我的 .aspx 页面中使用 JavaScript。 如何在 Javascript 中放置断点
我最近开始修补 Project Euler 问题,并尝试用 Javascript 解决它们。这样做我往往会产生许多无限循环,现在我想知道是否有比终止 Firefox 或 Chrome 中的选项卡更好的
有没有办法在程序执行期间生成一个交互式 python 控制台(最好是 iPython)而不暂停主程序并且能够检查和修改程序变量?类似于浏览器为 JavaScript 提供的功能。 我知道 pdb.se
我正在使用 FFmpeg @ Android 并希望能够进入 FFmpeg 代码(Eclipse + Seqouya),同时编译 FFmpeg 我使用 --disable-stripping --en
我从使用互操作调用 win32 api 函数的 .net 进程中得到一个异常。 我有一个调试器,我想查看 LastError 的值。 是否可以从 Visual Studio 调试器中查看 LastEr
我正在尝试通过 VBA 创建一个宏,以在 IE 的多个选项卡中打开一组指定的链接。目前我正在使用下面的代码,如果我试图打开 3 个或更少的选项卡,它大部分时间都可以工作。任何超过 3 的代码都会在“N
好的,这似乎是一个愚蠢的问题,因为 MonoDevelop 越来越成熟,所以我确定我只是想念它,但我环顾四周,所有关于这个主题的问题似乎都是关于远程调试或 Mac 上的调试。 我使用的是 Ubuntu
如何调试 Rscripts是从命令行运行的? 我目前正在使用 getopt传递命令行选项的包,当有错误时,我很难: 看看到底出了什么问题; 在 R 中交互式调试(因为脚本需要命令行选项。) 有没有人有
支持 PDF 和网络上的信息很少。我碰巧在博客中看到一篇文章,提到 $.write() 或 $.writeln() 将向 javascript 控制台写入一个字符串。相当有用。有谁知道这个 $ 对象是
PyCharm 1.5 中是否可以使用 Firefox 和 Chrome 支持的 JavaScript 调试? 如果是这样,它能否与 Python/Django 调试器一起有效运行? 如果没有,有没有
我确定这以前发生在人们身上,某些东西在 Debug模式下工作,你在发布时编译,但有些东西坏了。 这发生在我在嵌入式 XP 环境中工作时,我发现最好的方法确实是编写一个日志文件来确定它会出错的地方。 您
我目前正在为即将到来的项目评估 Flow3。 AOP 模式和依赖注入(inject)将非常适合我们的目的。 现在我想不通的是如何在 Controller Action 中调试一些结果。 public
最初,我有一个包含测试服务器的 Django 应用程序。要调试此设置,我只需添加 import pdb; pdb.set_trace()代码中的任何位置,并且有一个断点将我扔到终端中的交互式调试器中(
我是一名优秀的程序员,十分优秀!