0%

一、重点

  • 新增一个中断处理程序的步骤
    1. 编写新的中断处理程序
    2. 获取中断号m。
    3. 将新的中断处理程序装入内存或驻留内存,将新的中断处理程序的偏移地址和段地址保存到物理地址4*m和4*m+2处。

二、预备知识

三、寄存器

8086有14个寄存器:

  • 通用寄存器
    • 数据寄存器:ax、bx、cx、dx
    • 指针寄存器:sp、bp
    • 变址寄存器:si、di
  • 控制寄存器 ip、flag
  • 段寄存器:
    • 代码段 cs
    • 数据段 ds
    • 堆栈段 ss
    • 附加段 es

8086中[…]中的…只能是bx、bp、si、di。此时bp默认ss段,di默认es段,bx、si默认ds。

总线

物理地址的形成

为与先前的计算机兼容,现在的CPU还是使用段地址:偏移地址方式得到物理地址。

数据在计算机内的表现形式

  • 整数

    二进制补码表示。

    无符号数的补码还是原码。

    有符号数补码:

    ​ 从右向左,遇到第一个1后,反转剩余位。

标志寄存器

16位:flags 32位:eflags

标志位

  • 条件标志位 6个

    • SF

      符号标志

      结果是否为负,即最高位是否为1。

      对无符号数运算结果的记录,有符号数无意义。

    • ZF

      零标志

      相关指令执行后,结果是否为0。

    • OF

      溢出

      有符号数运算后是否产生溢出。

    • CF

      进位

      二进制无符号数进行运算时,记录进位或借位。

    • AF

      辅助

    • PF

      奇偶

      指令执行后,结果的所有bit中1的个数是否为偶数。

  • 控制标志位

    • DF

      方向

      是否从高地址向低地址处理字符串。

    • 中断允许

    • 跟踪

  • 系统标志位

影响标志寄存器的指令

有影响:

大都是运算指令,如add、sub、mul、div、inc、or、and、xor

无影响:

大多是传送指令,如mov、push、pop

还有call、ret

用到了标志位的指令

// TODO

操作标志寄存器

LAHF load ah from flags

SAHF store ah into flags

  • 传送
  • 进栈
  • 出栈

四、寻址方式

  • 寄存器寻址

    寄存器是操作数的存放地址。

    1
    inc bx
    1
    add ax,bx

    寄存器的位数决定了操作数的位数

  • 寄存器间接寻址

    格式: [R]

    注意:

    • 80x86中,R可以是8个32位通用寄存器(eax、ebx、ecx、edx、edi、esi、ebp、esp)中的任意一个,也可以是4个16位通用寄存器(bx、di、si、bp)中的一个,但不能是位的通用寄存器。
    • R是(bp、ebp、esp)时,默认段为ss。其他默认为ds。
  • 变址寻址

    格式:[R*F+V] [R*F+V] V[R*F]

    说明:R为寄存器(register),F(1、2、4、8)为比例因子(factor),V是位移量

    注意:

    • 当R为16位寄存器或esp时,F只能为1且必须省略不写。
    • V是有符号数、数值表达式、变量、标号,变量、标号取偏移地址。
    • V不可为寄存器。
  • 基址加变址寻址

    格式:[BR+IR*F+V] V[BR+IR*F] V[BR][IR*F]

    说明:BR基址寄存器 IR变址寄存器 F比例因子 V位移量

    注意:

    • 默认段寄存器由BR决定。
    • 使用16位寄存器时,BR只能是bx、bp,IR只能是si、di,F只能为1。bx时段默认为ds,bp默认为ss。
    • 使用32位寄存器时,BR可以选任意32位通用寄存器,IR可以选除esp外的任意通用寄存器。BR可以和IR相同,此时未带比例因子的为BR。当F为1时,在前面的为BR。ebp、esp时段为ss,其余为ds。
  • 立即寻址

    格式:n

    说明:n为常数或结果确定的表达式。

    示例:

    1
    mov word ptr [si],12h
    1
    mov eax,-12345678h
  • 直接寻址

    格式:段寄存器:[n] 变量 变量+常量

    说明:n为常数或数值表达式,表示偏移地址。

    注意:

    • 必须要加段寄存器

    示例:

    1
    inc buf
    1
    mov ds:[20h],cl

寻址注意事项

  • 源操作数与目的操作数不能都是存储器方式的。
  • 立即数没有类型,不含变量的存储器方式表示的操作数类型不明确,因此必须显示指明类型。
  • 如果类型都是明确的,那类型必须匹配。
  • 段超越
    • 取指令(not等)只能用cs段
    • 压栈、出栈只能用ss段
    • 串操作中的目的串只能用es段

五、宏汇编语言

表达式

  • 常量

    用伪指令equ或=来定义

  • 数值表达式

    • 算术运算
    • 逻辑运算
    • 大小关系运算
  • 变量

    用db、dw、dd等数据定义伪指令来定义

    属性:

    • 所属段
    • 偏移地址
    • 类型(字节、字、双字等)

    格式:变量名 数据定义伪指令 表达式[,…]

    注意:

    表达式可以为:

    • 数值
    • ASCII字符串
  • 标号

    属性:

    • 段属性
    • 偏移地址
    • 类型 NEAR FAR
  • 地址表达式

    • 属性定义算符
      • 类型运算符 PTR
      • 定义类型运算符 THIS 指定下一个能分配的存储单元的类型
    • 属性分离算符
      • 取段址算符 SEG
      • 取偏移地址算符 OFFSET
      • 取类型算符 TYPE
    • 其他算符
      • LENGTH 取变量所含的数据存储单元个数算符
      • SIZE 取变量所含的数据存储区大小算符
      • HIGH LOW 字节分离算符

机器指令语句

  • 数据传送

    • 一般数据传送

      • 传送

        • 一般传送 MOV
        • 有符号数传送 MOVSX
        • 无符号数传送 MOVZX
      • 数据交换

        • 一般数据交换 XCHG

          源操作数不能是立即数

        • 字节交换 BSWAP

        • 交换加 XADD

      • 查表转换

        • XLAT

          将(bx)(ebx)为首址,(al) 为位移量的字节存储在al中

    • 地址传送

      • 传送偏移地址 lea (load effective address)
      • 传送偏移地址及数据段首址地址 LDS
      • 传送偏移地址及附加数据段 LES
  • 算术运算

      • inc
      • add
      • dec
      • neg 求补 每一位取反后+1
      • sub
      • cmp
      • 有符号乘 imul
      • 无符号乘 mul
      • IDIV
      • DIV
    • 符号扩展
      • CBW
      • CWD
      • CWDE
      • CDQ
  • 位操作

    • 逻辑运算

      • NOT

      • AND

      • TEST

        源操作数与目的操作数做and,然后置标志位

      • BT

        根据位编号对目的操作数中的位来测试

        1
        bt eax, 52
      • OR

      • XOR

    • 移位

      • SAL

      • SHR

        逻辑右移,最高位补0

      • SAR

        算术右移,最高位不变

      • ROL

      • ROR

      • RCL

        带进位的循环左移

      • RCR

    • 双精度移位指令

伪指令语句

也称汇编控制指令

  • 处理器选择

    .386 .8086

  • 数据定义

    • db
    • dw
  • 符号定义

    • 等价伪指令 equ
    • 等号 =
    • 定义符号名 label
  • 段定义

    • 段定义

      1
      2
      3
      segment_name segment 
      ...
      segment_name ends

      使用类型:

      use16 use32

    • 假定 assume

    • 置汇编地址计数器 $

      ​ ORG 设置汇编地址计数器$的值

  • 过程定义

  • 程序模块的定义与通信伪指令

  • 宏定义

  • 条件汇编

  • 格式控制、列表控制及其他功能伪指令

常用DOS系统功能调用

  • 1号调用 键盘输入一个字符,存入al
  • 2号调用 输出一个dl中的字符到显示器
  • 9号调用 将ds:dx 指向的以$结尾的字符串送到显示器显示

六、程序设计的基本方法

顺序

分支

转移指令

  • 条件转移

    • 简单条件转移
    • 无符号数条件转移
    • 有符号数条件转移
    • 循环转移
  • 无条件转移

    可以段内,可以段间

    JMP CALL RET INT IRET

循环

子程序

定义:

1
2
3
4
dtob proc near
...
...
dtob endp

调用:

call

返回:

ret

七、其他方法和技术

字符串操作

