Skip to content

Latest commit

 

History

History
1166 lines (600 loc) · 52.4 KB

computer_science.md

File metadata and controls

1166 lines (600 loc) · 52.4 KB

原则和思想

1. 计算机的三大原则

  • 输入、运算、输出是硬件的基础
  • 软件是指令和数据的集合
  • 计算机用数字表示所有信息（严格遵守规则和指令）

计算机是执行程序的机器，程序是指令和数据的集合。

指令，就是控制计算机进行输入、运算、输出的命令。把向计算机发出的指令一条条列出来，就得到了程序。函数就是一组指令的名字。语句、方法、子例程、子程序也都可以用来指代一组指令。

程序中的数据分为两类，一类是作为指令执行对象的输入数据，一类是从指令的执行结果得到的输出数据。在编程时程序员会为数据赋予名字，称其为变量。

无论使用哪种开发方法，编写出来的程序其内容最终都会表现为数值的罗列，其中的每个数值要么表示“指令”，要么表示作为指令操作对象的“数据”。程序最终就是指令与数据的集合。

在非 OOP 语言中，用函数表示指令，用变量表示数据，程序就是函数和数据的集合。

2. 计算机系统结构中的八大思想

面向摩尔定律的设计

摩尔定律（Moore’s Law）指出，单芯片上的集成度每 18 至 24 个月翻一番。因此，计算机设计者必须预测其设计完成时的工艺水平。

使用抽象简化设计

使用抽象（abstraction）来表示不同的设计层次，是提高硬件和软件生产力的主要技术之一。通过抽象隐藏了复杂性，即在高层次中看不到低层次中的细节，只能看到一个简化的模型。

抽象原理是理解现代计算机系统的基础，硬件和软件的设计都采用分层的的方法构建计算机系统，下层对其上层隐藏本层的实现细节。

指令集体系结构是硬件和软件之间的接口，属于最重要的一个抽象层次。而过程（procedure）或函数是软件中实现抽象的一种方法，参数的角色是作为过程与其他程序、数据之间的接口。

加速大概率事件

加速大概率事件（common case fast）比优化小概率事件更能提高性能。

比如 MIPS 将寄存器$zero恒置为 0 这种根据使用频率来确定要定义的常数的方法。

通过并行提高性能

通过流水线提高性能

通过预测提高性能

存储器层次

通过冗余提高可靠性

硬件设计的三条基本原则

  • 简单源于规整
  • 越小越快
  • 优秀的设计需要恰当的折中

硬件： 计算机的组成

计算机内部主要由被称作IC 的元件组成，核心的只有三种：CPU（处理器）、内存和I/O。只要用电路把CPU、内存以及I/O 上的引脚相互连接起来，为每块IC 提供电源，再为CPU 提供时钟信号，硬件上的计算机就组装起

来了。

CPU （Central Processing Unit，中央处理器）是计算机的大脑，负责解释、执行程序，在其内部可对数据执行运算并控制内存和I/O。通常用Hz 来表示驱动CPU 运转的时钟信号的频率。1秒发出1 次时钟信号就是1Hz，

内存用于存储指令和数据。

I/O （Input/Output，输入／输出）负责把键盘、鼠标、显示器等周边设备和主机连接在一起，实现数据的输入与输出。

2.2 步骤

  • 连接电源、数据和地址总线
  • 连接 I/O
  • 连接时钟信号
  • 连接用于区分读写对象是内存还是 I/O 的引脚
  • 连接剩余的控制引脚
  • 连接外部设备，通过 DMA输入程序
  • 连接用于输入输出的外部设备
  • 输入测试程序并进行调试

电阻值计算

将金色或银色的色环放到右手边，然后从左边开始依次读出剩余3 个色环的颜色。从左侧开始数，第3 位的数字表示10 的次方数。

电阻颜色代码 0~9 分别对应 黑棕红橙黄绿蓝紫灰白。误差等级：银色代表±10%，金色±5%。

软件：程序设计

3. 汇编

4. 程序流程 - 程序是流动的

Flow Chart

表示程序流程（Flow）的图（Chart）就是流程图（Flow Chart），流程图不依赖于特定编程语言。

可以画流程图来思考算法。思考算法时要分两步：

  1. 整体考虑程序的粗略流程（初始化处理→循环处理→收尾处理）

  2. 考虑程序各个部分细节的流程

基本的程序流程

  • 顺序执行

    按照指令记录在内存中的先后顺序依次执行，PC 寄存器的值会自动更新（最基本的程流程）。

  • 条件分支 - 比较后跳转

    根据若干个条件的成立与否，在程序的流程中产生若干个分支。

  • 循 环 - 比较后跳转

    在程序的特定范围内反复执行若干次。

    条件分支和循环，在高级语言中用「程序块」表示，在机器语言和汇编语言中用「跳转指令」表示，在硬件上通过把PC 寄存器的值设为要跳转到的目的地的内存地址实现。如果将将PC 寄存器的值设置设为之前执行过的步骤所对应的内存地址，就构成了循环。如果设置为尚未处理的步骤对应的内存地址，就是条件分支。

结构化程序设计

使用程序块表示程序流程：仅使用顺序执行、条件分支和循环表示程序的流程，不再使用跳转指令。

在硬件层面，条件分支和循环都必须使用跳转指令实现。但是，高级语言使用了程序块作为跳转指令的抽象，即使不使用跳转语句，程序的所有流程仍然可以表述出来。而使用跳转指令会使程序流程状态复杂，就像意大利面条一样。

结构化异常处理：用程序块来表示这种错误处理方式的机制，如 try～Catch。

