5 数组与预处理命令

课程内容#

数组的定义与初始化#

定义：存储一个固定大小的相同类型元素的顺序集合
初始化
- int a[100] = {2, 3}; // a[0] = 2, a[1] = 3
- int a [100] = {0}; // 数组的清空操作：数组每一位都初始化为 0 值
  - 其实只是定义了第 0 位为 0，但会引发其他位自动初始化为 0
其他
- 从下标 0 开始
- 数组空间大小：所有变量大小的总和
- 存储空间连续
  - int a[3]

地址	0123	4567	89[10][11]
元素	a[0]	a[1]	a[2]

- 上述定义的数组都属于静态数组
  - 不建议的操作：int n; scanf ("% d", &n); int arr (n);
- 下标 - 值的映射
  - 已知索引，取值的时间效率是 O (1)

素数筛#

核心思想：用素数去枚举掉所有合数

当作一个算法框架去学习，有很多演变
素数：只有 1 和它本身两个因子
- 1 既不是素数也不是合数
- 2 是最小的素数
- 素数一定是奇数（除了 2），奇数不一定是素数
借助数组结构。数组可以表示三种信息：
- 下标
- 下标映射的值
- 值的正负
算法衡量标准及该算法性能
- 空间复杂度：O (N)，有 N 个数字就开辟大小为 N 的数组
- 时间复杂度：O (N * logN)、O (N * loglogN)-- 优化版，趋近于 O (N)
  - 不是 O (N)，是因为有重复标记情况
  - log 以谁为底不重要，以 2 为底就已经很小了
  - 怎么计算：均摊思想，根据时间复杂度与概率来算期望...
打标记：素数，0；合数，1
- 借助数组的两种状态信息：下标→数字，值→标记
素数筛扩展
- 求一个范围内所有数字的最小、最大素因子
- 比如 12：2、3

线性筛#

从欧拉第 7 题入手
- 求第 10001 个素数
- 可以使用枚举法 O (N * sqrt (N))、素数筛
- 估算第 10001 位素数大小不会超过多少？
  - 规律：20 万以内排名的素数，其范围不会超过排名的 20 倍
来自素数筛的思考
- 6 被标记了几次？2 次：2、3
- 30 被标记了几次？3 次：2、3、5
- 如果一个数字 N 的素数分解式中，含有 m 种不同的素数，N 被标记几次？m 次
- 那么可不可以只被标记 1 次呢？👇
线性筛
- 空间、时间都是O(n)
- 用一个整数 M 去标记合数 N
- M、N 的关系符合四个性质
  1. N 的因子中最小的素数为 p
  2. N = p * M
  3. ❗ p 一定小于等于M 中最小的素因子
    - 类似七擒孟获的道理，只在最后一次标记
  4. 利用 M * P' （所有不大于【M 的最小素数】的素数集合）标记 N1、N2、...

【i 和 iii 有点等价的意味】

代码
- 核心思想：N = M（↑尽可能大） * p（↓尽可能小）
  - 枚举 M，慢慢增大 p 值，直到 p 值满足终止条件：性质 iii
  - 相比 M，p 更好控制！
- 避免重复的关键就是第 iii 条性质
- 注意：虽然有两层 for 循环，但时间复杂度是 O (N)，因为第二层 for 循环里的 break，整个数组就遍历一次
- 与素数筛初始条件优化为 i * i 的区别是？素数筛还是有重复标记的情况

二分查找法#

顺序查找→折半查找：O (N)→O (logN)
关键前提：查找序列单调
代码
- 主要演示三个部分：①在数组中二分查找 ②在函数中二分查找 ③
- 对于函数的二分查找实现部分
  - 应该可以把 binary_search_f_i 和 binary_search_f_d 统一为一个函数
  - 关注后面的学习，可否辨识传入的函数指针的返回类型
  - 但实现部分有差别，因此意义应该不大
- main 函数中被注释的代码，测试的是在数组与函数中二分查找的结果，如下：
- - 利用函数做二分查找的范围可以更灵活
- double 类型判等：用差值小于 EPSL 判断
  - 记得 #undef EPSL
- 细节详见注释
  - 学习顺序：binary_search 👉 binary_search_f_i 👉 binary_search_f_d
