C 语言系统学习

C 语言编译过程

预处理

• #include ：头文件包含（把头文件中的内容复制到指令所在的位置）
• #define N 5：宏定义（简单的文本替换）
• #define FOO(x) (1 + (x) * (x))：带参数的宏（宏函数）（文本替换：用“实参”替换“形参”）
• 宏函数注意事项：

• 为什么要用宏函数？
  • 避免函数调用的开销（频繁调用且简短的函数可以用宏函数）；
  • 提供了一定的“宏编程”能力。

编译

• 经过预处理器处理的文件会交给编译器进行编译；
• 编译器会把程序翻译成对应平台的汇编代码。

汇编

• 汇编器会把生成的汇编代码翻译成对应平台的机器代码（目标文件）；
• 此时程序还不能运行，还需要经过最后一个步骤——链接。

链接

• 在链接阶段，链接器会把由汇编器生成的目标代码和程序需要的其它附加代码整合在一起，生成最终可执行的程序；
• 这些附加代码包括程序用到的库函数（如 printf 函数）。

汇总

• 整个过程如下图所示：

虚拟内存空间

• 程序经过预处理、编译和链接，最终生成可执行文件；
• 可执行文件被操作系统加载到内存，程序得以运行，运行中的程序称为进程（process）；
• 每个进程都有自己的虚拟内存空间，如下图所示：

变量

• 变量要绑定一个值：

输入输出模型

• 输入输出模型是为了平衡内存和外部设备的速度差异。

printf

• printf = print + format 打印＋格式化；
• 作用：打印格式串中的内容，并用后面表达式的值替换转换说明（即 %d 、%f 等占位符）。

• 格式串：

scanf

• 原理：从左到右，依次匹配格式串中的每一项；

• scanf 返回匹配成功的转换说明的个数；
• 能够匹配任意多个空白字符；
• 如果有一项匹配不成功，scanf 会立刻返回。

整数的编码

有/无符号整数

• 无符号整数：

• 有符号整数：

• 两个性质：

• 原码、补码、反码

  • 正数的原码、反码、补码均相同。

  • 原码：用最高位表示符号位，其余位表示数值位的编码称为原码。其中，正数的符号位为 0，负数的符号位为 1。

  • 负数的反码：把原码的符号位保持不变，数值位逐位取反，即可得原码的反码。

  • 负数的补码：在反码的基础上加 1 即得该原码的补码。

  • 例如：

    • +11 的原码为: 0000 1011

    • +11 的反码为: 0000 1011

    • +11 的补码为: 0000 1011

    • -7 的原码为：1000 0111

    • -7 的反码为：1111 1000

    • -7 的补码为：1111 1001

  • 注意：

    • 对补码再求一次补码操作就可得该补码对应的原码。
    • 在计算机系统中，数值一律用补码来表示（存储）。
    • 使用补码，可以将符号位和其他位统一处理;

浮点数

• 浮点数是不精确的

字符

• 字符的编码为 ASCII：

• 类型通用的两个特征：

• 表示值：

• 支持哪些操作：

• 读/写（和用户操作）

• 惯用法：

类型转换

• 隐式转换：不要将有符号整数和无符号整数混合运算

• 强制转换

定义别名

• 定义别名的作用

sizeof 运算符

• sizeof() 运算符

void 类型

• void 是一个类型
  • 空类型
  • 没有值

表达式

• 表达式：计算某个值的公式
• 最简单的表达式：变量和常量
• 运算符：连接表达式，创建更复杂的表达式
• 属性：优先级、结合性

位运算符

• i<<n：如果没有溢出，左移 $n$ 位相当于乘以 $2^{n}$；
• i>>n： 右移 $n$ 位，相当于除以 $2^{n}$（向下取整）；
  • 如果 i 是无符号值或者非负值，则在左边补 0；
  • 如果 i 是负值，其结果是由实现定义的，有可能在左边补 0，也有可能在左边补 1。
• 为了可移植性，最好仅对无符号数进行移位运算。

问题一

• 判断一个数是否奇数：
  • 需要注意 -1 % 2 == -1 ，因此不能使用 n % 2 == 1 来判断。

1
2
3
4

bool isOdd(int n)
{
	return (n % 2 != 0);
}

• 采用二进制的形式：

1
2
3
4

bool isOdd(int n)
{
	return (n & 0x1);//奇数的最后一位一定是1，掩码（mask）
}

问题二

