文章目录
前言
一、计算机网络概述
1 互联网的构成
2.网络分类
3.接入网
4.网络核心的两大功能
①路由
②转发
5.网络分层
①OSI 7层模型
②TCP/IP 4层模型
③两种模型比较
二、物理层
1.物理介质
①引导型介质
②非引导型介质
2.数据交换方式
①分组交换
②电路交换
3.信道复用
①频分复用
②时分复用
③波分复用
④码分复用
三、数据链路层
1.功能（要解决的问题）
2.数据链路层提供的服务
3.成帧（Framing）
3.1 要解决的关键问题：如何标识一个帧的开始？
3.2 成帧（framing）的方式
①带比特填充的定界符法
②物理层编码违例
4.差错控制
4.1 背景
4.2 差错检验与纠正
①奇偶检验 (Parity Check)
②校验和 (Checksum)
③循环冗余校验 (Cyclic Redundancy Check，CRC)
④汉明码
5.流量控制
6.媒体接入控制 MAC (Medium Access Control)子层
6.1 信道分配问题
① 时分多址接入-TDMA
② 频分多址接入-FDMA
6.2 多路访问协议
6.2.1 随机访问协议
①ALOHA
②载波侦听多路访问协议CSMA
6.2.2 受控访问协议
①位图协议（预留协议）
②令牌传递
③二进制倒计数协议
6.2.3 有限竞争协议
①自适应树搜索协议（Adaptive Tree Walk Protocol）
6.3虚拟局域网VLAN
6.4无线局域网WLAN
四、网络层
1.网络层概述
2.网络层关键功能
3.Internet网际协议
3.1 IPv4协议及其相关技术
3.1.1 基本概念
3.1.2 IPv4数据报格式
3.1.3 数据报分片
3.1.4 IP协议功能及报头字段总结
3.2 IP地址
3.2.1 概述
3.2.1 子网划分
3.2.3 无类域间路由
3.3 DHCP动态主机配置协议
3.4 ARP地址解析协议
3.5 网络地址转换(NAT)
3.6 ICMP: 互联网控制报文协议
4.路由算法
4.1 距离向量路由
算法过程
特殊情况考虑
4.2 链路状态路由
算法过程
距离向量和链路状态算法比较
4.3 层次路由
4.4 广播路由
实现方法
5.Internet路由协议
5.1 路由选择协议RIP
5.2 BGP-外部网关路由协议
6.路由器的工作原理
6.1 路由器概述
6.2 路由器控制层
6.3 路由器数据层
7.拥塞控制算法
7.1 概述
7.2 流量调节
7.3 随机早期检测RED (Random Early Detection)
8.服务质量
8.1概述
8.2 流量整形
①漏桶算法
②令牌桶算法
8.3 数据包调度
9.三层交换
9.1 三层交换的技术背景
9.2 三层交换的动机
9.3 三层交换机的工作原理
10.虚拟专用网VPN (Virtual Private Network)
10.1 VPN的技术背景
10.2 VPN的原理
10.3 VPN的实现方式
11.IPv6协议
五、传输层
1.传输层概述
1.1 套接字
1.2 传输层提供的服务
1.3 因特网传输层提供的服务
2.传输层基本服务——复用和分用
2.1 复用和分用概述
2.2 套接字标识与端口号
2.3 TCP/UDP套接字（复用和分用）
3.无连接传输：UDP
3.1 UDP报文段结构
3.2 UDP校验和（checksum）
3.3 为什么需要UDP？
4.面向连接的传输：TCP
4.1 可靠传输
4.2 流水线技术
①GBN 协议（回退 N 步协议）
②SR 协议（选择重传协议）
③TCP 可靠通信的具体实现
GBN、SR和TCP小结
4.3 TCP报文段结构
5.TCP流量控制
6.拥塞控制
6.1 拥塞控制的类型
6.2  TCP拥塞控制要解决的问题
6.3 TCP拥塞控制的实现
六、应用层
1.应用层概述
1.1 应用进程通信方式
①客户/服务器（C/S, Client/Server）方式
②对等（P2P，Peer to Peer）方式
1.2 服务器进程工作方式
2.域名系统
2.1 概述
2.2 域名系统名字空间和层次结构
2.3 域名解析过程
3.电子邮件
3.1 邮件发送的常用协议
3.2 Webmail
4.WWW
4.1 WWW体系结构与协议
4.2 HTTP
概述
HTTP发展现状
Web安全与隐私：Cookie
5.流媒体
5.1 概述
5.2 流媒体动态自适应传输
6.内容分发网络CDN
6.1 概述
6.2 关键问题
6.3 机理与解决方式
7.P2P网络
8.远程登录Telnet
9.FTP
9.1 概述
9.2 工作过程
写在最后

前言
为了准备期末考试，同时也是为了之后复习方便，特对计算机网络的知识进行了整理。本篇内容大部分是来源于我们老师上课的ppt。而我根据自己的理解，将老师的PPT整理成博文的形式以便大家复习查阅，同时对于一些不是很清楚的地方，我去查阅了相关资料进行补充，当然也会有少部分个人看法夹带其中来帮助大家理解。

应评论要求这里放上本文的思维导图以供大家更好的查看


一、计算机网络概述
1 互联网的构成
网络边缘:位于互联网边缘与互联网相连的计算机和其他设备,如桌面计算机、移动计算机、服务器、其他智能终端设备

网络核心:由互联端系统的分组交换设备和通信链路构成的网状网络

如：分组交换路由器、链路层交换机、通信链路(光纤、铜缆、无线电、激光链路)
2.网络分类
个域网PAN（ Personal Area Network ）

能在便携式消费电器与通信设备之间进行短距离通信的网络
覆盖范围一般在10米半径以内，如蓝牙耳机等

局域网LAN（Local Area Network）

局部地区形成的区域网络，如企业网络
分布地区范围有限，可大可小，大到一栋建筑、小到办公室内的组网
电脑WLAN接入，打印机共享等等

城域网MAN（Metropolitan Area Network ）

范围覆盖一个城市的网络

广域网WAN（Wide Area Network）

覆盖很大地理区域，乃至覆盖地区和国家

3.接入网
接入网的用途

接入网的用途是将主机连接到边缘路由器上
边缘路由器是端系统Host去往任何其他远程端系统的路径上的第一台路由器

各种异构网络通过边缘路由器接入
接入网分类：

光纤到户FTTH
数字用户线DSL
同轴电缆
无线接入
企业和家庭网络

4.网络核心的两大功能
①路由
确定数据分组从源到目标所使用的路径（全局操作）
②转发
路由器或交换机将接收到的数据分组转发出去（即移动到该设备的某个输出接口）（本地操作）
5.网络分层
①OSI 7层模型

数据链路层 (Data Link Layer)

实现相邻（Neighboring）网络实体间的数据传输
成帧（Framing）：从物理层的比特流中提取出完整的帧
错误检测与纠正：为提供可靠数据通信提供可能
物理地址（MAC address）：48位，理论上唯一网络标识，烧录在网卡，不便更改
流量控制，避免“淹没”（overwhelming）:当快速的发送端遇上慢速的接收端，接收端缓存溢出
共享信道上的访问控制（MAC）：同一个信道，同时传输信号。如同：同一个Wifi热点（AP）连接着多个无线用户（手机），则多个用户同时需要发送数据，如何控制发送顺序？

网络层 (Network Layer)

将数据包跨越网络从源设备发送到目的设备（host to host）
路由（Routing）：在网络中选取从源端到目的端转发路径，常常会根据网络可达性动态选取最佳路径，也可以使用静态路由
路由协议：路由器之间交互路由信息所遵循的协议规范，使得单个路由器能够获取网络的可达性等信息
服务质量（QoS）控制：处理网络拥塞、负载均衡、准入控制、保障延迟

异构网络互联：在异构编址和异构网络中路由寻址和转发

传输层 (Transport Layer)

将数据从源端口发送到目的端口（进程到进程）
网络层定位到一台主机（host），传输层的作用域具体到主机上的某一个进程
网络层的控制主要面向运营商，传输层为终端用户提供端到端的数据传输控制
两类模式：可靠的传输模式，或不可靠传输模式
可靠传输：可靠的端到端数据传输，适合于对通信质量有要求的应用场景，如文件传输等
不可靠传输：更快捷、更轻量的端到端数据传输，适合于对通信质量要求不高，对通信响应速度要求高的应用场景，如语音对话、视频会议等

会话层 (Session Layer)

利用传输层提供的服务，在应用程序之间建立和维持会话，并能使会话获得同步

表示层（Presentation Layer）

关注所传递信息的语法和语义，管理数据的表示方法，传输的数据结构

应用层（Application Layer）

通过应用层协议，提供应用程序便捷的网络服务调用

②TCP/IP 4层模型

③两种模型比较

注：我们教材的是以下分层来讲述的


二、物理层

物理层考虑的是怎样才能在连接各种计算机的传输媒体上传输数据比特流，而不是指具体的传输媒体。
物理层的作用是要尽可能地屏蔽掉不同传输媒体和通信手段的差异。
用于物理层的协议也常称为物理层规程 (procedure)。

1.物理介质
①引导型介质

信号在固体介质中传播，例如铜、光纤、同轴电缆

光纤

高速运行

高速点对点传输（10-100 Gbps）
低错误率

中继器相距很远，对电磁噪声免疫



双绞线

两根绝缘铜线互相缠绕为一对
电话线为1对双绞线，网线为4对双绞线，广泛用于计算机网络（以太网）双向传输
第5类：100 Mbps~1 Gbps；第6类：10Gbps
传输距离一般为为100米


同轴电缆

两根同心铜导线，双向传输
电缆上的多个频率通道
带宽可达100Mbps
传输距离一般为200米


②非引导型介质

信号自由传播，例如无线电（陆地无线电、卫星无线电信道)

无线电

电磁频谱中各种“波段”携带的信号
没有物理“电线”
不依赖介质的广播
半双工（发送方到接收方）

无线链路类型

无线局域网（WiFi）

10-100 Mbps；10米
广域（如3/4/5G蜂窝）

在~10公里范围内
蓝牙：短距离，有限速率
地面微波：点对点；45 Mbps
同步卫星：36000km高空， 280毫秒的往返时延
低轨卫星：近地，但围绕地球高速运动，需要大量卫星才能覆盖地球


2.数据交换方式
①分组交换
分组交换采用把一个个小的数据包存储转发传输来实现数据交换。
主要的一些缺点：

1、不具有实时性。

2、存在延时。

3、会造成通信阻塞。

4、存在无用的重复数据。

5、会出现丢包的情况。
优点：

1、设计简单。

2、资源利用率很高。
②电路交换
电路连接的三个阶段：
1、建立连接。

2、数据传输。

3、释放连接。
优点：

1、传输速度快、高效。

2、实时。
缺点：

1、资源利用率低。

2、新建连接需要占据一定的时间，甚至比通话的时间还长。
电路交换的多路复用

频分多路复用FDM

时分多路复用TDM

3.信道复用

复用 (multiplexing) 是通信技术中的基本概念。

它允许用户使用一个共享信道进行通信，降低成本，提高利用率。

①频分复用

将整个带宽分为多份，用户在分配到一定的频带后，在通信过程中自始至终都占用这个频带。
频分复用的所有用户在同样的时间占用不同的带宽资源（请注意，这里的“带宽”是频率带宽而不是数据的发送速率）。


②时分复用
时分复用则是将时间划分为一段段等长的时分复用帧（TDM 帧）。每一个时分复用的用户在每一个 TDM 帧中占用固定序号的时隙。


③波分复用
波分复用就是光的频分复用。使用一根光纤来同时传输多个光载波信号。


④码分复用
各用户使用经过特殊挑选的不同码型，因此彼此不会造成干扰。
三、数据链路层
1.功能（要解决的问题）
成帧 （Framing）

将比特流划分成“帧”的主要目的是为了检测和纠正物理层在比特传输中可能出现的错误，数据链路层功能需借助“帧”的各个域来实现

差错控制 （Error Control）

处理传输中出现的差错，如位错误、丢失等

流量控制 （Flow Control）

确保发送方的发送速率，不大于接收方的处理速率，避免接收缓冲区溢出
2.数据链路层提供的服务
1.无确认 无连接 服务（ Unacknowledged connectionless ）

接收方不对收到的帧进行确认
适用场景：误码率低的可靠信道；实时通信；
网络实例：以太网

2.有确认 无连接 服务（ Acknowledged connectionless ）

每一帧都得到单独的确认
适用场景：不可靠的信道（无线信道）
网络实例：802.11

3.有确认 有连接 服务（ Acknowledged connection-oriented ）

适用场景：长延迟的不可靠信道

3.成帧（Framing）
3.1 要解决的关键问题：如何标识一个帧的开始？

接收方必须能从物理层接收的比特流中明确区分出一帧的开始和结束，这个问题被称为帧同步或帧定界
关键：选择何种定界符？定界符出现在数据部分如何处理？

3.2 成帧（framing）的方式
①带比特填充的定界符法
定界符：两个0比特之间，连续6个1比特，即01111110，0x7E



发送方检查有效载荷：若在有效载荷中出现连续5个1比特，则直接插入1个0比特


接收方的处理：

若出现连续5个1比特，

若下一比特为0，则为有效载荷，直接丢弃0比特；

若下一比特为1，则连同后一比特的0，构成定界符，一帧结束
②物理层编码违例

核心思想：选择的定界符不会在数据部分出现
4B/5B编码方案

4比特数据映射成5比特编码，剩余的一半码字（16个码字）未使用，可以用做帧定界符

例如： 00110组合不包含在4B/5B编码中，可做帧定界符
前导码

存在很长的 前导码（preamble），可以用作定界符

例如：传统以太网、802.11
曼切斯特编码 / 差分曼切斯特编码

正常的信号在周期中间有跳变，持续的高电平（或低电平）为违例码，可以用作定界符

例如：802.5令牌环网

4.差错控制
4.1 背景
链路层存在的一个问题：信道的噪声导致数据传输问题

差错（ incorrect ）：数据发生错误
丢失（ lost ）：接收方未收到
乱序（out of order）：先发后到，后发先到
重复（repeatedly delivery）：一次发送，多次接收

解决方案：差错检测与纠正、确认重传

确认：接收方校验数据（差错校验），并给发送方应答，防止差错
定时器：发送方启动定时器，防止丢失
顺序号：接收方检查序号，防止乱序递交、重复递交

4.2 差错检验与纠正
目标
保证一定差错检测和纠错能力的前提下，如何减少冗余信息量？
考虑的问题

信道的特征和传输需求
冗余信息的计算方法、携带的冗余信息量
计算的复杂度等

两种主要策略

检错码（error-detecting code）


在被发送的数据块中，包含一些冗余信息，但这些信息只能使接收方推断是否发生错误但不能推断哪位发生错误，接收方可以请求发送方重传数据主要用在高可靠、误码率较低的信道上，例如光纤链路偶尔发生的差错，可以通过重传解决差错问题


纠错码（error-correcting code)


发送方在每个数据块中加入足够的冗余信息，使得接收方能够判断接收到的数据是否有错，并能纠正错误（定位出错的位置）主要用于错误发生比较频繁的信道上，如无线链路也经常用于物理层，以及更高层（例如，实时流媒体应用和内容分发）使用纠错码的技术通常称为前向纠错（FEC，Forward Error Correction)

常用的检错码包括：
①奇偶检验 (Parity Check)
1位奇偶校验是最简单、最基础的检错码。
1位奇偶校验：增加1位校验位，可以检查奇数位错误。


②校验和 (Checksum)
主要用于TCP/IP体系中的网络层和传输层


③循环冗余校验 (Cyclic Redundancy Check，CRC)
数据链路层广泛使用的校验方法
CRC校验码计算方法

设原始数据D为k位二进制位模式
如果要产生n位CRC校验码，事先选定一个n+1位二进制位模式G (称为生成多项式，收发双方提前商定)，G的最高位为1
将原始数据D乘以2^n （相当于在D后面添加 n 个 0），产生k+n位二进制位模式，用G对该位模式做模2除，得到余数R（n位，不足n位前面用0补齐）即为CRC校验码


CRC校验码计算示例

D = 1010001101
n = 5
G = 110101 或 G = x5 + x4 + x2 + 1
R = 01110
实际传输数据：101000110101110



④汉明码
目标：以奇偶校验为基础，找到出错位置，提供1位纠错能力

给定n位待发送的数据，首先确定校验位的个数k（根据2^k≥k+n+1）
确定校验位在码流中的位置，2^i,i=0,1,2,……，得到校验位P_1,P_2,P_4,P_8,……
确定分组，即每个校验位分别负责哪些数据位

P_1负责位置号的二进制符合XXXX1形式的数据位，即1,3,5,7,9,……

P_2负责位置号的二进制符合XXX1X形式的数据位，即2,3,6,7,10,……

P_3负责位置号的二进制符合XX1XX形式的数据位，即4,5,6,7,12,13,14,15,……
基于偶校验确定每组的校验位（0或1）


注： 汉明码是采用奇偶校验的码。它采用了一种非常巧妙的方式，把这串数字分了组，通过分组校验来确定哪一位出现了错误。


实际的海明码编码的过程也并不复杂，我们通过用不同过的校验位，去匹配多个不同的数据组，确保任何一个数据位出错，都会产生一个多个校验码位出错的唯一组合。这样，在出错的时候，我们就可以反过来找到出错的数据位，并纠正过来。当只有一个校验码位出错的时候，我们就知道实际出错的是校验码位了。

5.流量控制
链路层存在的另一个问题：接收方的处理速率

接收方的接收缓冲区溢出

解决方案

基于反馈 (feedback-based) 的流量控制

接收方反馈，发送方调整发送速率
基于速率 (rate-based) 的流量控制

发送方根据内建机制，自行限速

6.媒体接入控制 MAC (Medium Access Control)子层
数据链路层分为两个子层：

MAC子层：介质访问

LLC子层：承上启下（弱层）


6.1 信道分配问题
① 时分多址接入-TDMA
TDMA: time division multiple access

