汇编语言

发表于 2020-05-31

重点

新增一个中断处理程序的步骤
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

循环

子程序

定义：

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

宏指令

宏定义
宏调用
宏展开

定义：

name macro
	...
	...
name endm

调用：直接用宏名调用。

传参：

带间隔符的参数

< > 尖括号括住
数字参数

%
宏参数的连接

&
宏体中的变量与标号

local

重复汇编伪指令：

给定次数的重复汇编

rept 26
	db char
char = char+1
	endm

不定次数的重复汇编

IRP

IRPC

条件汇编伪指令：

IF

ELSE

ENDIF

引入宏库：

1	include macro.lib

模块化程序

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

输入/输出和WIN32编程

中断

内中断

中断源：

中断向量表：

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

编写中断处理程序
安装（复制到固定地址处）
设置中断向量表

外中断

嵌入式

名词

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：

特点：

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

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

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

OS课件内容

发表于 2020-05-17

问题

阅读全文 »

算法上课内容总结

发表于 2020-05-07 更新于 2020-05-08

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})$。

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。

构造 LCS

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

作业排程

钢条切割

矩阵链乘法

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

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

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

一个递归求解方案

计算最优代价

伪代码：

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 算法，其要求可以存在负值权重的边，但不可以存在负值回路。

排序算法

发表于 2020-05-07 更新于 2020-05-11

排序方法	平均时间复杂度	最坏时间复杂度
插入排序	$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)$	-

最短路径

发表于 2020-05-06 更新于 2020-05-07

单源最短路径

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

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

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

全点对最短路径

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

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

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

算法的正确性证明

发表于 2020-05-05

图算法入门

发表于 2020-05-05

图的表示和存储方式

邻接链表邻接矩阵

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

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

所有结点对的最短路径问题

发表于 2020-05-05

贪心算法

发表于 2020-05-04 更新于 2020-05-06

简介

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

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

原理

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

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

步骤

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

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

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

应用

活动选择问题

霍夫曼编码

最小生成树

单源最短路径的 Dijkstra 算法

动态规划

发表于 2020-05-04 更新于 2020-05-07

简介

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

原理

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

步骤

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

（1）刻画一个最优解的结构特征。

（2）递归地定义最优解的值。

（3）计算最优解的值，通常采用自底向上的方法。

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

应用

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

最长公共子序列

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

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

一个递归解

计算 LCS 的长度

我们使用两个表 c 和 b。

构造 LCS

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

作业排程

钢条切割

矩阵链乘法

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

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

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

一个递归求解方案

计算最优代价

伪代码：

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

构造最优解

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

分治法

发表于 2020-05-04 更新于 2020-05-07

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

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

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

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

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

分析分治算法

应用

归并排序

最大子数组问题

矩阵乘法的 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})$。

线性时间排序

发表于 2020-05-04

算法渐进分析

发表于 2020-05-04

概率分析和随机化算法

发表于 2020-05-04

算法导论

发表于 2020-05-04

算法复习

发表于 2020-05-04 更新于 2020-05-07

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

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

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

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

算法的特性：

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

引论

数学知识

级数：
证明方法
- 归纳法
- 反证法
递归简论
- 设计递归的基本法则：
  1. 基准情形
  2. 不断推进
  3. 设计效益：假设所有的递归调用都能运行。
  4. 合成效益法则：不要做重复性工作。

算法分析

数学基础

$O(f(N))$ 上限

$Ω(f(N))$ 下限

$Θ(f(N))$ 相等

$o(f(N))$ 小于

表、栈和队列

表
- 数组
- 链表
栈

中缀表达式转换为后缀表达式：

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

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

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

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

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

队列

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

CreateQueue()
IsFull()
IsEmpty()
Enqueue()
Dequeue()

// 队列的数组实现
// 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$

散列

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

优先队列

二叉堆

/*----------- 建造最大堆 -----------*/
/* 下滤：将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;
}

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. 下沉排序
利用堆的性质进行排序
归并排序

分治。先分，分成小单位；再治，对小单位排序；最后合并。
==快速排序==
桶排序

知道元素的范围
基数排序

次位优先
表排序

大型结构的排序，移动不能
外部排序

不相交集

图论算法

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

算法设计技巧

贪婪算法
分治算法
动态规划

核心思想：

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

更多

广度优先搜索

复杂度总结

BuildHeap

//
// 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);
//}

摊还分析

高级数据结构及其实现

软件工程

发表于 2020-04-21

MATLAB入门

发表于 2020-04-21

Windows 驱动程序入门

发表于 2020-04-18 更新于 2020-04-21

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

INF driver setup information 设备安装信息

编码

发表于 2020-04-16

JSON

发表于 2020-04-16 更新于 2020-04-21

JSON (JavaScript Object Notation)

阅读全文 »

Android KTX

发表于 2020-04-16

Material Design入门

发表于 2020-04-14

WorkManager入门

发表于 2020-04-14

文档补完-HTML

发表于 2020-04-13 更新于 2020-04-21

Elements

主根元素

阅读全文 »

dp sp px

发表于 2020-04-13 更新于 2020-04-18

dp

Density-independent Pixels 像素无关密度

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

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

阅读全文 »

Android Animation

发表于 2020-04-11 更新于 2020-05-05

Tween Animation

变换动画

阅读全文 »

Activity之间跳转

发表于 2020-04-09

Room入门

发表于 2020-04-09 更新于 2020-04-21

使用

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 时，查询将自动异步运行在后台线程。

阅读全文 »

SQL入门

发表于 2020-04-08

REST

发表于 2020-04-08

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

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

SOAP

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

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

RESTful

REST 是名词，RESTful 是动词。

RESTful API

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

文档补完-Android API reference

发表于 2020-04-07 更新于 2020-04-15

API reference | Android 开发者 | Android Developers

阅读全文 »

View绘制

发表于 2020-04-07

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

阅读全文 »

Git

发表于 2020-04-02

Vim

发表于 2020-04-01

文档补完-Android Plugin DSL

发表于 2020-03-31

Android Plugin 3.4.0-dev DSL Reference

阅读全文 »

Android自定义View

发表于 2020-03-30

自定义 View 有两种方法：

继承 View 的子类，如TextView；

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

阅读全文 »

Android常用库

发表于 2020-03-29 更新于 2020-04-09

// 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"

Dagger入门

发表于 2020-03-29

Navigation入门

发表于 2020-03-25 更新于 2020-04-06

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

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

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

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

阅读全文 »

Kotlin空安全

发表于 2020-03-23 更新于 2020-04-21

可空类型

声明为可空类型：

1	var s: String? = null

阅读全文 »

Kotlin协程

发表于 2020-03-21 更新于 2020-03-23

配置（Android）

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

示例：加载网络图片

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入门

发表于 2020-03-20 更新于 2020-03-21

CSS

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

CSS 组成

CSS 由选择符（选择器）与声明组成，声明由属性和值组成。

1
2
3

p {
    color: blue;
}

阅读全文 »

HTML入门

发表于 2020-03-19

HTML

sample

<html>
    <head>
        <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
        <title>制作我的第一个网页</title>
    </head>
    <body>
        <h1>Hello HTML</h1>
    </body>
</html>