第8章 抽象数据类型与子程序
8.1 抽象数据类型
抽象数据类型（Abstract Data Type,ADT):属性（数据和操作）明确地与特定实现分离的容器。
在计算领域，可以从应用层、逻辑层和实现层这三个方面来观察数据。
1.应用层：特定问题中的数据的视图。
2.逻辑（或抽象）层：数据值（域）和处理它们的操作的抽象视图。
3.实现层：明确表示出了存放数据项的结构，并用程序设计语言对数据的操作进行编码。
数据结构（data structure）：一种抽象数据类型中的复合数据域的实现。
容器（container）：存放和操作其他对象的对象。
8.2 栈
栈（Stack）：抽象复合结构，只能从一端访问栈中的元素
1.可以在第一个位置插入元素，也可以删除第一个元素
2.LIFO(Last In First Out)
3.删除的项总是在栈中时间最短的项目
4.插入操作（Push推进）没有任何约束；整个LIFO行为都体现在删除操作（Pop弹出）上
5.没有长度属性，没有返回栈中项目个数的操作
6.需要确定栈是否为空，当栈空时再弹出项目会出错
8.3 队列
队列（Queue）：一种抽象复合结构，队列中的项目从一端入，从另一端出
1.插入操作在队列的尾部（rar）进行，删除操作在队列的头部（front）进行
2.FIFO
3.删除的总是在队列中时间最长的项目
4.插入操作没有任何约束；整个FIFO行为都体现在删除操作上
8.4 列表
列表的列是无止境的。
列表有三个属性特征：项目是同构的，项目是 线性的，列表是 变长的。
项目可以被删除和检索，所以列表中的项目必须能够相互比较。
注意：不要把列表误认为是数组，因为数组的结构是 内嵌，列表的结构是抽象，而且列表应用于数组中。
链式结构（linked structure）：一个将数据项和找到下一项位置的信息保存到同一容器的实现方法。
链式结构以节点的概念为基础。其中一个节点由两部分构成： 用户的数据和指向列表的下一个节点的链接或指针。
列表的最后一个节点的指针变量存放的是表示列表结束的符号，通常为 null ，用“/”表示。
无序列表与有序列表的相互比较：
无序列表：该列表的顺序并不重要，项目只是随意被放入其中。
有序列表：项目之间具有语义关系。除了第一个项目之外所有项目都存在某种 排序关系 。除了最后一个项目，所有项目都有着 相同的关系 。
8.5 树
8.5.1 二叉树
二叉树：具有唯一起始节点（根节点）的抽象复合结构，其中每个节点可以有两个子女节点，根节点和每个节点之间都有且只有一条路径。
根：树中唯一的开始节点。
叶节点：没有子女的树节点。
除了根节点之外，每个节点都只有一个父母节点。
8.5.2 二叉检索树
要在树上找一个项目，我们必须检查每一个节点，直到找到想要的那个，或者发现它并不在树上。
二叉检索树就像已排序的列表，节点间存在语义排序。
二叉检索树中的节点可以具有0个，1个，2个子女。
二叉检索树还具有语义属性来刻画树中节点上的值。（任何节点的值都要大于它的左子树中的所有节点的值，并且要小于它的右子树中的所有节点的值）
-在二叉检索树中搜索
这种搜索法与线性结构的二分检索之间很相似，一次计较就排除很大一部分数据。
info（current）：指的就是这个节点的用户数据。
left（current）：指向的就是这个节点的左子树的根节点。
null说明指针指向空值
树的形状是由项目插入树的顺序决定的。
构造二叉检索树
输出二叉检索数中的数据
8.5.3 其他操作
8.6 图
1.树是表示存在的体系结构中关系的有效方式，也就是说，一个节点之多只有一个指向它的节点(它的父母)。如果去掉这种约束，就得到了另一种数据结构–图。
2.图(graph):由一组节点和一组把节点相互连接起来的边构成的数据结构。
顶点(vertex)：图中的节点。
边(弧)(edge(arc)):表示图中两个节点的连接的顶点对。
临顶点(adjacent vertice):通过边连接起来的两个顶点。
路径(path):连接图中两个顶点的一系列顶点。
3.无向图(undirected graph):其中的边没有方向的图。
有向图(directed graph(digraph)):其中的边是从一个顶点指向另一个顶点(或同一个顶点)的图。
8.6.1 创建图
许多信息可以被呈现在图上：顶点、边和权值。
创建一个表格需要以下操作：
•在表格中添加一个顶点
•在表格中添加一条边
•在表格中添加一个权值
8.6.2 图算法
1.深度优先搜索
当我们试图在两个顶点间寻找路径时，用栈来储存访问的顶点。用深度优先搜索来检查第一个与起点相邻的顶点。如果它是终点，则搜索结束。否则，检查所有与第一个顶点相邻的顶点。同时，我们需要存储其他和起点相邻的顶点，随后需要的时候会用到它们。如果不存在一条从与起点相邻的第一个顶点出发的路径，那么我们回到顶点，尝试第二个顶点、第三个顶点，以此类推。
2.广度优先搜索
在广度优先搜索中，我们想要回溯到尽可能远，以找到从最初的顶点出发的路径。因此栈不再是一个适合寻找较早路径的数据结构。我们采用队列来保存元素的顺序。
3.单源最短路搜索
最小行程次数的航线并不意味着是最短的总距离。最短路遍历必须说明在搜索过程中城市间的公里数(边权值的和)，而不是像深度优先搜索和广度优先搜索那样。我们想要检索离当前顶点最近的顶点，也就是说，与此顶点相连的边权值最小的顶点。我们称这种抽象容器位优先队列，被检索的元素是在队列中拥有最高优先度的元素。
8.7
许多子程序都是高级语言或语言附带库的一部分
参数列表：程序中两部分之间的通信机制
形参：列在子程序后的括号中的标识符
实参：子程序调用中列在括号中的标识符
8.7.2
传递参数的基本方式有两种：通过值传递和通过引用（地址）传递
如果一个形参是值参，调用单元将把实参的一个副本传递给子程序
如果一个形参是引用参数，调用单元将把实参的地址传递给子程序
第九章 面向对象设计与高级程序设计语言
9.1 面向对象方法
9.1.1 面向对象
对象：在问题背景中相关的事物或实体。
类：一组具有相似属性和行为的对象的描述。
域：类中的特定项，可以是数据或子程序。
方法：定义了类的一种行为的特定算法。
9.1.2 设计方法
集体讨论（第一阶段），过滤，场景（确定每个类的行为），责任算法(为列出的类的责任编写算法)
9.1.3 一个计算机示例
9.2 翻译过程
汇编语言输入汇编器
9.2.1 编译器
编译器：把高级语言编写的程序翻译成机器码的程序。
9.2.2 解释器
解释器：输入用高级语言编写的程序，指导计算机执行每个语句指定的动作的程序。
编译/解释
字节码：编译Java源代码使用的标准机器语言。
Java具有可移植性
Java编译器输出的程序将被解释而不是被执行。
Java程序总是被翻译成字节码而不是机器码。
9.3 程序设计语言的范型
范型：用作模式或模型的实体和一组假设、概念、值和实践，构成了共享它们的 聚合体 观察现实的方式，尤其适用于精神学科。
9.3.1 命令式范型
面向过程的范型
面向对象的范型
9.3.2 声明式范型
声明式范型是一个描述结果的模型，但是完成结果的过程则不被描述。
这种范型中有两种基本模型：函数式和逻辑式。
函数式模型：基于函数的数学概念。计算通过对函数求值来实现，而问题求解通过函数调用来实现。因此基本的原理是函数的求值，而不是变量和赋值语句。
Scheme是解释型语言，因此结果在声明后立即显示。
逻辑编程基于象征逻辑的原则。这个模型包括了一系列关于对象的事实和 一系列关于对象间关系的规则。
一个程序包括了向这些对象和关系询问可以通过事实和规则推演的问题。
解决潜在问题的算法用逻辑的规则来推演出事实和规则的答案。