目的段只允许在当前附加段中,所以程序中一定要定义附加数据段,最简单的办法就是让当前数据段与附加数据段重合。

  • 传送 MOVS

    作用:DS:[SI]->ES:[DI]

    所以使用该指令前要设置好DS,SI,ES,DI。

  • 搜索 SCAS

    在ES:[DI]开始的串中搜索AL中存放的字符。

  • 比较 CMPS

    可带前缀REPE/REPZ REPNE/REPNZ

    前者CX/ECX不=0,ZF=1 未比较完且两串元素相等时继续比较。

    后者CX/ECX不=0,ZF不=1,未比较完且两串元素不相等时继续比较。

  • 取 LODS

    DS:[SI]->AL

  • 存 STOS

    AL->DS:[SI]

重复前缀:

  • REP
  • REPE REPZ
  • REPNE REPENZ

宏指令

  1. 宏定义
  2. 宏调用
  3. 宏展开

定义:

1
2
3
4
name macro
...
...
name endm

调用:直接用宏名调用。

传参:

  • 带间隔符的参数

    < > 尖括号括住

  • 数字参数

    %

  • 宏参数的连接

    &

  • 宏体中的变量与标号

    local

重复汇编伪指令:

  • 给定次数的重复汇编
1
2
3
4
rept 26
db char
char = char+1
endm
  • 不定次数的重复汇编

    IRP

    IRPC

条件汇编伪指令:

1
2
3
4
5
IF

ELSE

ENDIF

引入宏库:

1
include macro.lib

模块化程序

  • 组合方式
    • 定位方式
    • 组合方式
    • ‘类别’
  • 通信方式

八、输入/输出和WIN32编程

九、中断

内中断

中断源:

中断向量表:

​ 存储了中断处理程序的入口地址

  1. 编写中断处理程序
  2. 安装(复制到固定地址处)
  3. 设置中断向量表

外中断

十、嵌入式

名词

Soc System on Chip 片上系统

BSP Board Support Package

USB Universal Serial Bus 通用串行总线

$I^2C$ Inter-Integrated Circuit

MMU Momory Manager Unit 内存管理单元

概述

  • 嵌入式系统定义:

    应用为中心,以计算机技术为基础,软件、硬件可裁剪,适应应用系统对功能、可靠性、成本、体积、功耗严格要求的专用计算机系统。

  • 组成:

    • 嵌入式微处理器
    • 外围硬件设备
    • 嵌入式操作系统
    • 用户的应用程序
  • 嵌入式系统的特点

    • 关注成本

    • 实时性

    • 使用嵌入式操作系统 EOS Embedded Operating System

    • 减少软件的瞬时故障

    • 低功耗

    • 运行环境

    • 系统资源有限

    • 在ROM中存放所有程序的目标代码

    • 处理器选择多样化

      • 微处理器 MPU
      • 微控制器 MCU
      • 数字信号处理器 DSP Digital Signal Processor
      • 片上系统 SoC System On Chip
    • 专用开发工具和方法设计

    • 软件的固件化

      嵌入式系统是一个软硬件高度结合的产物,为了提高执行速度和系统可靠性,嵌入式系统的软件一般都固化在存储器西片或处理器芯片中。

    • 构成

      • 核心芯片

        • 嵌入式微处理器

          具有32位以上的处理器,性能较高,价格较贵。

        • EMCU

          又称单片微型计算机 Single Chip Microcomputer,低廉的价格,优良的性能。

        • EDSP

          强大的数据处理功能和高运行速度。

        • ESoC

          客户定制的,面向特定用途的。

      • 存储器

        • 易失性存储器

          • SRAM

            最早最成熟

          • DRAM

            高密度高带宽

        • 非易失性存储器

          • OTP
          • ROM
          • EEPROM
          • Flash
      • 常规外设及其接口

      • 专用外设及其接口

      • 嵌入式操作系统

      • 板级支持包 BSP Board Support Package

        让硬件支持操作系统

      • 应用程序

      • 嵌入式开发工具

设计方法

  • 单片机

    汇编语言编写相应的程序即可。

  • 嵌入式处理器系统

    • 处理器选型
      • 够用
      • 适用
      • 成本
      • 功耗
      • 软件开发工具
      • 内置调试工具
      • 评估板
    • 操作系统
    • 编程语言
  • 测试工具

    • 内存分析工具
    • 性能分析
    • GUI测试
    • 覆盖分析
  • 测试策略

    • 单元测试

    • 集成测试

    • 系统测试 确认测试

      所有的系统测试和确认测试都要在目标环境下进行

处理器

标准的指令集架构有两大体系,精简指令集架构 RISC Reduced Instruction Set Computer,复杂指令集架构 CISC Complex Instruction Set Computer。

处理器采用两大体系结构冯·诺依曼和哈佛结构。

  • 嵌入式系统对微处理器的要求
    • 实时性
    • 技术密集
    • 专用紧凑
    • 安全可靠

ARM处理器

  • ARM内核命名规则

  • ARM处理器结构

    • RISC体系结构 Reduced Instruction Set Computer

      只有加载和存储指令可以访问存储器

      数据处理指令只对寄存器的内容进行操作

    • Thumb

      在性能和代码大小之间提供了出色的折中

      7种处理器模式:

      • 用户模式
      • FIQ 中断模式
      • IRQ 中断模式
      • 管理模式
      • 终止模式
      • 系统模式
      • 未定义
    • 寄存器

      37个寄存器:

      • 程序计数器 PC

      • 程序状态寄存器

        当前程序状态寄存器 CPSR

        备份的程序状态寄存器 SPSR

  • 具体的ARM7TDMI Thumb Debug Multiply Ice

FPGA

现场可编程门阵列 Field Programmable Gate Array FPGA

  • FPGA结构资源

    • 硬件资源

    • 软件资源

    • IP核资源

      IP核可以解析为拥有知识产权的设计,可以通过授权而应用的通用模块。

SoC

特点:

  1. 设计时大量使用可复用的IP
  2. 其制成

克服前后端相分离的弊病。

SoPC:

System on Programmable Chip 片上可编程系统

多核处理器:

片上多核处理器 CMP Chi Multi-Processor

常用架构:

SMP Symmetric Multiprocessing

AMP

多核处理器需要考虑的问题:

  • 节点间通信方式

    • 基于共享内存的访问方式
    • 基于消息传递的访问方式
  • 任务调度策略

    • 静态调度
    • 动态调度
  • cache一致性

    cache作用:协调处理器和存储器速度不匹配的问题。

    协议机制:

    • 基于监听
    • 基于目录
  • 系统异构性

    如大端小端

存储器

  • 嵌入式系统的存储器选择

    选择原则:

    • 内部存储器与外部存储器
    • 引导存储器
    • 配置存储器
    • 程序存储器
    • 数据存储器
    • 易失性存储器和非易失性存储器
    • 串行存储器与并行存储器
  • 可擦除可编程ROM EPROM

  • 在线编程和擦除 E^2PROM

  • Flash 闪存

    之所以称为闪存,是因为用电擦除且能擦除整个存储矩阵或部分存储矩阵,通过公共源极或公共衬底加高压实现,速度很快。

    将程序和数据写入到Flash存储器中的过程叫编程

外围设备和IO接口

  • LCD Liquid Crystal Display

    体积小 重量轻 辐射低

  • 常见输入输出接口类型

    • $I^2C$ Inter-Integrated Circuit

      通过串行数据线SDL 和串行时间线 SCL Serial Clock Line连接嵌入式处理器与外设IC设备。

    • $I^2S$ Inter-IC Sound

    • CAN Controller Area Network

      稳定性不错(知道这个就行了)

    • USB Universal Serial Bus

    • 红外线

      方向性

    • 蓝牙

      球状

    • 以太网 (不考)

  • 嵌入式最小系统

    1. 处理器
    2. 内存
    3. 时钟
    4. 电源和复位
  • 驱动程序与寄存器

    直接利用寄存器与周边沟通的程序,也叫驱动程序。

    获取周边的方式:

    内存映像

    IO地址

操作系统

  • 特征

    1. 小巧
    2. 实时性
    3. 可装卸
    4. 固化代码
    5. 弱交互性
    6. 强稳定性
    7. 统一的接口
  • 实时操作系统的常用术语

  • 常用的操作系统

    • VxWorks
    • QNX 开源
    • Nucleus PLUS 软件组件构成OS
    • uC/OS

问题

  • arm处理器流水线

    ARM7 3级流水线 取址 译码 执行

    ARM9 5

    ARM10 6

