c programming

Libra

2024-09-18

Language

C语言
- 程序是如何生成的
  - 预处理
    - 执行预处理指令
      - #include
        
        头文件包含
        
        文本替换
      - #define N 5
        
        宏定义
        
        文本替换
      - #define FOO(x) (1 + (x) * (x))
        
        宏函数
        
        原理：用“实参”替换“形参”，文本替换
        
        注意事项
        
        左括号应该紧贴宏函数的名字
        
        参数要加括号
        
        表达式要加括号
        
        好处
        
        避免函数调用的开销
        
        用来替换频繁调用且简短的函数
        
        提供一定的宏编程能力
  - 编译
    - 将预处理后的文件翻译成汇编代码
  - 汇编
    - 将汇编代码翻译成机器代码，生成目标文件
  - 链接
    - 将目标文件和库文件链接在一起，生成可执行程序
- 进程的虚拟内存空间
  - 内核
  - 栈
  - 堆
  - 数据段
  - 代码段
- 变量
  - 三要素
    - 变量名
      - 引用变量绑定的值
    - 类型
      - 规定了值的取值范围
        
        编码
        
        长度
      - 限定了值的操作
    - 值
- 格式化输入和输出
  - 输入输出模型
  - printf
    - 格式：printf(格式串，表达式1, …)
    - 原理：打印格式串中的内容，并用后面表达式的值替换转换说明。
    - 格式串
      - 普通字符
        
        原样输出
      - 转换说明
        
        %m.pX | %-m.pX
        
        m.p
        
        控制输出格式
        
        m: 最小字段宽度
        
        p: 精度。具体含义依赖于后面的X
        
        d: 最少显示数字的个数，不够前面补0
        
        f, lf：显示小数点后几位
        
        X
        
        如何转换类型
  - scanf
    - 格式：scanf(格式串，表达式1, ….)
    - 原理
      - 模式匹配函数 (格式串 <–> stdin中的字符)
      - 从左到右，根据格式串，匹配stdin中的字符；如果匹配成功，继续匹配下一项；如果匹配失败，立刻返回；返回值表示成功匹配的转换说明个数。
    - 格式串
      - 普通字符
        
        精确匹配
      - 空白字符 (‘ ‘, ‘\n’, ‘\t’, ‘\v’, ‘\f’)
        
        匹配任意多个空白字符，包括0个
      - 转换说明
        
        %d: 忽略前置的空白字符，匹配一个有符号的十进制整数
        
        %f: 忽略前置的空白字符，匹配一个浮点数
        
        %c: 匹配一个字符
- 基本数据类型
  - 整数
    - 无符号整数
      - 编码
        
        二进制编码
    - 有符号整数
      - 编码
        
        补码
        
        x + (~x) = 11…1 = -1
        
        x + (-x) = 100…0 = 0
  - 浮点数
    - 编码
      - IEEE 754
    - 不精确的
  - 字符
    - 编码
      - ASCII
        
        ‘\0’: 0
        
        ‘ ‘: 32
        
        ‘0’: 48
        
        ‘A’: 65
        
        ‘a’: 97
    - 值的书写方式
      - 字符转义序列
        
        \n
        
        \r
        
        \t
        
        \
        
        '
        
        "
      - 数字转义序列
        
        八进制
        
        以\开头，后面接最多三个八进制数字
        
        \101
        
        十六进制
        
        以\x开头，后面接十六进制数字
        
        \x41
    - 值的操作
      - C语言把字符类型当作小的整数来处理
      - <ctype.h>
        
        字符分类函数
        
        字符转换函数
        
        c = tolower(c)
        
        c = toupper(c)
    - 值的读写
      - 读
        
        scanf + %c
        
        c = getchar()
      - 写
        
        printf + %c
        
        putchar(c)
  - 类型转换
    - 隐式转换
      - 整数提升
      - 范围小 –> 范围大：int –> long –> long long –> float –> double
      - 同一转换等级，有符号 –> 无符号
    - 显示转换
      - 格式：(type-name) expression
      - 使用场景
        
        求浮点数的小数部分
        
        说明注释，注意这里发生了类型转换，可能会丢失精度。
        
        避免溢出
        
        精确控制类型转换
  - 给类型定义别名
    - 格式：typedef 类型别名;
    - 好处
      - 提高代码的可读性
      - 提高代码的可移植性
  - sizeof运算符
    - 作用：计算某一类型值所占的内存长度 (以字节为单位)
