第八章 抽象数据类型与子程序
8.1 抽象数据类型
抽象数据类型（ADT）：属性（数据和操作）明确地与特定实现分离的容器。
本章介绍的抽象数据类型是在现实世界的问题中反复出现过的。这些ADT是储存数据项的容器，每种ADT都具有特定的行为。称他们为容器是因为他们存在的唯一目的就是存放其他对象。
容器：存放和操作其他对象的对象。
8.2栈
栈是一种复合抽象结构，只能从一端访问栈中的元素。可以在第一个位置插入元素，也可以删除第一个元素，会计师称他为LIFO，即为后进先出（Last In First Out）。
另一种描述栈的访问行为的说法是删除的项总是在项中时间最短的项目。
使栈的插入和输出有惯用语，插入操作叫Push（推进），删除操作叫Pop（弹出）。
8.3队列
队列也是一种抽象结构，队列中的项目从一端入，从另一端出。会计师称之为FIFO，即先进先出（First In First Out）的缩写。插入操作在队列的rear（尾部）进行，删除操作在头部进行。
另一种描述是，删除的总是在对队列中时间最长的项目。
插入和删除操作没有标准的相关术语。
Enqueue Enque Enq Enter Insert都可以表示插入操作。
Dequeue Deque Deq Delete Remove 都可以表示删除操作。
8.4 列表
列表有三个属性特征：项目是同构的，项目是线性的，项目是变长的。
栈和队列对于删除操作都有全部的定义，列表通常提供插入一个项目的操作（Insert） 删除一个项目的操作（Delete） 检索一个项目是否存在（IsThere）以及报告中的项目数量（GetLength），它们有一些机制允许用户查看序列中的每一项。因为项目可以被删除和检索，所以列表中的项目必须能够相互比较。
不要把列表误认为是数组，数组是内嵌结构，列表是抽象结构。
列表也可以被形象化为链式结构，链式结构以节点的概念为基础。一个节点有、由两个部分构成：用户的数据和指向列表的下一个结点的链接或指针。列表的最后一个节点的指针变量存放的是表示列表结束的符号，通常为null，用“/”表示。
8.5 树
8.5.1 二叉树
二叉树是一种抽象结构，其中的每个节点可以有两个后继节点，叫做子女。每个子女又仍是分叉树的节点，因此也可以有两个子节点，而这些子女又有了自己的子女，以此类推，就形成了树的的分支结构。起始节点叫做根。
如果一个节点没有子女，则这个节点叫做树叶。
8.5.2 二叉检索树
二叉检索树就像已排列的列表，节点间存在语义排序。
在二叉树中检索
构造二叉搜索树
因为John是第一个插入的值，所以它是根节点。第二个值Phil大于John，因此他将成为右子树的根节点。lila大于John但小于Phil，因此他将成为左子树的根节点。
算法：
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）图算法
深度优先搜索
当我们试图在两个顶点间寻找路径时，用栈来储存访问的顶点。用深度优先搜索来检查第一个与起点相邻的顶点。如果它是终点，则搜索结束。否则，检查所有与第一个顶点相邻的终点。
同时，我们需要存储其他和起点相邻的顶点，随后需要的时候会用到它们。如果不存在一条从与起点相邻的第一个顶点出发的路径，那么我们回到顶点，尝试第二个顶点、第三个顶点，以此类推。因为我们想要沿着一条路径尽可能深的访问各个节点，如果没有找到终点就回溯，因此栈是一种存储顶点的合适的数据结构。
广度优先搜索
在广度优先搜索中，我们想要回溯到尽可能远，以找到从最初的顶点出发的路径。因此栈不再是一个适合寻找较早路径的数据结构。它是按照元素出现的相反顺序来保存元素，即最晚的路径在顶部。
单源最短路搜索
8.7 子程序
许多子程序都是高级语言或语言附带库的一部分。
假设已经检验过这些算法中的抽象数据类型的容量。例如，如下列表算法：
WHITE(more data)
Read value
Insert(mylist,value)
Reset(mylist)
White"item in the list are"
WHITE(MOreitems(mylist))
GetNext(mylist,nextitem)
write nextitem
Insert操做需要一个列表和一个插入其中的值。Reset操作需要一个用来重置的列表。Moreitems操作需要一个列表来查看是否有更多元素等待被返回。Getnext操作需要一个操作列表并且返回一个列表中的下一个元素。这些信息的交流是通过参数列表的概念实现的。
第九章 面向对象设计与高级程序设计语言
9.1 面向对象方法
面向对象
对象：在问题背景中相关的事物或实体。
对象类或类：一组具有相似的属性和行为的对象的描述。
域：类中的特定项，可以是数据或者子程序。
方法：定义了类的一种行为的算法。
设计方法
-
集体讨论：确定问题中的类的第一个阶段。
-
过滤：回顾集体讨论阶段确定的类，看那些类是可以合并的以及还缺少哪些类。
-
场景：确定每个类的行为。
-
责任算法：为列出的所有类的责任编写算法。
一个计算机示例
2.翻译过程
编译器
编译器：把用高级语言编写的程序翻译成机器码的程序。
早期编译器输出的是程序的汇编语言版本，这个版本还要经过汇编器处理才能得到可执行的机器语言程序。随着计算机科学家更加深入地了解翻译过程，编译器变得更加复杂，汇编语言的阶段通常被省略了。
翻译器
翻译器：输入用高级语言编写的程序，指导计算机执行每个语句指定的动作的程序。
字节码：编译Java源代码使用的标准机器语言。
3.程序设计语言的范型
命令式范型
-
面向过程的范型
面向过程编程是一种命令式模型，在这里语句被分组成了子程序。一个程序是子程序分层次构成的，每一层执行整个问题求解的一个必要的特定任务。为代码示例描述了这种模型。我们编写子程序并且通过向其传递所需数据来完成它们的功能。 -
面向对象的范型
面向对象视角是与对象交互的一种方式。每个对象负责执行它自己的动作。在面向对象的范型中，数据对象是活跃的。对象和操作对象的代码绑定在一起，使得每个对象负责控制自己的操作。
声明式范型
声明式范型是一个描述结果的模型，但是完成结果的过程则不被描述。
-
函数式模型
函数式模型基于函数的数学概念。计算通过对函数求值来实现，而问题求解通过函数调用来实现。因此基本的原理是函数的求值，而不是变量和赋值语句。 -
逻辑编程
逻辑编程基于象征逻辑的原则。这个模型包括了一系列关于对象的事实和一系列关于对象间关系的规则。一个程序包括了向这些对象和关系询问可以通过事实和规则推演的问题。解决潜在问题的算法用逻辑的规则来推演出事实和规则的答案。4.高级程序设计语言的功能性
（1）布尔表达式
布尔表达式：一个标识符序列，标识符之间由相容的运算符分割，求得的值是true或false。
布尔表达式可以是： -
一个布尔变量
-
一个算术表达式加一个关系运算符，再加一个算术表达式
-
一个布尔表达式加一个布尔运算符再加一个布尔表达式
（2）数据归类
强类型化：每个变量都有一个类型，只有这种类型的值才能存储到该变量中。
数据类型：一组值以及能够应用于这种类型的值的基本操作集合的说明。
分类：
-
整数
-
实数
-
字符
-
布尔型
-
字符串
-
声明
声明：把变量、动作或语言中的其他实体与标识符关联起来的语句，使程序员可以通过名字引用这些项目。
保留字：一种语言中具有特殊意义的字，不能用它作为标识符。
区分大小写：大写字母和小写字母被看作是不同的；两个拼写方式相同但大小写形式不同的标识符被看作是两个不同的标识符。
（3）输入/输出结构
（4）控制结构
控制结构：确定程序中的其他指令的执行顺序的指令。
嵌套逻辑
异步处理
异步：不与计算机中的其他操作同时发生；换句话说，与计算机的动作
9.5 面对对象语言的功能性
封装：实现信息隐蔽的语言特征。
对象类或类（问题求解阶段）：属性和行为相似的一组对象的说明。
对象（问题求解阶段）：与问题背景相关的事物或实体。
对象（实现阶段）：类的一个实例。
类（实现阶段）：对象的模式。
实例化：创建类的对象。
继承：类获取其他类的属性（数据域和方法）的机制。
多态：一种语言的继承体系结构中具有两个同名方法且能够根据对象应用合适的方法的能力。
面向对象的程序用以下结构刻画：
——封装：实施信息隐蔽的语言特征，用类结构实现。
——继承：允许一个类继承另一个类的属性和行为的语言特征。
——多态：语言具备的消除同名操作的歧义的能力。