递归版代码
- 函数的参数与迭代方式有所不同，需确定查找边界

牛顿迭代法#

目的：求解 f (x) = 0 时 x 的值
条件：函数可导；收敛
迭代一次公式：x2 = x1 - f(x1) / f'(x1)
核心思想：每迭代一次，x2 会比 x1 更接近要求的 x 的值，直到 f (x) 的绝对值比 EPSL 小即可
代码
- ⭐循环终止条件记得取绝对值！
- x = n / 2.0 这个初始值是固定的吗？
  - 不是
  - 这个值是设想的 x 最近的解，在解的左右两侧都没问题
  - 不过不能取 0 哈，因为导数为 0，会导致除数为 0
- 对 NewTon 函数做一个包装，得到 my_sqrt 函数
- 不是二分查找！二分需要单调～

预处理命令#

#开头的命令
- #include <stdio.h> →在预处理时，将 stdio.h 文件原封不动地拷贝到当前位置
宏定义

定义符号常量：常量→符号。

#define PI 3.1415926
#define MAX_N 1000

便于批量修改值

傻瓜表达式

#define MAX(a, b) (a) > (b) ? (a) : (b)
#define S(a, b) a * b

傻 eg. #define S (a, b) a * b
- S (2 + 3, 4 + 5) → 简单替换 → 2 + 3 * 4 + 5 等价于 2 + (3 * 4) + 5
- 在替换过程中不做任何运算！

定义代码段（高级）

#define P(a) { \
    printf("%d\n", a); \
}

宏只能接受一行定义，换行需要使用反斜杠 '' （连接符）
预定义的宏（系统封装好的）
- 宏的两端是两个下划线
- DATA、TIME：预编译时的日期、时间，不预处理就不会改变
  - 可以实现类似指纹识别的功能？预存储的关系？
- 非标准宏：有的环境可能未定义，不同环境的标准可能不同，所以可移植性不好
  - 怎么处理呢？可以使用条件式编译👇
条件式编译
- #ifdef DEBUG
  - 说明：是否定义了 DEBUG 宏
  - 注意：DEBUG 一定是一个宏，而不是变量！
    - 宏在预编译后生效，变量在编译后生效
- #ifndef DEBUG 是否没定义
- #if MAX_N == 5 宏 MAX_N 是否等于 5
  - 可在游戏中判断用户手机版本
- #elif MAX_N == 4
- #else
- 一定要以 #endif结束！！！
  - 【编码规范】
  - 如同 va_start、va_end
简易编译过程
- C 源码 .c
👇预处理阶段 (预编译) (gcc -E)：包含头文件、宏替换等预处理命令，替换所有的 #命令
- 编译源码 .c
👇语法检查、编译 (gcc –S)
- 汇编源码 .s、.asm
👇汇编 (gcc -c)
- 对象文件 .o（linux 下）或 .obj（windows 下）
👇链接 (gcc)
- 可执行程序 a.out（linux 下）或 a.exe（windows 下）（二进制文件）
PS：最后还有一个装载过程，主要是建立可执行文件、虚拟地址、物理地址三者的映射关系

字符串#

字符数组
- 定义：char str [size];
- 初始化

char str[] = "hello world";
char str[size] = {'h', 'e', 'l', 'l', 'o'};

Line1
- [] 里可不指明大小，系统会自动算
- 系统会自动加终止符 '\0'，字符数组大小：11+1
Line2
- size 至少为 6，考虑终止符 '\0' 占一位
  - 多余的位都补 '\0'
- 如果不加 size，就要在数组最后加字符 '\0'，系统不会自动加
'\0'
- 一个终止标记位
- 底层对应 0 值：false
- '\0' 可作为终止条件，如：for 循环读入字符串
字符后面会有 '\0' 吗？没有，是字符串的特性
相关操作
- 头文件：<string.h>
- strlen(str)
  - 返回字符 '\0' 的下标，长度不含 '\0'
  - PS：sizeof () 会考虑变量实实在在占用的内存，会考虑 '\0'，单位为字节
- strcmp(str1, str2);
  - 按字典序比较 ASCII 码大小
    - 从第一位开始
  - 返回值为差值（相等即为 0）