十一、更多

  • 汇编源程序 .asm

    汇编 .obj

    link .exe

  • see lang/assembly.md

    1. jmp 无条件转移

    2. 立即数不能直接送入段寄存器

    3. 代码段中有标号时,一定要用assume指出cs

    4. macro 宏定义

    5. 1
      2
      3
      ; 下面两句不要忘记写
      mov ax,data
      mov ds,ax
    6. lodsb ; 从输入串中(ds:[di])取一个字符->al

      另:lodsw

    7. 2号功能:显示输出 (dl) = 输出字符

      1
      2
      3
      4
      5
      out1    macro a
      mov dl,a
      mov ah,2
      int 21h
      endm
    8. 10号功能:带缓冲的键盘输入 ds:[dx]=缓冲区首址

      1
      2
      3
      4
      5
      scan    macro a
      lea dx,a
      mov ah,10
      int 21h
      endm
    9. 清屏

      1
      2
      mov ax,3
      int 10h
    10. ?表示所定义的变量无特定初值

    11. 常量不会存储在数据段里

    12. 乘除指令

    • 有符号乘

      1
      imul opd,ops

      ​ opd为16/32位的寄存器,ops为同类型的寄存器、存储器操作数或立即数

      1
      imul opd,ops,n

      opd为16/32位的寄存器,ops为同类型的寄存器、存储器操作数,n为立即数

      1
      imul ops

      ops为寄存器或存储器操作数,代表x*ops,x类型由ops决定

      (al)*(ops)->ax

      (ax)*(ops)->dx,ax // dx高位,ax低位

      (eax)*(ops)->edx,eax

      若高位不是低位的符号扩展,则cf=1、of=1,否则cf=0、of=1

    • 无符号乘

      1
      mul ops

      参与运算的源操作数及结果都是无符号数

    • 有符号除

      1
      idiv ops

      字节除法:(ax)/(ops)->al(商),ah(余数)

      字除法:(dx,ax)/(ops)->ax,dx

      双字除法:(edx,eax)/(ops)->eax,edx

      前面的存放高位,后面的存放低位

      余数与被除数同号

    • 无符号除

      1
      div ops

      字节除法:(ax)/(ops)->al(商),ah(余数)

      字除法:(dx,ax)/(ops)->ax,dx

      双字除法:(edx,eax)/(ops)->eax,edx

  • 8086 CPU 寄存器简介

  • ip、eip不能直接作为操作数

  • 栈操作,操作数类型必须为字(word)

debug使用

  • R

    查看、改变寄存器内容

  • D

    查看内存(存储器)中的内容

  • E

    改写内存中的内容

  • U

    机器->汇编

  • T

    执行机器指令

  • A

    以汇编指令的格式在内存中写入机器指令

LEC 1 概述

解决问题的三要素:输入 输出 算法

数据结构

输入、输出与数据结构直接相关。

数据结构时数据之间的逻辑关系、数据在计算机上的存储方式、数据的操作。

数据结构与算法设计是密切相关的。

算法

算法是为了求解问题而给出的指令序列。

一般特性

正确性
有效性
确定性
有穷性

算法效率

计算时间
存储空间
网络带宽

LEC 2 算法渐进分析

一般我们不必花大力气算出算法的精确运行时间,我们关心的是在大规模的输入下,算法的运行时间是如何随着输入规模的增大而变化的。此时,我们可以忽略低阶项和常量,使用渐进分析。
开销函数的估计是相对的而不是绝对的,开销函数的阶的增长决定了开销的大小。

渐进符号

$O$ 渐进上界
$Ω$ 渐进下界
$Θ$ 渐进紧确界

分析实例

矩阵求和

$O(n)$ $n=k^2$ (k 为矩阵维度)

插入排序

最好 O(n) 最坏 O(n^2)

合并排序

$O(nlgn)$

LEC 3 递归关系

许多算法,时间开销函数都可以用递归关系来描述。

置换法

猜想出一个表达式,验证表达式的正确性。

递归树

将迭代过程展成树的形式,分析树的每一层的消耗,然后求和。

迭代法

根据迭代公式,利用数学方法求解。

主方法

主方法依赖如下的主定理:

可以根据主定理方便求解效率,但有真空地带。

LEC 4 线性时间的排序法

基于比较的排序的开销下限

这一节先分析了基于比较的方法的排序的开销下限,我们通过判定树模型证明下限为$nlgn$。要打破这个下限,就要寻找非比较的排序方法,即:

计数排序

基本思想是排序指定范围内(0~k)的数,使用大小分别为n、k、n的数组a、b、c。根据 c 中小于 x 的个数,将元素放到 b 的指定位置。

基数排序

基本思想是根据数字每一位的大小进行排序。

桶排序

基本思想是将待排序元素放入桶中,每个桶分别排序,桶之间保持顺序。

LEC 5 分治法

分治法的思想,将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时的三个步骤:

分解步骤将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小。

解决步骤递归的求解子问题,如果子问题的规模足够小,则停止递归直接求解。

合并步骤将子问题的解组合成原问题的解。

应用

二分搜索

归并排序

最大子数组问题

矩阵乘法的 Strassen 算法

Strassen 算法的运行时间的递归式为:

$T(n)=7T(n/2)+Θ(n^2)$

这里 a=7,b=2,$f(n)=Θ(n^2)$,即$n^{log_ba}=n^{log_27}$。存在ε=0.8有$f(n)=O(n^{lg7-ε})$。符合主定理的情况1,则$T(n)=Θ(n^{lg7})$。

最近点对算法

最近点对算法的递归式为:

$T(n)=2T(n/2)+O(n)$

这里 a=2,b=2,$f(n)=O(n)$,即$n^{log_ba}=n^{log_22}=n$。符合主定理的情况2,则$T(n)=O(nlgn)$。

LEC 6 随机化算法

雇佣关系

快速排序

随机化算法的分类

Las Vegas 算法 :总能给出正确的解或者无解。

Monte Carlo 算法 :大多数给出正确解,错误率可以控制在一定程度上。

如检查两个长串是否相同,直接比较为 Las Vegas 算法,验证指纹则为 Monte Carlo 算法。

LEC 7 统计算法

LEC 8 动态规划

简介

动态规划(dynamic programming),这里的 programming 不是编程的意思,而是表格的意思,意味着将求出的子问题的解存到表格中,以便下次用到时直接查表取出。动态规划与分治法类似,都是通过组合子问题的解来求解原问题。是典型的以空间换取时间的时空权衡的例子。

原理

适合用动态规划求解的问题的两个要素:最优子结构子问题重叠

步骤

动态规划求解的一般步骤:

(1)刻画一个最优解的结构特征。

(2)递归地定义最优解的值。

(3)计算最优解的值,通常采用自底向上的方法。

(4)利用计算出的信息构造一个最优解。

应用

动态规划有着很规范的范式,一般按照步骤来。

最长公共子序列

刻画最长公共子序列的特征

我们很容易用“剪切-粘贴”技术证明:两个序列的 LCS 包含这两个序列前缀的 LCS。即 LCS 问题拥有最优子结构。

一个递归解

计算 LCS 的长度

我们使用两个表 c 和 b。

Snipaste_2020-05-05_18-20-06

构造 LCS

沿着表 b 的箭头方向,从右下角开始,打印出公共元素即可。

作业排程

钢条切割

矩阵链乘法

矩阵链乘法就是寻找一个最优括号化方案,使得需要的标量乘法计算次数最少。

最优括号化方案的结构特征

最优括号化方案拥有最优子结构,我们可以使用“剪切-粘贴”方法很容易得证明,最优括号化方案包含其子链的最优括号化方案。

一个递归求解方案

计算最优代价

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MATRIX-CHAIN-ORDER(p)
n = p.length-1
let m[1..n 1..n] and s[1..n-1,2..n] be new table
for i = 1 to n
m[i,i] = 0
for l = 2 to n
for i = 1 to n-l+1
j = i+l-1
m[i,j] = ∞
for k = i to j-1
q = m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]
if q < m[i,j]
m[i,j] = q
s[i,j] = k
return m and s

构造最优解

设计一个算法输出括号化方案。

LEC 9 贪心算法

简介

贪心算法和动态规划算法一样,通常用来求解最优化问题

贪心算法的思想是每一步都选择局部最优解,很多时候这种方法能得到最优解,而且速度比动态规划快很多,也更简单。

原理

并没有确定的方法简单证明一个问题是否适用贪心算法。