特殊的程序流程

  • 中断处理（Interrupt）- 特殊的条件分支

    由于外部的原因使正常的流程中断，中断后再返回到之前流程的过程就是中断处理流程。中断处理是指计算机使程序的流程突然跳转到程序中的特定地方，即跳转到中断处理例程（Routine）或是中断处理程序（Handler）。中断处理以从硬件发出的请求为条件，使程序的流程产生分支，因此中断处理是一种特殊的条件分支。

    中断处理中的跳转是通过CPU 所具备的硬件功能实现的，即计算机具有硬件上处理中断的能力，处理中断请求的程序内置于被烧录在计算机ROM 中BIOS 系统或操作系统中。

  • 事件驱动（Event Driven）- 特殊的条件分支

    事件驱动

    事件（Event）是指用户在应用程序中点击鼠标或者敲击键盘等操作。应用程序则根据事件的类型做出相应的处理。这种机制就是事件驱动。即用户的操作等产生事件后，由事件决定程序的流程。可以把事件驱动理解成是两个程序在对话。

    事件驱动也是一种特殊的条件分支，它以从操作系统送来的通知为条件，根据通知的内容决定程序下一步的流程。

    事件驱动是一种适用于GUI 环境的编程风格，用户可以通过鼠标和键盘来操作应用程序。

    使用状态转化图或状态转化表表示事件驱动

    状态转化图中有多个状态，反映了由于某种原因从某个状态转化到另一个状态的流程。

5. 算法 - 处理问题的步骤

算法（Algorithm）是被明确定义的有限个规则的集合，用于根据有限的步骤解决问题。例如在既定的精度下，把求解sin x 的计算步骤无一遗漏地记录下来的文字。— JIS（日本工业标准）关于算法的定义

把解决问题的步骤无一遗漏地用文字或图表示出来就形成了算法。使用编程语言表达，算法就变成了程序。

了解算法的目的是能够借助算法将自己的想法完整地传达给计算机。只要理清在现实世界解决问题的步骤，再结合计算机的特性，就一定能想出算法。

算法要点

  • 解决问题的步骤明确且有限

    算法中的步骤必须明确。如果步骤中有与直觉相关的因素，就不是算法。不是算法就不能用程序表示。同时算法中的步骤必须有限。

  • 计算机只会机械地解决问题

    计算机不能自发地思考，因此计算机不靠直觉而是机械地解决问题。计算机所执行的由程序表示的算法必须是由机械的步骤所构成。机械的步骤是指，只要按照这个步骤做就一定能完成。

  • 了解并应用典型算法

    先自己思考算法，再去应用典型算法。

    比如求解最小公倍数，可以这样得到：用两个整数的乘积除以这两个整数的最大公约数。

    算法名称 用途 基本思想
    辗转相除法 求解最大公约数 反复用较大的数减去较小的数，直到两个数的值相等
    埃拉托斯特尼筛法 判定素数 用待判定的数除以比它小的所有正整数
    顺序查找 检索数据
    二分查找 检索数据
    哈希查找 检索数据
    冒泡排序 数据排序
    快速排序 数据排序

  • 解决问题时利用计算机的处理速度

    比如判定素数，鸡兔同笼等。

  • 使用编程技巧提升程序执行速度

    解决一个问题的算法未必只有一种。如何比较用于解决同一个问题的多种算法的优劣呢？就看转化为程序后，哪种算法的执行时间更短。虽然计算机的处理速度很快，但是当处理的数据数值巨大或是数量繁多时，还是要花费大量的时间。

    有时稍微往算法中加入一些技巧，就能大幅度地缩短处理时间。

    在算法技巧中有个著名的技巧叫作哨兵。哨兵是一种含有特殊值的数据，可用于标识数据的结尾等。比如，字符串的末尾用0 表示，链表的末尾用－1 表示。哨兵多用在线性搜索（从若干个数据中查找目标数据）等算法中。线性搜索的基本过程是将若干个数据从头到尾，依次逐个比对，直到找到目标数据。

  • 找出数字间的规律

    所有的信息都可以用数字表示是计算机的特性。因此为了构造算法，经常会利用数字间的规律。

  • 先在纸上考虑算法

    思考算法的时候，要先在纸上用文字或图表描述出解决问题的步骤，而不要立刻开始编写代码。

    画流程图就可以方便地把算法用图表示出来，因此请诸位大量地、灵活地运用它。如果不想画流程图，也可以用语言把算法描述出来，写成文书。

    在纸上画完或写完流程以后，再把具体的数据代入以跟踪流程的处理，确认是否能得到预期的结果。在验算的时候，建议使用简单的数据，这样即使是用心算也能得出正确的结果。

算法举例

辗转相除法

辗转相除法（欧几里得算法）是一个机械地求解最大公约数问题的算法（使用除法 / 减法运算）。

使用减法求最大公约数时，用两个数中较大的数减去较小的数（步骤），反复进行上述步骤，直到两个数的值相等（步骤的终止）。如果最终这两个数相同，那么这个数就是最大公约数。

根据这个简单的算法，我们可以回顾以下算法的几个要点：

  • 步骤是明确的、完全不依赖直觉的；

  • 步骤是机械的、不需要动脑筋就能完成的；

  • 使步骤终止的原因是明确的。

将算法转化为 C 语言程序

/// gcd.c
#include <stdio.h>

int euclid(int a, int b);

int main(){
    
    int a = 0;
    int b = 0;
    int gcd = 0;

    printf("Enter two integer numbers:\n");
    scanf("%d %d", &a,&b);

    gcd = euclid(a,b);

    printf("Greatest common divisor of %d and %d is : %d\n", a,b,gcd);

    return 0;
}

int euclid(int a, int b){
    while(a != b){
        if (a > b) {
            a = a - b;
        } else {
            b = b - a;
        }
    } 
    return a;
}

在终端（命令行界面）中输入以下命令，根据提示输入两个整数，比如，输入88 和 24，即可求得他们的最大公约数 8。

$ gcc -c gcd.c -o gcd.o
$ gcc gcd.o -o gcd.exe
$ ./gcd.exe

