标签：02 ADT bullet text Review 抽象数据类型 STACK empty

结构化开发方法

• 基本思想：自顶向下，逐步求精，过程抽象，模块化技术
• 概念：
  • 结构化程序设计：按照一定的原则与原理，组织编写正确且易读的程序的软件技术。
  • 结构化分析设计：数据流图、数据字典、模块结构图。
• 优势：合理性（管理复杂性的有效手段：分解，抽象，层次）、正确性（依据规约，完成任务）

程序 & 抽象

程序：

• 程序运行：在某个数据体上施以某些操作。
• 两个要素：
  1. 操作（功能）Functions/Operations/Actions；
  2. 客体（对象）Objects/Data；
• 两种抽象方法：
  1. 从操作/功能入手，形成：基于过程的抽象；
  2. 从客体/对象入手，形成：基于数据的抽象；

过程抽象 & 数据抽象：

• 过程抽象：指任何一个明确定义功能的操作都可以被使用者看作单个的实体，尽管这个操作实际上可能由一系列更低级的操作完成。
• 数据抽象：
  • 概念：定义了数据类型和施加于该类型对象上的操作，并限定了对象的值只能通过使用这些操作修改和观察，包含两个概念：1. 模块封装；2. 信息隐蔽。
  • 意义：数据抽象提供了面向对象计算的起点：系统应该被分解为概念上的实体，实体的内部细节应该被隐藏。
  • 发展历程：
    1. 第一阶段：从无类型的二进制到基本数据类型；
    2. 第二阶段：从基本类型到用户自定义类型；
    3. 第三阶段：从用户自定义类型到抽象数据类型（Abstract Data Types）-面向对象

面向对象的软件构造（OOSC）

• 面向对象的分解好在何处：
  • 复用性（Reusability）：数据（结构）及其上之操作的整体复用，而非仅仅复用操作功能；
  • 可拓展性（Extendibility），连续性（Continuity）：对象更直接对应问题空间的概念，因而较“功能”更稳定；
• 含义：
  • OOSC乃是基于系统所操作之对象类型（而非系统需实现之功能）来架构系统的途径。
  • OOSC乃是将系统构造为抽象数据类型实现（可能是部分实现）的结构化组合。（这个“抽象数据类型的实现”就是类（class））
• 对象刻画（注重外部视图，而非内部视图）：
  • 主要方法：
    • 考虑一类具有相似属性的对象而不是单个对象。
    • 定义对象的类型不是通过定义对象的物理表述，而是通过定义它们的行为：即它们提供给外部的服务。
  • 主要标准：1. 完整的（Completely）；2. 无歧义的（Unambiguously）；3. 不过分描述的（Without overspecifying）-记住信息隐藏；

抽象数据类型（ADT，Abstract Data Type）

• 定义：
  • 数据类型：由一个对象集合（值集合）以及在该集合上定义的若干合法运算所组成的运算集合组成。
  • 抽象数据类型：用“数学方法”定义对象集合和运算集合，仅通过运算的性质刻画数据对象，而独立于计算机中可能的表示方法。
• ADT规约方法：
  1. 代数方法
  2. 模型方法（C.A.R.Hoare的前后断言方法：通过已定义的（抽象）数据类型来给出要定义的新类型的抽象模型）

代数规范

• 构成：
  • 语法部分：
    1. ADT名；
    2. 运算（函数）的定义域和值域；
  • 公理部分：
    1. 给出一组刻画各运算之间相互关系的方程来定义各运算的含义；
    2. 语义正确性：相应代数满足规约中公理部分的所有公理；
• ADT函数分类：一个ADT \(T\) 中可有三种函数（算子）：
  1. Creators（构造算子）：\(\text{OTHER} \rightarrow T\)。eg. new
  2. Queries（观察算子）：\(T\times \dots \rightarrow \text{OTHER}\)。eg. item, empty
  3. Commands（运算算子）：\(T\times \dots \rightarrow T\)。eg. put, remove

Reminder: Partial functions

• A partial function, identified here by \(\nrightarrow\), is a function that may not be defined for all possible arguments.

• 实例：

\[\begin{array}{c} \textbf{ADT specification of stacks} \\ \\ \begin{array}{ll} \textbf{TYPES}: \\ \bullet\ STACK[G] \text{--}G:\text{Formal generic parameter} \\ \\ \textbf{FUNCTIONS(Operations)}: \\ \bullet\ put:\ STACK[G]\times G \rightarrow STACK[G] \\ \bullet\ remove:\ STACK[G] \nrightarrow STACK[G] & \text{

标签：02,ADT,bullet,text,Review,抽象数据类型,STACK,empty
From： https://www.cnblogs.com/seed42-blog/p/18233224