按顺序依次接入并使用信道
每个用户使用固定且相同长度的时隙
某时隙轮到某用户使用时，该用户没有数据要发送，则该时隙被闲置

例子: 6-user LAN, 1,3,4时隙有数据发送, 2,5,6时隙被闲置


② 频分多址接入-FDMA
FDMA: frequency division multiple access

信道总频带被划分为多个相同宽度的子频带
每个用户占用一个子频带，不管用户是否有数据发送

例子: 6-user LAN, 1,3,4频带有数据发送, 2,5,6频带被闲置


6.2 多路访问协议

6.2.1 随机访问协议
特点：冲突不可避免
①ALOHA
纯ALOHA协议
原理：想发就发！
特点：

冲突：两个或以上的帧
随时可能冲突
冲突的帧完全破坏
破坏了的帧要重传

分隙ALOHA

分隙ALOHA是把时间分成时隙（时槽）
时隙的长度对应一帧的传输时间。
帧的发送必须在时隙的起点。
冲突只发生在时隙的起点



②载波侦听多路访问协议CSMA
特点：“先听后发”

改进ALOHA的侦听/发送策略分类


非持续式CSMA
1.特点

①经侦听，如果介质空闲，开始发送

②如果介质忙，则等待一个随机分布的时间，然后重复步骤①
2.好处

等待一个随机时间可以减少再次碰撞冲突的可能性
3.缺点

等待时间内介质上如果没有数据传送，这段时间是浪费的

持续式CSMA
p-持续式CSMA
1.特点
①经侦听，如介质空闲，那么以 p的概率 发送，以(1–p)的概率延迟一个时间单元发送

②如介质忙，持续侦听，一旦空闲重复①

③如果发送已推迟一个时间单元，再重复步骤①
1-持续式CSMA
1.特点

①经侦听，如介质空闲，则发送

②如介质忙，持续侦听，一旦空闲立即发送

③如果发生冲突，等待一个随机分布的时间再重复步骤①
2.好处：持续式的延迟时间要少于非持续式
3.主要问题：如果两个以上的站等待发送，一旦介质空闲就一定会发生冲突
4.注意

1-持续式是p-持续式的特例
6.2.2 受控访问协议

特点：克服了冲突
①位图协议（预留协议）


竞争期：在自己的时槽内发送竞争比特

举手示意
资源预留

传输期：按序发送

明确的使用权，避免了冲突

②令牌传递
令牌：发送权限
令牌的运行：发送工作站去抓取，获得发送权

除了环，令牌也可以运行在其它拓扑上，如令牌总线
发送的帧需要目的站或发送站将其从共享信道上去除；防止无限循环

缺点：令牌的维护代价

③二进制倒计数协议

站点：编序号，序号长度相同

竞争期：有数据发送的站点从高序号到低序号排队，高者得到发送权

特点：高序号站点优先
6.2.3 有限竞争协议
利用上述二者的优势
①自适应树搜索协议（Adaptive Tree Walk Protocol）

在一次成功传输后的第一个竞争时隙，所有站点同时竞争。
如果只有一个站点申请，则获得信道。
否则在下一竞争时隙，有一半站点参与竞争（递归），下一时隙由另一半站点参与竞争
即所有站点构成一棵完全二叉树。



6.3虚拟局域网VLAN
广播域（Broadcasting Domain）

广播域是广播帧能够到达的范围；
缺省情况下，交换机所有端口同属于一个广播域，无法隔离广播域；
广播帧在广播域中传播，占用资源，降低性能，且具有安全隐患。


VLAN是一个在物理网络上根据用途，工作组、应用等来逻辑划分的局域网络，与用户的物理位置没有关系。

通过路由器或三层交换机进行VLAN间路由，实现VLAN间通信。



VLAN类型


基于端口的VLAN




基于MAC地址的VLAN




基于协议的VLAN




基于子网的VLAN




6.4无线局域网WLAN

无线局域网（Wireless Local Area Network，WLAN)：指以无线信道作为传输介质的计算机局域网

基础架构模式（Infrastructure）



分布式系统（DS）
访问点（AP）
站点（STA）
基本服务集（BSS）
扩展服务集（ESS）
站点之间通信通过AP转发

自组织模式（Ad hoc）



站点（STA）
独立基本服务集（IBSS）
站点之间直接通信
共享同一无线信道

无线局域网需要解决的问题
1.有限的无线频谱带宽资源

通道划分、空间重用
提高传输速率，解决传输问题
提高抗干扰能力和保密性

2.共享的无线信道

介质访问控制方法（CSMA/CA）
可靠性传输、安全性

3.组网模式管理

BSS构建、认证、关联
移动性支持（漫游）
睡眠管理（节能模式）

四、网络层
1.网络层概述
网络层在数据链路层提供的两个相邻端点之间的数据帧的传送功能上，进一步管理网络中的数据通信，将数据设法从源端经过若干个中间节点传送到目的端，从而向运输层提供最基本的端到端的数据传送服务。


2.网络层关键功能

路由（控制面）

选择数据报从源端到目的端的路径
核心：路由算法与协议


转发（数据面）

将数据报从路由器的输入接口传送到正确的输出接口



3.Internet网际协议
3.1 IPv4协议及其相关技术
3.1.1 基本概念
IPv4协议，网际协议版本4，一种无连接的协议，是互联网的核心，也是使用最广泛的网际协议版本，其后继版本为IPv6
internet协议执行两个基本功能

寻址(addressing)
分片(fragmentation)

3.1.2 IPv4数据报格式


版本： 4bit ，表示采用的IP协议版本
首部长度： 4bit，表示整个IP数据报首部的长度
区分服务： 8bit ，该字段一般情况下不使用
总长度： 16bit ，表示整个IP报文的长度,能表示的最大字节为2^16-1=65535字节
标识： 16bit ， IP软件通过计数器自动产生，每产生1个数据报计数器加1；在ip分片以后，用来标识同一片分片
标志： 3bit，目前只有两位有意义。

MF，置1表示后面还有分片，置0表示这是数据报片的最后1个；

DF，不能分片标志，置0时表示允许分片
片偏移： 13bit，表示IP分片后，相应的IP片在总的IP片的相对位置
生存时间TTL(Time To Live) ：8bit,表示数据报在网络中的生命周期，用通过路由器的数量来计量，即跳数（每经过一个路由器会减1）
协议：8bit，标识上层协议（TCP/UDP/ICMP…）
首部校验和：16bit ，对数据报首部进行校验，不包括数据部分
源地址：32bit，标识IP片的发送源IP地址
目的地址：32bit，标识IP片的目的地IP地址
选项：可扩充部分，具有可变长度，定义了安全性、严格源路由、松散源路由、记录路由、时间戳等选项
填充：用全0的填充字段补齐为4字节的整数倍

3.1.3 数据报分片
分片原因
数据报长度大于传输链路的MTU

MTU（Maximum Transmission Unit）, 最大传输单元

链路MTU
路径MTU (Path MTU)


分片策略

允许途中分片：根据下一跳链路的MTU实施分片
不允许途中分片：发出的数据报长度小于路径MTU（路径MTU发现机制）

重组策略

途中重组，实施难度太大
目的端重组（互联网采用的策略）
重组所需信息：原始数据报编号、分片偏移量、是否收集所有分片




IPv4分片策略

IPv4分组在传输途中可以多次分片

源端系统，中间路由器（可通过标志位设定是否允许路由器分片，DF标志位）


IPv4分片只在目的IP对应的目的端系统进行重组
IPv4分片、重组字段在基本IP头部

标识、标志、片偏移


IPv6分片机制有较大变化（见IPv6部分的介绍）


注：分组 (packet) 与 帧(frame)的关系


3.1.4 IP协议功能及报头字段总结
网络层基本功能

支持多跳寻路将IP数据报送达目的端：目的IP地址
表明发送端身份：源IP地址
根据IP头部协议类型，提交给不同上层协议处理：协议

其它相关问题

数据报长度大于传输链路的MTU的问题，通过分片机制解决：标识、标志、片偏移
防止循环转发浪费网络资源（路由错误、设备故障…），通过跳数限制解决：生存时间TTL
IP报头错误导致无效传输，通过头部机校验解决：首部校验和

3.2 IP地址
3.2.1 概述


IP地址，网络上的每一台主机（或路由器）的每一个接口都会分配一个全球唯一的32位的标识符


将IP地址划分为固定的类，每一类都由两个字段组成


网络号相同的这块连续IP地址空间称为地址的前缀，或网络前缀


IP地址共分为A、B、C、D、E五类，A类、B类、C类为单播地址


IP地址的书写采用点分十进制记法，其中每一段取值范围为0到255



IP特殊地址


3.2.1 子网划分

子网划分(subnetting)，在网络内部将一个网络块进行划分以供多个内部网络使用，对外仍是一个网络
子网(subnet )，一个网络进行子网划分后得到的一系列结果网络称为子网
子网掩码(subnet mask )，与 IP 地址一一对应，是32 bit 的二进制数，置1表示网络位，置0表示主机位
子网划分减少了 IP 地址的浪费、网络的组织更加灵活、便于维护和管理




3.2.3 无类域间路由

将32位的IP地址划分为前后两个部分，并采用斜线记法，即在IP地址后加上“/”，然后再写上网络前缀所占位数



一个 CIDR 地址块可以表示很多地址，这种地址的聚合常称为路由聚合（route aggregation），也称为构成超网 (supernet)
聚合技术在Internet中大量使用，它允许前缀重叠，数据包按具体路由的方向发送，即具有最少IP地址的最长匹配前缀


注：当路由器收到一个IP数据包时，它会将数据包的目的IP地址与自己本地路由表中的所有路由表进行逐位（Bit-By-Bit）对比，直到找到匹配度最长的条目，这就是最长前缀匹配机制。（路由比对之前会用相应路由的目的网络掩码进行逻辑与运算，再拿结果与路由路径比对）

3.3 DHCP动态主机配置协议
DHCP ：动态主机配置协议

当主机加入IP网络，允许主机从DHCP服务器动态获取IP地址
可以有效利用IP地址，方便移动主机的地址获取

工作模式：客户/服务器模式（ C/S ）

基于 UDP 工作，服务器运行在 67 号端口， 客户端运行在 68 号端口


DHCP 客户从UDP端口68以广播形式向服务器发送发现报文（DHCPDISCOVER）
DHCP 服务器广播发出提供报文（DHCPOFFER）
DHCP 客户从多个DHCP服务器中选择一个，并向其以广播形式发送DHCP请求报文（DHCPREQUEST）
被选择的DHCP服务器广播发送确认报文（DHCPACK）

3.4 ARP地址解析协议
背景

网络设备有数据要发送给另一台网络设备时，必须要知道对方的网络层地址（即IP地址）。IP地址由网络层来提供，但是仅有IP地址是不够的，IP数据报文必须封装成帧才能通过数据链路进行发送。数据帧必须要包含目的MAC地址，因此发送端还必须获取到目的MAC地址。通过目的IP地址二获取的MAC地址的过程是由ARP（Address Resolution Protocol）协议来实现的。

注：因为下层协议是通过MAC地址来确定各自身份的，所以下层发送必须要MAC地址

IP 与 MAC地址


ARP协议工作过程



A已知B的IP地址，需要获得B的MAC地址（物理地址）
如果A的ARP表中缓存有B的IP地址与MAC地址的映射关系，则直接从ARP表获取
如果A的ARP表中未缓存有B的IP地址与MAC地址的映射关系，则A广播包含B的IP地址的ARP query分组

在局域网上的所有节点都可以接收到ARP query


B接收到ARP query分组后，将自己的MAC地址发送给A
A在ARP表中缓存B的IP地址和MAC地址的映射关系

超时时删除



路由到另一个局域网



A创建IP数据包（源为A、目的为E）
在源主机A的路由表中找到路由器R的IP地址223.1.1.4
A根据R的IP地址223.1.1.4，使用ARP协议获得R的MAC地址
A创建数据帧（目的地址为R的MAC地址）
数据帧中封装A到E的IP数据包
A发送数据帧，R接收数据帧

3.5 网络地址转换(NAT)
定义

网络地址转换(NAT)用于解决IPv4地址不足的问题，是一种将私有（保留）地址转化为公有IP地址的转换技术

私有IP地址：

A类地址：10.0.0.0–10.255.255.255

B类地址：172.16.0.0–172.31.255.555

C类地址：192.168.0.0–192.168.255.255

NAT工作机制




出数据报：外出数据报用 NAT IP地址(全局), 新port # 替代  源IP地址(私有), port #


