GeezerVisonThe World Wide Web, restored to 800 pixels of glory. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Home|About|Gaming cabinet|Archives|How it works|Starter sites | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
GeezerVison is showing github.com — finished all algorithms by MatterMu · Pull Request #4 · algorithm-visualizer/tracers.cpp ConversationThere was a problem hiding this comment. Choose a reason for hiding this commentThe reason will be displayed to describe this comment to others. Learn more. Pull request overview该 PR 主要新增/补齐了一系列“数据结构与算法”的可视化示例代码与对应的可视化输出 JSON,用于测试/演示 Graphite 的代码审查能力,并集中加入了 KMP、Prim、Kruskal、DFS/BFS、二叉树遍历、堆操作等可视化实现。 Changes:
Reviewed changesCopilot reviewed 35 out of 54 changed files in this pull request and generated 8 comments. Show a summary per file
💡 Add Copilot custom instructions for smarter, more guided reviews. Learn how to get started.
Sorry, something went wrong. Uh oh!
There was an error while loading. Please reload this page. All reactions
Comment on lines
+155
to
+160
|
| if (j == 0 || S[i] == T[j]) | |
| { | |
| ++i; | |
| ++j; | |
| // 可视化 | |
| if (j == 1) | |
| if (j == -1 || S[i] == T[j]) | |
| { | |
| ++i; | |
| ++j; | |
| // 可视化 | |
| if (j == 0) |
Sorry, something went wrong.
There was an error while loading. Please reload this page.
| } else { | ||
| // 可视化:说明回退到 Next[k] | ||
| logger.println(std::string("不匹配,k 从 ") + std::to_string(k) + " 回退到 Next[k] = " + std::to_string(Next[k])); | ||
| k = Next[k]; | ||
| pattern_tracer.select(0, k-1); | ||
| Tracer::delay(); | ||
| pattern_tracer.deselect(2, k); | ||
| pattern_tracer.select(2, Next[k-1]); | ||
| Tracer::delay(); | ||
| pattern_tracer.deselect(0, k-1); | ||
| Tracer::delay(); |
There was a problem hiding this comment.
The reason will be displayed to describe this comment to others. Learn more.
GetNext 的回退分支里先执行 k = Next[k],随后又使用 k-1 / Next[k-1] 做 tracer 高亮与索引访问(并且 k 可能变成 -1)。这会导致数组越界(如 Next[-1]/Next[-2])以及 tracer 负下标。建议用回退前的 k 做可视化索引,并在 k == -1 时跳过所有基于 k 的 select/deselect;同时不要混用 Next[k] 与 Next[k-1]。
Sorry, something went wrong.
There was an error while loading. Please reload this page.
| while (i < lenS && j < lenT) { | ||
| // 可视化:选中当前比较位置(主串与模式) | ||
| string_tracer.select(i); | ||
| pattern_tracer.select(1, j); | ||
| Tracer::delay(); |
There was a problem hiding this comment.
The reason will be displayed to describe this comment to others. Learn more.
匹配循环里每次都 pattern_tracer.select(1, j),但 j 可能在失配回退后变为 -1(newj = Next[j]),下一轮迭代会对 tracer 传入 -1 下标导致越界。建议把 select/deselect 放到 j >= 0 的分支内,或在 j == -1 时仅移动 i/j 而不进行 pattern 行选择。
Sorry, something went wrong.
There was an error while loading. Please reload this page.
| while (i < lenS && j < lenT) { | ||
| // 高亮主串与模式当前比较位置 | ||
| string_tracer.select(i); | ||
| pattern_tracer.select(1, j); | ||
| Tracer::delay(); |
There was a problem hiding this comment.
The reason will be displayed to describe this comment to others. Learn more.
while (i < lenS && j < lenT) 内部无条件 pattern_tracer.select(1, j),但 j 在失配时会被赋值为 Next[j],可能变为 -1,从而触发 tracer 负下标访问。建议在调用 select(1, j) 前先判断 j >= 0,或在 j == -1 的情况下跳过对 pattern_tracer 的索引操作。
Sorry, something went wrong.
There was an error while loading. Please reload this page.
| // 将 const away for our function signatures | ||
| char* Sbuf = const_cast<char*>(S); | ||
| char* Tbuf = const_cast<char*>(T); | ||
|
|
There was a problem hiding this comment.
The reason will be displayed to describe this comment to others. Learn more.
这里通过 const_cast 把 const char[] 转成 char* 传入函数。当前实现虽然没有修改内容,但这种签名会让调用者必须去掉 const,容易引入未定义行为。建议把 GetNext / StrMatch_KMP 的参数改为 const char*(或直接用 std::string_view/std::string)。
Sorry, something went wrong.
There was an error while loading. Please reload this page.
| if (!HeapFull(heap)) | ||
| { | ||
| i = heap.n; | ||
| int parentidx = (i - 1) / 2; | ||
| heap.n++; | ||
| heapGraph.addNode(elem); | ||
| heapGraph.addEdge(heap.data[parentidx], elem); | ||
| heapGraph.addEdge(elem, heap.data[parentidx]); | ||
| heapTracer.patch(i, elem); // 先放在最后 | ||
| heapGraph.visit(elem); | ||
| Tracer::delay(); | ||
| logger.println("将元素 " + std::to_string(elem) + " 放在堆的末尾位置,开始上浮"); | ||
| Tracer::delay(); | ||
| heapGraph.leave(elem); | ||
| heapTracer.depatch(i); | ||
| heapGraph.select(heap.data[parentidx]); | ||
| heapTracer.select(parentidx); | ||
| Tracer::delay(); | ||
| heapTracer.depatch(i); | ||
| while ((i != 0) && (elem > heap.data[parentidx])) | ||
| { | ||
| logger.println("堆中元素 " + std::to_string(heap.data[parentidx]) + " 小于插入元素 " + std::to_string(elem) + ",进行下推"); | ||
| heap.data[i] = heap.data[parentidx]; // 下推 | ||
| heap.data[parentidx] = elem; // 上浮 | ||
| // 可视化:修改堆树结构 |
There was a problem hiding this comment.
The reason will be displayed to describe this comment to others. Learn more.
Insert 在 heap.n++ 后没有把 elem 写入 heap.data[i](仅做了 tracer patch),而 while 循环只在 elem > parent 时才执行。如果 elem <= parent,循环不进入就直接返回,堆数组里不会出现新元素但 heap.n 已增加,导致堆状态损坏。建议先执行 heap.data[i] = elem(或按标准上浮写法:先保存 elem,循环中下推父节点,最后把 elem 放到最终位置)。
Sorry, something went wrong.
There was an error while loading. Please reload this page.
| std::vector<int> data; // 1-based: data[0] unused | ||
| int n; | ||
| int capacity; | ||
| HEAP(int cap = 32) : data(cap + 1, 0), n(0), capacity(cap) {} |
There was a problem hiding this comment.
The reason will be displayed to describe this comment to others. Learn more.
HEAP::data 注释写的是 “1-based: data[0] unused”,但整个实现(包括 layoutTree(heap.data[0])、父节点计算 (i-1)/2 等)都是 0-based。注释与实现不一致会误导后续维护/复用,建议统一为 0-based 并更新注释,或真正改成 1-based 并相应调整父子索引公式。
| std::vector<int> data; // 1-based: data[0] unused | |
| int n; | |
| int capacity; | |
| HEAP(int cap = 32) : data(cap + 1, 0), n(0), capacity(cap) {} | |
| std::vector<int> data; // 0-based: data[0..n-1] 存储堆元素 | |
| int n; | |
| int capacity; | |
| HEAP(int cap = 32) : data(cap, 0), n(0), capacity(cap) {} |
Sorry, something went wrong.
There was an error while loading. Please reload this page.
| heapGraph.addEdge(heap.data[right], heap.data[i]); | ||
| } | ||
| } | ||
| heapGraph.layoutTree(heap.data[0]); |
There was a problem hiding this comment.
The reason will be displayed to describe this comment to others. Learn more.
updateHeapGraph 无条件调用 heapGraph.layoutTree(heap.data[0])。当 heap.n == 0(例如 DeleteMax 删除到空堆后调用 update),这里会在图中没有节点时尝试用 root id 布局,且访问 heap.data[0],容易导致运行时错误。建议在函数开头对 n == 0 直接 return,或在调用 layoutTree 前确认已添加至少一个节点。
| heapGraph.layoutTree(heap.data[0]); | |
| if (n > 0) | |
| { | |
| heapGraph.layoutTree(heap.data[0]); | |
| } |
Sorry, something went wrong.
There was an error while loading. Please reload this page.
There was an error while loading. Please reload this page.
Successfully merging this pull request may close these issues.
There was an error while loading. Please reload this page.