6. 数据结构 - 数据的排列方式

Algorithms + Data Structures = Programs - Niklaus Wirth

程序员应该把算法（处理问题的步骤）和数据结构（作为处理对象的数据的排列方式）一起考虑。选用的算法和数据结构要相互匹配。

前面我们学习了算法。我们知道，程序是用来在计算机上实现现实世界中的业务和娱乐活动的，为了达到这个目的，程序员们需要结合计算机的特性，用程序来表示现实世界中对问题的处理步骤，即处理流程。

那么如何结合计算机的特性，用程序来表示现实世界中的数据结构呢？首先我们需要了解数据结构的基础，典型的数据结构以及如何用程序实现典型的数据结构。

使用变量在内存中存取数据

内存和变量的关系是，使用变量在内存中存取数据。

计算机所处理的数据都存储在内存，内存是一种 IC 芯片，使用集成电路 Integrated Circuit 技术制造。

内存内部被分割成了若干个数据存储单元，每个单元可以存储 8 比特的数据。为区分各个单元，每个单元都被分配了一个编号——内存地址。依靠指定地址的方式编写程序很麻烦，使用变量是为了方便编程。

程序使用变量把数据存储进内存或从内存中把数据读出来的。变量的实质是按照变量所存储数据的大小被分配到的一块内存空间。变量是程序中数据存储的最小单位，每个变量都对应着一块物理上的内存空间。变量作为数据的容器，可以改变其中所存储的数据。

int myVar = 256; /* 定义变量myVar，并将数据 256 存入变量 */

数组是数据结构的基础

  • 批量数据处理：数组反映了内存连续分布的物理结构

    数组是把若干个数据沿直线排列起来的数据结构，实质是连续分配的一块特定大小的内存空间。

    数组是为了存储多个数据而在内存上集中分配出的一块内存空间，数组名是这块空间整体赋的名字。可以通过在[和]之间指定序号（索引）的方式分别访问数组内的各块内存空间，即数组元素 。数组元素本质上也是变量，但是比起单独定义多个变量，使用数组可以同时定义出多个变量，能够更加高效地编写出能够实现排序等算法的程序。

  • 了解数组的应用——作为典型算法的数据结构

    数组是一种直接利用内存物理结构（计算机的特性）的最基本的数据结构。

    数组是数据结构的基础。因为数组反映了内存的物理结构本身。在内存中存储数据的空间是连续分布的。而在程序中，往往要从内存整体中分配出一块连续的空间以供使用。如果用程序中的语句表示这种分配使用方式的话，就要用到数组。只要使用数组就能通过程序实现各种各样的算法以处理大量的数据。

    无论是在哪种编程语言中，数据结构的基础都是数组，因此设法灵活地运用数组是关键。

  • 典型数据结构

    数组有局限性，为了适应复杂多变的现实需求，需要在逻辑上改造数组。使用不同的手段处理数组，会得到不同的数据结构。数组有时可以转化为栈，有时可以转化为队列。

    就像在算法中有典型算法一样，在数据结构中也有典型数据结构。这些数据结构都是通过程序从逻辑上改变了内存的物理结构，即数据在内存上呈现出的连续分布状态。

    典型数据结构 特征 实现
    栈 LIFO（优先读取后存入的数据） 数组、栈顶指针、入栈/出栈函数
    队列 FIFO（优先读取先存入的数据） 数组、队头/队尾变量、入队/出队函数
    链表 可以任意地改变数据的排列顺序 自我引用的结构体
    二叉树 把数据分为两路排列（链表的特殊形态) 带有两个连接信息的成员的自我引用结构

    栈（Stack）的 本意是干草堆。栈和队列：

    • 相似：都可以把不能立刻处理的数据暂时存储起来。

    • 区别：数据的存取形式不同（栈 LIFO ，队列 FIFO）。

  • 栈和队列的实现

    使用数组、栈顶指针、入栈函数和出栈函数实现栈。

    char Stack[100]; 					/* 作为栈本质的数组 */
char StackPointer = 0; 				/* 栈顶指针 */

/* 入栈函数 */
void Push(char Data){	
    Stack[StackPointer] = Data;		/* 把数据存储到栈顶指针所指的位置上 */
    StackPointer++;					/* 更新栈顶指针的值 */
}

/* 出栈函数 */
char Pop(){
    StackPointer--;					/* 更新栈顶指针的值 */
	return Stack[StackPointer];		/* 把数据从栈顶指针所指的位置中取出来 */
}

    使用一个数组、两个变量和两个函数实现队列。

    char Queue[100]; 	/* 作为队列本质的数组 */
char SetIndex = 0; 	/* 标识数据存储位置的索引 */
char GetIndex = 0; 	/* 标识数据读取位置的索引 */

/* 存储数据的函数 */
void Set(char Data){
    Queue[SetIndex] = Data;	 /* 存入数据 */
    SetIndex++;				/* 更新标识数据存储位置的索引 */
    
    if (SetIndex >= 100){	/* 如果已到达数组的末尾则折回到开头 */
        SetIndex = 0;
    }
}

/* 读取数据的函数 */
char Get(){
    char Data;				
    Data = Queue[GetIndex];		/* 读出数据 */
    GetIndex++;					/* 更新标识数据读取位置的索引 */

    if (GetIndex >= 100){		/* 如果已到达数组的末尾则折回到开头 */
    	GetIndex = 0;
    }
    
    return Data;				/* 返回读出的数据 */
}

结构体

  • 结构体汇集了若干个数据项

    结构体，就是把若干个数据项汇集到一处并赋予其名字后所形成的一个整体。被汇集到结构体中的每个数据项都被称作结构体的成员。

    一旦定义完结构体，就可以把结构体当作是一种数据类型，用它来定义变量，通过定义结构体变量，在内存上就分配出了一块空间。接下来就可以使用.（点语法）存取结构体的成员。

    C 语言中结构体的定义方法如下：

    struct SmartPhone{
	char name; 	/* Name of SmartPhone - Member*/
	int price; 	/* Price of SmartPhone - Member*/
	char os; 	/* Operation System of SmartPhone - Member*/
};

