问题标签 [abstract-data-type]

哪一个是 C 语言中 N-ary 树的简洁实现？

特别是，我想实现一个 n-ary 树，而不是自平衡树，每个节点中的子节点数量不限，其中每个节点都包含一个已经定义的结构，例如：

我正在尝试深入研究 Dictionary ADT 和 Skip List for Java。我的教科书对此并没有太多的介绍，而且它所涵盖的内容都非常复杂。哪个是获取有关 Dictionary ADT 和 Skip List for Java 的更多信息的最佳在线站点。我正在寻找一个能直观地说话并给出很多例子的人。

我正在做一个名为数据结构和算法的单元。我们刚刚开始，我的教授刚刚教给我们什么是代数语义以及什么是公理等基础知识。到目前为止，我只是以数组的形式使用树。不使用预排序树的签名作为树（值，树，树），其中值是节点中的值，左节点是第一棵树，右节点是第二棵树。

现在我将我的树定义为树（值，树，树）或 Nil，我不知道如何去定义 addNode（值，树）的代数。

每个级别都变得越来越复杂，另外，我无论如何都想不到一次扫描一个级别，现在已经尝试了一个小时。当我们沿着树向下走时，代数只是分支成越来越多的 if-else。我做对了吗？你能为我指出正确的方向吗？或者树不能实现为树（值，树，树）？

这是我教程的一部分（在附加问题中不值得任何标记），但我不是在寻找即时答案，我喜欢这个主题，并想了解更多。

编辑1：我查看了维基百科，我不想使用教科书来获得明确的答案，我只是在寻找正确方向的提示，无论我的方法是正确的还是完全不可能将树定义为树（值，树，树）。我知道您可以以列表的形式表示树 ADT。但我真的想好好想想。希望这是有道理的。非常感谢你们！

编辑2：嗯，很难通过互联网解释。假设我正在定义一个名为“树”的新数据结构。我可以以任何我想要的方式定义它，它必须表现得像一个平衡的二叉树（虽然，父母和孩子的值无关紧要）所以我将它定义为树：树（值，树，树）或无它不是编程代码，这就是我的定义。Tree 是一个值 + 2 棵其他树，或者 Tree 是 nil。现在 addNode(value, tree) 向树添加一个节点，同时仍然保持平衡。它不是编程代码，它只是代数语义。不知道能不能解释清楚。但是我找到了一个可以使用队列或堆栈实现的解决方案，但这是我必须定义的另一个 ADT，它是无效的。

编辑3：似乎我已经假设了许多使问题变得比实际应该更难的事情。首先，从我给出的一点解释来看，Gamecat 的回答是完美的。但我同意这些评论，包括其他 ADT 是完全有效的。事实上，当我们构建任何使用 Int 的东西时，我们正在为该结构使用 ADT。我认为每个 ADT 都必须是独一无二的。无论如何，非常感谢您的回答！

我正在尝试找到一种更好的方法来实现这些方法，因为在非常大的集合中它们需要很长时间，有什么想法吗？

编辑：

我相信我找到了一种更快的方法来计算similarityOfMultisets 方法：

问题是通过两种不同的方法访问一系列值。首先，按优先级；这是用堆简单地实现的。此外，必须可以用一个或多个符号“标记”每个值，通过这些符号可以访问项目列表。

通过在两个不同的结构中引用相同的数据，这将很容易有效地实现。但是，这些必须形成一个有凝聚力的队列。因此，通过一个结构删除的项目也必须从另一个结构中删除，堆不是非常适合的操作。

是否有一种数据结构能够通过一个值提供有效的排序（理想地为推送/弹出优化），而不会完全降低在任意位置查找/删除节点的性能？

我应该使用什么数据结构来实现 BTree？为什么？

什么是面向对象编程中的抽象数据类型？我已经浏览了这个主题的wiki，但我仍然不清楚。有人可以澄清一下吗？

C++ 中是否有一个我可以#include 的链表？或者如果我想使用一个，我需要创建自己的吗？

C 编程语言的 ADT 库有什么好的实现吗？实现列表、哈希映射、集合、堆栈、队列、链接列表等？我知道这是一个愚蠢的问题，但我不想实现所有这些只是为了意识到它已经存在。

我在互联网上看到了它们的碎片——当然。但是，你们中是否有任何人有很好的经验的全面的、一体化的、运行良好的解决方案？

据我了解，Haskell 中的列表类型是在内部使用链表实现的。但是，该语言的用户无法看到实现的细节，也无法修改构成链表的“链接”以使其指向不同的内存地址。我想，这是在内部完成的。

那么，列表类型如何被限定为 Haskell 呢？它是“数据类型”还是“抽象数据类型”？什么是链表类型的实现？

另外，由于 Prelude 提供的列表类型不是链表类型，那么如何实现基本的链表功能呢？

例如，这段代码旨在将元素 a 添加到列表的索引 n 处：

使用“真正的”链表，添加元素只需修改指向内存地址的指针。这在 Haskell 中是不可能的（或者是吗？），因此问题是：我将元素添加到列表中的实现是最好的，还是我遗漏了什么（reverse我认为该函数的使用特别难看，但是没有可能吗？）

请不要犹豫，如果我所说的任何内容有误，请纠正我，并感谢您的宝贵时间。