• 如何判断一个非 0 整数是否为 2 的幂 （1，2，4，8，16，......） ？
  • 从二进制中能够看到只有一位为 1，其余都是 0。

• 代码：

1
2
3
4

bool isPowerOf2(int n)
{
	return (n & n-1) == 0;
}

问题三

• 给定一个值不为 0 的整数，请找出值为 1 的最低有效位（last set bit）。

• 代码：

1
2
3
4

int lastSetBit(int n)
{
	return n & -n;
}

• 原理：
  • n 的原码（补码）：0001 1000
  • -n 的补码：0110 1000
  • n & -n 的码：0000 1000
  • 在计算机系统中，数值一律用补码来表示（存储）。

问题四

• 给定两个不同的整数 a 和 b，请交换它们两个的值（要求不使用中间临时变量）。
  • 关键是找到一对逆运算，如 a=a+b-b;
• 代码：

1
2
3
4
5
6

void swap(int a,int b)
{
	a = a + b;
	b = a - b;
	a = a - b;
}

• 但是使用加法容易造成溢出的情况，可以使用异或这个逆运算。

1
2
3
4
5
6

void swap(int a,int b)
{
	a = a ^ b;
	b = a ^ b;
	a = a ^ b;
}

问题五

• 一个数组中有一种数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这种数？
• 关键部分：

1
2
3
4
5
6
7
8
9
10

//采用异或运算找到数组中出现奇数次的数
int yihuo_find(vector<int>& a)
{
    int eor = 0;
    for(int i=0;i<a.size();i++)
    {
        eor = eor ^ a[i];//用eor与数组中的所有元素相异或
    }
    return eor;
}

• 代码：

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

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

//采用异或运算找到数组中出现奇数次的数
int yihuo_find(vector<int>& a)
{
    int eor = 0;
    for(int i=0;i<a.size();i++)
    {
        eor = eor ^ a[i];//用eor与数组中的所有元素相异或
    }
    return eor;
}