struct SmartPhone aPhone; 
aPhone.name = "ePhone 21"; 
aPhone.price = "9999"; 
aPhone.os = "catOS";

  • 使用结构体的数组实现链表和二叉树

    在实际的程序中，为了能够处理大量的数据，都会在各种各样的情景下灵活地运用链表。链表类似数组，但其中的每个元素和另一个元素都好像是手拉着手。

    为了让各个元素把手拉起来，就需要在结构体中再添加一个成员：指向其他元素的指针 pointer。指针 pointer 存储了下一个元素的地址。

    struct SmartPhone{
	char name; 	/* Name of SmartPhone - Member*/
	int price; 	/* Price of SmartPhone - Member*/
	char os; 	/* Operation System of SmartPhone - Member*/
	struct SmartPhone* pointer; /* 指向其他元素的指针1 */
};

    因为指针 pointer 存储的是与下一个数组元素的连接信息，所以只要替换了指针 pointer 的值，就可以对数组中元素排序，使元素的排列顺序不同于其在内存上的物理排列顺序。

    二叉树多用于实现那些用于搜索数据的算法，比如“二分查找法”。比起只使用链表，使用二叉树能够更快地找到数据。在二叉树的实现中，用了带有两个连接信息的成员的自我引用结构体。

    struct SmartPhone{
	char name; 	/* Name of SmartPhone - Member*/
	int price; 	/* Price of SmartPhone - Member*/
	char os; 	/* Operation System of SmartPhone - Member*/
	struct SmartPhone* Ptr1; /* 指向其他元素的指针1 */
	struct SmartPhone* Ptr2; /* 指向其他元素的指针2 */
};

7. 面向对象编程 - 间接技术

在C 语言中，结构体是数据的集合，它将数据捆绑在一起，使得我们可以将这些数据看作是一个整体。而对结构体中的数据进行操作的函数却写在了结构体的外部。然而在面向对象编程中，将表示事物行为的函数也放入了这个整体，这就形成了对象的概念，使得这个整体既能描述属性，又能描述行为。

面向对象编程（OOP，Object Oriented Programming）是一种编写程序的方法，旨在提升开发大型程序的效率，便于修改和扩展程序功能。

OOP 以对象（Object）为中心，对象的构成要素包含对象的行为及操作。OOP 涉及的主要编程技巧是继承、封装、多态。

理解 OOP

  • 通过拼装类（组件）构建程序

    类（Class）就是把程序中有关联的函数和变量汇集到一起所编成的组。把汇集到类中的函数和变量统称为类的成员（Member）。

    作为 OOP 中最基本的要素，类是程序的组件（Component）。使用 OOP 编程时，我们通过把若干个类组装到一起构建一个完整的程序。能否灵活地运用类是OOP的关键。

  • 利用 OOP 类库提升程序的开发效率和可维护性

    类库是一组类（组件），即程序组件集合，利用类库可以提升编程的效率。

    在实际应用面向对象编程时，组中有些人只负责制作类（组件），有些人只负责使用类（组件）。还可以把一部分组件的开发任务委托给合作公司，或者买来商业组件使用。

    创造类的人，应该考虑程序的开发效率和可维护性，并决定应该将什么抽象为类。必须把组件设计成即使是坏了（有缺陷了）也能轻松地替换。在功能升级后，旧组件能够被新组件所替换的设计也是必不可少的。

    创造者和使用者之间就需要事先商定类的使用规范。对于类的使用者而言，类似「类看起来是什么样子」的这种关于规范的描述通常被称为接口（Interface）。

  • OOP 适用于大型程序开发

    封装（将函数和变量放入黑盒，使其对外界不可见）可以降低复杂度。

  • OOP 是在为现实世界建模

    程序可以在计算机上实现现实世界中的业务和娱乐活动，程序赋予了计算机各种各样的用途。

    在实际建模的过程中，要进行组件化和省略化这两步。组件化，就是将可看作是由若干种对象构成的集合的现实世界分割成组件。

  • OOP 可以借助UML 设计程序

    建模就是在为面向对象编程做设计，使用建模表记方法 UML（Unified Modeling Language，统一建模语言）可以把对现实世界建模的结果以图形的形式表示出来。

    注意，UML 仅仅规定了建模的表记方法，并不专门用于面向对象编程。

    UML 了从各种各样的角度表示对现实世界建模的结果，规定了九种图：

名称 主要用途
用例图（Use Case Diagram） 表示用户使用程序的方式
类图（Class Diagram） 表示类以及多个类之间的关系
对象图（Object Diagram） 表示对象
时序图（Sequence Diagram） 从时间上关注并表示多个对象间的交互
协作图（Collaboration Diagram） 从合作关系上关注并表示多个对象间的交互
状态图（Statechart Diagram） 表示对象状态的变化
活动图（Activity Diagram） 表示处理的流程等
组件图（Component Diagram） 表示文件以及多个文件之间的关系
配置图（Deployment Diagram） 表示计算机或程序的部署配置方法

