问题标签 [abstract-data-type]

如果使用数组实现，我可以看到使用两个堆栈的优势，因为使用数组比队列更容易实现堆栈。但是如果使用链表，有什么好处呢？将堆栈弹出到队列中的行为增加了链表和数组实现的开销。

简要背景：广泛使用的许多（大多数？）当代编程语言至少有少数共同的 ADT [抽象数据类型]，特别是，

• 字符串（由字符组成的序列）

• 列表（值的有序集合），以及

• 基于映射的类型（将键映射到值的无序数组）

在 R 编程语言中，前两个分别实现为character和vector。

当我开始学习 R 时，有两件事几乎从一开始就很明显：list是 R 中最重要的数据类型（因为它是 R 的父类data.frame），第二，我无法理解它们是如何工作的，至少不够好，无法在我的代码中正确使用它们。

一方面，在我看来，R 的list数据类型是映射 ADT 的直接实现（dictionary在 Python、NSMutableDictionaryObjective C、hashPerl 和 Ruby、object literalJavascript 等中）。

例如，您可以像创建 Python 字典一样创建它们，通过将键值对传递给构造函数（在 Python 中dict不是list）：

您可以像访问 Python 字典一样访问 R List 的项目，例如x['ev1']. 同样，您可以通过以下方式仅检索“键”或“值”：

但是 Rlist也不同于其他地图类型的 ADT（无论如何，来自我学过的语言）。我的猜测是，这是 S 初始规范的结果，即从头开始设计数据/统计 DSL [领域特定语言] 的意图。

listR与其他广泛使用的语言（例如，Python、Perl、JavaScript）中的映射类型之间的三个显着区别：

首先，listR 中的 s 是一个有序集合，就像向量一样，即使值是键控的（即键可以是任何可散列值，而不仅仅是顺序整数）。几乎总是，其他语言中的映射数据类型是无序的。

其次，lists 可以从函数中返回，即使您在list调用函数时从未传入 a ，并且即使返回 的函数list不包含（显式）list构造函数（当然，您可以在实践中通过将返回的结果包装在对 ) 的调用中unlist：

R s的第三个特点list：它们似乎不能成为另一个 ADT 的成员，如果您尝试这样做，那么主容器将被强制为list. 例如，

我在这里的意图不是批评这种语言或它是如何记录的；同样，我并不是说list数据结构或其行为方式有任何问题。我所追求的只是纠正我对它们如何工作的理解，以便我可以在我的代码中正确使用它们。

以下是我想更好地理解的事情：

• 确定函数调用何时返回 a list（例如，strsplit上面提到的表达式）的规则是什么？

• 如果我没有明确地为 a 分配名称list（例如，list(10,20,30,40)），那么默认名称是否只是以 1 开头的连续整数？（我假设，但我不能肯定答案是肯定的，否则我们将无法通过list调用来强制这种类型的向量unlist。）

• 为什么这两个不同的运算符 ,[]和[[]], 返回相同的结果？

  x = list(1, 2, 3, 4)

  两个表达式都返回“1”：

  x[1]

  x[[1]]

• 为什么这两个表达式不返回相同的结果？

  x = list(1, 2, 3, 4)

  x2 = list(1:4)

请不要将我指向 R 文档 ( ?list, R-intro)——我已仔细阅读它，但它并不能帮助我回答我刚才提到的问题类型。

（最后，我最近了解到并开始使用一个 R 包（在 CRAN 上可用）hash，它通过 S4 类实现传统的地图类型行为；我当然可以推荐这个包。）

我正在尝试在 Fotran 77 中工作，我发现需要基于树的数据结构。除了用数组实现树之外，还有什么方法可以按照大多数语言的标准实现来构建带有指向其他节点的指针节点的树？

这种野兽的文档很少，而且似乎没有任何标准的结构类型可以使这成为可能。

想法？

我正在尝试用 Java 实现一个非常简单的 Trie，它支持 3 个操作。我希望它有一个 insert 方法、一个 has 方法（即 trie 中的某个单词）和一个 toString 方法以字符串形式返回 trie。我相信我的插入工作正常，但 has 和 toString 被证明是困难的。这是我到目前为止所拥有的。

trie 类。

和节点类

因此，基本上，在创建 Trie 时，会创建一个 TrieNode 作为具有 26 个子节点的根。当尝试插入时，会在该根节点上调用 insert，它会在正确的位置递归地创建一个新节点，并继续直到单词完成。我相信该方法工作正常。