- strcpy(dest, src);
- 比较和拷贝的结束标志：找字符 '\0'，如果 '\0' 丢了呢？所以有
- 更安全的比较与拷贝：strncmp、strncpy
  - 针对 '\0' 不小心丢了的情况
  - 最多比较、拷贝 n 个字节
- 内存相关
  - memset(str, c, n)
  - 不局限于字符串操作，str 对应一个地址即可
    - 这里举例对数组的操作
    - memset(arr, 0, sizeof(arr))
      - 初始化，清空为 0
    - memset(arr, 1, sizeof(arr))
      - 这里不是把每位置为 1，因为操作的是每个字节，而 int 占 4 个字节
      - 0000...01000...001000....0001...
    - memset(arr, -1, sizeof(arr))
      - 确实是 - 1，因为 - 1 在 1 个字节里就是 11111111
头文件：<stdio.h>
两者结合可以做格式拼接：一个读入，一个输出
scanf 里的 str1 类比于终端的输入，它被换成了字符串输入

随堂练习#

实现没有 BUG 的 MAX 宏#

思路：①手算正确输出👉②先写最简单的有 BUG 的实现，并有友好的输出显示👉③针对错误输出依次找问题，解决
①正确输出如图
②先写有 BUG 的，并实现友好的输出显示

#define MAX(a, b) a > b ? a : b
#define P(func) { \
    printf("%s = %d\n", #func, func); \
}

Line2-4：友好输出显示
- #func 直接输出其字符串表示
- 不加 #就是调用其值
③针对错误输出依次找问题，解决
- （解决 BUG 的顺序也很重要，不过这里 BUG 的顺序很好）
- 这个时候看下错误情况
- 因为宏导致的错误，可以看预处理后的文件
  - gcc -E *.c 输出预处理替换掉宏之后的代码
- 第一次纠错
  - 解决：可以将红框处用括号提高优先级

#define MAX(a, b) (a > b ? a : b)

- 第二次纠错
  - 第四个结果为 2，思路如上图
  - 注意条件运算符 '?:'
    - 优先级很低：比 '>' 低
    - 有多个 '?:' 存在时，其结合方向是右到左
  - 解决：对于每个变量再用括号提高优先级

#define MAX(a, b) ((a) > (b) ? (a) : (b))

- 第三次纠错
  - a++ 运行了两次
    - 实际应该先拿 a 作比较，再进行 a+1
  - 解决：把 ++ 运算前的值先赋给一个变量；定义成一个代码段生成的表达式

#define MAX(a, b) ({\
    __typeof(a) _a = (a);\
    __typeof(b) _b = (b);\
    _a > _b ? _a : _b;\
})

__typeof (a++) 里的 a++ 执行吗？
- 用于表达式的时候不执行，只是取出其类型
({}) 表达式
- 值为小括号内最后一个表达式的值，数据类型为最后一个表达式的数据类型
- 参考C 语言的小括号和花括号结合使用 && 复合语句-CSDN
- 去掉 {} 或者 () 都不行！
  - () 里只能放逗号表达式
    - 逗号表达式取最后一个式子的值
  - {} 是代码段，没有返回值
    - 若直接定义成宏函数
    - 直接 printf 输出，就失去了 MAX 返回最大值的本质
    - ❓用 return 返回值
      - 需要声明
      - 但直接用表达式代表返回值更聪明
最终版代码

结果全部正确！

实现打印 LOG 宏#

代码
- 交付工作时，免去 log 信息，可以使用条件式编译
  - 编译时使用 "gcc -DDEBUG" 可以传入 DEBUG 宏定义
  - #else 后面定义一个空的宏替换
- 变参宏
  - 变参 '...' 取一个名字即可。eg. args...
- 宏中 "#"、"##" 使用
  - "#"：取字符串
  - "##"：连接
    - 解决 log 宏传入是空字符的情况：如果是空，frm 后面的 "," 会自动去除，可参考预编译结果👇
    - 参考替换文本宏-cppreference
    - ab 和 a##b 的区别
      - ab 不会将 a、b 代入再连接
      - 需 ## 连接的 a、b 对应的传入参数可以不定义
        
        预处理就会将这些未定义的变量名连接起来，连接后的变量名定义过即可

亮点笔记#