UML 被广泛地应用于绘制面向对象编程的设计图，只要了解了UML 中仅有的这九种图的作用，就可以从宏观的角度把握并理解面向对象编程思想了。在进行面向对象编程的设计时，要去关注对象。也就是要在一开始就把所需要的类确定下来，然后再在每个类中列举出该类应该具有的函数和变量。要一边观察作为程序参照物的现实世界，一边思考待解决的问题是由哪些事物（类）构成的。

  • OOP 通过在对象间传递消息驱动程序

    函数是隶属于某个类的，调用某个对象所拥有的函数称为对象间的消息传递。用C++ 等 OOP 语言编写程序时，程序可以通过由一个对象去调用另一个对象所拥有的函数这种方式运行起来。

    OOP 语言中可以使用UML 中的「时序图」和「协作图」表示程序的运行过程。在时序图中，把用矩形表示 的对象横向排列，从上往下表示时间的流逝，用箭头表示对象间的消息传递（即程序上的函数调用）。

  • OOP 使用 继承、封装和多态提升开发效率和可维护性

    • 继承（ Inheritance）- 继承已存在的类所拥有的成员来生成新的类

      只要去继承已存在的类，就能高效地生成新的类。如果一个类被多个类所继承，那么只要修正了这个类，就相当于把继承了这个类的所有类都修正了。

    • 封装（ Encapsulation）- 信息隐藏

      在类所拥有的成员中，隐藏那些不必要展现给该类调用者的成员。

      为了对类进行封装，需要在类成员的定义前指定关键词public（表示该成员对外可见）或是private（表示该成员对外不可见）。

      只要通过封装把外界不关心的成员隐藏起来，类就可以被当作是黑盒，变成了易于使用且便于维护的组件了。而且由于隐藏起来的成员不能被外界所访问，所以也就可以放心地随意修改这些成员。

    • 多态（Polymorphism）- 多样性或多义性

      针对同一种消息，不同的对象可以进行不同的操作。实现多态可以有多种方法。

      只要利用了多态，生成对同一个消息可以执行多种操作的一组类，使用这组类的程序员所需要记忆的东西就减少了。

类和对象的区别

类是做饼干的模具，用模具做出来的饼干是对象。

类是对象的定义，而对象是类的实例（Instance）。现实世界中，也有类（定义）和对象（实体）的区别。

当我们定义了一个类MyClass时，我们还无法直接使用类MyClass 所持有的成员，要想使用就必须在

内存上生成该类的副本，这个副本就是对象。先要创建一个个类的对象然后才能使用类中定义的成员

类的定义和使用

  • 创建类的程序员定义类

    考虑类的复用性、可维护性、如何对现实世界建模以及易用性等，把相关的函数和变量汇集到类中。

  • 使用类的三种方法

    由目标类的性质以及程序员的目的决定应该使用三者中的一种。

    • 调用类的成员：仅调用类所持有的个别成员（函数和变量）

    • 通过组合使用：在类的定义中包含其他的类

    • 通过继承使用：通过继承已存在的类定义出新的类

数据：存储、交换和加密

8. 数据库

基本概念

  • 表（Table）

    被整理成表格形式的数据。一张表由若干个列（字段，Field）和行（记录，Record）构成。

  • 数据库（Database）

    • 数据库是数据（Data）的基地（Base），实质是某种数据文件，通常以DBMS 作为中介间接地读写。

    • 应用程序向 DBMS 请求操作数据，DBMS收到请求后，实际操作数据文件。数据文件、DBMS、应用程序是数据库系统的构成要素。

    • 数据库系统的形式：独立型系统、文件共享性系统、客户端／服务器型系统、Web 系统。

  • 关系型数据库（Relational Database）

    数据被拆分整理到多张表中，表与表之间的关系也可以被记录下来。适合存储大规模数据。

    在关系型数据库中，把录入到表中的每一行数据都称为记录（行或元组），把构成一条记录中的各个数据项，所在的列都称作字段（列或属性）。

  • DBMS（Database Management System）

    数据库管理系统 DBMS 是应用程序和数据文件的中介。DBMS不仅可以使应用程序轻松地读写数据文件，还能通过主键和检查参照完整性实现一致且安全的数据存储。SQL Server、Oracle、DB2等DBMS使用基本相同的SQL 语句操作。

设计数据库

  • 筛选出必要的数据

  • 考虑各种数据的属性（模式或内模式）

    数据的类型，整数还是浮点小数，字符串最多允许包含多少个字符，是否允许NULL 值（表示未知或者不存在的值）。

通过拆表和整理数据实现规范化

  • 规范化

    将一张大表分割成多张小表，然后再在小表之间建立关系，以此来达到整理数据库结构的目的。

    规范化是为了形成结构优良的数据库，要点是在一个数据库中要避免重复存储相同的数据。

用主键和外键在表间建立关系

  • 键（Key）- 用于设定表和表之间的关系

    为了在表和表之间建立关系（Relationship），加入能够反映表与表之间关系的字段键。

  • 为了在表间建立关系，必须加入能够反映表与表之间关系的字段，为此添加了名为键的新字段。

  • 主键（Primary Key）- 主键的值唯一标识表中的一条记录

    • 要在各个表中添加一个字段，即主键，主键的值能够唯一标识表中的一条记录。

    • 将主键命名为「某某ID」：主键存储的是能够唯一标识一条记录的ID（Identification，识别码），在主键上绝不能存储相同的值，如果试图录入在主键上含有相同值的记录，DBMS 就会产生一个错误通知，这就是DBMS 所具备的一种一致并且安全地存储数据的机制。

    • 复合主键：主键既可以只由一个字段充当，也可以将多个字段组合在一起形成复合主键。

  • 外键（Foreign Key）

    其他表上的主键对于本表而言就是外键。通过主键和外键上相同的值，多个表之间就产生了关联。

  • 连接表（Link Table）- 把多对多分解成两个一对多

    表之间的关系使记录和记录关联了起来。记录之间虽然在逻辑上有一对一、多对多以及一对多（等同于多对一）三种关系，但是在关系型数据库中无法直接表示多对多关系。

    当出现多对多关系时，可以在这两张表之间再加入一张表，把多对多关系分解成两个一对多关系，加入的这张表被称作连接表。

