1

我正在上 CS 课程，但坦率地说，我不知道讲师在谈论抽象数据类型代数方面的内容。这不是我很容易在网络上找到解决方案的东西，我想也许社区中的某个人会对这个问题有更深入的了解或不了解。

堆：

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

符号肯定有点奇怪......上面的实际含义是什么〜我理解队列和堆栈的一般行为是先进先出与先进后出。

4

1 回答 1

2

抽象数据类型可用于描述类型的行为必须如何，而无需指定实现。您将类型定义为一组公理或规则，这些公理或规则描述了每时每刻必须满足的条件。Djikstra曾经说过 ADT 是一种非常有用的工具来描述队列的行为……但是，撇开 Djikstra 著名的超批评幽默不谈，我至少可以想到 ADT 的一个实际应用：断言。

断言允许您指定您的类型如何在正式的、可编译的、可运行的语言中工作（与自然语言文档相反）。在契约式设计中，它们通常被写成谓词，在源语言或某种形式的元语言中执行方法（通常是对类型的任何操作）之前或之后必须保持。支持断言的框架（例如CodeContracts对于 .NET) 自动检查每个谓词是否应该成立。这样，如果你自己的代码违反了你的一个断言，你就知道你有一个错误。因此，在某种意义上，它可以被视为一种单元测试形式，不是通过指定测试用例（这将是经验测试方法），而是通过指定您的类型必须适合的前置条件、后置条件和不变量（这将是理论测试方法）。

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

从纯理论的角度来看，ADT 只是一种抽象，它允许我们推理类型的行为，而不管它们的具体实现如何。如果你喜欢形式主义（就像我一样），没有什么比让开发人员给你一个定理列表更好的了，而不是一个模棱两可的胡说八道来描述他的代码应该做什么。

另一方面，诸如逻辑或函数式编程之类的一些替代编程范式（替代面向对象的替代方案，而不是次要的、不重要的等）在类型构造中大量基于 ADT。一个非常有趣的例子是Haskell语言。它为您提供了类型、继承和多态性的全新图景。

于 2013-02-14T16:24:13.253 回答