0x00 查找 主要有如下查找算法（Searching Algorithms)： 顺序查找（Linear Search） 二分查找（又称折半查找Binary Search） 以及几个对查找优化的数据类型： 哈希表（又称散列表Hash Table） B树（参见树那一节） 介绍一个基本概念叫做平均查找长度（ASL）： ASL的计算公式如下： ASL=∑i=1nPi×CiASL=\sum_{i=1}^n P_i\times C_i ASL=i=1∑n​Pi​×Ci​ 上式中 n为查找长度 PiP_iPi​为第iii个元素为目标的概率 CiC_iCi​为找到第iii个元素所需要进行的比较次数 0x01 顺序查找和二分查找 0x00 顺序查找 顺序查找不做详述，就是最简单的查找算法，从第一个开始往后依次查找，直到找到目标或者到达结尾。顺序表一般针对无序的序列。 在此，不给出代码了，仅分析其平均查找长度，对于顺序查找而言在查找成功的情况下，ASL计算为： ASL=∑i=1nin=n+12ASL=\sum_{i=1}^n \frac{i}{n} = \frac{n+1}{2} ASL ...

0x00 I/O设备 0x00 分类 按传输速率分类为： 低速设备：键盘鼠标 中速设备：打印机 高速设备：磁带机，磁盘，光盘 按信息交换的单位分类： 块设备：数据存储以数据块为单位，如磁盘，传输速率高可寻址，可以进行随机读写 字符设备：数据存储的基本单位是字符，如打印机，传输速率低不可寻址，输入输出时采用中断驱动方式 常见的设备及介质： CD-ROM为光盘存储器，强调只读，说其只能写入一次是错误的 Flash存储器可以实现随机存取，但其从原理上讲仍为ROM ROM即只读存储器，只能读出不能写入，信息永久保存 0x01 控制方式 程序直接控制：每读入一个字，CPU都要对外设状态进行循环检查，造成了CPU资源的极大浪费，且CPU与I/O设备之间只能串行工作 中断驱动方式：允许I/O设备打断CPU而请求服务，数据中的每个字在存储器和I/O控制器之间的传输都必须经过CPU，仍然会消耗较多的CPU DMA方式：基本单位是数据块，所传送的数据直接送入内存，在传送一个或多个块开始和结束时才需要CPU干预，在DMA控制器下完成 DMA往往连接高速存储器，其优先级高于中断请 ...

0x00 基本概念 0x00 信息的交互方式 单工通信：只有一个方向的通信而没有反方向的交互，仅需要一条信道 半双工通信：通信双方都可以发送或接受消息，但任何一方都不能同时发送和接收，需要2条信道 全双工通信：通信双方可以同时发送和接收信息，需要2条信道 信源是产生和发送数据的源头，信宿是接受数据的终点，信道是信号的传输媒介。 注：信道不等同于电路！一条电路可包含多个信道。 把数据变换为模拟信号的过程叫调制，把数据变换为数字信号的过程叫编码。 波特率（码元传输速率）即为每秒传输的码元的个数（可能发生的信号变化次数）。比特率（信息传输速率）即为每秒传输的二进制码元的个数。要注意两者不同，波特率是每秒码元的个数，比特率是每秒二进制码元的个数。 故又有：波特率=比特率/每符号所含的比特数。 传输： 基带传输：将基带信号直接传送到通信线路（数字信道）上 频带传输：将基带信号经过调制后传送到通信线路（模拟信道）上 在计算机内部一般使用并行传输。 0x01 编码 非归零码NRZ：用低电平表示0高电平表示1，容易实现但没有检错功能，无法判断一个码元的开始和结束，收发双方难以同步 曼彻斯 ...

