2019-2020-1学期 20192415
《网络空间安全专业导论》第四周学习总结
第八章 抽象数据类型与子程序
8.1 抽象数据类型
抽象数据类型（Abstract Data Type,ADT）:属性（数据与操作）明确地与特定现实分离的容器
容器（container）：存放和操作其他对象的对象
数据结构（data structure）：一种抽象数据类型中的复合数据域的实现
用户层：特定问题中数据的视图
逻辑层：数据值（域）和处理它们的操作的抽象视图
实现层：明确表示出了存放数据项的结构，并用程序设计语言对数据的操作进行编码
（用明确的数据和子程序表示对象的属性，涉及数据结构）
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 列表
-
列表的列是无止境的
-
列表有三个属性特征：项目是同构的，项目是线性的，列表是变长的
-
插入（Insert）,删除（Delete），检索（IsThere）,报告（GetLength）
-
项目可以被删除和检索，所以列表中的项目必须能够相互比较
-
列表≠数组：
数组是内嵌结构 列表是抽象结构 列表应用于数组中 -
可被形象化为链式结构
链式结构（linked structure）:一个将数据项和找到下一项位置的信息保存到同一容器的实现方法 -
无序列表
-
有序列表：项目之间具有语序关系
8.5 树
分层体系结构
8.5.1 二叉树
二叉树（binary tree）：具有唯一起始节点的复合抽象结构，其中每个节点可以有两个子女节点，根节点和每个节点之间都有且只有一条路径
子女：每个节点可以有两个后继节点
根（root）:树中唯一的开始节点
叶节点（leaf node）:没有子女的树节点
8.5.2 二叉检索法
搜索→构造→输出
任何节点的值都要大于它的左子树中的所有节点的值，并且要小于它的右子树中的所有节点的值
current→节点
iofo（current）→用户数据
left(current)→左子树根节点
right(current)→右子树根节点
null→空值
二叉检索法的搜索效率与树的形状有关
要输出根的值，必须先输出所有比根的值小的值；输出了根的值后，还必须输出所有比根的值大的值。
（×）此句话为翻译错误
8.6 图
图（garph）:由一组节点和一组把节点相互连接起来的边构成的数据结构
顶点（vertex）:图中的节点
边（弧）（edge(arc)）:表示图中两个节点的连接的顶点对
无向图（undirected graph）:其中的边没有方向的图
有向图（directed graph(disgraph)）:其中的边是从一个顶点指向另一个顶点（或同一个顶点）的图
加权图表示有附加值的图
用数学语言讲，设G为图，对图的每一条边e来说，都对应于一个实数W(e)（可以通俗的理解为边的“长度”，只是在数学定义中图的权可以为负数），我们把W（e）称为e的“权”。把这样的图G称为“加权图”。
邻顶点（adjacent vertice）:通过边连接起来的两个顶点
路径（path）:连接图中两个顶点的一系列顶点
8.6.1 创建图
8.6.2 图算法
- 深度优先搜索
栈是一项存储顶点的合适的数据结构。
检查第一个与起点相邻的顶点，若非终点则检查所有与第一个顶点相邻的顶点。
沿着一条路径尽可能深地访问各个节点，如果没有找到终点则回溯。
必须回溯时，选择离你无法走通位置最近的分支继续搜索。
- 广度优先搜索
想要回溯到尽可能远，以找到最初的顶点出发的路径。
栈是按照元素出现的相反的顺序来保存元素。
- 单源最短路搜索
8.7 子程序
许多子程序都是高级语言或语言附带库的一部分。
8.7.1 参数传递
参数列表（parameter list）:程序中两部分之间的通信机制
形参（paramter）:列在子程序名后的括号中的标识符
看作子程序中使用的临时标志符，定义子程序中的动作。
实参（argument）:子程序调用中列在括号中的标识符
实参表示的是调用单元中的真正变量。
调用子程序时传递的实参个数必须与子程序中定义的形参个数相同。二者根据位置匹配。
8.7.2 值参与引用参数
传递参数的基本方式：值传递/引用（地址）传递
值参（value parameter）：由调用单元传入实参的副本（写在留言板上）的形参
引用参数（reference parameter）:由调用单元传入实参的地址（写在留言板上）的形参
第九章 面向对象设计与高级程序设计语言
9.1 面向对象方法
9.1.1 面向对象
9.1.2 设计方法
- 集体讨论
产生暂时列表
- 过滤
相同的类，有共同属性和行为的类，不属于问题的解决方案的类→过滤
- 场景
给每个类分配场景，责任将被实现为子程序
封装（encapsulation）:把数据和动作的逻辑属性与它们的实现细节分离
- 责任
在面向对象的设计观念，重点是数据而不是动作
9.2 翻译过程
9.2.1 编译器
9.2.2 解释器
解释器：输入用高级语言编写的程序，知道计算机执行每个语句指定的动作的程序。
与汇编器和编译器只是输出机器码且机器码在单独执行不同的是，解释器在翻译过语句之后会立即执行这个语句。可以把解释器看作理解编写程序所使用语言的模拟器或虚拟机。
第二代高级语言可以分为两种，一种是要编译的，一种是要解释的。FORTRAN、COBOL和ALGOL是要编译的语言；Lisp、SNOBOL4和APL是要解释的语言。
为了达到最佳可移植性，Java被编译成一种标准机器语言--字节码
字节码(bytecode):编译Java源代码使用的标准机器语言。
存在标准的机器语言是因为：一种名为JVM(Java虚拟机)的软件解释器接受字节码程序，然后执行它。也就是说，字节码不是某个特定硬件处理器的机器语言，任何具有JVM的机器都可以运行编译过的Java程序。
JVM：为执行字节码程序设计的假想机。
9.3 程序设计语言的范型
范型:用作模式或模型的实体
两种主要范型：命令式
声明式
9.3.1 命令式范型
FORTRAN、BASIC、C、Pascal和C++都是命令式范型。
这些命令式范型具有顺序执行指令的特征，变量的使用代表了内存地址，而使用的赋值语句则改变这些变量的值。
-
面向过程的范型：
面向过程编程是一种命令式模型，在这里语句被分组为子程序。
编写子程序并通过向其传递所需数据来完成他们的功能。
在面向过程的范型中，数据被认为是被动并且被程序所操控的。
-
面向对象的范型
面向对象视角是对象交互的一种方式。每个对象负责执行它自己的动作。
在面向对象的范型中，数据对象是活跃的。对象和操作对象的代码绑定在一起，使得每个对象负责控制自己的操作。
SIMULA和Smalltalk是最先支持面向对象编程的语言。 Java和Python是两种新式的面向对象编程语言。
封装、继承、多态是面向对象的范式的三个特点。###
9.3.2 声明式范型
声明式范型是一个描述结果的模型，但是完成结果的过程则不被描述。
在这种范型中有两种基本模型：函数式和逻辑式。
1.函数式模型：基于函数的数学概念。计算通过对函数的求值来实现，二问题求解通过函数调用来实现。
最常见的函数范型语言是Lisp、Scheme(Lisp的一种衍生语言)和ML。
2.逻辑编程：基于象征逻辑的原则。这个模型包括了一系列关于对象的事实和一系列关于对象间关系的规则。
一个程序包括了向这些对象和关系询问可以通过事实和规则推演的问题。
3.PROLOG是第三代逻辑编程语言，包含三种语句：
一种声明了对象及对象之间关系的事实；
一种定义了对象及对象之间关系的规则；
第三种询问对象及对象之间关系的问题。
在PROLOG系统中，常量以小写字母开头，变量以大写字母开头。事实上，我们以一个常量代替一个变量来询问事实真相。
9.4 高级程序设计语言的功能性
两种伪代码结构--选择和重复(循环)是命令式语言的标志。
9.4.1 布尔表达式
1.布尔表达式(Boolean expression):一个标识符序列，标识符之间由相容的运算符分隔，求得的值式true或false。
2.一个布尔表达式可以是：
一个布尔变量
一个算术表达式加一个关系运算符，再加一个算术表达式
一个布尔表达式加一个布尔运算符，再加一个布尔表达式
3.布尔变量是内存中的一个地址，由存放true或false的标识符引用。
4.关系运算符是比较两个值的运算符。
5.两个算术表达式之间的关系运算符是询问两个表达是之间是否存在这种关系，例如：xValue<yValue是一个断言，即xValue小于yValue。如果xValue确实小于yValue，那么这个表达式的结果是true；如果xValue大于或等于yValue，那么结果为false。
9.4.2 数据归类
1.强类型化(strong typing):每个变量都有一个类型，只有这种类型的值才能存储到该变量中。
2.数据类型(data type):一组值以及能够应用于这个类型的值的基本操作集合的说明。
3.大多数高级语言都固有四种数据类型，即整数、实数、字符和布尔型。
整数：整数数据类型表示的是一个整数值的范围，这个范围由表示整数值的字节数决定。有些高级语言提供几种范围不同的整数类型，允许用户根据特定问题选择最适合的类型。应用于整数的操作是标准的算术运算符和关系运算符。
实数：实数数据类型表示的是特定精度的数的范围，与整数数据类型一样，这个范围由表示实数值的字节数决定。许多高级语言有两种大小的实数。
布尔型：布尔数据类型只有两个值--true和false。还可以为布尔变量指定一个布尔表达式。
整数、实数和布尔型称为简单数据类型或原子数据类型，因为每个值都是独立的，不可再分割。
字符串：一个字符序列，在某些语言中这个序列通常被看作一个数据值。
我们使用单引号圈起字符，用双引号圈起字符串。有些高级语言可以采取同样的符号圈起字符和字符串。
声明(declaration):把变量、动作或语言中的其他实体与标识符关联起来的语句，使程序员可以通过名字引用这些项目。
4.保留字(reserved word):一种语言中具有特殊意义的字，不能用它作为标识符。
5.C++、Java、python和VB.NET是区分大小写的。
6.区分大小写(case sensitive):大写字母和小写字母被看作是不同的；两中拼写方法相同但大小写形式不同的标识符被看作是两个不同的标识符。
7.C++和Java用分号来结束语句。VB.NET则利用一行的节为或者注释符号来结束语句。
9.4.3 输入/输出结构
9.4.4 控制结构
1.控制结构(control structure)：确定程序中的其他指令的执行顺序的指令。
2.嵌套逻辑：在任何控制语句中被执行或跳过的语句可以是简单的语句或块(一组语句)，对于这些语句没有任何限制。
事实上，被跳过或重复的语句可以包含一个控制结构。选择语句可以在循环结构中被嵌套。循环结构可以在选择语句中被嵌套。选择和循环语句可以子啊子程序中被嵌套，而子程序可以在循环或选择结构中被嵌套。
3.异步处理：程序必须识别用户点击鼠标的行为，处理该点击然后继续运行。
异步(asynchronous):不与计算机中的其他操作同时发生；换句话说，与计算机的动作不同步。
异步处理也叫事件驱动处理。
9.5 面向对象语言的功能性
1.封装(encapsulation)：实施信息隐蔽的语言特性。
对象类或类(问题求解阶段)(object class or class(problem-solving phase))：属性和行为相似的一组对象的说明。
对象(问题求解阶段)(object(problem-solving phase))：与问题背景相关的事物或实体。
对象(实现阶段)(object（implementation phase))：类的一个实例。
类(实现阶段)(class（implementation phase))：对象的模式。
实例化(instantiate)：创建类的对象。
2.继承(inheritance)：类获取其他类的属性（数据域和方法）的机制。
3.多态(polymorphism)：一种语言的继承体系结构中具有两个同名方法且能够根据对象应用合适的方法的能力。