数值转换

数的转换

• 数制及其特征

  数制	基本数码	基数	位权	形式表示符
  十进制	0,1,2,3…9	r=10	10n	D
  二进制	0,1	r=2	2n	B
  八进制	0,1,2,3,4…7	r=8	8n	O
  十六进制	0-9,A,B,C,D,E,F	r=16	16n	H

• R进制->十进制

  • 使用位权展开法
  • 将R进制的每一位数值用R^k形式表示
  • R为底数/基数
  • k为指数

• 十进制->R进制

  • 使用短除法

• 二进制<–>八进制

• 二进制<–>十六进制

数据的存储单位

• 在计算机中，数据的最小存储单位为BIT，1比特为1个二进制位。字节（Byte），1个字节为8个二进制位
• 二进制有两个数：0,1
• 位（Bit）
• 字节（Byte）
  • 1B=8bit
  • 1KB=1024B
  • 1MB=1024KB
  • 1GB=1024MB
• 除字节Byte外，还有千字节（KB），兆字节（MB），吉字节（GB），太字节（TB）

二进制的运算

• 二进制的算术运算：加、减、乘、除
• 二进制的逻辑运算：与、或、非、异或

数据的表示

数的表示

• 机器数和真值：两者之间的区别是真值的符号在机器数中用二进制符号位表示

• 码制

  	数值+1	数值-1	1+（-1）	整数数值范围
  原码	0000 0001	1000 0001	1000 0010	-（2n-1-1）~2n-1-1
  反码	0000 0001	1111 1110	1111 1111	-（2n-1-1）~2n-1-1
  补码	0000 00001	1111 1111	0000 0000	-2n-1~2n-1-1
  移码	1000 0001	0111 1111	1000 0000	-2n-1~2n-1-1

  • 原码：第一位为符号位，其余组成真值
  • 反码：正数与原码相同；负数除第一位外其余数值位按位取反
  • 补码：正数与原码相同；负数在反码基础上加一（常用于加减法运算，部分计算机数的表示、存储）
  • 移码：在补码基础上数值不变，符号位取反（常用于浮点数的阶码）

定点数和浮点数

• 定点数：小数点的位置固定不变的数，小数点不需要占用一位二进制
  • 定点整数：小数点固定在最右边
  • 定点小数：小数点固定在某一位
• 浮点数：N=R^e*M，其中M称为尾数，e是指数（阶码，用移码表示），R为基数（阶码的底）
  • 阶符
  • 阶码：决定数值表示的范围
  • 数符
  • 尾数：决定数值表示的精度
  • 流程：对阶->尾数计算->结果格式化

计算机的基本组成

计算机的结构

• 
• 运算器
  • 算术逻辑单元ALU：数据的算术运算和逻辑运算
  • 累加寄存器AC：通用寄存器，为ALU提供一个工作区，用来暂时保存数据
  • 数据缓冲寄存器DR：写内存时，暂存指令或数据
  • 状态条件寄存器PSW：存状态标志与控制标志（争议：也有将其归为控制的）
• 控制器
  • 程序计数器PC：存储下一条要执行指令的地址（地址不同于指令组成中的地址码）
  • 指令寄存器IR：存储即将要执行的指令
  • 指令译码器ID：对指令进行分析解释
  • 时序部件：提供时序控制信号指令中的操作码字段

计算机基本概念

• CPU的性能指标：主频、字长、CPU缓存、核心数量
• 总线的分类：数据总线、控制总线、地址总线
• 总线的性能指标：带宽、位宽、工作频率
• BIOS/CMOS
• 系统性能评测方法：时钟频率、指令执行、等效指令速度法、数据处理速率（PDR）、核心程序法、基准测试程序

总线系统

• 一条总线同一时刻仅允许一个设备发送，但允许多个设备接收
• 总线的分类
  • 数据总线：在CPU与RAM之间来回传送需要处理或是需要存储的数据
  • 地址总线：用来指定在RAM之中存储的数据的地址
  • 控制总线：将微处理器控制单元的信号传送到周边设备
• 总线的性能指标：带宽、位宽、工作频率（带宽=位宽*工作频率）

指令

• 一条指令就是机器语言的一个语句，是一组有意义的二进制代码
• 组成
  • 操作码字段OP：指出了计算机要执行什么性质的操作
  • 地址码字段A：包含各操作数的地址及操作结果的存放地址等

寻址方式

• 立即寻址方式：操作数直接在指令中，速度快，灵活性差
• 直接寻址方式：指令中存放的是操作数的地址
• 间接寻址方式：指令中存放了一个地址，这个地址对应的内容是操作数的地址
• 寄存器寻址方式：寄存器存放操作数
• 寄存器间接寻址方式：寄存器内存放的是操作数的地址

流水线

• 流水线：多条指令重叠进行操作的一种准并行处理实现技术
• 流水线周期：执行时间最长的一段
• 流水线计算公式
  • 1条指令执行时间+（指令条数-1）*流线线周期
    • 理论公式：(t₁+t₂+…+t_k)+(n-1)*Δt
    • 实践公式：k * Δt + (n-1) * Δt
• 流水线的吞吐率（TP）计算的最基本的公式为：TP=n/T_k（T_k表示总共花费时间）
• 流水线的最大吞吐率：流水线周期的倒数

多级存储器结构

金字塔形层次结构

• 存储器被组织成金字塔形的层次结构，自上而下组成6个层次结构，依次变得更慢、访问频率更低、容量更大、每字节的造价更便宜
  • S0：寄存器。CPU寄存器保存来自cache的字
  • S1：芯片内的高速缓存（cache）。芯片内的cache保存取自芯片外cache的cache行
  • S2：芯片外的高速缓存（SRAM，DRAM，DDRAM）。芯片外的cache保存取自主存储器上的cache行
  • S3：主存储器（Flash，PROM，EPROM，E2PROM）。主存储器保存取自外部存储器上的文件
  • S4：外部存储器（磁盘，光盘，CF卡，SD卡）外部存储器保存远程二级存储器上的文件
  • S5：远程二级存储器（分布式文件系统，Web服务器）

Cache

• 功能：提高CPU数据输入输出的速率，突破所谓的“冯诺依曼瓶颈”

• 速度：在计算机的存储系统体系中，Cache是访问速度较快的层次

• 原理：使用Cache改善系统性能的依据是程序的局部性原理

• 组成：Cache由两部分组成：控制部分和Cache存储器部分

• 平均系统周期时间（以读操作为例：使用“Cache+主存储器”）t₃=hxt₁+(1-h)xt₂

  • h代表对Cache的访问命中率
  • t₁表示Cache的周期时间
  • t₂表示主存储器周期时间
  • t₃表示系统的平均周期
  • (1-h)又称为失效率（未命中率）

• 地址映像

  • 通常由SRAM（Static Random Access Memory，静态存储器）组成，其访问速度远高于主存，接近CPU
  • 其功能是提高CPU数据输入输出的速率。其理论依据是程序的局部性原理。实现基础是将主存和Cache划分成大小相同的块/页
  • 装入缓存时将主存块与Cache块的映射关系存入相联存储表（硬件实现）中
  • CPU通过主存地址访问时先访问Cache（命中可提升速度，所以其关键性能指标是命中率），依据主存地址关联相联存储表转换为Cache地址。如果在Cache没有，才需要访问主存（Cache页置换，置换算法会影响命中率）

• 直接映像和变换

  • 主存储器中一块只能映像到cache的一个特定块中
  • 主存和缓存分为相同大小的数据块
  • 主存空间按缓存容量分为区，每一区的块数与缓存的总块数相等
  • 主存中某区的一块存入缓存时只能存入缓存中块号相同的位置
  • 特点：
    • 地址变换电路简单，访问速度快
    • 空间利用率低，冲突概率高
    • 对页面置换算法依赖度高，且Cache空间利用率较低，命中率较低

• 全相联地址映像和变换

  • 主存中任意一块可以映像到Cache中的任意一块的位置上
  • 主存和缓存分成相同大小的数据块
  • 主存的某一数据块可以装入缓存的任意一块空间中
  • 特点：
    • 空间利用率高
    • 冲突概率低
    • 实现复杂，速度慢，适合小容量cache

• 组相联地址映像和变换

  • 主存和cache按同样大小分块
  • cache分为若干组，如两块一组，主存按cache组数分区
  • 每个组采用直接映射方式
  • 组内的块则采用全相连映像方式
  • 特点：
    • 是以上两种方式的折衷
    • 实现难度和造价要比直接映像方式高

I/O控制方式

• 直接程序控制：无条件传送方式、程序查询方式
• 中断方式
• 直接存储器存取方式（DMA）：在传送数据块的过程中不需要CPU干涉
• 输入输出处理机（IOP）

可靠性和校验码

可靠性

• 串联系统R=R₁xR₂x…xR_n，R为可靠度，R₁~R_n每个串联部分可靠度
• 并联系统R=1-(1-R₁)x(1-R₂)x…x(1-R_n)，（1-R）又称为失效率
• 混合系统为串联和并联的叠加

校验码

• 码距：一个编码系统的码距就是整个编码系统中任意（所有）两个码字（合法编码）的最小距离

  • 举例：要对A，B两个字母进行编码
    • 若用1位长度的二进制编码，若A=1，B=0。这样A，B之间的最小码距为1
    • 若用1位长度的二进制编码，若A=11，B=00。这样A，B之间的最小码距为2
    • 若用1位长度的二进制编码，若A=111，B=000。这样A，B之间的最小码距为3

• 奇偶校验码：

  • 通过在编码中增加一位校验位来使编码中的1的个数为奇数（奇校验）或者为偶数（偶校验），从而使码距变为2
  • 仅可检错，可检测1（奇数）位错

• CRC（循环冗余码）：

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

  • 三者中唯一用到模2运算

  • 仅可检错，可检测多位错

• 海明码：

  • 在数据位之间插入K个校验位，通过扩大码距来实现检查和纠错
  • 设数据位是n位，校验位是k位，则n和k必须满足 2^k-1>=n+k
  • 可检错，且可纠1位错

一文总结嵌入式七大通信总线协议

电阻

• 代号：R

• 单位：欧姆（Ω）、千欧（KΩ）、兆欧（MΩ）等。

• 作用：分流、限流、分压、降压、隔离和偏置等。

  • 隔离：电阻的隔离作用并非传统意义上的物理隔离，而是通过电阻的特性（如分压、限流、阻抗匹配等）来实现电路信号或功能的某种隔离效果。具体来说，电阻在电路中可以防止不同部分之间的直接相互影响，确保信号的稳定传输和电路的正常工作。
  • 偏置：电阻的偏置作用主要体现在为电路中的电子元件（如晶体管、场效应管等）提供稳定的工作点电压或电流。通过设置合适的偏置电阻，可以确保电子元件在正常工作范围内进行操作，从而提高电路的稳定性和可靠性。

