2020—2021—1学期20212306《网络空间安全导论》第四周学习总结

• 2020—2021—1学期20212306《网络空间安全导论》第四周学习总结
  • 学习内容：《计算机科学概论》第八，九章
  • 第八章：抽象数据类型与子程序
    • 8.1抽象数据类型
    • 8.2栈
    • 8.3队列
    • 8.4列表
    • 8.5树
      • 8.5.1二叉树
      • 8.5.2二叉检索树
      • 8.5.3其他操作
    • 8.6图
      • 8.6.1创建图
      • 8.6.2图算法
    • 8.7子程序
      • 8.7.1参数传递
      • 8.7.2值参与引用参数
  • 第九章：面向高级设计与高级程序设计语言
    • 9.1面向对象方法
      • 9.1.1面向对象
      • 9.1.2设计方法
      • 9.1.3示例
    • 9.2翻译过程
      • 9.2.1编译器
    • 9.3程序设计语言范型
      • 9.3.1命令式范型
      • 9.3.2声明式范型
    • 9.4高级程序设计语言的功能性
      • 9.4.3输入/输出结构
      • 9.4.4控制结构
    • 9.5面向对象语言的功能性
      • 9.5.1封装
      • 9.5.2类
      • 9.5.3继承
      • 9.5.4多态
    • 9.6过程设计与面对对象设计的区别
  • 总结与反思

学习内容：《计算机科学概论》第八，九章

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

本章，我们将进一步谈论抽象和抽象容器：我们不知道如何实现复合结构。同时将讨论更多关于子程序语句的内容，这也是一种代码反应设计的方式，也是算法和子算法通信的方式。

8.1抽象数据类型