贪心选择性质最优子结构是两个关键要素。

步骤

(1)将最优化问题转化为这样的形式:对其做出一次选择后,只剩下一个子问题需要求解。

(2)证明作出贪心选择后原问题总是存在最优解。即贪心选择总是安全的。

(3)证明做出贪心选择后剩余的子结构满足性质:其最优解与贪心选择组合即可得到原问题的最优解,这样就得到了最优子结构。

应用

活动选择问题

霍夫曼编码

最小生成树

单源最短路径的 Dijkstra 算法

LEC 10 图算法

图的表示和存储方式

邻接链表 邻接矩阵

邻接链表因为在表示稀疏图时非常紧凑而成为通常的选择。

在稠密图的情况下,我们可能倾向于使用邻接矩阵表示法。快速判断任意两个节点之间是否有边相连,可能也需要使用邻接矩阵表示法。

LEC 11 最小生成树

LEC 12 单源最短路径

单源最短路径

单源最短路径问题是从源结点到其它结点的最短路径问题。

一般解决方案是 Bellman-Ford 算法,其允许负值权重的边。当存在负值环路时,算法返回不存在问题的解,否则返回最短路径及权重。思想是通过松弛操作逐渐降低权重。

还有著名的 Dijkstra 算法,其要求所有边的权重都为非负。其利用了贪心算法的思想,每次都选择最短路径。

LEC 13 全成对最短路径

全点对最短路径

全点对最短路径问题是从任一结点到其余结点的最短路径的问题。

如果不存在负值权重的边,可以用 Dijkstra 算法对每个结点进行操作。

还有一种利用动态规划思想的 Floyd-Warshall 算法,其要求可以存在负值权重的边,但不可以存在负值回路。

排序方法 平均时间复杂度 最坏时间复杂度
插入排序 $O(n^2)$ $O(n^2)$
合并排序 $O(nlgn)$ $O(nlgn)$
快速排序 $O(nlgn)$​ $O(n^2)$
随机快速排序 $O(nlgn)$ -
计数排序 $O(n+k)$ -
基数排序 $O(d(n+k))$ $O(d(n+k))$
桶排序 $O(n)$ -

单源最短路径

单源最短路径问题是从源结点到其它结点的最短路径问题。

一般解决方案是 Bellman-Ford 算法,其允许负值权重的边。当存在负值环路时,算法返回不存在问题的解,否则返回最短路径及权重。思想是通过松弛操作逐渐降低权重。

还有著名的 Dijkstra 算法,其要求所有边的权重都为非负。其利用了贪心算法的思想,每次都选择最短路径。

全点对最短路径

全点对最短路径问题是从任一结点到其余结点的最短路径的问题。

如果不存在负值权重的边,可以用 Dijkstra 算法对每个结点进行操作。

还有一种利用动态规划思想的 Floyd-Warshall 算法,其要求可以存在负值权重的边,但不可以存在负值回路。

图的表示和存储方式

邻接链表 邻接矩阵

邻接链表因为在表示稀疏图时非常紧凑而成为通常的选择。

在稠密图的情况下,我们可能倾向于使用邻接矩阵表示法。快速判断任意两个节点之间是否有边相连,可能也需要使用邻接矩阵表示法。

简介

贪心算法和动态规划算法一样,通常用来求解最优化问题

贪心算法的思想是每一步都选择局部最优解,很多时候这种方法能得到最优解,而且速度比动态规划快很多,也更简单。

原理

并没有确定的方法简单证明一个问题是否适用贪心算法。

贪心选择性质最优子结构是两个关键要素。

步骤

(1)将最优化问题转化为这样的形式:对其做出一次选择后,只剩下一个子问题需要求解。

(2)证明作出贪心选择后原问题总是存在最优解。即贪心选择总是安全的。

(3)证明做出贪心选择后剩余的子结构满足性质:其最优解与贪心选择组合即可得到原问题的最优解,这样就得到了最优子结构。

应用

活动选择问题

霍夫曼编码

最小生成树

单源最短路径的 Dijkstra 算法

简介

动态规划(dynamic programming),这里的 programming 不是编程的意思,而是表格的意思,意味着将求出的子问题的解存到表格中,以便下次用到时直接查表取出。动态规划与分治法类似,都是通过组合子问题的解来求解原问题。是典型的以空间换取时间的时空权衡的例子。

原理

适合用动态规划求解的问题的两个要素:最优子结构子问题重叠

步骤

动态规划求解的一般步骤:

(1)刻画一个最优解的结构特征。

(2)递归地定义最优解的值。

(3)计算最优解的值,通常采用自底向上的方法。

(4)利用计算出的信息构造一个最优解。

应用

动态规划有着很规范的范式,一般按照步骤来。

最长公共子序列

刻画最长公共子序列的特征

我们很容易用“剪切-粘贴”技术证明:两个序列的 LCS 包含这两个序列前缀的 LCS。即 LCS 问题拥有最优子结构。

一个递归解

计算 LCS 的长度

我们使用两个表 c 和 b。

Snipaste_2020-05-05_18-20-06

构造 LCS

沿着表 b 的箭头方向,从右下角开始,打印出公共元素即可。

作业排程

钢条切割

矩阵链乘法

矩阵链乘法就是寻找一个最优括号化方案,使得需要的标量乘法计算次数最少。

最优括号化方案的结构特征

最优括号化方案拥有最优子结构,我们可以使用“剪切-粘贴”方法很容易得证明,最优括号化方案包含其子链的最优括号化方案。

一个递归求解方案

计算最优代价

伪代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
MATRIX-CHAIN-ORDER(p)
n = p.length-1
let m[1..n 1..n] and s[1..n-1,2..n] be new table
for i = 1 to n
m[i,i] = 0
for l = 2 to n
for i = 1 to n-l+1
j = i+l-1
m[i,j] = ∞
for k = i to j-1
q = m[i,k]+m[k+1,j]+p[i-1]*p[k]*p[j]
if q < m[i,j]
m[i,j] = q
s[i,j] = k
return m and s

构造最优解

设计一个算法输出括号化方案。

分治法的思想,将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解。

分治模式在每层递归时的三个步骤:

分解步骤将问题划分为一些子问题,子问题的形式与原问题一样,只是规模更小。

解决步骤递归的求解子问题,如果子问题的规模足够小,则停止递归直接求解。

合并步骤将子问题的解组合成原问题的解。

分析分治算法

应用

归并排序

最大子数组问题

矩阵乘法的 Strassen 算法

Strassen 算法的运行时间的递归式为:

$T(n)=7T(n/2)+Θ(n^2)$

这里 a=7,b=2,$f(n)=Θ(n^2)$,即$n^{log_ba}=n^{log_27}$。存在ε=0.8有$f(n)=O(n^{lg7-ε})$。符合主定理的情况1,则$T(n)=Θ(n^{lg7})$。

最近点对算法

最近点对算法的递归式为:

$T(n)=2T(n/2)+O(n)$

这里 a=2,b=2,$f(n)=O(n)$,即$n^{log_ba}=n^{log_22}=n$。符合主定理的情况2,则$T(n)=O(nlgn)$。

数据结构研究组织大量数据的方法,算法分析则是对算法运行时间的评估。

算法是为求解一个问题需要遵循的、被清除地指定的简单指令的集合。

数据结构在计算机科学界至今没有一个标准的定义

普遍认可的算法的定义:算法是解决特定问题求解步骤的描述。

算法的特性:

  • 有穷性
  • 确定性
  • 可行性
  • 输入
  • 输出

引论

  • 数学知识

    级数:

  • 证明方法

    • 归纳法
    • 反证法
  • 递归简论

    • 设计递归的基本法则:
      1. 基准情形
      2. 不断推进
      3. 设计效益:假设所有的递归调用都能运行。
      4. 合成效益法则:不要做重复性工作。

算法分析

  • 数学基础

    $O(f(N))$ 上限

    $Ω(f(N))$ 下限

    $Θ(f(N))$ 相等

    $o(f(N))$ 小于

表、栈和队列

    • 数组
    • 链表
  • 中缀表达式转换为后缀表达式:

    中缀表达式可以通过栈转换成后缀表达式,P54

后缀表达式转换成表达式树同样借助栈:P71

扫描后缀表达式,若遇到operator,构造单节点树,入栈;

若遇到operand,从栈中弹出两棵树,以operand为根,合并弹出的两棵树,将得到的树入栈