• 热敏电阻（RT）：分为正温度系数热敏电阻（PTC）和负温度系数热敏电阻（NTC）。

• 光敏电阻（RL）：又称为光导管，在特定波长的光照射下，其阻值迅速变小。

• 压敏电阻（RPS）：具有非线性伏安特性并有抑制瞬态过电压作用的固态电压敏感元件。当端电压低于某一阈值时，压敏电阻器的电流几乎等于零；超过此阈值时，电流值随端电压的增大而急剧增加。

• 电位器（W或RP）：阻值可以调整的电阻。分为旋转式、直滑式和带开关式。

• 好坏判别：用万用表电阻挡测得实际阻值与标称值一致或在允许误差范围内为好。(烧坏一般变黑色)。在路测量实际阻值≤标称值。

电容

• 代号：C

• 单位：法拉（F）、豪法（mF）、微法（uF）、钠法（nF）、皮法（pF）。

• 特性：隔直流电通交流电

• 作用：隔直、耦合、旁路、滤波、调谐回路和能量转换控制电路等方面。

  • 耦合：电容耦合是一种利用分布电容进行信号传递的耦合方式，也被称为电场耦合或静电耦合。其主要作用体现在以下几个方面：

    • 隔离强电和弱电系统：电容耦合可以隔离强电和弱电系统，确保弱电系统免受强电系统的干扰。
    • 提供高频信号通路：电容对高频信号的阻抗较小，因此能够提供高频信号的有效传输通路。
    • 阻止工频电流进入弱电系统：通过电容的耦合作用，可以阻止工频电流进入弱电系统，保护弱电系统的稳定运行。
    • 提高电路稳定性：在电子电路中，电容耦合常用于放大电路，以防止信号间的干扰，提高电路的整体稳定性。例如，在三极管放大电路中，电容耦合用于隔离前后级信号，防止直流偏置对放大电路的影响，同时实现交流信号的传输。

  • 旁路：旁路电容是指在电路中并联一个电容器，以提供一条低阻抗的通道，将高频信号绕过某个电路元件。其主要作用包括：

    • 滤波：旁路电容可以用来滤除电路中的高频噪声信号。在大多数电路中，电源线上会存在一些高频噪声，旁路电容可以将这些噪声引至地线，从而保持信号的净度。此外，旁路电容还可以平滑脉冲信号，将一个脉冲信号转换为一个连续的直流信号，提供更加稳定的电压。
    • 耦合：虽然旁路电容的主要作用不是耦合，但在某些情况下，它也可以用来实现不同电路之间的耦合。例如，在音频放大器中，旁路电容可以用来将输入和输出之间的直流偏置隔开，从而实现交流信号的传输。
    • 数据存储：由于电容器能够在充电和放电之间存储电荷，因此旁路电容也可以用来实现短期的数据存储。通过控制充放电过程，可以存储和读取数据。

• 相关名词

  • 耐压：表示容器在长期工作过程中能接受的最高电压值
  • 容量：容量的大小就是表示能贮存电能的大小；电容对交流信号的阻碍作用称为容抗，它与交流信号的频率和电容量有关。

• 容量识别方法：

  • 容量大的电容其容量值在电容上直接表明
  • 容量小的电容其容量值在电容上用字母表示或数字表示
    • 字母表示法：1m = 1000uf；1P2 = 1.2PF；1n = 1000PF
    • 数字表示法：
      • 示为小数的或标示为一位或两位整数的，标示数就是容量值；
        • 标为小数的，容量单位为uF；
        • 标为整数的，容量单位为pF；
      • 用三位数字表示容量大小，前两位表示有效数字，第三位数字是倍率（或补几个“0”个数）。如：
        • 102表示10x10²PF = 1000PF
        • 224表示22x104PF = 220000PF

• 好坏判别：两极短路放电后，用万用表电阻挡测，表针摆出后能返回到原处为好;表针摆出后不返回为短路;表针摆出后返回不到原处为好漏电;表针不摆出为开路;短路、开路、漏电严重为损坏。对于小电容，测量表针不摆动，再用串联“电笔法”或“交流信号法” 判定好坏。

电感

• 代号：L

• 别称：扼流器、电抗器、动态电抗器

• 在电路中常用“L”加数字表示，如：L6表示编号为6的电感。

• 特性：通直流电阻交流电。 直流可通过线圈，直流电阻就是导线本身的电阻，压降很小;当交流信号通过线圈时，线圈两端将会产生自感电动势，自感电动势的方向与外加电压的方向相反，阻碍交流的通过，交流电频率越高，线圈阻抗越大。

• 作用：滤波、升压、谐振、分频等。在电路中可与电容组成串、并联振荡电路。

  • 谐振：电感的谐振作用主要体现在与电容器并联或串联构成的谐振电路中。谐振电路是一种能够选择特定频率信号进行放大或抑制的电路。
  • 分频：电感的分频作用通常与铁磁谐振现象相关，特别是在含有非线性电感（如铁心电感）的电路中更为显著。铁磁谐振是指在铁心电感元件中，由非线性电感和电容组成的电路在一定条件下产生的谐振现象。分频谐振是铁磁谐振的一种表现形式，指在某些特定的电路中，由于电容器和电感器之间的相互作用，使得电流和电压的频率变为原始频率的整数分之一时发生的谐振现象。

• 单位：亨（H）、毫亨（mH）、微亨（uH）

• 好坏判别：用万用表电阻挡测有一定阻值不开、短路为好。(烧坏一般变黑色)。

电源变压器

• 代号：B
• 初级次级电压和线圈圈数之间的关系：式中N称为电压比（圈数比）。当N<1时，则N1>N2，V1>V2，该变压器为降压变压器，反之则为升压变压器。
• 绕制公式： N1/ N2 =V1/ V2
  • V1：输入电压；V2：与输出电压；N1：一级线圈匝数≥1000匝；N2：次级线圈匝数。
  • 变压器线圈匝数越多，电磁感应越明显(输入电压V1=220V或380V）。
  • 次级线圈N2根据输出电压V2的需要决定匝数)。
  • 输出功率与输入功率在理想变压器是一样的：P=IU(一般输出功率只有70—90%)。

脉冲变压器

• 脉冲变压器是变压器一种特殊类型，它所变换的不是正弦电压，也不是交流方波，而是接近矩形的单极性脉冲。
• 脉冲变压器广泛应用于各种开关电源中。脉冲变压器一般是做脉冲高频信号耦合、阻抗变换、电压变换之用，指标要求比一般工频变压器高，铁芯常用高导磁铁合金或铁氧体，绕制要求比较严格。

扬声器

• 代号：Y
• 分类：
  • 按工作频率分低音、中音、高音；
  • 按音圈阻抗分低阻抗和高阻抗、内磁式外磁式等。
• 好坏判别：用万用表R×1Ω挡或1.5V干电池，一边不断碰触两接线柱，能发出“喀喀”声。检测扬声器是粗略的，以听声音来主观评价它的质量好坏。
• 扬声器有两个接线柱（两根引线），当单只扬声器使用时两根引脚不分正负极性，多只扬声器同时使用时两个引脚有极性之分。
• 额定功率
  • 单位：W或AV
  • 扬声器的功率有标称功率和最大功率之分。标称功率称额定功率、不失真功率。
• 额定阻抗
  • 单位：Ω
  • 阻抗一般和频率有关。额定阻抗是指音频为400Hz时，从扬声器输入端测得的阻抗。它一般是音圈直流电阻的1.2~1.5倍。常见的阻抗有4Ω、8Ω、16Ω、32Ω等。

二极管

• 代号：D或BG

• 由一个PN结构成。分正负极，P为正极，N为负极；

• 分类：普通、稳压、变容、发光、开关和光电二极管。

  • 变容二极管：又称“可变电抗二极管”，是一种特殊的半导体器件，其电容量可以随外加电压的变化而变化。二极管电容量是指二极管PN结之间的电容量。
  • 光电二极管：也被称为光敏二极管，是一种能够将光信号转换为电信号的半导体器件。

• 作用：整流、稳压、变容、发光（LED）、升压、开关等作用。

• 好坏判别：用万用表R×1K挡对换表笔测，正向阻值3—9K，反向阻值∞(无穷大)为好。

• 电极判别：用万用表R×1K挡对换表笔测，正向阻值3—9K时，黑表笔接的一端为正极，相反一端为负极。“小黑正”(注：从外观上看标有黑或白色的一端为负极)。

• 特性：单相导电（电流只能从正极流向负极，反向不导电）。

• 稳压二极管：起稳压作用;稳压管的负极接正电压，正极接负电压(和普通的二极管接法相反)，当加在稳压二极管的反向电压增加到大于稳压值时，稳压管就导通，形成一个反向电流，把负极电压限制在稳压值上。

• 发光二极管：半导体二极管的一种，可以把电能转化成光能；代号LED；也具有单向导电性，反向击穿电压约5伏，使用时必须串联限流电阻以控制通过管子的电流。限流电阻R可用下式计算： R=(E-UF)/IF 式中E为电源电压，UF为LED的正向压降，IF为LED的一般工作电流。LED使用低压电源，供电电压在6-24V之间，消耗能量较同光效的白炽灯减少80%;使用10万小时后，光衰为初始的50%。

• 光电二极管：和普通二极管一样，也是由一个PN结组成的半导体器件，也具有单方向导电特性。但在电路中它不是作整流元件，而是把光信号转换成电信号的光电传感器件。

• 双向触发二极管：具有对称性的二端半导体器件。常用来触发双向可控硅 ，在电路中作过压保护定时、移相、调速、调光等用途。测量双向触发二极管正、反向电阻值。正常时其正、反向电阻值均应为无穷大。若测得正、反向电阻值均很小或为0，则说明该二极管已击穿损坏。

单相可控硅

• 代号：BCR
• 定义：一种半导体元器件，又称晶体闸流管，单向可控硅是由三个PN结PNPN组成的四层三端半导体器件与具有一个PN结的二极管相比，单向可控硅正向导通受控制极电流控制;可控硅对控制极电流没有放大作用。
• 好坏判别：用万用表R×1K挡对换表笔测AK、AG正反向阻值均为∞，测GK正向阻值3—9K，反向阻值∞为好管。
• 电极判别：用万用表R×1K挡对换表笔测GK，正向阻值3—9K时，黑表笔接的一端为G(控制)极，红表笔接的一端为K(阴极)极，另一端为A(阳极)极。
• 作用：整流、稳压、开关等作用。
• 工作原理：
  • 可控硅的导通条件：一是可控硅阳极与阴极间必须加正向电压，二是控制极也要加正向电压。以上两个条件，必须同时具备，可控硅才会处于导通状态。可控硅一旦导通后，即使降低控制极电压或去掉控制极电压，可控硅仍然导通。
  • 可控硅关断条件：降低或去掉加在可控硅阳极至阴极之间的正向电压，使阳极电流小于最小维持电流以下。