0x00 基本功能 功能： 为网络层提供服务 无确认的无连接：适用于实时通信，如以太网 有确认的无连接：适用于误码率较高的场合，如无线通信 有确认的面向连接的：适用于可靠性实时性较高的场合 就是没有无确认的有连接 链路管理：链路建立、维持和释放 组帧 定义帧的数据格式 帧定界：确定帧的界限，添加首部和尾部，用标志位F（0111 1110） 帧同步：发送方和接收方都能区分出帧的起始和终止 透明传输：保证任何数据都能在链路上传输 流量控制：实际上限制发送方的数据流量，以防接收方跟不上 差错控制 进一步说一下何谓可靠服务何谓不可靠服务： 可靠服务由网络本身负责，通过一系列的机制来保证传输的可靠性，可靠服务通过检错、纠错、应答机制来保证数据最后准确地到达目的地，对于不可靠的服务，则必须通过应用或用户来保障数据传输的正确性 0x01 组帧 字符计数法：在头部加一个字段来标识帧内的字符数，知道这个数即可确定帧的结束位置，最大的问题在于，如果这个数出错将会带来灾难性后果。 字符填充的首尾定界符法：在头部和尾部加一些特定的字符来标识开始和结尾，信息位中如果有相同的字符，就使用转义 ...