时间复杂度=表达式的长度

  • 队列

    1
    2
    3
    4
    5
    struct QNode {
    ElementType *Data; /* 存储元素的数组 */
    Position Front, Rear; /* 队列的头、尾指针 */
    int MaxSize; /* 队列最大容量 */
    };
    • CreateQueue()
    • IsFull()
    • IsEmpty()
    • Enqueue()
    • Dequeue()
    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
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    // 队列的数组实现
    // Created by aoyun on 2019/11/24.
    //
    #include <stdbool.h>
    #include <stdio.h>
    #include <stdlib.h>

    #define ERROR -1

    typedef int ElementType;
    typedef int Position;
    struct QNode {
    ElementType *Data; /* 存储元素的数组 */
    Position Front, Rear; /* 队列的头、尾指针 */
    int MaxSize; /* 队列最大容量 */
    };
    typedef struct QNode *Queue;

    static Queue CreateQueue(int MaxSize) {
    Queue Q = (Queue) malloc(sizeof(struct QNode));
    Q->Data = (ElementType *) malloc(MaxSize * sizeof(ElementType));
    Q->Front = Q->Rear = -1; // ZJU代码有错
    Q->MaxSize = MaxSize;
    return Q;
    }

    static bool IsFull(Queue Q) {
    return ((Q->Rear + 1) % Q->MaxSize == Q->Front);
    }

    /**
    *
    * @param Q
    * @param X
    * @return 是否入队成功,队列已满会失败
    */
    static bool AddQ(Queue Q, ElementType X) {
    if (IsFull(Q)) {
    printf("队列满");
    return false;
    } else {
    Q->Rear = (Q->Rear + 1) % Q->MaxSize; // 队尾向后移
    Q->Data[Q->Rear] = X;
    return true;
    }
    }

    static bool IsEmpty(Queue Q) {
    return (Q->Front == Q->Rear);
    }

    ElementType DeleteQ(Queue Q) {
    if (IsEmpty(Q)) {
    printf("队列空");
    return ERROR;
    } else {
    Q->Front = (Q->Front + 1) % Q->MaxSize;
    return Q->Data[Q->Front];
    }
    }

    int main() {
    Queue Q = CreateQueue(4);
    AddQ(Q, 1);
    AddQ(Q, 2);
    AddQ(Q, 3);
    AddQ(Q, 4);
    printf("\n%d", DeleteQ(Q));
    }

  • 二叉树

    最多两个子节点

  • 二叉查找树

    每一个根节点,左子树的所有元素比根节点小,右子树相反。

  • AVL树

    有条件的平衡树

  • 伸展树

  • 树的遍历

  • B-树

    在2m阶B树中关键码个数n与B树高度h之间的关系为 $h≤log_m((n+1)/2)+1$

散列

  • 散列函数
  • 分离链接法
  • 开放定址法
  • 再散列
  • 可扩散列

优先队列

  • 二叉堆

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /*----------- 建造最大堆 -----------*/
    /* 下滤:将H中以H->Data[p]为根的子堆调整为最大堆 */
    void PercDown(MaxHeap H, int p) {
    int Parent, Child;
    ElementType X;

    X = H->Data[p]; /* 取出根结点存放的值 */
    for (Parent = p; Parent * 2 <= H->Size;) {
    Child = Parent * 2;
    if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1]))
    Child++; /* Child指向左右子结点的较大者 */
    if (X >= H->Data[Child])
    break; /* 找到了合适位置 */
    else /* 下滤X */
    H->Data[Parent] = H->Data[Child];
    Parent = Child;
    }
    H->Data[Parent] = X;
    }
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    void MaxDown(MaxHeap H, int p) {
    int Parent, Child; // Parent-父节点在数组中的指针 Child-子节点在数组中的指针
    int X;
    X = H->Data[p];
    for (Parent = p; Parent * 2 < H->Size;) { // 从上往下,找p的正确位置
    Child = Parent * 2; // Child在Parent*2处
    if ((Child != H->Size) && (H->Data[Child] < H->Data[Child + 1])) {
    Child++; // 找到较大的Child
    }
    if (X > H->Data[Child]) { // p就是正确位置
    break;
    } else { // 子节点更大,把子节点数值赋值到父节点位置
    H->Data[Parent] = H->Data[Child];
    }
    Parent = Child; // 父节点转到Child位置,重新开始新的一轮寻找父节点正确位置的过程
    }
    H->Data[Parent] = X;
    }
  • 应用

  • d-堆

  • 左式堆

  • 斜堆

  • 二项队列

排序

  • 冒泡排序

  • 选择排序

  • 插入排序

    向扑克牌一样,把新元素插入到正确的位置

  • 希尔排序

    缩小增量的插入排序

  • 堆排序

    1. 堆的构造
    2. 下沉排序

    利用堆的性质进行排序

  • 归并排序

    分治。先分,分成小单位;再治,对小单位排序;最后合并。

  • ==快速排序==

  • 桶排序

    知道元素的范围

  • 基数排序

    次位优先

  • 表排序

    大型结构的排序,移动不能

  • 外部排序

屏幕截图_216_.png

不相交集

图论算法

  • 定义
  • 拓扑排序
  • 最短路径
    • Dijkstra算法 单源最短路径
    • Floyd算法 多源最短
  • 网络流
  • 最小生成树
    • Prim
    • Kruskal
  • 深度优先搜索
  • NP-完全性

算法设计技巧

  • 贪婪算法

  • 分治算法

  • 动态规划

    核心思想:

    将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他局部解。依次解决各子问题,最后一个子问题就是初始问题的解。

  • 随机化算法

  • 回溯算法

更多

广度优先搜索

复杂度总结

  • BuildHeap
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
//
// Created by aoyun on 2019/11/24.
//
#include <stdlib.h>
#include <stdio.h>

#define ElementType int

/**
* <p>插入排序</p>
* 把元素插到正确的位置
* @param A 待排序数组
* @param N 数组元素个数
*/
static void InsertionSort(ElementType A[], int N) { /* 插入排序 */
int P, i;
ElementType Tmp;

for (P = 1; P < N; P++) {
Tmp = A[P]; /* 取出未排序序列中的第一个元素*/
for (i = P; i > 0 && A[i - 1] > Tmp; i--) /*从后向前*/
A[i] = A[i - 1]; /*依次与已排序序列中元素比较并右移*/
A[i] = Tmp; /* 放进合适的位置 */
}
}

/**
* <p>希尔排序</p>
*
* @param A
* @param N
*/
void ShellSort(ElementType A[], int N) { /* 希尔排序 - 用Sedgewick增量序列 */
int Si, D, P, i;
ElementType Tmp;
/* 这里只列出一小部分增量 */
int Sedgewick[] = {929, 505, 209, 109, 41, 19, 5, 1, 0};

// 找到合适的初始增量
for (Si = 0; Sedgewick[Si] >= N; Si++); /* 初始的增量Sedgewick[Si]不能超过待排序列长度 */

for (D = Sedgewick[Si]; D > 0; D = Sedgewick[++Si])
for (P = D; P < N; P++) { /* 插入排序*/
Tmp = A[P];
for (i = P; i >= D && A[i - D] > Tmp; i -= D)
A[i] = A[i - D];
A[i] = Tmp;
}
}

void Swap(ElementType *a, ElementType *b) {
ElementType t = *a;
*a = *b;
*b = t;
}

static void PercDown(ElementType A[], int p, int N) { /* 改编代码4.24的PercDown( MaxHeap H, int p ) */
/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */
int Parent, Child;
ElementType X;

X = A[p]; /* 取出根结点存放的值 */
for (Parent = p; (Parent * 2 + 1) < N; Parent = Child) {
Child = Parent * 2 + 1;
if ((Child != N - 1) && (A[Child] < A[Child + 1]))
Child++; /* Child指向左右子结点的较大者 */
if (X >= A[Child]) break; /* 找到了合适位置 */
else /* 下滤X */
A[Parent] = A[Child];
}
A[Parent] = X;
}

/**
* 利用堆的特性排序
* @param A
* @param N
*/
void HeapSort(ElementType A[], int N) { /* 堆排序 */
int i;

for (i = N / 2 - 1; i >= 0; i--)/* 建立最大堆 */
PercDown(A, i, N);

for (i = N - 1; i > 0; i--) {
/* 删除最大堆顶 */
Swap(&A[0], &A[i]); /* 见代码7.1 */
PercDown(A, 0, i);
}
}

