第1-3章

2025-02-12 20:58:16   0  举报





仅支持查看

AI智能生成

第1章计算机系统知识（5~6分） 1.1 计算机系统基础知识 1.2 计算机体系结构 1.3 安全性、可靠性与系统性能评测基础知识第2章程序设计语言（固定6分） 2.1程序设计语言概述 2.2 语言处理程序基础第3章数据结构（5分） 3.1 线性结构 3.2 数组、矩阵和广义表 3.3 树 3.4 图 3.5 查找 3.6 排序

计算机系统知识

程序设计语言

数据结构

作者其他创作

大纲/内容

第1章计算机系统知识

1.1 计算机系统基础知识

1.1.1 计算机系统硬件基本组成

计算机系统

硬件（计算机的实体部分，由各种电子元器件组成）

运算器

负责算术运算（+ - * / 基本运算和附加运算）和逻辑运算（包括移位、逻辑测试或比较两个值等）

控制器

负责应对所有的信息情况，调度运算器把计算做好

存储器

记忆设备

内部存储器（主存）

速度高、容量小

用于临时存放程序、数据、中间计算结果

外部存储器（辅存）

速度慢、容量大

长期保存程序和数据

输入设备

输入原始数据及各种命令

输出设备

输出计算机运行结果

软件（由具有各类特殊功能的信息（程序）组成，这些程序寄寓于各类媒体（RAM、ROM、磁带、磁盘、光盘等））

分类

系统软件

语言处理程序

操作系统

服务性程序

数据库管理系统

网络软件

应用软件

1.1.2 中央处理单元CPU

CPU功能

程序控制

通过指令控制程序的执行顺序

操作控制

产生操作信号，控制相应部件按指令功能要求操作

时间控制

控制操作信号的出现、持续时间及出现的时间顺序

数据处理

算数、逻辑运算

对系统内外部中断（异常）做出响应

运算器

算数逻辑单元（ALU，Arithmetic and Logic Unit）

数据处理，算数、逻辑运算

累加寄存器（AC，Accumulator）

为ALU提供工作区，至少有一个

数据缓冲寄存器（DR，Data Register）

作为CPU、内存和外部设备之间数据传输的中转站

状态条件寄存器（PSW，Program Status Word），程序状态字

保存各种状态条件标志

控制器

指令寄存器（IR，Instruction Register）

用于暂存当前正在执行的一条指令

指令译码器（ID，Instruction Decoder）

操作码

地址码

程序计数器（PC，Program Counter）、指令计数器

寄存和计数，存放下一条指令的地址，自动加1

地址寄存器（AR，Address Register）

保存当前所访问内存单元的地址

时序产生器（Timing Generator）

类似于“时间作息表”，给计算机各部分提供工作所需的时间标志，利用定时脉冲的顺序和不同的脉冲间隔实现

操作控制器（Control Unit）

根据指令所需完成的操作和信号，发出各种微操作命令序列，用以控制所有被控对象，完成指令的执行

寄存器组

专用寄存器

通用寄存器

内部总线

多核CPU

多CPU(在计算机主板上有多个物理CPU，每一个物理CPU之间通过系统总线连接)

Architectual State: 架构状态，包括通用数据寄存器、段寄存器、控制寄存器等

Execution Engine: 执行引擎，用来执行CPU指令，包括算数逻辑单元ALU等

Local APIC: 局部高级可编程中断控制器，用来处理CPU中断

Bus Interface:总线接口

多核CPU（在一个物理CPU内部，封装了多个物理核心。这些物理核心可能位于同一个Die（晶元）上（AMD，多核），也可能位于多个Die上（Intel，多芯））

每一个物理核心都有自己的Architectual State、Execution Engine、Local APIC，每一个物理核心都可以看成是一个逻辑 CPU

多核CPU内部物理核心之间通过片内总线通信，速度会快于系统总线

可同时进行多任务处理

超线程技术（逻辑核心共享Execution Engine，同一时刻，只能执行1条指令流上的指令）

作用于物理CPU内部的物理核心上，可以提升CPU核心的利用率

1.1.3 数据表示

机器数（定义：连同符号位一起数字化的数）

特点

符号数字化

数值的大小受机器字长的限制，每个机器数所占的二进制位数受限于机器硬件规模，与机器字长有关，超过机器字长的数位要被舍去

真值

机器数中除“+”“-”符号外，其余部分表示的值

分类

最高位表示正、负的符号位，符号位“1”表示“-”，“0”表示“+”，其余位表示数值

无符号数（机器字长的所有二进制位均表示数值）

正数

约定小数点的位置在最低位之后，纯整数

约定小数点的位置在最高位之前，纯小数

码制

原码（保持原有的数值部分的形式不变）

反码

补码

移码

定点数、浮点数

定点数（小数点位置固定不变的数）

定点整数

纯整数，小数点在最低有效数值位之后（例如整数100，小数点其实在最后一位，所以忽略不写）

原码/反码

取值范围

当机器字长n=4时，能表示的带符号的数的范围是-7~+7,即-(2^3-1)~2^3-1

最大的数：+111=1*2^2+1*2^1+1*2^0=4+2+1=7=2^3-1=2^(4-1)-1

最小的数：-111=-(1*2^2+1*2^1+1*2^0)=-(4+2+1)=-7=-(2^3-1)=-(2^(4-1)-1)

当机器字长为n时，能表示的带符号的数的范围是-(2^(n-1)-1)~2^(n-1)-1

数码个数

当机器字长n=4时，能表示的带符号的数有15个(-7到+7之间总的有15个数，15=16-1=2^4-1)

当机器字长为n时，能表示的带符号的数有2^n-1个

补码/移码（人为规定-8的补码是1000）

取值范围

当机器字长n=4时，能表示的带符号的数的范围是-8~+7即-(2^3)~2^3-1

当机器字长为n时，能表示的带符号的数的范围是-(2^(n-1))~2^(n-1)-1

数码个数

当机器字长n=4时，能表示的带符号的数有16个

当机器字长为n时，能表示的带符号的数有2^n个

补码相对于原码和反码还能表示一个更小的数(-8)

定点小数

纯小数，小数点在最高有效数值位之前（例如：0.123，小数点固定在最高位）

原码/反码

取值范围

当机器字长n=4时，能表示的带符号的定点小数的范围是-(1-2^(-3))~1-2^(-3))

最大的数：符号位为+，后3位为111，即0.111
0.111(B)+0.001(B)=1(B)（这里的1是二进制）
0.111(B) = 1(B)-0.001(B)
0.111(B) = 2^0-2^(-3)=1-2^(-3)

最小的数：符号位为-，后3位为111，即-0.111

当机器字长n=4时，能表示的带符号的定点小数的范围是-(1-2^(-(n-1)))~1-2^(-(n-1)))

数码个数

当机器字长n=4时，能表示的带符号的数有15个

当机器字长为n时，能表示的带符号的数有2^n-1个

补码/移码（人为规定-1的补码是1000）

取值范围

当机器字长n=4时，能表示的带符号的定点小数的范围是-1~1-2^(-3)

当机器字长为n时，能表示的带符号的数的范围是-1~1-2^(-(n-1))

数码个数

当机器字长n=4时，能表示的带符号的数有16个

当机器字长为n时，能表示的带符号的数有2^n个

补码相对于原码和反码还能表示一个更小的数(-1)

浮点数（小数点位置不固定的数，表示更大范围的数）

浮点数表示法

阶码为带符号的纯整数（数值范围），尾数为带符号的纯小数（精度）

一个二进制数N可以表示为N=2^E*F,E称为阶码，F称为尾数

浮点数相加

相同阶

不同阶

规格化浮点数

浮点数所能表示的数值范围主要由阶码决定，所表示数值的精度则由尾数决定。为充分利用尾数来表示更多的有效数字，通常采用规格化浮点数，将尾数的绝对值限定在区间[0.5,1]

浮点数表示数值范围

浮点数的阶码（包括 1 位阶符）用R位的移码表示，尾数（包括1位数符）用M位的补码表示

工业标准IEEE754

1.1.4 校验码

概述

码距

码距=2,有检错能力

码距≥3,可能有纠错能力

一个校验码要想能够检错和纠错那么它的码距至少是3

分类

奇偶校验码（码距为2，有检错能力,没纠错能力。常用的奇偶校验码有3种:水平奇偶校验码、垂直奇偶校验码和水平垂直校验码）

奇校验

发送方

增加一位校验码，使得编码中的1的个数为奇数

接收方

验证编码中1的个数是否为奇数

偶校验

发送方

增加一位校验码，使得编码中的1的个数为偶数

接收方

验证编码中1的个数是否为偶数

海明码（利用多组数位的奇偶性来检错和纠错，可以检错和纠错，码距为3）

数据位n位，校验位k位，2^k-1≥n+k

循环冗余码(k个数据位[n,r+1]后跟r个校验位[r,1] ,可以检错但不能纠错,码距为2 ,采用模2运算得到校验码)

利用生成多项式为k个数据位产生r个校验位来进行编码，其编码长度为k+r

1.1.5 进制转化

4种进制形式

二进制

二进制是Binary，简写为B

由0和1两个数字组成，开头都是以0B开始

十进制

十进制是Decimal，简写为D

都是以0-9这九个数字组成，不能以0开头

八进制

八进制是Octal，简写为O

由0-7数字组成，为了区分与其他进制的数字区别，开头都是以0开始

十六进制

十六进制为Hexadecimal，简写为H

由0-9和A，B，C，D，E，F分别表示数字10～15组成。为了区分于其他数字的区别，开头都是以0x开始

计数到F后，再增加1个，就进位

整数转换

十进制转R进制

十进制转二进制的原理：十进制数除以2，余数为权位上的数，得到商继续除以2，直到商为0终止，然后反向取余数

例如(67)10 → (1000011)2
将67除以2得商33，余数1；将商（33）作为第二次的被除数一次类推，直到商为0

十进制转八进制的原理：跟十转二原理一样，十进制数除以8，余数为权位上的数，得到商继续除以8，直到商为0终止，然后反向取余数

例如758（十进制）→ 1366（八进制）

十进制转十六进制的原理：跟十转二原理一样，十进制数除以16，余数为权位上的数，得到商继续除以16，直到商为0终止，然后反向取余数

例如951（十进制）→ 3B7（十六进制）

R进制转十进制

（把R进制数按权展开、相加即得十进制数）

二进制转八进制、十六进制

3位二进制数按权展开相加得到1位八进制数。（注意事项，3位二进制转成八进制是从右到左开始转换，不足时补0）

二进制转八进制

二进制转十六进制

八进制转二进制

八进制数通过除2取余法，得到二进制数，对每个八进制为3个二进制，不足时在最左边补零

小数转换

十进制转R进制

十进制小数转换成R进制小数采用“乘R取整，顺序输出”

十进制转二进制

例题： 0.68D = ______ B（精确到小数点后3位）

如下所示，0.68乘以2，取整，然后再将小数乘以2，取整，直到达到题目要求精度。
得到结果：0.101B.
0.68*2=1.36（取1）
0.36*2=0.72（取0）
0.72*2=1.44（取1）
0.44*2=0.88（取0）
0.88*2=1.76（取1）
.........

十进制转八进制

例：10.68（精确到小数点后三位，即乘三次8））注：整数位按整数位的转法转换，小数位按小数位的转法转换
10的八进制为12
0.68*8=5.44（取5）
0.44*8=3.52（取3）
0.52*8=4.10（取4）
最终的结果从上到下依次排序，为：12.534

十进制转十六进制

例：25.68（精确到小数点后三位，即乘三次16）注：整数位按整数位的转换法转换，小数位按小数位的转法转换
25的十六进制为19
0.68*16=10.88（取10，即A）
0.88*16=14.08（取14，即E）
0.08*16=1.28（取1）
最终的结果从上到下依次排序，为：19.AE1

R进制转十进制

把R进制数按权展开，相加即得十进制数

1.1.6 数据的寻址方式

指令格式

指令中的（目标 / 源）操作数来源
立即数：四位十六进制，如1234H
寄存器：操作数在寄存器中
存储器：操作数有“[ ]”

R=寄存器，E=有效地址，S=操作数，（A)=A中的内容，代码不特别说明表示8086汇编语言，PC=程序计数器（指向当前指令的下一条）

立即寻址

含义：指令的地址码部分给出的不是操作数的地址而是操作数本身，操作数直接包含在指令中，紧跟在操作码之后。

例子： MOV AX,1234H;——1234H就是采用立即寻址

隐含寻址

含义：操作数隐含的由累加器给出。（即某指令由固定的操作数，不需要给出）

例子：8086汇编语言 CWD;把AX中的内容按符号位拓展成DX,AX双字

直接寻址

含义：指令的地址码部分给出的形式地址A就是操作数的有效地址EA，即操作数的有效地址在指令字中直接给出。
E=A,S=(E)=(A)

例子：MOV AX,[1234H]

间接寻址

含义：指令的地址码部分给出的是操作数的有效地址EA所在的存储单元的地址或是指示操作数地址的地址指示字。即有效地址EA是由形式地址A间接提供的，因而称为间接寻址。
E=(A),S=(E)=((A))

理论上讲可以多次间接寻址，但大多数计算机只允许一次（由于A的寻址范围不足以覆盖整个存储空间）

相对寻址

含义：指令中给出相对于PC的偏移量A
E=(PC)+A,S=(E)=((PC)+A)

注：A是个带符号数，一般用补码表示，若A的位数与PC不一致，需要带符号填充。

基址寻址

含义：指令中给出相对于基址寄存器R的偏移量A
E=( R )+A,S=(E)=(( R )+A)

注：A是个带符号数，一般用补码表示，若A的位数与R不一致，需要带符号填充。

变址寻址

含义：指令中给出相对变址寄存器R的偏移量A
E=( R )+A,S=(E)=(( R )+A)

注：A是个带符号数，一般用补码表示，若A的位数与R不一致，需要带符号填充。

寄存器直接寻址

含义：指令中给出寄存器号R，操作数存放在R中
E=R,S=(E)=( R )

例子：MOV AX,BX——操作数在BX中

寄存器间接寻址

含义：指令中给出寄存器号R，R中存放操作数的有效地址
E=( R ),S=(E)=(( R ))

例子：MOV AX,[SI]

寻址空间大小

设定机器字长位n，A的位数位m

寻址方式获取的操作数的速度：立即寻址>寄存器寻址>直接寻址>寄存器间接寻址>间接寻址>相对寻址=变址寻址

1.2 计算机体系结构

1.2.1 计算机体系结构的发展

计算机体系结构分类

宏观（按处理机的数量）

单处理系统

系统只有一个通用 CPU，与其他外部设备结合起来，实现存储、计算、通信、I/O功能

并行处理与多处理系统（多核系统）

有两个或多个紧密通信的 CPU，它们共享计算机总线，有时还共享时钟、内存和外设等。

任务可以被划分为多个子任务，每个子任务由独立的处理单元（如CPU核心）并行执行。

分布式处理系统

建立在网络之上的软件系统，由多台计算机组成，地域上分散，逻辑上一个整体。

系统中的各个节点（计算机）通过通信网络相互连接，共享资源、协同工作。

微观（并行程度）

Flynn分类法

单指令流、单数据流（SISD，Single Instruction stream Single Data stream）

单指令流、多数据流（SIMD）

多指令流、单数据流（MISD）

多指令流、多数据流（MIMD）

冯泽云分类法

字串行位串行（WSBS，Word Serial and Bit Serial, WSBS）

字并行位串行（WPBS）

字串行位并行（WSBP）

字并行位并行（WPBP）

Handler分类法

PCU（处理控制器器或宏流水） K级

算术逻辑部件 ALU 或处理部件 PE 的个数 D级

每个算术逻辑部件包含基本逻辑线路 ELC 的套数 W级

Kuck分类法

单指令流单执行流（SISE）

单指令流多执行流（SIME）

多指令流单执行流（MISE）

多指令流多执行流（MIME）

复杂指令集计算机 CISC和精简指令集计算机RISC（按指令的复杂程度分类）

CISC全称Complex Instruction Set Computers，复杂指令集计算机