NAT转换表：每个 (源IP地址, port #)到(NAT IP地址, 新port #) 映射项


入数据报：对每个入数据报的地址字段用存储在NAT表中的(源IP地址, port #)替代对应的 (NAT IP地址, 新port #)


NAT根据不同的IP上层协议进行NAT表项管理

TCP，UDP，ICMP


传输层TCP/UDP拥有16-bit 端口号字段

所以一个WAN侧地址可支持60,000个并行连接


NAT的优势

节省合法地址，减少地址冲突
灵活连接Internet
保护局域网的私密性

3.6 ICMP: 互联网控制报文协议
ICMP: 互联网控制报文协议

ICMP 允许主机或路由器报告差错情况和提供有关异常情况的报告
由主机和路由器用于网络层信息的通信
ICMP 报文携带在IP 数据报中： IP上层协议号为1

ICMP报文类型

ICMP 差错报告报文

终点不可达：不可达主机、不可达网络，无效端口、协议


ICMP 询问报文

回送请求/回答 (ping使用)



ICMP 报文格式



ICMP报文的前 4 个字节包含格式统一的三个字段：类型、代码、检验和
相邻的后四个字节内容与ICMP的报文类型有关

ICMP报文类型及功能


4.路由算法
路由算法须满足的特性：

正确性
简单性
鲁棒性
稳定性
公平性
有效性

根据路由算法是否随网络的通信量或拓扑自适应划分

静态路由选择策略（非自适应路由选择）
动态路由选择策略（自适应路由选择）

4.1 距离向量路由
算法基本思想


每个节点周期性地向邻居发送它自己到某些节点的距离向量；


当节点x接收到来自邻居的新DV估计，它使用B-F方程更新其自己的DV :

Dx(y) ← minv{c(x,v) + Dv(y)}    for each node y ∊ N


上述过程迭代执行，Dx(y)收敛为实际最小费用 dx(y)


距离向量算法特点：迭代的、分布式的

每次本地迭代由下列引起: 本地链路费用改变、邻居更新报文
分布式:各节点依次计算，相互依赖


注：路由器只掌握物理相连的邻居以及链路费用

算法过程


路由器启动时初始化自己的路由表

初始路由表包含所有直接相连的网络路径，距离均为0





路由器周期性地向其相邻路由器广播自己知道的路由信息


相邻路由器可以根据收到的路由信息修改和刷新自己的路由表




路由器经过若干次更新后，最终都会知道到达所有网络的最短距离


所有的路由器都得到正确的路由选择信息时网络进入“收敛”（convergence）状态



特殊情况考虑
计数到无穷问题（The Count-to-Infinity Problem）



好消息传播快，坏消息传播慢，是距离向量路由的一个主要缺点
4.2 链路状态路由

注：所有路由器掌握完整的网络拓扑和链路费用信息

算法过程
链路状态（Link State）路由可分为五个部分：


发现邻居，了解他们的网络地址；




设置到每个邻居的成本度量；




开销/度量/代价：

自动发现设置或人工配置
度量：带宽、跳数、延迟、负载、可靠性等


常用度量：链路带宽（反比）

例如：1-Gbps以太网的代价为1，100-Mbps以太网的代价为10


可选度量：延迟

发送一个echo包，另一端立即回送一个应答
通过测量往返时间RTT，可以获得一个合理的延迟估计值





构造一个分组，分组中包含刚收到的所有信息；


构造链路状态分组（link state packet，LSP）

发送方标识
序列号
年龄
邻居列表




将此分组发送给其他的路由器；



每个LSP分组包含一个序列号，且递增
路由器记录所收到的所有（源路由器、序列号）对
当一个新分组到达时，路由器根据记录判断：

如果是新分组，洪泛广播
如果是重复分组，丢弃
如果是过时分组，拒绝





计算到其他路由器的最短路径。


Dijkstra算法示例

D(k)：从计算节点到目的节点k当前路径代价

p(k)：从计算节点到目的节点k的路径中k节点的前继节点


距离向量和链路状态算法比较
网络状态信息交换的范围

DV:邻居间交换
LS:全网扩散

网络状态信息的可靠性

DV:部分道听途说
LS:自己测量

4.3 层次路由
产生原因

过于庞大的路由表存储、查找困难，路由信息交互开销高

现实情况：

地址分配往往是随机的，难以进行高效的地址聚合
每个网络的网络管理员有自己的管理方法和思路，并不希望每个路由器都干涉本网络内部的地址分配等问题

层次路由可以解决：

网络扩展性问题：当网络扩大时，控制路由表条目和路由表存储空间的增长
管理的自治问题：网络管理员可以控制和管理自己网络的路由

基本思路


互联网由大量不同的网络互连，每个管理机构控制的网络是自治的


自治系统（AS，Autonomous System）

一个管理机构控制之下的网络
一个AS内部通常使用相同的路由算法/路由协议，使用统一的路由度量（跳数、带宽、时延 …）
不同的AS可以使用不同的路由算法/路由协议
每个AS有一个全球唯一的ID号：AS ID



自治系统内的还可以进一步划分层次：私有自治系统或区域


效果


4.4 广播路由
广播（Broadcasting）：源主机同时给全部目标地址发送同一个数据包
实现方法
①给每个主机单独发送一个数据包

效率低、浪费带宽
Server需要知道每个目的地址

②多目标路由（multi-destination routing）

在需要转发的路由器线路复制一次该数据报
网络利用率高
Server依然需要知道所有的目的地址


注：以上方法难以实现

③泛洪（flooding）

一种将数据包发送到所有网络节点的简单方法
将每个进入数据包发送到除了进入线路外的每条出去线路

用途

保证性：一种有效广播手段，可确保数据包被传送到网络中每个节点
鲁棒性：即使大量路由器被损坏，也能找到一条路径（如果存在）
简单性：仅需知道自己的邻居

无控制的泛洪

实现广播最显而易见的技术
环路可能导致广播风暴
路由器可能收到多个副本
节点需要跟踪已泛洪的数据包以阻止洪泛
即使利用跳数来限制，也会出现成倍爆炸

解决方法：受控制的泛洪（每个路由器进行有选择的泛洪）

序号控制泛洪
逆向路径转发

④生成树（spanning tree）

源节点向所有属于该生成树的特定链路发送分组
改进了逆向路径转发
没有环路
最佳使用带宽
最少副本，消除了冗余分组
一个路由器可以不必知道整颗树，只需要知道在一颗树中的邻居即可


5.Internet路由协议
5.1 路由选择协议RIP
概述

路由选择协议RIP（ Routing Information Protocol）是基于距离矢量算法的协议
使用跳数衡量到达目的网络的距离

RIP 认为一个好的路由就是它通过的路由器的数目少，即“距离短”
RIP 允许一条路径最多只能包含 15 个路由器


RIP协议的基本思想

仅和相邻路由器交换信息
路由器交换的内容是自己的路由表
周期性更新：30s



工作过程

初始化



周期性更新



小结
RIP协议的特点

算法简单，易于实现
收敛慢
需要交换的信息量较大

RIP协议的适用场合

中小型网络

RIP协议的防环路机制

触发更新
毒性反转
水平分割
其他

5.2 BGP-外部网关路由协议
路由协议

内部网关协议 IGP： 有 RIP 和、OSPF、ISIS 等多种具体的协议
外部网关协议 EGP：目前使用的协议就是 BGP

边界网关协议BGP (Border Gateway Protocol)

目前互联网中唯一实际运行的自治域间的路由协议

BGP功能

eBGP：从相邻的AS获得网络可达信息
iBGP： 将网络可达信息传播给AS内的路由器
基于网络可达信息和策略决定到其他网络的“最优”路由

BGP会话: 两个BGP路由器通过TCP连接交换BGP报文

通告到不同网络前缀的路径，即路径向量协议

BGP路径通告



AS2的路由器2c从AS3的路由器3a接收到路径AS3, X
根据AS2的策略，AS2的路由器2c接受路径AS3, X，通过iBGP传播给AS2的所有路由器
根据AS2策略，AS2的路由器2a通过eBGP向AS1的路由器1c通告从AS3的路由器3a接收到路径AS2, AS3, X


路由器可能会学到多条到达目的网络的路径:

AS1的路由器1c从2a学到路径AS2,  AS3, X
AS1的路由器1c从3a学到路径AS3, X

由策略，AS1路由器1c可能选择路径AS3, X, 并在AS1中通过iBGP通告路径

6.路由器的工作原理
6.1 路由器概述
路由器是互联网最主要的网络设备，包含2个核心功能

控制层：运行各种路由协议：BGP、OSPF、RIP，学习去往不同目的的转发路径：路由表
数据层：根据上述路由表，将收到的IP分组转发到正确的下一跳链路


6.2 路由器控制层

路由器可同时运行多个路由协议
路由器也可不运行任何路由协议，只使用静态路由和直连路由
路由管理根据路由优先级，选择最佳路由，形成核心路由表
控制层将核心路由表下发到数据层，形成转发表（FIB）
若存在多个“去往同一目的IP前缀”的不同类型路由，路由器根据优先级选择最佳路由
优先级数值越小，优先级越高



6.3 路由器数据层
路由器中IP报文转发核心功能

链路层解封装，IP头部校验
获取报文目的IP地址
用目的IP地址，基于最长前缀匹配规则查询转发表
查询失败，丢弃报文
查询成功

获取转发出接口和下一跳IP地址
IP头部“TTL”字段值减1，重新计算IP头部“校验和”
重新进行链路层封装，发送报文




注：普通IP报文转发过程中，路由器不查看传输层及以上层协议的内容



IP报文在路由器转发前后的变化

链路层封装更新，IP头部“TTL”减1，IP头部“校验和”更新



数据报在不同硬件单元的处理

报文输入的接口卡

链路层解封装
转发表查询（该工作在输入接口卡处理）
通过交换结构将报文排队发往目的接口卡（发送过快将产生拥塞）


交换结构

从输入接口卡发往输出接口卡


报文输出的接口卡

从交换结构接收报文（排队进行后续处理，到达太快将产生拥塞）
链路层封装
从输出接口发送报文





3种典型的交换结构

7.拥塞控制算法
7.1 概述
拥塞

网络中存在太多的数据包导致数据包传输延迟或丢失，从而导致网络吞吐量下降
拥塞控制（congestion control）

需要确保通信子网能够承载用户提交的通信量，是一个全局性问题，涉及主机、路由器等多种因素
产生拥塞的原因

主机发送到网络的数据包数量过多，超过了网络的承载能力
突发的流量填满了路由器的缓冲区，造成某些数据包会被丢弃

拥塞控制的基本策略

开环控制----事先对通信流参数进行协商，协商后，不管网络是拥塞还是带宽充足，参数不能动态改变

开环控制属于预防性拥塞控制，它竭力使网络总是处于无拥塞状态运行。开环控制的方法包括决定什么时候接受新流量，什么时候丢弃数据包和丢弃哪些数据包。其缺点是没有考虑网络的当前状态


闭环控制—根据网络状态进行动态控制，包括两部分：反馈机制和控制机制。闭环控制方法分为两个子类：显式反馈与隐式反馈

7.2 流量调节

抑制包(Choke Packets)：用于通知发送方减小发送量，路由器选择一个被拥塞的数据包，给该数据包的源主机返回一个抑制包，抑制包中的目的地址取自该拥塞数据包。源主机收到抑制包后，减少发向特定目的地址的流量
逐跳的抑制包(Hop-by-Hop Choke Packets)：在高速或长距离网络中，由于源主机响应太慢，抑制包算法对拥塞控制的效果并不好，可采用逐跳抑制方法；其核心思想是抑制包对它经过的每个路由器都起作用，能够迅速缓解发生拥塞处的拥塞，但要求上游路由器有更大的缓冲区
显式拥塞通告（ECN，Explicit Congestion Notification），在IP包头中记录数据包是否经历了拥塞。在数据包转发过程中，路由器可以在包头中标记为经历拥塞，然后接收方在它的下一个应答数据包里显示该标记作为显式拥塞信号
RFC2474中重新定义TOS域为包含一个6位的区分服务码点(DSCP) 和2位未使用位；RFC3168重新定义RFC2474中TOS域未使用的两位为ECN域，包含如下值：

00：发送主机不支持ECN

01或者10：发送主机支持ECN

11：路由器正在经历拥塞

7.3 随机早期检测RED (Random Early Detection)

使路由器的队列维持两个参数，即队列长度最小门限 THmin 和最大门限 THmax
RED 对每一个到达的数据报都先计算平均队列长度 LAV
若平均队列长度小于最小门限 THmin ，则将新到达的数据报放入队列进行排队
若平均队列长度超过最大门限 THmax，则将新到达的数据报丢弃
若平均队列长度在最小门限 THmin  和最大门限THmax 之间，则按照某一概率 p 将新到达的数据报丢弃
RED 将路由器的到达队列划分成为三个区域



丢弃概率 p 与 THmin 和 Thmax 的关系

当 LAV <Thmin 时，丢弃概率 p = 0
当 LAV >Thmax 时，丢弃概率 p = 1
当 THmin < LAV < THmax时，  0  p  1

例如，按线性规律变化，从 0 变到 pmax

8.服务质量
8.1概述
问题的提出

互联网本身只能提供“尽力而为的服务”或称“尽最大努力交付的服务”
当互联网越来越多的用于传输多媒体信息时，由于这些实时业务对网络的传输延时、延时抖动等特性较为敏感，这样网络的传输质量就难以保障了
IP网络不能保证特定业务的QoS要求，已经成为IP网络发展的巨大障碍
网络的服务质量越来越多的引起人们的关注，甚至成为网络技术研究的热点问题

什么是网络服务质量？（QoS, Quality of Service）
QoS是网络在传输数据流时要满足一系列服务请求，具体可以量化为带宽、时延、抖动、丢包率等性能指标
8.2 流量整形
流量整形(traffic shaping)：其作用是限制流出某一网络的某一连接的流量与突发，使这类报文以比较均匀的速度向外发送
①漏桶算法

到达的数据包（网络层的PDU）被放置在底部具有漏孔的桶中（数据包缓存）
漏桶最多可以排队b个字节，漏桶的这个尺寸受限于内存。如果数据包到达的时候漏桶已经满了，那么数据包应被丢弃
数据包从漏桶中漏出，以常量速率（r字节/秒）注入网络，因此平滑了突发流量


②令牌桶算法

产生令牌：周期性的以速率r向令牌桶中增加令牌，桶中的令牌不断增多。如果桶中令牌数已到达上限，则丢弃多余令牌
消耗令牌：输入数据包会消耗桶中的令牌。在网络传输中，数据包的大小通常不一致。大的数据包相较于小的数据包消耗的令牌要多
判断是否通过：输入数据包经过令牌桶时存在两种可能：输出该数据包或者被丢弃。当桶中的令牌数量可以满足数据包对令牌的需求，则将数据包输出，否则将其丢弃


注：漏桶算法和令牌桶算法的区别在于漏桶算法输出的流量永远不可能超过一定限制，而令牌桶算法可以容忍短时间内的高流量输出，对于一些突发流量的需求比较友好

8.3 数据包调度
在同一个流的数据包之间以及在竞争流之间分配路由器资源的算法称为包调度算法，它负责分配带宽和其他路由器资源，负责确定把缓冲区中的哪些数据包发送到输出链路上

先来先服务FCFS（First-Come First-Serve）
公平队列算法（Fair Queueing/Round Robin）
加权公平队列算法（Weighted Fair Queueing）
优先级调度（Priority Scheduling）

9.三层交换
9.1 三层交换的技术背景

二层交换网络中的广播，限制了网络规模的扩展

交换机对目标地址无法匹配的数据帧进行广播转发
交换机对目标地址为广播地址的数据帧进行广播转发
交换机为维护生成树状态产生大量的桥协议数据单元(Bridge Protocol Data Unit，BPDU)
这些广播帧会大量消耗网络资源，并频繁影响用户的数据通信


VLAN虽然可以将广播的影响限定在一定范围内，但同时也隔离了正常的用户间数据通信
传统路由器致力于解决VLAN间互联互通，但是其转发效率和拓扑复杂性带来的网络通信瓶颈无法有效应对规模扩展

9.2 三层交换的动机

利用第三层协议中的信息来加强第二层交换功能，形成带有路由功能的交换
融合VLAN 间的二层隔离和三层互通，消除大规模网络中广播对性能的影响
简化网络配置，简化网络拓扑，优化网络管理，降低网络部署成本


9.3 三层交换机的工作原理

10.虚拟专用网VPN (Virtual Private Network)
10.1 VPN的技术背景

计算机网络按用途分类

专用、公用


专用网络的实现方式

使用专用链路：铺设、租用（费用高，不灵活）
使用公共链路：不安全


虚拟专用网VPN (Virtual Private Network)

专用网络的经济、可靠、灵活的解决方案
利用安全隧道技术将专用网络在公共网络上扩展


VPN的设计原则

安全性、隧道与加密、数据验证、用户验证、防火墙与攻击检测



10.2 VPN的原理

VPN指利用公用网络架设专用网络的远程访问技术
VPN通过隧道技术在公共网络上模拟出一条点到点的逻辑专线，从而达到安全数据传输的目的




VPN对数据机密性和完整性的保护



10.3 VPN的实现方式


用VPN连接合作伙伴




用VPN实现专用网络的远程访问




11.IPv6协议
初始动机：应付“32-bit地址空间耗尽”问题（CIDR和NAT都无法从根本上解决地址短缺问题），增加地址空间

IPv6 地址

地址长度为128bit，是IPv4地址长度的4倍
IPv6地址空间数量约为3*1038
IPv6地址表示法，冒分十六进制，x : x : x : x : x : x : x : x

简化方法：每个x前面的0可省略，可把连续的值为0的x表示为“::”, 且“::”只能出现1次
简化前地址，2001:0DA8:0000:0000:200C:0000:0000:00A5
简化后地址，2001:DA8:0000:0000:200C::A5



五、传输层
1.传输层概述

传输层位于应用层和网络层之间：

基于网络层提供的服务，向分布式应用程序提供通信服务


按照因特网的“端到端”设计原则：

应用程序只运行在终端上，即不需要为网络设备编写程序


站在应用程序的角度：

传输层应提供进程之间本地通信的抽象：即运行在不同终端上的应用进程仿佛是直接连在一起的



1.1 套接字

设想在应用程序和网络之间存在一扇“门”：

需要发送报文时：发送进程将报文推到门外
门外的运输设施（因特网）将报文送到接收进程的门口
需要接收报文时：接收进程打开门，即可收到报文


在TCP/IP网络中，这扇“门”称为套接字（socket），是应用层和传输层的接口，也是应用程序和网络之间的API

1.2 传输层提供的服务

因特网的网络层提供“尽力而为”的服务：

网络层尽最大努力在终端间交付分组，但不提供任何承诺
具体来说，不保证交付，不保证按序交付，不保证数据完整，不保证延迟，不保证带宽等


传输层的有所为、有所不为:

传输层可以通过差错恢复、重排序等手段提供可靠、按序的交付服务
但传输层无法提供延迟保证、带宽保证等服务



1.3 因特网传输层提供的服务

最低限度的传输服务：

将终端-终端的数据交付扩展到进程-进程的数据交付
报文检错


增强服务：

可靠数据传输
流量控制
拥塞控制


因特网传输层通过UDP协议和TCP协议，向应用层提供两种不同的传输服务：

UDP协议：仅提供最低限度的传输服务
TCP协议：提供基础服务和增强服务



2.传输层基本服务——复用和分用
2.1 复用和分用概述
传输层基本服务：将主机间交付扩展到进程间交付，通过复用和分用实现



复用：

发送方传输层将套接字标识置于报文段中，交给网络层
分用：

接收方传输层根据报文段中的套接字标识，将报文段交付到正确的套接字

2.2 套接字标识与端口号

端口号是套接字标识的一部分：

每个套接字在本地关联一个端口号
端口号是一个16比特的数


端口号的分类：

熟知端口：0～1023，由公共域协议使用
注册端口：1024～49151，需要向IANA注册才能使用
动态和/或私有端口：49152～65535，一般程序使用


报文段中有两个字段携带端口号

源端口号：与发送进程关联的本地端口号
目的端口号：与接收进程关联的本地端口号





2.3 TCP/UDP套接字（复用和分用）
UDP套接字

使用<IP地址，端口号>二元组标识UDP套接字
服务器使用一个套接字服务所有客户

TCP套接字
使用<源IP地址，目的IP地址，源端口号，目的端口号> 四元组标识连接套接字
服务器使用一个监听套接字和多个连接套接字服务多个客户，每个连接套接字服务一个客户

3.无连接传输：UDP
3.1 UDP报文段结构

UDP报文：

报头：携带协议处理需要的信息
载荷（payload）：携带上层数据


用于复用和分用的字段：

源端口号
目的端口号


用于检测报文错误的字段：

报文总长度
校验和（checksum）




3.2 UDP校验和（checksum）
校验和字段的作用:  对传输的报文段进行检错

以下是报文段的字段




key
human
hex




Source
192.168.1.106
c0a8 016a


Destination
11.111.111.111
0b6f 6f6f


Protocol
UDP(17)
11


Length
17
11


Source Port
63549
f83d


Destination Port
12345
3039


Length
17
11


Checksum
0xb12d
b12d


Data
hello UDP
6865 6c6c 6f20 5544 5000


将上表中所有的 16 进制数加起来，之后取反码。有一点需要注意的是，如果遇到最高位进位，那么需要对结果进行回卷，意思是

求出来的即是校验和。
3.3 为什么需要UDP？
为什么需要UDP？

应用可以尽可能快地发送报文：

无建立连接的延迟
不限制发送速率（不进行拥塞控制和流量控制）


报头开销小
协议处理简单

UDP适合哪些应用？

容忍丢包但对延迟敏感的应用：

如流媒体
以单次请求/响应为主的应用：

如DNS
若应用要求基于UDP进行可靠传输：

由应用层实现可靠性

4.面向连接的传输：TCP
4.1 可靠传输
数据包有序、无差错到达接收端
如何实现可靠传输，基本原则是什么？

利用ACK确认
重传机制
差错检测

可靠传输实现举例-Stop and Wait

注：该实现俗称tcp的三次握手和四次挥手。三次挥手我们也常称为“请求 -> 应答 -> 应答之应答”的三个回合，主要就是为了建立连接

建立一条TCP连接需要确定两件事：

双方都同意建立连接（知晓另一方想建立连接）
初始化连接参数（序号，MSS等）



四次挥手：目的就是确保断开连接时双方都是确认结束的状态

4.2 流水线技术
由于信道上一直有数据不间断地传送，这种传输方式可获得很高的信道利用率。


①GBN 协议（回退 N 步协议）
发送窗口

发送方维持的发送窗口，它的意义是：位于发送窗口内的分组都可连续发送出去，而不需要等待对方的确认。这样，信道利用率就提高了。

发送方每收到一个确认，就把发送窗口向前滑动一个分组的位置。


累积确认

接收方一般采用累积确认的方式。即不必对收到的分组逐个发送确认，而是对按序到达的最后一个分组发送确认，这样就表示：到这个分组为止的所有分组都已正确收到了。
优点：容易实现，即使确认丢失也不必重传。
缺点：不能向发送方反映出接收方已经正确收到的所有分组的信息。

如果发送方发送了前 5 个分组，而中间的第 3 个分组丢失了。这时接收方只能对前两个分组发出确认。发送方无法知道后面三个分组的下落，而只好把后面的三个分组都再重传一次。

这就叫做 Go-back-N（回退 N），表示需要再退回来重传已发送过的 N 个分组。

可见当通信线路质量不好时，连续 ARQ 协议会带来负面的影响。
②SR 协议（选择重传协议）
SR 协议在 GBN 协议的基础上进行了改进，它通过让发送方仅重传那些它怀疑在接收方出错（即丢失或受损）的分组而避免了不必要的重传。选择重传协议只重传真正丢失的分组。

选择重传的接收窗口与发送窗口一样大
选择重传协议允许与接收窗口一样多的分组失序到达,并保存这些失序到达的分组,直到连续的一组分组被交付给应用层。
标记发出分组,当ACK=Sf 时,将窗口滑过所有连续的已确认的分组

如果还有未确认的分组,则重发所有检测到的未被确认的分组并重启计时器
如果所有分组都被确认了则停止计时器


确认，确认号(ACK)只定义完好接收的那一个分组的序号,并不反馈任何其他分组的信息


注：SR协议ack确认和GBN的累计确认不同，是一个一个确认


计时器

理论上选择重传协议要为每个分组使用一个计时器。当某个计时器超时后,只有相应的分组被重传。换而言之，返回N协议将所有的分组当做一个整体对待，而选择重传协议则分别对待每一个分组。但是大多数SR的运输层仅使用了一个计时器.。注意只使用一个计时器而做到跟踪所有发出去的分组的情况的做法是：标记发出分组,当ACK=Sf 时,将窗口滑过所有连续的已确认的分组，如果还有未确认的分组，则重发所有检测到的未被确认的分组并重启计时器，如果所有分组都被确认了则停止计时器。


快速重传


仅靠超时重发丢失的报文段，恢复太慢！


发送方可利用重复ACK检测报文段丢失：

发送方通常连续发送许多报文段
若仅有个别报文段丢失，发送方将收到多个重复序号的ACK
多数情况下IP按序交付分组，重复ACK极有可能因丢包产生



TCP协议规定： 当发送方收到对同一序号的3次重复确认时，立即重发包含该序号的报文段


所谓快速重传，就是在定时器到期前重发丢失的报文段



③TCP 可靠通信的具体实现

TCP 连接的每一端都必须设有两个窗口——一个发送窗口和一个接收窗口。
TCP 的可靠传输机制用字节的序号进行控制。TCP 所有的确认都是基于序号而不是基于报文段。
TCP 两端的四个窗口经常处于动态变化之中。
TCP连接的往返时间 RTT 也不是固定不变的。需要使用特定的算法估算较为合理的重传时间

GBN、SR和TCP小结
Go-Back-N协议

接收方：

使用累积确认
不缓存失序的分组
对失序分组发送重复ACK

发送方：

超时后重传从基序号开始的所有分组

SR

接收方：

缓存失序的分组
单独确认每个正确收到的分组

发送方：

每个分组使用一个定时器
仅重传未被确认的分组

TCP协议
接收方：

使用累积确认
缓存失序的报文段
对失序报文段发送重复ACK
增加了推迟确认

发送方：

超时后仅重传最早未确认的报文段
增加了快速重传

4.3 TCP报文段结构


最大段长度（MSS）：

TCP段中可以携带的最大数据字节数
建立连接时，每个主机可声明自己能够接受的MSS，缺省为536字节


窗口比例因子（window scale）：

建立连接时，双方可以协商一个窗口比例因子
实际接收窗口大小 = window size * 2^window scale


选择确认（SACK）：

最初的TCP协议只使用累积确认
改进的TCP协议引入选择确认，允许接收端指出缺失的数据字节


发送序号和确认序号的含义



5.TCP流量控制
TCP接收端

使用显式的窗口通告，告知发送方可用的缓存空间大小
在接收窗口较小时，推迟发送确认
仅当接收窗口显著增加时，通告新的窗口大小

TCP发送端

使用Nagle算法确定发送时机
使用接收窗口限制发送的数据量，已发送未确认的字节数不超过接收窗口的大小


Nagle算法的解决方法：

在新建连接上，当应用数据到来时，组成一个TCP段发送（那怕只有一个字节）
在收到确认之前，后续到来的数据放在发送缓存中
当数据量达到一个MSS或上一次传输的确认到来（取两者的较小时间），用一个TCP段将缓存的字节全部发走



Nagle算法的优点：

适应网络延时、MSS长度及应用速度的各种组合 常规情况下不会降低网络的吞吐量


6.拥塞控制
发送方根据自己感知的网络拥塞程度，限制其发送速率
6.1 拥塞控制的类型

网络辅助的拥塞控制

路由器向端系统提供显式的反馈，例如：

设置拥塞指示比特
给出发送速率指示


ATM、X.25采用此类方法


端到端拥塞控制

网络层不向端系统提供反馈
端系统通过观察丢包和延迟，自行推断拥塞的发生
TCP采用此类方法



6.2  TCP拥塞控制要解决的问题
发送方如何感知网络拥塞？

发送方利用丢包事件感知拥塞：

拥塞造成丢包和分组延迟增大

-无论是丢包还是分组延迟过大，对于发送端来说都是丢包了


丢包事件包括：

-重传定时器超时

-发送端收到3个重复的ACK

发送方采用什么机制限制发送速率?


发送方使用拥塞窗口cwnd限制已发送未确认的数据量:

LastByteSent-LastByteAcked <= cwnd




cwnd随发送方感知的网络拥塞程度而变化


发送方感知到网络拥塞后，采取什么策略调节发送速率？
①AIMD

乘性减（Multiplicative Decrease）

发送方检测到丢包后，将cwnd的大小减半（但不能小于一个MSS）
目的：迅速减小发送速率，缓解拥塞


加性增（Additive Increase）

若无丢包，每经过一个RTT，将cwnd增大一个MSS，直到检测到丢包
目的：缓慢增大发送速率，避免振荡




注：MSS是发送速率TCP建立连接时双方确定的每一个报文段所能承载的最大数据长度


②TCP慢启动

慢启动的策略：

每经过一个RTT，将cwnd加倍


慢启动的具体实施：

每收到一个ACK段，cwnd增加一个MSS
只要发送窗口允许，发送端可以立即发送下一个报文段


特点：

以一个很低的速率开始，按指数增大发送速率



区分不同的丢包事件

超时：说明网络交付能力很差

收到3个重复的ACK：说明网络仍有一定的交付能力


收到3个重复的ACK：

将cwnd降至一半
使用AIMD调节cwnd


超时：

设置门限 =cwnd/2
cwnd=1MSS
使用慢启动增大cwnd至门限
使用AIMD调节cwnd



6.3 TCP拥塞控制的实现

发送方维护变量ssthresh
发生丢包时，ssthresh=cwnd/2
ssthresh是从慢启动转为拥塞避免的分水岭：

cwnd低于门限时，执行慢启动
cwnd高于门限：执行拥塞避免


拥塞避免阶段，拥塞窗口线性增长：

每当收到ACK， cwnd=cwnd + MSS*(MSS/cwnd)


检测到3个重复的ACK后：

TCP Reno实现： cwnd= ssthresh+3，线性增长
TCP Tahoe实现：cwnd=1 MSS，慢启动





TCP发送端的事件与动作


六、应用层
1.应用层概述

每个应用层协议都是为了解决某一应用问题，通过位于不同主机中的多个应用进程之间的通信和协同工作来完成

两台主机通信实际是其对应的两个应用进程(process)在通信
应用进程: 为解决具体应用问题而彼此通信的进程


应用层的具体内容就是规定应用进程在通信时所遵循的协议

客户/服务器（C/S, Client/Server）方式
对等（P2P，Peer to Peer）方式



1.1 应用进程通信方式
①客户/服务器（C/S, Client/Server）方式

应用层的许多协议是基于C/S方式，例如，在移动互联网环境下，每个应用APP都是一个客户端

客户(client)和服务器(server)是指通信中所涉及的2个应用进程
客户/服务器方式描述的是应用进程之间服务和被服务的关系
客户是服务请求方（主动请求服务，被服务）
服务器是服务提供方（被动接受服务请求，提供服务）


C/S方式可以是面向连接的，也可以是无连接的
面向连接时，C/S通信关系一旦建立，通信就是双向的，双方地位平等，都可发送和接收数据


客户进程的特点

在进行通信时临时成为客户，它也可在本地进行其它的计算
用户计算机上运行，在打算通信时主动向远地服务器发起通信
客户方必须知道服务器进程所在主机的IP地址才能发出服务请求
需要时可以与多个服务器进行通信

服务器进程的特点

专门用来提供某种服务的程序，可“同时”处理多个远地或本地客户的请求
必须始终处于运行状态才有可能提供服务
通信开始之前服务器进程不需要知道客户进程所在主机的IP地址，无论客户请求来自哪里，服务器进程被动等待服务请求的到来即可
通常是当系统启动时即自动调用并一直运行着。某些服务器程序也可以由用户或其它进程在通信前启动
被动等待并接受来自多个客户的通信请求

②对等（P2P，Peer to Peer）方式

对等方式是指两个进程在通信时并不区分服务的请求方和服务的提供方

只要两个主机都运行P2P软件，它们就可以进行平等、对等的通信
双方都可以下载对方存储在硬盘中的共享文档，如果权限允许的话


音频/视频应用推动了P2P对等通信方式的发展（BitTorrent）
音频/视频流量已占主要比
P2P方式从本质上看仍然是使用了C/S方式，但强调的是通信过程中的对等，这时每一个P2P进程既是客户同时也是服务器


1.2 服务器进程工作方式


循环方式(iterative mode)

一次只运行一个服务进程
当有多个客户进程请求服务时，服务进程就按请求的先后顺序依次做出响应 (阻塞方式)



并发方式(concurrent mode)

可以同时运行多个服务进程
每一个服务进程都对某个特定的客户进程做出响应 (非阻塞方式)



无连接循环方式服务

使用无连接的UDP服务进程通常都工作在循环方式，即一个服务进程在同一时间只能向一个客户进程提供服务。(顺序服务)
服务进程收到客户进程的请求后，就发送UDP用户数据报响应该客户
对其他客户进程发来的请求则暂时不予理睬，这些请求都在服务端的队列中排队等候服务进程的处理
当服务进程处理完毕一个请求时，就从队列中读取来自下一个客户进程的请求，然后继续处理




面向连接的并发方式服务

面向连接的TCP服务进程通常都工作在并发服务方式，服务进程在同一时间可同时向多个客户进程提供服务。(并发服务)
在TCP服务进程与多个客户进程之间必须建立多条TCP连接，每条TCP连接在其数据传送完毕后释放
一个TCP连接对应一个（熟知）服务端口
主服务进程在熟知端口等待客户进程发出的请求。一旦收到客户的请求，就创建一个从属服务进程，并指明从属服务进程使用临时套接字与该客户建立TCP连接，然后主服务进程继续在原来的熟知端口等待向其他客户提供服务





2.域名系统
2.1 概述

域名系统（DNS，Domain Name System）是互联网重要的基础设施之一，向所有需要域名解析的应用提供服务，主要负责将可读性好的域名映射成IP地址
Internet采用层次结构的命名树作为主机的名字，并使用分布式的域名系统 DNS。Internet的DNS是一个联机分布式数据库系统
名字到域名的解析是由若干个域名服务器程序完成的。域名服务器程序在专设的结点上运行，相应的结点也称为名字服务器(Name Server)或域名服务器(Domain Name Server)


2.2 域名系统名字空间和层次结构


2.3 域名解析过程

递归查询

当收到查询请求报文的域名服务器不知被查询域名的IP地址时，该域名服务器就以DNS客户的身份向下一步应查询的域名服务器发出查询请求，即替本地域名字服务器继续查询
较少使用




迭代查询

当收到查询请求报文的域名服务器不知道被查询域名的IP地址时，就把自己知道的下一步应查询的域名服务器IP地址告诉本地域名字服务器，由本地域名字服务器继续向该域名服务器查询，直到得到所要解析的域名的IP地址，或者查询不到所要解析的域名的IP地址
通常使用




3.电子邮件
3.1 邮件发送的常用协议
简单邮件传输协议SMTP（Simple Mail Transfer Protocol）——邮件服务器之间传递邮件使用的协议

最终交付（邮件访问）协议::从邮件服务器的邮箱中获取邮件

POP3：Post Office Protocol-Version 3，第三版邮局协议
IMAP：Internet Message Access Protocol，Internet邮件访问协议
Webmail（HTTP）：基于Web的电子邮件




3.2 Webmail
Webmail——基于Web的电子邮件

提供电子邮件服务的IMAP和SMTP替代方案
使用Web作为界面，用户代理就是普通的浏览器
用户及其远程邮箱之间的通信通过HTTP进行


4.WWW
4.1 WWW体系结构与协议

WWW=World Wide Web=万维网
HTTP服务器和客户端，以及它们之间执行的HTTP协议



服务器

Web页面（HTML文档）：包含多种对象或链接
Web对象（包括：静态对象和动态对象）：可以是 HTML文档、 图像文件、视频文件、声音文件、脚本文件等
对象用URL（统一资源定位符）编址：协议类型://主机名:端口//路径和文件名

客户端

发出请求、接收响应、解释HTML文档并显示
有些对象需要浏览器安装插件


统一资源定位器URLs


www协议


4.2 HTTP
概述

超文本传输协议HTTP（ HyperText Transfer Protocol）在传输层通常使用TCP协议，缺省使用TCP的80端口
HTTP为无状态协议，服务器端不保留之前请求的状态信息

无状态协议：效率低、但简单
有状态协议：维护状态相对复杂，需要维护历史信息，在客户端或服务器出现故障时，需要保持状态的一致性等


HTTP标准

HTTP/1.0: RFC 1945（1996年）
HTTP/1.1: RFC 2616（1999年）
HTTP/2: RFC 7540（2015年）、RFC 8740（2020年）



HTTP发展现状

HTTP/1.0（1996）

无状态，非持久连接


与HTTP/1.1（1999）

支持长连接和流水线机制
缓存策略优化、部分资源请求及断点续传


HTTPS：HTTP+TLS（2008）

增加SSL/TLS（TLS 1.2）层，在TCP之上提供安全机制


HTTP/2.0（2015、2020）

目标：提高带宽利用率、降低延迟
增加二进制格式、TCP多路复用、头压缩、服务端推送等功能




Web安全与隐私：Cookie
HTTP 无状态协议，服务器 用cookies保持用户状态

HTTP在响应的首部行里使用一个关键字头set-cookie：选择的cookie号具有唯一性
后继的HTTP请求中使用服务器响应分配的cookie：
Cookie文件保存在用户的主机中，内容是服务器返回的一些附加信息，由用户主机中的浏览器管理
Web服务器建立后端数据库，记录用户信息，cookie作为关键字

例如：

Set-Cookie: SID=31d4d96e407aad42; Path=/; Domain=example.com

Cookie:  SID=31d4d96e407aad42





Cookies一般包含5个字段

域指明Cookie来自何方，每个域为每个客户分配Cookie有数量限制
路径标明服务器的文件树中哪些部分可以使用该Cookie
内容采用“名字=值”的形式，是Cookie存放内容的地方，可以达到4K容量，内容只是字符串，不是可执行程序
安全指示浏览器只向使用安全传输连接的服务器返回Cookie





Cookie技术是把双刃剑，能分析用户喜好，向用户进行个性化推荐

用Cookie在某网站标识用户信息，查找用户以前浏览网站记录
用Cookie记录用户购物清单
用Cookie可以保存4K内容，跟踪用户浏览网站的喜好
用Cookie跨站点跟踪用户点击广告


Cookie技术是把双刃剑，也能跟踪用户网络浏览痕迹，泄露用户隐私

Cookie跟踪用户以前浏览过哪些网站，跟踪用户频繁浏览哪类网站
Cookie收集用户信息，用户网络交互时关注的关键词


Cookie容易嵌入间谍程序，这是个误区，Cookie文件保存的只是文本串，没有可执行程序

用户可以设置浏览器限制使用Cookie



5.流媒体
5.1 概述

流媒体概念

连续媒体（音视频）经压缩编码、数据打包后，经过网络发送给接收方
接收方对数据进行重组、解码和播放


流媒体的特性

端到端时延约束
时序性约束：流媒体数据必须按照一定的顺序连续播放
具有一定程度的容错性：丢失部分数据包也可完成基本功能


流媒体面临的挑战

约束条件：网络特性（带宽有限、动态变化、延迟与抖动、丢失、异构性）
目标：流媒体服务质量要素（画质、启动延迟、平滑、交互性）
如何在“尽力服务”的网络传输条件下获得良好的视频质量？



5.2 流媒体动态自适应传输

DASH (Dynamic Adaptive Streaming over HTTP)

动态自适应流媒体传输协议DASH，由MPEG组织制定的标准
类似协议：苹果HTTP Live Streaming（HLS）； Adobe的HTTP Dynamic Streaming（HDS）；微软的Microsoft Smooth Streaming


DASH 基本思想

完整视频被拆分为固定时长 (2s-10s) 的视频片段(segment)， 每段提供不同码率
视频片段与其对应的元文件（URL）一同存放于DASH服务器
客户端基于网络条件、缓冲大小等，对每个视频片段，自适应选择合适的视频码率来下




DASH中普遍使用的自适应码率ABR（Adaptive bitrate）
6.内容分发网络CDN
6.1 概述

内容分发网络CDN

Content Delivery Network，or Content Distribution Network


基本思想源于MIT对Web服务瞬间拥塞问题的解决（1998）

一种Web缓存系统，靠近网络边缘（用户）提供内容服务
目前提供更丰富的服务，包括静态内容、流媒体、用户上传视频等


主要优点

降低响应时延，避免网络拥塞
避免原始服务器过载及防止DDoS攻击
分布式架构，具有良好的可扩展性
对用户透明，无需用户感知



6.2 关键问题
怎样将内容（如从百万的视频中选定的内容）分发给同时发起访问的数百万用户？
6.3 机理与解决方式
DNS重定向实现CDN

将请求调度到较近或负载较轻的CDN服务器
HTTP重定向请求内容，服务提供者返回清单CDN

原始服务器决策CDN服务器
HTTP响应：状态码30X，Location：指明新的位置



DNS辅助实现CDN

负载均衡DNS负责决策CDN服务器选择
负载均衡DNS需要收集CDN服务器的位置和负载情况
如果找不到被请求的对象，需要从原始服务器获取


7.P2P网络
P2P文件分发协议：BitTorrent

文件被划分为256Kb大小的块
具有种子(torrents)的节点发送或接收文件


8.远程登录Telnet

Telnet协议引入网络虚拟终端NVT（Network Virtual Terminal），使用一种专门的键盘定义来屏蔽不同计算机系统对键盘输入的差异性，同时定义客户进程与远程服务器进程之间的交互过程
NVT是Telnet协议定义的一组通用字符集，通过这种统一的数据表示方式，来保证不同硬件、软件与数据格式的终端与主机之间通信的兼容性
本地终端输入的字符首先由本地Telnet客户进程转换为NVT格式，通过网络将NVT格式的字符传输到远程主机，远程Telnet服务器进程再将NVT格式的字符转换为远程主机能够识别和处理的字符格式
使用Telnet协议在网络中传输的数据都是NVT格式，不同的用户终端与服务器进程均与本地终端格式无关

Telnet的工作过程

本地Telnet客户进程与远程主机上的Telnet服务器进程建立TCP连接
将本地终端上输入的用户名和口令及以后输入的任何命令或字符以网络虚拟终端NVT格式传输给远程主机
将远程主机输出的NVT格式的数据转化为本地所接受的格式送回本地终端，包括输入命令回显和命令执行结果
本地终端对远程主机撤销连接，从而结束 Telnet远程登录过程


9.FTP
9.1 概述
文件传输协议FTP(File Transfer Protocol)  是Internet上使用最广泛的应用层协议之一

FTP提供交互式的访问，允许用户指明文件的类型与格式，并允许文件具有存取权限
FTP屏蔽了各计算机系统的细节，适用于在异构网络中任意计算机之间传送文件
RFC 959早在1985年就已经成为Internet的正式标准
FTP使用C/S方式实现

9.2 工作过程

服务器主进程打开TCP21端口，等待客户进程发出的连接请求
客户可以用分配的任意一个本地端口号与服务器进程的TCP21端口进行连接
客户请求到来时，服务器主进程启动从属进程来处理客户进程发来的请求
服务器从属进程对客户进程的请求处理完毕后即终止，但从属进程在运行期间根据需要还可能创建其他一些子进程
服务器主进程返回，继续等待接收其他客户进程发来的连接请求，服务器主进程与从属进程并行工作

FTP的两个端口与两个连接

控制连接在整个会话期间一直保持，客户进程发出的文件传输请求通过控制连接发送给服务器控制进程（工作在TCP21端口），但控制连接不用来传输文件
服务器控制进程在接收到客户进程发送来的文件传输请求后就创建数据传输进程（工作在TCP20端口）和数据连接
数据连接用来连接客户进程和服务器数据传输进程，实际完成文件的传输。服务器数据传输进程在文件传输完毕后关闭数据连接并结束运行


写在最后
这篇知识汇总我写了好久，因为ppt的缘故，知识整理需要自己消化一遍然后挑选重要的部分整理摘录下来，同时对于某些知识点的组织结构做了相应调整，对于不太清楚的地方，我也去查阅了相关资料做了补充。但需要注意的是有些知识点并不完整，该知识点整理也只是根据我们当时考试的考点来整理的，所以不足之处请见谅。
愿我们以梦为马，不负人生韶华！

与君共勉

1 断言使用：


NSAssert(<#condition#>, <#desc, ...#>)
如：NSAssert(falg==YES,
@"RETURN IS YES");
2 case执行：


新建Scheme，选择测试的target，
在product中，选择test，进行case执行


3 以上描述的case执行，会去执行全部的case，可以选择单个case的执行


点击代码左侧栏，有个回放button，可以执行单个case，结果同样会打在console里面

基于严蔚敏及吴伟民编著的清华大学C语言版教材并结合网上相关资料整理(http://www.docin.com/p-2027739005.html)

第一章：绪论

1.数据结构：是一门研究非数值计算的程序设计问题中计算机的操作对象以及他们之间的关系和操作等的学科。

2.数据结构涵盖的内容：



3.基本概念和术语:

数据：对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。

数据元素：数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

数据对象：性质相同的数据元素的集合，是数据的一个子集。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合。

数据类型：一个值的集合和定义在这个值集上的一组操作的总称。

4.算法和算法分析

1）算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。

算法五个特性：有穷性，确定性，可行性，输入，输出。

2）算法设计要求：正确性，可读性，健壮性，效率与低存储量需求。

3）算法分析：时间复杂度，空间复杂度，稳定性

 

第二章：线性表

1.线性结构特点：在数据元素的非空有限集合中，(1)存在唯一的一个被称做“第一个”的数据元素；(2)存在唯一的一个被称做“最后一个”的数据元素；(3)除第一个之外，集合中的每个数据元素均只有一个前驱；(4)除最后一个之外，集合中每个数据元素均只有一个后继。

2.线性表定义：有限个性质相同的数据元素组成的序列。



3.线性表的存储结构：顺序存储结构和链式存储结构

顺序存储定义：把逻辑上相邻的数据元素存储在物理上相邻的存储单元中的存储结构。

通常用数组来描述数据结构中的顺序存储结构。

链式存储结构: 其结点在存储器中的位置是随意的，即逻辑上相邻的数据元素在物理上不一定相邻。通过指针来实现。

数据结构的基本运算：修改、插入、删除、查找、排序

4.线性表的顺序表示和实现

1）修改：通过数组的下标便可访问某个特定元素并修改。

时间复杂度O(1)

2） 插入:在线性表的第i个位置前插入一个元素

实现步骤：

   ①将第n至第i 位的元素逐一向后移动一个位置；

   ②将要插入的元素写到第i个位置；

   ③表长加1。

   注意：事先应判断: 插入位置i 是否合法?表是否已满?

   应当符合条件： 1≤i≤n+1  或  i=[1, n+1]

   核心语句：

for (j=n; j>=i; j--)

a[j+1]=a[ j ]; 

a[ i ]=x;   

n++;

  插入时的平均移动次数为：n(n+1)/2÷（n+1）＝n/2≈O(n)

3）删除：删除线性表的第i个位置上的元素

  实现步骤：

  ①将第i+1 至第n 位的元素向前移动一个位置；

  ②表长减1。

  注意：事先需要判断，删除位置i 是否合法?

  应当符合条件：1≤i≤n  或  i=[1, n]

  核心语句：

{

    for ( j=i+1; j<=n; j++ )

    a[j-1]=a[j]; 

    n--;

}

  顺序表删除一元素的时间效率为:T(n)=(n-1)/2 ≈O(n)

  顺序表插入、删除算法的平均空间复杂度为O(1)

5.线性表的链式表示和实现

线性链表：用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的）。

一个数据元素称为一个结点，包括两个域：存储数据元素信息的域称为数据域；存储直接后继存储位置的域称为指针域。指针域中存储的信息称作指针或链。

由于链表的每个结点中只包含一个指针域，故线性链表又称为单链表。

1）单链表的修改(或读取）

思路：要修改第i个数据元素，必须从头指针起一直找到该结点的指针p，return p;  

然后才能：p->data=new_value

读取第i个数据元素的核心语句是：

Linklist *find(Linklist *head ,int i)

{ 

   int j=1;

   Linklist *p;

   P=head->next;

   While((p!=NULL)&&(j<i))

   {

       p=p->next;

       j++;

    }

}

2）单链表的插入





链表插入的核心语句：

Step 1：s->next=p->next;

Step 2：p->next=s；

3）单链表的删除



删除动作的核心语句（要借助辅助指针变量q）：

q = p->next;           //首先保存b的指针，靠它才能找到c；

p->next=q->next;  //将a、c两结点相连，淘汰b结点；

free(q) ；               //彻底释放b结点空间

4）双向链表的插入操作



设p已指向第i 元素，请在第 i 元素前插入元素 x：

① ai-1的后继从 ai ( 指针是p)变为 x（指针是s) :

                s->next = p  ;   p->prior->next = s ;

② ai  的前驱从ai-1 ( 指针是p->prior)变为 x ( 指针是s);

                s->prior = p ->prior ; p->prior = s ;

5）双向链表的删除操作



设p指向第i 个元素，删除第 i 个 元素

后继方向：ai-1的后继由ai ( 指针p)变为ai+1(指针 p ->next );

                   p ->prior->next =  p->next  ;

前驱方向：ai+1的前驱由ai ( 指针p)变为ai-1 (指针 p -> prior );

                 p->next->prior = p ->prior ;

6.循环链表

循环链表是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点，整个链表形成一个环。

循环链表的操作和线性链表基本一致，差别仅在于算法中的循环条件不是p或p->next是否为空，而是它们是否等于头指针。

学习重点：


	
线性表的逻辑结构，指线性表的数据元素间存在着线性关系。在顺序存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。
	
	

	
顺序存储结构用一维数组表示，给定下标，可以存取相应元素，属于随机存取的存储结构。
	
	

	
链表操作中应注意不要使链意外“断开”。因此，若在某结点前插入一个元素，或删除某元素，必须知道该元素的前驱结点的指针。
	
	

	
掌握通过画出结点图来进行链表（单链表、循环链表等）的生成、插入、删除、遍历等操作。
	
	

	
数组（主要是二维）在以行序/列序为主的存储中的地址计算方法。
	
补充重点：


	
每个存储结点都包含两部分：数据域和指针域(链域)
	
	

	
在单链表中，除了首元结点外，任一结点的存储位置由 其直接前驱结点的链域的值 指示。
	
	

	
在链表中设置头结点有什么好处？
	
    头结点即在链表的首元结点之前附设的一个结点，该结点的数据域可以为空，也可存放表长度等附加信息，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理，编程更方便。


	
如何表示空表？
	
（1）无头结点时，当头指针的值为空时表示空表；

（2）有头结点时，当头结点的指针域为空时表示空表。


	
链表的数据元素有两个域，不再是简单数据类型，编程时该如何表示？
	
 因每个结点至少有两个分量，且数据类型通常不一致，所以要采用结构数据类型。


	
sizeof(x)——  计算变量x的长度（字节数）；
	
          malloc(m) —  开辟m字节长度的地址空间，并返回这段空间的首地址；

          free(p)   —— 释放指针p所指变量的存储空间，即彻底删除一个变量。


	
链表的运算效率分析：
	
（1）查找 

因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为 O(n)。

（2） 插入和删除 

因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为 O(1)。

但是，如果要在单链表中进行前插或删除操作，因为要从头查找前驱结点，所耗时间复杂度将是 O(n)。

例：在n个结点的单链表中要删除已知结点*P，需找到它的前驱结点的地址，其时间复杂度为 O（n）


	
顺序存储和链式存储的区别和优缺点？
	
    顺序存储时，逻辑上相邻的数据元素，其物理存放地址也相邻。顺序存储的优点是存储密度大，存储空间利用率高；缺点是插入或删除元素时不方便。

　　链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针。链式存储的优点是插入或删除元素时很方便，使用灵活。缺点是存储密度小，存储空间利用率低。


	
顺序表适宜于做查找这样的静态操作；
	
	

	
链表宜于做插入、删除这样的动态操作。
	
	

	
若线性表的长度变化不大，且其主要操作是查找，则采用顺序表；
	
	

	
若线性表的长度变化较大，且其主要操作是插入、删除操作，则采用链表。
	
① 数组中各元素具有统一的类型；

② 数组元素的下标一般具有固定的上界和下界，即数组一旦被定义，它的维数和维界就不再改变。

③数组的基本操作比较简单，除了结构的初始化和销毁之外，只有存取元素和修改元素值的操作。


	
三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素的 行下标  、列下标 和 元素值 。
	
第三章：栈和队列

1.栈:限定仅在表尾进行插入或删除操作的线性表。

栈的基本操作：在栈顶进行插入或删除，栈的初始化、判空及取栈顶元素等。

入栈口诀：堆栈指针top “先压后加”

出栈口诀：堆栈指针top “先减后弹”

top=0表示空栈。

 

2.栈的表示和实现

     1)构造一个空栈S

    Status InitStack(SqStack &S)

    {

        S.base = (SElemType *) malloc(STACK_INIT_SIZE * sizeof(SElemType));

        if(!S.base) exit (OVERFLOW); //存储分配失败

            S.top = S.base;

            S.stacksize = STACK_INIT_SIZE;

            return OK;

    }

 

    2)返回栈顶元素

       Status GetTop(SqStack S, SElemType e) 

        {//若栈不空，则用e返回S的栈顶元素，并返回OK，否则返回ERROR

            if(S.top == S.base) return ERROR;

            e = *(S.top-1);

            return OK; 

        }//GetTop

 

    3)顺序栈入栈函数PUSH（）

Status Push(SqStack &S, SElemType e)

{ //插入元素e为新的栈顶元素

    if(S.top-S.base>=S.stacksize)//栈满，追加存储空间

   {

    s.base = (SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));

    if(!S.base) exit(OVERFLOW);//存储分配失败

    S.top = S.base + S.stacksize;

    S.stacksize += STACKINCREMENT;

    }

    *S.top++ =e;

    return OK:

}//PUSH

