相关疑难解决方法(0)

假设我们有两个堆栈而没有其他临时变量.

是否可以仅使用两个堆栈"构造"队列数据结构？

我正在寻找C/CPP中工作窃取队列的正确实现.我环顾了谷歌,但没有找到任何有用的东西.

也许有人熟悉一个好的开源实现？(我不想实施原始学术论文中的伪代码).

您能对现代数据结构有什么看法？我们都知道经典的,比如树木,尝试,堆叠,列表,B树等等(我认为Cormen的书是一本非常好的"经典之书").但是最近的研究呢？我可以至少命名其中两个:手指树和朱迪阵列.我想知道更多.

与此问题相关,基于用户Eric Lippert的评论.

是否有任何情况下Rope数据结构比字符串生成器更有效？有些人认为绳索数据结构在速度方面几乎从不比典型情况下的本地字符串或字符串构建器操作更好,所以我很想看到确实绳索更好的真实场景.

这是一个衍生问题,但我正在询问您至少应该熟悉它们的实用性的数据结构.如果没有一些专业知识,这些结构太难实现.

我会说两者之间的良好界限是堆 - 你应该能够编写一个堆,但它需要你一天.不合适的是BST等.编辑:我认为这取决于你在做什么.我认为列出一个包含总结您使用它的原因的短语会很棒!

这是一个开始的列表:

1. B +树:单个键上的一般索引结构很好
2. Kd树:空间数据
3. 红黑树:自平衡BST; 还有AVL或splay树
4. 跳过列表:用于随机或(伪)顺序访问的良好混合结构
5. Trie:线性时间字符串搜索

Fibonacci堆在实践中用于任何地方吗？我环顾四周,找到了相关问题的答案(见下文),但实际上并没有回答这个问题.

1. Fibonacci有很好的实现,包括标准库,如Boost C++.这些库包含Fibonacci堆的事实表明它们必须在某个地方有用.
2. 我们知道Fibonacci堆在实践中需要满足某些条件:" 要在实践中受益于Fibonacci堆,你必须在reduce_keys非常频繁的应用程序中使用它们 "; " 为了使Fibonacci Heap真正发光,您需要以下两种情况之一:a)昂贵的比较:Fib Heaps最小化组织数据所需的比较次数.b)大多数操作是updateKey/insert/delete.作为Fibonacci堆叠将这些更新"组合"到下一个extractMin,"批次"越大,它获得的效率就越高. "
3. 有一个称为"Brodal Queue"的数据结构,我不确定之前我听说过它似乎有时间复杂性行为至少与Fibonacci堆一样好. 这是一个很好的表格,比较了不同种类堆的各种操作的时间复杂性.
4. 在关于是否有斐波那契的任何应用程序问题或二项堆,应答者只给了二项堆的例子.

这可能听起来很幼稚,但是在给定足够的代码的情况下,是否存在无法用C构造的任何数据结构/算法？我理解图灵完成的论点.我也知道拥有一个优雅的解决方案是有益的,时间复杂性很重要(即在Ruby/Java/C#/ Haskell/Lisp中实现时更具表现力或简洁性).我研究或使用的所有语言似乎都已创建或随后重构为基于C的编译器,解释器和/或虚拟机.一些复杂的数据结构是否只能通过解释器和/或虚拟机实现？如果该虚拟机或解释器是基于C的,那么这不仅仅是底层C代码的另一个数据结构抽象吗？即C具有简单类型系统,但作为动态类型系统的基础.我很惊讶地发现元编程似乎可以在C中使用预处理器(ioccc.org Immanuel Herrmann).我也看到了一些模仿Erlang并发模型的有趣的C算法,但不记得源代码.

启发这个问题的是StackOverflow帖子(鲜为人知的有用数据结构)和Patrick Dussud对channel9的采访(垃圾收集 - 过去,现在和将来) - 解释他们如何编写第一个CLR垃圾收集器(用Lisp编写,目标是JVM) ,从Lisp编译为C++用于CLR).

所以,在一天结束时,在我完成打卡之后,我想知道这个问题是否可能更多是关于C编程语言设计而不是编程的方便性和时间复杂性.例如,我可以在Prolog中实现一个非常优雅且非常难以理解的任何其他方式的高度复杂的算法,但我仍然受到组装指令和计算机体系结构(开/关)的限制.棒,所以我整晚都在这里.

最近我遇到了SkipList数据结构.这真的帮助我解决了一个难以解决的难题.我正在努力使用平衡二叉树来解决它,但它变得非常复杂,因为树需要始终保持平衡,我想知道不仅存在特定值而且存在某个范围内的值.SkipList帮助我有效地解决了这个问题.

我想知道我需要知道的其他数据结构是什么？我知道 - 数组,列表,堆栈,队列,链接列表,哈希表,树及其不同的形式,如B-tree,Trie等.想知道您是否发现其他一些有趣的数据结构/概念以及有用的定期开发周期.