特点

①指令数量众多，指令系统中拥有大量的指令，通常有100～250条。

②指令使用频率相差悬殊。最常用的是一些比较简单的指令，仅占指令总数的20%,但在程序中出现的频率却占80%,大部分指令很少使用。

③变长的指令。指令长度不是固定的，变长的指令增加译码电路的复杂性。

④支持很多种寻址方式,通常为5～20种。

⑤以微程序控制为主。CISC的指令系统很复杂，难以用硬布线逻辑电路实现控制器，通常采用微程序控制。

⑥指令可以对主存单元中的数据进行处理，但是执行速度比较慢。

代表：Intel公司的x86系列CPU

应用：主要应用于桌面PC，笔记本市场（windows，Mac等）

区别

RISC全称Reduced Instruction Set Computers，精简指令集计算机

特点

①指令数量少。优先选取使用频率最高的一些简单指令和一些常用指令，避免使用复杂指令。只提供LOAD和STORE这两条指令对存储器操作。

LOAD用于从存储器中读数据

STORE用于把数据写入存储器

其余操作在CPU的寄存器之间进行

②指令长度固定，指令格式种类少。因为RISC指令数量少，格式少，相对简单，其指令长度固定，指令之间各字段的划分比较一致，译码相对容易。

③指令的寻址方式少。通常只支持寄存器寻址方式、立即数寻址和相对寻址方式。

④以硬布线逻辑控制为主，为提高操作的执行速度，采用硬布线逻辑构建控制器。

⑤CPU中的通用寄存器数量多，一般在32个以上，有的可达上千个。

⑥单周期指令执行，采用流水线结构。简化了指令系统，利用流水线技术，可以使得大部分指令都在一个机器周期内完成。当然，操作存储器的LOAD和STORE指令可能需要多个周期。

⑦优化的编译器，RISC的精简指令集使编译工作简单化。指令长度固定，格式少，寻址方式少，易于实现优化，生成高效率执行的机器代码。

代表：ARM指令构架，MIP指令构架

应用：主要用于移动手机端（如Android，ios）

指令流水线

指令控制方式

顺序方式

串行执行，按指令的先后顺序执行，即执行完一条指令才启动下一条指令

优点：控制简单、硬件代价小

缺点：执行指令速度慢，一个时刻只能有一条指令执行，资源利用率低

重叠方式

一次重叠执行方式

前一条指令的执行阶段和后一条指令的取指阶段重叠

优点:时间缩短了1/3，提高功能部件利用率

缺点：硬件代价较大，控制过程也相对复杂

二次重叠执行方式

更节约时间(正常情况下，处理机中同时有 3 条指令在执行)

相比顺序执行可以缩短2/3的时间，是一种理想的指令执行方式

流水方式

横坐标表示时间，即输入流水线中各个任务在流水线中所经过的时间

纵坐标表示空间，即流水线的每个流水段

性能指标

流水线执行时间

流水线执行时间 = 一条指令执行的时间 + 最长时间段 × (n-1)

加速比S

加速比 = 不采用流水线的执行时间 / 采用流水线的执行时间

流水线的操作周期

流水线的操作周期为长操作时间

吞吐率TP（单位时间内流水线完成的任务数量，或输出结果的数量）

流水线的吞吐率是最长流水段操作时间的倒数

连续输入n条指令的吞吐率 = 总指令数/总指令数执行的时间（n为总指令数）

顺序执行时间

顺序执行时间=一条指令执行的时间×总指令数

1.2.2 存储系统

存储器的层次结构

Cache 和主存之间的交互功能全部由硬件实现，而主存与辅存之间的交互功能可由硬件和软件结合起来实现

存储器的分类

按存储器所处的位置分类

内存

也称为主存，设在主机内或主机板上，用来存放机器当前运行所需要的程序和数据，以便向CPU提供信息

外存

也称为辅存，用来存放当前不参加运行的大量信息，而在需要时调入内存

如磁盘、磁带和光盘等

按存储器的构成材料分类

磁存储器

用磁性介质做成

如磁芯、磁泡、磁膜、磁鼓、磁带及磁盘等

半导体存储器

所用元件

双极型

MOS型

数据是否需要刷新

静态(Static Memory）

动态(Dynamic Memory）

光存储器

利用光学方法读/写数据的存储器

如光盘（Optical Disk)

按存储器的工作方式分类

读/写存储器（Random Access Memory，RAM）

既能读也能写

只读存储器

数据的写入方式

固定只读存储器(Read Only Memory，ROM)

在厂家生产时就写好数据的，其内容只能读出，不能改变

一般用于存放系统程序BIOS和用于微程序控制

可编程的只读存储器
(Programmable Read Only Memory，PROM)

其中的内容可以由用户一次性地写入，写入后不能再修改

可擦除可编程的只读存储器
（Erasable Programmable Read Only Memory，EPROM)

其中的内容既可以读出，也可以由用户写入，写入后还可以修改

改写的方法:写入之前先用紫外线照射15～20分钟以擦去所有信息，然后再用特殊的电子设备写入信息

电擦除可编程的只读存储器
(Electrically Erasable Programmable Read Only Memory,EEPROM)

与 EPROM相似，EEPROM中的内容既可以读出，也可以进行改写。但用电擦除的方法进行数据改写

闪速存储器
(Flash Memory)

简称闪存，闪存的特性介于EPROM和 EEPROM之间，类似于EEPROM，也可使用电信号进行信息的擦除操作

整块闪存可以在数秒内删除，速度远快于EPROM

按访问方式分类

按内容访问的存储器

相联存储器

按寻址方式分类

随机存储器
(Random Access Memory，RAM)

可对任何存储单元存入或读取数据，访问任何一个存储单元所需的时间是相同的

顺序存储器
(Sequentially Addressed Memory，SAM)

访问数据所需要的时间与数据所在的存储位置相关，磁带是典型的顺序存储器

直接存储器
(Direct Addressed Memory，DAM)

介于随机存取和顺序存取之间的一种寻址方式

磁盘是一种直接存取存储器，它对磁道的寻址是随机的，而在一个磁道内则是顺序寻址

存储容量计算

概述

术语解释

存储地址寄存器 MAR：MAR 位数 = 地址总线根数，决定了存储单元的个数

存储单元：若干个存储元组成

存储单元个数 = 2^MAR 位数 = 2 ^地址总线根数，单位：个

存储单元地址：给存储单元按顺序给定的地址编号

存储数据寄存器 MDR：MDR 位数 = 数据总线根数，决定了存储字长

存储字长：存储字的长度（位数），单位：bit

存储字长 = MDR 位数 = 数据总线根数，单位：bit

存储字：存储单元中的一连串二进制代码组合

存储元：存储一位二进制代码的基本单元电路

容量计算

存储单元个数

存储单元个数 = 末地址 - 首地址 + 1

【例题】存按字节编址，地址从 A4000H 到 CBFFFH，共有（ ? ）个字节。

根据公式存储单元个数 = 末地址 - 首地址 + 1 可知
存储空间 = C B F F F H − A 4000 H + 1 = 28000 H = 0010 1000 0000 0000 0000 B = 160 KB
注：1 K B = 2 ^10 B

存储容量

按位计算(b，bit)：存储容量 = 存储单元个数 * 存储字长

按字节计算(B，Byte)：存储容量 = 存储单元个数 * 存储字长 / 8

单位转换：1 字节 = 8 位，即 1 Byte = 8 bit

所需芯片数

所需芯片数 = 存储空间 / 存储容量

高速缓存

特点

位置：位于CPU和主存之间

容量：几千字节~几兆字节

速度：比主存快5~10倍

构成：快速半导体存储器

内容：主存局部域的副本

组成

地址映像方法(假设某台计算机主存容量为l MB，被分为2048块，每块512B；Cache容量为8KB，被分为16块，每块也是512B)

直接映像

优点：硬件简单，成本低，地址变换速度快，而且不涉及替换算法问题

缺点：不够灵活，Cache的存储空间得不到充分利用，每个主存块只有一个固定位置可存放，容易产生冲突，使Cache效率下降

只适合大容量Cache采用

全相联映像

优点：Cache的利用率高，块冲突概率低

缺点：无法从主存块号中直接获得Cache的块号，变换比较复杂，速度比较慢

只适合于小容量Cache采用

组相联映像

Cache替换算法

需要替换算法的原因

程序运行一段时间后，Cache存储空间被占满，当再有新数据调用时，就需要某种机制决定替换的对象

常见的几种

随机替换算法（Random Replacement，RR）

当缓存满时，随机选择一个缓存块进行替换

命中率低，实际效果很不稳定

先进先出算法（First In First Out, FIFO）

优先替换最先被调入Cache的主存块

导致频繁访问的数据被替换，从而产生所谓的“抖动现象”

近期最少使用算法（Least Recently Used, LRU）

将最久未被访问过的主存块替换。每个Cache行设置一个“计数器”，用于记录多久未被访问

基于“局部性原理”，近期被访问过的主存块，在不久的将来也很有可能被再次访问，因此淘汰最久没被访问过的块是合理的。LRU算法的实际运行效果优秀，Cache命中率高

最不经常使用（Least Frequently Used, LFU）

将被访问次数最少的主存块替换。每个Cache行设置一个“计数器”，用于记录多久未被访问

曾经被访问过的主存块在未来不一定会用到，LFU实际运行效果不好

Cache的性能分析

Cache的命中率

cache 的命中率与容量

cache 容量大，命中率高，当容量达到一定值时，命中率将不再明显提高
cache 容量大，成本越高
容量是成本与命中率的折中

cache 的命中率与块长

取决于程序的局部特性
对着块由小到大增长，命中率最初将提高，而后反而下降
块长最优值较难确定，一般取每块4~8个可编址单位，或是一个主存周期能读出的主存的信息长度
除此之外，地址映象方式、替换策略等影响命中率

多级Cache

当CPU试图从某地址load数据时，只有两级Cache的系统举例

虚拟存储器

外存储器（软盘、硬盘、光盘、U盘（闪存技术）、磁带）

磁表面存储器（磁盘、磁带）

定义：指把某些磁性材料薄薄地涂在金属铝或塑料表面上作为载磁体来存储信息

优点

1.存储容量大，位价格低

2.记录介质可以重复使用

3.记录信息可以长期保存而不丢失，甚至可以脱机存档

4.非破坏性读出，读出时不需要再生

缺点

1.存取速度慢

2.机械结构复杂

3.对工作环境要求较高

原理：当磁头和磁性记录介质有相对运动时，通过电磁转换完成读/写操作

编码方法：按某种方案（规律），把一连串的二进制信息变换成存储介质磁层中一个磁化翻转状态的序列，并使读/写控制电路容易、可靠地实现转换

磁记录方式：通常采用调频制(FM)和改进型调频制(MFM)的记录方式

包含

磁盘存储器

磁盘设备的组成

硬盘存储器

组成

盘片：存储信息

驱动器：核心部件是磁头组件和盘片组件

控制器：是硬盘存储器和主机的接口，主流的标准有旧E、SCSI、SATA等。

接口：主机和磁盘存储器之间的连接逻辑

存储区域：一块硬盘含有若干个记录面，每个记录面划分为若干条磁道，而每条磁道又划分为若干个扇区。扇区（也称块）是磁盘读写的最小单位，也就是说磁盘按块存取。

磁头数：即记录面数，表示硬盘总共有多少个磁头，磁头用于读取/写入盘片上记录面的信息，一个记录面对应一个磁头。

柱面数：表示硬盘每一面盘片上有多少条磁道。在一个盘组中，不同记录面的相同編号（位置）的诸磁道构成一个圆柱面。

扇区数：表示每一条磁道上有多少个扇区

磁盘的性能指标

记录密度：指盘片单位面积上记录的二进制的信息量，通常以道密度、位密度和面密度表示。

道密度（tpi,每英寸磁道数）：沿磁盘半径方向单位长度上的磁道数

位密度(bpi,每英寸位数)：磁道单位长度上能记录的二进制代码位数

面密度：位密度和道密度的乘积

注意：磁盘所有磁道记录的信息量一定相等的，并不是圆越大信息越多，故每个磁道的位密度都不同

磁盘的容量：一个磁盘所能存储的字节总数称为磁盘容量

非格式化容量

定义：指磁记录表面可以利用的磁化单元总数

非格式化容量=面数*（磁道数/面）*内圆周长*最大密度

格式化容量

定义：指按照某种特定的记录格式所能存储信息的总量

格式化容量=面数*（磁道数/面）*（扇区数/道）*（字节数/扇区）

平均存取时间=寻道时间（磁头移动到目的磁道）+旋转延迟时间（磁头定位到所在扇区）+传输时间（传输数据所花费的时间）

数据传输率：磁盘存储器在单位时间内向主机传送数据的字节数，称为数据传输率

磁盘地址：驱动器号|柱面（磁道）号|磁头号（盘面号）|数据块号（扇区号）

驱动器号：一台电脑可能有多个硬盘，首先我们会选中一个特定的硬盘

柱面（磁道）号：移动磁头臂（寻道）

盘面号：激活某个磁头

扇区号：通过旋转将特定扇区划过磁头下方

硬盘的工作过程：硬盘的主要操作是寻址、读盘、写盘。每个操作都对应一个控制字，硬盘工作时，第一步是取控制字，第二步是执行控制字。硬盘属于机械式部件，其读写操作是串行的，不可能在同一时刻既读又写，也不可能在同一时刻读两组数据或写两组数据。

磁带存储器

磁鼓存储器

光盘存储器

定义：利用光学原理读/写信息的存储装置，它采用聚焦激光束对盘式介质以非接触的方式记录信息

组成

光盘片(透明的聚合物基片,铝合金反射层,漆膜保护层的固盘)

光盘驱动器

光盘控制器

盘驱动软件

分类

只读型光盘CD-ROM：只能读出其中内容，不能写入或修改

CD-R：只可写入一次信息，之后不可修改

CD-RW：可读可写光盘，可以重复读写

DVD-ROM：高容量的CD-ROM，DVD表示通用数字化多功能光盘

特点：存储密度高，携带方便，成本低，容量大，存储期限长，容易保存

固态硬盘SSD

采用高性能闪存作为硬盘来记录数据，这种“硬盘”称固态硬盘。

存储介质分类

Flash芯片

DRAM

固态硬盘除了需要闪存外，还需要其他硬件和软件的支持。

注：闪存是在E2PROM的基础上发展起来的，本质上是只读存储器。

特点：具有传统机械硬盘不具备的读写快速、质量轻、能耗低以及体积小等特点

价格昂贵、容量较低、一旦损坏，数据较难恢复

1.2.3 输入/输出技术

I/O 设备编址方式

独立编址

定义：I/O 地址和存储器地址是分开的，所以对 I/O 设备的访问必须有专门的 I/O 指令

I/O端口地址与存储器地址无关，是完全独立的两个地址空间。

访问数据的指令也完全不同，用于接口的指令值用于接口的读/写，其余的指令全都是用于内存的，因此在编程序或读取程序中容易使用和辨认。

优点：I/O指令与存储器指令有明显区别，程序编制清楚，便于理解

缺点：I/O指令少，一般只能对端口进行传送操作，尤其需要CPU提供存储器读/写、I/O设备读写两组控制信号，增加控制的复杂性

统一编址

定义：将 I/O 地址看作存储器地址的一部分

内存地址和接口地址统一在一个公共的地址空间里，即内存单元和接口共用地址空间。

优点：原则上用于内存的指令都可以用于接口，增强了对接口的操作功能，而且在指令上也不在区分内存和接口指令。

缺点：整个地址空间被分为两部分，导致内存地址不连续。由于内存的指令和用于接口的指令是完全一样的，维护程序时就需要根据参数定义表仔细加以辨认。

CPU与外设间的传送方式

直接程序控制

无条件传送

最简单的数据传送方式 , 适用于总是处于准备好状态的外设 , 外设无条件地随时接收 CPU 发来的输出数据 , 也能够无条件地随时向 CPU 提供需要输入的数据

前提：外设始终处于准备好状态 , 在实际应用中受到很大的限制

程序查询方式