/* 归并排序 - 递归实现 */

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void
Merge(ElementType A[], ElementType TmpA[], int L, int R, int RightEnd) { /* 将有序的A[L]~A[R-1]和A[R]~A[RightEnd]归并成一个有序序列 */
int LeftEnd, NumElements, Tmp;
int i;

LeftEnd = R - 1; /* 左边终点位置 */
Tmp = L; /* 有序序列的起始位置 */
NumElements = RightEnd - L + 1;

while (L <= LeftEnd && R <= RightEnd) {
if (A[L] <= A[R])
TmpA[Tmp++] = A[L++]; /* 将左边元素复制到TmpA */
else
TmpA[Tmp++] = A[R++]; /* 将右边元素复制到TmpA */
}

while (L <= LeftEnd)
TmpA[Tmp++] = A[L++]; /* 直接复制左边剩下的 */
while (R <= RightEnd)
TmpA[Tmp++] = A[R++]; /* 直接复制右边剩下的 */

for (i = 0; i < NumElements; i++, RightEnd--)
A[RightEnd] = TmpA[RightEnd]; /* 将有序的TmpA[]复制回A[] */
}

void Msort(ElementType A[], ElementType TmpA[], int L, int RightEnd) { /* 核心递归排序函数 */
int Center;

if (L < RightEnd) {
Center = (L + RightEnd) / 2;
Msort(A, TmpA, L, Center); /* 递归解决左边 */
Msort(A, TmpA, Center + 1, RightEnd); /* 递归解决右边 */
Merge(A, TmpA, L, Center + 1, RightEnd); /* 合并两段有序序列 */
}
}

void MergeSort(ElementType A[], int N) { /* 归并排序 */
ElementType *TmpA;
TmpA = (ElementType *) malloc(N * sizeof(ElementType));

if (TmpA != NULL) {
Msort(A, TmpA, 0, N - 1);
free(TmpA);
} else printf("空间不足");
}

/* 归并排序 - 循环实现 */
/* 这里Merge函数在递归版本中给出 */

/* length = 当前有序子列的长度*/
void Merge_pass(ElementType A[], ElementType TmpA[], int N, int length) { /* 两两归并相邻有序子列 */
int i, j;

for (i = 0; i <= N - 2 * length; i += 2 * length)
Merge(A, TmpA, i, i + length, i + 2 * length - 1);
if (i + length < N) /* 归并最后2个子列*/
Merge(A, TmpA, i, i + length, N - 1);
else /* 最后只剩1个子列*/
for (j = i; j < N; j++) TmpA[j] = A[j];
}

void Merge_Sort(ElementType A[], int N) {
int length;
ElementType *TmpA;

length = 1; /* 初始化子序列长度*/
TmpA = malloc(N * sizeof(ElementType));
if (TmpA != NULL) {
while (length < N) {
Merge_pass(A, TmpA, N, length);
length *= 2;
Merge_pass(TmpA, A, N, length);
length *= 2;
}
free(TmpA);
} else printf("空间不足");
}

/**
* 前中后3值选出pivot
* @param A
* @param Left
* @param Right
* @return
*/
ElementType Median3(ElementType A[], int Left, int Right) {
int Center = (Left + Right) / 2;
if (A[Left] > A[Center])
Swap(&A[Left], &A[Center]);
if (A[Left] > A[Right])
Swap(&A[Left], &A[Right]);
if (A[Center] > A[Right])
Swap(&A[Center], &A[Right]);
/* 此时A[Left] <= A[Center] <= A[Right] */
Swap(&A[Center], &A[Right - 1]); /* 将基准Pivot藏到右边*/
/* 只需要考虑A[Left+1] … A[Right-2] */
return A[Right - 1]; /* 返回基准Pivot */
}

void Qsort(ElementType A[], int Left, int Right) { /* 核心递归函数 */
int Pivot, Cutoff, Low, High;

if (Cutoff <= Right - Left) { /* 如果序列元素充分多,进入快排 */
Pivot = Median3(A, Left, Right); /* 选基准 */
Low = Left;
High = Right - 1;
while (1) { /*将序列中比基准小的移到基准左边,大的移到右边*/
while (A[++Low] < Pivot);
while (A[--High] > Pivot);
if (Low < High) {
Swap(&A[Low], &A[High]);
} else {
break; // while(1)
}
}
Swap(&A[Low], &A[Right - 1]); /* 将基准换到正确的位置 */
Qsort(A, Left, Low - 1); /* 递归解决左边 */
Qsort(A, Low + 1, Right); /* 递归解决右边 */
} else {
InsertionSort(A + Left, Right - Left + 1); /* 元素太少,用简单排序 */
}
}

void QuickSort(ElementType A[], int N) { /* 统一接口 */
Qsort(A, 0, N - 1);
}

/* 基数排序 - 次位优先 */

/* 假设元素最多有MaxDigit个关键字,基数全是同样的Radix */
#define MaxDigit 4
#define Radix 10

/* 桶元素结点 */
typedef struct Node *PtrToNode;
struct Node {
int key;
PtrToNode next;
};

/* 桶头结点 */
struct HeadNode {
PtrToNode head, tail;
};
typedef struct HeadNode Bucket[Radix];

int GetDigit(int X, int D) { /* 默认次位D=1, 主位D<=MaxDigit */
int d, i;

for (i = 1; i <= D; i++) {
d = X % Radix;
X /= Radix;
}
return d;
}

/**
* <p>基数排序</p>
* 每次选择一个基准,如个位、十位、百位
* @param A
* @param N
*/
void LSDRadixSort(ElementType A[], int N) { /* 基数排序 - 次位优先 */
int D, Di, i;
Bucket B;
PtrToNode tmp, p, List = NULL;

for (i = 0; i < Radix; i++) /* 初始化每个桶为空链表 */
B[i].head = B[i].tail = NULL;
for (i = 0; i < N; i++) { /* 将原始序列逆序存入初始链表List */
tmp = (PtrToNode) malloc(sizeof(struct Node));
tmp->key = A[i];
tmp->next = List;
List = tmp;
}
/* 下面开始排序 */
for (D = 1; D <= MaxDigit; D++) { /* 对数据的每一位循环处理 */
/* 下面是分配的过程 */
p = List;
while (p) {
Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
/* 从List中摘除 */
tmp = p;
p = p->next;
/* 插入B[Di]号桶尾 */
tmp->next = NULL;
if (B[Di].head == NULL)
B[Di].head = B[Di].tail = tmp;
else {
B[Di].tail->next = tmp;
B[Di].tail = tmp;
}
}
/* 下面是收集的过程 */
List = NULL;
for (Di = Radix - 1; Di >= 0; Di--) { /* 将每个桶的元素顺序收集入List */
if (B[Di].head) { /* 如果桶不为空 */
/* 整桶插入List表头 */
B[Di].tail->next = List;
List = B[Di].head;
B[Di].head = B[Di].tail = NULL; /* 清空桶 */
}
}
}
/* 将List倒入A[]并释放空间 */
for (i = 0; i < N; i++) {
tmp = List;
List = List->next;
A[i] = tmp->key;
free(tmp);
}
}

/* 基数排序 - 主位优先 */

/* 假设元素最多有MaxDigit个关键字,基数全是同样的Radix */

#define MaxDigit 4
#define Radix 10

///* 桶元素结点 */
//typedef struct Node *PtrToNode;
//struct Node{
// int key;
// PtrToNode next;
//};

///* 桶头结点 */
//struct HeadNode {
// PtrToNode head, tail;
//};
typedef struct HeadNode Bucket[Radix];

//int GetDigit ( int X, int D )
//{ /* 默认次位D=1, 主位D<=MaxDigit */
// int d, i;
//
// for (i=1; i<=D; i++) {
// d = X%Radix;
// X /= Radix;
// }
// return d;
//}