- 表达式
  - 计算某个值的公式，最简单的表达式：变量和常量
  - 运算符：连接表达式，创建更复杂的表达式
    - 优先级
    - 结合性
  - 赋值
    - v = expr
    - 值：赋值后，左边表达式的值 (v)
    - 副作用：改变了 v 的值
  - 算术
    - 两个整数相除，结果为整数 (向0取整)
    - 浮点数不支持 % 运算
    - 余数可能为负，它的符号和被除数相同
  - 自增和自减
    - i++
      - 值：原来的i
      - 副作用：i自增
    - ++i
      - 值：原来的 i 加 1
      - 副作用：i自增
  - 位运算
    - 移位
      - <<: 左移n位，相当于乘以2的n次方
      - >>：右移n位，相当于除以2的n次方
      - 注意事项
        
        不要对有符号数进行右移运算
        
        <<和>>没有副作用
    - 按位
      - ~
      - &
      - |
      - ^
        
        a ^ a = 0
        
        a ^ 0 = a
        
        a ^ b = b ^ a
        
        (a ^ b) ^ c = a ^ (b ^ c)
    - 常见的面试题
      - 判断一个数是否为奇数
        
        n & 0x1
      - 判断一个数是否是2的幂
        
        (n & n-1) == 0
      - 求一个数的 last set bit
        
        n & -n
      - 交换两个整数 (不使用中间临时变量)
      - 找单独的数
      - 找两个单独的数
- 语句
  - 表达式语句
  - 分支语句
    - if语句
    - switch语句
      - 注意事项
        
        switch 后面的表达式必须是整数 (字符、枚举)
        
        多个 case 标签可以共用一组语句
        
        警惕 case 穿透现象
  - 循环语句
    - while (expr) statement
      - 在循环体前设置退出点
    - do statement while (expr);
      - 在循环体后设置退出点
    - for (初始语句 expr2; expr3) statement
      - 在循环体前设置退出点
  - 跳转语句
    - break
    - continue
    - goto
    - return
  - 空语句
    - ;
  - 复合语句
    - { statements }
- 数组
  - 一维数组
    - 内存模型
      - a. 一片连续的内存空间，并且这片空间又被划分为大小相等的小空间
        
        目的是为了随机访问数组的元素
      - b. 为什么数组的下标一般从 0 开始?
        
        寻址公式：i_addr = base_addr + i * sizeof(elem)
      - c. 为什么一般来说数组的效率高于链表？
        
        数组是连续的，所以数组的空间局部性更好
        
        数组占用的内存空间比链表少
    - 定义和初始化
      - int arr[] = {1, 2, 3, 4, 5}
        
        变量名：arr
        
        类型：int[5]
    - 操作
      - 取下标 []
    - 输入和输出
      - 数组和for循环是一对好伙伴
    - 求数组的长度
      - SIZE(a) (sizeof(a) / sizeof(a[0]))
  - 二维数组
    - 本质：元素是一维数组的数组
    - 定义和初始化
      - int matrix[3][4] = { {1, 2, 3, 4}, {2, 2, 3, 4}, {3, 2, 3, 4}}
        
        matrix: int[3][4]
        
        matrix[1]: int[4]
        
        matrix[1][1]: int
    - 操作
      - 取下标 []
    - 输入和输出
      - 二维数组和嵌套的for循环是一对好伙伴
  - 常量数组
    - const int arr[] = {1, 2, 3, 4};
    - 常量数组的元素不能被修改
      - 一般用常量数组存储不会发生改变的数据 (静态数据)
    - 好处
      - 安全
      - 有利于编译器优化程序
- 函数
  - Function
    - 函数的功能应该越单一越好；函数的实现越高效越好
  - C语言是一门面向过程 (函数) 的语言
    - 函数是C语言程序的基本构建组件，C语言程序是由函数之间的相互调用完成的。
  - 语法结构
    - 函数的声明
      - bool is_prime(int n);
    - 函数的定义
      - bool is_prime(int n) { … }
    - 函数的调用
      - is_prime(34)
    - 函数指针
      - is_prime
  - 参数传递
    - 实际参数 –> 形式参数
    - 值传递 (复制)
      - 局限性：不能被调函数中修改主调函数中的值
        
        解决方案：指针
      - 特例：数组作为参数传递时，会退化成指向它第一个元素的指针。
        
        优点
        
        避免大量数据的复制
        
        避免值传递的局限性
        
        可以让函数调用更灵活
        
        缺点：丢失了长度信息
  - 局部变量
    - 作用域：能够引用变量的文本区域；作用于编译期
      - 块作用域
    - 存储期限：变量”存活”的时间长度；作用于运行时
      - 默认为自动存储期限
      - 通过static关键字，修改为静态存储期限
  - 外部变量
    - 作用域
      - 文本作用域
    - 存储期限
      - 静态存储期限
  - 递归
    - 名字
      - recursion
        
        走重复的路
        
        一条代码路径执行了一遍又一遍
      - 递归
        
        递
        
        把大问题分解成若干个子问题，子问题和大问题的求解方式一致，只是问题规模不一致。
        
        归
        
        把子问题的解合并成大问题的解
    - 例子
      - 电影院的例子
      - Fibnacci数列
        
        不是所有具有递归结构的问题，都适合用递归求解
      - 汉诺塔
        
        边界条件
        
        递归关系