4)顺序栈出栈函数POP()

status Pop( SqStack &S,SElemType &e)

{ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK,否则返回ERROR

    if(S.top == S.base) return ERROR; 

    e=* —S.top;

    return OK;

        }

3.栈的应用

数制转换，括号匹配的检验，行编辑程序，迷宫求解，表达式求值，递归实现。

4.队列：是一种先进先出的线性表，它只允许在表的一端进行插入，而在另一端删除元素。

允许插入的一端叫做队尾，允许删除的一端叫做队头。

除了栈和队列外，还有一种限定性数据结构是双端队列。双端队列是限定插入和删除操作在表的两端进行的线性表。

5.链队列结点类型定义：

 typedef Struct QNode{

     QElemType        data;     //元素

     Struct   QNode   *next;  //指向下一结点的指针

   }Qnode , * QueuePtr ;

链队列类型定义：

 typedef  struct {

  QueuePtr     front ; //队首指针

  QueuePtr     rear ; //队尾指针

  }  LinkQueue;

链队示意图：



①  空链队的特征：front=rear

②  链队会满吗？一般不会，因为删除时有free动作。除非内存不足！

③  入队（尾部插入）：rear->next=S; rear=S;

    出队（头部删除）：front->next=p->next;

6.顺序队

顺序队类型定义：