我的 has 函数非常糟糕，因为出于某种原因，我必须在括号外加上 return 语句。我不能将它包含在 else 子句中，否则编译器会抱怨。除此之外，我认为该方法应该进行一些调整，但我无法终生解决。

toString 是我试图解决的野兽，但我扔给它的任何东西都不起作用，所以我会保留它，直到我解决问题。如果我有工作，我可能会想办法将它重新格式化为 toString 函数。

int val = word.charAt(0) - 64; 的目的 是因为输入的每个字符串都必须全部大写（我将创建一个字符串格式化函数来确保这一点）所以第一个字母的 int 值 - 64 将是它在数组中的位置。即数组索引0是A，所以A = 64，A - 64 = 0。B = 65，B - 64 = 1，依此类推。

我有一个行为很像堆栈的抽象数据类型。它表示特定用户制作的“图形对象”的历史。

每个“图形对象”包含一个或多个“线”、一个日期范围、键和一个标题。

每个“行”都包含一个为我的数据库中特定数据子集配置的 sql 生成器。

我希望这些“历史”在他们的会话之间可供用户使用。它将以标签的形式显示，例如“最近的图表”。

您认为在会话之间保留此类数据的最佳方式是什么。此应用程序可能会变得相当大，因此效率是一个问题。

我正在做这个作业，有一些我无法理解的东西（来自启动材料）。

我不明白最后一行背后的想法，我如何在代码中使用它？

我试图在 Scala 中实现一个在类型上参数化的通用数据类型T，它应该是Ordered[T]. 具体来说，它是 Sleator & Tarjan 的倾斜堆优先级队列的持久版本。在根据此处和 Odersky-Spoon-Venners 中的说明添加了许多复杂的类型参数声明后，在测试/调试实际功能之前，我遇到了一个编译器错误。

下面是我的代码的简化版本。

这给出了以下错误：

我已经尝试了声明的几种变体delMin，但无济于事。我想我理解这个问题（方法+需要订购保证），但我应该把它放在哪里？有没有办法声明delMin为返回SkewHeap[T]而不是SkewHeap[U]？

每当在 Haskell 中我们需要一些变体数据类型时，我们都会将ADT与模式匹配结合使用。Clojure 人员在此类用例中使用什么？

我在 C 上写了一些 ADT：我date.c and date.h 在 date.c 中有两个文件，我有：

在 date.h 里面我有：

编译器给我错误：

有人可以解释我的typedef有什么问题吗，在此先感谢

编辑：

文件一切正常，问题是，当我将结构更改为：

和指向：

程序完美运行，所以我想了解其中的区别

假设我有一个代表某种树结构的广告：

据我所知，没有办法对类型构造函数进行模式匹配（或者匹配函数本身没有类型？）但我仍然想使用编译时类型系统来消除返回或解析的可能性树节点的错误“类型”。例如，可能 CNode 只能是 ANode 的父节点。我可能有

作为一个 Parsec 解析函数，它被用作我的 CNode 解析器的一部分：

根据类型系统，parseANode 最终可能返回一个 Maybe CNode、一个 Maybe BNode 或一个 Maybe ANode，但我真的想确保它只返回一个 Maybe ANode。请注意，这不是我想要执行的数据模式值或运行时检查 - 我实际上只是试图检查我为特定树模式编写的解析器的有效性。IOW，我不是要检查解析数据的模式正确性，我真正想做的是检查我的解析器的模式正确性——我只是想确保有一天我不会搞砸 parseANode返回 ANode 值以外的值。

我希望也许如果我匹配绑定变量中的值构造函数，类型推断会弄清楚我的意思：

但这有很多问题，其中最重要的是 parseANode 不再可以自由地返回 Nothing。无论如何它都不起作用 - 看起来绑定变量被视为模式匹配，并且运行时在 parseANode 返回 Nothing 或 Maybe BNode 或其他东西时抱怨非详尽的模式匹配。

我可以按照以下方式做一些事情：

但这种情况很糟糕，因为它假设约束适用于所有节点——我可能对此不感兴趣——实际上它可能只是 CNodes 只能作为 ANodes 的父节点。所以我想我可以这样做：

但这使得与 *Node 的模式匹配变得更加困难 - 事实上这是不可能的，因为它们只是完全不同的类型。我想我可以在任何我想进行模式匹配的地方创建一个类型类

无论如何，这似乎有点混乱。谁能想到一个更简洁的方法来做到这一点？