int main()
{
    vector<int>  vec1= {1, 1, 3, 3, 3}; //3是奇数个
    int ans = yihuo_find(vec1);
    printf("%d",ans);
    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

• 证明：
  • 1、具有 a^a=0 和 a^0=a 的性质；
  • 2、偶数个数据累积异或后是 0，奇数个数据累积异或后就剩下它自身。

问题六

• 一个数组中有两个不相等的数出现了奇数次，其他数都出现了偶数次，怎么找到并打印这两个数？
• 关键代码：

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

//采用异或运算找到数组中出现奇数次的两个数a、b
void yihuo_find(vector<int>& a,int& ans_1,int& ans_2)
{
    int eor = 0,eor_2 = 0;
    for(int i=0;i<a.size();i++)
    {
        eor = eor ^ a[i];//找到eor = a^b
    }
    //找到eor = a^b中的最右侧的1（问题三的函数）
    int OnlyOne = lastSetBit(eor);
    //由于eor = a^b中的最右侧为1，a和b在这一位一定不相等
    //只需要在数组中找到这一位只为1的数再做一次eor即可把a或者b找出来
    for(int i=0;i<a.size();i++)
    {
        if((OnlyOne & a[i]) != 0)
        {
            eor_2 = eor_2 ^ a[i];//找到eor_2 = a或者eor_2 = b
        }
    }
    ans_1 = eor_2;
    ans_2 = eor_2 ^ eor;
}

• 代码：

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

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <vector>
using namespace std;

//把int类型最右侧的1找出来
int lastSetBit(int n)
{
	return n & -n;
}

//采用异或运算找到数组中出现奇数次的两个数a、b
void yihuo_find(vector<int>& a,int& ans_1,int& ans_2)
{
    int eor = 0,eor_2 = 0;
    for(int i=0;i<a.size();i++)
    {
        eor = eor ^ a[i];//找到eor = a^b
    }
    //找到eor = a^b中的最右侧的1
    int OnlyOne = yihuo_last_one(eor);
    //由于eor = a^b中的最右侧为1，a和b在这一位一定不相等
    //只需要在数组中找到这一位只为1的数再做一次eor即可把a或者b找出来
    for(int i=0;i<a.size();i++)
    {
        if((OnlyOne & a[i]) != 0)
        {
            eor_2 = eor_2 ^ a[i];//找到eor_2 = a或者eor_2 = b
        }
    }
    ans_1 = eor_2;
    ans_2 = eor_2 ^ eor;
}

int main()
{
    int ans_1=0,ans_2=0;
    vector<int>  vec1= {1, 1, 3, 3, 3, 6}; 
    yihuo_find(vec1,ans_1,ans_2);
    printf("%d、%d\n",ans_1,ans_2);
    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

语句

• 语句的分类：

数组

数组的内存模型

• 连续的一片内存空间，并且会划分成大小相等的小空间。
• 使用同一类型使得能够随机访问元素。

• 数组的索引一般是从 0 开始的：

• 数组效率一般高于链表效率：
  • 空间利用率更高；
  • 空间局部性（数组是连续的）。

数组的定义

• 数组的定义：
  • 数组的操作只有取下标。

• 求数组的大小的宏函数：

1

#define SIZE(a) (sizeof(a) / sizeof(a[0]))

• 类型的判断：
  • 先看标识符；
  • 从标识符表示往右看；
  • 再从标识符往左看得到完整的类型信息，例：

多维数组

• 注意：C 语言只有一维数组，多维数组本质上也是一维数组。

常量数组

• 常量数组：元素不能够修改。
  • 安全，用于存储静态数组；
  • 效率高，编译器能够对常量数组做一些优化。

函数

函数的特征

• 数学上的函数：有返回值，没有副作用；
• C 语言的函数：可以没有返回值，可以有副作用。

函数的准则

• 函数的功能应该越单一越好（能够复用），函数的实现越高效越好；
• 函数是 C 语言的“基本构建组件”，C 语言的本质就是函数之间的调用。

函数相关概念

• 函数定义（隐含了声明）：void foo(int a) {...}
• 函数声明：void foo(int a);
• 函数调用：foo(3);
• 函数指针：foo 或 &foo

参数传递

• 参数传递的内存调用示例：

• 特例：数组作为参数传递时，会退化成指向第一个元素的指针！

局部变量和外部变量

• 作用域：编译时变量名可以被引用的文本范围；
• 存储期限：运行时变量绑定的值可以被引用的时间长度：

• 局部变量：定义在函数里面的变量；
  • 作用域：块作用域，从定义开始到块的末尾（块：大括号 {} ）。
  • 存储期限：
    • 默认——自动存储期限-栈
    • static ——静态存储期限-数据段
• 默认存储期限示例：

• 静态存储期限示例：

• 外部变量（全局变量）：定义在函数外面的变量。
  • 作用域：文件作用域，从定义开始到文件末尾。
  • 存储期限：静态存储期限。

相关问题

• 静态存储期限的局部变量和外部变量有什么区别？
  • 答：作用域不同！
• 静态储存期限的局部变量有什么作用？（使用场景）
  • 答：能够存储上一次函数调用的状态！

递归

递归的含义

• 递归的含义：

• 具有递归结构的问题，不一定要用递归求解。
• 递归可能存在大量重复计算的问题。
• 可以采用动态规划来避免重复计算的问题：顺序求解子问题，并将子问题的解保存起来，从而避免重复计算，最终求解到大问题。

汉诺塔问题

• 汉诺塔问题：

约瑟夫环问题

• 约瑟夫环问题：

• 更一般的约瑟夫环问题：

递归三问

• 递归三问：什么时候使用递归？

指针基础

内存模型

• 指针的内存模型：
  • 计算机的最小寻址单位——字节
  • 变量的地址——变量首字节的地址
  • 指针——地址
  • 指针变量——存储地址值的变量

指针的操作

• 指针的定义：
  • 变量名：p
  • 类型：int*
  • 注意事项：声明指针变量时，需要指定它指向对象的类型

• 指针的两个基本操作：
  • 取地址运算符：& —— &i
  • 解引用运算符：* —— *p
    • 指针变量 p 指向对象的别名
    • 间接引用——访问内存两次

野指针

• 野指针：不知道指向哪块数据。
  • 对野指针进行解引用操作，是未定义行为。

• 如何给指针变量赋值？

  • int *p = &i;
  • int *q = p; —— 指针变量 p，q 指向同一个对象。
  • p = NULL;：空指针，不指向任何对象指针。

• 指针赋值示例：

指针的应用

• 作为参数——在被调函数中修改主调函数的值。

• 指针作为返回值。
  • 教训：不要返回指向当前栈帧的指针！

指针常量和常量指针

• 指针变量 p 对内存 1，内存 2 都有写权限：

• 常量指针，对内存 1 有写权限：

• 指针常量，对内存 2 有写权限：

• 两边加 const 修饰符，对内存 1，内存 2 都没有写权限：

• 本质：限制变量的写权限！

传入参数和传出参数

• 传入参数：在函数里面，不会（不能够）通过指针变量修改它指向的对象：

• 传出参数：在函数里面，可以通过指针变量修改它指向的对象！

指针的算术运算

• 画图表现数组和指针：

• 指针加上一个整数，结果还是一个指针：
  • 指针加上一个整数 n，其含义在于指针向右偏移了 n 个单位；
  • 单位表示的是对象类型的大小。

• 指针减去一个整数 n，其含义在于指针向左偏移了 n 个单位：

• 两个指针相减，结果是一个整数：

• 根据指针减法，可以定义指针的比较运算：

指针和数组的关系

• 采用指针处理数组：

• * 和 ++ 的组合，-- 同理：

• 指针运算的组合的示例：

• 在必要的时候，数组可以退化成指向它索引为 0 元素的指针：

• 数组退化的几种情况总结

  • 数组作为参数：fun(arr);
  • 数组在赋值表达式的右边：int* p = arr;
  • 数组参与算术运算：arr+3;

• 指针也支持取下标运算：

• 下标可以放到中括号 [] 前面：

字符串

字符串字面值

• 三种书写方式：
  • 如第三种方式，如果两个字符串字面值之间仅有空白字符，可以认为这两个字符串字面值是相邻的，相邻的字符串字面值在编译的时候就会拼接成一个字符串字面值。

• 内存模型：
  • 字符串字面值在代码段——不可被修改的。
  • 可以把字符串字面值看作常量数组。

• 字符串字面值支持的操作：
  • 常量数组能支持的操作，字符串字面值都支持，例：
  • 十进制转换为十六进制的函数：

字符串变量

• 总纲：
  • C 语言中没有字符串类型—— string、String
  • C 语言中的字符串依赖字符数组存在！
  • C 语言字符串是一种“逻辑类型”。

• 注意事项：
  • 字符串必须以 '\0' 结尾！
  • 在 C 语言中求字符串的长度不是 $O(1)$ 的时间复杂度，不能写成下面的例子：

声明和初始化

• 注意数组的初始化和字符串的字面值。

读和写（和用户交互）

• printf()+%s 输出字符串

• scanf()+%s 读字符串
  • %s 的匹配规则：
    • 忽略前置空白的字符，读取字符填入字符数组；
    • 遇到空白字符结束。
  • 缺点：
    • 不能够存储空白字符；
    • 不会检查数组越界。

• puts() 函数：puts(str); 等价于 printf("%s\n",str);

• gets() 函数
  • 从 stdin（标准输入流） 中读取一行数据，传入字符数组，并将 '\n' 替换为 '\0'；
  • 缺陷：不会检查数组越界。

• fgets() 函数
  • 和 gets() 函数的区别：
    • 会检查是否越界；
    • 会存储 '\n' 符，并在后面添加 '\0'。

字符串库函数

• 需要引入 #include <string.h> 库。

strlen

• strlen() 的实现和遍历字符串的惯用法：

• strlen() 不会计算 '\0'：

strcpy() 和 strncpy() 函数

• strcpy() 函数不检查数组越界，strncpy() 函数要设定最大拷贝的数量。

• strcpy() 函数的实现和惯用法：
  • 将赋值运算符右侧的"表达式”的值赋给左侧的变量，赋值表达式的值就是被赋值的变量的值。
  • 例如：a=(b=5) 相当于 b=5 和 a=b 两个赋值表达式，因此 a 的值等于 5，整个赋值表达式的值也等于 5。

• strncpy() 函数的实现：

strcat() 和 strncat() 函数

• strcat() 函数不检查数组越界，strncat() 函数要设定最大拷贝的数量。

• strcat() 函数的实现：

• strncat() 函数的实现：

strcmp()函数

• 字符串的比较：strcmp() 函数
• 比较规则：字典序（ASCII）

• strcmp() 函数的实现：

字符串数组

字符串数组

• 字符数组的数组——二维字符数组
  • 缺陷：
    • 浪费内存空间；
    • 交换字符串不方便。
  • 初始化的时候是数组初始化式。

字符指针数组

• 储存的是字符指针，比较灵活，不会造成内存空间的浪费；
• 直接初始化的时候是字面值，字符串存储在代码段，无法修改；
• 需要能够修改的字符串要先定义字符串变量再合并到字符指针数组。

命令行参数

• 命令行参数可以认为是操作系有调用 main() 函数时传递的参数。
• 命令行参数和从 stdin （标准输入）读取数据有什么区别？
  • 命令行参数：程序还未执行；
  • 从 stdin 读取数据：程序已经运行。
• 命令行参数有什么作用？
  • cp src dst：写一些非常通用的程序；
  • ls -l ：改变程序的行为，参数不同，行为不同。

• argc : argument count，命令行参数的个数；
• argv：argument vector ，命令行参数，命令行参数都是字符串。
  • argv[0]：表示可执行程序的路径。

• 命令行参数的内存模型：

• 命令行参数的类型转换（sscanf() 函数)：

• 不同的指定格式（类型）读取函数，从不同的输入中读取数据：

结构体

结构体的含义

• 对象的含义：
  • 属性：静态数据；
  • 方法：行为。
• C 语言的结构体类似其它语言的“类”，不一样的是，结构体只有属性没有方法。

结构体的语法

• 结构体的语法：

• 一般来说，使用 typedef 给 struct 类型取别名 Student，这样就可以直接使用 Student a; 来定义结构体。

• 匿名结构体，只能被使用一次

结构体的内存模型

• 一片连续的内存空间；
• 会按声明的顺序存放每一个成员；
• 在结构体变量的中间或后面，可能会有填充（由于以前的数据总线只有 32 bit ，因此填充是为了对齐，对齐是为了更快地访问数据）。

结构体变量的操作

• 获取成员和赋值（结构体变量的复制），但是由于结构体的参数量可能很大，所以往往更习惯传递一个指向结构体变量的指针。

• 结构体指针操作的语法糖：

枚举

• 枚举的作用：表示一些离散值（类别或者状态）
• 枚举的定义和用法：

动态内存分配

• 为什么要在堆上分配空间？
  • 因为栈空间是受限的！
    • 栈帧的大小是在编译期间确定的，而且栈不能存放动态大小的数据；
    • 栈空间比较小：
      • 主线程：8M；
      • 其他线程：2M；
      • 因此栈上不能存放很大的数据。
    • 每个线程都有自己的栈，所以栈空间最好不要放多线程共享的数据。

堆空间

• 堆空间的内存模型：

• 如何申请堆空间？

• 在堆上成功创建连续的内存空间后会返回指向新内存块的指针，创建失败则返回空指针。

• calloc() 函数的示例代码：

1
2
3
4
5
6
7
8
9

int main(void)
{
	int *p = calloc(100,sizeof(int));
	if(p==NULL)
	{
		printf("Error: calloc failed\n");
		exit(1);
	}
}

• 其中 void* 是通用指针，作用是可以和其它类型指针相互转换。
  • 如果 void* 指向对象的类型还不确定，不能够直接操作通用指针（例如对指针进行解引用等操作）。

动态数组

• 自定义实现动态数组的模型：

• 依赖关系如下：
  • 依赖接口，不需要依赖具体的实现！

• realloc() 函数的缩容和扩容原理

• 扩容代码：

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

void grow_capacity(Vector* v)
{
    int new_capacity = v->capacity < PREALLOC_MAX ?
        v->capacity * 2 : v->capacity+PREALLOC_MAX;
    
    //下面代码有问题，realloc失败会返回NULL，原来的内存空间不会被释放，造成内存泄漏
    //v->elements = realloc(v->elements,new_capacity * sizeof(E));
    
    //正确代码写法
    E* p = realloc(v->elements,new_capacity * sizeof(E));
    if(p == NULL)
    {
        printf("Error: realloc failed in grow_capacity!");
        exit(1);
    }

    v->elements = p;
    v->capacity = new_capacity;
}

• 大端法和小端法

• free() 函数的使用问题：
  • free() 函数使用之后，其原本指针属于悬空指针（野指针的一种），因此
    • 要避免 free() 函数使用多次的问题（double free）；
    • free() 函数使用之后继续使用原本的指针（use after free）；
  • 当堆上的数据不在使用时，应该有且只释放一次！

• 垃圾回收器的优缺点：

• main.c 代码：

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

#include "Vector.h" //""：搜索路径：当前目录 -> 系统的头文件包含的目录下
#include <stdio.h>  //<>：搜索路径：系统的头文件包含目录下
#include <stdlib.h>

int main(void)
{
    //创建空的动态数组
    Vector* v = vector_create();

    for(int i=0; i<200; i++)
    {
        push_back(v,i);
    }
    printf("push_finish\n");
    vector_destroy(v);
    printf("destroy_finish\n");
    system("pause"); // 防止运行后自动退出，需头文件stdlib.h
    return 0;
}

• Vector.h 代码：

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

//头文件：类型的定义和API声明
#include <stddef.h>
#include <stdlib.h>

typedef int E;

typedef struct
{
    E* elements;
    int capacity;
    int size;
}Vector;

//函数声明
//构造函数
Vector* vector_create(void);

//析构函数
Vector* vector_destroy(Vector* v);

void push_back(Vector* v,E val);

• Vector.c 代码：

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

#include "Vector.h"//""：搜索路径：当前目录 -> 系统的头文件包含的目录下

#define DEFAULT_CAPACITY 8
#define PREALLOC_MAX 1024 //提前申请的最大值

//构造函数（创建空的动态数组）
Vector* vector_create(void)
{
    Vector* v = malloc(sizeof(Vector));
    if(v==NULL)
    {
        printf("Error: malloc failed in vector_create!");
        exit(1);
    }
    E* p = malloc(DEFAULT_CAPACITY * sizeof(E));
    if(p == NULL)
    {
        free(v);//要将之前创建的v释放掉
        printf("Error: malloc failed in vector_create!");
        exit(1);
    }
    //设置基本参数
    v->elements = p;
    v->capacity = DEFAULT_CAPACITY;
    v->size = 0;

    return v;
}

//析构函数（释放动态数组）
Vector* vector_destroy(Vector* v)
{
    //从内到外释放（按照申请的相反顺序释放）
    free(v->elements);
    free(v);
}

void grow_capacity(Vector* v)
{
    int new_capacity = v->capacity < PREALLOC_MAX ?
        v->capacity * 2 : v->capacity+PREALLOC_MAX;
    
    //下面代码有问题，realloc失败会返回NULL，原来的内存空间不会被释放，造成内存泄漏
    //v->elements = realloc(v->elements,new_capacity * sizeof(E));
    
    //正确代码写法
    E* p = realloc(v->elements,new_capacity * sizeof(E));
    if(p == NULL)
    {
        printf("Error: realloc failed in grow_capacity!");
        exit(1);
    }

    v->elements = p;
    v->capacity = new_capacity;
}

void push_back(Vector* v,E val)
{
    //判断是否需要扩容
    if(v->size == v->capacity)
    {
        grow_capacity(v);
    }
    //添加元素val
    v->elements[v->size++] = val;
}

二级指针

• 二级指针，即指向指针的指针。

• C 语言函数是的参数传递属于传值，因此下面例子中只是把指针 head 的值传入了 addNode() 函数的栈帧中，并没有实质性地修改指针 head 的指向。

• 传二级指针即可解决上述问题：

• 总结：怎么确定传一级指针还是二级指针？
  • 想要修改哪个变量，就传那个变量的地址；
  • 想修改指针指向的对象，传一级指针；
  • 想修改指针的值（指向），传二级指针。

函数指针

• 函数指针，即指向函数的指针，它保存了函数的地址，可以通过它调用指向的函数。

• 函数指针的语法和调用：

• 函数指针的作用：
  • 函数式编程（传递函数，返回函数），通过函数指针支持函数式编程。
    • 分解任务，解耦合。
  • 编写非常通用的函数（功能非常强大的函数）。
• qsort() 函数示例：

• qsort() 函数利用函数指针（钩子函数）分解任务，解耦合：

数据结构

链表

单向链表

• 增：在某个结点后面添加结点。

• 删：在某个结点后面删除。

• 查：
  • 根据索引查找结点；
  • 查找与特定值相等的结点。

• 遍历：正向遍历。

双向链表

• 双向链表的模型：

• 基本操作：
  • 增：能够在某个结点的前后添加；
  • 删：删除当前结点；
  • 查：
    • 根据索引查找值：
      • 单链表：$O(n)$，平均遍历 $\frac{n}{2}$；
      • 双链表：$O(n)$，平均遍历 $\frac{n}{4}$；
    • 查找与特定值相等的结点：
      • 无序：$O(n)$；
      • 有序：双链表比单链表效果更好（在多次查找的时候，通过记录上一次查找的结点来优化）；
    • 查找前驱结点：$O(n)$；
  • 遍历：
    • 正向；
    • 逆向。
• 空间和时间：
  • 空间换时间：缓存、缓冲；
  • 时间换空间：压缩、交换区（ swap area ）；