- 指针
  - 指针基础
    - 概念
      - 地址：字节是计算机最小的寻址单位；每个字节都有地址
      - 变量的地址：变量首字节的地址
        
        &x
      - 指针就是地址
      - 指针变量：存放地址值的变量
      - 野指针
        
        不知道指向哪个数据的指针
        
        危害：对野指针进行解引用，会导致未定义的行为
      - 空指针
        
        不指向任何对象的指针，在C语言中用NULL表示
    - 语法
      - 定义
        
        int* p;
        
        变量名：p
        
        类型：int *
      - 赋值
        
        p = &i;
        
        p = q;
        
        p = NULL;
    - 基本操作
      - 解引用：*
        
        i: 直接访问，访问内存一次
        
        *p: 间接访问，访问内存两次
    - 应用
      - 作为参数
        
        在被调函数中，通过指针变量，修改主调函数中的值
        
        传入参数：const int* p
        
        不能通过指针变量，修改主调函数中的值
        
        传出参数: int* p
        
        通过指针变量，修改主调函数中的值
        
        作为返回值来用
      - 作为返回值
        
        千万不能返回指向当前栈帧区域的指针！
    - const
      - 本质：限制变量访问内存的权限
      - int *p = &i;
        
        p代表的内存：R/W
        
        *p代表的内存：R/W
      - const int *p = &i;
        
        p代表的内存：R/W
        
        *p代表的内存：R
      - int * const p = &i;
        
        p代表的内存：R
        
        *p代表的内存：R/W
      - const int * const p = &i;
        
        p代表的内存：R
        
        *p代表的内存：R
  - 指针和数组的关系
    - a. 可以利用指针处理数组
      - 指针的算术运算
        
        指针加上一个整数
        
        指针减去一个整数
        
        两个指针相减
        
        定义指针的比较运算
        
        p == q 等价于 p - q == 0
        
        p > q 等价于 p - q > 0
        
        p < q 等价于 p - q < 0
      - ++和*的组合
        
        p++，(p++)
        
        值：*p
        
        副作用：p自增
        
        (*p)++
        
        值：*p
        
        副作用：*p 自增
        
        ++*p, ++(*p)
        
        值：*p + 1
        
        副作用：*p自增
        
        *++p, *(++p)
        
        值：*(p + 1)
        
        副作用：p自增
    - b. 数组名可以作为指向它第一个元素的指针
    - c. 指针也支持取下标运算
      - p[i] = *(p + i) = *(i + p) = i[p]
  - 指针的高级应用
    - 动态内存分配
      - 为什么需要动态内存分配
        
        栈帧的大小需要在编译时确定
        
        栈空间不能存具有动态大小的数据
        
        栈的大小是受限的
        
        栈空间不能存很大的数据
        
        每个线程都有自己的栈
        
        栈空间不适合存放线程之间共享的数据
      - 基础概念
        
        空指针：不指向任何对象的指针
        
        不能解引用
        
        悬空指针
        
        指向已释放的堆内存空间，是野指针的一种
        
        通用指针类型：void*
        
        不能解引用
        
        可以和其它类型的指针相互转换 (隐式转换)
      - API
        
        void* malloc(size_t size)
        
        void* calloc(size_t n, size_t size)
        
        void* realloc(void* ptr, size_t size)
        
        注意事项：ptr一定是malloc, calloc, realloc 的返回值
        
        void free(void* ptr)
        
        注意事项
        
        ptr一定是malloc, calloc, realloc 的返回值
        
        double free
        
        use after free
        
        内存泄漏
    - 二级指针
      - 本质：指向一级指针变量的指针
      - 声明
        
        Node** p;
      - 指针作为参数，传递一级指针，还是传递二级指针
        
        宗旨：想修改哪个变量，就传递那个变量的地址
        
        传值
        
        const int* p
        
        修改指针变量指向的对象
        
        int* p
        
        修改指针变量的值 (指向)
    - 函数指针
      - 概念：指向函数的指针
      - 语法
        
        定义函数指针变量
        
        void (*func) (int, int)
        
        函数地址
        
        foo
        
        &foo
        
        通过函数指针调用函数
        
        func(实参列表)
        
        (*func)(实参列表)
      - 作用
        
        C语言是通过函数指针，来模拟函数式编程
        
        解耦合
        
        易组合
      - qsort
        
        作用：对任意数组排序
        
        参数
        
        base
        
        数组的起始地址
        
        nmemb
        
        待排序元素的个数
        
        size
        
        每个元素的大小
        
        int (compare) (const void p1, const void* p2)
        
        钩子函数
