如何理解ADT（抽象数据类型代数）？

我正在参加CS课程，但坦率地说，我不知道讲师讲的是什么抽象数据类型代数。这并不是我很容易在网络上找到解决方案的原因，我想也许社区中的某个人会对问题有更深刻的洞察力或未解决的问题。如何理解ADT（抽象数据类型代数）？

堆栈：

isempty(createstack()) = true 
isempty(push(n, s)) = false 
top(push(n, s)) = n 
pop(push(n, s)) = s

队列：

isempty(createqueue()) = true 
isempty(add(n, q)) = false 
front(add(n, q)) = n, if q is empty 
front(add(n, q)) = front(q), if q is not empty removefront(add(n, q)) = q, 
if q is empty  removefront(add(n, q)) = add(n, removefront(q)), 
if q is not empty

符号无疑是一个有点奇怪......什么是高于平均实质〜我明白队列的一般行为和作为先进先出和先进先出的堆叠。

来源

2013-02-09 peter_gent

没有那些只是规则描述它是如何工作的？。例如“isempty（add（n，q））= false”...如果将N添加到队列Q中，Q不是空的...如果将N添加到Q并且Q是空的，前面是N – 2013-02-09 22:28:03

即可。在演讲中，演讲者将演讲者的方括号内的括号括起来，用于某些复杂的抽象运算符。 – 2013-02-09 22:51:49

这里没有“ADT代数”。该文章包含操作和*伪代码*（这意味着，它应该是“在上下文中可理解的”，但没有其他）描述了预期的操作行为。分别阅读堆栈或队列，以了解具体的实现细节/示例和“真实”使用案例。 – 2013-02-09 23:38:36

抽象数据类型可用于描述类型的行为必须如何指定实现。您将类型定义为一组公理或规则，用于描述哪些条件必须在每个时刻都适用。 Djikstra曾经说过ADT是描述队列行为的非常有用的工具......但是，把Djikstra的着名的超级批评者幽默放在一边，我可以想到至少有一个ADT的实际应用：assertions。

断言允许您指定类型如何以正式，可编译，可运行的语言（与自然语言文档相反）工作。在Design by contract methodoloy中，它们通常被写成谓词，它必须在源语言或某种形式的元语言的方法执行之前或之后（通常是该类型的任何操作）持有。支持断言的框架（例如.NET的CodeContracts）会自动检查每个谓词在应该出现时的状态。这样，如果你自己的代码违反了你的一个断言，你就知道你有一个bug。因此，从某种意义上说，它可以被看作是单元测试的一种形式，而不是通过指定测试用例（这将是实证测试方法），而是通过指定您的类型必须符合的先决条件，后置条件和不变量（这将是理论测试方法）。

尽管我没有在主流软件开发中使用过，但据我所知（检查断言可能会影响性能），但它们可以在测试过程中使用。

从纯理论的角度来看，ADT就是这样一种抽象，它允许我们推理类型的行为，而不管它们的具体实现如何。如果你喜欢形式主义（就像我一样），没有什么比开发人员给你一个定理列表更好，而不是描述他的代码应该做什么的模糊喋喋不休。另一方面，诸如逻辑或函数式编程的某些替代编程范例（替代于面向对象的替代，而不是次要的，不重要的等）是基于类型构造的ADT而沉重的。一个非常有趣的例子是Haskell语言。它为您提供了一个类型，继承和多态的全新图片。

来源

2013-02-14 16:24:13

如何理解ADT（抽象数据类型代数）？

回答

相关问题