#define    QUEUE-MAXSIZE  100  //最大队列长度

     typedef    struct {

            QElemType     *base;    //队列的基址

             int                    front;     //队首指针

             int                     rear;    //队尾指针

       }SqQueue

建队核心语句：

q.base=(QElemType *)malloc(sizeof (QElemType)* QUEUE_MAXSIZE);       //分配空间

顺序队示意图：



7.循环队列：

队空条件 :  front = rear       (初始化时：front = rear )

队满条件： front = (rear+1) % N         (N=maxsize)

队列长度（即数据元素个数）：L=（N＋rear－front）% N

1)初始化一个空队列

Status   InitQueue ( SqQueue  &q ) //初始化空循环队列 q

{   

q.base=(QElemType *)malloc(sizeof(QElemType）* QUEUE_MAXSIZE);   //分配空间

if (!q.base)  exit(OVERFLOW);//内存分配失败，退出程序

   q.front =q.rear=0; //置空队列

    return OK;

 } //InitQueue;

 

2)入队操作

Status   EnQueue(SqQueue  &q,  QElemType e)

{//向循环队列 q 的队尾加入一个元素 e

   if ( (q.rear+1) %  QUEUE_MAXSIZE ==  q.front)

                    return  ERROR ; //队满则上溢，无法再入队

        q.rear = ( q.rear + 1 ) %  QUEUE_MAXSIZE;

        q.base [q.rear] = e;    //新元素e入队

        return  OK;

 }// EnQueue;

 

3)出队操作

Status     DeQueue ( SqQueue  &q,    QElemType &e)

 {//若队列不空，删除循环队列q的队头元素，

        //由 e 返回其值，并返回OK

      if ( q.front = = q.rear )   return ERROR;//队列空

      q.front=(q.front+1) % QUEUE_MAXSIZE; 

      e = q.base [ q.front ] ;

     return OK;

    }// DeQueue


	
链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两种方法。
	
补充重点：


	
为什么要设计堆栈？它有什么独特用途？
	
	

	
什么叫“假溢出” ？如何解决？
	
① 调用函数或子程序非它莫属；

② 递归运算的有力工具；

③ 用于保护现场和恢复现场；

④ 简化了程序设计的问题。                         

2.为什么要设计队列？它有什么独特用途？

① 离散事件的模拟（模拟事件发生的先后顺序,例如 CPU芯片中的指令译码队列）；

② 操作系统中的作业调度（一个CPU执行多个作业）；

③ 简化程序设计。

答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。解决假溢出的途径———采用循环队列。

4.在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是先 移动队首位置 ，后 取出元素。

5.线性表、栈、队的异同点：

相同点：逻辑结构相同，都是线性的；都可以用顺序存储或链表存储；栈和队列是两种特殊的线性表，即受限的线性表（只是对插入、删除运算加以限制）。

不同点：① 运算规则不同：

线性表为随机存取；

而栈是只允许在一端进行插入和删除运算，因而是后进先出表LIFO；

队列是只允许在一端进行插入、另一端进行删除运算，因而是先进先出表FIFO。

② 用途不同，线性表比较通用；堆栈用于函数调用、递归和简化设计等；队列用于离散事件模拟、OS作业调度和简化设计等。

 

第四章：串

1.串是数据元素为字符的线性表，串的定义及操作。

串即字符串，是由零个或多个字符组成的有限序列，是数据元素为单个字符的特殊线性表。

串比较：int strcmp(char *s1,char *s2);            

求串长：int strlen(char *s);                          

串连接：char  strcat(char *to,char *from)   

子串T定位：char strchr(char *s,char *c);

2.串的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小”的问题。

模式匹配算法 。

串有三种机内表示方法：

 

3.模式匹配算法 ：

算法目的：确定主串中所含子串第一次出现的位置（定位）

定位问题称为串的模式匹配，典型函数为Index(S,T,pos)