在字段上设置索引以提升数据检索速度

  • 索引（Index）- 目录

    • 可以在表的各个字段上设置索引，这也是DBMS 所具备的功能之一。

    • 索引即「目录」，数据库的索引是一种能够高效地查找目标数据的机制。

    • 索引仅仅是提升数据检索和排序速度的内部机制，与键无关。一旦在字段上设置了索引，DBMS 就会自动为这个字段创建索引表。

    • 仅为要频繁检索和排序的字段设置索引。一旦设置了索引，每次向表中插入数据时，DBMS 都必须更新索引表。提升数据检索和排序速度的代价，是插入或更新数据速度的降低。

  • 索引表

    一种数据结构，存储着字段的值以及字段所对应记录的位置。当查询数据时，DBMS 先在索引表中进行数据的检索和排序，然后再根据位置信息从原来的数据表中把完整的记录取出来。

设计用户界面

只要通过拆表实现了规范化、设置了主键和外键、确保没有多对多关系、根据需要设置了参照完整性和索引，那么数据库的设计就告一段落了。接下来就该进入为了利用数据库中的数据而编写数据库应用程序的阶段了。

在设计系统时，请记住：优先设计数据库，然后再设计用户界面。

数据库应用程序的基础功能是能够对记录进行CRUD 的操作， 即记录的插入（CREATE）、获取（REFER）、更新（UPDATE）、删除（DELETE）。统计、打印等更加丰富功能也可以在后期加上。

DBMS 具有自动生成主键和外键上的值的功能，所以在设计用户界面时，需要显示其余的字段，并要使CRUD 操作能够通过按钮和菜单来完成。

向DBMS 发送CRUD 操作的SQL 语句

DBMS基本都支持**SQL **(Structured Query Language，结构化查询语言)。

一旦向DBMS 发送了一条命令（SQL 语句），与此相应的操作就会立刻被执行。使用SQL 语言通常不需要定义变量或者考虑程序的执行流程。

CRUD SQL
C INSERT
R SELECT
U UPDATE
D DELETE

使用数据对象向DBMS 发送SQL 语句

数据对象（Data Object）

DBMS 的一个高级功能——事务控制

事务（Transaction）

  • BEGIN TRANSACTION（开启事务）语句

    用于通知DBMS开启事务

  • COMMIT（提交事务）语句

    用于通知DBMS 提交事务

  • ROLL BACK（事务回滚）语句

    用于在事务进行中发生问题时，把数据库中的数据恢复到事务开始前的状态。

数据加密

以https:// 开头的 URL，表示数据正在使用加密的方式进行传输。文本、图像等各种形式的信息，都可以作为加密对象的数据中。但是计算机会把所有的数据都用数字表示，即便数据有各种展现形式，加密技术基本相同。假设加密的对象仅限于文本数据。

  • 字符编码

    文本数据可以由各种各样的字符构成，为每个字符都被分配的一个数字就是字符编码。

  • 字符集

    定义了应该把哪个编码分配给哪个字符的字符编码体系，比如ASCII 字符集、Unicode 字符集等。

  • 明文和密文

    未经加密的文本数据。如果数据以明文的方式在网络中传输，就有可能被盗取滥用。因此要对明文进行加密，将它转换成为密文。

  • 加密

    加密技术的基本手段是字符编码的变换，即将构成明文的每个字符的编码分别变换成其他的数值。

    加密方式 说明 算法
    错开字符编码 XOR
    对称密钥加密技术 加 / 解密使用数值相同的密钥
    公开密钥加密技术 用公钥加密，用私钥解密 RSA 算法

    • 对称密钥加密技术

      在加密和解密的过程中使用数值相同的密钥。必须事先把密钥的值作为只有发送者和接收者才知道的秘密保护好。

    • 公开密钥加密技术

      用于加密的密钥可以公开给全世界，因此称为“公钥”，而用于解密的密钥是只有自己才知道的秘密，因此称为“私钥”。

  • 解密

    把密文还原成明文的过程

  • 密钥

    用于加密和解密的数字。密钥越长，解密越困难。

    合理的密钥应该满足的条件：长短适中、可以反复使用、可以通过某种通信手段交给接收者，并且通信双方以外的其他人难以用它来解密。

    一般会公开使用的加密方式，而只对密钥的值保密。

  • 数字签名 - 证明数据的发送者是谁

    对比由文件整体计算出的信息摘要（Message Digest，一个数值），可以证明文件的内容有没有被篡改。加密处理过的信息摘要就是数字签名。MD5。

网络：计算机通信

9. TCP/IP 网络

基本概念

  • 网络（Network）- 通过连接多台计算机所组成的、可用于信息交换的系统

    • LAN（Local Area Network，局域网）

    • WAN（Wide Area Network，广域网）

      互联网作为网络的一种，可以使我们的计算机和远在千里之外的计算机连接在一起。

  • 协议（Protocol）- 对信息发送方式的规定或约束

    信息可以以电信号的形式在网线中传播，所以计算机彼此之间能够进行信息交换。但为了交换信息，还必须在发送者和接收者之间事先确定发送方式。

    TCP/IP（Transmission Control Protocol/Internet Protocol ）协议族是事实上的标准。

了解网络

构成网络的硬件 举例
网卡（NIC，NetworkInterface Card） 以太网（Ethernet）网卡
网线
集线器
路由器