0x00 图 图是一种抽象数据类型（ADT），是一种由有限个结点（node或vertex）和边（edge）组成的非线性数据结构。一个图由顶点集（set of vertices）V和边集（set of edges）E组成，记为G=(V, E)。如下图就是由顶点集V={0, 1, 2, 3, 4}和边集E={01, 04, 14, 12, 13, 23, 34}组成。 注意：线性表可以是空表，树可以是空树，但是图不可以是空图，也就是说，图中不能一个顶点都没有，图的边集可以为空，但是图的顶点集一定不为空。 图这种数据结构蛮有用的，比如上面的图可以表示一幅人际关系网，每个结点可以表示一个人，也可以表示城市道路的交通网等等。 0x01 图的种类 0x00 有向图 有向图（Directed graph或digraph），是图中用来连接各顶点的边带有方向的图。又有定义，边集E是有向边（也成为弧）的有限集合时所构成的图，如图： 上图可表示为： G1=(V1,E1)V1={1,2,3,4}E1={<1,2>,<1,4>,<2,4>,<3,1>,&l ...

0x00 内存管理 0x00 内存管理的主要功能 内存空间的分配与回收 地址转换：在多道程序的环境下，程序中的逻辑地址和物理地址不可能一致，因此必需提供地址转换功能，把逻辑地址转换为对应的物理地址 在链接阶段完成重定位形成整个程序的完整逻辑空间，在装载阶段完成重定位，形成整个程序的完整逻辑地址空间 内存空间的扩充：利用虚拟存储技术或自动覆盖技术，在逻辑上扩充内存 存储保护：保证各个作业在自己的存储空间运行，互不干扰 0x01 内存的装入模块装入内存的方式 绝对装入：编译时如果知道程序将驻留在内存的某个位置，那么编译程序可以将产生的绝对地址的目标代码绝对装入程序按照装入模块中的地址，将程序和数据装入内存。绝对装入仅适用于单道程序环境。 可重定位装入：也称静态重定位，多道程序的环境下，多个目标模块的起始地址都是从0开始的，程序中其他地址都是相对于起始地址的，此时应采用可重定位装入方式，根据内存当前的状况将装入模块装入到内存适当的位置，装入时对目标程序中指令和数据的修改过程称为重定位，地址变换通常是在装入时一次完成的，所以又称为静态重定位。静态重定位的一个特点是在一个作业装入内存时，必 ...

0x00 DNS 递归查询（较为少用） 一定要注意在递归查询的过程中，最开始连接的服务器返回给客户端地址 在递归查询的方式中，用户主机和每一个域名服务器都仅发送了一条DNS查询请求，用户主机查不到就往上查本地域名服务器，本地域名服务器查不到，则此时本地域名服务器作为DNS客户端继续往上查。 递归与迭代相结合（又称迭代查询） 在域名解析的过程中，系统上的域名解析软件必须知道一个本地DNS的IP 0x01 FTP FTP工作时使用2个并行的TCP连接，相对应也会使用2个端口，一个是使用21端口的控制连接，另一个是使用20端口的数据连接。因为控制信息的传送与数据传送是分离的，此过程又称为控制信息的带外传送。 注意：这里21端口的控制连接和20端口的数据连接都是在服务端的！ 服务器监听在21端口等待客户连接，连接上之后此端口在整个会话期间一直保持打开的状态，用于连接的控制（例如中途停止传输）。 数据连接用来进行数据的传输，传送完成之后即刻关闭，控制连接在数据连接被释放后释放。 FTP提供交互式的访问，允许客户指明文件的类型与格式，允许文件具有存取权限，提供以用户权限管理 ...

0x00 基本概念 传输层的基本功能 提供进程之间的逻辑通信 对收到的报文进行差错检测（首部和数据部分） 复用和分用：复用指的是发送方不同的应用进程都可以使用同一个传输层协议，分用是接收方的传输层在剥去报文的首部后能够把这些数据交付给目的应用进程 端口用来标识主机中的应用进程，传输层的服务访问结点（SAP）为端口，端口号只具有本地意义。端口号长度为16位，因此其能表示216=655362^{16}=65536216=65536个端口。 注：数据链路层的SAP为MAC地址，网络层的SAP为IP地址 端口号的划分： 服务端使用端口号 熟知端口号：0-1023，例如FTP-21，TELNET-23，DNS-53 登记端口号：1024-49151 客户端使用端口号：49152-65535，也即短暂端口号或临时端口号，客户进程运行时动态选择 套接字：在网络中发送盒和接收方使用套接字来识别端点。 套接字=(主机IP，端口号)\text{套接字=(主机IP，端口号)} 套接字=(主机IP，端口号) 0x01 TCP TCP提供面向连接的服务，传输数据之前首先建立连接，传送完成之后释 ...

0x00 基本概念 0x00 定义及功能 计算机网络是一些互联的、自治的计算机系统的集合。从组成上看，由硬件、软件、协议三大部分组成，从工作方式上看，可以分为边缘部分和核心部分，从功能上看由通信子网和资源子网（基本组成）组成。 网络资源包括硬件资源、软件资源与数据资源。因特网采用的核心技术即为TCP/IP。 计算机网络的功能： 数据通信 资源共享 分布式处理 提高可靠性 负载均衡 0x01 分类 按分布范围分类： 广域网WAN，交换技术 城域网MAN，多采用以太网技术 局域网LAN，广播技术 个人区域网PAN 按传输技术分类： 广播式网络：所有联网计算机都共享一个公共通信通道，故不需要网络层，也不存在路由选择问题。 点对点网络：每条物理线路连接一对计算机 按拓扑结构（主要取决于通信子网）： 星型网络：每个计算机用单独的线路与中央设备相连 总线型网络：用单根传输线连接计算机 环形网络：所有计算机设备连接成一个环 网状形网络 0x02 性能指标 带宽 时延 发送时延：将分组数据推向链路所需时间 传播时延：电磁波传播所花费的时间 处理时延：数据在交换结点为存储转发所花费的 ...

0x00 基本概念 栈（Stack）是一个抽象数据类型（ADT），对一个集合的元素定义了两个基本操作，入栈（push）以及出栈（pop），栈遵循后进先出原则（LIFO, last in, first out），就像手枪的弹夹一样，最后放入的那颗子弹往往最先打出去。 此处说这是一个ADT抽象数据类型是因为其既可以用链表实现也可以用数组实现，实现的方法不唯一，其并不是一个存储（物理）结构，而是一个抽象数据类型，对于抽象数据类型准确的定义是指一个数学模型以及定义在该模型上的一组操作。 队列（Queue）也是一种抽象数据类型，其同样定义了两个基本操作，入队（enqueue）以及出队（dequeue），其遵循先进先出原则（FIFO, first in, first out），就像我们去买火车票排的那个队列一样，遵循先来后到，先来的先买，买完后出队（从队头删除），后来的自动站在队尾（在队尾添加）。 对于队列还有一种一般化（generalized）的形式就是双端队列（double-ended queue, 一般简写为deque），双端队列两头都可以进行插入（入队）和删除（出队）操作。 栈和队列均 ...