BF算法的实现—即编写Index(S, T, pos)函数

BF算法设计思想：

将主串S的第pos个字符和模式T的第1个字符比较，

若相等，继续逐个比较后续字符；

若不等，从主串S的下一字符（pos+1）起，重新与T第一个字符比较。 

直到主串S的一个连续子串字符序列与模式T相等。返回值为S中与T匹配的子序列第一个字符的序号，即匹配成功。

否则，匹配失败，返回值 0。

Int Index_BP(SString S, SString T, int pos)

{ //返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数值为0.

 // 其中，T非空，1≤pos≤StrLength(S)

    i=pos;      j=1;

   while ( i<=S[0] && j<=T[0] ) //如果i,j二指针在正常长度范围，

     {  

       if (S[i] = = T[j] ) {++i, ++j; }   //则继续比较后续字符

       else {i=i-j+2; j=1;} //若不相等，指针后退重新开始匹配

      }

  if(j>T[0]) return i-T[0];  //T子串指针j正常到尾，说明匹配成功，  else return 0;        //否则属于i>S[0]情况，i先到尾就不正常

} //Index_BP

补充重点：

1.空串和空白串有无区别？

答：有区别。

空串(Null String)是指长度为零的串；

而空白串(Blank  String),是指包含一个或多个空白字符‘  ’(空格键)的字符串.

2.“空串是任意串的子串；任意串S都是S本身的子串，除S本身外，S的其他子串称为S的真子串。”



 

第五章：数组和广义表

重点：二维数组的位置计算。

矩阵的压缩存储：特殊矩阵(三角矩阵，对称矩阵)，稀疏矩阵，

 

第六章：树和二叉树

1.树：是n(n≥0)个结点的有限集。(1)有且仅有一个特定的称为根（root）的结点;（2）当n>1时，其余的结点分为m(m≥0)个互不相交的有限集合T1,T2，…，Tm。每个集合本身又是棵树，被称作这个根的子树 。

2.二叉树：是n（n≥0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。

二叉树的性质，存储结构。

性质1: 在二叉树的第i层上至多有2^(i-1)个结点（i>0）。

性质2: 深度为k的二叉树至多有2^k-1个结点（k>0）。

性质3: 对于任何一棵二叉树，如果其终端结点数为n0,度为2的结点数有n2个，则叶子数n0=n2＋1

性质4: 具有n个结点的完全二叉树的深度必为 [log2n]+1

性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）。

二叉树的存储结构：

1).顺序存储结构

按二叉树的结点“自上而下、从左至右”编号，用一组连续的存储单元存储。

若是完全/满二叉树则可以做到唯一复原。

不是完全二叉树：一律转为完全二叉树！

方法很简单，将各层空缺处统统补上“虚结点”，其内容为空。

缺点：①浪费空间；②插入、删除不便 

2).链式存储结构

用二叉链表即可方便表示。一般从根结点开始存储。


			
lchild
			
			

			
data
			
			

			
rchild
			
		
优点：①不浪费空间；②插入、删除方便

3.二叉树的遍历。

指按照某种次序访问二叉树的所有结点，并且每个结点仅访问一次，得到一个线性序列。

遍历规则:二叉树由根、左子树、右子树构成，定义为D、 L、R

若限定先左后右，则有三种实现方案：

  DLR               LDR                   LRD

先序遍历           中序遍历          后序遍历

4.线索二叉树

1）线索二叉树可以加快查找前驱与后继结点，实质就是将二叉链表中的空指针改为指向前驱或后继的线索，线索化就是在遍历中修改空指针。

通常规定：对某一结点，若无左子树，将lchild指向前驱结点；若无右子树，将rchild指向后继结点。

还需要设置左右两个tag，用来标记当前结点是否有子树。

若ltag==1,lchild指向结点前驱；若rtag==1，rchild指向结点后继。

2）线索二叉树的存储结构如下：

typedef struct ThreadNode{

ElemType data;

struct ThreadNode *lchild, *rchild;

int ltag, rtag;

}ThreadNode, *ThreadTree;



5.树和森林

1）树有三种常用存储方式：

①双亲表示法     ②孩子表示法    ③孩子—兄弟表示法

2）森林、树、二叉树的转换

(1)将树转换为二叉树

树中每个结点最多只有一个最左边的孩子(长子)和一个右邻的兄弟。按照这种关系很自然地就能将树转换成相应的二叉树：a.在所有兄弟结点之间加一连线

b.对每个结点，除了保留与其长子的连线外，去掉该结点与其它孩子的连线。



(2)将一个森林转换为二叉树：

具体方法是：a.将森林中的每棵树变为二叉树；

b.因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。



(3)二叉树转换为树

是树转换为二叉树的逆过程。

a.加线。若某结点X的左孩子结点存在，则将这个左孩子的右孩子结点、右孩子的右孩子结点、右孩子的右孩子的右孩子结点，都作为结点X的孩子。将结点X与这些右孩子结点用线连接起来。

b.去线。删除原二叉树中所有结点与其右孩子结点的连线。



 

(4)二叉树转换为森林：

假如一棵二叉树的根节点有右孩子，则这棵二叉树能够转换为森林，否则将转换为一棵树。

a.从根节点开始，若右孩子存在，则把与右孩子结点的连线删除。再查看分离后的二叉树，若其根节点的右孩子存在，则连线删除。直到所有这些根节点与右孩子的连线都删除为止。

b.将每棵分离后的二叉树转换为树。



6.树和森林的遍历


	
树的遍历
	
① 先根遍历：访问根结点；依次先根遍历根结点的每棵子树。

② 后根遍历：依次后根遍历根结点的每棵子树；访问根结点。

 


	
森林的遍历
	
① 先序遍历

若森林为空，返回；

访问森林中第一棵树的根结点；

先根遍历第一棵树的根结点的子树森林；

先根遍历除去第一棵树之后剩余的树构成的森林。

② 中序遍历

若森林为空，返回；

中根遍历森林中第一棵树的根结点的子树森林；

访问第一棵树的根结点；

中根遍历除去第一棵树之后剩余的树构成的森林。

 

7.哈夫曼树及其应用

Huffman树：最优二叉树（带权路径长度最短的树）

Huffman编码：不等长编码。

树的带权路径长度：(树中所有叶子结点的带权路径长度之和)

构造Huffman树的基本思想：权值大的结点用短路径，权值小的结点用长路径。

构造Huffman树的步骤（即Huffman算法）：

(1) 由给定的 n 个权值{ w1, w2, …, wn }构成n棵二叉树的集合F = { T1, T2, …, Tn } （即森林） ，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。

(2) 在F 中选取两棵根结点权值最小的树 做为左右子树构造一棵新的二叉树，且让新二叉树根结点的权值等于其左右子树的根结点权值之和。

(3) 在F 中删去这两棵树，同时将新得到的二叉树加入 F中。

(4) 重复(2) 和(3) , 直到 F 只含一棵树为止。这棵树便是Huffman树。

具体操作步骤：





应用：用于通信编码

　　在通信及数据传输中多采用二进制编码。为了使电文尽可能的缩短，可以对电文中每个字符出现的次数进行统计。设法让出现次数多的字符的二进制码短些，而让那些很少出现的字符的二进制码长一些。假设有一段电文，其中用到 4 个不同字符Ａ，Ｃ，Ｓ，Ｔ，它们在电文中出现的次数分别为 7 ， 2 ， 4 ， 5 。把 7 ， 2 ， 4 ， 5 当做 4 个叶子的权值构造哈夫曼树如图(a) 所示。在树中令所有左分支取编码为 0 ，令所有右分支取编码为1。将从根结点起到某个叶子结点路径上的各左、右分支的编码顺序排列，就得这个叶子结点所代表的字符的二进制编码，如图(b) 所示。这些编码拼成的电文不会混淆，因为每个字符的编码均不是其他编码的前缀，这种编码称做前缀编码。

 

第七章 图

1.图的定义，概念、术语及基本操作(https://blog.csdn.net/eyishion/article/details/53234255)

1）图的定义

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成;

通常表示为:G(V,E),G表示一个图，V是图G中顶点的集合，E是图G中边的集合；

注意：在图中数据元素称之为顶点(Vertex),而且顶点集合有穷非空；在图中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示。

2）图的分类


	
按照有无方向，分为无向图和有向图；
	
无向图：如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。

无向边：若顶点M到顶点N的边没有方向，称这条边为无向边，用无序偶对(M,N)或(N,M)表示。

无向图是有边和顶点构成。如下图所示就是一个无向图G1：



无向图G1= (V1,{E1}),其中顶点集合 V1={A,B,C,D};边集合E1={(A,B),(B,C),(C,D),(D,A)}

有向图：如果图中任意两个顶点之间的边都是有向边，则称该图为有向图。

有向边：若顶点M到顶点N的边有方向，称这条边为有向边，也称为弧，用偶序对 < M, N >表示；M表示弧尾，N表示弧头

有向图是有弧和顶点构成，如下图所示是一个有向图G2：



有向图G2=(V2，{E2}),其中顶点集合 V2={A,B,C,D};弧集合E2={< A,D>,< B,A>,< C,A>,< B,C>}

对于弧< A,D>来说， A是弧尾，D是弧头

注意：无向边用 小括号 “()”表示，有向边用“<>”表示。

无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图。

含有n个顶点的无向完全图有n * (n-1)/2条边。下面是一个无向完全图



4个顶点，6条无向边，每个顶点对应3条边 ，一共4个顶点 总共 4*3，每个顶点对应的边都重复计算了一次，所以整体要除以2。

对于n各 顶点和e条边的无向图满足：0<=e <= n(n-1)/2

有向完全图：在有向图中，如果任意两个顶点之间都存在方向互为相反的两条弧，则称该图为有向完全图。

含有n个顶点的无向完全图有n * (n-1)条边。下面是一个有向完全图



4个顶点，12条弧，一共4个顶点 总共 4*3。

2，按照弧或边的多少，分为稀疏图和稠密图；

若边或弧的个数e<=NlogN(N是顶点的个数)，称为系数图，否则称为稠密图；

3，按照边或弧是否带权，其中带权的图统称为网

有些图的边或弧具有与它相关的数字，这种与图的边或弧相关的数叫做权。

有向网中弧带权的图叫做有向网；

无向网中边带权的图叫做无向网；

比如下图就是一个无向图



 

图的顶点和边间关系

邻接点 度 入度 出度

对于无向图，假若顶点v和顶点w之间存在一条边，则称顶点v和顶点w互为邻接点，边(v,w)和顶点v和w相关联。

顶点v的度是和v相关联的边的数目，记为TD(v);



上面这个无向图G1，A和B互为邻接点，A和D互为邻接点，B和C互为邻接点，C和D互为邻接点;

A的度是2,B的度是2,C的度是2,D的度是2;所有顶点度的和为8，而边的数目是4；

图中边的数目e = 各个顶点度数和的一半。

对于有向图来说，与某个顶点相关联的弧的数目称为度(TD)；以某个顶点v为弧尾的弧的数目定义为顶点v的出度(OD)；以顶点v为弧头的弧的数目定义为顶点的入度(ID)

度(TD) = 出度(OD) + 入度(ID);



比如上面有向图，

A的度为3 ，A的入度 2，A的出度是1

B的度为2 ，B的入度 0，B的出度是2

C的度为2 ，C的入度 1，C的出度是1

D的度为1 ，D的入度 1，D的出度是0

所有顶点的入度和是4，出度和也是4，而这个图有4个弧

所以 有向图的弧 e = 所有顶点入度的和 = 所有顶点出度的和

路径 路径长度 简单路径 回路 (环) 简单回路(简单环)

设图G=(V，{E})中的一个顶点序列{u=Fi0,Fi1,Fi2,….Fim=w}中，(Fi,j-1,Fi,j)∈E 1 ≤j ≤m,则称从顶点u到顶点w之间存在一条路径，路径上边或弧的数目称作路径长度，

若路径中的顶点不重复出现的路径称为简单路径

若路径中第一个顶点到最后一个顶点相同的路径称为回路或环

若路径中第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环

比如下图 ：



从B 到 D 中顶点没有重复出现 ，所以是简单路径 ，边的数目是2，所以路径长度为 2。



图1和图2都是一个回路(环),图1中出了第一个顶点和最后一个顶点相同之外，其余顶点不相同，所以是简单环(简单回路)，图2，有与顶点C重复就不是一个简单环了；

连通图相关术语

连通图

在无向图G(V,{E})中，如果从顶点V到顶点W有路径，则称V和W是连通的。如果对于图中任意两个顶点Vi、Vj∈V,Vi和Vj都是连通的，则称G是连通图。

如下图所示：



图1，顶点A到顶点E就无法连通，所以图1不是连通；图2，图3，图4属于连通图；

连通分量

若无向图为非连通图，则图中各个极大连通子图称作此图的连通分量；

图1是无向非连通图，由两个连通分量，分别是图2和图3。图4尽管也是图1的子图，但是它不满足极大连通，也就说极大连通应当是包含ABCD四个顶点，比如图2那样；

强连通图

在有向图G(V,{E})中，如果对于每一对Vi ,Vj∈V,Vi≠Vj,从Vi到Vj和从Vj到Vi都存在有向路径,则称G是强连通图。



图1不是强连通图因为D到A不存在路径，图2属于强连通图。

强连通分量

若有向图不是强连通图，则图中各个极大强连通子图称作此图的强连通分量；



图1不是强连通图，但是图2是图1的强连通子图，也就是强连通分量；

生成树和生成森林

生成树

假设一个连通图有n个顶点和e条边，其中n-1条边和n个顶点构成一个极小连通子图，称该极小连通子图为此连通图的生成树；



图1是一个连通图含有4个顶点和4条边，图2，图3，图4含有3条边和4个顶点，构成了一个极小连通图子图，也称为生成树，为什么是极小连通子图，因为图2，图3，图4中少一条边都构不成一个连通图，多一条边就变成一个回路(环)，所以是3条边和4个顶点构成的极小连通子图。图5尽管也是3个边4个顶点，但不是连通图。

生成森林

如果一个有向图恰有一个顶点的入度为0，其余顶点的入度为1，则是一颗有向树；

入度为0，相当于根节点，入度为1，相当于分支节点；，比如下面的有向图就是一个有向树



顶点B的入度是0，其余顶点的入度是1；

一个有向图的生成森林由若干颗有向树组成，含有图中全部顶点，但有足以构成若干颗不相交的有向树的弧；



有向图1去掉一些弧后分解成2颗有向树，图2和图3，这两颗树就是有向图图1的生成森林；

2.图的存储结构

1).邻接矩阵(数组)表示法

① 建立一个顶点表和一个邻接矩阵

② 设图 A = (V, E) 有 n 个顶点，则图的邻接矩阵是一个二维数组 A.Edge[n][n]。