这些硬件的规格只有相互匹配了才能连接在一起。网卡的种类一旦确定，网线、集线器和路由器的规格也就确定了。既然硬件的规格一致了，就意味着其中传输的电信号的形式也是一致的。

  • MAC 地址 - 标识网卡

    每一块网卡所带有的ROM（Read Only Memory，只读存储器）中都预先烧录了一个唯一的MAC (Media Access Control）地址。

  • IP 地址 - 对计算机进行分组管理

    • 在TCP/IP 网络中，除了硬件上的MAC 地址，还需要为每台计算机设定一个软件上的编号，即IP 地址。

    • 主机（Host）就是指设定了IP 地址的计算机。路由器是特殊的计算机，也有IP 地址。

    • IP 地址是一个32 比特的整数，每8 比特为一组，组间用“.”分隔， 分成4 段表示。8 比特所表示的整数换算成十进制后范围是0～255，因此可用作IP 地址的整数是0.0.0.0～255.255.255.255。

    • 最多能配置的计算机，需要出去 0000 、1111以及路由器。

    • 在TCP/IP 网络中，传输的数据都会携带 MAC 地址和 IP 地址两个地址。

    • 在macOS上，可以使用 ifconfig命令可以查看查看计算机中网卡的MAC 地址 和 IP 地址。

    • 使用 arp -a 查看IP 地址和MAC 地址的对应关系 (ARP 缓存表)

    $ ifconfig

# en0:
# 	ether 00:00:5D:B8:39:B0 
# 	inet  192.168.237.141

    eth0表示以太网网卡，ether 表示 MAC地址（制造商和产品编号），inet 表示 IP地址 ( IPv4地址 )。

  • 子网掩码（Subnet Mask）

    IP 地址中，网络地址表示分组（即LAN），主机地址表示各台计算机（即主机）。子网掩码的作用就是标识出在32 比特的IP 地址中，从哪一位到哪一位是网络地址，从哪一位到哪一位是主机地址。

  • DHCP（Dynamic Host Configuration Protocol，动态主机设置协议）

    DHCP 服务器上记录着可以被分配到LAN 内计算机的IP 地址范围和子网掩码的值。IP 地址和子网掩码都是在软件上设置的参数。

  • 路由器（Router）

    路由器是决定数据传输路径的设备。数据经过路由器转发的过程即是路由（Routing）。

    # Print Routing tables （macOS）
$ netstat -nr

    • 路由表

      分布在世界各地的LAN 中的路由器相互交换着信息，互联网正是由于这种信息的交换才得以联通。这种信息被称作路由表，用来记录应该把数据转发到哪里。在一台路由器的路由表中，只会记录通往与之相邻的路由器的路径，而并不会记录世界范围内的所有传输路径。

    • 直接交付

      如果数据的发送目的地就在本LAN 中，则可以直接发送数据而无需经过路由器转发。

    • 间接交付

      如果数据的发送目的地在LAN 外（或发送目的地的IP 地址不在路由表中），则需要经过路由器转发。

  • DNS 服务器可以把主机名解析成IP 地址

    DNS（Domain Name System，域名系统）服务器。

    由主机名和域名组合起来形成的名字称作FQDN（Fully Qualified DomainName，完整限定域名）。

  • TCP 的作用及TCP/IP 网络的层级模型

CSMA/CD 机制

命令 作用
ifconfig 显示网络接口(interface)信息（接口名称，类型，IP地址，MAC地址等）
ping 测试网络连通性
arp -a 显示本地存储的IP-MAC对应关系
netstat -nr 显示路由表（可以找到网关Gateway）
traceroute 追踪到达IP目的地的全程路由
tcpdump 网络抓包，监听网络接口不同层的通信，并过滤出特定的内容（特定协议、特定端口等）
host DNS域名解析，返回域名对应的IP地址

通用数据交换格式

由字符构成的纯文本文件，用来存储结构化的数据、配置应用程序等。

  • CSV（逗号分隔值）

    仅记录信息本身，扩展名.csv，CSV文件比较小。文件尺寸大，意味着存储空间占用更多、传输及处理时间更长的。

123, "apple", 200
456,"computer",300

标记语言

标记：通过添加标签为数据赋予意义的行为。标记语言：可以用标签为数据赋予意义的语言。

给人看的 HTML 给计算机看的 XML
用途 编写网页 使用标签为信息赋予意义
通用数据交换格式
扩展性 固定的标记语言（使用由HTML 定义的若干种标签） 可扩展的标记语言

HTML 是用于编写网页的标记语言，用途仅限于信息的可视化——展现网页。

HTML 决定了可用于编写网页的标签。可使用的标签的种类决定了标记语言的规范。Web浏览器会对HTML 的标签进行解析，把由它们标记的信息渲染成在视觉上可以阅读的网页。

XML - 可扩展，元语言，纯文本

XML - 定义任意标记语言的元语言，可以为信息赋予意义

  • 可扩展

    XML（Extensible Markup Language，可扩展标记语言） 本身不会限定标签种类，允许XML 使用者自己创建标签，即在<和>中可以是任意单词。

    XML 仅仅限定了进行标记时标签的书写格式（书写风格），通过定义要使用的标签种类，就可以创造出一门新的标记语言。

    你可以使用灵活的XML 为各个行业、各个特殊用途创建标记语言。

  • 元语言：用于定义新语言的语言。通过使用XML 可以定义出各种各样的新语言。

  • 纯文本：只包含字符。

  • XML 的主要用途：为在互联网上交换的信息赋予意义，在互联网以外的场景也可以使用XML。

  • 完整的 XML 文档 - 声明+实例+DTD

    • XML 声明：<?xml version="1.0" encoding="UTF-8"?>
    • XML 实例：文档中通过标签被标记的部分
    • 文档类型描述 DTD：用<!DOCTYPE和]>括起来的部分就是DTD，DTD定义了XML 实例的结构，通过DTD 可以严格地检查 XML 实例的内容是否有效。（XML Schema 技术也可用于定义XML 实例结构）

  • 格式良好的 XML 文档（Well-formed XML Document）

    遵循XML 约束、正确标记了的文档（能通过XML 解析器的解析）

  • 有效的 XML 文档（Valid XML document）

    在XML 文档中写有DTD（Document Type Definition，文档类型描述）信息

  • **通过 xmlns 属性为 XML 标签设定命名空间 **

    命名空间（NameSpace）通常是一个能代表企业或个人的字符串，用于修饰限定标签的名字。

    XML 文档并非互联网专用，但是XML 确实是一种主要通过互联网在全世界的计算机之间交换数据时使用的数据格式。为了防止这种同形异义带来的混乱，W3C 推荐使用 XML 命名空间（Namespace in XML）。

    在XML文档中，通过把xmlns=" 命名空间的名字"作为标签的一个属性记述，就可以为标签设定命名空间。

  • DOM（Document Object Model，文档对象模型）

    用于处理 XML 文档的程序组件，比如 Windows 的msxml3.dll 。

