第八章 抽象数据类型与子程序

1.抽象数据类型
抽象数据类型（Abstract Data Type，ADT）：属性（数据和操作）明确地与特定实现分离的容器。
设计的目标是通过抽象减少复杂度。如果在逻辑层定义了有用的结构和处理它们的操作，就可以随便使用它们了。
应用（或用户）层是特定问题中的数据的视图。逻辑（或抽象）层是数据值（域）和处理它们的操作的抽象视图。实现层明确表示出了存放数据项的结构，并用程序设计语言对数据丽操作进行编码。这个视图用明确的数据域和子程序表示对象的属性。
数据结构（data structure）：一种抽象数据类型中的复合数据域的实现。
容器（container）：存放和操作其他对象的对象。

2.栈
栈是一种抽象复合结构，只能从一端访问栈中的元素。可以在第一个位置插入元素，也可以删除第一个元素。会计师称它为LIFO，即后进先出（Last In First Out）的缩写。
从另一种描述栈的访问行为的说法是删除的项总是在栈中时间最短的项目。从这个角度观察栈就更加抽象。插入操作没有任何约束；整个LIFO行为都体现在删除操作上。
Push：插入操作（推进）。
Pop：删除操作（弹出）。
例：
WHILE(more data)
Read value
Push(myStack,value)
WHILE(NOT IsEmpty(myStack))
Pop(myStack,value)
Write value
注：桌面检查此算法以确定这些值的确以相反顺序输出。
3.队列
队列中的项目从一端入，从另一端出。会计师称之为FIFO，即先进先出（First In First Out）的缩写。插入操作在队列的rear（尾部）进行，删除操作在队列的front（头部）进行。
另一种描述队列的访问行为的说法是删除的总是在队列中时间最长的项目。从这个角度观察队列就更加抽象。与栈一样，插入操作没有任何约束；整个FIFO行为都体现在删除操作上。遗憾的是，插入和删除操作没有标准的相关术语。Enqueue、Enque、Enq、Enter和Inset都可以表示插入操作。Dequeue、Deque、Deq、Delete和Remove都可以表示删除操作。
例：
WHILE(more data)
Read value
Enque(myQueue,value)
WHILE(NOT IsEmpty(myQueue))
Deque(myQueue,value)
Write value
4.列表
列表的三个属性特征：

• 项目是同构的
• 项目是线性的
• 列表是变长的
  不要把列表误认为是数组，数组是内嵌结构，列表是抽象结构。然而列表应用于数组中。列表也可以被形象为链式结构。
  链式结构（linked structure）：一个将数据和找到下一项位置的信息保存到同一容器的实现方法。链式结构以节点的概念为基础。一个节点由两部分构成：用户的数据和指向列表的下一个节点的链接或指针。列表的最后一个节点的指针变量存放的是表示列表结束的符号，通常为null，用“/”表示。
  
• 无序列表的顺序并不重要，项目只是随意的被放入其中。
• 有序列表中，项目之间具有语义关系。除了第一个项目之外所有项目都存在某种排序关系。除了最后一个项目，所有项目都有着相同的关系。

5.树
（1）二叉树
二叉树（binary tree）：具有唯一起始节点（根节点）的抽象复合结构，其中每个节点可以有两个子女节点，根节点和每个节点之间都有且只有一条路径。
根（root）：树中唯一的开始节点。
叶节点（leaf node）：没有子女的树节点。
（2）二叉检索树
二叉检索树就像已排序的列表，节点间存在语义排序。

• 二叉检索树具有二叉树的属性，也就是说二叉检索树中的节点可以具有0个、1个或2个子女。
  
• 二叉检索树还具有语义属性来刻画树中节点上的值，即任何节点的值都要大于它的左子树中的所有节点的值，并且要小于它的右子树中的所有节点的值。

在二叉检索树中检索
算法：
++IsThere（tree，item）++
IF（tree is null）
RETURN FALSE
ELSE
IF（item equals into(tree))
RETURN TRUE
ELSE
IF (item < info(tree))
IsThere(left(tree),item)
ELSE
IsThere(right(tree),item)