双向可控硅

• 代号：SCR
• 双向可控硅具有两个方向轮流导通、关断的特性。双向可控硅实质上是两个反并联的单向可控硅，是由NPNPN五层半导体形成四个PN结构成、有三个电极的半导体器件。
• 由于主电极的构造是对称的(都从N层引出)，所以它的电极不像单向可控硅那样分别叫阳极和阴极，而是把与控制极相近的叫做第一电极A1，另一个叫做第二电极A2。
• 双向可控硅的主要缺点是承受电压上升率的能力较低。这是因为双向可控硅在一个方向导通结束时，硅片在各层中的载流子还没有回到截止状态的位置，必须采取相应的保护措施。
• 电极和好坏判别：用万用表R×1挡或R×10挡对换表笔测T2、T1或T2、G极正、反阻值指针均不动;用万用表R×1挡或R×10挡对换表笔测T1和G极正、反向阻值均为几十至几百欧，其中必有一次阻值稍大，则稍大的一次红笔接的为G极，黑笔所接为T1极，余下是T2极。
• 作用：交流控制电路，如温度控制、灯光控制、防爆交流开关和交流电机调速、换向、交流稳压等电路。

三极管

• 代号：BG或Q、V和T

• 定义：一种电流控制型器件半导体元器件，又称晶体管;它由两个PN结构成，有三个电极，分别称基极(B)称集电极称(C)发射极(E);按导电类型分有PNP型和NPN型两种管;

• 分类：按功率分有大、中、小功率三种管；按用途分有高、低频两种管。

• 晶体三极管的电流放大系数随温度升高而增大，在实际电路中，主要应用了放大电路和开关电路，是一种小电流控制大电流的放大元件。

• 作用：放大(电压电流)、稳压、开关、振荡等作用。

• 基极判别：用万用表R×1KΩ挡一支表笔固定某一极，另一支表笔去测另外两极，测量得两次阻值都比较小(3—9K)时，固定表笔接的脚就是基极。

• 型号判别：根据测量得基极时固定表笔的颜色，若测量得基极时固定表笔的颜色为红表笔，则该管为PNP型;若测量得基极时固定表笔的颜色为黑表笔，则该管为NPN型。

• 发射判别：用万用表R×10KΩ挡对换表笔去测另外两极，以测量得次阻值小的一次为准(30K以上);PNP型管红表笔接的脚就是E极“小红发”;NPN型管黑表笔接的脚就是E极“小黑发”;另一管脚为C极。

• 好坏判别：

  • 用万用表R×1KΩ挡对换表笔测称B—C和B—E极，正向阻值3—9K，反向阻值∞(无穷大);
  • 用万用表R×10K挡对换表笔测称C—E极，正向阻值30K以上，反向阻值∞(无穷大);
  • 达以上两个条件为好管。

• 带阻尼型管好坏判别：

  • 用万用表R×1Ω或R×10Ω挡对换表笔测称B—E极，正向阻值均为十几至几十欧;
  • 用万用表R×1K挡对换表笔测称C—E极，正向阻值3—9K反向阻值∞(无穷大);
  • 达以上两个条件为好管。

• 放大能力测量：用万用表R×10KΩ挡;PNP管红表笔接C极，黑表笔接E极;NPN管黑表笔接C极，红表笔接E极;用手指接通B与C极时，表针摆动幅度越大说明该项管放大能力越好。表针无摆动为无放大能力已损坏。

• 三极管的三种工作状态

  • 放大状态：三极管的BE极加正向电压时，在正偏状态(BE极之间电压为0.5-0.7V)这时集电极与发射极之间的电流大小受基极控制，三极管处于放大(导通)状态。
  • 饱和(导通)状态：三极管的BE极加正向电压时，在超正偏状态(BE极之间电压大于0.7V以上)这时集电极与发射极之间的电阻很小，就像开关闭合一样，三极管处于饱和(导通)状态。
  • 截止状态：三极管的发射极加反向电压或两断电压为零时,这时集电极与发射极之间的电阻很大，就像开关断开一样，三极管处于截止(不导通)状态;(Vb ≤Ve)。

• 放大电路：当基极(输入端)输入一个较小的基极电流时，其集电极(输出端)将按比例产生一个较大的集电极电流，这个比例就是三极管的电流放大系数。(VC >Vb > Ve)

  • 放大作用的理解：三极管不会产生能量，但它可以通过小电流控制大电流;放大的原理就在于：通过小的变化的交流输入，控制大的静态直流起较大的相应的变化

• 开关电路：三极管在电路中通常用做电子开关。在开关状态下的三极管处于饱和(导通)状态和截止状态。

• 三极管放大工作状态下各电极电压电流的变化关系：

  • 对于NPN型管：Vb↑–Ib↑–Ic↑–Vc↓–Ie↑–Ve↑;Vb↓–Ib↓–Ic↓–Vc↑–Ie↓–Ve↓
  • 对于PNP型管：Vb↑–Ib↓–Ic↓–Ve↑–Ic↓–Vc↓;Vb↓–Ib↑–Ic↑–Ve↓–Ic↑–Vc↑
  • 注：基极电压Vb;基极电流Ib;集电极电流Ic;集电极电压Vc;发射极电流Ie;发射极电压Ve;上升、增大↑;下降、变小↓

光耦元件

• 代号：OC
• 定义：光耦隔离就是采用光耦合器进行隔离,光耦合器的结构相当于把发光二极管和光敏(三极)管封装在一起。发光二极管把输入的电信号转换为光信号传给光敏管转换为电信号输出，由于没有直接的电气连接，这样既耦合传输了信号，又有隔离作用。

三端稳压器

• 三端稳压器件：如78xx、79xx 系列三端稳压器件是最常用的线性降压型DC/DC 转换器。单独的元件可用万用表测量各脚间电阻来粗略判别是否损坏，最好是接入电路中测量; 78系列输出是正压;79系列输出是负压。万用表测量其输出电压就可以判断其好坏了。
• 用途：用于电路的稳压.输出固定电压，以防止电压过高烧毁电路。
• 类别：三端稳压器的通用产品有78系列(正电源)和79系列(负电源)，输出电压由具体型号中的后面两个数字代表;有5V，6V，8V，9V，10V，12V，15V，18V，24V等档次;输出电流以78(或79)后面加字母来区分L表示0.1;AM表示0.5A，无字母表示1.5A，如78L05表求5V 0.1A。
• 使用注意事项：(VI)和(Vo)之间的关系，输入/输出之间要有2-3V及以上的电压差。例:7805 该三端稳压器的固定输出电压是5V，而输入电压至少大于7V。
• 79系列7905，-5V，引脚：1—地、2—进、3—出；78系列7805，+5V，引脚：1—进、2—地、3—出。

集成电路

• 代号：IC
• 定义：集成电路是一种微型电子器件或部件。采用一定的工艺，把一个电路中所需的晶体管、二极管、电阻、电容和电感等元件及布线互连一起，制作在一小块或几小块半导体晶片或介质基片上，然后封装在一个管壳内，成为具有所需电路功能的微型结构;其中所有元件在结构上已组成一个整体。
• 分类：按其功能、结构的不同，可以分为模拟集成电路、数字集成电路和数/模混合集成电路三大类。
• 芯片命名方式非常多，一般都是 字母+数字+字母：前面的字母是芯片厂商或是某个芯片系列的缩写。中间的数字是功能型号。如：MC7805和LM7805，从7805上可以看出它们的功能都是输出5V，只是厂家不一样。后面的字母多半是封装信息，要看厂商提供的资料才能知道具体字母代表什么封。引脚排列：有单列引脚、双列引脚、四列引脚，引脚读数从有“.”标示处读起或放正型号数字对正自己，从下排脚读起。

继电器

• 代号：J
• 定义：电磁继电器KV是一种电子控制器件，一般由电磁铁、衔铁、弹簧片、触点等组成;它具有控制系统(又称输入回路)和被控制系统(又称输出回路)，通常应用于自动控制电路中，它实际上是用较小的电流，较低的电压去控制较大电流，较高的电压的一种电磁效应“自动开关”。故在电路中起着自动调节、安全保护、转换电路等作用。
• 继电器的“常开、常闭”触点，可以这样来区分：继电器线圈未通电时处于断开状态的静触点，称为“常开触点”;处于接通状态的静触点称为“常闭触点”。用万用表电阻档测一下，有阻值的脚是线圈。

电流互感器

• 代号：CT
• 定义：电力系统中一种重要的测量设备，用于测量高电流并将其转换成适宜进行计量和保护的低电流信号。
• 工作原理：电流互感器基于电磁感应原理工作。它由闭合的铁心和绕阻组成，包括一次绕组和二次绕组。一次绕组匝数很少，串在需要测量的电流的线路中；二次绕组匝数比较多，串接在测量仪表和保护回路中。当一次绕组中有电流流过时，会在铁心中产生交变磁通，进而在二次绕组中感应出相应的电流。
• 主要作用：
  • 电流测量：电流互感器能够将高电流转换为低电流输出，以满足计量和监测的要求。这对于电力系统的负荷管理、故障诊断和电能计量非常重要。
  • 电流保护：通过测量电流互感器的输出信号，可以实时监测电路中的电流情况。当电流超过预设的阈值时，电流保护装置会触发，采取相应的措施来避免电路的过载和短路，保护电力设备和系统安全。
  • 电流控制：电流互感器还可用于控制和调节电力系统中的电流，确保系统的稳定性、优化能源利用和提高工作效率。
• 类型：
  • 环形电流互感器：最常见的类型，由环形的铁芯和绕组组成，体积小、重量轻、安装方便，常用于低压电力系统、电能计量和智能电网等领域。
  • 柱形电流互感器：由柱形的铁芯和绕组组成，具有高精度和较大的额定电流范围，适用于中高压电力系统、变电站和发电机等场合。
  • 分合式电流互感器：采用可分离的结构，可以在不中断电路的情况下安装或移除，广泛应用于高压电力系统、故障录波和保护装置等领域。
  • 封闭式电流互感器：在绝缘容器中封装，具有良好的绝缘性能和防护能力，适用于高湿度、污染或易燃环境下的应用。
  • 智能电流互感器：常用于智能电网、物联网和远程监测等应用，提供更高级别的数据处理和管理能力。

类别代号

• D——电能表

第一组别

• D——单相

• H——三相

• J——直流

• S——三相三线

• T——三相四线

第二组别

• A——数字化
• E——机电式
• S——电子式
• Z——智能

特征描述1