void MSD(ElementType A[], int L, int R, int D) { /* 核心递归函数: 对A[L]...A[R]的第D位数进行排序 */
int Di, i, j;
Bucket B;
PtrToNode tmp, p, List = NULL;
if (D == 0) return; /* 递归终止条件 */

for (i = 0; i < Radix; i++) /* 初始化每个桶为空链表 */
B[i].head = B[i].tail = NULL;
for (i = L; i <= R; i++) { /* 将原始序列逆序存入初始链表List */
tmp = (PtrToNode) malloc(sizeof(struct Node));
tmp->key = A[i];
tmp->next = List;
List = tmp;
}
/* 下面是分配的过程 */
p = List;
while (p) {
Di = GetDigit(p->key, D); /* 获得当前元素的当前位数字 */
/* 从List中摘除 */
tmp = p;
p = p->next;
/* 插入B[Di]号桶 */
if (B[Di].head == NULL) B[Di].tail = tmp;
tmp->next = B[Di].head;
B[Di].head = tmp;
}
/* 下面是收集的过程 */
i = j = L; /* i, j记录当前要处理的A[]的左右端下标 */
for (Di = 0; Di < Radix; Di++) { /* 对于每个桶 */
if (B[Di].head) { /* 将非空的桶整桶倒入A[], 递归排序 */
p = B[Di].head;
while (p) {
tmp = p;
p = p->next;
A[j++] = tmp->key;
free(tmp);
}
/* 递归对该桶数据排序, 位数减1 */
MSD(A, i, j - 1, D - 1);
i = j; /* 为下一个桶对应的A[]左端 */
}
}
}

void MSDRadixSort(ElementType A[], int N) { /* 统一接口 */
MSD(A, 0, N - 1, MaxDigit);
}

//int main() {
// int a[] = {3, 1, 2};
// QuickSort(a, 3);
//}

摊还分析

高级数据结构及其实现

一、概述

二、软件过程 P30

要点 P46

软件过程是产生一个软件系统的一系列活动。软件过程模型是这些过程的抽象表示。

一般过程模型描述软件过程的组成。一般过程模型实例包括瀑布模型、增量式开发、面向复用的开发。

需求工程是开发软件描述的过程。

设计和实现过程是将需求描述转换为一个可运行的软件 系统的过程。系统化的设计方法用来完成这个转换。

软件有效性验证时检查系统是否和它的描述一致,以及是否符合系统客户的真正需要的过程。

软件进化是修改已存在的软件系统以适应用户新的需求的过程。

软件过程应包含对变更的活动。这可能包括一个原型构造过程,以帮助避免在需求和设计上的错误决定。

Rational 统一过程是新式基本过程模型,其特点是由阶段(开端、细化、构造、转换)所构成,但是它把活动(需求、分析、设计)和阶段相区别。

三、敏捷软件开发 P49

要点 62

Scrum 方法是一种提供项目管理框架的敏捷方法。它的核心是一组冲刺循环,开发一个系统增量是有固定的时间周期的。规划是基于积压的工作的优先权安排的。

四、需求工程 P65

要点 85

一个软件系统的需求描述了系统应该做什么以及定义系统运行时和实现时的约束。

功能需求是有关系统一定要提供的服务或者是必须执行的运算的描述。

非功能需求约束所开发的系统和所采用的开发过程,

需求工程过程包括可行性研究,需求导出和分析,需求描述,需求有效性验证和需求管理。

需求有效性验证是检查需求的有效性、一致性、完备性、真实性和可检验性。

五、系统建模 P88

要点 P104

上下文模型描述所建模的系统是如何在含有其他系统和流程的环境中工作的。它们帮助定义被建系统的边界。

用例图和时序图用来描述系统用户之间或系统用户和其他系统之间的交互。用例描述的是系统和外部参与者之间的交互;时序图通过表示系统对象之间的交互为用例图添加更多的信息。

结构模型表示的系统的体系结构。类图用来定义系统中的类的静态结构以及类之间的关联关系。

行为模型用来描述可执行系统的动态行为。我们可以从系统处理数据的角度和事件激励系统产生响应的角度来建立这种模型。

活动图用来为数据的处理过程建模,其中每一个活动图代表一个处理步骤。

状态图用来为响应内外部事件的系统行为建模。

模型驱动工程是一种软件开发的方法,其中的系统表示可自动转换为可执行代码的模型的集合。

六、体系结构设计

要点 P122

应用较多的体系结构模式有MVC、分层体系结构、容器结构、客户机-服务器结构,以及管道和过滤器结构。

七、设计与实现

要点 P142

面向对象的设计过程包括系统体系结构的设计、识别系统中的对象、运用不同的对象模型描述设计,以及文档化组件接口。

面向对象的设计过程中会产生不同的模型。这些模型包括静态模型(类模型、泛化模型、关联模型)和动态模型(时序模型、状态机模型)。

八、软件测试 P145

审查和复查是分析和审查系统需求、设计模型、程序的源代码,甚至的建议的系统测试,被称为“静态”V&V技术。 146

审查主要关心一个系统的源代码,也涉及任何可读的软件表示,如它的需求、设计模型。 147

审查的优势 147

测试用例是一个对输入和在特定环境下的期望的输出以及所测试的对象的一个描述。 147

回归测试——重新运行先前的测试以检测对程序的变更没有引入新的故障。

测试驱动开发(TDD):155

要点 P161

开发测试包括单元测试,即测试单个对象和方法;组件测试,即测试相关的一组对象;系统测试,即测试部分或完整的系统。

测试优先开发是开发的一种方式,在代码测试之前就已经写好测试。做小的代码更改和进行代码重构,直到所有测试成功执行。

情景(脚本)测试是非常有用的,因为它可以复制系统的使用。它包括设计一种典型的使用场景,并以此来导出测试案例。

接收测试是一个用户的测试过程,目的是决定这个软件是否足以进行部署。以及能否用在它的实际操作环境中。

九、软件进化 P163

要点 P177

WDF Windows Driver Frameworks Windows 程序驱动程序框架

INF driver setup information 设备安装信息

dp

Density-independent Pixels 像素无关密度

一个基于屏幕物理密度的抽象的单位。

TA 与 屏幕物理密度/像素密度 相关,对应不同的 density

阅读全文 »

使用

By default, to avoid poor UI performance, Room doesn’t allow you to issue queries on the main thread. When Room queries return LiveData, the queries are automatically run asynchronously on a background thread.

为避免糟糕的 UI 性能,Room 不允许你在主线程查询数据库。但当查询返回 LiveData 时,查询将自动异步运行在后台线程。

阅读全文 »

REST (REpresentational State Transfer) 表现层状态转换。

REST 是一种设计风格,便于不同软件在网络上传递信息。

SOAP

SOAP (Simple Object Access Protocol) 简单对象访问协议。

SOAP 是网络交换数据的一种协议规范。

RESTful

REST 是名词,RESTful 是动词。

RESTful API

符合 REST 风格的 API 称为 RESTful API。

要绘制东西,需要 4 个基本组件:存储像素点的 Bitmap、主持绘制的 Canvas、绘图的基本元素(Path,Rect,text,Bitmap等)、描述颜色和样式的 Paint。

阅读全文 »

Git

简介

Git是一个免费的,开源的分布式版本控制系统,被设计用来又快又好地处理大大小小的项目。

分布式 集中式

配置

1
2
$ git config --global user.name "Your Name"
$ git config --global user.email "email@example.com"

--global 表示这台机器上的所有仓库都会用这个配置。

建立工程

初始化文件夹为仓库

1
2
$ git init
Initialized empty Git repository in D:/Temp/learn-git/.git/

之后本地文件夹就会有.git文件夹

基本使用

添加文件到版本库

在Git目录下新建文件。

1
2
3
4
5
6
7
8
9
10
11
$ git status
On branch master

No commits yet

Untracked files:
(use "git add <file>..." to include in what will be committed)

first.txt

nothing added to commit but untracked files present (use "git add" to track)

git status 查看当前==文件夹==状态。

1
$ git add .

给当前目录下的所有文件创建一个快照。这些快照保存在一个暂时的区域,Git中叫做index(暂存区)。

1
$ git commit

之后再用git commit就可以把暂存区中的内容永久地存到Git仓库里。

直接git commit会要求你输入这次提交的信息,vim方式输入。

git commit -m "message" 可以综合这两步过程。

修改

修改一下文件内容,然后把TA们添加到暂存区。

1
$ git diff --cached

可以查看最近一次add的文件的修改内容,如下所示:

1
2
3
4
5
6
7
8
9
diff --git a/first.txt b/first.txt
index b683137..53c5510 100644
--- a/first.txt
+++ b/first.txt
@@ -1 +1 @@
-This is first line.
\ No newline at end of file
+First line.
\ No newline at end of file

add之后再status查看当前暂存区与上一次commit之间的差别。

如果没什么再需要修改的,就可以commit添加到仓库了。

git commit -a 可以把addcommit一次完成。

这会把所有修改的(不包括新建的)文件添加到暂存区,再commit提交

Git追踪的是内容不是文件

查看历史

1
$ git log

git log可以在任何时刻使用,来查看每一次commit的信息