又称为轮询方式 , CPU 需要不断查询外设的状态 , 判断外设是否准备好进行输入或输出操作

优缺点

优点

实现比较简单 , 成本低廉

缺点

效率低 : CPU 与外围设备串行工作 , 在同一时间只能与一台外设通信 , 无法与多态设备并行通信 , 工作效率低下 ;

时效差 : 对于需要实时响应的外设 , CPU 需要等待大量时间 , 程序查询方式可能无法满足要求

中断方式（中断方式利用中断机制，使I/O系统在与外设交换数据时，CPU 无须等待，也不必查询I/O状态，即可以抽身出来处理其他任务，因此提高了系统效率。）

中断向量：提供中断服务程序的入口地址

中断响应时间：发出中断请求开始，到进入中断服务程序

保存现场，返回来执行源程序

中断处理方法

(1)多中断信号线法：就是给每个中断源"拉一根电话线",做到专线专用。

(2)中断软件查询法：CPU收到中断后转到中断服务程序，由该程序来确认中断源。

(3)雏菊链法：硬件查询法，所有的I/O模块共享一条共同的中断请求线。

(4)总线仲裁法：一个I/O设备在发出中断请求前，必须先获得总线控制权。由总线仲裁机制来决定谁有权发出中断信号。

(5)中断向量表法：中断向量表用来保存各个中断源的中断服务程序的入口地址，当外设发出中断后，由中断控制器确定其中继号。

中断优先级控制

解决

当不同优先级的多个中断源同时提出中断请求时，CPU 应优先响应优先级最高的中断源

若此时 CPU 正在处理某中断源，同时有更高级中断请求，则 CPU 需要立即停止正在处理的中断源去响应这个更高级的中断请求，完成该请求后再恢复处理，即中断嵌套

为了便于实现多级中断嵌套，使用堆栈来保护断点和现场最有效

优缺点

优点

支持多个程序进程和外围设备的并行数据传输操作 , 提高了 CPU 的利用率

缺点

每次数据传输都需要向 CPU 发送中断信号 , 如果中断次数较多 , 会占用大量 CPU 时间

外围设备数量较大时 , 过多的中断次数导致 CPU 无法及时响应中断 , 出现数据丢失的情况

直接存储器方式（DMA）

在存储器与I/O设备间直接传送数据，即在内存与 I/O 设备之间传送一个数据块的过程中，不需要 CPU 的任何干涉，只需要CPU在过程开始启动(即向设备发出“传送一块数据”的命令)与过程结束(CPU通过轮询或中断得知过程是否结束和下次操作是否准备就绪)时的处理，实际操作由DMA硬件直接执行完成，CPU在此传送过程中可做别的事情

CPU是在一个总线周期结束时响应DMA请求的

输入/输出处理机（IOP）

一个专用处理机，用于完成主机的输入/输出操作。IOP 根据主机的 I/O 命令，完成对外设数据的输入/输出。

数据传送方式有三种：字节多路方式、选择传送方式和数组多路方式。

效率：I/O处理机>通道方式>DMA方式>程序中断方式>程序控制（查询）方式

1.2.4 总线结构

通过总线来传输信息的，根据信息的内容总线分类

数据总线（Data Bus，DB）：在CPU与RAM之间来回传送需要处理或是需要储存的数据

方向

双向

功能

用来传送数据信息

性能

DB的宽度决定了CPU和其他设备之间每次交换数据的位数

地址总线（Address Bus，AB）：用来指定在RAM（Random Access Memory）之中储存的数据的地址

方向

单向

功能

用于传送CPU发出的地址信息

性能

地址总线的宽度决定了CPU的最大寻址能力

控制总线（Control Bus，CB）：将微处理器控制单元（Control Unit）的信号，传送到周边设备，一般常见的为 USB Bus和1394 Bus

方向

双向

功能

用来传送控制信号、时序信号、状态信息

性能

CB 中的每一条线的信息传送方向是单方向且确定的，但 CB 作为一个整体则是双向的

常见总线

1) ISA(Industry Standard Architecture)总线：ISA是工业标准总线，只能支持16位的I/O设备。

(2) EISA(Extended Industry Standard Architecture)总线：EISA是在ISA总线的基础上发展起来的32位总线。

(3) PCI(Peripheral Component Interconnection)总线：PCI总线是目前微型机上广泛采用的内总线，采用并行传输方式。

(4)PCIExpress总线。PCI Express简称为PCI-E，采用点对点串行连接，每个设备都有自己的专用连接，不需要向整个总线请求带宽，而且可以把数据传输率提高到一个很高的频率。