• D——多功能
• F——多费率
• H——谐波
• K——费控
• P——最大需量
• X——无功（“有功”和“有无功组合”缺省，“无功”放到特征描述栏，纯无功电能表时采用）
• Y——预付费

特征描述2

• C——槽装式（嵌入式）
• H——多用户
• J——防窃电
• L——长寿命
• M——模组化
• U——导轨

注册号

• 如果产品是统一设计的，采用设计序号。

自由字段

连接符

• -

通信信道

• B——蓝牙通信
• C——CDMA
• D——多种通信方式（具备种以上通信方式，例如双模）
• F——WIFI
• G——GPRS
• H——HRF
• J——微功率无线
• L——有线网络
• N——以太网
• P——公用电话线
• Q——光纤
• W——230MHz专网
• Y——音频
• Z——载波
• NB——NBIoT
• 4G——4G
• 5G——5G
• 其他字母组合——新通信方式简称

分隔符

• /

改进号

举例

• DDZM1234-Z——单相智能电能表，M表示模组化，注册号为1234，通信信道为载波通信
• DDZKM1234iot-Z/a——单相费控智能电能表，M表示模组化，注册号为1234，物联网，通信信道为载波通信，a表示第一次改版
• DTSY1234c——三相四线电子式预付费电能表，注册号为1234，c表示CPU卡
• DTSY1234s——三相四线电子式预付费电能表，注册号为1234，s表示射频卡
• DTEL862/b——三相四线机电式电能表，L表示长寿命，设计序号为862，b表示第二次改版
• DTSX1234——三相四线电子式无功电能表，注册号为1234
• DJSF1234——直流电子式多费率电能表，注册号为1234

• 他们站在一切人之上——之前站在一切人之下，所以叫做反常。
• 今天的暂时的妥协，即酝酿着明天的更大的战争。

单相与三相的区别

• 电压等级

  • 单相电：电压通常为220V，适用于低功率设备的供电。
  • 三相电：电压通常为380V，能够提供更大的输出功率和电压，适用于高功率负载的供电。
  • 单相电的电压是220V，是火线和零线之间的电压（相电压）。
  • 三相电的每根相线之间的电压是380V（线电压）。

• 应用领域

  • 单相电：多用于居民用电，如家庭照明、家用电器等。由于大部分家庭电器不需要太大的功率和电压，因此单相电在家庭用电中占据主导地位。

  • 三相电：多用于工业领域，如电动机、变压器、发电机等设备的供电。三相电在发电、电能转换等方面存在优势，能够提供稳定且高效的电力供应。

• 电力传输特性

  • 单相电：电力传输相对简单，但受限于电压和功率，难以满足大规模工业用电的需求。
  • 三相电：三相电通过三根相线传输电力，每根相线之间的电压相位差为120度，这种相位差使得三相电在传输过程中能够保持电流和电压的平衡，从而实现更高的电力传输效率和负载均衡能力。此外，三相电还具有更好的稳定性和可靠性，能够减少电力线路的损耗和故障。

• 三相电的优势：

  • 三相电特殊的相位差使得三个相位的电流波形相互错开，总和起来近似恒定，因此供电更加稳定。同时，这种稳定的电流波形也减少了电流波动，有利于保证设备运行的稳定性和延长使用寿命。
  • 通过三个相位的电势叠加，三相电能够提供更高的总功率。这种高功率输出特性使得三相电在工业生产、大型建筑、商业中心等需要大量电能的场所具有显著优势。
  • 三相电在传输相同功率时，由于电流分布更为均匀，电能损耗较小，输电效率更高。这种高效传输特性使得三相电在远距离输电和大电流应用中具有显著优势。

单相三线

• 定义：单相三线制是指由一根相线（火线）、一根中性线（零线）和一根地线组成的供电方式。这种供电方式主要用于单相负载的供电。

• 特点：

• 相线：提供单相交流电的电压，通常为220V（在中国标准中）。

• 中性线：在三相四线制供电系统中，中性线用于平衡三相负载的电流，并作为单相负载的回路。在单相三线制中，中性线同样作为单相负载的回路。

• 地线：用于安全接地，防止电器设备漏电时对人体造成伤害。

三相三线

• 定义：三相三线制是指由三根相线（火线）组成的供电方式，没有中性线。这种供电方式主要用于三相平衡负载的供电。三根火线分别为A线、B线和C线。

• 特点：

  • 三根相线：每根相线之间的电压相位差为120度，提供三相交流电。在三相三线制中，由于没有中性线，因此不能用于单相负载的供电。

  • 三相平衡：在三相三线制供电系统中，要求三相负载尽量平衡，以保证电流和电压的稳定。

三相四线

• 定义：三相四线制是指由三根相线和一根中性线组成的供电方式。这种供电方式既可用于三相负载的供电，也可用于单相负载的供电。

• 特点：

  • 三根相线：与三相三线制相同，提供三相交流电。

  • 中性线：在三相四线制中，中性线不仅用于平衡三相负载的电流，还作为单相负载的回路。这使得三相四线制供电系统能够同时满足三相和单相负载的供电需求。

  • 灵活性：由于三相四线制供电系统具有中性线，因此其供电方式更加灵活，适用范围也更广。

单相负载

定义：单相负载是指电路中只有一个相位与负载相连的负载。在单相电路中，电源通常提供一根火线（相线）和一根零线（中性线），负载则连接在这两根线之间，从而获取电能进行工作。

三相负载

• 定义：三相负载是指在电力系统中，由三个独立的单相负载以一定的方式连接，并同时从三相电源获取电能的负载。这三个单相负载分别连接到三相电源的三个相位上，形成一个三相电路。三相负载是工业和商业应用中常见的负载类型，因为它们能够更有效地利用三相电源提供的能量，实现更高的功率输出和更好的负载均衡能力。
• 特点：
  • 三相平衡
  • 高效率
  • 大功率
• 连接方式：
  • 星形
  • 三角形

三角形连接和星形连接

• 三角形连接

  • 接线方式：

    • 将三相电源或负载中的每一相的末端与后续相的前端相连，然后再从3个连接点引出端线。这种接线方式因其形状似三角形而得名。
    • 在电机中，三角形连接是将电机三相绕组的首尾互相连接，并将每个连接点引出作为相线。

  • 电压电流特性：

    • 在三角形连接中，负载的相电压等于三相电源的线电压，即对于标准的三相电源，相电压为380V。
    • 线电流与相电流的关系是：线电流是相电流的根号3倍（约1.73倍）。

  • 适用场景：

    • 三角形连接常用于大功率电机，因为它能够提供较高的相电压（380V），有助于提高电机的功率输出。
    • 然而，三角形连接的启动电流较大，因此在某些情况下需要采用星形-三角形（Y-Δ）转换启动方式来降低启动电流。

• 星形连接

  • 接线方式：
    • 将三相电源或负载的三个绕组的末端连接在一起，形成一个公共点（中性点），然后从每个绕组的始端引出端线。
    • 在电机中，星形连接是将电机三相绕组的三条尾连接在一起，三条头接电源。
  • 电压电流特性：
    • 在星形连接中，负载的相电压是三相电源线电压的1/根号3倍（约0.577倍），即对于标准的三相电源，相电压为220V。
    • 对于三相对称负载，线电流等于相电流。
  • 适用场景：
    • 星形连接常用于小功率电机或需要降低启动电流的场合。由于相电压较低，因此启动电流也相应较小。
    • 星形连接还可以方便地引出中性线，实现三相四线制供电，满足某些特定需求。

• 我们太看重了白昼，又太忽视黑夜。生命，至少有一半是在黑夜中呀。
• 一棵树上落着一群鸟儿，把树砍了，鸟儿也就没了吗？不，树上的鸟儿没了，但它们在别处。同样，此一肉身，栖居过一些思想、情感和心绪，这肉身火化了，那思想、情感和心绪也就没了吗？不，他们在别处。
• 进退维谷之日正可能是别有洞天之时。
• 所谓命运，就是说，这一出 “人间戏剧”需要各种各样的角色，你只能是其中之一，不可以随意调换。
• 佛法博大精深，但我确实不认为满腹功利是对佛法的尊敬。便去烧香，也不该有那样的要求，不该以为命运欠了你什么。莫非是佛一时疏忽错有安排，倒要你这凡夫俗子去提醒一二？唯当去求一份智慧，以醒贪迷。
• 不断的苦难才是不断需要信心的原因。
• 科学需要证明，信仰并不需要。
• 爱，原就是自卑弃暗投明的时刻。
• 皈依并不在一个住所，皈依是在路上。
• 彻底的圆满只不过是彻底的无路可走。
• 一切尘世之名都可以磨灭，而“我”不死。
• 左右苍茫时，总也得有条路走。
• 我想，上帝为人性写下的最本质的两条密码是：残疾与爱情。
• 而你若永远地走向它，你便随时都在它的光照之中。
• 残疾人以及所有的人，固然应该对艰难的生途说“是”，但要对那无言的坚壁说“不”，那无言的坚壁才是人性的残疾。
• 如果白昼的语言已经枯朽，就用黑夜的梦语，用诗的性灵。
• 放弃自卑，同时放弃怨恨；其实这两点必然是同时放弃的，因为曾经，它们也是一齐出生的。
• 那路途中的一切，有些与我擦肩而过从此天各一方，有些便永驻进我的心魂，雕琢我，塑造我，锤炼我，融入我而成为我。
• 白昼的清晰是有限的，黑夜却漫长，尤其是那心流所遭遇的黑暗更是辽阔无边。
• 生命的意义本不在向外的寻取，而在向内的建立。
• 心中对叛徒的看法似乎都在动摇，我慢慢看见，勇猛和可敬之外还有还有着更为复杂的人生处境。
• 仇恨的最大弊端是仇恨的蔓延，压迫的最大遗患是压迫的复制。
• 而那虚假的信仰一旦揭开，内里仍不过一场权利之争，一切轰轰烈烈立刻没了根基。
• 今天，绝对的信仰之光正趋淡薄，日新月异的生活道具正淹没着对生命意义的追求。
• 神性不明之时，强人最易篡居神位。
• 唯对神性的追问与寻觅，是实际可行的信仰之路。
• 接受苦难，从而走向精神的超越。
• 生命本无意义，是”我“使生命获得意义。
• 当精神联通了那无限之在，追随了那绝对价值，他就会因自身的局限而谦虚，因人性的丑陋而忏悔，视固有的困苦为锤炼，看琳琅的美物为道具，既知不断地超越自身才是目的，又知这样的超越乃是永远的过程。
• 不必统一的真实，不如叫作真诚。
• 在看似已然明朗的地方，开始文学的迷茫路。
• 游戏规则是人订的，但游戏——游戏的欲望、游戏的限制、游戏的种种困阻和种种可能性，都是神定。
• 残奥会的圣火不由次神点燃。
• 自从我学会了寻找，我就已经找到。