注：在有向图的邻接矩阵中，

   第i行含义：以结点vi为尾的弧(即出度边）；

   第i列含义：以结点vi为头的弧(即入度边）。

邻接矩阵法优点：容易实现图的操作，如：求某顶点的度、判断顶点之间是否有边（弧）、找顶点的邻接点等等。

邻接矩阵法缺点：n个顶点需要n*n个单元存储边(弧);空间效率为O(n^2)。



2).邻接表(链式)表示法

① 对每个顶点vi 建立一个单链表，把与vi有关联的边的信息（即度或出度边）链接起来，表中每个结点都设为3个域:



② 每个单链表还应当附设一个头结点（设为2个域），存vi信息；

③ 每个单链表的头结点另外用顺序存储结构存储。

邻接表的优点：空间效率高；容易寻找顶点的邻接点；

邻接表的缺点：判断两顶点间是否有边或弧，需搜索两结点对应的单链表，没有邻接矩阵方便。

3.图的遍历

遍历定义：从已给的连通图中某一顶点出发，沿着一些边，访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。

图的遍历算法求解图的连通性问题、拓扑排序和求关键路径等算法的基础。

图常用的遍历：一、深度优先搜索；二、广度优先搜索 

深度优先搜索（遍历）步骤：(如下图)

① 访问起始点 v;

② 若v的第1个邻接点没访问过，深度遍历此邻接点；

③ 若当前邻接点已访问过，再找v的第2个邻接点重新遍历。

基本思想：——仿树的先序遍历过程。

遍历结果：v1->v2->v4->v8->v5-v3->v6->v7

广度优先搜索（遍历）步骤：

① 在访问了起始点v之后，依次访问 v的邻接点；

② 然后再依次（顺序）访问这些点（下一层）中未被访问过的邻接点；

③ 直到所有顶点都被访问过为止。



遍历结果：v1->v2->v3->v4->v5-v6->v7->v8

4.图的连通性问题

1）对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。

2）最小生成树:在连通网的所有生成树中，所有边的代价和最小的生成树。

构造最小生成树有很多算法，但是他们都是利用了最小生成树的同一种性质：MST性质（假设N=(V,{E})是一个连通网，U是顶点集V的一个非空子集，如果（u，v）是一条具有最小权值的边，其中u属于U，v属于V-U，则必定存在一颗包含边（u，v）的最小生成树），下面就介绍两种使用MST性质生成最小生成树的算法：普里姆算法和克鲁斯卡尔算法。

Kruskal算法特点：将边归并，适于求稀疏网的最小生成树。

Prime算法特点: 将顶点归并，与边数无关，适于稠密网。

Prime算法构造最小生成树过程如下图：



Kruskal算法构造最小生成树过程如下图：



5.有向无环图及其应用

有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边(u,v)∈E(G)，则u在线性序列中出现在v之前。

1）拓扑排序

拓扑排序对应施工的流程图具有特别重要的作用，它可以决定哪些子工程必须要先执行，哪些子工程要在某些工程执行后才可以执行。

我们把顶点表示活动、边表示活动间先后关系的有向图称做顶点活动网(Activity On Vertex network)，简称AOV网。

一个AOV网应该是一个有向无环图，即不应该带有回路，因为若带有回路，则回路上的所有活动都无法进行（对于数据流来说就是死循环）。在AOV网中，若不存在回路，则所有活动可排列成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，我们把此序列叫做拓扑序列(Topological order)，由AOV网构造拓扑序列的过程叫做拓扑排序(Topological sort)。AOV网的拓扑序列不是唯一的，满足上述定义的任一线性序列都称作它的拓扑序列。

拓扑排序的实现：

a.在有向图中选一个没有前驱的顶点并且输出

b.从图中删除该顶点和所有以它为尾的弧（白话就是：删除所有和它有关的边）

c.重复上述两步，直至所有顶点输出，或者当前图中不存在无前驱的顶点为止，后者代表我们的有向图是有环的，因此，也可以通过拓扑排序来判断一个图是否有环。



2）关键路径

AOE-网是一个带权的有向无环图，其中，顶点表示事件，弧表示活动，权表示活动持续的时间。通常，AOE-网可用来估算工程的完成时间。

关键路径：在AOE网中，从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键路径。

关键活动：关键路径上的活动称为关键活动。关键活动：e[i]=l[i]的活动

由于AOE网中的某些活动能够同时进行，故完成整个工程所必须花费的时间应该为始点到终点的最大路径长度。关键路径长度是整个工程所需的最短工期。

与关键活动有关的量：

(1)事件的最早发生时间ve[k]：ve[k]是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从顶点vk发出的活动能够开工的最早时间。 

(2)事件的最迟发生时间vl[k]：vl[k]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。

(3)活动的最早开始时间e[i]:若活动ai是由弧<vk , vj>表示，则活动ai的最早开始时间应等于事件vk的最早发生时间。因此，有：e[i]=ve[k]

(4)活动的最晚开始时间l[i]:活动ai的最晚开始时间是指，在不推迟整个工期的前提下， ai必须开始的最晚时间。若ai由弧<vk，vj>表示，则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后。因此，有：l[i]=vl[j]-len<vk,vj> 

示例如下：





6.最短路径

从某顶点出发，沿图的边到达另一顶点所经过的路径中，各边上权值之和最小的一条路径叫做最短路径。

1）迪杰斯塔拉算法--单源最短路径



 



所有顶点间的最短路径—用Floyd（弗洛伊德）算法

第八章：查找

查找表是称为集合的数据结构。是元素间约束力最差的数据结构：元素间的关系是元素仅共在同一个集合中。（同一类型的数据元素构成的集合）

1.静态查找表

  1）顺序查找（线性查找）

  技巧：把待查关键字key存入表头或表尾（俗称“哨兵”），这样可以加快执行速度。

int Search_Seq( SSTable  ST , KeyType  key ){

ST.elem[0].key =key;

for( i=ST.length; ST.elem[ i ].key!=key;  - - i  );

      return i;

} // Search_Seq

//ASL＝（1＋n）/2，时间效率为 O(n)，这是查找成功的情况:

顺序查找的特点：

优点：算法简单，且对顺序结构或链表结构均适用。

       缺点： ASL 太大，时间效率太低。

  2）折半查找(二分查找)——只适用于有序表，且限于顺序存储结构。

  若关键字不在表中，怎样得知并及时停止查找？

  典型标志是：当查找范围的上界≤下界时停止查找。

  ASL的含义是“平均每个数据的查找时间”，而前式是n个数据查找时间的总和，所以：

 

3）分块查找（索引顺序查找）

思路：先让数据分块有序，即分成若干子表，要求每个子表中的数据元素值都比后一块中的数值小（但子表内部未必有序）。然后将各子表中的最大关键字构成一个索引表，表中还要包含每个子表的起始地址（即头指针）。

特点：块间有序，块内无序。

查找：块间折半，块内线性

查找步骤分两步进行：

① 对索引表使用折半查找法（因为索引表是有序表）；

② 确定了待查关键字所在的子表后，在子表内采用顺序查找法（因为各子表内部是无序表）；

查找效率ASL分析：



2.动态查找表

1）二叉排序树和平衡二叉树


	
二叉排序树的定义----或是一棵空树；或者是具有如下性质的非空二叉树：
	
 （1）若它的左子树不空，则左子树上所有结点的值均小于根的值；

 （2）若它的右子树不空，则右子树的所有结点的值均大于根的值；

 （3）它的左右子树也分别为二叉排序树。

二叉排序树又称二叉查找树。

二叉排序树的查找过程：

BiTree SearchBST(BiTree T, KeyType key)

{

        //在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，

        //若查找成功，则返回指向该数据元素结点的指针，否则返回空指针

        if ((!T)||EQ(key, T->data.key))  return(T); //查找结束

        else if LT(key, T->data.key) return (SearchBST(T->lchild, key)); //在左子树中继续查找

        else return (SearchBST(T->rchild,key)); //在右子树中继续查找

}


	
二叉排序树的插入
	
        思路：查找不成功，生成一个新结点s，插入到二叉排序树中；查找成功则返回。

   SearchBST (K,  &t) { //K为待查关键字，t为根结点指针

   p=t;       //p为查找过程中进行扫描的指针

   while（p!=NULL）

{

   case {

               K= p->data:  {查找成功，return true;}

               K< p->data :  {q=p；p=p->lchild }  //继续向左搜索

               K> p->data :  {q=p；p=p->rchild } //继续向右搜索

            }

  }  //查找不成功则插入到二叉排序树中

s =(BiTree)malloc(sizeof(BiTNode)); 

s->data=K; s ->lchild=NULL; s ->rchild=NULL;

      //查找不成功，生成一个新结点s，插入到二叉排序树叶子处

case {

            t=NULL：   t=s;   //若t为空，则插入的结点s作为根结点

            K < q->data: q->lchild=s;  //若K比叶子小，挂左边

            K > q->data: q->rchild=s; //若K比叶子大，挂右边

        }

return OK;

}


	
二叉排序树的删除
	
假设：*p表示被删结点的指针； PL和PR 分别表示*P的左、右孩子指针；

*f表示*p的双亲结点指针；并假定*p是*f的左孩子；则可能有三种情况：



*p有两颗子树，有两种解决方法：

法1：令*p的左子树为 *f的左子树，*p的右子树接为*s的右子树；如下图(c)所示  //即 fL=PL  ;   SR=PR   ;

法2：直接令*p的直接前驱(或直接后继)替代*p，然后再从二叉排序树中删去它的直接前驱(或直接后继) 。如图(d),当以直接前驱*s替代*p时，由于*s只有左子树SL,则在删去*s之后，只要令SL为*s的双亲*q的右子树即可。 // *s为*p左子树最右下方的结点



删除算法如下：

Status Delete(BiTree &p)

{

    //从二叉排序树种删除结点p，并重接它的左或右子树

    if(!p->rchild) //右子树空，只需重接它的左子树

    {

        q=p;

        p=p->lchild;

        free(q);

    }

    else if(!p->lchild) //左子树空，只需重接它的右子树

    {

        q=p;

        p=p->rchild;

        free(q);

    }

    else //左右子树都不空

    {

        q=p; 

        s=p->lchild;

        while(s->rchild)  //转左，然后向右到尽头(找p的直接前驱) 图(b)

        {

            q=s;

            s=s->rchild;

        }

        p->data = s->data; //s指向被删结点的“前驱”

        if(q!=p)  //重接*q的右子树

        {

            q->rchild=s->lchild;

        }

        else  //q=p,说明s->rchild为空(即：p->lchild->rchild为空)，重接*q的左子树

        {

            q->lchild=s->lchild;

        }

         delete s;

    }//end else 左右子树都不空

    return TRUE;

}

二叉排序树查找分析：和折半查找类似，与给定值比较的关键字个数不超过树的深度。然而，折半查找长度为n的表的判定树是惟一的，而含有n个结点的二叉排序树却不惟一。

含有n个结点的二叉排序树的平均查找长度和树的形态有关。当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树。树的深度为n，其平均查找长度为(n+1)/2(和顺序查找相同)，这是最差的情况。最好的情况是二叉排序树的形态和折半查找的判定树相同，其平均查找长度和log2n成正比。

(n>=2)

 


	
平衡二叉树
	
又称AVL树，即它或者是一颗空树，或者具有如下性质：它的左子树和右子树都是平衡二叉树，且左子树与右子树的深度之差的绝对值不超过1。

平衡因子：该结点的左子树的深度减去它的右子树的深度。

平衡二叉树的特点：任一结点的平衡因子只能取：-1、0 或 1。

如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。

平衡旋转可以归纳为四类：单向右顺时针旋转(LL)；单向左逆时针旋转(RR)；双向旋转先左逆时针后右顺时针(LR)；双向旋转先右顺时针后左逆时针(RL)





平衡二叉树查找分析：

时间复杂度为O(logn)

3.B-树和B+树

B+树是应文件系统所需而出的一种B树的变型树。一棵m阶的B+树和m阶的B-树的差异在于：

1.有n棵子树的结点中含有n个关键字，每个关键字不保存数据，只用来索引，所有数据都保存在叶子节点。

2.所有的叶子结点中包含了全部关键字的信息，及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接。

3.所有的非终端结点可以看成是索引部分，结点中仅含其子树（根结点）中的最大（或最小）关键字。

通常在B+树上有两个头指针，一个指向根结点，一个指向关键字最小的叶子结点。

B-树：一棵m阶的B-树或者是一棵空树，或者是满足下列要求的m叉树：


	
树中的每个结点至多有m棵子树；
	
	

	
若根结点不是叶子结点，则至少有两棵子树；
	
	

	
除根结点外，所有非终端结点至少有[ m/2 ] ( 向上取整 )棵子树。
	
	

	
所有的非终端结点中包括如下信息的数据（n,A0,K1,A1,K2,A2,….,Kn,An）
	
其中：Ki（i=1,2,…,n）为关键码，且Ki < K(i+1)，

Ai 为指向子树根结点的指针(i=0,1,…,n)，且指针A(i-1) 所指子树中所有结点的关键码均小于Ki (i=1,2,…,n)，An 所指子树中所有结点的关键码均大于Kn。n 为关键码的个数。


	
所有的叶子结点都出现在同一层次上，并且不带信息（可以看作是外部结点或查找失败的结点，实际上这些结点不存在，指向这些结点的指针为空）。
	
 

4.哈希表

哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

 

1）哈希函数构造方法


	
直接定址法
	
取关键字或关键字的某个线性函数值为散列地址。

即 H(key) = key 或 H(key) = a*key + b，其中a和b为常数。


	
除留余数法
	
取关键字被某个不大于散列表长度 m 的数 p 求余，得到的作为散列地址。

即 H(key) = key % p, p < m。


	
数字分析法
	
当关键字的位数大于地址的位数，对关键字的各位分布进行分析，选出分布均匀的任意几位作为散列地址。

仅适用于所有关键字都已知的情况下，根据实际应用确定要选取的部分，尽量避免发生冲突。


	
平方取中法
	
先计算出关键字值的平方，然后取平方值中间几位作为散列地址。

随机分布的关键字，得到的散列地址也是随机分布的。


	
折叠法（叠加法）
	
将关键字分为位数相同的几部分，然后取这几部分的叠加和（舍去进位）作为散列地址。

用于关键字位数较多，并且关键字中每一位上数字分布大致均匀。


	
随机数法
	
选择一个随机函数，把关键字的随机函数值作为它的哈希值。

通常当关键字的长度不等时用这种方法。

构造哈希函数的方法很多，实际工作中要根据不同的情况选择合适的方法，总的原则是尽可能少的产生冲突。

通常考虑的因素有关键字的长度和分布情况、哈希值的范围等。

如：当关键字是整数类型时就可以用除留余数法；如果关键字是小数类型，选择随机数法会比较好。

 

2）哈希冲突的解决方法

 


	
开放定址法
	
Hi=(H(key) + di) MOD m i=1,2,…,k (k<=m)

当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。

当冲突发生时，使用某种探查(亦称探测)技术在散列表中寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到。

按照形成探查序列的方法不同，可将开放定址法区分为线性探查法、二次探查法、双重散列法等。

a.线性探查法

hi=(h(key)+i) ％ m ，0 ≤ i ≤ m-1

基本思想是：探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1]，…，直到 T[m-1]，此后又循环到 T[0]，T[1]，…，直到探查到 有空余地址 或者到 T[d-1]为止。

b.二次探查法

hi=(h(key)+i*i) ％ m，0 ≤ i ≤ m-1

基本思想是：探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+1^2]，T[d+2^2]，T[d+3^2],…，等，直到探查到 有空余地址 或者到 T[d-1]为止。缺点是无法探查到整个散列空间。

c.双重散列法

hi=(h(key)+i*h1(key)) ％ m，0 ≤ i ≤ m-1

基本思想是：探查时从地址 d 开始，首先探查 T[d]，然后依次探查 T[d+h1(d)], T[d + 2*h1(d)]，…，等。

该方法使用了两个散列函数 h(key) 和 h1(key)，故也称为双散列函数探查法。

定义 h1(key) 的方法较多，但无论采用什么方法定义，都必须使 h1(key) 的值和 m 互素，才能使发生冲突的同义词地址均匀地分布在整个表中，否则可能造成同义词地址的循环计算。

该方法是开放定址法中最好的方法之一。


	
链接法（拉链法）
	
将所有关键字为同义词的结点链接在同一个单链表中。若选定的散列表长度为 m，则可将散列表定义为一个由 m 个头指针组成的指针数组 T[0..m-1] 。

凡是散列地址为 i 的结点，均插入到以 T[i] 为头指针的单链表中。

T 中各分量的初值均应为空指针。

在拉链法中，装填因子 α 可以大于 1，但一般均取 α ≤ 1。



3.哈希表的查找及其分析

哈希表是实现关联数组（associative array）的一种数据结构，广泛应用于实现数据的快速查找。

查找过程中，关键字的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。

影响产生冲突多少有以下三个因素：

1）哈希函数是否均匀；

2）处理冲突的方法；

3）哈希表的加载因子。

 

第九章：内部排序

排序:将一个数据元素(或记录)的任意序列，重新排列成一个按关键字有序的序列。

稳定性——若两个记录A和B的关键字值相等，且排序后A、B的先后次序保持不变，则称这种排序算法是稳定的。

1.插入排序

思想：每步将一个待排序的对象，按其关键码大小，插入到前面已经排好序的一组对象的适当位置上，直到对象全部插入为止。

简言之，边插入边排序，保证子序列中随时都是排好序的。

1)  直接插入排序

    在已形成的有序表中线性查找，并在适当位置插入，把原来位置上的元素向后顺移。



时间效率： 因为在最坏情况下，所有元素的比较次数总和为（0＋1＋…＋n-1)→O(n^2)。

其他情况下也要考虑移动元素的次数。 故时间复杂度为O(n^2)

空间效率：仅占用1个缓冲单元——O（1）

算法的稳定性：稳定

直接插入排序算法的实现：

void InsertSort ( SqList &L ) 

{ //对顺序表L作直接插入排序

 for ( i = 2;  i <=L.length; i++) //假定第一个记录有序

{

     L.r[0]= L.r[i];

       j=i-1 ;                      //先将待插入的元素放入“哨兵”位置

     while（L[0] .key<L[j].key)

    {  

        L.r[j+1]= L.r[j];

        j--  ;                    

    }      //只要子表元素比哨兵大就不断后移

    L.r[j+1]= L.r[0];      //直到子表元素小于哨兵，将哨兵值送入

                                 //当前要插入的位置（包括插入到表首）

}

}

2)折半插入排序

子表有序且为顺序存储结构，则插入时采用折半查找定可加速。

优点：比较次数大大减少，全部元素比较次数仅为O(nlog2n)。

时间效率：虽然比较次数大大减少，可惜移动次数并未减少， 所以排序效率仍为O(n^2) 。

空间效率：仍为 O(1)

稳 定  性： 稳定

 

3)希尔排序—不稳定

基本思想：先将整个待排记录序列分割成若干子序列,分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。

优点：让关键字值小的元素能很快前移，且序列若基本有序时，再用直接插入排序处理，时间效率会高很多。

时间效率：当n在某个特定范围内，希尔排序所需的比较和移动次数约为n^1.3,当n->无穷，可减少到n(log2n)^2

空间效率：O(1)



4)快速排序

基本思想：从待排序列中任取一个元素 (例如取第一个) 作为中心，所有比它小的元素一律前放，所有比它大的元素一律后放，形成左右两个子表；然后再对各子表重新选择中心元素并依此规则调整，直到每个子表的元素只剩一个。此时便为有序序列了。

优点：因为每趟可以确定不止一个元素的位置，而且呈指数增加，所以特别快！

前提：顺序存储结构



时间效率：O(nlog2n) —因为每趟确定的元素呈指数增加

空间效率：O（log2n）—因为递归要用栈(存每层low，high和pivot)

稳 定 性： 不 稳 定 — —因为有跳跃式交换。

算法：

int partition(SqList &L,int low,int high)

{

  L.r[0] = L.r[low];

  pivot key = L.r[low].key;

    while(low < high)

    {

     while(low<high&&L.r[high]>=pivot) high--;

     L.r[low] = L.r[high];

     while(low<high&&L.r[low]<=pivot) low++;

     L.r[high] = L.r[low];

    }

    L.r[low] = pivot;

    return low;

}

 

5)冒泡排序

基本思路：每趟不断将记录两两比较，并按“前小后大”（或“前大后小”）规则交换。

优点：每趟结束时，不仅能挤出一个最大值到最后面位置，还能同时部分理顺其他元素；一旦下趟没有交换发生，还可以提前结束排序。

前提：顺序存储结构



冒泡排序的算法分析：

时间效率：O（n^2) —因为要考虑最坏情况

空间效率：O（1） —只在交换时用到一个缓冲单元

稳 定 性： 稳定  —25和25*在排序前后的次序未改变

冒泡排序的优点：每一趟整理元素时，不仅可以完全确定一个元素的位置（挤出一个泡到表尾），还可以对前面的元素作一些整理，所以比一般的排序要快。

选择排序：选择排序的基本思想是：每一趟在后面n-i 个待排记录中选取关键字最小的记录作为有序序列中的第i  个记录。

6)简单选择排序

思路异常简单：每经过一趟比较就找出一个最小值，与待排序列最前面的位置互换即可。