代码演示#

素数筛#

代码

对偶逻辑，控制缩进
- if continue
prime 数组前部分可以同时计数和存储（整体用来打标记）
- 一开始 prime [0]、prime [1] 并没有用，空闲着
- 不会出现超车的问题：偶数肯定是合数，素数至少隔一个才出现
第二个 for 循环的初始条件可以优化
- 初始条件：i * 2 → i * i
- 时间效率：O (Nlogn)→O (Nlognlogn)
- 因为比 i * i 小的合数肯定已经被比 i 小的数标记过了
  - 这样减少了前面一部分重复标记的次数，但不是完全
  - 完全避免重复标记要使用线性筛
- 危险点：i * i 指数增长，更可能溢出int 能存储的最大值
  - 是否可以提前加一个判断？不过可能带来更大的耗时
  - 换一个上限更高的存储 i * i 的数据类型

数组#

代码

输出
- 细节👇

声明、初始化#

编程技巧：多开 5 位，避免溢出，可以降低 bug 率

#define max_n 100
int arr[max_n + 5];

在函数内的变量空间都定义在栈区
- 栈区可以用羽毛球筒去理解，后进先出
- 栈区大小 (默认)：8MB≈800 万 Byte (字节)
在函数内声明的数组可能是不干净的，需手动初始化
- = {0};
- scanf 读入

for (int i = 0; i < max_n; i++) {
scanf("%d",arr + i);
}

- arr + i 等价于 &arr [i]& 不能少！
在函数外声明的数组
- 系统会自动将其清空为 0，类似于 = {0} 操作
- 可开辟大小受电脑内存限制，基本无限制
malloc、calloc、realloc 定义的数组在堆区，即使在函数内部定义

占用空间、地址#

sizeof () 对应的控制字符是 % lu，无符号长整型
数组名 arr 代表的就是数组的首地址，即 & arr [0]

printf ("% p % p\n", arr, &arr [0]); // 地址值一样

地址 + 1 偏移多少字节取决于地址表示的元素字节数

传参#

条件：外部和函数里参数表现形式一致
- 一维数组：int arr [100];
  - void func(int *num)
- 二维数组：int arr2[100][100];
  - void func2 (int **num) 报警告
    - num + 1 和 arr + 1 的表现形式不一致
    - num 是指向 int 指针的指针
    - num 和 num +1 的地址相差一个【指针】的大小，64 位操作系统里是 8 个字节
    - arr 和 arr + 1 的地址相差一个【一维数组】的大小，4 * 100 字节
  - void func2(int (*num)[100]) 可以
- 三维数组：int arr3 [100][100][32]
  - void func3(int (*num)[100][32]) 可以
  - (*num)[100][32] 可以写成 num [][100][32]
    - (*num) 和 num [] 表现形式一样，但本质其实不一样
❓q 指向的是 nil？就是 0x0

附加知识点#

数组可以表示三种信息
int arr [100]; //arr 作为参数传到函数，是作为数组首元素的地址的
1 取反是 - 2？推导一下
- 1： 0000...001
- 取反：1111...110
- 符号位不变，取反加一得：1000...010
- 即 - 2
- 结论：所有正整数的按位取反是其本身 + 1 的负数
包含 <math.h> 的源文件，在编译时添加 - lm，使用 gcc *.c -lm
编码习惯，一行不超过 80 个字符
控制字符 "%X"：大写的十六进制

思考点#

函数与宏谁更厉害？
- 宏能生成函数，宏可不是函数的爸爸？

Tips#

vim 自动补齐头文件的格式修改：加空格
- 进入～/.vimrc 文件，修改 SetTitle () 里对应的格式即可
宏的展开、嵌套，自己去摸索
参考工具书第 8 章 8.1、8.4 以及第 15 章

Bo2SS

5 数组与预处理命令

课程内容#

数组的定义与初始化#

素数筛#

线性筛#

二分查找法#

牛顿迭代法#

预处理命令#

字符串#

随堂练习#

实现没有 BUG 的 MAX 宏#

实现打印 LOG 宏#

亮点笔记#

代码演示#

素数筛#

数组#

声明、初始化#

占用空间、地址#

传参#

附加知识点#

思考点#

Tips#

课程速记#