TODO

分支和合并

管理分支

一个Git仓库可以有多个分支。

新建分支

1
$ git branch dev

查看分支

1
$ git branch

Git会显示出所有分支,TODO

1
2
  dev
* master

切换分支

2.23加入,现在还在试验阶段,是为了分担git checkout(以前切换分支是checkout)的功能。

Git 更新(Windows) git update-git-for-windows

1
$ git switch dev

就切换到了dev分支

分享和更新项目

检查和比较

补丁

原理

更多

.gitignore

.gitignore用来规定一些不需要提交到版本库(不被Git追踪)的文件,大多是配置文件和临时文件或中间生成的文件。第一次push后,在.gitignore中写入新的过滤规则是不会更新的,所有最好一开始就编写好,否则需要先git rm

.gitignore忽略规则的匹配语法

来自 https://www.cnblogs.com/kevingrace/p/5690241.html

在 .gitignore 文件中,每一行的忽略规则的语法如下:
1)空格不匹配任意文件,可作为分隔符,可用反斜杠转义
2)以“”开头的行都会被 Git 忽略。即#开头的文件标识注释,可以使用反斜杠进行转义。
3)可以使用标准的glob模式匹配。所谓的glob模式是指shell所使用的简化了的正则表达式。
4)以斜杠”/“开头表示目录;”/“结束的模式只匹配文件夹以及在该文件夹路径下的内容,但是不匹配该文件;”/“开始的模式匹配项目跟目录;如果一个模式不包含斜杠,则它匹配相对于当前 .gitignore 文件路径的内容,如果该模式不在 .gitignore 文件中,则相对于项目根目录。
5)以星号”**”通配多个字符,即匹配多个任意字符;使用两个星号”*“ 表示匹配任意中间目录,比如`a//z`可以匹配 a/z, a/b/z 或 a/b/c/z等。
6)以问号”?“通配单个字符,即匹配一个任意字符;
7)以方括号”[]“包含单个字符的匹配列表,即匹配任何一个列在方括号中的字符。比如[abc]表示要么匹配一个a,要么匹配一个b,要么匹配一个c;如果在方括号中使用短划线分隔两个字符,表示所有在这两个字符范围内的都可以匹配。比如[0-9]表示匹配所有0到9的数字,[a-z]表示匹配任意的小写字母)。
8)以叹号”!“表示不忽略(跟踪)匹配到的文件或目录,即要忽略指定模式以外的文件或目录,可以在模式前加上惊叹号(!)取反。需要特别注意的是:如果文件的父目录已经被前面的规则排除掉了,那么对这个文件用”!”规则是不起作用的。也就是说”!”开头的模式表示否定,该文件将会再次被包含,如果排除了该文件的父级目录,则使用”!”也不会再次被包含。可以使用反斜杠进行转义。

需要谨记:git对于.ignore配置文件是按行从上到下进行规则匹配的,意味着如果前面的规则匹配的范围更大,则后面的规则将不会生效;

2019-11-28 22:39:44

自定义 View 有两种方法:

继承 View 的子类,如TextView

直接继承 View 类。需要自己绘制 UI 元素。

阅读全文 »

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
// 2020-3-29 19:45:53
// kotlin coroutines
implementation 'org.jetbrains.kotlinx:kotlinx-coroutines-android:1.3.5'
// Glide
implementation 'com.github.bumptech.glide:glide:4.11.0'
annotationProcessor 'com.github.bumptech.glide:compiler:4.11.0'
// OkHttp
implementation 'com.squareup.okhttp3:okhttp:4.4.0'
// ViewPager2
implementation "androidx.viewpager2:viewpager2:1.0.0"
// dagger
// apply plugin: 'kotlin-kapt'
def dagger_version = "2.27"
implementation "com.google.dagger:dagger:$dagger_version"
kapt "com.google.dagger:dagger-compiler:$dagger_version"
// material
implementation 'com.google.android.material:material:1.2.0-alpha05'
// 2020-4-9 14:47:57
// retrofit
implementation 'com.squareup.retrofit2:retrofit:2.8.1'
implementation 'com.squareup.retrofit2:converter-gson:2.8.1'
// Room
// apply plugin: 'kotlin-kapt'
def room_version = "2.2.3"
implementation "androidx.room:room-runtime:$room_version"
kapt "androidx.room:room-compiler:$room_version"
// optional - Kotlin Extensions and Coroutines support for Room
implementation "androidx.room:room-ktx:$room_version"
// Lifecycle
implementation "androidx.lifecycle:lifecycle-extensions:2.2.0"
kapt "androidx.lifecycle:lifecycle-compiler:2.2.0"
implementation "androidx.lifecycle:lifecycle-viewmodel-ktx:2.2.0"
// coroutines
api "org.jetbrains.kotlinx:kotlinx-coroutines-core:1.3.4"
api "org.jetbrains.kotlinx:kotlinx-coroutines-android:1.3.4"

Navigation 组件由下面3个关键部分组成:

Navigation Graph XML resource 包含与navigation有关的所有信息,如destination path等。

NavHostFragment Layout XML 添加到layout的widget,显示了Navigation Graph的destination。

NavController Kotlin/Java 对象 追踪在 Navigation Graph 中的位置,协调那些destination。

阅读全文 »

配置(Android)

1
2
// kotlin coroutines
implementation 'org.jetbrains.kotlinx:kotlinx-coroutines-android:1.3.5'

示例:加载网络图片

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class MainActivity : AppCompatActivity() {

override fun onCreate(savedInstanceState: Bundle?) {
super.onCreate(savedInstanceState)
setContentView(R.layout.activity_main)
val coroutineScope = CoroutineScope(Dispatchers.Main)
coroutineScope.launch(Dispatchers.Main) {
val url = getImageUrl()
Glide.with(this@MainActivity).load(url).into(iv)
}

}

private suspend fun getImageUrl() = withContext(Dispatchers.IO) {
val client = OkHttpClient()
val request = Request.Builder()
.url("http://guolin.tech/api/bing_pic")
.build()
return@withContext client.newCall(request).execute().body?.string()
}
}

withContext()可以切换到指定的线程,然后在闭包内的逻辑结束后,再切换到原来的线程继续执行。

Dispatchers

2020-03-21 22:09:50

CSS

CSS 用于指示 HTML 在浏览器中的显示样式。

CSS 组成

CSS 由选择符(选择器)与声明组成,声明由属性和值组成。

1
2
3
p {
color: blue;
}
阅读全文 »

HTML

sample

1
2
3
4
5
6
7
8
9
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>制作我的第一个网页</title>
</head>
<body>
<h1>Hello HTML</h1>
</body>
</html>
阅读全文 »

简介

HTTP (Hypertext Transfer Protocol 超文本传输协议)是一种用于分布式、协作式和超媒体信息系统的应用层协议。HTTP 协议定义了客户端如何从服务器请求 Web 页面,以及服务器如何把 Web 页面返回给客户端。HTTP 是万维网数据通信的基础。

阅读全文 »

Service是一种可以在后台执行长时间运行操作而不提供界面的应用组件。

阅读全文 »

Android 构建时会编译源代码和应用资源,然后打包为APK文件。Android Studio 使用 Gradle 来自动执行和管理构建流程。Android Plugin for Gradle 与 Gradle 搭配使用,专门为 Android 应用的构建提供支持。

阅读全文 »

启用 Data Binding

Data Binding 库与 Android Gradle 插件捆绑在一起,所以不需要声明依赖,但需要启用。

阅读全文 »

概述

数字系统

可以用不同数字反映的物理量称为数字量。

表示数字量的信号称为数字信号。

处理数字信号的电子电路称为数字电路(数字逻辑电路、逻辑电路),其功能通过逻辑运算和逻辑判断完成。

阅读全文 »

写在前面

make这一阶段花费时间和机器配置有关,可能长达几小时,建议选择好时间。同时需要足够的磁盘空间,22G以上。

环境:Ubuntu 18.04.1 阿里云服务器

阅读全文 »

前言

注解在Java SE5中引入。注解好处多多,TA可以使我们的代码变得简洁,减少样板代码,还能存储有关程序的额外信息。程序员还可以自定义注解

阅读全文 »

前言

这是打算认真写博客后的第一篇,今天来研究一下Java的反射机制。

反射简介

反射机制可以让人们在运行时获得类的信息。

Class类和java.lang.reflect类库(包含Constructor Method Field Modifier Array类)为反射提供了支持。

阅读全文 »