抽象数据类型：属性(数据和操作）明确地与特定现实分离的容器。

为了把ADT的概念与上下文联系起来，需要看看如何观察数据。在计算机领域，可以从应用层，逻辑层，现实层这三个方面观察数据。
应用（或用户）层是特定问题中的数据的视图。
逻辑（或抽象）层是数据值（域）和处理他们的操作的抽象视图。
现实层明确表示出了存放数据项的结构，并用程序设计语言对数据的操作进行编码。这个视图用明确的数据域和子程序表示对象的属性。这一层涉及了数据结构

数据结构：一种抽象数据类型中的复合数据域的实现。

这一章的抽象数据类型是在现实世界的问题中反复出现过的，这些ADT是存储数据项的容器，每种ADT都具有特定的行为，称它们为容器。

容器：存放和操作其他对象的对象

8.2栈

栈是一种抽象复合结构，只能从一段访问栈中的元素。
LIFO（先进后出）：可以在第一个位置插入，也可以删除第一个元素。插入操作（Push推进）没有任何约束，整个LIFO行为都体现在删除操作（Pop弹出）上。
另一种访问栈的行为的说法是删除的项总是在栈中时间最短的项目。（这个角度观察栈就更加抽象。）
栈没有长度属性，所以没有返回栈中项目个数的操作。我们需要的是确定栈是否为空的操作，因为当栈空的时候再弹出项目会出错

8.3队列

队列也是一种抽象结构。队列中的项目从一端入，另一端出。称为FIFO，意思是先进先出。插入操作在队列的尾部进行，删除操作在队列的头部进行。
另一种描述队列的访问行为的说法是删除的总是在队列中时间最长的项目。

8.4列表

列表有三个属性：项目是同构的，项目是线性的，列表是变长的。
线性的意思是，每个项目除了第一个都有一个独特的组成部分在他之前，除了最后一个也都有一个独特的组成部分在他之后。
栈和列队对于删除操作都有全部定义，列表通常提供一个插入项目的操作，删除一个项目的操作，检索一个项目是否存在，以及报告列表中项目的数量。因为项目可以被删除和检索，所以列表中的项目必须能够相互比较。
不要把列表误认为是数组！！因为数组是内嵌结构，列表是抽象结构。然而列表运用于数组中。
列表也可以被形象化为链式结构，链式结构以节点的概念为基础，一个节点由两部分构成：用户的数据和指向列表的下一个节点的链接或指针。列表的最后一个节点的指针变量存放的是表示列表结束的符号，通常是null，用/表示。

链式结构：一个将数据项和找到下一项位值的信息保存到同一容器的实现方法。

无序列表的顺序并不重要，项目只是随意被放入其中。有序列表中，项目之间具有语义关系。除了第一个项目之外所有项目都存在某种排列关系。除了最后一个项目所有项目都有着相同的关系。

8.5树

列表，栈，列队这样的抽象结构本质上都是线性的，只模拟了一种数据关系，然而更复杂的关系需要更复杂的结构来表示。分类一般发生在高层，随着不断向下的移动，许多的节点，这种分层体系叫作树。在计算机领域，我们所说的通常是二叉树，即每个节点最多有两个子节点的树。

8.5.1二叉树

二叉树：具有唯一起始节点（根节点）的抽象复合结构，其中每个节点可以有两个子女节点，根节点和每个节点之间都有且只有一条路径。
根：树中唯一的开始节点。
叶节点：没有子女的树节点。

树的头部是一个起始节点，叫做根，它不是任何节点的子女。如果一个节点左边的子节点存在，那么这个子节点叫做左子女，反之右边的子节点存在，叫做右子女。如果一个节点没有子女。则这个节点叫做树叶。
此外，二叉树的定义还说明了根节点和每个节点之间有且只有一条路径，也就是说，除根节点外，每个节点都只有一个父母节点。根节点的每个子女本身又是一个小二叉树或子树的根。事实上，树中每个节点都可以被看作一个子树的根。根节点是树中其它所有节点的先辈。

8.5.2二叉检索树

二叉检索树具有二叉树的形状属性，还具有语义属性来刻画树中节点上的值，即任何节点的值都要大于他的左子树中所有节点的值，并且要小于它的右子树中的所有节点的值。
1.在二叉检索树中搜索
如果current指向一个节点，那么info（current）指的就是这个节点中的用户数据，left（current）指向的是current的左子树的根节点，right指向的是current右子树的根节点。null是一个特殊值，说明指针指向空值。因此，如果一个指针是null，那么这个子树就是空的。
二叉检索树的搜索效率与树的形状有直接关系。而树的形状又由项目插入树的顺序决定的。
2.构造二叉检索树
搜索算法为如何构造二叉搜索树提供了线索如果过在搜索路径中没有找到要找的项目，那么最后到达的就是这个项目应该在的位置。
3.输出二叉检索树中的数据
要输出根的值，必须先输出它的左子树中的所有值，即所有比根的值小的值。输出了根的值后，还必须输出他的右子树中的所有值，即所有比根的值大的值。
这个算法似乎很容易，这就是递归算法的妙处：简短精致。

8.5.3其他操作

二叉检索树其实是和列表具有同样功能的对象，他们的区别在于操作的有效性，而行为是相同的。

8.6图

树是表示存在层次结构关系的一种有效方式，也就是说，一个节点至多只有一个指向它的节点。如果去掉这种约束，就得到了另一种数据结构————图。图由一组节点和连接节点的线段构成，图中的节点叫做顶点，图中的线段叫做边（弧）。

图：由一组节点和一组把节点相互连接起来的边构成的数据结构。
顶点：图中的节点。
边（弧）：表示图中两个节点的连接的顶点对。

图中的顶点表示对象，边则描述了顶点之间的关系。图有两种:

无向图：其中的边没有方向的图。
有向图：其中的边是从一个顶点指向另一个顶点（或同一个顶点）的图。

如果两个顶点有一条边相连，则把它们称为领顶点，两个顶点通过一条有顺序的路径相连。

8.6.1创建图

列表，栈，队列和树都是可容纳元素的容器。用户根据特定的问题选择最合适的容器，不被纳入检索过程的算法是没有固定语义的；栈返回的元素是在其中停留最少的元素，队列返回的是在其中停留时间最长的元素。队列和树返回的信息都是被请求的。然而不同的是，在图中定义的算法可以解决实际问题。

8.6.2图算法

1.深度优先搜索
当我们试图在两个顶点间寻找路径时，用栈来存储访问顶点。用深度优先搜索来检查第一个与起点相邻的顶点。如果他是终点，则搜索结束。否则，检查所有与第一个顶点相邻的顶点。因为我们想要沿着一条路径尽可能深地访问各个节点，如果没有找到终点则回溯，因此栈是一种存储顶点的适合的数据结构。
我们不能多次处理同一个顶点。
这种搜索叫做深度优先搜索，因为我们走向最深的分支。但你必须回溯时，选择离你无法走通位置的最近的分支继续搜索。相比于更早时候可选的其他分支，你会选择一条尽可能可以走远的路。
2.广度优先搜索
在广度优先搜索中，我们想要回溯到尽可远，以找到从最初顶点出发的路径，因此栈不再是一个适合寻找较早路径的数据结构。
广度优先搜索会优先检查所有与起点相邻的顶点，而不是检查与这些项目的其他顶点。
3.单源最短路径搜索
我们需要辅助的数据结构存储此后处理的城市，最后广度优先搜索算法可以找到最小换成次数的航线。但是这并不代表最短的总距离。最短路遍历必须说明在搜索过程中城市间的距离，而不是像深度优先搜索和广度优先搜索一样。我们想要检索当前顶点最近的顶点，也就是与此顶点相连的边权值最小的顶点。我们称这种抽象容器为优先队列，被检索的元素是在队列中拥有最高优先度的元素，比如这里，我们就让距离数最为优先，则可以弹出一系列包括两个顶点和两个顶点间距离的元素.

8.7子程序

许多子程序都是高级语言或语言附带库的一部分。只需要查询计算该值的子程序的名字，然后调用该子程序来进行计算即可。

8.7.1参数传递

参数列表是子程序要使用标识符或值的列表，它放置在子程序名后的括号中。由于子程序是在被调用之前定义的，所以它不知道调用单元会传递什么样的变量。为了解决这个问题，在子程序后面的括号中声明了一个变量名的列表。这些标识符称为形参。当子程序被调用时，调用单元将列出子程序名，并在其后的括号中列出一系列标识符，这些标识符叫做实参。实参表示的是调用单元中的真实变量。

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

当动作执行时，实参将逐个代替形参。子程序将在留言板上第一个位值查看它的第一个形参，在第二个位置察看它的第二个形参。调用子程序时传递的实参个数必须与子程序定义中的形参个数相同。

8.7.2值参与引用参数

传递参数的基本方式有两种，即通过值传递和通过引用传递。如果一个形参是值参，调用单元将把实参的一个副本传递给子程序。如果一个形参是引用参数，调用单元将把实参的地址传给子程序。所以子程序不能改变实参内容（因为接受的只是一个副本），相反，子程序可以改变调用单元传递给引用参数的任何实参，因为子程序操作的是实际变量，而不是副本。

值参：由调用单元传入实参的副本的形参。
引用参数：由调用单元传入实参的地址的形参。

第九章：面向高级设计与高级程序设计语言

面向对象的设计是审视设计过程的另一种方式它从数据角度出发而非任务。

9.1面向对象方法

9.1.1面向对象

在面向对象的思想中，数据和处理数据的算法绑在一起，因此每个对象负责自己的处理，面向对象设计的底层概念是类和对象。

对象：在问题背景中相关的食物或实体
对象类或类：一组具有相似的属性和行为的对象的描述
字段：表示类的属性
方法：定义了类的一种行为的特定算法

类是一种模式，说明了对象是什么以及他的行为

9.1.2设计方法

有四个阶段
1.头脑风暴：确定问题中类的第一个阶段
头脑风暴是一种集体问题求解的方法，包括集体中的每个成员自由发言。
2.过滤：过滤保留下来的类将在下一阶段仔细研究。
3.场景：该阶段将确定每个类的行为。目标是给每个类分配责任，最终责任将实现为子程序。

封装：把数据和动作集中在一，使数据和动作的逻辑属性与他们的实现细节分离。封装是抽象的关键

责任的类型有两种，即类必须知道什么（知识）和类必须能够做什么（行为）。
4.责任算法：执行责任的算法一般都相当短
5.总结：自顶向下的设计方法重点在于把输入转化成输出的过程，结果将生成任务的体系结构。面向对象设计的重点是要转换的数据对象，结果生成的是对象的体系结构。

9.1.3示例

面向对象的设计比自顶向下额设计更好，因为他创建的一些类还可以用于其他背景。可复用性是面对对象设计的一大优点。为一个问题涉及的类还可以用于解决另一个问题，因为每个类都是自约束的，也就是说，每个类只负责自己的行为。

9.2翻译过程

在研究高级语言之前，我们先来看看工具的基本功能。

9.2.1编译器

编译器翻译用高级语言编写的程序的程序。随着科学家更加深入地了解翻译过程，编译器变得复杂，汇编语言的阶段通常被省略了
任何计算机只要具有一种高级语言的编译器，就能运行这种语言编写的程序。要编译一个程序就必须具有这个编译器在特定机器上的机器码版本，想要在多种类型的机器上使用一种高级语言，就要具有这种语言的多个编译器。
9.2.2解释器

解释器：输入永高及语言编写的程序，知道计算机执行每个语句指定的动作的程序。

解释器与汇编器和编译器不同，他在翻译过语句之后会立即执行着这种语句。
第二代高级语言可分为两种：一种是需要编译的，一种是需要解释的
因为需要解释的语言编写的程序通常比要编译的程序的运行速度慢很多，所以要编译的语言发展成了主流，于是产生了Java。在Java的设计中，可移植性是最重要的特征。为了达到最佳可移植性，Java被编译成一种标准的机器语言————字节码。

字节码：编译Java源代码使用的标准机器语言

标准化的高级语言实现的可移植性与把Java程序翻译成字节码然后在JVM上解释它所实现的可移植性是不同的。Java编译器输出的程序将被解释，而不是直接被执行。

9.3程序设计语言范型

什么是范型？“用作模式或模型的实体”和“一组家属。概念。值和实践，构成了共享他们的聚合体观察现实方式，尤其适用于精神学科”

9.3.1命令式范型

具有顺序执行指令的特征。变量的使用代表了内存地址，而使用赋值语句则改变这些变量的值。
1.面向过程的范型
面向过程编程是一种命令式模式，在这里语句被分组为子程序。一个程序是子程序分层构成的，每一层执行整个问题求解的一个必要的特定任务。
2.面向对象的范型
面向对象视角是与对象交互的一种方式，每个对象负责执行它自己的动作。
在面向过程的范型中，数据被认为是被动并且被程序所操控的，数据对象是活跃的。每个对象负责控制自己的操作。

9.3.2声明式范型

声明式范型是一个描述结果的模型，但是完成结果的过程则不被描述。
该范型中的两种基本模型：函数式和逻辑式。
1.函数式模型
基于函数的数学概念，基本的原理是函数的求值。
2.逻辑编程
基于数理逻辑的原则，解决潜在问题的算法用逻辑的规则来推演出事实和规则的答案。

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

命令式语言的标志就是两种伪代码结构——选择和重复（循环）。
1.布尔表达式
布尔表达式是一个标识符序列，标识符之间由相容的运算符分隔，球的的值是true和false。
2.数据归类
强类型化：只能在变量中存储适合的类型的要求。
数据类型：描述一组数值和一组可以应用在这种类型的数值上的基本操作
大多数高级语言都有四种数据类型：整数实数字符和布尔型
声明：把变量动作或言语中的其他实体与标识符关联起来的语句，使程序言可以通过名字引用这些项目。
保留字：一种语言中具有特殊意义的子，不能用他作为标识符

9.4.3输入/输出结构

高级语言把输入文本的数据看做一个分为多行的字符流。
字符的含义由存放值的内存单元的数据类型决定输出与基础所有输入语句都由三部分构成：要存放数据的变量的声明、输入语句和要读入的变量名以及数据流自身。
在非强类型语言中，输入格式决定了类型。
输入语句创建字符流。在强类型语言中不管输入输出语句的语法或输入输出流在哪，处理的关键在于数据类型。数据类型确定字符是如何被转换为位模式以及如何被转换为字符。

9.4.4控制结构

重复选择和子程序，这种结构叫做控制结构。（他们决定了其他指令在程序中被执行的顺序）
1.嵌套逻辑。选择语句可以在循环结构中被嵌套，循环结构可以在选择语句被被嵌套（同选择，循环语句和子程序）
2.异步处理。

异步：不与计算机这种的其他操作同时发生。换句话说，与程序的操作不同步

9.5面向对象语言的功能性

面向语言对象的基本构造是类
对象语言中三个必要组成成分：封装，继承和多态。

9.5.1封装

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

9.5.2类

实例化：创建类的对象

默认情况下，类中的字段是私有的，也就是说，除非某一个类的字段被标识为公有，否则任何其他对象都不能访问这个类的对象的字段。

9.5.3继承

继承：获取其他类的属性的机制

继承通过允许应用程序使用已经被测试过的类和从一个类中继承应用所需的属性来促进重用。

9.5.4多态

多态：语言在运行时确定给定调用执行哪些可能的方法的能力。

9.6过程设计与面对对象设计的区别

在面向过程的版本中，列表被呈现为传递给子程序的记录，以便子程序可以对其操作。
操作他的数据结构和子程序是用户程序的一部分。在面向对象的版本中，类对象的实现通过封装实现对用户的隐藏。

总结与反思

第八章，第九章的部分概念难以理解。在学习过程中，要广泛查找资料，认真看每一个字，弄清楚每一个词才能理解书中到底要表达什么，一个概念不理解或是一个词没弄明白，对接下来的阅读都会有极大的影响。