2020-2021第一学期20202411《计算机科学概论》第四周自习总结
自习内容：《计算机科学概论》第8章 抽象数据类型与子程序 第9章 面向对象设计与高级程序设计语言
这两部分是对在程序设计层中对前两章的进一步延伸与拓展，通过自上而下的模型对程序的执行作一些初步的观察，并且引出高级语言。
第8章 抽象数据类型与子程序
我们使用的算法设计是自上而下的模型，一些抽象的容器被称为抽象数据类型（abstract data type）。
8.1 抽象数据类型
抽象数据类型（abstract data type，ADT）：属性（数据和操作）明确地与特定实现分离的容器。
可以从应用层、逻辑层和实现层来观察数据。应用层是特定问题中的数据的视图。逻辑层是数据值和处理他们的操作的抽象视图。实现层明确表示出了存放数据项的结构，并用程序设计语言对数据的操作进行编码。它们称为容器是因为它们存在的唯一目的就是存放其他对象。
数据结构（data structure）：一种抽象数据类型中的复合数据域的实现。
容器（container）：存放和操作其他对象的对象。
8.2 栈
栈是一种抽象复合结构，只能从一端访问栈中的元素。处理类型为LIFO（last in first out），即删除的项总是在栈中时间最短的项目。
8.3 队列
队列也是种抽象结构，队列中的项目从一端入，从另一端出。处理类型为FIFO（first in first out），即删除的总是在队列中时间最长的项目。
8.4 列表
列表有三个属性：项目是同构的，项目是线性的，列表是变长的。线性（linear）表示每个项目除了第一个都有一个独特的组成部分在它之前，除了最后一个也都有一个独特的组成部分在它之后。
链式结构（linked structure）：一个将数据项和找到下一项位置的信息保存到同一容器的实现方法。
列表可以形象化为链式结构。链式结构以节点的概念为基础。一个节点由两个部分构成：用户的数据和指向列表的下一个节点的链接或指针。
无序列表的顺序并不重要，项目只是随意被放入其中。
8.5 树
分层体系结构称为树。
二叉树（binary tree）：具有唯一起始节点（根节点）的抽象复合结构，其中每个节点可以有两个子女节点，根节点和每个节点之间都有且只有一条路径。
根（Root）：树中唯一的开始节点。
叶节点（leaf node）：没有子女的树节点。
从树的根节点开始，沿着跟的后续子树前进，直到找到了要找的项目或发现一个空子树为止。
8.6 图
图是由一组节点和连接节点的线段构成。
图（graph）：由一组节点和一组节点相互连接起来的边构成的数据结构。
顶点（vertex）：图中的节点。
边（弧）（edge（arc））：表示图中两个节点的连接的顶点对。
无向图（undirected graph）：其中的边没有方向的图。
有向图（directed graph（digraph））：其中的边是从一个顶点指向另一个顶点（或同一个顶点）的图。
邻顶点（adjacent vertice）：通过边连接起来的两个顶点。
路径（path）：连接图中两个顶点的一系列顶点。
列表、栈、队列和树都是可容纳元素的容器。顶点、边和权值可以被呈现在图上。
1.深度优先算法：用栈来存储访问的顶点。用深度优先搜索来检查第一个与起点相邻的顶点。如果是它是终点，则搜索结束。否则，检查所有与第一个顶点相邻的顶点。
2.广度优先搜索：用队列来保存元素的顺序。优先检查所有与起点相邻的顶点，而不是检查与这些顶点相邻的其他顶点。
3.单元最短搜索：被检索的元素是队列中拥有最高优先度的元素，称为优先队列（priority queue）。
8.7 子算法
参数列表（parameter list）：程序中两部分之间的通讯机制。
形参（parameter）：列在子程序名后的括号中的标识符。
实参（argument）：子程序调用中列在括号中的标识符。
传递参数的基本方式有两种，即通过值传递和通过引用（或地址）传递。
值参（value parameter）：由调用单元传入实参的副本（写在留言板上）的形参。
引用参数（reference parameter）：由调用单元传入实参的地址（写在留言板上）的形参。
支持它们的语言都标有值参和引用参数的语法。
第9章 面向对象设计与高级语言设计语言
高级语言是实现这些算法的正式算法，需要翻译程序把用高级语言编写的程序翻译成机器码。
9.1 面向对象方法
面向对象的设计方法是用叫作对象的独立实体生成解决方案的问题求解方法。面向对象设计（OOD）的底层概念是类（class）和对象（object）。
对象（object）：在问题背景中相关的事物或实体。
对象类（object class）或类（class）：一组具有相似的属性和行为的对象的描述。
字段（field）：表示类的属性。
方法（method）：定义了类的一种行为的特定算法。
设计方法：1.头脑风暴。2.过滤。3.场景。4。责任算法。5.总结。
封装（encapsulation）：把数据和动作集中在一起，使数据和动作的逻辑属性与它们的实现细节分离。
示例：1.问题。2.头脑风暴和过滤。3.责任算法。
9.2 翻译过程
用汇编语言编写的程序要输入汇编器，由它把汇编语言指令翻译成机器码，最终执行的是汇编器输出的机器码。
编译器（compiler）：把用高级语言编写的程序翻译成机器码的程序。
编译器是一种程序，要编译一个程序，就必须具有这个编译器在特定机器上的机器码版本。想要在多种类型的机器上使用一种高级语言，就要具备这种语言的多个编译器。
解释器（interpreter）：输入用高级语言编写的程序，指导计算机执行每个语句指定的动作的程序。
解释器在翻译过语句之后会立刻执行这个语句。
可植入性是Java最重要的特性。
字节码（bytecode）：编译Java源代码使用的标准机器语言。
字节码不是某个特定硬件处理器的机器语言，任何具有JVM的机器都可以运行编译过的Java程序。
9.3 程序设计语言规范
命令式范型：1.面向过程编程是一种命令式模型，在这里语句被分组为子程序。2.面向对象视角是与对象交互的一种方式。每个对象负责执行它自己的动作，在面向过程的反省中，数据被认为是被动并且被程序所操作的。
声明式范型：声明式范型是一个描述结果的模型，但是完成结果的过程则不被描述。有两种基本模型，即函数式和逻辑式。1.函数式模型基于函数的数学概念。2.逻辑编程基于数理逻辑的原则。
9.4 高级语言设计语言的功能性
两种伪代码结构——选择和重复（循环）是命令式语言的标志。
布尔表达式（Boolean expression）：一个标识符序列，标识符之间由相容的运算符分隔，求得的值是true或false。
只能在变量中存储合适的类型的要求叫作强化类型。数据类型是描述一组数值和一组可以应用在这种类型的数值上的基本操作。
强类型化（strong typing）：每个变量都有一个类型，只有这种类型的值才有存储到该变量中。
数据类型（data type）：一组值以及能够应用这种类型的值的基本操作集合的说明。
1.数据类型（整数、实数、字符、布尔型、字符串）。
声明（declaration）：把变量、动作或语言中其他实体与标识符关联起来的语句，使程序员可以通过名字引用这些项目。
保留字（reserved word）：一种语言中具有特殊意义的字，不能用它作为标识符。
区分大小写（case sensitive）：大写字母和小写字母被看作是不同的；两个拼写方法相同但大小写形式不同的标识符被看作是两个不同的标识符。
控制结构（control structure）：确定程序中的其他指令的执行顺序的指令。
根据结构化程序设计，程序中的每个逻辑单元都只能有一个入口和一个出口。
1.嵌套逻辑。
2.异步处理。
异步（asynchronous）：不与计算机中的其他操作同时发生，与程序的操作不同步。
9.5 面向对象语言的功能性
封装（encapsulation）：实施信息隐蔽的语言特性。
对象（问题求解阶段）（object（problem-solving phase））：与问题背景相关的事物或实体。
类（实现阶段）（class（implementation phase））：对象的模式。
6对象类或类（问题求解阶段）（object class or class（problem-solving phase））：属性和行为相似的一组对象的说明。
对象（实现阶段）（object（implementation phase））：类的一个实例。
实例化（instantiate）：创建类的对象。
继承（inheritance）：类获取其他类的属性（数据字段和方法）的机制。
超类是被继承的类，派生类是继承的类。类构成了继承体系结构。
多态（polymorphism）：语言在运行时确定给定调用将执行哪些可能的方法的能力。
9.6 过程设计与面向对象设计的区别
Q&A见小组讨论。