- 字符串
  - 字符串字面值
    - 书写方式
      - 三种
    - 内存布局
      - 代码段 (只读)
      - 以字符数组的形式存储，以 \0 字符结尾
    - 操作
      - 将字符串字面值看作是字符常量数组
        
        取下标
  - 字符串变量
    - 内存模型：C语言没有真正的字符串类型，字符串变量依赖字符数组存在。
    - 定义并初始化
      - char s[] = { ‘H’, ‘e’, ‘l’, ‘l’, ‘o’, ‘\0’ };
      - char s[] = “Hello”;
        
        推荐1
      - char s[10] = “Hello”;
        
        推荐2
      - char s[6] = “Hello”;
      - char s[5] = “Hello”;
        
        不是字符串
    - 操作
      - 字符串变量依赖字符数组存在
        
        取下标 []
      - <string.h>
        
        strlen
        
        求字符串的长度，不计算空字符 ‘\0’
        
        strcpy, strncpy
        
        字符串复制
        
        strcat, strncat
        
        字符串的拼接
        
        strcmp
        
        字符串的比较
        
        返回值
        
        <0: s1 < s2
        
        =0: s1 == s2
        
        0: s1 > s2
        
        比较规则
        
        字典序 (ASCII)
    - 输入输出
      - 输出
        
        printf + %s
        
        puts
      - 输入
        
        scanf + %s
        
        忽略前置的空白字符，读取字符存入字符数组，遇到空白字符结束
        
        读入单词
        
        gets
        
        读取一行数据，并把’\n’替换成’\0’
        
        缺陷：不检查数组是否越界
        
        fgets(str, n, stdin)
        
        读取一行数据，存储换行符，并在换行符后面添加 ‘\0’
  - 字符串数组
    - 二维字符数组
      - 可能浪费内存空间
      - 不灵活
    - 字符指针数组
      - 非常灵活
    - 命令行参数
      - 操作系统传递给 main 函数的参数
        
        int main(int argc, char* argv[])
      - 参数转换
        
        sscanf(argv[i], ….)
      - 作用
        
        传递不同参数，程序展示不同的行为
        
        ls
        
        ls -l
        
        有利于编写通用的工具
        
        cp src dst
- 结构体
  - 定义结构体类型
  - 定义结构体类型的变量，并赋初始值
  - 内存模型
    - a. 一片连续的内存空间
    - b. 成员是按声明的顺序依次存放
    - c. 在结构体的中间或者末尾，可能会出现填充
  - 操作
    - 访问成员
      - s.name
    - 赋值 (结构体的复制)
      - s2 = s1
      - 结构体作为参数或返回值时，会涉及整个结构体的复制！
        
        传递指向结构体的指针
    - 语法糖
      - p->name 等价于 (*p).name
  - 给结构体类型定义别名
    - 不要给指针类型定义别名！
- 枚举
  - 语法
    - 定义枚举类型
    - 定义枚举类型的变量
  - 作用：表示一些离散值 (扑克牌的花色、状态、类别…)
  - 枚举值是整数！
- 文件流
  - 模型
    - 1. 流模型
      - 将读端和写端解耦
      - 程序员不需要手动care文件的位置
    - 1. 程序员视角下的文件
      - 字节序列
      - pos: 下一个读写的字节
      - EOF: 标识着文件的末尾
    - 1. 文本文件 & 二进制文件
    - 1. 缓冲区类型
      - 满缓冲
      - 行缓冲
        
        stdin, stdout
      - 无缓冲
        
        stderr
        
        打印错误信息
    - 1. 标准流
      - stdin: 0
      - stdout: 1
      - stderr: 2
  - API
    - 打开
      - fopen
        
        filename
        
        绝对路径
        
        相对路径
        
        mode
        
        r
        
        存在
        
        不会清空
        
        不存在
        
        打开失败
        
        w
        
        存在
        
        清空
        
        不存在
        
        创建
        
        a
        
        存在
        
        不清空
        
        不存在
        
        创建
    - 关闭
      - fclose
    - 读写
      - 以文本方式
        
        a. 一个字符一个字符
        
        fgetc (stream)
        
        fputc (c, stream)
        
        b. 一行一行
        
        fgets
        
        str
        
        count
        
        stream
        
        fputs
        
        str
        
        stream
        
        c. 格式化地读写
        
        fscanf
        
        fprintf
      - 以二进制方式
        
        fread
        
        fwrite
    - 移动文件位置
      - fseek
        
        stream
        
        offset
        
        whence
        
        参照点
        
        SEEK_SET
        
        SEEK_CUR
        
        SEEK_END
      - ftell
      - rewind