XML 主要约束

  • 文档开头有XML 声明（XML 版本和字符编码）

  • XML 声明后，有且仅有一个根元素，该标签包含了所有其他的标签

  • 有内容的元素< 标签名>内容</ 标签名>，没有内容的元素< 标签名/>

  • 标签名区分大小，不以数字开头，中间无空格

  • 半角空格、换行符、制表符（TAB）都当做空白字符，所以在文档中可以任意地换行或缩进书写

  • 标签中可以再嵌套标签以表示层级结构，但不能交叉嵌套，即开始标签和结束标签要正确匹配

  • 在开始标签中，可以以“属性名 = " 属性值"”的形式，加入任意的属性

  • 内容中使用五个特殊符号（< > & " ' ）时，要分别写成 &lt;, &gt;, &amp;, &quot;, &apos;

    当内容中需要书写大量特殊符号，用<![CDATA[”和“]]>把内容括起来，就可以在里面直接使用。

  • 注释<!-- Comment -->

用 XML 定义的标记语言示例（W3C）

标记语言 名称 用途
XSL 为XML 中的信息提供显示格式
MathML 描述数学算式
SMIL 把多媒体数据嵌入到网页中
SVG 用向量表示图形数据
XHTML 用XML 定义HTML4.0
SOAP Simple Object Access Protocol，简单对象访问协议 实现分布式计

为了实现各自的目的，每一种标记语言中都定义了各种各样的标签。

分布式计算

把程序分散部署在用网络连接起来的多台计算机上，使这些计算机相互协作，充分发挥计算机整体的计算能力。简单地说，SOAP 就是使运行在A 公司计算机中的A 程序，可以调用运行在B 公司计算机中的B 程序。

JSON

YAML

YAML 语言（发音 /ˈjæməl/ ）专门用来写配置文件，实质通用的数据串行化格式。

语法规则

使用# 注释，大小写敏感，使用缩进表示层级关系，允许使用空格缩进（保证相同层级的元素左侧对齐）。

数据结构

YAML 支持的三种数据结构：对象，数组和纯量。使用对象和数组，可以形成复合结构。

  • 对象

    键值对的集合，使用冒号结构表示。对象又称为映射（mapping）/ 哈希（hashes） / 字典（dictionary）。

  • 数组

    一组按次序排列的值，又称为序列（sequence） / 列表（list）。

    一组连词线开头的行，构成一个数组。

    数据结构的子成员是一个数组，则可以在该项下面缩进一个空格。

  • 纯量（scalars）

    单个的、不可再分的值

由各种技术组合而成的计算机系统

系统

由多个要素相互发生关联，结合而成的带有一定功能的整体。将各种各样的硬件和软件组合起来构建而成的系统就是计算机系统。

成功的计算机系统是什么样的呢？那就是能完全满足客户需求的计算机系统。客户期待的是由计算机带来的IT 解决方案，而并非计算机技术。能满足需求且稳定地工作，这样的计算机系统正是被客户所需要的。

设备利用率 = 正常运转的时间 / (正常运转的时间+出现故障处于维修状态的时间)

瀑布模型

软件开发过程的模型有瀑布模型、原型模型、螺旋模型等。使用模型是为了将复杂的事物简单化。

庞大复杂的事物往往无法直接做出来，人们往往要把庞大复杂的事物先分解成细小简单的要素来进行设计。有了各个要素的设计图，整体的设计图也就出来了。先根据每个要素的设计图制成小零件（程序中的模块），待每个小零件的测试（单元测试）都通过了，剩下的就只是一边看着整体的设计图，一边把这些零件组装起来了。然后再来一轮测试（集成测试），测试组装起来的零件是否能正确地协作运转。

瀑布模型阶段 瀑布模型文档
需求分析 系统策划文档、系统功能需求规格文档
外部设计 外部设计文档
内部设计 内部设计文档
程序设计 程序设计文档
编码实现 模块设计文档、测试计划文档
测试 测试报告
部署、维护 部署手册、维护手册

  • 设计即拆解

    从需求分析到程序设计，进行的工作都是拆解业务，即把将要为计算机系统所替代的手工业务拆解为细小的要素。计算机系统的设计，就是拆解

  • 集成

    从编码实现到部署、维护阶段，所进行的工作则是集成，把拆解后的细小要素转换成程序的模块，再把这些模块拼装在一起构成计算机系统。

程序设计方法 拆解时所关注的事物 亮点
面向对象 构成计算机系统的事物（对象） 简化了系统维护
通用功能分割 在整个计算机系统中通用的功能
STS（Source，Transform，Sink） 数据流（输入、变换、输出）
TR（Transaction） 事务（数据的处理单位）
Jackson 输入数据和输出数据
Warnier 输入数据

回顾：计算机的三大原则

  • 计算机只能够做输入、运算、输出三种操作

  • 程序是指令和数据的集合

  • 计算机有自己的处理方法

各种设计方法，其关注点要么在输入、运算、输出、指令、数据这几个要素的某一个上，要么在某几个的组合上。引进计算机系统的目的是通过用计算机替代靠手工作业进行的业务，来提升工作效率。因此在设计时，要使手工作业的业务顺应计算机的处理方式来进行替换。

参考资料

  • 《计算机组成与设计：硬件/软件接口》
  • 《计算机是怎样跑起来的》
  • 《JSON必知必会》
  • 《面向对象是怎样工作的》
  • 《设计模式》
  • YAML 语言教程-阮一峰