图

• 图 G 由顶点集 V 和边集 E 组成，记为 G = (V, E)，其中 V(G) 表示图 G 中顶点的有限非空集；E(G) 表示图 G 中顶点之间的关系（边）集合。若 V = {v₁, v₂, …, v_n}，则用 |V| 表示图 G 中顶点的个数，也称图 G 的阶，E = {(u, v) | u ∈ U, v ∈ V}，用 |E| 表示图 G 中边的条数。
• 线性表可以是空表，树可以是空树，但图不可以是空，即 V 一定是非空集。而 E 可以为空集。
• 若 E 是无向边（简称边）的有限集合时，则图 G 为无向图。边是顶点的无序对，**记为(v, w)或(w, v)，因为(v, w) = (w, v)**，其中 v、w 是顶点。可以说顶点 w 和顶点 v 互为邻接点。边(v, w)依附于顶点 w 和 v，或者说边(v, w)和顶点 v、w 相关联。
• 若 E 是有向边（也称弧）的有限集合时，则图 G 为有向图。弧是顶点的有序对，记为<v, w>，其中 v、w 是顶点，v 称为弧尾，w 称为弧头，<v, w> 称为从顶点 v 到顶点 w 的弧，也称 v 邻接到 w，或 w 邻接自 v。**<v, w> != <w, v>**。
• 简单图
  • 不存在重复边
  • 不存在顶点到自身的边
• 多重图：图 G 中某两个结点之间的边数多于一条，又允许顶点通过同一条边和自己关联，则 G 为多重图。
• 对于无向图：
  • 顶点 v 的度是指依附于该顶点的边的条数，记为 TD(v)
  • 在具有 n 个顶点、e 条边的无向图中，$\sum\limits_{i=1}^nTD(V_i) = 2e$，即无向图的全部顶点的度的和等于边数的2倍。
• 对于有向图：
  • 入度是以顶点 v 为终点的有向边的数目，记为 ID(v)
  • 出度是以顶点 v 为起点的有向边的数目，记为 OD(v)
  • 顶点的 v 的度等于其入度和出度之和，即 TD(v) = ID(v) + OD(v)
  • 在具有 n 个顶点、 e 条边的有向图中， $\sum\limits_{i=1}^nID(V_i) = \sum\limits_{i=1}^nOD(V_i) = e$
• 路径——顶点 v_p 到顶点 v_p 之间的一条路径是指顶点序列，V_p, V_i1, V_i2, …, V_q。
• 回路——第一个顶点和最后一个顶点相同的路径称为回路或环。
• 简单路径——在路径序列中，顶点不重复出现的路径称为简单路径。
• 简单回路——除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路。
• 路径长度——路径上边的数目。
• 点到点的距离——从顶点 u 出发到顶点 v 的最短路径若存在，则此路径的长度称为从 u 到 v 的距离；若从 u 到 v 根本不存在路径，则记该距离为无穷（∞）。
• 无向图中，若从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的。若图 G 中任意两个顶点都是连通的，则称图 G 为连通图，否则称为非连通图。
  • 对于 n个顶点的无向图 G，
    • 若 G 是连通图，则最少有 n-1 条边
    • 若 G 是非连通图，则最多可能有 $C_{n-1}^2$条边
• 有向图中，若从顶点 v 到顶点 w 和从顶点 w 到顶点 v之间都有路径，则称这两个顶点是强连通的。
  • 对于 n 个顶点的有向图 G，若 G 是强连通图，则最少有 n 条边（形成回路）
• 设有两个图 G = (V, E) 和 G’ = (V’, E’)，若 V‘ 是 V 的子集，且 E’ 是 E 的子集，则称 G’ 是 G 的子图。
• 若有满足 V(G’) = V(G) 的子图 G’，则称其为 G 的生成子图。
• 无向图中的极大连通子图（子图必须连通，且包含尽可能多的顶点和边）称为无向图的连通分量。
• 有向图中的极大强连通子图（子图必须强连通，同时保留尽可能多的边）称为有向图的强连通分量。
• 连通图的生成树是包含图中全部顶点的一个极小连通子图（边尽可能的少，但要保持连通）。若图中顶点树为 n，则它的生成树含有 n-1 条边。对生成树而言，若砍去它的一条边，则会变成非连通图，若加上一条边则会形成一个回路。
• 在非连通图中，连通分量的生成树构成了非连通图的生成森林。
• 边的权——在一个图中，每条边都可以标上具有某种含义的数值，该数值称为该边的权值。
• 带权图/网——边上带有权值的图称为带权图，也称网。
• 带权路径长度——当图是带权图时，一条路径上所有边的权值之和，称为该路径的带权路径长度。
• 无向完全图——无向图中任意两个顶点之间都存在边。
  • 若无向图的顶点数 |V| = n，则 |E|∈[0, $C^2_n$] = [0, n(n-1)/2]
• 有向完全图——有向图中任意两个顶点之间都存在方向相反的两条弧。
  • 若有向图的顶点数 |V| = n，则 |E|∈[0, 2$C^2_n$] = [0, n(n-1)]
• 边数很少的图称为稀疏图，反之称为稠密图。二者没有绝对的界限，一般来说 |E| < |V|log|V| 时，可以将 G 视为稀疏图。
• 树——不存在回路，且连通的无向图
  • n 个顶点的树，必有 n-1 条边
  • n 个顶点的图，若 |E| > n-1，则一定有回路
• 有向树——一个顶点的入度为0，其余顶点的入度均为1的有向图，称为有向树。

树的基本概念

数的定义和基本术语

• 树：从树根生发，逐级分支。
• 空树：结点数为0的树。
• 非空树的特性：
  • 有且仅有一个根结点。
  • 没有后继的结点称为“叶子结点”（或终端结点）。
  • 有后继的结点称为“分支结点”（或非终端结点）。
  • 除了根结点外，任何一个结点都有且仅有一个前驱。
  • 每个结点可以有一个或多个后驱。
• 树是 n （n >= 0）个结点的有限集合，n = 0 时，称为空树，这是一种特殊情况。在任意一颗非空树中应满足：
  1. 有且仅有一个特定的称为根的结点。
  2. 当 n > 1 时，其余结点可分为 m (m > 0)个互不相交的有限集合 T₁,T₂,…T_m，其中每个集合本身又是一颗树，并且称为根结点的子树。
• 树是递归定义的数据结构。
• 结点之间的关系描述：
  • 祖先结点
  • 子孙结点
  • 双亲结点（父结点）
  • 孩子结点
  • 兄弟结点
  • 堂兄弟结点
  • 两个结点之间的路径：只能从上往下
  • 路径长度：经过几条边
• 结点和树的属性描述：
  • 结点的层次（深度）——从上往下数
  • 结点的高度——从下往上数
  • 树的高度（深度）——总共多少层
  • 结点的度——有几个孩子（分支）
  • 树的度——各结点的度的最大值
• 有序树：逻辑上看，树中结点的各子树从左至右是有次序的，不能互换。
• 有序树：逻辑上看，树中结点的各子树从左至右是无次序的，不能互换。
• 森林：森林是 m(M >= 0)棵互不相交的树的集合。

树的性质

• 结点数 = 总度数 + 1

• 树的度——各结点度的最大值

• m叉树——每个结点最多只能有m个孩子的树

• 度为 m 的树	m 叉树
  任意结点的度 <= m（最多 m 个孩子）	任意结点的度 <= m（最多 m 个孩子）
  至少有一个结点度 = m（有 m 个孩子）	允许所有结点的度都 < m
  一定是非空树，至少有 m + 1 个结点	可以是空树

• 度为 m 的树第 i 层至多有 m^i-1个结点（i >= 1）

  • m 叉树第 i 层至多有m^i-1个结点（i >= 1）

• 高度为 h 的 m 叉树至多有$\frac{m^h-1}{m-1}$（等比求和）

• 高度为 h 的 m 叉树至少有 h 个结点；高度为 h 同时度为 m 的树至少有 h+m-1 个结点。

• 具有 n 个结点的 m 叉树的最小高度为 log_m(n(m-1)+1)。

二叉树

二叉树的定义和基本术语

• m 叉树是 n （n >= 0）个结点的有限集合：
  • 或者为空二叉树，即 n = 0。
  • 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树分别是一颗二叉树。
  • 特点：
    • 每个结点至多只有两棵子树
    • 左右子树不能颠倒（二叉树是有序树）
• 二叉树是递归定义的数据结构。
• 二叉树的五种状态：
  • 空二叉树
  • 只有左子树
  • 只有右子树
  • 只有根结点
  • 左右子树都有
• 几个特殊的二叉树：
  • 满二叉树。一棵高度为 h，且含有2^h-1个结点的二叉树。特点：
    • 只有最后一层有叶子结点。
    • 不存在度为1的结点。
    • 按层序从1开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父结点为 i/2。
  • 完全二叉树。当且进当其每个结点都与高度为 h 的满二叉树中编号为 1~n 的结点一一对应时，称为完全二叉树。特点：
    • 只有最后两层可能有叶子结点。
    • 最多只有一个度为1的结点。
    • 按层序从1开始编号，结点 i 的左孩子为 2i，右孩子为 2i+1；结点 i 的父结点为 i/2。
    • i <= n/2 为分支结点，i > n/2 为叶子结点。
    • 如果某结点只有一个孩子，那么一定是左孩子。
  • 二叉排序树。一棵二叉树或者是空二叉树，或者是具有如下性质的二叉树：
    • 左子树上所有结点的关键字均小于根结点的关键字。
    • 右子树上所有结点的关键字均大于根结点的关键字。
    • 左子树和右子树又各是一颗二叉排序树。
  • 平衡二叉树。树上任一结点的左子树和右子树的深度之差不超过1。
    • 平衡二叉树能有更高的搜索效率。

二叉树的性质

• 设非空二叉树度为0、1和2的结点个数分别为n₀、n₁和n₂，则 n₀ = n₂ + 1（叶子结点比二分支结点多一个）
• 二叉树第 i 层至多有 2^i-1个结点（i >= 1）
• 高度为 h 的二叉树至多有$2^h-1$（等比求和）
• 具有 n 个(n > 0)结点的完全二叉树的高度 h 为 log₂(n+1) 或 log₂n + 1
• 对于完全二叉树，可以由结点数 n 推出度为0、1和2的结点个数分别为n₀、n₁和n₂
  • 完全二叉树最多只有一个度为1的结点，即 n₁ = 0或1，而n₀ = n₂ + 1故n₀ + n₂ 一定是奇数
    • 若完全二叉树有 2k （偶数）个结点，则必有n₁ = 1，n₀ = k，n₂ = k-1
    • 若完全二叉树有 2k-1 （奇数）个结点，则必有n₁ = 0，n₀ = k，n₂ = k-1

