2020-2021 1学期20212329《计算机科学概论》第四周学习总结
第八章 抽象数据类型与子系统
8.1 抽象数据类型（ADT）
属于（数据和操作）明确地与特定实现分离的容器。
应用层是特定问题中的数据的视图。
逻辑层是数据值（域）和处理它们操作的抽象视图。
实现层明确表示出了存放数据项的结构，兵勇程序设计语言对数据的操作进行编码。
这个视图用明确的数据域和子程序表示对象的属性。这一层涉及了数据结构
数据结构：一种抽象数据类型中的复合数据域的实现。
这一章介绍的抽象数据类型是在现实世界的问题中反复出现过的。这些ADT是存储数据的容器，每种ADT都具有特定的行为。称它们为容器
容器：存放和操作其他对象的对象。
8.2 栈
栈是一种抽象复合结构，只能从一端访问栈中的元素第一个位置可插入和删除一个元素（后进先出）称作LIFO
插入操作没有任何约束，整个LIFO行为都体现在删除操作上。
8.3 队列
抽象结构，队列中的项目从一端入另一端出。（先进先出）称为FIFO
插入操作没有任何约束，整个FIFO行为都体现在删除操作上。
插入和删除没有标准的相关术语
插入：Enqueue、Enque、Enq、Enter和Insert
删除：Dequeue、Deque、Deq、Remove和Delete
8.4 列表---链式结构
属性特征：项目是同构的，项目是线性的，列表是变长的。
提供操作：Insert、Delete、IsThere、GetLength
区分列表与数组：数组是内嵌结构，列表是抽象结构，列表应用于数组中。
链式结构：一个将数据项和找到下一项位置的信息保存到同一容器的实现方法。
以节点的概念为基础，节点由用户的数据和指向列表的下一个节点的链接或指针。
列表的最后一个节点的指针变量存放的是表示列表结束的符号，通常表示为null，用/表示
有序列表项目之间具有语义关系
除了第一个项目--所有项目存在某种排序关系
除了最后一个项目--所有项目都有着相同的关系
8.5 树
动物阶级关系--分层体系结构--树--二叉树
8.5.1 二叉树
抽象结构，每个节点最多有两个子节点的树。后继节点称为子女。起始节点称为根。
左子女 右子女
仅有一个节点时，它的位置可选择且固定。
节点的子女数=0---树叶---叶节点
树中的每一个节点都可以被看作一个子树的根
先辈，子孙：子孙=子女+子女的子女---根节点是树中所有其他节点的先辈。
8.5.2 二叉检索树
语义属性刻画树中节点上的值--任何节点上的值大于它的左子树中所有的节点的值，小于它的右子树中所有结点的值
二叉树的两种变体
构造二叉检索树--从根到叶
输出二叉检索树中的数据（如何做到输出根的值？）
递归算法
8.5.3 其他操作
二叉树与列表具有相同功能，区别在于操作有效性。
忽略了Length的概念----算法计算树中的节点数
递归定义
8.6 图
去除约束（一个节点至多有一个指向它的节点）---图：由一组节点和连接节点的线段构成。节点成为顶点，线段称为边（弧）
无向图：边没有方向 有向图：边是从一个顶点指向另一个顶点
邻顶点：有一条边相连
路径：连接图中两个顶点的一系列顶点
8.6.1 创建图
8.6.2 图算法
深度优先：在两个顶点之间寻找路径：用栈来存储访问的顶点，用深度优选搜索来检查第一个与起点相邻的顶点（是终点则结束）
同时存储其他和起点相邻的顶点，逐一尝试。
广度优先：最少停顿次数，按照元素出现的相反顺序来保存元素
单源最短路：权值和最小。
8.7 子程序
8.7.1 参数传递
参数列表是子程序要使用的标识符或值的列表，放置在子程序名后的括号中。
参数列表:程序中两部分之间的通信机制。
形参：列在子程序名后的括号中的标识符
实参：子程序调用中列在括号中的标识符
8.7.2 值参与引用参数
传递参数基本方式：通过值传输和通过引用（地址）传输
值参：由调用单元传入实参的副本的形参
引用参数：由调用单元传入实参的地址的形参
访问值参子程序只需访问留言板自身内容，访问引用参数子程序必须访问留言版上列出的地址中的内容。
值参和引用参数的区别
第九章 面向对象设计与高级程序设计语言
9.1 面向对象方法
对象由数据和处理数据的操作构成。面向对象设计的重点是对象以及它们在问题中的交互。求解策略将应用于数据，而不是任务。
-9.1.1 面向对象
对象是在问题背景中具有意义的事物或实体。
对象类（类）是一组具有相似的属性和行为的对象的描述。
求解时需要把问题中的类隔离开来。对象之间通过发送消息（调用其他对象的子程序）进行通信。
类中包含的字段表示类的属性。
方法是处理对象中的数据值的指定算法。
-9.1.2 设计方法
分解过程有四个阶段：头脑风暴、过滤、场景、责任算法
1.头脑风暴：集体问题求解的方法，集思广益，集体行为
2.过滤：出现有共同属性和行为的类将其组合
3.知道什么和类必须能够做什么。类把它的数据封装了起来使得一个类的对象不能直接访问另一个类中的数据。
封装：把数据和动作集中起来，使数据和动作的逻辑属性与它们的实现细节分离。
4.责任算法
-9.1.3 示例
9.2 翻译过程
-9.2.1 编译器
把用高级语言编写的程序翻译成机器码的程序。
-9.2.2 解释器
输入用高级语言编写的程序，知道计算机执行每个语句指定的动作的程序。
9.3 程序设计语言范型
-9.3.1 命令式范型
1.面向过程
2.面向对象
-9.3.2 声明式范型
1.函数式模型
2.逻辑编程
9.4 高级程序设计语言的功能性
-9.4.1 布尔表达式
一个标识符序列，标识符之间由相容的运算符隔开，求得的值是true或false
运算符符号
-9.4.2 数据归类
强化类型：每个变量都有一个类型，只有这种类型的值才能存储到该变量中。
数据类型：整数，实数，字符串，布尔型。
-9.4.3 输入/输出结构
-9.4.4 控制结构
1.嵌套逻辑
2.异步处理
异步：不与计算机中的其他操作同时发生。
9.5 面向对象语言的功能性
-9.5.1 封装
封装：实时信息隐蔽的语言特性
-9.5.2 类
-9.5.3 继承
类获取其他类的属性的机制
-9.5.4 多态
语言在运行时确定给定调用将执行哪些可能的方法的能力。