——首先，在n个记录中选择最小者放到r[1]位置；然后，从剩余的n-1个记录中选择最小者放到r[2]位置；…如此进行下去，直到全部有序为止。

优点：实现简单

缺点：每趟只能确定一个元素，表长为n时需要n-1趟

前提：顺序存储结构



时间效率：O(n^2)——虽移动次数较少，但比较次数较多

空间效率：O(1)

算法稳定性——不稳定

Void SelectSort(SqList  &L ) 

{

for (i=1;  i<L.length; ++i)

{

     j = SelectMinKey(L,i);  //在L.r[i..L.length]中选择key最小的记录

     if( i!=j )   r[i] <--> r[j]; //与第i个记录交换

      } //for

  }  //SelectSort

 

7）堆排序

设有n个元素的序列 k1，k2，…，kn，当且仅当满足下述关系之一时，称之为堆。



如果让满足以上条件的元素序列 （k1，k2，…，kn）顺次排成一棵完全二叉树，则此树的特点是：树中所有结点的值均大于（或小于）其左右孩子，此树的根结点（即堆顶）必最大（或最小）。

堆排序算法分析：

时间效率：O(nlog2n)。因为整个排序过程中需要调用n-1次HeapAdjust( )算法，而算法本身耗时为log2n；

空间效率：O(1)。仅在第二个for循环中交换记录时用到一个临时变量temp。

稳定性： 不稳定。

优点：对小文件效果不明显，但对大文件有效。

 

8）归并排序----稳定

将两个或两个以上有序表组合成一个新的有序表。

时间复杂度：O(nlogn)

空间复杂度：和待排记录等数量的辅助空间。

 

9）基数排序

时间复杂度：对于n各记录（每个记录含d个关键字，每个关键字取值范围为rd个值）进行链式基数排序的时间复杂度为O(d(n+rd)),其中每一趟分配的时间复杂度为O(n),每一趟收集的时间复杂度为O(rd)

10）各种内部排序方法的比较讨论



(1) 从平均时间性能看，快速排序最佳，其所需时间最省，但快速排序的最坏情况下的时间性能不如堆排序和快速排序。后两者相比较，在n较大时，归并排序所需时间较堆排序省，但它所需的辅助存储量最多。

(2)基数排序的时间复杂度可写成O(dn)。因此，它最适用于n值很大而关键字较小的序列。

(3)从方法的稳定性来比较，基数排序是稳定的内排方法，所需时间复杂度为O(n^2)的简单排序方法也是稳定的，然而，快速排序、堆排序和希尔排序等时间性能较好的排序方法是不稳定的。

明天就要考试了，来一波知识点整理。都会了，期末考试你不过你来找我！
第一章
1.按微处理器的字节分类
 4 位微处理器
 8 位微处理器
 16位微处理器 
 32位微处理器

2.这个必须背，不是简答就是简答，肯定出简答


3.系统软件
给一个实例判断是否是系统软件！
常见的系统软件：
操作系统、程序语言设计、语言处理程序、数据库管理程序、系统辅助处理程序

第二章
1.微处理器的性能指标
a.字长 CPU能同时处理的数据位数 
b.主频 CPU的时钟频率，主频越高，运算速度越快

2.8086的编程结构(掌握)这个必须背，简答题必出
从功能上8086分为两部分，总线接口部分(BIU) 和 执行部件(EU)
a.	总线接口部件
	a)	4个16位的段地址寄存器
		i.	CS 代码段地址寄存器
		ii.	DS 数据段地址寄存器
		iii.	ES 附加段地址寄存器
		iv.	SS 堆栈段地址寄存器
	b)	16位的指令指针寄存器 IP
	c)	20位的地址加法器
	d)	6字节的指令队列缓冲器
b.	执行部件
	a)	4个通用寄存器 AX、BX、CX、DX
	b)	4个专用寄存器
		i.	基数指针寄存器 BP
		ii.	堆栈指针寄存器 SP
		iii.	源变址寄存器 SI
		iv.	目的变址寄存器 DI
	c)	标志寄存器 FR
	d)	算数逻辑部件ALU (算术运算和逻辑运算)

3.8086的标志寄存器共16位，7位未用，，，知道什么时候表示什么意义即可
a.	状态标识6个
	a)	符号标志 SF
	b)	零标志 ZF
	c)	奇偶标志 PF
	d)	进位标志 CF
	e)	辅助进位标志 AF
	f)	溢出标志 OF
b.	控制标志3个
	a)	方向标志 DF
	b)	中断允许标志 IF
	c)	跟踪标志 TF 
有符号有意义：ZF  SF  PF  OF
无符号有意义：PF  ZF  CF  AF

4.8086的总线周期–填空啦选择啦
由4个时钟周期组成，时钟周期是CPU最基本的时间计量单位
4个时钟周期称为4个状态：T1、T2、T3、T4
Tw放在T3和T4之间

5.8086的最小模式典型配型  （掌握数量、名称、芯片型号、功能）(掌握)这个你不背，老师都不放过你，简答题必出不是最大就是最小
a.有1片8284A，作为时钟发生器，提供时钟信号和同步ready信号和reset信号
b.有3片8282或74LS273，用来作为地址锁存器，暂存地址
c.有2片8286/8287，作为总线收发器，增加数据总线的驱动能力
d.有1片8086，作为微处理器，负责CPU对存储器和IO端口的数据传输以及指令的执行

6.8086的最大模式典型配置(掌握)要求同最小模式
a.	有两个或多个8086，作为微处理器，功能同最小模式
b.	有1片8284A，作为时钟发生器，功能同最小模式
c.	有3片8282或74Ls273，用来做地址锁存器，功能同最小模式
d.	有2片8286/8287，作为总线收发器，功能同最小模式
e.	有1片8288，作为总线控制器，控制总线是否让出
f.	有1片8259A，作为中断控制器，控制是否处理中断

7.中断–填空啦选择啦
a.	中断分类：
	a)	硬件中断/外部中断
		i.	非屏蔽中断 – 引脚NMI
		ii.	可屏蔽中断 – 引脚INIR
	b)	软件中断/内部中断
b.	中断向量和中断向量表
	a)	中断向量表中最多容纳256个中断向量
	b)	一个中断向量占4个存储单元
	c)	查向量表时，中断类型号*4为起始地址，连续4个存储单元

8.中断响应过程 填空选择
INAT引脚两次有效，第一次有效为中断请求信号，第二次有效为发送中断类型号

9.存储器 主要填空题,掌握编址方法
a.	物理地址 = 段地址 * 16 + 逻辑地址
b.	I/O编址的两种方法： 
	a)	存储器映像
	b)	I/O端口独立编址

第三章
1.Pentium的寻址方式(掌握)一定出填空，给你指令问什么方式，看清题目描述就好
a.	立即数寻址
	a)	立即数只能作为源操作数，不能作为目的操作数
b.	寄存器寻址
c.	输入/输出端口寻址
	a)	I/O直接寻址
	b)	I/O间接寻址
d.	存储器寻址
	有效地址EA = 基址 + 变址 * 比例因子 + 位移量
	a)	直接寻址                          MOV AX , [1070H]
	b)	寄存器间接寻址                    MOV AX , [BX]
	c)	寄存器相对寻址                    MOV AX , [SI + 100]
	d)	基址加变址的寻址                  MOV AX , [BX + SI]
	e)	相对的基址加变址寻址              MOV AX , [BP + SI + 100]
	f)	相对的带比例因子的变址寻址        IMUL EBX , [ESI * 4 + 7]
	g)	基址加比例因子的变址寻址          MOV EAX , [EBX][ESI * 4]
	h)	相对的基址加比例因子的变址寻址    MOV EAX , [EDI * 4][EBP + 80]

2.指令的注意事项 MOV—判断题一定出
a)	不能在两个内存单元之间传送数据
b)	不能从一个段地址寄存器向另一个段地址寄存器发送数据
c)	CS、IP、EIP寄存器不能作为目的操作数

第四章
1.随机存取存储器RAM
a.	SRAM 
	a)	触发器构成
b.	DRAM
	a)	电容构成

2.只读存储器 ROM—可能会出简答题吧
a.	掩膜型ROM
b.	可编程只读存储器PROM
c.	可擦除、可编程只读存储器EPROM
d.	可用电擦除的可编程只读存储器E2PROM
e.	闪烁存储器

3.存储器片选信号的产生方法，，简单题常客，优点缺点，原理特点
a.	线选法
	a)	电路简单
	b)	直接用地址线做为片选信号，每条地址选一个芯片
	c)	用于容量小、存储芯片也少的小系统中
	d)	整个存储器的地址不连续，空间浪费大
	e)	同一单元可对应不同的地址
b.	全译码法
	a)	存储单元是唯一的，不会出现地址重叠
	b)	只要选择的好，可以保证地址的连续
	c)	电路复杂
c.	部分译码法
	a)	简化译码电路，容易实现
	b)	会有地址重叠的问题，浪费空间
	c)	如果组织的好，也可以保证地址的连续性
d.	混合译码法
	a)	因为包括了线选法，所以也有地址不连续和地址重叠的问题

4.存储器的容量扩充方法----填空题
a.	数据宽度的扩充
b.	字节的扩充

5.内存按照字访问—判断啦选择啦填空啦
a.	对准状态
	a)	要求起始地址为偶数地址
b.	非对准状态
	a)	由于提供的对字访问的地址为奇地址造成的

6.Cache的组织方式 (特点、大体原理) (掌握)–简答题一般会出
a.	全相联方式
	a)	主存的一个区块可能映像到Cache的任何一个地方
b.	直接映像方式
	a)	主存的一个区块只能映像到Cache的一个对应的地方
c.	组相连方式
	a)	将Cache分为均等容量的几路，每一路包含许多组，各路中，组的数量和编号相同，每一组又包含1个或多个区块。
	b)	主存的一个区块只能映像到Cache的指定组号和指定块号的区块，但可以映像到不同路中的相应区块

第五章
1.接口按照功能分类
a.	使CPU正常工作所需要的辅助电路
b.	输入/输出接口

2.CPU和输入/输出设备之间的信号–记住它，填空选择一定有啊
a.	数据信息
b.	状态信息
c.	控制信息

3.I/O端口
定义：CPU和外设进行数据传输时，各类信息在接口中进入不同的寄存器
编址方式：与存储器统一编址方式和I/O端口独立编址方式

4.CPU和外设之间的数据传送方式 (原理 、 特点) (掌握)一定考，有点迷，没整理好
a.	程序方式 
	a)	条件传送方式
	b)	无条件传送方式
b.	中断方式
c.	DMA方式
	a)	特点
	i.	是一个接口电路 
	ii.	能够控制系统总线
	iii.	操纵外设和存储器之间的数据传输

第六章
1.串行通信的方式
a.	根据方向划分
	a)	半双工方式
	b)	单工方式
	c)	全双工方式
b.	根据数据格式划分
	a)	同步方式  （同步字符  最多两个）  通信双方要求同一个时钟信号
	b)	异步方式  （一个起始位，停止位（1 , 1.5 , 2），奇偶校验位） 

2.可编程串行通信接口8251A基本性能
a.	同步方式
	a)	可用5、6、7和8位来代表字符
	b)	能够自动检测同步字符，从而实现同步
	c)	允许同步方式下增加奇偶校验位进行校验
b.	异步方式
	a)	也可用5、6、7和8位来代表字符
	b)	用1位做奇偶校验位
	c)	在异步方式下自动为每个数据增加一个启动位，并根据编程为每个数据增加1个、1.5个或2个停止位

3.8251A的初始化(掌握)好好看看


4.8251A在异步模式下模式寄存器中的关系，，，填空题啦
时钟频率 = 波特率因子 * 波特率
8251 内部地址  c/d 
TxD   数据发送  
RxD   数据接收

5.可编程并行通信接口8255A，一定考，相信我，100%编程题
a.	内部结构
	a)	3个8位数据端口： 端口A、 端口B、 端口C
	b)	端口C通过控制命令被分为两个4位端口，分别用来给端口A和端口B提供控制信号和状态信号
b.	控制字
	a)	方式选择控制字
	b)	端口你C置1 / 置0控制字
c.	工作方式
	a)	方式0、方式1、方式2
	b)	端口A可工作在三种方式中的任意一种
	c)	端口B只能工作在方式0或方式1
	d)	端口C配合端口A和端口B工作
	e)	只有端口A工作在方式2
d.	应用实例(掌握) (掌握) (掌握)
	a)	作为连接打印机的接口 课本233页
	b)	传输数据

第七章

1.8259A的编程结构(掌握)
a.	控制部分
	a)	4个8位寄存器，存放初始化命令字ICW1-ICW4 
	b)	3个8位寄存器，存放操作命令字OCW1-OCW3  
b.	处理部件
	a)	中断请求寄存器IRR  （保存8个中断信息）
	b)	中断优先级裁决器PR    （比较优先级大小）
	c)	当前中断服务寄存器ISR     （记录）

2.8259A的工作方式，设置优先级的方式(特点、原理) (掌握) (掌握)简答题啊
a.	全嵌套方式
	a)	最常用的工作方式，中断请求按照优先级0~7进行处理，0级最高，7级最低
	b)	中断优先级裁决器将收到的中断请求与当前中断服务寄存器的IS位比较，判断新收到的是否比当前的正在处理的中断的优先级高，如是，则进行中断嵌套
b.	特殊嵌套方式
	a)	与全嵌套方式相比，只有一点差别，当处理某一级中断时，如果有同级中断请求，也会给予响应
c.	优先级自动循环方式
	a)	一般用在系统中的多个中断源优先级相等的场合。
	b)	在这种方式下，优先级队列是变化的，一个设备受到中断服务以后，它的优先级自动降为最低
d.	优先级特殊循环方式
	a)	与优先级自动循环相比，只有一点不同，就是一开始的最低优先级和最高优先级是由编程确定的。

3.几个8259A级联可以控制几个中断–填空题的常客
1个控制 8 个中断
2个控制 8 – 1 + 8 = 15
3个控制 8 – 2 + 8 * 2 = 22
4个控制 8 – 3 + 8 * 3 = 29
X个控制 8 – x + 8 * （x - 1） = ?      x <= 8

####4.8259A的初始化流程(掌握) (掌握)-记住它


初始化说明：
1.ICW1写入偶端口，ICW2～ICW4写入奇端口
2.ICW1～ICW4的设置次序固定  （16位和32位系统中，ICW4必须设置；只有在级联的情况下，设置ICW3）
3.ICW1和ICW2须设置，ICW3和ICW4非必须 
4.在级联时，主片和从片各设置ICW3
5.对于每个8259A，ICW1和ICW2是必须要设置的
ICW3 的设置为中断类型号的高5位，中断类型号的低三位决定了中断请求从哪个引脚进入

第八章
1.DMA控制器初始化
a.	将数据传输缓冲区的起始地址或结束地址送到地址寄存器中
b.	将传输的字节数、字数或双字数送到计数器中

2.8237A的编程结构
通道内最大传输64KB
a.	4个独立的通道，每个通道包含
	1).当前地址寄存器  16位
	2）.基本地址寄存器  16位
	3）.当前字节计数器  16位
	4）.基本字节寄存器  16位
	5）模式寄存器  8 位
b.	4个通道公用控制寄存器和状态寄存器

3.8237A工作时个各信号的配合引脚变化(掌握)一定考，课本261页
a.	作为从模块工作时
b.	作为主模块工作时    地址16位

4.8237A的工作模式
a.	单字节传输模式
b.	块传输模式
c.	请求传输模式
d.	级联传输模式

第九章

1.16位计数器范围
	二进制 最大65536
	BCD码 最大10000

2.8253/5254的工作模式
a.	定时
	a)	模式2	分频器   周期性的脉冲
	b)	模式3	方波发生器
b.	计数
	a)	模式0	计数结束产生中断
	b)	模式1	可编程的单稳态触发器
	c)	模式4	软件触发的选通信号发生器
	d)	模式5	硬件触发的选通信号发生器

3.8253/5254的应用举例	(编程题) (掌握) (掌握) (掌握)第二个必考编程题，加油
第十章
1.D/A转换器  方法 a,b   及特点
a.	由并联电阻和运算放大器构成的DA转换器   每个电阻都不一样
b.	T型权电阻网络和运算放大器   只有R 和2R    （最常见）
c.	DA转换器的指标
	a)	分辨率   反映了D/A转换器的灵敏度，指辨别最小电压增量的能力
	b)	转换精度   绝对转换精度（程度）、相对转换精度（物理量）
	c)	转换速率和建立时间  反应转换速率 
	d)	线性误差    

2.A/D转换器
a.	AD转换涉及的参数
	a)	分辨率     能够分辨最小信号的能力
	b)	转换精度      反映了A/D转换器的实际值接近理想值的精确程度
	c)	转换率         完成一次A/D转换器所需要的时间的倒数
b.	AD转换的方法及特点
	a)	计数式AD转换     简单，速度慢
	b)	双积分式AD转换    抗干扰能力强 ， 速度不算快
	c)	逐次逼近AD转换     速度最快
	d)	用软件和DA转换器来实现AD转换  速度较快

第十一章
1.键盘结构
a.	最简单的键盘结构   --- 引脚连接
b.	键盘的矩阵式结构   ----矩阵连接

2.键的识别
a.	行扫描法
b.	行反转法

第十五章

1.计算机总线的分类及应用  常见的
a.	内部总线   cpu总线
	a)	用来连接片内运算器和寄存器等各大部件
	b)	也叫片内总线
b.	局部总线   PCI  ISA EISA
	a)	连接主机板上的各主要部件
	b)	可以通过扩展插槽连接各种适配器，如 卡，声卡、网卡、图像卡等
c.	系统总线
	a)	连接各CPU插件板和其他总线主模块
	b)	最流行的系统总线是MULTIBUS、STDBUS和VME
d.	外部总线   USB   SCSI   RS-232-C   EIDE 
	a)	微型机与外设之间的通信总线

2.总线的性能指标
a.	宽度	一次可同时传输的数据位数
b.	总线频率	总线工作时每秒钟能传输数据的次数
c.	传输率	总线工作时每秒钟能传输的字节数

文档地址：点击跳转