构造二叉检索树
算法：
++Inset（tree，item）++
IF(tree is null)
Put item in tree
ELSE
IF(item < info(tree))
Insert(left(tree),item)
ELSE
Insert(right(tree),item)

输出二叉检索树中的数据
算法：
++Print（tree）++
IF(tree is NOT null)
Print(left(tree))//Recursive call R1
Write info(tree)
Print(right(tree))//Recursive call R2

（3）其他操作
计算节点数
算法：
++Length（tree）++
IF(tree is null)
RETURN 0
ELSE
RETURN Length(left(tree))+Length(right(tree)) + 1

6.图
图（graph）：由一组节点和一组把节点相互连接起来的边构成的数据结构。
顶点（vertex）：图中的节点。
边（弧）（edge（arc））：表示图中两个节点的连接的顶点对。
无向图（undirected graph）：其中的边没有方向的图。
有向图（directed graph）：其中的边是从一个顶点指向另一个顶点（或同一个顶点的）图。
邻顶点（adjacent vertice）：通过边连接起来的两个顶点。
路径（path）：连接图中两个顶点的一系列顶点。

（1）创建图
创建一个表格需要以下操作：

• 在表格添加一个顶点
• 在表格添加一条边
• 在表格添加一个权值

（2）图算法

深度优先搜索

当我们试图在两个顶点间寻找路径时，用栈来储存访问的顶点。用深度优先搜索来检查第一个与起点相邻的顶点。如果它是终点，则搜索结束。否则，检查所有与第一个顶点相邻的终点。
同时，我们需要存储其他和起点相邻的顶点，随后需要的时候会用到它们。如果不存在一条从与起点相邻的第一个顶点出发的路径，那么我们回到顶点，尝试第二个顶点、第三个顶点，以此类推。因为我们想要沿着一条路径尽可能深的访问各个节点，如果没有找到终点就回溯，因此栈是一种存储顶点的合适的数据结构。

广度优先搜索

在广度优先搜索中，我们想要回溯到尽可能远，以找到从最初的顶点出发的路径。因此栈不再是一个适合寻找较早路径的数据结构。它是按照元素出现的相反顺序来保存元素，即最晚的路径在顶部。

单源最短路搜索

7.子程序

（1）参数传递

参数列表（parameter list）：程序中两部分之间的通信机制。
形参（parameter）：列在子程序名后的括号中的标识符。
实参（argument）：子程序调用中列在括号中的标识符。

（2）值参与引用参数

值参（value parameter）：由调用单元传入实参的副本（写在留言板上）的形参。
引用参数（reference parameter）：由调用单元传入实参的地址（写在留言板上）的形参。

小结

• 列表、栈、队列、树和图都是有用的抽象复合结构。
  
• 列表和树有着相同的属性：元素可以被插入、删除和检索。
• 列表、栈、队列和树都仅仅是容器结构，但是图则更复杂。
• 子程序声明使得子算法可以独立实现。

第九章 面对形象设计与高级程序设计语言

1.面向对象方法
面向对象
对象（object）：在问题背景中相关的事物或实体。
对象类（object class）或类（class）：一组具有相似的属性和行为的对象的描述。
域（field）：类中的特定项，可以是数据或者子程序。
方法（method）：定义了类的一种行为的算法。

设计方法

• 集体讨论：确定问题中的类的第一个阶段。
  
• 过滤：回顾集体讨论阶段确定的类，看那些类是可以合并的以及还缺少哪些类。
  
• 场景：确定每个类的行为。
• 责任算法：为列出的所有类的责任编写算法。

一个计算机示例

2.翻译过程

编译器
编译器（compiler）：把用高级语言编写的程序翻译成机器码的程序。
早期编译器输出的是程序的汇编语言版本，这个版本还要经过汇编器处理才能得到可执行的机器语言程序。随着计算机科学家更加深入地了解翻译过程，编译器变得更加复杂，汇编语言的阶段通常被省略了。