二叉树的存储结构

二叉树的顺序存储

• 顺序存储的实现

  1 2 3 4 5 6 7

  #define MaxSize 100 struct TreeNode { ElemType value; //结点中的数据元素 bool isEmpty; //结点是否为空 } TreeNode t[MaxSize];

  定义一个长度为 MaxSize 的数组 t，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点。

• 几个重要的基本操作

  • i 的左孩子—— 2i
  • i 的右孩子—— 2i+1
  • i 的父结点—— i/2
  • i 所在的层次—— log₂(n+1))或 log₂n + 1

• 若完全二叉树中共有 n 个结点

  • 判断 i 是否有左孩子——2i <= n
  • 判断 i 是否有右孩子——2i+1 <= n
  • 判断 i 是否是叶子或分支结点——i > n/2

• 如果不是完全二叉树，依然按层序将各结点顺序存储，则无法从结点编号反映出结点间的逻辑关系。

• 二叉的顺序存储中，一定要把二叉树的结点编号与完全二叉树对应起来。

• 最坏情况：高度为 h 且只有 h 个结点的单支树（所有结点只有右孩子），也至少需要 2^h-1个存储单元。

二叉树的链式存储

• 链式存储的代码实现

  1 2 3 4

  typedef struct BiTNode { ElemType data; //数据域 struct BiTNode *lchild, *rchild; //左、右孩子指针 } BiTNode, *BiTree;

  n 个结点的二叉链表共有 n+1 个空链域。

• 二叉树的建立

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

  struct ElemType { int value; } typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; //定义一棵空树 BiTree root = NULL; //插入根结点 root = (BiTree)malloc(sizeof(BiTree)); root->data = {1}; root->lchild = NULL; root->rchild = NULL; //插入新结点 BiTNode * p = (BiTNode *)malloc(sizeof(BiTNode)); p->data = {2}; p->lchild = NULL; p->rchild = NULL; root->lchild = p; //作为根结点的左孩子

• 三叉链表——方便找父结点

  1 2 3 4 5

  typedef struct BiTNode { ElemType data; //数据域 struct BiTNode *lchild, *rchild; //左、右孩子指针 struct BiTNode *parent; //父结点指针 } BiTNode, *BiTree;

二叉树的先/中/后序遍历

• 遍历：按照某种次序把所有结点都访问一遍。

• 层次遍历：基于树的层次特性确定的次序规则。

• 先/中/后序遍历：基于树的递归特性确定的次序规则。

  • 先序遍历：根左右（NLR）
  • 中序遍历：左根右（LNR）
  • 后序遍历：左右根（LRN）

• 二叉树的递归特性：

  • 要么是个空二叉树。
  • 要么就是由“根结点+左子树+右子树”组成的二叉树。

• 算术表达式的“分析树”

  • 先序遍历：根左右 -> 前缀表达式
  • 中序遍历：左根右 -> 中缀表达式（需要加界限符）
  • 后序遍历：左右根 -> 后缀表达式

• 先序遍历的代码实现

  1. 若二叉树为空，则什么都不做
  2. 若二叉树非空：
     1. 访问根节点
     2. 先序遍历左子树
     3. 先序遍历右子树

  1 2 3 4 5 6 7 8 9 10 11 12 13

  typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; //先序遍历 void PreOrder(BiTree T) { if (T != NULL) { visit(T); //访问根结点 PreOrder(T->lchild); //递归遍历左子树 PreOrder(T->rchild); //递归遍历右子树 } }

• 中序遍历的代码实现

  1. 若二叉树为空，则什么都不做
  2. 若二叉树非空：
     1. 先序遍历左子树
     2. 访问根节点
     3. 先序遍历右子树

  1 2 3 4 5 6 7 8 9 10 11 12 13

  typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; //中序遍历 void InOrder(BiTree T) { if (T != NULL) { InOrder(T->lchild); //递归遍历左子树 visit(T); //访问根结点 InOrder(T->rchild); //递归遍历右子树 } }

• 后序遍历的代码实现

  1. 若二叉树为空，则什么都不做
  2. 若二叉树非空：
     1. 先序遍历左子树
     2. 先序遍历右子树
     3. 访问根节点

  1 2 3 4 5 6 7 8 9 10 11 12 13

  typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; //后序遍历 void PostOrder(BiTree T) { if (T != NULL) { PostOrder(T->lchild); //递归遍历左子树 PostOrder(T->rchild); //递归遍历右子树 visit(T); //访问根结点 } }

• 先序遍历——第一次路过时访问结点

• 中序遍历——第二次路过时访问结点

• 后序遍历——第三次路过时访问结点

• 应用：求树的深度

  1 2 3 4 5 6 7 8 9 10 11

  int treeDepth(BiTree T) { if (T == NULL) { return 0; } else { int l = treeDepth(T->lchild); int r = treeDepth(T->rchild); //树的深度 = Max(左子树深度，右子树深度)+1 return l > r ? l+1 : r+1; } }

二叉树的层序遍历

• 算法思想：

  1. 初始化一个辅助队列
  2. 根结点入队
  3. 若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）
  4. 重复上一步直至队列为空

• 代码实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

  //二叉树的结点（链式存储） typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; //链式队列结点 typedef struct LinkNode { BiTNode * data; //存指针而不是结点 struct LinkNode *next; }LinkNode; typedef struct { LinkNode *front, *rear; //队头队尾 } //层序遍历 void LevelOrder(BiTree T) { LinkQueue Q; InitQueue(Q); //初始化辅助队列 BiTree p; EnQueue(Q, T); //将根结点入队 while (!IsEmpty(Q)) { //队列不空则循环 DeQueue(Q, p); //队列结点出队 visit(p); //访问出队结点 if(p->lchild != NULL) EnQueue(Q, p->lchild); //左孩子入队 if(p->rchild != NULL) EnQueue(Q, p->rchild); //右孩子入队 } }

由遍历序列构造二叉树

• 一个中/前/后/层序遍历序列可能对应多种二叉树形态。中序 + 前/后/层序遍历可得到唯一二叉树。
• 由前序/后序/层序找到树的根结点，并根据中序序列划分左右子树，再找到左右子树根结点。

线索二叉树

• 如何找到指定结点 p 在中序遍历序列中的前驱和后继：从根结点出发，重新进行一次中序遍历，指针 q 记录当前访问的结点，指针 pre 记录上一个被访问的结点。

• 当 q == p 时，pre 为前驱。

• 当 pre == p 时，q 为后继。

• 中序线索二叉树：

  • 前驱线索：左孩子指针充当
  • 后继线索：右孩子指针充当

• 线索二叉树的存储结构

  1 2 3 4 5 6 7 8 9 10 11 12

  //二叉树的结点（链式存储） typedef struct BiTNode { ElemType data; struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; //线索二叉树结点 typedef struct ThtreadNode { ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; //左、右线索标志 tag:1 表示线索 tag:0 表示孩子 } TreadNode, *TreadTree;

二叉树线索化

• 借用 pre 指针找到中序前驱

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

  //中序遍历 void InOrder(BiTree T) { if (T != NULL) { InOrder(T->lchild); //递归遍历左子树 visit(T); //访问根结点 InOrder(T->rchild); //递归遍历右子树 } } //访问结点 q void visit(BiTNode *q) { if (q == p) //当前访问结点刚好是结点 p final = pre; //找到 p 的前驱 else pre = q; //pre 指向当前访问的结点 } //辅助全局变量，用于查找结点 p 的前驱 BiTNode * p; //p 指向目标结点 BiTNode * pre == NULL; //指向当前访问的结点的前驱 BiTNode * final == NULL; //用于记录最终结果

• 中序线索化

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

  //全局变量 pre，指向当前访问结点的前驱 ThreadNode *pre = NULL; //中序线索化二叉树 T void CreateInThread(ThreadTree T) { pre = NULL; //pre初始化为NULL if (T != NULL) { //非空二叉树才能线索化 InThread(T); //中序线索化二叉树 if (pre->rchild == NULL) pre->rtag = 1; //处理遍历的最后一个结点 } } //线索二叉树结点 typedef struct ThtreadNode { ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; //左、右线索标志 tag:1 表示线索 tag:0 表示孩子 } TreadNode, *TreadTree; //中序遍历二叉树，一边遍历一边线索化 void InThread(ThreadTree T){ if (T != NULL) { InThread(T->lchild); //递归遍历左子树 visit(T); //访问根结点 InThread(T->rchild); //递归遍历右子树 } } void visit(ThreadNode *q) { if (q->lchild == NULL) { //左子树为空，建立前驱线索 q->lchild = pre; q->ltag = 1; } if (pre != NULL && pre->rchild == NULL) { pre->rchild = q; //建立前驱结点的后继线索 pre->rtag = 1; } pre = q; }

• 先序线索化

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

  //全局变量 pre，指向当前访问结点的前驱 ThreadNode *pre = NULL; //先序线索化二叉树 T void CreatePreThread(ThreadTree T) { pre = NULL; //pre初始化为NULL if (T != NULL) { //非空二叉树才能线索化 PreThread(T); //先序线索化二叉树 if (pre->rchild == NULL) pre->rtag = 1; //处理遍历的最后一个结点 } } //线索二叉树结点 typedef struct ThtreadNode { ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; //左、右线索标志 tag:1 表示线索 tag:0 表示孩子 } TreadNode, *TreadTree; //先序遍历二叉树，一边遍历一边线索化 void PreThread(ThreadTree T){ if (T != NULL) { visit(T); //访问根结点 if (T->ltag == 0) PreThread(T->lchild); //递归遍历左子树 PreThread(T->rchild); //递归遍历右子树 } } void visit(ThreadNode *q) { if (q->lchild == NULL) { //左子树为空，建立前驱线索 q->lchild = pre; q->ltag = 1; } if (pre != NULL && pre->rchild == NULL) { pre->rchild = q; //建立前驱结点的后继线索 pre->rtag = 1; } pre = q; }

• 后序线索化

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39

  //全局变量 pre，指向当前访问结点的前驱 ThreadNode *pre = NULL; //后序线索化二叉树 T void CreatePostThread(ThreadTree T) { pre = NULL; //pre初始化为NULL if (T != NULL) { //非空二叉树才能线索化 PostThread(T); //后序线索化二叉树 if (pre->rchild == NULL) pre->rtag = 1; //处理遍历的最后一个结点 } } //线索二叉树结点 typedef struct ThtreadNode { ElemType data; struct ThreadNode *lchild, *rchild; int ltag, rtag; //左、右线索标志 tag:1 表示线索 tag:0 表示孩子 } TreadNode, *TreadTree; //后序遍历二叉树，一边遍历一边线索化 void PreThread(ThreadTree T){ if (T != NULL) { PreThread(T->lchild); //递归遍历左子树 PreThread(T->rchild); //递归遍历右子树 visit(T); //访问根结点 } } void visit(ThreadNode *q) { if (q->lchild == NULL) { //左子树为空，建立前驱线索 q->lchild = pre; q->ltag = 1; } if (pre != NULL && pre->rchild == NULL) { pre->rchild = q; //建立前驱结点的后继线索 pre->rtag = 1; } pre = q; }

线索二叉树——找前驱/后继

• 在中序线索二叉树中找到指定结点 *p 的中序后继 next

  • 若 p->rtag == 1，则 next = p->rchild
  • 若 p->rtag == 0，则 next = p的右子树中最左下结点

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  //找到以 p 为根的子树中，第一个被中序遍历的结点 ThreadNode *Firstnode(ThreadNode *p) { //循环找到最左下结点（不一定是叶结点） while(p->ltag == 0) p = p->lchild; return p; } //在中序线索二叉树中找到结点 p 的后继结点 ThreadNode *Nextnode(ThreadNode *p) { //右子树中最左下结点 if (p->rtag == 0) return Firstnode(p->rchild); else return p->rchild; //rtag == 1直接返回后继线索 } //对中序线索二叉树进行中序遍历（利用线索实现的非递归算法） 空间复杂度：O(1) void Inorder(ThreadNode *T) { for(ThreadNode *p = Firstnode(T); p != NULL; p = Nextnode(p)) visit(p); }

• 在中序线索二叉树中找到指定结点 *p 的中序前驱 pre

  • 若 p->ltag == 1，则 next = p->lchild
  • 若 p->ltag == 0，则 next = p的左子树中最右下结点

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  //找到以 p 为根的子树中，最后一个被中序遍历的结点 ThreadNode *Lastnode(ThreadNode *p) { //循环找到最右下结点（不一定是叶结点） while(p->ltag == 0) p = p->lchild; return p; } //在中序线索二叉树中找到结点 p 的前驱结点 ThreadNode *Prenode(ThreadNode *p) { //左子树中最右下结点 if (p->ltag == 0) return Firstnode(p->lchild); else return p->lchild; //rtag == 1直接返回后继线索 } //对中序线索二叉树进行逆向中序遍历 void RevInorder(ThreadNode *T) { for(ThreadNode *p = Lastnode(T); p != NULL; p = Prenode(p)) visit(p); }

• 在先序线索二叉树中找到指定结点 *p 的先序后继 next

  • 若 p->rtag == 1，则 next = p->rchild
  • 若 p->rtag == 0，则
    • 若 p 有左孩子，则先序后继为左孩子
    • 若 p 没有左孩子，则先序后继为右孩子

• 在先序线索二叉树中找到指定结点 *p 的先序前驱 pre

  • 若 p->ltag == 1，则 next = p->lchild
  • 若 p->ltag == 0，则
    • p 必有左孩子。由于先序遍历中左右子树中的结点只可能是根的后继，不可能是前驱。只能从头开始先序遍历找前驱。
    • 若改用三叉链表可以找到父节点
      • p 为左孩子，则 p 的父结点即为其前驱
      • p 为右孩子，
        • 其左兄弟为空，则 p 的父结点即为其前驱
        • 其左兄弟非空，则 p 的前驱为左兄弟子树中最后一个被先序遍历的结点

• 在后序线索二叉树中找到指定结点 *p 的后序前驱 pre

  • 若 p->ltag == 1，则 next = p->lchild
  • 若 p->ltag == 0，则 p 必有左孩子
    • 若 p 有右孩子，则后序前驱为右孩子
    • 若 p 没有右孩子，则后序前驱为左孩子

• 在后序线索二叉树中找到指定结点 *p 的先序后继 next

  • 若 p->rtag == 1，则 next = p->rchild
  • 若 p->rtag == 0，则
    • p 必有右孩子。由于先序遍历中左右子树中的结点只可能是根的后继，不可能是前驱。只能从头开始先序遍历找前驱。
    • 若改用三叉链表可以找到父节点
      • p 为右孩子，则 p 的父结点即为其前驱
      • p 为左孩子，
        • 其右兄弟为空，则 p 的父结点即为其前驱
        • 其右兄弟非空，则 p 的前驱为右兄弟子树中第一个被后序遍历的结点

树和森林

树的存储结构

• 双亲表表示法（顺序存储）

  • 用数组顺序存储各个结点。每个结点中保存数据元素、指向双亲结点（父节点）的“指针”。

  1 2 3 4 5 6 7 8 9

  #define MAX_TREE_SIZE 100 //树中最多结点数 typedef struct { //树的结点定义 ElemType data; //数据元素 int parent; //双亲位置域 } PTNode; typedef struct { //树的类型定义 PTNode nodes[MAX_TREE_SIZE]; //双亲表示 int n; //结点数 } PTree;

  • 优缺点：

    • 优点：找双亲（父结点）方便

    • 缺点：找孩子不方便，只能从头到尾遍历整个数组

    • 适用于“找父亲“多，”找孩子“少的应用场景。如：并查集

  • 双亲表示法也可表示森林，每棵树的根结点双亲指针 = -1。

• 孩子表示法（顺序存储 + 链式存储）

  • 用数组顺序存储各个节点。每个结点中保存数据元素、孩子链表头指针

  1 2 3 4 5 6 7 8 9 10 11 12

  struct CTNode { int child; //孩子结点在数组中的位置 struct CTNode *next; //下一个孩子 }; typedef struct { ElemType data; struct CTNode *firstChild; //第一个孩子 } CTBox; typedef struct { CTBox nodes[MAX_TREE_SIZE]; int n, r; } CTree;

  • 优缺点：
    • 优点：找孩子很方便
    • 缺点：找双亲（父结点）不方便，只能遍历每个链表
    • 适用于“找父亲“少，”找孩子“多的应用场景。如：服务流程树
  • 用孩子表示法存储森林，需要记录多个根的位置。

• 孩子兄弟表示法（链式存储）

  1 2 3 4

  typedef struct CSNode { ElemType data; struct CSNode *firstchild, *nextsibling; } CSNode, *CSTree;

  • 树的孩子兄弟表示法与二叉树类似，采用二叉链表实现。每个结点内保存数据元素和两个指针，但两个指针的含义和二叉树结点不同。
  • 存储森林时，森林中每棵树的根结点视为平级的兄弟关系。

树、森林和二叉树的转化

• 树转换为二叉树
  1. 先在二叉树中，画一个根结点。
  2. 按“树的层序”依次处理每个结点。
     • 处理一个结点的方法是：如果当前处理的结点在树中有孩子，就把所有孩子结点用右指针串成一串，并在二叉树中把第一个孩子挂在当前结点的左指针上。
• 森林转换为二叉树
  1. 先把所有树的根结点画出来，在二叉树中用右指针串成一串。
  2. 按“森林的层序”依次处理每个结点。
     • 处理一个结点的方法是：如果当前处理的结点在树中有孩子，就把所有孩子结点用右指针串成一串，并在二叉树中把第一个孩子挂在当前结点的左指针上。
• 二叉树转换为树

1. 先画出树的根结点
2. 从树的根结点开始，按“树的层序”恢复每个结点的孩子
   • 如何恢复一个结点的孩子，在二叉树中，如果当前处理的结点有左孩子，就把左孩子和一整串右指针拆下来，按顺序挂在当前结点的下面。

• 二叉树转换为森林
  1. 先把二叉树的根结点和一整串右指针拆下来，作为多棵树的根结点
  2. 按“森林的层序”恢复每个结点的孩子
     • 如何恢复一个结点的孩子，在二叉树中，如果当前处理的结点有左孩子，就把左孩子和一整串右指针拆下来，按顺序挂在当前结点的下面。

树、森林的遍历

• 树的先根遍历（深度优先遍历）。若树非空，先访问根结点，再依次对每棵子树进行先根遍历。

  1 2 3 4 5 6 7 8

  //树的先根遍历 void PreOrder(TreeNode *R) { if (R != NULL) { visit(R); //访问根结点 while (R 还有下一个子树 T) Prerder(T); //先根遍历下一棵子树 } }

• 树的后根遍历（深度优先遍历）。若树非空，先依次对每棵子树进行后根遍历，最后再访问根结点。

  1 2 3 4 5 6 7 8

  //树的后根遍历 void PostOrder(TreeNode *R) { if (R != NULL) { while (R 还有下一个子树 T) Prerder(T); //后根遍历下一棵子树 visit(R); //访问根结点 } }

  树的后根遍序列与这棵树相应二叉树的中序序列相同。

• 数的层次遍历（用队列实现）（广度优先遍历）

  1. 若树非空，则根结点入队
  2. 若队列非空，队头元素出队并访问，同时该元素的孩子依次入队
  3. 重复上一步直至队空

• 先序遍历森林。

  • 若森林为非空，则按如下规则进行遍历：
    • 访问森林中第一棵树的根结点
    • 先序遍历第一棵树中根结点的子树森林
    • 先序遍历除去第一棵树之后剩余的树构成的森林
  • 效果等同于依次对二叉树的先序遍历。

• 中序遍历森林。

  • 若森林为非空，则按如下规则进行遍历：
    • 中序遍历森林中第一棵树的根结点的子树森林
    • 访问第一棵树的根结点
    • 中序遍历除去第一棵树之后剩余的树构成的森林
  • 效果等同于依次对各个树进行后根遍历
  • 转化为二叉树后效果等同于依次对二叉树的中序遍历

哈夫曼树

• 结点的权：有某种现实含义的数值（如：表示结点的重要性等）
• 结点的带权路径长度：从树的根到该结点的路径长度（经过的边数）与该结点上权值的乘积
• 树的带权路径长度：树中所有叶结点的带权路径长度之和（WPL，Weighted Path Length）
• 在含有 n 个带权叶结点的二叉树中，其中带权路径长度（WPL）最小的二叉树称为哈夫曼树，也称最优二叉树。
• 哈夫曼树的构造：给定 n 个权值分别为 w₁，w₂，…，w_n 的结点。
  1. 将这 n 个结点分别作为 n 棵仅含一个结点的二叉树，构成森林 F。
  2. 构造一个新结点，从 F 中选取两棵根结点权值最小的树作为新结点的左、右子树，并且将新结点的权值置为左、右子树上根结点的权值之和。
  3. 从 F 中删除刚才选出的两棵树，同时将新得到的树加入 F 中。
  4. 重复以上两步，直至 F 中只剩下一棵树为止。
• 每个初始结点最终都成为叶结点，且权值越小的结点到根结点的路径长度越大。
• 哈夫曼树的结点总数为 2n-1。
• 哈夫曼树中不存在度为1的结点。
• 哈夫曼树并不唯一，但 WPL 必然相同且为最优。
• 固定长度编码——每个字符用相等长度的二进制位表示。
• 可变长度编码——允许对不同字符用不等长的二进制位表示。
• 若没有一个编码是另一个编码的前缀，则称这样的编码为前缀编码。非前缀编码有歧义。
• 由哈夫曼树得到哈夫曼编码——字符集中的每个字符作为一个叶子结点，每个字符出现的频度作为结点的权值，再构建哈夫曼树。

并查集

• 用互不相交的树，表示多个“集合”

  • 如何“查”到一个元素到底属于哪一个集合——从指定元素出发，找到根结点
  • 如何把两个集合“并”为一个集合——让一棵树成为另一棵树的子树即可

• “并查集”的存储结构：参考树的双亲表示法

  • 集合的两个基本操作——“并”和“查”
    • Find——“查”操作：确定一个指定元素所属集合
    • Union——“并”操作：将两个不相交的集合合并为一个
    • 并查集（Disjoint Set）是逻辑结构——集合的一种具体实现，只进行“并”和“查”两种基本操作

• “并查集”的代码实现——初始化

  1 2 3 4 5 6 7 8

  #define SIZE 13 int UFSets[SIZE]; //初始化并查集 void Initial(int S[]) { for (int i = 0; i < SIZE; i++) S[i] = -1; }

• “并查集”的代码实现——并、查

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  //Find “查”操作，找 x 所属集合（返回 x 所属根结点） 最坏时间复杂度：O(n) int Find(int S[], int x) { while(S[x] >= 0) //循环寻找 x 的根 x = S[x]; return x; //根的S[]小于0 } //Union “并”操作，将两个集合合并为一个 时间复杂度：O(1) void Union(int S[], int Root1, int Root2) { //要求 Root1 与 Root2 是不同的集合 if (Root1 == Root2) return; //将根 Root2 连接到另一根 Root1 下面 S[Root2] = Root1; }

• 优化思路：在每次 Union 操作构建树的时候，尽量不让树长高

  • 用根结点的绝对值表示树的结点总数（例如 -6 而不是 -1）
  • Union 操作，让小树合并到大树

  1 2 3 4 5 6 7 8 9 10 11 12

  //Union “并”操作，小树合并到大树 void Union(int S[], int Root1, int Root2) { if (Root1 == Root2) return; if (S[Root2] > S[Root1]) { //Root2 结点数更少 S[Root1] += S[Root2]; //累加结点总数 S[Root2] = Root1; //小树合并到大树 } else { S[Root2] += S[Root1]; //累加结点总数 S[Root1] = Root2; //小树合并到大树 } }

  该方法构造的树高不超过 log₂n+1

• 并查集的进一步优化

  • Find 操作的优化（压缩路径）：先找到根结点，再将查找路径上所有结点都挂到根结点下。

    1 2 3 4 5 6 7 8 9 10 11 12

    //Find “查”操作优化，先找到根结点，再进行“压缩路径” int Find(int S[], int x) { int root = x; while (S[root] >= 0) root = S[root]; //循环找到根 while (x != root) { //压缩路径 int t = S[x]; //t 指向 x 的父结点下 S[x] = root; //x 直接挂到根结点下 x = t; } return root; //返回根结点编号 }

    每次 Find 操作，先找根，再“压缩路径”，可使树的高度不超过 O(α(n))。α(n) 是一个增长很缓慢的函数，对于常见的 n 值，通常 α(n) <= 4，因此优化后并查集的 Find、Union 操作时间开销都很低。

定义和基本操作

• 串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为 S = ‘a₁a₂……a_n‘（n >= 0)。其中，S 是串名，单引号（有的地方用双引号）括起来的字符序列是串的值；a_i可以是字母、数字或其他字符；串中字符的个数 n 称为串的长度。n = 0时的串称为空串（用∅表示）

• 子串：串中任意个连续的字符组成 的子序列。

• 主串：包含子串的串。

• 字符在主串中的位置：字符在串中的序号。

• 子串在主串中的位置：子串的第一个字符在主串中的位置。

• 空串和空格串：

  • M = ‘’（空串）
  • N = ‘ ‘（三个空格符号组成的空格串，每个空格字符占1B）

• 串是一种特殊的线性表，数据元素之间呈线性关系。

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

• 串的基本操作，如增删改查等通常以子串为操作对象。

• 基本操作：

  • StrAssign(&T, chars)：赋值操作。把串T赋值为 chars。
  • StrCopy(&T, S)：复制操作。由串 S 复制得到串 T。
  • StrEmpty(S)：判空操作。若 S 为空串，则返回 TRUE，否则返回 FALSE。
  • StrLength(S)：求串长。返回串 S 的元素个数。
  • ClearString(&S)：清空操作。将 S 清为空串。
  • DestroyString(&S)：销毁串。将串 S 销毁（回收存储空间）。
  • Concat(&Y, S1, S2)：串联接。用 T 返回由 S1 和 S2联接而成的新串。
  • SubString(&Sub, S, pos, len)：：求子串。用 sub 返回串 S 的第 pos 个字符起长度为 len 的子串。
  • Index(S, T)：定位操作。若主串中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；否则函数值为0。
  • StrCompare(S, T)：比较操作。若 S > T，则返回值 > 0；若 S = T，则返回值 = 0；若 S < T，则返回值 < 0。

• 字符集：

  • 英文字符——ASCII字符集
  • 中英文——Unicode字符集
  • 基于同一个字符集，可以有多种编码方案。

存储结构

• 顺序存储

  • 静态数组实现（定长顺序存储）

    1 2 3 4 5

    #define MAXLEN 255 //预定义最大串长为255 typedef struct { char ch[MAXLEN]; //每个分量存储一个字符 int length; //串的实际长度 } SString;

  • 动态数组实现（堆分配存储）

    • 用完需要手动 free

    1 2 3 4 5 6 7

    typedef struct { char *ch; //按串长分配存储区，ch 指向串的基地址 int length; //串的长度 } HString; HString S; S.ch = (char *)malloc(MAXLEN * sizeof(char)); S.length = 0;

• 四种顺序存储方案：

  • 最后一个位置放 length
  • 第一个位置放 length
  • 没有 length，以 ‘\0’ 表示结尾
  • ch[0] 废弃不用，最后一个位置放 length

• 串的链式存储

  • 存储密度低：每个字符1B，每个指针4B

    1 2 3 4

    typedef struct StringNode { char ch; //每个结点存1个字符 struct StringNode *next; } StringNode, * String;

  • 存储密度提高

    1 2 3 4

    typedef struct StringNode { char ch[4]; //每个结点存多个字符 struct StringNode * next; } StringNode, * String;

• SubString(&Sub, S, pos, len)：：求子串。用 sub 返回串 S 的第 pos 个字符起长度为 len 的子串。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  #define MAXLEN 255 //预定义最大串长为255 typedef struct { char ch[MAXLEN]; //每个分量存储一个字符 int length; //串的实际长度 } SString; //求子串 bool SubString(SString &sub, SString S, int pos, int len) { //子串范围越界 if (pos + len - 1 > S.length) return false; for (int i = pos; i < pos + len; i++) SUb.ch[i - pos + 1] = S.ch[i]; Sub.length = len; return true; }

• StrCompare(S, T)：比较操作。若 S > T，则返回值 > 0；若 S = T，则返回值 = 0；若 S < T，则返回值 < 0。

  1 2 3 4 5 6 7 8

  int Strcompare(SString S, SString T) { for (int i = 1; i <= S.length && i <= T.length; i++) { if (S.ch[i] != T.ch[i]) return S.ch[i] - T.ch[i]; } //扫描过的所有字符都相同，则长度长的串更大 return S.length-T.length }

• Index(S, T)：定位操作。若主串中存在与串 T 值相同的子串，则返回它在主串 S 中第一次出现的位置；否则函数值为0。

  1 2 3 4 5 6 7 8 9 10 11 12

  int Index(SString S, SString T) { int i = 1, n = Strlength(S), m = StrLength(T); SString sub; //用于暂存子串 while(i <= n - m + 1) { SubString(sub, S, i, m); if(StrCompare(sub, T) != 0) ++i; else return i; //返回子串在主串中的位置 } return 0; //S 中不存在与 T 相等的子串 }

朴素模式匹配算法

• 字符串模式匹配：在主串中找到与模式串相同的子串，并返回其所在位置。

  • 子串——主串的一部分，一定能找到
  • 模式串——不一定能在主串中找到

• 朴素模式匹配算法：主串长度为 n，模式串长度为 m。将主串中所有长度为 m 的子串依次与模式串对比，直到找到一个完全匹配的子串，或所有子串都不匹配为止。

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  int Index(SString S, SString T) { int i = 1, j = 1; while(i <= S.length && j <= T.length) { if(S.ch[i] == T.ch[i]) { ++i; ++j; } else { i = i - j +2; j = 1; } } if(j > T.length) return i-T.length; else return 0; }

  最坏时间复杂度：O(nm)

KMP算法

KMP算法的实现

• 朴素模式匹配算法

  • 一旦发现当前这个子串中某个字符不匹配，就只能转而匹配下一个子串（从头开始）
  • 不匹配的字符之前，一定是和模式串一致的

• KMP算法中主串指针不回溯。

• 算法实现

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

  int Index_KMP(SString S, SString T, int next[]) { int i = 1, j = 1; while(i <= S.length && j <=T.length) { if(j == 0 || S.ch[i] == T.ch[j]) { ++i; ++j; //继续比较后继字符 } else j = next[j]; //模式串向右移动 } if(j > T.length) return i - T.length; //匹配成功 else return 0; }

  KMP算法，最坏时间复杂度 O(m+n)，其中，求 next 数组时间复杂度 O(m)

求 next 数组

• next 数组的作用：当模式串的第 j 个字符失配时，从模式串的第 next[j] 的继续往后匹配。
• 任何模式串都一样，第一个字符不匹配时，只能匹配下一个子串。因此，next[1] 都为0。
• 任何模式串都一样，第二个字符不匹配时，只能匹配下一个子串。因此，next[2] 都为1。
• 在不匹配的位置前边，划一条分界线。模式串一步一步往右移，直到分界线之前“能对上”，或模式串完全跨过分界线为止。此时 j 指向哪儿，next 数组值就是多少。

KMP算法的进一步优化

• 求 nextval 数组

  1 2 3 4 5 6 7

  nextval[1] = 0; for (int j = 2; j <= T; j++) { if (T.ch[next[j]] == T.ch[j]) nextval[j] = nextval[next[j]]; else nextval[j] = next[j]; }

  用 nextval 数组代替 next 数组进行计算。