(5)前端总线。微机系统中，前端总线(Front Side Bus，FSB）是将CPU连接到北桥芯片的总线。

(6)RS-232C。S-232C是一条串行外总线，其主要特点是所需传输线比较少，最少只需三条线(一条发、一条收、一条地线)即可实现全双工通信。

(7)SCSI总线。小型计算机系统接口(SCSI）是一条并行外总线，广泛用于连接软硬磁盘、光盘、扫描仪等。

(8)SATA。SATA是Serial ATA 的缩写，即串行ATA。它主要用作主板和大量存储设备(如硬盘及光盘驱动器）之间的数据传输之用。串行接口还具有结构简单、支持热插拔的优点。

(9)USB。通用串行总线(USB）当前风头正劲，近几年得到十分广泛的应用。USB总线最大的优点还在于它支持即插即用，并支持热插拔。

(10)IEEE-1394。EEE-1394是高速串行外总线，近几年得到广泛应用。IEEE-1394也支持外设热插拔，可为外设提供电源，省去了外设自带的电源，能连接多个不同设备，支持同步和异步数据传输。

(11)IEEE-488总线。IEEE-488是并行总线接口标准。

外部总线

(1) RS-232-C：一种串行外总线，主要特点是所需传输线比较少，最少只需3条线即可实现全双工通信；传输距离远，用电平传送为 15m，用电流环传送为 1km：有多种可供选择的传输速率，具有较好的抗干扰性。

(2) SCSI(Small Computer Standard Interface)总线：一种并行外总线，广泛用于连接硬盘、光盘等。该接口早期是8位的，后来发展成16位。sCSl-3 定义了怎样在8 位 SCSI 总线上每秒传输 20MB 数据和在16位 Wide scsl 总线上每秒传输 40MB 数据。该总线上最多可接63 种外设，传输距离可达 20m。

(3) USB(Universal Serial Bus)总线：USB 是1995年由微软、康柏、IBM 等公司联合制定的一种新的 PC 串行通信协议。USB由4条信号线组成，可以经过集线器进行树状连接，最多可达5层。该总线上可接 127 个设备，其最大的优点在于支持即插即用技术并支持热插拔。

(4) IEEE-1394: 一种串行外总线，由6条信号线组成，可接 63 个设备，传输速率从400MB/S、 800MB/S、1600MB/s 直到3.2GB/s，最大优点在于支持即插即用并支持热插拔。

根据总线它当中的数据线的多少

串行总线（适合长距离传输），只包含一条双向传输的数据线，或者两条单向传输的数据线。

并行总线（适合短距离连接，不宜过长），包含有多条双向的数据线来进行集成。

总线的落地实现有几种架构

单总线：将系统总线抽象成一个整体来看待后，所有设备其实都接在系统总线的一个实体上。
双总线：为了解决单总线系统中CPU空转的问题。双总线系统即在CPU和主存之间加上一条总线，专门用于CPU和主存之间进行数据的交互。
三总线
多总线

专用和非专用总线各自的优缺点

专用线：只连接一对物理部件的总线。

优点：不用争总线，控制简单，系统可靠。
缺点：总线数多且长，成本高，利用率低，不易扩展。

非专用线：可被多种功能与部件共享，但同一时刻只能被一个部件使用。

优点：集成度高，造价低，可扩展能力强，总线利用率高，易标准化。
缺点：流量小，争用总线，部件效率低，可能成为瓶颈，可靠性差。

1.3 安全性、可靠性与系统性能评测基础知识

1.3.1 计算机安全概述

安全威胁是指某个人、物、事件对某一资源的机密性、完整性、可用性或合法性所造成的危害

故意(如黑客渗透)

偶然（如信息发往错误的地址)

某种攻击就是威胁的具体实现

影响数据安全的因素

（1）内部因素。可采用多种技术对数据加密；制定数据安全规划；建立安全存储体系；建立事故应急计划和容灾措施；重视安全管理，制定数据安全管理规范。

2）外部因素。可将数据分成不同的密级，规定外部使用人员的权限。设置身份认证、密码、指纹、声纹、笔记等多种认证；设置防火墙，为计算机建立一道屏障，防止外部入侵破坏数据；建立入侵检测、审计和追踪，对计算机进行防卫。同时，也包括计算机物理环境的保障、防辐射、防水、防火等外部防灾措施。

1.3.2 加密技术和认证技术

加密技术

加密类型

对称加密（私钥）（共享密钥加密算法)

分类

数据加密标准(DES)算法。主要采用替换和移位的方法加密。DES算法运算速度快，密钥生产容易，适合于在当前大多数计算机上用软件方法实现，同时也适合在专用芯片上实现。

三重DES(3DES 或称 TDES)。

RC-5(Rivest Cipher 5)，需要大量的明文是用对称加密算法

国际数据加密算法( IDEA)，IDEA算法也是一种数据块加密算法，它设计了一系列加密轮次，每轮加密都使用从完整的加密密钥中生成的一个子密钥。

高级加密标准(AES)算法。基于排列和置换运算。AES是突发迭代的、对称密钥分组的密码，它可以使用 128、192 和256位密钥，并且用128 位（16字节）分组加密和解密数据。

RC4算法

优缺点

优点: 加密速度快（因为加密解密都是同一把），适合加密大量明文数据

缺点: 秘钥分发有缺陷，密钥发送过程中可能被别人获取到

非对称加密（公钥，公开密钥加密算法）

属于非对称密钥（公钥）算法：RSA、ECC、DSA

优缺点

优点: 密钥分发没有缺陷，公钥在分发过程中即使被别人获取到，也不能对数据解，私钥只在接收方手中。

缺点: 加密解密数据慢

不可逆加密

密钥管理主要是指密钥对的安全管理，包括密钥产生、密钥备份和恢复、密钥更新以及多密钥管理。

认证技术

哈希函数与信息摘要

防止篡改：将发送的明文进行Hash算法后得到摘要，将摘要放在加密好的密文的后面一起发送过去，接收方接收到数据使用私钥对密文进行解密得到明文，对明文使用和发送方相同的Hash算法得到摘要。然后和发送方发过来的摘要进行比对，如果一致则没有被篡改，否则有被篡改

MD5 摘要算法（防止发送的报文被篡改），对任意长度的输入计算得到的结果长度为128位。

SHA-1 安全散列算法

数字签名

数字签名可以解决否认、伪造、篡改及冒充等问题，应用范围十分广泛，如加密信件、商务信函、订货购买系统、远程金融交易、自动模式处理等。

数字签名使用的是发送方的密钥对，发送方用自己的私钥对摘要进行签名（加密），得到数字签名放在密文中一起发送过去。接收方用发送方的公钥对数字签名进行验证（解密），如果验证（解密）成功则该消息没有被假冒且不能否认，否则该消息的真是性为假。这是一个一对多的关系，任何拥有发送方公开密钥的人都可以验证数字签名的正确性。

数字加密则使用的是接收方的密钥对，这是多对一的关系，任何知道接收方公开密钥的人都可以向接收方发送加密信息，只有唯一拥有接收方私有密钥的人才能对信息解密。

数字签名只采用了非对称密钥加密算法，它能保证发送信息的完整性、身份认证和不可否认性，而数字加密则采用了对称密钥加密算法和非对称密钥加密算法相结合的方法，它能保证发送信息的保密性。

数字证书

CA：权威机构，信任机构（像公安局，法院）

数字证书：用户向CA机构申请数字证书，将个人信息和公钥发给CA机构，CA机构颁给用户数字证书，数字证书用CA的私钥进行签名（加密），用CA的公钥进行验证（解密）数字证书，得到用户的公钥。

用CA机构的私钥签名，用CA机构的私钥验证数字证书的真伪性
数字证书可以确认网站的合法性，用户的身份等

SSL协议（基于 Web 应用的安全协议，又叫安全套接层协议）

提供三方面的服务

用户和服务器的合法性认证

加密数据以隐藏被传送的数据

保护数据的完整性，目的是在两个通信应用程序之间提供私密性和可靠性

数字时间戳技术

数字时间戳服务(DTS)是网上电子商务提供的安全服务项目之一，能提供电子文件的日期和时间信息的安全保护。

时间戳(Time-stamp)是一个经加密后形成的凭证文档，它包括以下3个部分

需加时间戳的文件的摘要

DTS收到文件的日期和时间

DTS 的数字签名

1.3.3 计算机可靠性

计算机可靠性模型

第2章程序设计语言基础知识

2.1程序设计语言概述

2.1.1 程序设计语言的基本概念

1.低级语言和高级语言

低级语言

机器语言

机器语言是指用 0、1字符串组成的机器指令序列，是最基本的计算机语言。

汇编语言

汇编语言是指用符号表示指令的语言。

高级语言是从人类的逻辑思维角度出发、面向各类应用的程序语言，抽象程度大大提高，需要经过编译成特定机器上的目标代码才能执行。

常见：Java、C、C++、PHP、Python、Dephi、PASCAL

特点：与人们使用的自然语言比较接近，大大提高了程序设计的效率。

2.编译程序和解释程序

汇编程序将汇编语言编写的源程序翻译成为目标程序，然后执行。

编译程序(编译器)则是将高级语言编写的源程序翻译成目标语言程序，然后在计算机上执行目标程序。

翻译时将源程序翻译成独立保存的目标程序

机器上运行的是与源程序等价的目标程序，源程序和编译程序都不再参与目标程序的运行过程

解释程序也称为解释器，直接解释执行源程序，或者将源程序翻译成某种中间代码表示形式后再执行

翻译源程序时不生成独立的目标程序

解释程序和源程序要参与到程序的运行过程中

3.程序设计语言的定义

语法。由程序设计语言的基本符号组成程序中的各个语法成分(包括程序)的一组规则，其中由基本符号构成的符号(单词)书写规则称为词法规则，由符号(单词）构成语法成分的规则称为语法规则。程序语言的语法可通过形式语言进行描述。

语义。程序语言中按语法规则构成的各个语法成分的含义。

静态语义

动态语义

语用。表示构成语言的各个记号和使用者的关系，涉及符号的来源、使用和影响。

语境。理解和实现程序设计语言的环境，包括编译环境和运行环境。

4.程序设计语言的分类

命令式和结构化程序设计语言

命令式程序设计语言：基于动作的语言，计算被看作动作的序列。

命令式语言族开始于 FORTRAN、 PASCAL 和C语言，体现了命令式程序设计的关键思想

结构化程序设计语言：C、PASCAL

面向对象的程序设计语言

对象

类

继承

代表：C++、Java、Smalltalk

函数式程序设计语言

一类以λ-演算为基础的语言

代表: LISP 语言，其中大量使用了递归。

常见：Haskell、Scala、Scheme、APL

逻辑型程序设计语言

一类以形式逻辑为基础的语言。

代表:建立在关系理论和一阶谓词理论基础上的 Prolog 语言。适用于编写自动定理证明、专家系统、自然语言理解

2.1.2 程序设计语言的基本成分

数据成分：指一种程序语言的数据类型。

常量和变量：按照程序运行时数据的值能否改变分

程序中的数据对象可以具有左值和(或)右值，左值是指存储单元(或地址、容器)，右值是指具体值(或内容)。

变量具有左值和右值，在程序运行过程中其右值可以改变。

常量只有右值，在程序运行过程中其右值不能改变。

全局量和局部量：按数据的作用域范围分

系统为全局变量分配的存储空间在程序运行的过程中一般是不改变的。

为局部变量分配的存储单元是动态改变的。

数据类型：按照数据组织形式的不同可将数据分为基本类型、用户定义类型、构造类型及其他类型。C(C++）的数据类型如下。

基本类型：整型（int)、字符型(char)、实型(float、double)和布尔类型(bool)。

特殊类型：空类型(void)。

用户定义类型：枚举类型(enum)。

构造类型：数组、结构体和共用体。

指针类型：type *。

抽象数据类型：类类型。

运算成分

算术运算

“四则运算”，是加法、减法、乘法、除法、乘方、开方等几种运算的统称。

C语言中的算术运算符包括：+、-、*、/、++、--、% 等种类。

运算规则：只存在同级运算，则从左至右的顺序进行；有括号，则应先算括号里边，再按上述规则进行计算。

逻辑运算

与运算 &&：双目运算符

两边同时为真才为真，有一个假则结果为假
短路运算时，左边为假则表达式结果为假

或运算 ||：双目运算符

两边同时为假才为假，有一个真则结果为真
短路运算时，左边为真则表达式结果为真

非 !：单目运算符

真变假假变真
右结合从右向左算比如：!3<2，先算3<2为假，然后!假，结果为真。
比如：x=1,y=2,z=3,然后x=y=z，先算y=z，这个时候y的值为3，再算x=y，结果就是x、y、z的值都为3

关系运算

分类

传统的集合运算（并、差、交等）

专门的关系运算（选择、投影、连接、除法、外连接等）

常见的关系运算符包括：<、<=、>、>=、==、!= 等种类。前4种关系运算符(<、<=、>、>= )的优先级别相同，后2种(==、!=)也相同，而前4种高于后2种。

位运算：对二进制数的每一位进行操作的运算

控制成分

顺序结构

选择结构

循环结构

C(C++)语言提供的控制语句

复合语句。复合语句用于描述顺序控制结构。复合语句是一系列用“{” 和“}”括起来的声明和语句，其主要作用是将多条语句组成一个可执行单元。复合语句是一个整体，要么全部执行，要么一条语句也不执行。

if语句和switch语句，用于实现选择结构。

循环语句

①while语句

②do-while语句

③for语句

传输成分

函数

函数定义。包括函数首部和函数体两个部分。函数的定义描述了函数做什么和怎么做。

函数声明。函数应该先声明后引用。函数声明定义了函数原型。声明函数原型的目的在于告诉编译器传递给函数的参数个数、类型以及函数返回值的类型，参数表中仅需要依次列出函数定义中的参数类型。函数原型可以使编译器检查源程序中对函数的调用是否正确。

函数调用

传值调用

将实参的值传递给形参，实参可以是变量、常量和表达式。

不可以实现形参和实参间双向传递数据的效果。

传引用（地址）调用

将实参的地址传递给形参，形参必须有地址，实参不能是常量（值），表达式。

可以实现形参和实参间双向传递数据的效果，即改变形参的值同时也改变了实参的值。

2.2 语言处理程序基础

2.2.1 汇编程序基本原理

汇编语言

汇编语言是为特定的计算机或计算机系统设计的面向机器的符号化的程序设计语言。

汇编语言源程序由若干条语句组成

指令语句

又称为机器指令语句，汇编后能产生相应的机器代码，被 CPU 直接识别并执行相应的操作。

传送指令

算术运算指令

逻辑运算指令

移位指令

转移指令

处理机控制指令

伪指令语句

指示汇编程序在对源程序进行汇编时完成某些工作

常数定义伪指令语句

存储定义伪指令语句

开始伪指令语句

结束伪指令语句

宏指令语句

将多次重复使用的程序段定义为宏

汇编程序

汇编程序的功能是将用汇编语言编写的源程序翻译成机器指令程序。

2.2.2 编译程序基本原理

编译过程概述

编译、解释程序翻译阶段

编译方式：词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成
解释方式：词法分析、语法分析、语义分析

解释器与编译器

解释器

翻译源程序时不生成独立的目标程序

解释程序和源程序要参与到程序的运行过程中

编译器

翻译时将源程序翻译成独立保存的目标程序

机器上运行的是与源程序等价的目标程序，
源程序和编译程序都不再参与目标程序的运行过程

编译器和解释器都不可省略词法分析、语法分析、语义分析且顺序不可交换
编译器方式中中间代码生成和代码优化不是必要，可省略。即编译器方式可以在词法分析、语法分析、语义分析阶段后直接生成目标代码

编译过程划分成6 个阶段，实际的编译器可能会将其中的某些阶段结合在一起进行处理，比如说符号表管理和出错处理与上述6个阶段都有联系。

词法分析

语法分析

自顶向下的分析是对给定的符号串，试图自顶向下地为其构造一棵语法树，或者说从文法的开始符号出发，为其构造一个最佳推导。
自底向上的分析是对给定的符号串，试图自底向上地为其构造一棵语法树，或者说从给定的符号串本身出发，试图将其归约为文法的开始符号。
算符优先文法属于自底向上的分析法，它利用各个算符间的优先关系和结合规则来进行语法分析，特别是用于分析各种表达式。算符优先文法的任何产生式的右部都会出现两个非终结符相邻的情况，且任何一对终结符之间至多只有3 种算符关系，即“>”“<”和“=”之一成立

语义分析

中间代码生成

常见的中间代码有：后缀式（逆波兰式）、三地址码、三元式、四元式和树（图）等形式。

表达式id1:=id2+id3*60的树形表示为：

中间代码与具体的机器无关（不依赖具体的机器），可以将不同的高级程序语言翻译成同一种中间代码，中间代码可以跨平台。
因为与具体的机器无关，使用中间代码有利于进行与机器无关的优化处理和提高编译程序的可移植性。

代码优化

对前阶段产生的中间代码进行变换或进行改造，目的是使生成的目标代码更为高效，即省时间和省空间。

优化过程可以在中间代码生成阶段进行，也可以在目标代码生成阶段进行。

代码优化不依赖于具体机器，一般建立在对程序的控制流和输出流分析的基础上，与具体的机器无关

目标代码生成

目标代码生成的工作与具体的机器密切相关

寄存器的分配工作处于目标代码生成阶段

符号表：不断收集、记录和使用源程序中一些相关符号的类型和特征等信息，并将其存入符号表中。
记录源程序中各个字符的必要信息，以辅助语义的正确性检查和代码生成。

出错处理

动态错误

也称动态语义错误，它们发生在程序运行时，例如变量取零时作除数、引用数组元素下标错误等。

静态错误

指编译阶段发现的程序错误，可分为

语法错误

单词拼写错误、标点符号错、表达式中缺少操作数、括号不匹配等有关语言结构上的错误

静态语义错误

语义分析时发现的运算符与运算对象类型不合法等错误

词法分析

正规式与正规集

语法描述的基本概念

字母表：一个有穷字符集，记为Σ,字母表中的每个元素称为字符
Σ上的字（字符串）：由Σ中的字符构成的一个有穷序列。
不包含任何字符的序列称为空字，记为ε
Σ*表示Σ上所有字的全体（Σ上所有字符所能产生的字），包含空字ε

例：设Σ={ a，b }，则
Σ* = { ε，a，b，aa，ab，bb，ba，aaa，…}

若U、V为Σ*的两个子集，则U和V的连接（积）定义为UV = { αβ | α∈U & β∈V }，顺序不可颠倒

例：设U = { a，aa }、V = { b，bb }
则UV = { ab，abb，aab，aabb }

V自身的n次积记为V^n
V^0 = { ε }
V*是V的闭包：V*=V^0∪V^1∪V^2∪V^3∪…
V+是V的正规闭包：V+ = VV*,正规闭包是不包含 ε 的闭包

例：设U={ a，aa }
U* = { ε，a，aa，aaa，……}
U+ =UU*= { a，aa，aaa，aaaa，……}

编译原理里面的概念

正规式用来描述一类单词。

正规集是正规式描述的单词集。

单词，其实就是一个符号串，可以是字母、数字或者其他字符的组合。

运算符优先级

“*”(闭包) > (连接) > "|"(或)

方法（存在两个字符a,b）

正规式a，表示单一字符a，对应的正规集{a}。
正规式a|b，表示单一字符a或者b，对应有2个元素的正规集{a,b}。
正规式ab，表示由两个字符ab的元素，对应只有1个元素的正规集{ab}。
正规式ab(a|b)，ab是确定的部分，然后再添加a或b，对应正规集{aba,abb}。
正规式a*，*表示任意个，对应正规集{Φ,a,aa,aaa,...}。
正规式(a|b)*，可以表示任意由a、b组成的串的集合，对应正规集{Φ,a,b,ab,aa,bb...}。

(a|b) ，a或b，两个选择一个
(a|b)* 如果* 的值为2，表示出现的次数为2，即第1次从 a、b中选一个，第2次也是从 a、b中选一个
第1次为 a 第2次为b 则为 ab
第1次为 a 第2次为a 则为 aa
第1次为 b 第2次为a 则为 ba
第1次为 b 第2次为b 则为 bb

解析：
对于A，如果第一个*执行0次，第二个*执行1次，第三个*执行1次，结果为：ab，a不是偶数个，错误。
对于B，由于中间括号中两个aa必然成对出现，所以是偶数个a，正确。
对于C，第一个*执行1次，第二、三个*执行0次，第四个*执行1次，结果为：ab，a不是偶数个，错误。
对于D，如果(a|b)执行为a，且第一个*执行1次，第二个*执行1次，结果为：aaa，a不是偶数个，错误。

有限自动机

概述

词法分析的一个工具，它能够正确地识别正规集。

初态和终态

初态: 箭头指向的那个状态
终态：两个圆圈

字符识别与状态转移

识别时，状态到终态才算识别成功

确定的/不确定的有限自动机

确定的有限自动机（DFA）：对每一个状态来说识别字符后转移的状态是唯一的

不确定的有限自动机（NFA）：对每一个状态来说识别字符后转移的状态不一定是唯一的，是不确定的

识别多个字符

空符号

文法分类

上下文无关法

根据上述规则，句子无需考虑上下文，就可以判断正确性（符合<主语><谓语><间接宾语><直接宾语>的规则

He，me等为终结符号

<主语>、<谓语>、<间接宾语>等为非终结符号

定义<句子>语法结构，<句子>在这里称为开始符号，<谓语>→<动词>这种书写形式称之为产生式

例如:E→i|EAE A→+|*
是上下文无关语法，E、A是非终结符，E是开始符，而i，+和*是终结符

大多数程序设计语言的语法规则广泛地用上下文无关文法描述

中缀、后缀表达式转换

概述

优先级

优先级：
1.() 2. > 3. ∩ 4. ∪

优先级()x/±，优先级相同，从右往左

中缀表达式

常见的运算表达式, 例如: (3x4)x5-6

中缀和后缀的区别

中缀式：a + b
后缀式（逆波兰式）：ab+

中缀转后缀表达式

方式1: 直接生成
中缀式：a + b ----> 后缀式（逆波兰式）：ab+

方式2：栈

1 初始化两个栈: s1(运算符栈)， s2(存储中间结果栈)
2 从左到右扫描中缀表达式
(1) 遇到操作数，压入s2
(2) 遇到运算符, 与s1栈顶运算符进行优先级比较
a: “s1为空”或“栈顶运算符为左括号 ”(“, 压入s1
b: 优先级 > 栈顶运算符优先级，也将运算符压入s1, 否则将s1栈顶运算符弹出并压入到s2 中，再重复该步骤

3 遇到括号:
(1) 左括号 "(", 直接压入s1
(2) 右括号 ")", 依次弹出s1栈顶运算符，并压入s2,直到遇到左括号为止，此时将这一对括号丢弃，重复2-3步骤，直到表达式的最右边。

4 将s1中剩余的运算符依次弹出并压入s2
5 依次弹出s2中的元素并输出得到后缀表达式

后缀转中缀表达式

后缀式（逆波兰式）：ab+ ----> 中缀式：a + b

语法树的遍历

前序: 先输出父节点，再遍历左子树和右子树

中序: 先遍历左子树，再输出父节点，再遍历右子树

后序: 先遍历左子树，再遍历右子树，再输出父节点

第3章数据结构

3.1 线性结构

3.1.1 线性表

1.线性表的定义

线性表是n个元素的有限序列，通常记为(a1,a2,…,an)。其特点如下。

存在唯一的一个称为“第一个”的元素
存在唯一的一个称为“最后一个”的元素。
除了表头外，表中的每一个元素均只有唯一的直接前驱。
除了表尾外，表中的每一个元素均只有唯一的直接后继。

2.线性表的存储结构

1.顺序存储

线性表的顺序存储是用一组地址连续的存储单元依次存储线性表中的数据元素，从而使得逻辑关系相邻的两个元素在物理位置上也相邻。在这种存储方式下，存储逻辑关系无须占用额外的存储空间。

插入和删除

取值、查找、插入时间复杂度

取值

顺序表取值算法的时间复杂度为O(1)

查找

顺序表按值查找算法的平均时间复杂度为O(n)

插入

一般情况下，在第i（1≤i≤n）个位置插入一个元素时，需从最后一个元素即第n个元素开始，依次向后移动一个位置，直至第i个元素（共n-i+1个元素），仅当插入位置i=n+1时，才无须移动结点。

顺序表插入算法的平均时间复杂度为O(n)

优缺点

优点：可以随机存取表中的元素，存储密度高

缺点：插入和删除操作需要移动大量的元素，大片连续空间分配不方便，改变容量不方便

2.链式存储

线性表的链式存储是指用节点来存储数据元素，节点的空间可以是连续的，也可以是不连续的，因此存储数据元素的同时必须存储元素之间的逻辑关系。节点空间只有在需要的时候才申请，无须事先分配。

最基本的节点结构：数据域用于存储数据元素的值，指针域则存储当前元素的直接前驱或直接后继信息，指针域中的信息称为指针(链)。

【函数】设线性表中的元素是整型，则单链表结点类型的定义为：

typedef struct node{
int data; /*结点的数据域，此处假设为整型*/
struct node*next; /*结点的指针域*/
}NODE,*LinkList;

n个节点通过指针连成一个链表，若节点中只有一个指针域，则称为线性链表(单链表)。

插入

在单链表中，若在p所指结点后插入新元素结点（s所指结点，已经生成)。即先将p所指结点的后继结点指针赋给s所指结点的指针域，然后将p所指结点的指针域修改为指向s所指结点。操作过程可表示为： ① s->next = p->next; ② p->next = s;

删除

在单链表中删除p所指结点的后继结点时，即先令临时指针q指向待删除的结点，然后修改p所指结点的指针域为指向p所指结点的后继的后继结点，从而将元素b所在的结点从链表中删除，最后释放q 所指结点的空间。操作过程可表示为：① q = p -> next; ② p -> next = p -> next -> next; ③ free(q);

查找

双向链表。每个结点包含两个指针，分别指出当前元素的直接前驱和直接后继。其特点是可以从表中任意的结点出发，从两个方向上遍历链表。

插入

若双向链表中结点的 front 和 next 指针域分别指示当前结点的直接前驱和直接后继，则在双向链表中插入结点*s时指针的变化情况。操作过程可表示为： 1. s->front = p->front;
2. p->front->next = s; //或者表示为 s->front->next=s;
3. s->next=p;
4. p->front=s;

删除

在双向链表中删除结点时指针的变化情况。操作过程可表示为：
1. p->front->next = p->next; 2. p->next->front = p->front; free(p);

循环链表。在单向链表（或双向链表）的基础上令表尾结点的指针指向链表的第一个结点，构成循环链表。其特点是可以从表中任意结点开始遍历整个链表。

静态链表。借助数组来描述线性表的链式存储结构，用数组元素的下标表示元素所在结点的指针。

取值、查找、插入时间复杂度

取值

链表中逻辑相邻的结点并没有存储在物理相邻的单元中，给定的结点位置序号i，只能从链表的首元结点出发，顺着链域next逐个结点向下访问
取值算法的最坏时间复杂度是O(n)
取值算法的平均时间复杂度是O(n)

查找

查找过程与顺序表类似，从首元结点出发，依次将结点值和给定值e进行比较，返回查找结果
查找算法的平均时间复杂度是O(n)

插入

插入算法的平均时间复杂度是O(n)

优缺点

优点：插入和删除操作不需要移动大量的元素，只需要修改指针，离散的小空间分配方便，改变容量方便

缺点：不能随机访问表中的元素，存储密度低

3.1.2 栈和队列

1.栈

1.栈的定义及基本运算

定义

栈是只能通过访问它的一端来实现数据存储和检索的一种线性数据结构。只允许在一端进行插入或删除操作的线性表，栈的修改是按先进后出的原则进行的。因此，栈又称为先进后出(FILO，或后进先出）的线性表。

栈顶（Top）：线性表允许进行插入删除的那一端。
栈底（Bottom）：固定的，不允许进行插入和删除的另一端。
空栈：不含任何元素的空表。

栈进行插入和删除操作的一端称为栈顶Top，另一端称为栈底Bottom。

递归使用栈

栈的基本操作

置空栈 InitStack(S)：创建一个空栈S。

判栈空 Empty(S)：当栈S为空栈时返回真值；否则返回假值，top==0

入栈 Push(S, x)：进栈（栈的插入操作），若栈S未满，则将x加入使之成为新栈顶。

出栈 Pop(S)：将栈顶元素从栈中删除，并更新栈顶指针。若需要得到栈顶元素的值，可将 Pop(S)定义为一个函数，它返回栈顶元素的值。

读栈顶元素 Top(S)：返回栈顶元素的值，但不修改栈顶指针。

判断栈空或栈满

判断栈空的条件
初始化top=-1
top==-1

判断栈满的条件
初始化top=0
top==MaxSize

判断共享栈满的条件
初始化：0号栈栈顶top0=-1;1号栈栈顶top1=MaxSize
top0+1==top1 当0号栈进栈时top0先加1再赋值，1号栈进栈时top1先减一再赋值出栈时则刚好相反。

2.栈的存储结构

顺序存储

栈的顺序存储是指用一组地址连续的存储单元依次存储自栈顶到栈底的数据元素，同时附设指针 top 指示栈顶元素的位置。采用顺序存储结构的栈也称为顺序栈。

需要预先定义（或申请）栈的存储空间，也就是说，栈空间的容量是有限的。因此，在顺序栈中，当一个元素入栈时，需要判断是否栈满（栈空间中没有空闲单元），若栈满，则元素不能入栈。

链式存储

用链表作为存储结构的栈也称为链栈。由于栈中元素的插入和删除仅在栈顶一端进行，因此不必另外设置头指针，链表的头指针就是栈顶指针

栈的应用

栈的典型应用包括表达式求值、括号匹配等，在计算机语言的实现以及将递归过程转变为非递归过程的处理中，栈有重要的作用。

2.队列

1.队列的定义及基本运算

定义

队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。

（1）允许删除元素的一端称为队头（Front）。

（2）允许插入元素的一端称为队尾（Rear）。

（3）当队列中没有元素时称为空队列。

（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。

队列的修改是依先进先出的原则进行的。队列就像生活中排队购物，新来的人只能加入队尾（即不允许"加塞"），购物结束后先离开的总是队头（不允许中途离队），即当前"最老的"人离队。

【例】在队列中依次加入元素a1，a2，…，an之后，a1是队头元素，an是队尾元素。退出队列的次序只能是a1，a2，…，an。

队列的基本逻辑运算

置队空 InitQueue(Q)：创建一个空的队列Q

判队空 Empty(Q)：判断队列是否为空

入队 EnQueue(Q. x)：将元素x加入到队列Q的队尾，并更新队尾指针

【算法步骤】
判断队列是否为满，若满则返回ERROR
将新元素插入队尾，队尾指针加1

出队 DeQueue(Q)：将队头元素从队列Q中删除，并更新队头指针

【算法步骤】
判断队列是否为空，若空则返回ERROR
保存队头元素，队头指针加1

读队头元素 Frontque(Q)：返回队头元素的值，但并不更新队头指针

判断队列是否已满

(队尾+1) % 数组长度 = 队头（其实是有一个空余位置，只是为了计算方便这个位置不使用）

计算队列有效数据个数

队列中存在一种特殊情况：循环队列，一般定义循环队列的头指针front和尾指针rear均指向队列下标为0的位置，此时front=rear&l=0;

在循环队列中插入元素，若队列未满（l<n）尾指针后移一位（rear++）;

若队列已满（l==n）,则不能继续插入元素，应返回错误提示。

由于队列元素的删除等操作，头指针向后移动（front>0），当尾指针的移动至下标为n-1的位置时，队列未满，因此在循环队列中会出现rear<front的情况，因此在计算队列的长度时不能直接使用l=rear-front。为了避免出现计算错误，通过在公式中加入一个n并对n取模的办法来合并所有的队列情况，得到l=(rear-front+n)%n通用计算公式。

2.队列的存储结构

顺序表存储

顺序队列

队列的顺序存储结构又称为顺序队列，它也是利用一组地址连续的存储单元存放队列中的元素。由于队列中元素的插入和删除限定在表的两端进行，因此设置队头指针和队尾指针，分别指出当前的队头和队尾。

设顺序队列Q的容量为6，其队头指针为 front，队尾指针为 rear，头、尾指针和队列中元素之间的关系

在顺序队列中，为了降低运算的复杂度，元素入队时只修改队尾指针，元素出队时只修改队头指针。由于顺序队列的存储空间容量是提前设定的，所以队尾指针会有一个上限值，当队尾指针达到该上限时，就不能只通过修改队尾指针来实现新元素的入队操作了。若再有元素入队，就会发生“溢出”。

循环队列

若将顺序队列假想成一个环状结构（通过整除取余运算实现)，则可维持入队、出队操作运算的简单性，称之为循环队列

设循环队列Q的容量为 MAXSIZE，初始时队列为空，且 Q.rear 和 Q.front 都等于0

元素入队时，修改队尾指针Q.rear = (Q.rear+1)% MAXSIZE

元素出队时，修改队头指针Q.front =(Q.front+1)% MAXSIZE

根据队列操作的定义，当出队操作导致队列变为空时，则有 Q.rear==Q.front

若入队操作导致队列满，则 Q.rear==Q.front

链式存储

也称为链队列，这里为了便于操作，给链队列添加一个头结点，并令头指针指向头结点。因此，队列为空的判定条件是头指针和尾指针的值相同，且均指向头结点。

插入元素

删除元素

优缺点

优点

相比普通的队列，元素出队时无需移动大量元素，只需移动头指针。
可动态分配空间，不需要预先分配大量存储空间。
适合处理用户排队等待的情况。

缺点

需要为表中的逻辑关系增加额外的存储空间。

时间复杂度

读取时的时间复杂度为O(1)
插入、删除时的时间复杂度为O(1)

顺序队列和链式队列的比较

顺序队列是用数组实现的，首指针在出队的时候移动，尾指针在入队的时候移动，需要考虑队列为空和队列为满的两种情况

链式队列是用链表实现的，首指针不移动始终指向头节点，尾指针在入队的时候移动，只考虑队列为空的情况（不用考虑满是因为链表长度在程序运行过程中可以不断增加，只要存储空间够malloc就能申请内存空间来存放节点）

队列的应用

队列结构常用于处理需要排队的场合，例如操作系统中处理打印任务的打印队列、离散事件的计算机模拟等。

3.1.3 串

1.串的定义及基本运算

定义

串是由零个或多个字符组成的有限序列。在计算机科学中，常用串来表示文本、代码或数据。串是程序设计中重要的基本数据类型之一，常用于字符串匹配、文本处理和密码学等领域。

基本概念

(1) 空串：长度为零的串，表示为 ""（两个引号之间没有任何字符）。
(2) 空格串：只包含空格字符的字符串，例如 " "。
(3) 子串：由串中任意长度的连续字符构成的序列。含有子串的串称为主串，子串在主串中的位置指子串首次出现时，该子串的第一个字符在主串中的位置。空串是任意串的子串。例如，在字符串 "hello world" 中，"hello"、"world"、"lo"、"l"、"rld" 都是它的子串。
(4) 串相等：指两个串长度相等且对应位置上的字符也相同。
(5) 串比较：两个串比较大小时以字符的 ASCIL 码值作为依据。比较操作从两个串的第一个字符开始进行，字符的 ASCII 码值大者所在的串为大；若其中一个串先结束，则以串长较大者为大。

基本操作

串和线性表的关系

串是一种数据对象和操作都特殊的线性表，数据元素之间呈线性关系

串的数据对象限定为字符集（如中文字符、英文字符、数字字符、标点字符等）

串的基本操作，如增删改查等通常以子串为操作对象（C++ 中的 String）

串的基本操作

(1) 赋值操作 StrAssign(s, D)：将串t的值赋给串S。
(2) 连接操作 Concat(s,t)：将串t接续在串、的尾部，形成一个新串。
(3) 求串长 StrLength(s)：返回串s的长度。
(4) 串比较 StrCompare(s, b)：比较两个串的大小。
(5) 求子串 SubString(s, start, len)：返回串s中从 start 开始的、长度为len 的字符序列。

字符集编码

编码

任何数据存到计算机中定是二进制数。需要确定一个字符和二进制数的对应规则这就是“编码”

ASCII 码

字符集

英文字符 —— ASCII字符集
中英文 —— Unicode 字符集（基于同一个字符集，可以有多种编码方案，如：UTF-8，UTF-16）
注：采用不同的编码方式，每个字符所占空间不同，只需默认每个字符占 1B 即可

2.串的存储结构

串的静态存储：定长存储结构
串的顺序存储结构是用一组地址连续的存储单元来存储串值的字符序列。由于串中的元素为字符，所以可通过程序语言提供的字符数组定义串的存储空间，也可以根据串长的需要动态申请字符串的空间。

串的链式存储：块链
串也可采用链表方式作为存储结构，当用链表存储串中的字符时，每个节点中可以存储一个字符，也可以存储多个字符，要考虑存储密度的问题。在链式存储结构中，节点大小的选择和顺序存储方法中数组空间大小的选择一样重要，它直接影响对串处理的效率。

3.串的模式匹配
在主串中找到与模式串相同的子串，并返回其所在位置。它是各种串处理系统中最重要的运算之一,子串也称为模式串。

朴素的模式匹配算法—暴力匹配算法（Brute-Force）：这是一种简单直接的模式匹配算法。
从主串的第一个字符开始，逐个比较主串和模式串的对应字符。
如果某个字符不匹配，则主串和模式串的指针分别回溯到下一个位置再进行比较。
如果模式串的指针达到末尾，表示匹配成功，返回匹配的起始位置。
如果主串的指针达到末尾仍未匹配成功，则表示匹配失败。

步骤

假设主串S=“goodgoogle”，子串T=“google”，在主串中找到子串的位置。

(1) 从主串S的第一位开始，S与T的前三位都匹配成功，第四位匹配失败，此时将主串的指针退回到第二位，子串的指针退回子串开始，即从S[1]开始重新匹配。

(2) 主串S从第二位开始于子串T匹配，第（1）步就匹配失败，将主串指针指向第三位S[2]，子串指针指向开头，继续匹配。

(3) 同步骤（2），第（1）步就匹配失败，将主串指针移动到第四位S[3]，子串指针指向开头，继续匹配。

(4) 还是第（1）步就匹配失败，将主串指针移动到第五位S[4]，子串指针指向开头，继续匹配。

(5) 到步骤（5）终于第一步能够匹配上，从S[4]开始指针依次向后移动，六个字母全部匹配上，匹配成功

时间复杂度

最好情况，时间复杂度为O(m+n)(m为子串长度)；

最坏的情况就是每次不成功的匹配都发生在子串末尾，主串为S=“00000000000000000000000000000000000000000000000001”，子串为T=“0000000001”，推导可得此时的时间复杂度度为O((n-m+1)*m)=O(n*m)(n为主串长度)。

平均情况O(n+m),m是模式串，n是主串。

改进优化的模式匹配算法—KMP算法（Knuth-Morris-Pratt）：
KMP算法利用模式串中的匹配信息，避免不必要的回溯。
具体来说，KMP算法通过构建一个模式串的部分匹配表，即next数组。
next数组保存了模式串中不匹配时，应该回溯的位置。
在匹配过程中，当某个字符不匹配时，根据next数组的值进行指针的调整。
这样可以使得模式串指针不回溯到之前已经比较过的位置，提高匹配效率。

前缀表是一张表(一个数组)，表中记录的是字符串中的每个子串的最大相等前后缀的长度，前缀表决定了子串指针j在匹配失败时回溯到的位置，是用来回退的，它记录了模式串与主串(文本串)不匹配的时候，模式串应该从哪里开始重新匹配。

3.2 数组、矩阵和广义表

3.2.1 数组

1.数组的定义及基本运算

定义

数组是定长线性表在维数上的扩张，即线性表中的元素又是一个线性表。n维数组是一种“同构”的数据结构，其每个元素类型相同、结构一致。

以二维数组A[m,n]为例

行向量形式的线性表

列向量形式的线性表

特点

数据元素数目固定；

数据元素具有相同的类型；

数据元素的下标关系具有上下界的约束且下标有序。

数组的基本运算

给定一组下标，存取相应的数据元素。

给定一组下标，修改相应的数据元素中某个数据项的值。

2.数组的顺序存储

定义

一旦定义了数组，结构中的数据元素个数和元素之间的关系就不再发生变动，因此数组适合于采用顺序存储结构。

存储方式

由于计算机的内存结构是一维线性的，因此存储多维数组时必须按照某种方式进行降维处理，即将数组元素排成一个线性序列，这就产生了次序约定问题。

以行为主序的存储方式

以列为主序的存储方式

地址计算方式

3.2.2 矩阵

1.特殊矩阵（若矩阵中元素（或非0元素）的分布有一定的规律，则称之为特殊矩阵。）

分类

对称矩阵

第一行： 1 个元素
第二行： 2 个元素
第三行： 3个元素
.....
第n行: n 个元素
等差数列，等差数列求和公式: 总数 = (a1+an)n/2

求 ai,j 前共有多少个元素

下标从0开始

下标从1开始

对角矩阵

2.稀疏矩阵（在一个矩阵中，若非0元素的个数远远少于0元素的个数，且非0元素的分布没有规律，则称之为稀疏矩阵。）

稀疏矩阵的三元组表的顺序存储结构称为三元组顺序表，常用的三元组表的链式存储结构是十字链表

3.2.3 广义表

广义表与线性表的区别

线性表的元素都是结构上不可分的单元素

广义表的元素既可以是单元素，也可以是有结构的表。

广义表的定义

广义表一般记作：
LS=(a1,a2,.....an)，其中LS是广义表(a1,a2,.....an)的名称，n是其长度。在广义表的定义中，ai可以是单个元素，也可以是广义表，分别称为广义表LS的原子和子表。习惯上，用大写字母表示广义表的名称，用小写字母表示原子(广义表中的数据元素通常采用链式存储结构)。

下面列举一些广义表的例子：
(1) A=( ) A是一个空表，其长度为零。
(2) B=(e) B只有一个原子e，其长度为1.
(3) C=(a,(b,c,d)) C的长度为2，两个元素分别为原子a和子表(b,c,d)。
(4) D=(A,B,C) D的长度为3,3个元素都是广义表。显然，将子表的值代入后，则有D=(( ),(e),(a,(b,c,d)))
(5) E=(a,E) 这是一个递归的表，其长度为2。E相当于一个无限的广义表 E=(a,(a(a,.......)))。
(6) L=(a,(b,c,d)) L的表头是a, 表尾是 ((b,c,d))。

广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（）. Head(Tail(Head(Tail(Tail(A)))))

第一步： Tail(A)：(b,(c,d),(e,(f,g)))
第二步：Tail(Tail(A)) ： ((c,d),(e,(f,g)))
第三步： Head(……) ： (c,d)
第四步： Tail(……) ： (d)
第五步： Head(……) ： d

广义表的深度和长度

深度：观察括号的层数；长度：广义表中所包含的数据元素的个数

广义表 ( (a),((b),j,(((d)))) )的长度为 2，深度为 5

广义表A=( a,(a,b),((a,b),c) )，则它的深度为 3,它的长度为 3。

广义表的基本操作

（1）GetHead(LS)（取表头）：取出的表头为非空广义表的第一个元素，可以是一个单原子，也可以是一个子表。

（2）GetTail(LS)（取表尾）：取出的表尾为除去表头之外，由其余元素构成的表。即表尾一定是一个广义表，记得加（）。

广义表的特点

广义表的存储结构

3.3 树

3.3.1 树与二叉树的定义

1.树的定义及基本概念

定义

树是(n≥0)个节点的有限集合，n=0 时称为空树。在任一非空树(n>0)中：
(1) 有且仅有一个称为根的节点。
(2) 其余的节点可分为m(m≥0)个互不相交的有限子集T1，⋯，Tm，其中每个子集本身又是一棵树，并称其为根节点的子树。
树的递归定义表明了树的固有特性，也就是一棵树由若干棵子树构成，而子树又由更小的子树构成。

基本概念

(1) 双亲和孩子。结点的子树的根称为该节点的孩子；该节点称为其子节点的双亲。
(2) 兄弟。具有相同双亲的结点互为兄弟。
(3) 结点的度。一个结点的子树的个数记为该结点的度。例如 A 结点有2个子树，度为2。
(4) 叶子结点。也称为终端结点，指度为零的结点。
(5) 内部结点。度不为零的结点称为分支结点或非终端结点。除根结点之外，分支结点也称为内部结点。
(6) 结点的层次。根为第一层，根的孩子为第二层，以此类推。
(7) 树的高度。一棵树的最大层次数记为树的高度(或深度)。当前树的最大层数是4，所以树的高度是4。
(8) 结点的度。若将树中的结点的各子树看成是从左到右具有次序的，即不能交换，则称该树为有序树；否则称为无序树。
(9) 森林。是m(m≥0)棵互不相交的树的集合。

2.树的性质

1.树中的结点数=所有节点度数+1

每个节点的度数分别对应节点的子节点，设所有节点的度数为 d，总结点数为n，则 n = d + 根节点，即 n = d + 1

设总结点数为n，树中除根节点外，每个节点都对应一个分支，因此树中总分支数为 n - 1

假设分支节点有 nk 个，n = nk* k + 1; nk=>(n-1)/k n0=n-nk=n-(n-1)/k=(nk-n+1)/k
假设叶子节点有 n0 个，n = nk + n0; （分支节点不包含叶子节点，节点总数 = 分支节点数 + 叶子节点数）

2.度为m的树与m叉树的区别

3.度为m的树：树中结点的度的最大值为m
每个结点的度都为m，则第 i 层上至多有 m 的 i-1 次方个结点

5.高度为h、度为m的树至少有h+m-1个结点，高度为h的m叉树至少有h个结点

3.二叉树的定义

定义

二叉树(Binary Tree)是 n(n≥0)个节点的有限集合，它或者是空树(n=0)，或者是由一个根节点及两棵互不相交的且分别称为左子树和右子树的二叉树所组成。

二叉树与树的区别

二叉树的结点的子树要区分左子树和右子树，即使在结点点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。

二叉树的结点的最大度为2，而树中不限制节点的度数。

满二叉树和完全二叉树

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为k，且结点总数是(2^k) -1 ，则它就是满二叉树。

一颗树深度为h，最大层数为k，深度与最大层数相同k=h;

叶子数是： 2^h 第k层的结点数是： 2^(k-1) 总结点数是： 2^k-1 (2的k次方减1) 总结点数一定是奇数。

完全二叉树的结点数是任意的，从形式上讲它是个缺失的的三角形，但所缺失的部分一定是右下角某个连续的部分，最后那一行可能不是完整的，对于k层的完全二叉树，节点数的范围2^ (k - 1) -1 < N< 2^k - 1;

除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边

3.3.2 二叉树的性质与存储结构

1.二叉树的性质

2.二叉树的存储结构

1）顺序存储结构

二叉树的顺序存储结构方法是将二叉树的所有结点，按照一定的线性次序存储到连续的存储单元中，使得结点在这个序列中的相互位置能反映出结点之间的逻辑关系。需要维护结点和左、右孩子的关系：结点编号为n，则左孩子为 2n，右孩子为2n+ 1。

完全二叉树的顺序存储结构

在一棵具有n 个结点的完全二叉树中，从树根起，自上而下,逐层从左到右给所有结点编号，就能得到一个反映整个二叉树结构的线性序列．其中，每个结点的编号就作为结点的名称。

将数组下标作为结点名称(编号),就可将二叉树中所有结点的标号存储在一个一维数组中。

一般二叉树的顺序存储结构

对于一般的二叉树采用顺序存储时，为了能用结点在数组中的位置来表示结点之间的逻辑关系，也必须按近似满二叉树的形式来存储树中的结点。

在最坏情况下，一个深度为k且只有k个结点的单支树却需要长度为2^k-1的一维数组。

对比

对于完全二叉树而言，顺序结构既简单又节省存储空间；对于一般的二叉数，顺序结构将造成存储空间的浪费，顺序结构适用于完全二叉树，一般二叉树更适合使用链式存储结构。

2）链式存储结构

设计不同的结点结构可构成不同形式的链式存储结构。由二叉树的定义得知，二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支构成

结点结构至少包括：lchild左孩子指针域、data数据域和rchild右孩子指针域。

链表的头指针指向二叉树的根结点，在含有n个结点的二叉链表中有n+1个空链域。

为了便于找到结点的双亲，还可在结点结构中增加一个指向其双亲结点的指针域

n个结点的三叉链表n+2个空指针域

3.3.3 二叉树的遍历

定义

顺着一条搜索路径访问二叉树中的结点，每个结点均被访问一次，且只被访问一次。

目的

得到树中所有节点的一个线性排列

用途

是二叉树元素增删改查等操作的前提

求遍历序列（遍历二叉树比作开门）

先序遍历DLR

先序序列为ABDCEF

中序遍历LDR

中序序列为DBAECF

后序遍历LRD

后序序列为DBEFCA

根据遍历序列确定二叉树

根据先序序列和中序序列确定二叉树

已知二叉树的先序和中序序列，构造出相应的二叉树
先序：A B C D E F G H I J
中序：C D B F E A I H G J

由先序序列确定根，由中序序列确定左右子树

1、由先序知根为A，则由中序知左子树CDBFE，右子树IHGJ

2、再分别在左、右子树的序列中找出根、左子树、右子树序列

3、以此类推，直到得到二叉树

根据后序序列和中序序列确定二叉树

已知一颗二叉树的中序序列和后序序列分别是BDCEAFHG和DECBHGFA，请画出这两棵二叉树。

1、由后序遍历特征,根结点必在后序序列尾部，即根结点是A;

2、由中序遍历特征，根结点必在其中间,而且其左部必全部是左子树子孙(BDCE),其右部必全部是右子树子孙(FHG)；

3、继而,根据后序中的 DECB 子序列可确定B为 A的左孩子,根据 HGF 子序列可确定F为A的右孩子;依此类推,可以唯一地确定一棵二叉树

3.3.4 线索二叉树

线索二叉树

定义

若n个结点的二叉树采用链表作存储结构，则链表中含有 n+1 个空指针域，利用这些空指针域来存放指向结点的前驱和后继信息。若二叉树的二叉链表采用所示的结点结构，则相应的链表称为线索链表，其中指向节点前驱、后继的指针称为线索，加上线索的二叉树称为线索二叉树。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。

1.中序遍历二叉树，序列是：BCADE

2.找出没有右孩子的结点，并标出

3.在没有右孩子的结点处连上后继

平衡二叉树

定义

平衡二叉树，称AVL树，它或者是一棵空树，或者是具有以下性质的二叉树：它的左子树和右子树都是平衡树，且左子树和右子树的深度之差的绝对值不超过1

平衡因子:又称BF，定义为该结点的左子树的深度减去它的右子树深度。则平衡二叉树的所有结点的平衡因子只可能是-1、0、1。只要二叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。

二叉排序树

定义

二叉排序树，又称二叉查找树。或者是一棵空树，或者是满足以下性质的二叉树：
1、若其左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2、若其右子树不空，则右子树上所有结点的值均大于它的根结点的值
3、其左、右子树也分别为二叉排序树

特点

二叉排序树的中序遍历序列一定是递增有序的

作用

可用于元素的排序和搜索

构造二叉排序树

设输入序列为：（30,11,18,4,55,19,15,70,58）

例：设输入关键字序列为:58,60,15,80,19,55,4,18,70,11,30,
生成二叉排序树,试画出二叉排序树;假定查找每个结点
(关键字)的概率相同,计算查找成功时的平均查找长度ASL。

最坏的查找情况是单枝树（即高度ℎ为n）要查找ℎ

3.3.5 最优二叉树

1.最优二叉树（哈夫曼树）

定义

哈夫曼树：给定n个权值作为n个叶子结点，构造一棵二叉树，若该树的带权路径长度(wpl)达到最小，称这样的二叉树为最优二叉树，也称哈夫曼树。

路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

路径长度：路径上的分支数目称作路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为 L-1

路径长度 3 - 1 = 2 结点的权13 结点带权路径长度13(权) x 2(路径长度) = 26

树的路径长度：从树根到每一结点的路径长度之和。

权：赋予某个实体的一个量，是对实体的某个或某些属性的数值化描述。在数据结构中,实体有结点(元素）和边(关系）两大类，所以对应有结点权和边权。如果在一棵树中的结点上带有权值，则对应的就有带权树等概念。

结点的权：若将树中结点赋给一个有某种意义的数值，则这个数值称为该结点的权。

结点带权路径长度：从根结点到该结点之间的路径长度与该结点的权的乘积。

树的带权路径长度：所有叶子结点的带权路径长度之和，记为WPL（weighted path length）,权值越大的结点离根结点越近的二叉树才是最优二叉树

特点

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近，权值越小的结点离根结点越远。

性质

创建哈夫曼树

例如: 已知权值 W = {2,5,9,6,7},请构造哈夫曼树.

相同的权值构造出来的哈夫曼树形态不唯一

2.哈夫曼编码

定义

又称霍夫曼编码，是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）

哈夫曼编码是哈夫曼树在电讯通信中经典的应用之一。在电讯通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。

是一种高效的编码方式，在信息存储和传输过程中用于对信息进行压缩。广泛地用于数据文件压缩的十分有效的编码方法,其压缩率通常在20%～90%之间。

设计编码规则

在电文传输中，需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则：
（1）发送方传输的二进制编码，到接收方解码后必须具有唯一性，即解码结果与发送方发送的电文完全一样；
（2）发送的二进制编码尽可能地短。

1. 等长编码
这种编码方式的特点是每个字符的编码长度相同（编码长度就是每个编码所含的二进制位数）。译码简单且具有唯一性，但编码长度并不是最短的。

假设字符集只含有4个字符A，B，C，D，用二进制两位表示的编码分别为00，01，10，11。若现在有一段电文为：ABACCDA，则应发送二进制序列：00010010101100，总长度为14位。当接收方接收到这段电文后，将按两位一段进行译码。

能否使编码总长度更短呢？

实际应用中各字符的出现频度不相同，用短（长）编码表示频率大（小）的字符，使得编码序列的总长度最小，使所需总空间量最少。

2. 不等长编码
在传送电文时，为了使其二进制位数尽可能地少，可以将每个字符的编码设计为不等长的，使用频度较高的字符分配一个相对比较短的编码，使用频度较低的字符分配一个比较长的编码。

例如，若假设可以为A，B，C，D四个字符分别分配编码0，00，1，01，则电文 ‘ABACCDA’ 便为 ‘000011010’（共 9 位），并可将上述电文用二进制序列：000011010发送，其长度只有9个二进制位，但此编码存在多义性，可译为： ‘BBCCDA’、‘ABACCDA’、‘AAAACCACA’ 等。

数据的最小冗余编码问题
在上例中，随之带来了一个问题，接收方接到这段电文后无法进行译码，因为无法断定前面4个0是4个A，1个B、2个A，还是2个B，即译码不唯一，因此这种编码方法不可使用。

译码的唯一性问题
因此，为了设计长短不等的编码，以便减少电文的总长，还必须考虑编码的唯一性，即在建立不等长编码时要求任一字符的编码都不能是另一字符编码的前缀，这种编码称为前缀编码（其实是非前缀码）。在编码过程要考虑两个问题，数据的最小冗余编码问题，译码的唯一性问题，利用哈夫曼树可以很好地解决上述两个问题，由哈夫曼树得到的二进制前缀编码称为哈夫曼编码。

（1）利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树；
（2）从根结点开始，为到每个叶子结点路径上的左分支赋予0，右分支赋予1，并从根到叶子方向形成该叶子结点的编码。

用二叉树设计二进制前缀编码

以电文中的字符作为叶子结点构造二叉树。然后将二叉树中结点引向其左孩子的分支标 ‘0’，引向其右孩子的分支标 ‘1’；每个字符的编码即为从根到每个叶子的路径上得到的 0, 1 序列。如此得到的即为二进制前缀编码。任意一个叶子结点都不可能在其它叶子结点的路径中。

用哈夫曼树设计总长最短的二进制前缀编码

假设各个字符在电文中出现的次数（或频率）为 wi ，其编码长度为 li，电文中只有 n 种字符。设计电文总长WPL最短的编码，设计哈夫曼树（以 n 种字符出现的频率作权），由哈夫曼树得到的二进制前缀编码称为哈夫曼编码。

编码例：如果需传送的电文为 ‘ABCACCDAEAE’，即：A, B, C, D, E 的频率（即权值）分别为0.36, 0.1, 0.27, 0.1, 0.18，试构造哈夫曼编码。

译码
从哈夫曼树根开始，对待译码电文逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到电文结束。

3.3.6 树和森林

1.树的存储结构

树的双亲表示法

定义

以双亲作为索引的关键词的一种存储方式，每个结点只有一个双亲，所以选择顺序存储占主要以一组连续空间存储树的结点，同时在每个结点中，附设一个指示其双亲结点位置的指针域。如果结点是根结点，则其父指针为-1。

结点结构

优缺点分析

优点：parent指针域指向数组下标，所以找双亲结点的时间复杂度为O(1),向上一直找到根节点也快

缺点：由上向下找就十分慢，若要找结点的孩子或者兄弟，要遍历整个树

孩子表示法

定义

采用多重链表，每个结点有多个子树（无法确定子树个数，指针域），每个指针指向一棵子树的根结点。

结点结构

优缺点分析

优点：可以有效地表示每个结点的子结点

缺点：当结点的度数差异较大时，会造成空间的浪费，占用了大量不必要的孩子域空指针

孩子兄弟表示法

定义

一种将树结构转换为二叉树结构的方法。在这种二叉链表表示法中，每个结点有两个指针，一个指向其第一个子结点，另一个指向其右侧兄弟结点。

优缺点分析

优点：可以方便地找到结点的子结点和兄弟结点

缺点：如果需要找到结点的父结点，则可能需要遍历整棵树

树的双亲孩子表示

定义

双亲表示法和孩子表示法的结合。在这种表示法中，每个结点既有指向父结点的指针，也有指向其子结点链表的头指针。

优势

既可以快速找到结点的父结点，也可以快速访问其子结点。

2.树和森林的遍历

树的遍历

先根遍历，先访问树的根结点，然后再依次先根遍历根的每棵子树

先根遍历结果为 A ==> B ==> E ==> F ==> C ==> G ==> D ==> H ==> I ==> J

后根遍历，先依次遍历每棵子树，然后再访问根结点

后根遍历结果为 E ==> F ==> B ==> G ==> C ==> H ==> I ==> J ==> D ==> A

森林的遍历

3.树、森林和二叉树之间的相互转换

树、森林转换为二叉树

树转换为二叉树

树 --> 二叉树步骤
（1）将树中每个相邻的兄弟进行连线；
（2）将每个结点除第一个孩子以外，断开其他兄弟与其双亲结点的连线；
（3）适当旋转处理完后的树，使其呈现二叉树的形式。

第一步：给所有的兄弟结点加线，即兄弟相连；

第二步：把除了长子以外的线全部删除；

第三步：调整层次关系，注意第一个孩子（即长子）是二叉树的左子树，之前的兄弟结点是长子的右孩子

森林转换为二叉树

森林 --> 二叉树步骤
（1）将森林的每个树转换为二叉树；
（2）将每个二叉树按照原顺序将其根节点通过右孩子依次连接，变成一整个二叉树。

第一步：将森林中的每棵树变为二叉树，方式和我们之前实现的方式是一致的

第二步：将它们的根结点依次连在一起

第三步：调整层次位置

二叉树转换为树和森林（判断一棵二叉树能够转换成一棵树还是森林，标准很简单，那就是只要看这棵二叉树的根结点有没有右孩子，有的话就是森林，没有的话就是一棵树）

二叉树转换为树

二叉树 --> 树步骤
（1）每个结点的左孩子的右孩子全部连至左孩子的双亲结点；
（2）删除原来所有与右孩子相连的线（也就是之前到逆向）；
（3）调整层次关系。

第一步：每个结点的左孩子的右孩子全部连至左孩子的双亲结点

第二步：删除原来所有与右孩子相连的线

第三步：调整层次关系

二叉树转换为森林

二叉树 --> 森林步骤
（1）断开二叉树根结点沿右下方孩子结点所有的连线，分成多个二叉树；
（2）将每个二叉树转换为树，形成森林。

第一步，若结点 x 是其双亲 y 的左孩子，则把 x 的右孩子，右孩子的右孩子等等，依次都与 y 连接起来

第二步：去掉所有双亲到右孩子之间到连线

第三步：调整层次

3.4 图

3.4.1 图的定义与存储

1.图的定义

图(Graph)G 由V 和E两个集合组成，记为G=(V,E)。其中V是顶点的有穷非空集合，E是V中顶点偶对的有穷集合，这些顶点偶对称为边。通常，也将图G 的顶点集合和边集合分别记为V(G)和 E(G)。E(G)可以是空集，此时图G 中只有顶点而没有边。

有向图、无向图

有向图

若图G 中的每条边都是有方向的,则称G 为有向图。在有向图中，顶点对<x,y>是有序的，它称为从顶点x到顶点y的一条有向边。因此，<x,y>和<y,x>是不同的两条边。顶点用一对尖括号括起来，x是有向边的始点，y是有向边的终点，<x,y>也称作一条弧，x为弧尾，y为弧头。

无向图

若图G中的每条边都是没有方向的，则称G 为无向图。在无向图中，顶点对(x,y）是无序的，它称为顶点x和顶点y相关联的一条边。这条边没有特定的方向，在无向图中(x,y）和(y,x)是同一条边。顶点用一对圆括号括起来。

无论是无向图还是有向图，顶点数为n，边数为e，则所有顶点的度数之和为2e

完全图

无向完全图

对于含有n个顶点的无向图,若具有n(n-1)/2条边，称为无向完全图。

有向完全图

对于含有n个顶点的有向图,若具有n(n-1)条弧，则称为有向完全图。

顶点的度、入度、出度

无向图

顶点v的度是指依附于该顶点的边的条数，记为TD(v)

有向图

入度是以顶点v为终点的有向边的数目，记为ID(v)

出度是以顶点v为起点的有向边的数目，记为OD(v)

顶点v的度等于其入度和出度之和，即TD(v) = ID(v) + OD(v)

路径、路径长度和回路

路径长度——路径上边的数目。

回路——第一个顶点和最后一个顶点相同的路径称为回路或环。

子图

图的一部分

连通、连通图、连通分量（针对无向图）

若从顶点v到顶点w有路径存在，则称v和w是连通的。

若图中任意两个顶点都是连通的，则称为连通图，否则称为非连通图。

连通分量

无向图的极大连通子图（要求该连通子图包含所有的边）

强连通图、强连通分量（针对有向图）

若从顶点v到顶点w有路径存在，则称v和w是强连通的。

若图中任意两个顶点点都是强连通的，则称为强连通图，否则称为非强连通图。

强连通分量：有向图中的极大强连通子图

稠密图、稀疏图

边数很少称为稀疏图，反之称为稠密图。

边的权和网

边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。

带权图/网——边（或弧）上带有权值的图称为带权图，也称网。

带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。

生成树、生成森林

一个极小连通子图,它含有图中全部顶点，但只有足以构成一棵树的n-1条边,这样的连通子图称为连通图的生成树。若图中顶点数为n，则它的生成树含有n-1条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。

在非连通图中，连通分量的生成树构成了非连通图的生成森林。

有向树

一个顶点的入度为0、其余顶点的入度均为1的有向图，称为有向树。

简单路径、简单回路

简单路径

在路径序列中，顶点不重复出现的路径称为简单路径。

简单回路

除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。

距离

顶点之间的最短路径长度，若不存在通路记距离为无穷。

2.图的存储结构

邻接矩阵表示法

邻接矩阵更适合存储稠密图（边数很多的图）

完全图（每个顶点都和剩余的顶点有一条边）更适合采用邻接矩阵存储

优缺点

优点

便于判断两个顶点之间是否有边，即根据A[i][j]=0或1来判断。

A[i][j]=1表示顶点i和顶点j之间有一条无向边

A[i][j]=0表示顶点i和顶点j之间没有边

便于计算各个顶点的度

对于有向图，第i行元素之和就是顶点i的出度，第i列元素之和就是顶点i的入度。

对于无向图，邻接矩阵第i行元素之和就是顶点i的度

缺点

邻接链表表示法

有向图

有向图采用邻接表存储有 n+e 个表结点（n 为结点数，e 为边数）

无向图

无向图采用邻接表存储有 2e 个表结点（e 为边数）

邻接表更适合存储稀疏图（边数很少的图）

优缺点

优点

1、便于增加和删除顶点
2、便于统计边的数目，按顶点表顺序扫描所有边表可得到边的数目。
3、空间效率高。对于一个具有n个顶点e条边的图G,若G 是无向图，则在其邻接表表示中有n个顶点表结点和 2e 个边表结点;若G是有向图，则在其邻接表表示中有 n 个顶点表结点和。个边表结点。因此,邻接表表示的空间复杂度为 O(n十e),适合表示稀疏图。

缺点

1、不便于判断顶点之间是否有边
2、不便于计算有向图各个顶点的度

3.4.2 图的遍历

1.图的深度优先遍历（DFS）

定义

沿着一条路径一直搜索下去，在无法搜索时，回退到刚刚访问过的节点。

深度优先遍历（DFS，Depth-First Search）是一种图遍历算法，它沿着图的深度方向进行搜索。DFS 从一个起始节点开始，优先访问未被访问的邻接节点，尽可能深地探索每个分支，直到所有可能的分支都被访问过，然后回溯到上一个节点继续探索。类似于树的先序遍历，是树的先序通历的推广。

遍历过程

对于一个连通图，深度优先遍历的过程如下：
(1)从图中某个顶点 V出发,访问V。
(2)找出刚访问过的顶点的第一个未被访问的邻接点，访问该顶点，以该顶点为新顶点，重复此步骤，直至刚访问过的顶点没有未被访问的邻接点为止。
(3)返回前一个访问过的且仍有未被访问的邻接点的顶点，找出该顶点的下一个未被访问的邻接点，访问该顶点。
(4)重复步骤(2)和(3)，直至图中所有顶点都被访问过,遍历结束。

深度优先遍历的过程体现出后进先出的特点：用栈或递归方式实现。

空间、时间复杂度分析

采用邻接矩阵表示

空间复杂度

由于DFS需要一个递归工作栈，最差的情况是如图所示。当从第一个节点开始遍历时，先访问它，修改它的访问标记。然后找到它的第一个邻居（把它的邻居称为a），访问a，修改a的访问标记。

从a找到a的邻居（称为b），访问b，修改b的访问标记，...，依次递归，每个节点都需要进入函数调用栈，最深的函数栈层数为n，故其空间复杂度为O(n-1)~O(n)。

时间复杂度

时间复杂度为非两个部分：a：访问每个节点花费的时间 b：在每个节点找邻居花费的时间。
a：n个节点需要O(n)；
b：由于是邻接矩阵，对于节点i，需要扫描第i行的每一个元素，需要O(n)；
总的复杂度O(n^2)。

采用邻接表表示

空间复杂度

同邻接矩阵的分析

时间复杂度

时间复杂度分为两个部分：a：访问每个节点花费的时间 b：在每个节点找邻居花费的时间。
a：n个节点需要O(n)；
b：采用邻接表，总共的找邻居时间复杂度就是遍历边表的时间复杂度。对于有向图：O(e)，对于无向图O(2e)~O(e)（取最高阶）;
总的复杂度O(n+e)。

查找思路

2.图的广度优先遍历（BFS）

定义

所谓广度，就是一层一层的，向下遍历，层层堵截

广度优先遍历（BFS，Breadth-First Search）是一种图遍历算法，它沿着图的广度方向进行搜索。BFS 从一个起始节点开始，逐层访问所有邻接节点，然后继续访问这些邻接节点的邻接节点，直到图中的所有节点都被访问过。与层次遍历类似，因为它们都按层次访问图中的节点，逐层展开，直到遍历完整个图。

遍历过程

广度优先搜索遍历的过程如下：
(1)访问顶点vi ;
(2)访问vi 的所有未被访问的邻接点w1 ,w2 , …wk ;
(3)依次从这些邻接点(在步骤(2)中访问的顶点)出发，访问它们的所有未被访问的邻接点; 依此类推，直到图中所有访问过的顶点的邻接点都被访问;

广度优先遍历的过程用队列方式实现

空间、时间复杂度分析

采用邻接矩阵表示

空间复杂度

无论是邻接表还是邻接矩阵，BFS算法需要借助一个辅助队列，在最坏的情况下（如下图从中心节点出发），n个顶点需全入队一次，空间复杂度O(n)；

时间复杂度

采用邻接表表示

空间复杂度

同邻接矩阵的分析

时间复杂度

查找思路

深度优先遍历
v1 到 v2， v2 并没有有向边到v3，因此 1 不是深度优先遍历
v1 到 v3, v3到v4, v4 到 v5，此时 v5 已经没有邻接节点，返回到v4，v4 没有可访问的邻接节点返回到v3， v3没有可访问的邻接节点，返回到v1，v1 访问v2

广度优先遍历
依照广度优先遍历的特点，从v1 出发会先将邻接节点 v2 v3 遍历完
v1 v2 v3
v1 v3 v2

3.4.3 生成树及最小生成树

1.生成树的概念

概念

一个有n个顶点的连通图（如果图中任意两点都是连通的，那么图被称作连通图。如果此图是有向图，则称为强连通图（注意：需要双向都有路径））的生成树是该图的一个极小连通子图,它含有图中全部顶点,和构成一棵树的(n-1)条边。

若在一棵生成树上添加任何一条边,必定构成一个环,因为这条边使得它依附的那两个顶点之间有了第2条路径。

一棵有n个顶点的生成树(连通无回路图)有且仅有(n-1)条边,但是,有(n-1)条边的图不一定都是生成树。如果一个图有n个顶点和小于(n-1)条边,则是非连通图;如果它有多于(n-1)条边,则一定有回路.

深度优先、广度优先生成树

2.最小生成树

概念

常用算法

普利姆Prime算法

算法步骤

1.初始化时，选择一个顶点加入生成树中。
2.在剩余的未加入生成树的顶点中，找到一条边，使得这条边的权值最小，并且这条边的一个顶点在生成树中，另一个顶点不在生成树中。
3.将找到的这条边以及边的另一个顶点加入到生成树中。
4.重复步骤2和3，直到所有顶点都加入到生成树中。

过程

基本思想

Prim算法的基本思想是从图中的某一顶点开始，逐渐长出一棵包含所有顶点的最小生成树。每一步都添加一条连接已选顶点集合和未选顶点集合的最小边。

时间复杂度

克鲁斯卡尔Kruskal算法

算法步骤

1.将图中的所有边按权值从小到大排序。
2.初始化生成树为空。
3.按顺序遍历排序后的边，如果这条边连接的两个顶点属于不同的连通分量，则将这条边加入生成树中。
4.使用并查集数据结构来维护各个顶点的连通性。
5.重复步骤3，直到生成树中含有N-1条边为止。

过程

基本思想

Kruskal算法是基于贪心策略的算法，它的基本思想是按照边的权重顺序（从小到大）选择边，每次选择权重最小的边加入生成树中，如果加入这条边不会形成环，则这条边是最小生成树的一部分。

时间复杂度

3.4.4 拓扑排序

1、DAG 与 AOV 网

一个无环的有向图被称作有向无环图（DAG，Directed Acycline Graph）。它不同于有向树，DAG 将有向边改成无向边后可以出现环，而有向树不行。

2、拓扑排序

3.5 查找

3.5.1 查找的基本概念

1.基本概念

查找

查找是指根据给定的某个值，在查找表中确定一个其关键字等于给定值的记录或数据元素。

若表中存在这样的一个记录，则称查找成功，此时查找的结果可给出整个记录的信息，或指示该记录在查找表中的位置

若表中不存在关键字等于给定值的记录，则称查找不成功，此时查找的结果可给出一个 “空” 记录或 “空” 指针。

查找表

查找表是由同一类型的数据元素（或记录）构成的集合。由于 “集合” 中的数据元素之间存在着完全松散的关系，因此查找表是一种非常灵活的数据结构，可以利用其他的数据结构来实现，例如线性表、树表及散列表等。

关键字

关键字是数据元素（或记录）中某个数据项的值，用它可以标识一个数据元素（或记录）。

若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（对不同的记录，其主关键字均不同）。

称用以识别若干记录的关键字为次关键字。

当数据元素只有一个数据项时，其关键字即为该数据元素的值。

查找表常见操作

静态查找表

顺序查找，折半（二分）查找，分块查找

动态查找表

二叉树排序树，平衡二叉树，B_树，哈希表

2 平均查找长度

为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值，称为查找算法，在查找成功时的平均查找长度(Average Search Length, ASL)。

3.5.2 静态查找表的查找方法

1.顺序查找

概念

通常用于线性表，从表中第一个元素开始，逐一检查当前元素是否满足条件

基本思想

从表的一端开始，顺序扫描线性表，依次扫描到的结点关键字和给定的K值相比较。

若当前扫描到的结点关键字与 K相等，则查找成功。

若扫描结束后，仍未找到关键字等于 K的结点，则查找失败。

示例

适用

顺序查找的方法对于顺序存储方式和链式存储方式的查找表都适用，无论有序与无序。

平均查找长度

时间复杂度

顺序查找需要从头开始不断地按顺序检查数据，因此在数据量大且目标数据靠后，或者目标数据不存在时，比较的次数就会更多，也更为耗时。若数据量为 n，线性查找的时间复杂度便为 O(n)。

优缺点

优点

算法简单且适应面广，对查找表的结构没有要求，无论记录是否按关键字有序排列均可使用。

缺点

成功查找的平均次数约为表长的一半。与其他方法相比，顺序查找方法在n值较大时，其平均查找长度较大，查找效率较低。

2.折半查找

基本思想

先确定待查找记录所在的范围(区间)，然后逐步缩小范围直到找到或找不到该记录为止。

具体步骤

以 A 选项为例，根据算法，需要查找数应该是一个大于18而小于30数，否则根据二分查找算法不会与18至30数据段中间位置数据25进行比较。进一步分析，与25比较后，如果要查找数小于25，则与18至25数据段中间位置数据进行比较，如果大于25，则与25至30数据段中间位置数据进行比较，而不可能与18数据之间数据10进行比较。故选项B比较序列是不可能出现，因为数据表是有序，10只能存储在18之前位置，不能存储于18至25之间或25至30之间。同理可证C、D选项都是可行比较序列，本题选择B选项。

示例

适用

折平查找要求线性表必须采用顺序存储结构，并且表中的数据元素接关键字有序排列。

平均查找长度

时间复杂度

O(log2n）

优缺点

优点

比较次数少，折半查找的效率比顺序查找高。

缺点

对表结构要求高，只能用于顺序存储的有序表。查找前需要排序，而排序本身是一种费时的运算。同时为了保持顺序表的有序性，对有序表进行插入和删除时，平均比较和移动表中一半元素，这也是一种费时的运算。因此,折半查找不适用于数据元素经常变动的线性表。

3.分块查找

概念

又称索引顺序查找，它是把顺序查找和二分査找相结合的一种查找方法，即把线性表分成若干块，块和块之间有序，但每一块内的结点可以无序。

基本思想

（1）首先查找索引表
索引表是有序表，可采用二分查找或顺序查找，以确定待查的结点在哪一块。
（2）然后在已确定的块中进行顺序查找
由于块内无序，只能用顺序查找。

示例

假设要查找关键字 38 的具体位置。首先将 38 依次和索引表中各最大关键字进行比较，因为 22 < 38 < 48，所以可以确定 38 如果存在，肯定在第二个子表中。由于索引表中显示第二子表的起始位置在查找表的第 7 的位置上，所以从该位置开始进行顺序查找，一直查找到该子表最后一个关键字（一般将查找表进行等分，具体子表个数根据实际情况而定），结果在第 10 的位置上确定该关键字即为所找。

平均查找长度

优缺点

优点

分块査找介于顺序和二分查找之间，在表中插入或删除一个记录时，只要找到该记录所属的块，就在该块内进行插入和删除运算。因块内记录的存放是任意的，所以插入或删除比较容易，无须移动大量记录。

代价

增加一个辅助数组的存储空间和将初始表分块排序的运算

区别

3.5.3 动态查找表的查找方法

1.二叉排序树

2.平衡二叉树

3.B-树

3.5.4 哈希表

1.哈希表的定义

散列表(Hash table, 也叫哈希表)，是根据关键码值(key value)而直接进行访问的数据结构，通过建立键 key 与值 value 之间的映射，实现高效的元素查询。它通过把关键码值映射到表中一个位置来访问记录，以加快查找速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。可以使用哈希表做缓存。

哈希表最大优势就是插入/删除/查找的时间复杂度都是O（1）

2.哈希函数的构造方法

常用的哈希函数构造方法有直接定址法、数字分析法、平方取中法、折叠法、随机数法和除留余数法等。

直接定址法

取关键字的某个线性函数为散列地址： Hash （ Key ） = A*Key + B

优缺点

优点：简单、均匀

缺点：需要事先知道关键字的分布情况

使用场景：适合查找比较小且连续的情况。

除留取余法

假设设散列表中允许的地址数为m，取一个不大于 m ，但最接近或者等于 m 的质数 p 作为除数
函数原型：H(key)= key % p,将关键码转换成哈希地址 (p的值一般为不大于m且最接近m的质数)

优缺点

优点：简单易用，性能均衡

缺点：容易出现哈希冲突，需要借助特定方法解决

适用场景：范围不集中，分布分散的数据

平方取中法

假设关键字为 1234 ，平方是 1522756 ，抽取中间的 3 位 227 作为哈希地址

关键字为 4321 ，平方是18671041 ，抽取中间的 3 位 671( 或 710) 作为哈希地址

适用场景：不知道关键字的分布，而位数又不是很大的情况

3.处理冲突的方法

1.闭散列

开放定址法，当发生哈希冲突时，如果哈希表未被装满，说明在哈希表中必然还有空位置，那么可以把 key 存放到冲突位置中的 “ 下一个 ” 空位置中去。通常把寻找“下一个”空位的过程称为探测，Hi=(H(key)+di)%m i=i,2,…,k ( k ≤ m-1 )

其中，H(key)为散列函数，m为散列表表长，di为增量序列。

1.线性探测 di=1,2,3,...,m−1
这种探测方法可以将散列表假想成一个循环表，发生冲突时，从冲突地址的下一单元顺序寻找空单元，如果到最后一个位置也没找到空单元，则回到表头开始继续查找,直到找到一个空位，就把此元素放入此空位中。如果找不到空位，则说明散列表已满,需要进行溢出处理。

现在需要插入元素 44 ，先通过哈希函数计算哈希地址，下标为 4 ，因此 44 理论上应该插在该位置，但是该位置已经放了值为4 的元素，即发生哈希冲突。
线性探测：从发生冲突的位置开始，依次向后探测，直到寻找到下一个空位置为止。

2.二次探测
线性探测的缺陷是产生冲突的数据堆积在一块，这与其找下一个空位置有关系，因为找空位置的方式就是挨着往后逐个去找，因此二次探测为了避免该问题，找下一个空位置的方法为：Hi=(H0+i^2 )% m, 或者：Hi= (H0-i^2 )% m。其中： i = 1,2,3… ，H0是通过散列函数Hash(x) 对元素的关键码 key 进行计算得到的位置，m是表的大小。

3.伪随机探测法

2.开散列(哈希桶)

开散列法又叫链地址法 ( 开链法 ) ，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。

开散列中每个桶中放的都是发生哈希冲突的元素。开散列，可以认为是把一个在大集合中的搜索问题转化为在小集合中做搜索

4.哈希表的查找

3.6 排序

3.6.1 排序的基本概念

排序是处理数据的一种最常见的操作，所谓排序就是将数据按某字段规律排列，所谓的字段就是数据节点的其中一个属性。比如一个班级的学生，其字段就有学号、姓名、班级、分数等等，我们既可以针对学号排序，也可以针对分数排序。

内排序与外排序

如果待排序数据量不大，可以一次性全部装进内存进行处理，则称为内排序。

若数据量大到无法一次性全部装进内存，而需要将数据暂存外存，分批次读入内存进行处理，则称为外排序。

3.6.2 简单排序

1.直接插入排序

概念

插入排序是指在待排序的元素中，假设前面n-1(其中n>=2)个数已经是排好顺序的，现将第n个数插到前面已经排好的序列中，然后找到合适自己的位置，使得插入第n个数的这个序列也是排好顺序的。按照此法对所有元素进行插入，直到整个序列排为有序的过程，称为插入排序。

直接插入排序步骤

时间、空间复杂度

特点

稳定排序

算法简便，且容易实现

也适用于链式存储结构，只是在单链表上无需移动记录，只需修改相应的指针。

更适合于初始记录基本有序（正序）的情况，当初始记录无序，n较大时，此算法时间复杂度较高，不宜采用。

2.冒泡排序

概念

冒泡排序是一种最简单的交换排序方法,它通过两两比较相邻记录的关键字，如果发生逆序，则进行交换，从而使关键字小的记录逐浙往上“漂”(左移),或者使关键字大的记录逐渐向下“坠”(右移)。

实现思路

从待排序序列中找出一个最大值或最小值，这样的操作执行 n-1 次，最终就可以得到一个有序序列。

冒泡排序步骤

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

对 {14, 33, 27, 35, 10} 序列进行升序排序（由小到大排序），冒泡排序算法的实现过程是：

从 {14, 33, 27, 35, 10} 中找到最大值 35；

从 {14, 33, 27, 35, 10} 中找到最大值 35 的过程如下：
1) 比较 14 和 33 的大小，显然后者更大，不需要交换它们的位置，序列不发生改变。

2) 比较 33 和 27 的大小，前者大于后者，交换它们的位置

3)比较 33 和 35 的大小，后者更大，不需要交换它们的位置，序列不发生改变。

4)比较 35 和 10 的大小，前者大于后者，交换它们的位置

序列中值最大的元素 35 被移动到了序列的末尾。整个查找最大值的过程中，最大的元素就像水里的气泡一样，一点一点地“冒”了出来

从 {14,33,27,10} 中找到最大值 33；

从 {14, 27, 10} 中找到最大值 27；

从 {14, 10} 中找到最大值 14。

比 10 大的数都被一一找到，所以 10 必然是最小的数，这也是为什么“对 n 个数据进行排序，找最大值的过程只重复 n-1 次”的原因。

时间、空间复杂度

特点

稳定排序

可用于链式存储结构

移动记录次数较多，算法平均时间性能比直接插入排序差，当初始记录无序，n较大时，不宜采用。

3.简单选择排序

概念

简单选择排序属于选择类排序，主要动作就是“选择”，简单选择排序采用最简单的选择方式，从头至尾顺序扫描序列，找出最小的一个元素，和第一个元素交换，接着从剩下的元素中继续这种选择和交换，每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。

简单选择排序步骤

1.在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3.重复第二步，直到所有元素均排序完毕。

假设一个数组 [5, 8, 6, 3, 9, 2, 1, 7]，对其进行升序排序，使用简单选择排序的过程如下：

首先在未排序序列中找到最小的元素1，将其与序列的第一个元素5交换，得到 [1, 8, 6, 3, 9, 2, 5, 7]。
然后在剩下的未排序元素中找到最小的元素2，将其与第二个元素8交换，得到 [1, 2, 6, 3, 9, 8, 5, 7]。
继续这个过程，可以得到 [1, 2, 3, 6, 9, 8, 5, 7] -> [1, 2, 3, 5, 9, 8, 6, 7] -> [1, 2, 3, 5, 6, 9, 8, 7] -> [1, 2, 3, 5, 6, 7, 9, 8] -> [1, 2, 3, 5, 6, 7, 8, 9]。
最后，得到了完全排序的数组 [1, 2, 3, 5, 6, 7, 8, 9]。

时间、空间复杂度

时间复杂度

最坏情况：O(n^2)
最好情况：O(n^2)
平均情况：O(n^2)
选择排序的时间复杂度在各种情况下都是 O(n^2)，因为无论输入数组是否已经部分排序，算法都需要进行 n-1 次外层循环和相应的内层循环比较。

空间复杂度

选择排序是原地排序算法，只需要常数级的额外空间，占用 1 个临时空间，在交换数值时使用。

适用场景

小规模数据：当数据量较小时，选择排序的简单实现可能比复杂的排序算法更有效。
内存空间有限：由于是原地排序算法，选择排序只需要很少的额外内存。
对交换操作敏感的场景：相比冒泡排序，选择排序的交换次数较少。

优缺点

优点

实现简单，容易理解
交换次数少于冒泡排序
原地排序，不需要额外的存储空间

缺点

时间复杂度高，对于大规模数据效率低下
不稳定排序

3.6.3 希尔排序

希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

基本思想

将整个待排序序列分割成若干个子序列，分别对这些子序列进行插入排序，然后逐步减小子序列的间隔，直到间隔为1，最终对整个序列进行一次插入排序。这样，插入排序的效率会得到大幅提升。

希尔排序步骤

1.确定间隔序列：选择一个间隔序列，一般是逐步减半，直到间隔为1。
2.间隔排序：对间隔序列所对应的子序列进行插入排序。
3.逐步缩小间隔：重复第二步，逐步减小间隔，直到间隔为1，完成最终的插入排序。

选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择可以用一个序列来表示，{n/2,(n/2)/2...1}，称为增量序列。

时间复杂度、空间复杂度

希尔排序的时间复杂度取决于间隔序列的选择。一般来说，间隔序列的选择直接影响到希尔排序的性能。
1.最好情况时间复杂度： O(n log n)
2.平均情况时间复杂度：取决于间隔序列
3.最坏情况时间复杂度： O(n^2)

稳定性分析

（1）希尔排序是不稳定的排序算法
（2）在排序过程中，由于分组和增量递减的特性，相同大小的元素可能会因为分组后的插入排序操作而发生相对位置的改变。特别是当两个相等元素位于不同增量分组时，它们可能经过不同的插入排序路径，最终导致相对位置的变化

优缺点

优点

（1）相对于直接插入排序，希尔排序在处理大规模数据时通常具有更高的效率，因为它能够更快地减少数据的无序度
（2）希尔排序的空间复杂度为O(1)，不需要额外的存储空间
（3）实现相对简单，代码易于理解和维护

缺点

（1）稳定性差，可能会改变相等元素的相对位置
（2）时间复杂度的具体表现依赖于增量序列的选择，选择不当可能导致性能下降

3.6.4 快速排序

概念

快速排序（Quick Sort）是从冒泡排序算法演变而来的，实际上是在冒泡排序基础上的递归分治法。快速排序在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分。

主要思想

分治法，将一个大问题分割成小问题，解决小问题后再合并它们的结果。

快速排序的实现步骤

1.从待排序的数组中选择一个元素，称之为枢纽元（pivot）。
2.将数组中小于枢纽元的元素移到枢纽元的左边，将大于枢纽元的元素移到枢纽元的右边，这个过程称为分区（partition）。
3.递归地对枢纽元左边的子数组和右边的子数组进行排序。
4.当所有子数组都有序时，整个数组就自然有序。

时间、空间复杂度

时间复杂度

空间复杂度

快速排序是递归的，需要一个栈来存放数据。最好情况下的空间复杂度为 O(log2n)，最坏情况下的空间复杂度为 O(n)。

快速排序算法的特点

由于记录的移动是非顺次的，所以快速排序是一种不稳定的排序方法。
由于在排序过程中需要定位表的上界和下界，所以适用于顺序结构，很难用于链式结构。
适用于初始记录无序、记录较多的情况。在记录较多时，在平均情况下快速排序是所有内部排序方法中速度最快的一种。

3.6.5 堆排序

概念

堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

堆是一棵顺序存储的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。

堆排序的基本思路

堆排序的步骤
1.构造大根堆：从最后一个非叶子节点开始，向上调整每个节点，确保每个节点的值都大于其子节点的值。
2.交换元素：将堆顶元素（最大值）与数组末尾元素交换，然后减少堆的大小。
3.重构大根堆：调整剩余的堆，使其再次成为大根堆。
4.重复步骤2和3：直到堆的大小为1，此时数组已经排序完成。

调整为大顶堆

步骤1:
找到非叶子节点

调整大顶堆
左子结点(11) 比当前指向的节点(10)大，因此交换二者的位置并指向左子节点，左子节点无子节点，调整结束

步骤2:
找到非叶子节点
找到上一个非叶子节点的前一个非叶子节点，继续调整大顶堆

调整大顶堆
右子结点(14) 比当前指向的节点(9)大，因此交换右子节点当前指向的节点并指向右子节点，右子节点无子节点，调整结束

步骤3:
找到非叶子节点
找到上一个非叶子节点的前一个非叶子节点，继续调整大顶堆

调整大顶堆
当前指向的节点比其子节点都大，符合大顶堆的规则，因此不用进行调整, 调整结束

步骤4:
找到非叶子节点
找到上一个非叶子节点的前一个非叶子节点，继续调整大顶堆

调整大顶堆

调整为小顶堆

时间复杂度、空间复杂度

时间复杂度

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度最好和最坏情况下都是O(nlogn)级。

空间复杂度

堆排序不要任何辅助数组，只需要一个辅助变量，所占空间是常数与n无关，所以空间复杂度为O(1)。

堆排序的特点

不稳定排序

堆排序是不稳定的算法，它不满足稳定算法的定义。它在交换数据的时候，是比较父结点和子节点之间的数据，所以，即便是存在两个数值相等的兄弟节点，它们的相对顺序在排序也可能发生变化。
算法稳定性 -- 假设在数列中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。则这个排序算法是稳定的。

只能用于顺序结构，不能用于链式结构

3.6.6 归并排序

基本概念

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并

分治法在归并排序中的应用是将问题分解成更小的子问题，然后分别解决这些子问题，最后将子问题的解合并起来得到原问题的解。

具体来说，归并排序的分治法应用如下：
分解：将待排序的数组分成两个子数组，分别为左子数组和右子数组。
解决：递归地对左子数组和右子数组进行归并排序。
合并：将排好序的左子数组和右子数组合并成一个有序数组。

归并排序算法实现思路

将整个待排序序列划分成多个不可再分的子序列，每个子序列中仅有 1 个元素；
所有的子序列进行两两合并，合并过程中完成排序操作，最终合并得到的新序列就是有序序列。

使用归并排序算法对 {7, 5, 2, 4, 1, 6, 3, 0} 实现升序排序的过程

1) 将 {7, 5, 2, 4, 1, 6, 3, 0} 分割成多个子序列，每个子序列中仅包含 1 个元素。整个序列不断地被一分为二，最终被分割成 {7}、{5}、{2}、{4}、{1}、{6}、{3}、{0} 这几个序列。

2) 将 {7}、{5}、{2}、{4}、{1}、{6}、{3}、{0} 以“两两合并”的方式重新整合为一个有序序列

时间、空间复杂度