翻译器
翻译器（interpreter）：输入用高级语言编写的程序，指导计算机执行每个语句指定的动作的程序。
字节码（bytecode）：编译Java源代码使用的标准机器语言。

3.程序设计语言的范型

命令式范型

• 面向过程的范型
  面向过程编程是一种命令式模型，在这里语句被分组成了子程序。一个程序是子程序分层次构成的，每一层执行整个问题求解的一个必要的特定任务。为代码示例描述了这种模型。我们编写子程序并且通过向其传递所需数据来完成它们的功能。
  
• 面向对象的范型
  面向对象视角是与对象交互的一种方式。每个对象负责执行它自己的动作。在面向对象的范型中，数据对象是活跃的。对象和操作对象的代码绑定在一起，使得每个对象负责控制自己的操作。

声明式范型

声明式范型是一个描述结果的模型，但是完成结果的过程则不被描述。

• 函数式模型
  函数式模型基于函数的数学概念。计算通过对函数求值来实现，而问题求解通过函数调用来实现。因此基本的原理是函数的求值，而不是变量和赋值语句。

• 逻辑编程
  逻辑编程基于象征逻辑的原则。这个模型包括了一系列关于对象的事实和一系列关于对象间关系的规则。一个程序包括了向这些对象和关系询问可以通过事实和规则推演的问题。解决潜在问题的算法用逻辑的规则来推演出事实和规则的答案。

4.高级程序设计语言的功能性

（1）布尔表达式

布尔表达式（Boolean expression）：一个标识符序列，标识符之间由相容的运算符分割，求得的值是true或false。
布尔表达式可以是：

• 一个布尔变量
  
• 一个算术表达式加一个关系运算符，再加一个算术表达式
• 一个布尔表达式加一个布尔运算符再加一个布尔表达式

（2）数据归类

强类型化（strong typing）：每个变量都有一个类型，只有这种类型的值才能存储到该变量中。
数据类型（data type）：一组值以及能够应用于这种类型的值的基本操作集合的说明。
分类：

• 整数
• 实数
• 字符
• 布尔型
• 字符串
• 声明

声明（declaration）：把变量、动作或语言中的其他实体与标识符关联起来的语句，使程序员可以通过名字引用这些项目。
保留字（reserved word）：一种语言中具有特殊意义的字，不能用它作为标识符。
区分大小写（case sensitive）：大写字母和小写字母被看作是不同的；两个拼写方式相同但大小写形式不同的标识符被看作是两个不同的标识符。

（3）输入/输出结构

（4）控制结构

控制结构（control structure）：确定程序中的其他指令的执行顺序的指令。
嵌套逻辑
异步处理
异步（asynchronous）：不与计算机中的其他操作同时发生；换句话说，与计算机的动作不同步。

5.面向对象语言的功能性

（1）封装

封装（encapsulation）：实施信息隐蔽的语言特性。
对象类或类（问题求解阶段）（object class or class（problem-solving phase））：属性和行为相似的一组对象的说明。
对象（问题求解阶段）（object（problem-solving phase））：与问题背景相关的事物或实体。
对象（实现阶段）（object（implementation phase））：类的一个实例。
类（实现阶段）（class（implementation phase））：对象的模式。

（2）类

实例化（instantiate）：创建类的对象。

（3）继承

继承（inheritance）：类获取其他类的属性（数据域和方法）的机制。

（4）多态

多态（polymorphism）：一种语言的继承体系结构中具有两个同名方法且能够根据对象应用合适的方法的能力。

6.过程设计与面向对象设计的区别

小结

• 面向对象设计的重点是确定问题中的对象，并根据对象的属性和行为把它们抽象（分组）成类。
  
• 汇编器可以把汇编语言程序翻译成机器码。
  
• 存在多种高级程序设计语言的模型。
  
• 布尔表达式是关于程序状态的断言。
  
• 程序中的每个变量都有自己的数据类型。