C-Week6

我们现在继续翁恺的 C 语言教程：C 语言程序设计_中国大学 MOOC (慕课)

Lesson21 字符串

字符串在 Lesson20 指针中已有讲解。对于已有的知识点，我们略讲，只详细讲解没有提到过的知识点。

21.1 字符串介绍

字符串本质就是字符数组，只不过字符串的末尾必须有 \0'(或 0) 字符，表示字符串的结束。这个结束字符不属于字符串的内容，不会计入字符串长度（不是数组长度），也不会输出。

字符串可以用数组或者指针来访问，一般我们使用指针访问字符串。

除了用字符数组定义字符串以外，我们还可以用指针来定义字符串，比如：

1	char* str = "Hello";

我们可以参考遍历数组的方法来遍历字符串。

运算符对字符串是无效的。如果你想要对字符串进行增删查改，标准库 <string.h> 提供了一系列操作函数。

21.2 字符串常量

结合 Lesson20 4.2&10 食用

字符串常量被保存在只读的常量区。我们可以通过指针来访问字符串常量，但不能使用指针来修改它。如果你需要修改字符串，请使用字符数组。

总的而言，如果要构造一个字符串，可以用指针；如果要处理一个字符串，请用数组。

21.3 字符串的输入输出

字符串赋值时，如果是使用指针，那么实际上仍指向同一个字符串。比如：

1 2	char* s = "Hello"; char* t = s;

这个过程没有产生新的字符串，s 和 t 本质是相同的，对 s 所作的任何修改也会反映到 t 上。

scanf() 和 ptintf() 有特殊的格式字符 %s 可以用于字符串的输入输出。我们在这里着重讲一下 scanf()，printf() 参见 Lesson20 4.1.4。

scanf() 读取字符串时，是以空格、回车或者 Tab 为标志的。也就是说，像下面的语句：

1
2
3

char t[8];
scanf("%s", t);//为什么我们不用'&'了？请参考Lesson20 2.2
printf("%s", t);

输入：

1	Hello World

输出的是：

Hello

后面的 World 被无情地抛弃了。

所以我们称 scanf() 函数是 “不安全” 的，因为它没有强制要求检查。

在使用 Clang 编译时，你会收到这样一条 Warning：
1
warning: 'scanf' is deprecated(废弃的): This function or variable may be unsafe.
如果使用 MSVS 生成，这个 Warning 的性质会变成 Error！

在有些时候，这种不检查可能导致可怕的后果。例如，我输入一个长度超过数组大小的字符串：

damedame

我使用 VS2022 编译运行时，IDE 提示：

1	0x00007FF70C82149D 处有未经处理的异常(在 string.exe 中): 堆栈 Cookie 检测代码检测到基于堆栈的缓冲区溢出。

虽然程序也输出了东西，但……

damedame
damedame
E:\Learning\x64\Debug\string.exe (进程 36172)已退出，代码为 -1073740791 (0xc0000409)。
    //这退出代码不对劲啊！

Info

C 语言自身其实并没有限制下标的范围，而是直接根据数组的基地址计算对应下标的元素的基地址。(1. 栈上数组越界 & 栈溢出 - Hello CTF)

我们还有一个程序：

#include <stdio.h>

int main(void)
{
	char word[8];
	char word2[8];
	scanf("%s", t);
	scanf("%s", s);
	printf("%s##%s##", t, s);
}

输入：

1 2	12345678 12345678

输出：

1	##12345678##

等一下！谁把我的 t 给吞了？！那我缺的数据这一块谁给我补啊？

这里贴一张讨论区的解释图：

（来源：C 语言程序设计_中国大学 MOOC (慕课)，作者 @大柳树下）

即使是这张解释图，它本身也有需要解释的东西：

为什么 word 在高地址，word2 在低地址？

有些对 “栈” 这个概念一知半解的人会觉得，这数据不是后进先出吗？那这个 word2 不是应该堆在 word 上面、在高地址吗？首先，栈对于数据出入的规定是 “只允许在固定的一端进行插入和删除元素的操作”（栈（Stack）的实现 | CSDN 博客），但 “固定的一端” 一定得在高地址吗？在 Lesson20 4.2 中，我们给的参考图已经说明 “栈区内存向下（低地址）增长”，因此栈区内存是在低地址的一端进行插入和删除元素的操作。所以 word 先进，在较高的地址；word2 后进，在较低的地址。

那么数组呢？按后进先出原则，word[0] 不是应该在高地址？

后面一个问题是伪命题。数组和栈是两种不同的数据结构体系，数组遵循自己的内存分布方式（元素地址不断往高地址增加，具体见 Lesson20 2.4）。因此 word[0] 在低地址。

在计算机安全中，这被称为 “栈溢出 (Stack Overflow)”，溢出的数据将之前写入的数据给覆盖了。在实践中，攻击者可以通过分析目标函数的地址，输入足够数量的任意字符，让程序执行目标函数（即使正常流程下根本无法执行该函数），从而达到控制 / 破坏目的。

参考：栈溢出原理 - CTF Wiki；1. 栈上数组越界 & 栈溢出 - Hello CTF；栈溢出（一）：栈溢出原理以及基本 ROP

当然，scanf() 也有字符串长度检查，但只是可选的。比如：

1	scanf("%7s", s);//这里规定了字符串长度的上限是7

输入：

damedame

输出：

damedam

需要注意的是，如果下行有其他的字符串输入语句，剩下来的字符不会被丢弃，而是顺延到下一个输入语句（涉及缓冲区概念）。比如：

char t[8];
char s[8];
scanf("%7s", t);
scanf("%7s", s);
printf("%s#%s", t, s);

本来我要输入：

1 2	damedame dameyo

但是我只输入了 damedame，程序就输出了：

damedam#e

在进行字符串输入时，我们要保证输入的安全性。比如，接下来的程序就是一个反例：

1 2	char* string; scanf("%s", string);

我们没有对 string 进行初始化，因此这个指针是一个野指针。它指向的内存位置可能合法也可能不合法，所以程序可能正常也可能不正常 (doge

有时候我们只是想定义一个空的字符串，内容之后写入。此时要么指定字符串长度上限，即：

1	char str[100] = "";//此时str[0] == '\0'

要么用变长数组或者 malloc()。

但不要这么写：

1	char str[] = ""

编译器会认为该字符串的长度上限是 1。就这个 1 还被'\0' 占了，又用的是静态内存分配，结果就是你再也无法对这个字符串写入任何字符。

21.4 字符串数组

本节内容也可见于 Lesson20 4.1.2 & 5.4

字符串数组的定义：

1	char variable_name[r][m] = {list of string};

r 是字符串数组中可以存储的字符串值的最大数量。（可放空）
m 是每个字符串数组中可以存储的最大字符值数。（必填）

例如：

char month[][15] = {
    "January",
    "February",
    "March",
    "April",
    "May",
    "June",
    "July",
    "August",
    "Septemper",
    "October",
    "November",
    "December"
}

字符串数组和指向字符串的指针数组的区别：

21.5 程序参数

在有些教程中，main 函数的参数表既不是放空，也不写 void，而是写 int argc, const char* argv[]。这又是什么？

argc 和 argv 只是习惯写法，你大可以用 a 和 b 来替代它们。

参考 Microsoft 的文章：main function and command-line arguments (C++) | Microsoft Learn，我们对 argc 和 argv 分别定义如下：

argc：一个整数，它的值等于命令行参数的个数，始终大于等于 1。
argvorARV：一个字符串数组，表示运行程序时用户输入的命令行参数。按照约定，argv[0] 是用来调用程序的命令。argv[1] 是其后第一个命令行参数。命令行中的最后一个参数是 argv[argc - 1]，argv[argc] 始终为 NULL。

对于以下程序：

#include <stdio.h>

int main(int argc, const char *argv[])
{
	for (int i = 0; i < a; i++)
	{
		printf("%d:%s\n", i, argv[i]);
	}
}

我们有以下输出：

（系统信息：Kali GNU/Linux kali-rolling 2024.3 x86_64 (in WSL2)）

在 Main function - cppreference.com 中，还提到一种常见的非标准的 main 函数参数表：int argc, char* argv[], char* envp[]。envp 是一个 char** 类型的数组，指向一个指向执行环境变量的指针数组。

好，我们认识了程序参数，但它到底有什么用？原样输出？太 Low 了吧！

在 UNIX 系统中，我们可以为程序添加符号链接（软链接）。这就像在 Windows 中创建快捷方式一样。

我们可以使用 ln(link) 命令为程序创建符号链接：

1	$ ln -s a.out hi

注意这个 $ 只是一个提示符，用来突出用户输入的，复制命令的时候不要把提示符一起复制了

之后使用 ls(list) 命令可以看到：

1 2	$ ls a.out hi ...

如果想要查看文件名对应的链接关系，可以使用 -l 选项：

1 2	$ ls -l hi lrwxrwxrwx 1 watermelonabc watermelonabc 5 10月20日 10:00 hi -> a.out

我们可以看到 hi 有一个指向 a.out 的箭头，代表符号链接。

这时我们使用 hi 来运行程序，会出现：

通过参数，程序得以知道它是以何种方式被调用的，然后我们可以借此实现一些操作。（你可能更熟悉另一个名词 “命令行参数”）

这里介绍一下 UNIX 系统上的 BusyBox。BusyBox 是一个开源项目，提供了大约 400 个常见 UNIX/Linux 命令的精简实现。它将众多的 UNIX 命令集合进一个很小的可执行程序中，因此，它宣称自己是 “The Swiss Army Knife of Embedded Linux”(BusyBox)。

我们不可能只运行 BusyBox 这一个程序，必须指定一个命令。这个命令就是 BusyBox 的一个程序参数。

就拿瑞士军刀做个类比。瑞士军刀拿出来肯定是需要用其中具体的一项功能的，难不成你只是拿出来装个样子，或者领域展开，所有刀片全部展出？至少正经用的时候你肯定是什么用途就开什么刀片。

1
2
3

$ busybox ls
Desktop     Downloads   Pictures    Templates   a.out       hi
Documents   Music       Public      Videos      hello.c     install.sh

Note

当然，有很多开发者专门对未输入参数的情况做了适配。一般是输出程序本体的信息和用法。比如：

>$ busybox
>BusyBox v1.37.0 (Debian 1:1.37.0-4) multi-call binary.
>BusyBox is copyrighted by many authors between 1998-2015.
>Licensed under GPLv2. See source distribution for detailed
>copyright notices.

>Usage: busybox [function [arguments]...]
  or: busybox --list[-full]
  or: busybox --install [-s] [DIR]
  or: function [arguments]...

       BusyBox is a multi-call binary that combines many common Unix
       utilities into a single executable.  Most people will create a
       link to busybox for each function they wish to use and BusyBox
       will act like whatever it was invoked as.

>Currently defined functions:
       # 此处省略一连串函数名

21.6 字符串函数

本节参考 C 标准库 – <string.h>| 菜鸟教程

21.6.1 `putchar()` 和 `getchar()`

这两个函数的声明在 <stdio.h> 头文件中。

putchar() 可以将参数 char 指定的字符（一个无符号字符）写入到标准输出 stdout 中（即原样输出）。

标准输出是指将程序的输出结果显示到屏幕或其他设备上的过程，可以理解为我们运行程序时出现的小黑框。

它的声明：

1	int putchar(int char)

char – 这是要被写入的字符。该字符以其对应的 int 值进行传递。

该函数以无符号 char 强制转换为 int 的形式返回写入的字符，如果发生错误则返回 EOF(End Of File，类型为 int 且为负值的整型常量)。我们不需要检查 putchar() 正常时的输出，但可以检查 putchar() 不正常时的输出。

函数将 unsigned char 转换成 int 就是为了输出这个 EOF。

getchar() 从标准输入 stdin 获取一个字符（一个无符号字符）。

标准输入是指进程从其他设备得到输入数据的过程，通常对应终端的键盘。

它的声明：

1	int getchar(void)

该函数以无符号 char 强制转换为 int 的形式返回读取的字符，如果到达文件末尾或发生读错误，则返回 EOF。

如果需要结束 getchar() 读取，请输入 Ctrl+D (Unix) / Ctrl+Z (Windows)。

#include <stdio.h>

int main(int a, const char *b[])
{
	char ch;
	while ((ch = getchar()) != EOF)
	{
		putchar(ch);
	}
	printf("EOF\n");
}

Note

这个程序实现了字符串的输入输出。但 ch 是一个字符，按理来说只能读取一个字符，字符串它是吃不消的。为什么程序没有拒绝我们输入输出一个字符串呢？

在计算机中，输入输出设备和程序之间还隔着一层 SHELL，我们的输入要由 SHELL 交给程序。在一行内输入数据，如果没有换行，那么输入的数据不会提交给程序，而是暂存在 SHELL 里。按下回车后，数据将进入缓冲区，以供程序读取。如何读取这些数据由相应的函数决定。

因此我们输入的字符串是被拆成一个一个字符传递给函数的。

在缓冲区的结尾有一个标记，表示 “等待输入”。输入函数读取到这个标记，就会等待用户继续输入数据。此时，输入 Ctrl+D (UNIX) 或 Ctrl+Z (Windows) ，SHELL 会在缓冲区结尾写入一个代表输入结束的记号，输入函数读取到这个记号就不会要求用户输入了。

这涉及到 UNIX 下的 Canonical Mode（规范模式）。在规范模式下，一行内的输入会被缓存，并且可以编辑修改，直到按下回车键进行提交，系统就将当前缓冲区的内容发送到程序。

21.6.2~21.6.5

这四节分别介绍了 strlen、strcmp、strcpy 和 strcat。

请参照 Lesson20 4.4 常见的字符串操作和标准库规定。

21.6.6 `strchr()` 和 `strrchr()`

strchr() 用于查找字符串中的一个字符，并返回该字符在字符串中第一次出现的位置。

它的声明为：

1	char strchr(const char str, int c)

str – 要查找的字符串。
c – 要查找的字符，通常以整数形式传递（ASCII 值），但是最终会转换回 char 形式。

该函数从字符串的开头开始向后搜索，直到找到指定的字符或搜索完整个字符串。如果在字符串 str 中找到字符 c，则函数返回指向该字符的指针，如果未找到该字符则返回 NULL。由于返回的这个指针指向字符串中的字符，如果要将该指针用作字符串，应该将其传递给其他字符串处理函数，例如 printf() 或 strncpy()。

示例：

#include <stdio.h>
#include <string.h>

int main(void){
    char arr[] = "Hello";
    char* p = strchr(arr, 'l');
    printf("The location of the first 'l' in 'arr' is %d", p - arr + 1);
    //这里输出的是'l'在数组arr中的相对位置；
    //直接输出指针p的值，等于输出'l'在内存中的绝对位置
}

1	The location of the first 'l' in 'arr' is 3

strrchr() 用于查找字符串中的一个字符，并返回该字符在字符串中最后一次出现的位置。

它的声明为：

1	char strrchr(const char str, int c)

str – 要查找的字符串。
c – 要查找的字符，通常以整数形式传递（ASCII 值），但是最终会转换回 char 形式。

该函数从字符串的末尾开始向前搜索，直到找到指定的字符或搜索完整个字符串。如果找到字符，它将返回一个指向该字符的指针，否则返回 NULL。

示例：

#include <stdio.h>
#include <string.h>

int main(void){
    char arr[] = "Hello";
    char* p = strrchr(arr, 'l');
    printf("The location of the last 'l' in 'arr' is %d", p - arr + 1);
}

1	The location of the last 'l' in 'arr' is 4

如果一个字符串有好几个相同的目标字符，我们怎么让程序查找中间的那些字符呢？

#include <stdio.h>
#include <string.h>

int main(void){
    char furry[] = "furryfurryfur";
    char* fur = strchr(furry, 'f');
    fur = str(fur + 1, 'f');
    printf("The location of the second 'f' in 'furry' is %d\n", fur - furry + 1);
}

1	The location of the second 'f' in 'arr' is 6

基本的思路是：先查出原字符串中的第一个 f，然后在这个 f 之后的字符串（也就是 urryfurryfur）中查找第一个 f，循环往复，一直到字符串结束。

有时我们想截取一个字符串中以某一个字符为断点的前半或者后半部分，用 strchr 怎么做？

截取后半部分：

#include <stdio.h>
#include <string.h>

int main(void){
    char data[] = "furry";
    char* p = strchr(data, 'r');
    char* t = (char*)malloc(strlen(p) + 1);
    strcpy(t, p);
    printf("%s", t);
    free(t);
}

截取前半部分：

#include <stdio.h>
#include <string.h>

int main(void){
    char data[] = "furry";
    char* p = strchr(data, 'r');
    *p = '\0';// f u \0 r y
    char* t = (char*)malloc(strlen(s) + 1);
    strcpy(t, s);//只复制了'\0'之前的字符，即fu
    *p = 'c';
    printf("%s", t);
    free(t);
}

21.6.7 `strstr()` 和 `strcasestr()`

strstr() 在字符串 haystack 中查找第一次出现字符串 needle 的位置，不包含终止符 '\0'。

它的声明为：

1	char strstr(const char haystack, const char *needle)

haystack – 被检索的字符串。
needle – 在 haystack 字符串内要搜索的小字符串。

该函数返回在 haystack 中第一次出现 needle 字符串的位置（指针形式），如果未找到则返回 null。

示例：

#include <stdio.h>
#include <string.h>


int main()
{
   const char haystack[20] = "RUNOOB";
   const char needle[10] = "NOOB";
   char *ret;

   ret = strstr(haystack, needle);

   printf("子字符串是： %s\n", ret);

   return(0);
}

1	子字符串是： NOOB

strcasestr() 的作用和 strstr() 一致，但前者不区分大小写。

Warning

strcasestr() 不是标准中定义的函数，而是 GCC 提供的扩展函数。注意编译器兼容性。

strcasestr() 的声明：

1	char strcasestr(const char haystack, const char *needle);

haystack – 被检索的字符串。
needle – 在 haystack 字符串内要搜索的小字符串。

示例：

#define _GNU_SOURCE             // 宏定义应当有，否则编译会有Warning警告信息
#include <stdio.h>
#include <string.h>
int main(int argc, char *argv[])
{
    char *res = strstr("xxxhost: www.baidu.com", "Host");
    if(res == NULL) printf("res1 is NULL!\n");
    else printf("%s\n", res);     // print:-->'host: www.baidu.com'
    return 0;
}

21.6.8 `gets()` 和 `fgets()`

这两个函数在 <stdio.h> 头文件中声明

gets() 函数用以输入整个字符串。该函数从标准输入 stdin 读取一行，并把它存储在 str 所指向的字符串中。当读取到换行符 (\n) 时，或者到达文件末尾时，它会停止，具体视情况而定。停止后换行符被丢弃，同时在字符数组中读取的最后一个字符之后立即写入一个空字符。

它的声明：

1	char gets(char str)

str – 这是指向一个字符数组的指针，该数组存储了字符串。

如果成功，该函数返回 str。如果发生错误或者到达文件末尾时还未读取任何字符，则返回 NULL。

示例：

#include <stdio.h>

int main()
{
   char str[50];

   printf("请输入一个字符串：");
   gets(str);

   printf("您输入的字符串是：%s", str);

   return(0);
}

由于安全性问题，gets() 函数已经被 C11 完全废弃。C11 标准推荐使用 fgets() 作为替代。

fgets() 和 gets() 一样，最后的回车都会从缓冲区中取出来。只不过 gets() 是取出来丢掉，而 fgets() 是取出来自己留着。但总之缓冲区中是没有回车了。

Warning

gets() 函数不执行边界检查，因此极易受到缓冲区溢出攻击。鉴于此，该函数已经在 C99 标准的第三次修订中被弃用，并且在 C11 标准中完全移除。fgets() 和 gets_s() 是推荐的替代函数。

请不要使用 gets()！

——gets, gets_s - cppreference.com

fgets() 从给定的文件流（默认为标准输入 stdin ）中最多读取 count - 1 个字符，并将它们存储在由 str 指向的字符数组中。如果找到换行符（在这种情况下，str 将包含该换行符）或遇到文件末尾，则解析停止。如果读取了字节且没有发生错误，则在 str 中最后一个字符之后的位置写入一个空字符。

fgets() 的声明如下：

1	char* fgets( char* restrict str, int count, FILE* restrict stream );

str – 这是要被写入的 C 字符串。
count – 读取字符数量的上限（一般为 str 的长度）
stream – 要读取数据的文件流。如果是标准输入，输入 stdin

如果成功，返回 str。如果发生错误，返回 NULL。

fget() 函数中的 count 如果小于字符串的长度，那么字符串将会被截取；如果大于字符串的长度，则多余的部分系统会自动用 '\0' 填充。但是需要注意的是，如果输入的字符串长度没有超过 count–1，那么系统会将最后输入的换行符 '\n' 保存进来，保存的位置是紧跟输入的字符，然后剩余的空间都用 '\0' 填充。所以此时输出该字符串时 printf 中就不需要加换行符 '\n' 了，因为字符串中已经有了。

示例：

# include <stdio.h>
int main(void)
{
    char str[30];
    printf("请输入字符串：");
    fgets(str, 30, stdin);
    printf("%s", str);  //printf中不需要添加'\n', 因为字符串中已经有了
    return 0;
}

21.6.9 `puts()` 和 `fputs()`

这两个函数均在 <stdio.h> 中声明。

puts() 把一个字符串写入到标准输出 stdout，直到空字符，但不包括空字符。换行符会被追加到输出中。

它的声明：

1	int puts(const char *str)

str – 这是要被写入的 C 字符串。

如果成功，该函数返回一个非负值，如果发生错误则返回 EOF。

Tip

不同的实现返回不同的非负数：有些返回最后一个写入的字符，有些返回写入的字符数（如果字符串长度比 int 更大，则返回宏 INT_MAX 的值），有些简单地返回一个非负常数。

——puts - cppreference.com

示例：

#include <stdio.h>
#include <string.h>

int main()
{
   char str1[15];
   char str2[15];

   strcpy(str1, "RUNOOB1");
   strcpy(str2, "RUNOOB2");

   puts(str1);
   puts(str2);

   return(0);
}

1
2
3

RUNOOB1
RUNOOB2

如果不希望在输出后自动添加换行符，可以使用 fputs()。

这是 fputs() 的声明：

1	int fputs( const char* restrict str, FILE* restrict stream );

str – 这是一个数组，包含了要写入的以空字符终止的字符序列。
stream – 输出流。如果使用标准输出，输入 stdout

该函数返回一个非负值，如果发生错误则返回 EOF。

Tip

和 puts() 相同，不同的实现返回不同的非负数：有些返回最后一个写入的字符，有些返回写入的字符数（如果字符串长度比 int 更大，则返回宏 INT_MAX 的值），有些简单地返回一个非负常数。

——fputs - cppreference.com

示例：

#include <stdio.h>

int main(void)
{
    int rc = fputs("Hello World", stdout);

    if (rc == EOF)
       perror("fputs()"); // POSIX requires that errno is set
}

1	Hello World

Lesson22 枚举类型

22.1 常量的符号化

当我们的程序中需要一些常量时，一个好的编程习惯是使用 const、#define 等将常量符号化而不是写硬编码。这样的好处是易读性良好，读者可以通过常量名称知道这些常量的用途。

22.2 枚举类型

参考：C enum (枚举) | 菜鸟教程

有时，一些常量具有共同性，比如 Red、Yellow、Blue、Green 和 Orange 都属于 Color，这时我们可以将这 5 个颜色变量打包在一起，叫做 Color。我们定义的这个 Color 就是一个枚举。这可比写 5 个 const int 要来得简单！

从数据角度，枚举 (Enumeration) 指用户定义的一种数据类型。它使用 **enum** 关键字，以如下语句定义：

1	enum flag{constant1, constant2, constant3, ....... };

我们通常不用大括号外面的 flag，要用的是大括号里面的常量名。

我们可以为枚举元素指定一个整数值，没有指定值的枚举元素，其值为前一元素加 1。第一个枚举成员的默认值为整型的 0，后续枚举成员的值在前一个成员上加 1。

enum DAY
{
      MON, TUE, WED, THU, FRI, SAT, SUN
};
//MON = 0; TUE = 1; WED = 2; THU = 3; FRI = 4; SAT = 5; SUN = 6

1 2	enum season {spring, summer=3, autumn, winter}; //spring = 1; summer = 3; autumn = 4; winter = 5

作为一个数据类型，枚举可以用于变量定义。这里有三种定义方式：

enum DAY
{
      MON=1, TUE, WED, THU, FRI, SAT, SUN
};
enum DAY day;

enum DAY
{
      MON=1, TUE, WED, THU, FRI, SAT, SUN
} day;

enum
{
      MON=1, TUE, WED, THU, FRI, SAT, SUN
} day;

不论哪种方式，都需要带上关键字 enum

不过在 C 语言中，枚举类型是被当做 int 或者 unsigned int 类型来处理的，因此我们也可以用整数的方式来处理枚举变量：

#include <stdio.h>

enum DAY
{
      MON=1, TUE, WED, THU, FRI, SAT, SUN
};
int main(void){
	enum DAY p = TUE;
    scanf("%d", &p);
    printf("%d\n", p);
}

1
2

>>12
12

目前大部分的 C 语言编译器都允许给一个枚举类型的变量赋一个不存在于枚举类型的值（比如上面我们给枚举类型变量 x 赋值 12，编译器没有输出任何信息）。

Tip

其实，在实践中，我们一般不用枚举类型定义变量，虽然它能用，但不好用。

我们经常在定义一组相关的、具有离散值的常量时使用枚举，以便于程序的可读性和维护性。

按照 C 语言标准，我们无法遍历枚举类型。不过在一些特殊的情况下，枚举类型可以实现遍历，前提是枚举类型的值是连续的。

//连续的枚举类型
enum DAY
{
      MON=1, TUE, WED, THU, FRI, SAT, SUN
};
//不连续的枚举类型
enum
{
    ENUM_0,
    ENUM_10 = 10,
    ENUM_11
};

下面介绍几个遍历枚举类型的例子：

#include <stdio.h>

enum Color {red, yellow, blue, green, orange, NumColors};

int main(void){
    int color = -1;
    char* ColorName[NumColors] = {
        "red",
        "yellow",
        "blue",
        "green",
        "orange"
    };
    char* colorName = NULL;
    printf("Enter a code of your favorite color:")
    scanf("%d", &color);
    if (color >= 0 && color <= NumColors);
    {
        colorName = ColorName[color];
    }
    else
    {
        colorName = "unknown";
    }
    printf("Your favorite color is %s\n", colorName);
}
<!--code66-->

#include <stdio.h>
#include <stdlib.h>
int main()
{

    enum color { red=1, green, blue };

    enum  color favorite_color;

    /* 用户输入数字来选择颜色 */
    printf("请输入你喜欢的颜色: (1. red, 2. green, 3. blue): ");
    scanf("%u", &favorite_color);

    /* 输出结果 */
    switch (favorite_color)
    {
    case red:
        printf("你喜欢的颜色是红色");
        break;
    case green:
        printf("你喜欢的颜色是绿色");
        break;
    case blue:
        printf("你喜欢的颜色是蓝色");
        break;
    default:
        printf("你没有选择你喜欢的颜色");
    }

    return 0;
}
<!--code67-->

Note

一个递归实现会包含以下两部分：

基本情况 , 即问题中最小、最简单且无法再度细分的情况。基本情况经常和 “空” 有关，比如空字符串、空列表、空集合、空树、零，等等。
递归步骤 , 即将问题的较大情况细分为更简单或更小的、可以被递归调用解决的情况，然后将这些子问题的结果重新组合已得到原问题的答案的方法。

细分问题非常重要，否则递归可能会一直进行下去。如果每个递归步骤都能细分问题，并且基本情况是最小、最基本的，那么递归就是收敛的。

有的递归实现会有不止一个基本情况，不止一步递归步骤。例如，斐波那契数列就有两种基本情况，n=0 和 n=1.

——Reading 10: Recursion

Warning

还记得本节开头引用的例子吗？如果内容不变，这个故事会不停地递归下去！因此请为你的递归设置终止条件，不要让它变成无限递归 (Infinite Recursion)，因为递归到一定次数计算机就难以处理这个庞大的递归了。

迭代 / 循环实现中的无限循环通常会变成递归实现中的栈溢出错误。

——Reading 10: Recursion

23.2 用递归解决递推问题

8.4 的阶乘函数可以用递归来做。

我们对 $f(n)=n!$ 定义如下：

$\begin{cases}f(0)=1\\ f(n)=f(n-1)\cdot n(n\geq1)\end{cases}$

这就将一连串乘法分解成一个个小的乘法了。

int f(int n){
    if (n == 0){
        return 1;
    }
    else{
        return f(n - 1) * n;
    }
}

如果要计算 $f(3)$ ，这个递归函数要如何工作？

下图展示了该递归的工作方式。随着时间推移，函数从左到右工作：

（来源：Reading 10: Recursion）

也可以看看这张图：

（来源：How Recursion works in C - Stack Overflow）

如你需要可视化，可以在 Python Tutor code visualizer: Visualize code in Python, JavaScript, C, C++, and Java 复现代码并使用可以交互的可视化程序运行过程展示。

我们在此处直接提供可视化：

在以上展示中，我们可以看到栈是如何增长的。当 main 调用 f 以及 f 调用自身时，程序都会多一个调用栈 (Call Stack)，直到 f(0) 符合终止条件，结束递归调用。然后调用栈回滚，每次对 f 的调用都将其返回值返回给调用者，直到 f(3) 返回到 main，输出结果。

函数整体分配的内存空间叫作调用栈，调用栈由栈帧 (Stack Frame) 构成，每个栈帧存储与函数执行有关的信息。

递归函数每次调用自身时，系统都会为新开启的函数分配内存，以存储局部变量、调用地址和其他信息等。这些内存直至函数返回后才会被释放，因此会产生大量的内存开销。

15.3 的正序输出数字也可以用递归来解决

void print_number (int n)
{
    int x = n / 10;
    if (x != 0)
    {
        print_number(x);
    }
    printf("%d\n", n % 10);
}

可视化：

递归也可以用于解决斐波那契数列：

int fibonacci(int n) {
    if (n == 0 || n == 1) {
        return 1; // base cases
    }
    else {
        return fibonacci(n-1) + fibonacci(n-2); // recursive step
    }
}

我们使用递归树来描述这个递归算法：

（来源：2.2 迭代与递归 - Hello 算法）

也直接提供可视化：

我们看到，如果递归函数有多个最简子问题的答案，那么它的调用将会更加难以理解。不理解也没有关系，知道递归为什么能正常工作即可。

Tip

明白一个函数的作用并相信它能完成这个任务，千万不要跳进这个函数里面企图探究更多细节，否则就会陷入无穷的细节无法自拔。如果实在不相信，可以用归纳法来证明它的正确性。比如下面的汉诺塔问题，一口气十几个栈，连生成可视化的程序都难以招架。

—— 递归 & 分治 - OI Wiki

Warning

设计递归算法时常犯两种错误：

基本情况有缺漏，没有覆盖到全部最简子问题
递归步骤不能化简为更小的子问题，因此递归不会收敛，即不存在最简子问题。

——Reading 10: Recursion

23.3 尾递归

如果函数在返回前的最后一步才进行递归调用，则该函数可以被（受支持的）编译器或解释器优化。这种情况被称为尾递归（tail recursion）。

普通递归和尾递归的区别：

普通递归：当函数返回到上一层级的函数后，需要继续执行代码，因此系统需要保存上一层调用的上下文。

尾递归：递归调用是函数返回前的最后一个操作，这意味着函数返回到上一层级后，无须继续执行其他操作，因此系统无须保存上一层函数的上下文。

以计算 $1+2+⋯+n$ 为例，我们可以将结果变量 res 设为函数参数，从而实现尾递归：

/* 尾递归 */
int tailRecur(int n, int res) {
    // 终止条件
    if (n == 0)
        return res;
    // 尾递归调用
    return tailRecur(n - 1, res + n);
    /*
}

在尾递归中，求和操作是在 “递” 的过程中执行的，“归” 的过程只需层层返回。

（来源：2.2 迭代与递归 - Hello 算法）

可视化：

Warning

使用尾递归时，递归返回后不能进行任何操作。比如这个函数：

int g(int x) {
  if (x == 1) {
    return 1;
  }
  int y = g(x-1);
  return x*y;
}

——algorithms - What is tail recursion? - Computer Science Stack Exchange

23.4 分治思想

分治（Divide and Conquer），字面上的解释是 “分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

过程

分治算法的核心思想就是 “分而治之”。

大概的流程可以分为三步：分解 -> 解决 -> 合并

分解原问题为结构相同的子问题。
分解到某个容易求解的边界之后，进行递归求解。
将子问题的解合并成原问题的解。

分治法能解决的问题一般有如下特征：

该问题的规模缩小到一定的程度就可以容易地解决。
该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质，利用该问题分解出的子问题的解可以合并为该问题的解。
该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。

分治就是递归吗

从定义出发，我们会很自然地将分治法和递归联系起来。

但在具体实现中，我们也有使用迭代 (Iterative) 的情况。迭代是一种重复执行某个任务的控制结构。在迭代中，程序会在满足一定的条件下重复执行某段代码，直到这个条件不再满足。我们使用的循环结构 (for 和 while) 就属于迭代。

我们在 8.4 中对阶乘的 for 循环实现就是迭代的样例。

迭代和递归是两种基本的程序控制结构，用于实现执行重复性操作。

迭代和递归在实现、性能和适用性上有所不同：

（来源：2.2 迭代与递归 - Hello 算法）

迭代和递归在很多情况下可以互相转化，比如尾递归本质上就是迭代。但转换不一定值得。有以下两点原因：

转化后的代码可能更加难以理解，可读性更差。
对于某些复杂问题，模拟系统调用栈的行为可能非常困难。

总之，选择迭代还是递归取决于特定问题的性质。在编程实践中，权衡两者的优劣并根据情境选择合适的方法至关重要。

可以看看这篇 StackOverflow 问题：computer science - What is recursion and when should I use it? - Stack Overflow

23.5 汉诺塔问题

12.4 汉诺塔问题 - Hello 算法，可以配合【递归 2】如何治疗晕递归？- 哔哩哔哩 - bilibili 食用。

问题描述：给定三根柱子，记为 A、B 和 C 。起始状态下，柱子 A 上套着 n 个圆盘，它们从上到下按照从小到大的顺序排列。我们的任务是要把这 n 个圆盘移到柱子 C 上，并保持它们的原有顺序不变（如下图所示）。在移动圆盘的过程中，需要遵守以下规则：
1. 圆盘只能从一根柱子顶部拿出，从另一根柱子顶部放入。
2. 每次只能移动一个圆盘。
3. 小圆盘必须时刻位于大圆盘之上。

（来源：12.4 汉诺塔问题 - Hello 算法）

算法分析

我们将规模为 $i$ 的汉诺塔问题记作 $f(i)$ 。例如 $f(3)$ 代表将 3 个圆盘从 A 移动至 C 的汉诺塔问题。
1. 考虑基本情况
  - 对于问题 $f(1)$ ，即当只有一个圆盘时，我们将它直接从 A 移动至 C 即可。
  - 对于问题 $f(2)$ ，即当有两个圆盘时，由于要时刻满足小圆盘在大圆盘之上，因此需要借助 B 来完成移动。
    1. 先将上面的小圆盘从 A 移至 B 。
    2. 再将大圆盘从 A 移至 C 。
    3. 最后将小圆盘从 B 移至 C 。
    解决问题 $f(2)$ 的过程可总结为：将两个圆盘借助 B 从 A 移至 C 。其中，C 称为目标柱、B 称为缓冲柱。
2. 子问题分解
  
  对于问题 $f(3)$ ，即当有三个圆盘时，情况变得稍微复杂了一些。
  
  因为已知 $f(1)$ 和 $f(2)$ 的解，所以我们可从分治角度思考，将 A 顶部的两个圆盘看作一个整体。这样三个圆盘就被顺利地从 A 移至 C 了：
  1. 令 B 为目标柱、C 为缓冲柱，将两个圆盘从 A 移至 B 。
  2. 将 A 中剩余的一个圆盘从 A 直接移动至 C 。
  3. 令 C 为目标柱、A 为缓冲柱，将两个圆盘从 B 移至 C 。
  从本质上看，我们将问题 $f(3)$ 划分为两个子问题 $f(2)$ 和一个子问题 $f(1)$ 。按顺序解决这三个子问题之后，原问题随之得到解决。这说明子问题是独立的，而且解可以合并。
3. 分治策略归纳
  
  至此，我们可总结出解决汉诺塔问题的分治策略：将原问题 $f(n)$ 划分为两个子问题 $f(n−1)$ 和一个子问题 $f(1)$ ，并按照以下顺序解决这三个子问题。
  1. 将 $n−1$ 个圆盘借助 C 从 A 移至 B 。
  2. 将剩余 $1$ 个圆盘从 A 直接移至 C 。
  3. 将 $n−1$ 个圆盘借助 A 从 B 移至 C 。
  对于这两个子问题 $f(n−1)$ ，可以通过相同的方式进行递归划分，直至达到最小子问题 $f(1)$ 。而 $f(1)$ 的解是已知的，只需一次移动操作即可。

（来源：12.4 汉诺塔问题 - Hello 算法）

代码实现（仅算法）

/* 移动一个圆盘 */
void move(int *src, int *srcSize, int *tar, int *tarSize) {
    // 从 src 顶部拿出一个圆盘
    int pan = src[*srcSize - 1];
    src[*srcSize - 1] = 0;
    (*srcSize)--;
    // 将圆盘放入 tar 顶部
    tar[*tarSize] = pan;
    (*tarSize)++;
}

/* 求解汉诺塔问题 f(i) */
void dfs(int i, int *src, int *srcSize, int *buf, int *bufSize, int *tar, int *tarSize) {
    // 若 src 只剩下一个圆盘，则直接将其移到 tar
    if (i == 1) {
        move(src, srcSize, tar, tarSize);
        return;
    }
    // 子问题 f(i-1) ：将 src 顶部 i-1 个圆盘借助 tar 移到 buf
    dfs(i - 1, src, srcSize, tar, tarSize, buf, bufSize);
    // 子问题 f(1) ：将 src 剩余一个圆盘移到 tar
    move(src, srcSize, tar, tarSize);
    // 子问题 f(i-1) ：将 buf 顶部 i-1 个圆盘借助 src 移到 tar
    dfs(i - 1, buf, bufSize, src, srcSize, tar, tarSize);
}

/* 求解汉诺塔问题 */
void solveHanota(int *A, int *ASize, int *B, int *BSize, int *C, int *CSize) {
    // 将 A 顶部 n 个圆盘借助 B 移到 C
    dfs(*ASize, A, ASize, B, BSize, C, CSize);
}

使用的示例程序：

#include <stdio.h>
#include <stdlib.h>

// 移动一个圆盘
void move(int *src, int *srcSize, int *tar, int *tarSize) {
    // 从 src 顶部拿出一个圆盘
    int pan = src[*srcSize - 1];
    src[*srcSize - 1] = 0;
    (*srcSize)--;
    // 将圆盘放入 tar 顶部
    tar[*tarSize] = pan;
    (*tarSize)++;
    printf("Move disk %d from %p to %p\n", pan, (void*)src, (void*)tar);
}

// 求解汉诺塔问题 f(i)
void dfs(int i, int *src, int *srcSize, int *buf, int *bufSize, int *tar, int *tarSize) {
    // 若 src 只剩下一个圆盘，则直接将其移到 tar
    if (i == 1) {
        move(src, srcSize, tar, tarSize);
        return;
    }
    // 子问题 f(i-1) ：将 src 顶部 i-1 个圆盘借助 tar 移到 buf
    dfs(i - 1, src, srcSize, tar, tarSize, buf, bufSize);
    // 子问题 f(1) ：将 src 剩余一个圆盘移到 tar
    move(src, srcSize, tar, tarSize);
    // 子问题 f(i-1) ：将 buf 顶部 i-1 个圆盘借助 src 移到 tar
    dfs(i - 1, buf, bufSize, src, srcSize, tar, tarSize);
}

// 求解汉诺塔问题
void solveHanota(int *A, int *ASize, int *B, int *BSize, int *C, int *CSize) {
    // 将 A 顶部 n 个圆盘借助 B 移到 C
    dfs(*ASize, A, ASize, B, BSize, C, CSize);
}

int main() {
    int n = 3; // 圆盘数量
    int *A = (int *)malloc(n * sizeof(int)); // 源柱子
    int *B = (int *)malloc(n * sizeof(int)); // 辅助柱子
    int *C = (int *)malloc(n * sizeof(int)); // 目标柱子
    int *ASize = (int *)malloc(sizeof(int)); // 源柱子圆盘数量
    int *BSize = (int *)malloc(sizeof(int)); // 辅助柱子圆盘数量
    int *CSize = (int *)malloc(sizeof(int)); // 目标柱子圆盘数量

    // 初始化圆盘
    for (int i = 0; i < n; i++) {
        A[i] = n - i;
    }
    *ASize = n;
    *BSize = 0;
    *CSize = 0;

    printf("Solving Tower of Hanoi with %d disks:\n", n);
    solveHanota(A, ASize, B, BSize, C, CSize);

    free(A);
    free(B);
    free(C);
    free(ASize);
    free(BSize);
    free(CSize);

    return 0;
}

（由 Kimi 生成）

以及其可视化：

23.6 二分查找

10.1 二分查找 - Hello 算法

二分查找（Binary Search，也称为 “折半查找”）是一种基于分治策略的高效搜索算法。它利用数据的有序性，每轮缩小一半搜索范围，直至找到目标元素或搜索区间为空为止。

类比于在纸质词典上查找单词，如果想更快速地找到单词，你肯定不会从 Page 1 开始一页一页地翻，而是翻开中间的某一页。如果刚好目标就在这一页，那么皆大欢喜；如果不在这一页，那么就得按字母往前翻或者往后翻，在这个过程中你可能又会翻开另一页，然后往前 / 往后找。这就是二分查找在生活中的运用。

Harvard CS50 的讲师 David J. Malan 喜欢以 “撕电话簿” 为例解释二分查找。每一学年的课堂，他都会让学生上台用纸质电话簿找人，然后把不需要的部分撕掉！有一年的课堂，他甚至在讲台上放了好几本厚厚的电话簿！

问题描述

给定一个长度为 n 的数组 nums ，元素按从小到大的顺序排列且不重复。请查找并返回元素 target 在该数组中的索引。若数组不包含该元素，则返回 −1 。

（来源：10.1 二分查找 - Hello 算法）
算法分析

我们先初始化指针 $i=0$ 和 $j=n−1$ ，分别指向数组首元素和尾元素，代表搜索区间 $[0,n−1]$ 。请注意，中括号表示闭区间，其包含边界值本身。

接下来，循环执行以下两步：
1. 计算中点索引 $m=⌊\frac{i+j}{2}⌋$ ，其中 $⌊⌋$ 表示向下取整操作。
2. 判断 nums[m] 和 target 的大小关系。分为以下三种情况：
  
  a. 当 nums[m] < target 时，说明 target 在区间 $[m+1,j]$ 中，因此执行 i=m+1 。
  
  b. 当 nums[m] > target 时，说明 target 在区间 $[i,m−1]$ 中，因此执行 j=m−1 。
  
  c. 当 nums[m] = target 时，说明找到 target ，因此返回索引 m 。
若数组不包含目标元素，搜索区间最终会缩小为空。此时返回 −1 。

值得注意的是，由于 i 和 j 都是 int 类型，因此 i+j 可能会超出 int 类型的取值范围。为了避免大数越界，我们通常采用公式 $m=⌊i+\frac{j−i}{2}⌋$ 来计算中点。

除了上述双闭区间外，常见的区间表示还有 “左闭右开” 区间，定义为 $[0,n)$ ，即左边界包含自身，右边界不包含自身。在该表示下，区间 $[i,j)$ 在 $i=j$ 时为空。

由于 “双闭区间” 表示中的左右边界都被定义为闭区间，因此通过指针 i 和指针 j 缩小区间的操作也是对称的。这样更不容易出错，因此一般建议采用 “双闭区间” 的写法。

（来源：10.1 二分查找 - Hello 算法）

代码实现

/* 二分查找（双闭区间） */
int binarySearch(int *nums, int len, int target) {
    // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
    int i = 0, j = len - 1;
    // 循环，当搜索区间为空时跳出（当 i > j 时为空）
    while (i <= j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target)    // 此情况说明 target 在区间 [m+1, j] 中
            i = m + 1;
        else if (nums[m] > target) // 此情况说明 target 在区间 [i, m-1] 中
            j = m - 1;
        else // 找到目标元素，返回其索引
            return m;
    }
    // 未找到目标元素，返回 -1
    return -1;
}

/* 二分查找（左闭右开区间） */
int binarySearchLCRO(int *nums, int len, int target) {
    // 初始化左闭右开区间 [0, n) ，即 i, j 分别指向数组首元素、尾元素+1
    int i = 0, j = len;
    // 循环，当搜索区间为空时跳出（当 i = j 时为空）
    while (i < j) {
        int m = i + (j - i) / 2; // 计算中点索引 m
        if (nums[m] < target)    // 此情况说明 target 在区间 [m+1, j) 中
            i = m + 1;
        else if (nums[m] > target) // 此情况说明 target 在区间 [i, m) 中
            j = m;
        else // 找到目标元素，返回其索引
            return m;
    }
    // 未找到目标元素，返回 -1
    return -1;
}

用递归实现二分查找

尽管可以用递归实现，但一般把二分查找写成非递归的。

——《算法竞赛入门经典（第 2 版）》

如果要用递归实现，也可以：

从分治角度，我们将搜索区间 $[i,j]$ 对应的子问题记为 $f(i,j)$ 。

以原问题 $f(0,n−1)$ 为起始点，通过以下步骤进行二分查找：

计算搜索区间 $[i,j]$ 的中点 $m$ ，根据它排除一半搜索区间。
递归求解规模减小一半的子问题，可能为 $f(i,m−1)$ 或 $f(m+1,j)$ 。
循环第 1 步和第 2 步，直至找到 target 或区间为空时返回。

/* 二分查找：问题 f(i, j) */
int dfs(int nums[], int target, int i, int j) {
    // 若区间为空，代表无目标元素，则返回 -1
    if (i > j) {
        return -1;
    }
    // 计算中点索引 m
    int m = (i + j) / 2;
    if (nums[m] < target) {
        // 递归子问题 f(m+1, j)
        return dfs(nums, target, m + 1, j);
    } else if (nums[m] > target) {
        // 递归子问题 f(i, m-1)
        return dfs(nums, target, i, m - 1);
    } else {
        // 找到目标元素，返回其索引
        return m;
    }
}

/* 二分查找 */
int binarySearch(int nums[], int target, int numsSize) {
    int n = numsSize;
    // 求解问题 f(0, n-1)
    return dfs(nums, target, 0, n - 1);
}

（来源：12.2 分治搜索策略 - Hello 算法）

注意事项
- 二分查找仅适用于有序数据。若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。因为排序算法的时间复杂度通常为 $O(nlog⁡n)$ ，比线性查找和二分查找都更高。对于频繁插入元素的场景，为保持数组有序性，需要将元素插入到特定位置，时间复杂度为 $O(n)$ ，也是非常昂贵的。
- 二分查找仅适用于数组。二分查找需要跳跃式（非连续地）访问元素。
- 小数据量下，线性查找性能更佳。在线性查找中，每轮只需 1 次判断操作；而在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；因此，当数据量 n 较小时，线性查找反而比二分查找更快。
  线性查找就是按顺序遍历整个数组。
  1
  2
  3
  4
  5
  6
  7
  8
  /* 在数组中查找指定元素 */
  int find(int *nums, int size, int target) {
  for (int i = 0; i < size; i++) {
  if (nums[i] == target)
  return i;
  }
  return -1;
  }

23.7 快速排序

** 快速排序（quick sort）** 是一种基于分治策略的排序算法，运行高效，应用广泛。

快速排序的核心操作是 **“哨兵划分”**，其目标是：选择数组中的某个元素作为 “基准数”，将所有小于基准数的元素移到其左侧，而大于基准数的元素移到其右侧。具体来说，哨兵划分的流程为：

选取数组最左端元素作为基准数，初始化两个指针 i 和 j 分别指向数组的两端。
设置一个循环，在每轮中使用 i（j）分别寻找第一个比基准数大（小）的元素，然后交换这两个元素。
循环执行步骤 2. ，直到 i 和 j 相遇时停止，最后将基准数交换至两个子数组的分界线。

哨兵划分完成后，原数组被划分成三部分：左子数组、基准数、右子数组，且满足 “左子数组任意元素 $≤$ 基准数 $≤$ 右子数组任意元素”。因此，我们接下来只需对这两个子数组进行排序。

Note

哨兵划分的实质是将一个较长数组的排序问题简化为两个较短数组的排序问题。

——11.5 快速排序 - Hello 算法

“哨兵划分” 的 C 语言实现：

/* 元素交换 */
void swap(int nums[], int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

/* 哨兵划分 */
int partition(int nums[], int left, int right) {
    // 以 nums[left] 为基准数
    int i = left, j = right;
    while (i < j) {
        while (i < j && nums[j] >= nums[left]) {
            j--; // 从右向左找首个小于基准数的元素
        }
        while (i < j && nums[i] <= nums[left]) {
            i++; // 从左向右找首个大于基准数的元素
        }
        // 交换这两个元素
        swap(nums, i, j);
    }
    // 将基准数交换至两子数组的分界线
    swap(nums, i, left);
    // 返回基准数的索引
    return i;
}

快速排序的整体流程如下图所示。

首先，对原数组执行一次 “哨兵划分”，得到未排序的左子数组和右子数组。
然后，对左子数组和右子数组分别递归执行 “哨兵划分”。
持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。

快速排序的 C 语言实现：

/* 快速排序 */
void quickSort(int nums[], int left, int right) {
    // 子数组长度为 1 时终止递归
    if (left >= right) {
        return;
    }
    // 哨兵划分
    int pivot = partition(nums, left, right);
    // 递归左子数组、右子数组
    quickSort(nums, left, pivot - 1);
    quickSort(nums, pivot + 1, right);
}

23.8 过河卒问题 —— 广度优先搜索

问题描述：在平面直角坐标系的原点，有一个过河卒需要走到目标点 B。它只能向下或者向右移动。现给出点 B 的坐标 $(m,n)$ ， $0\leqslant m,n\leqslant20$ ，计算出过河卒从原点到 B 点的路径条数。

该问题本质上是杨辉三角问题：

#include <stdio.h>

const int MAX_SIZE = 25;

int main(void)
{
    int a[MAX_SIZE][MAX_SIZE] = {};
    int m = 0, n = 0;
    scanf("%d %d", &m, &n);
    for(int i = 0; i <= m; i++)
    {
        for(int j = 0; j <= n; j++)
        {
            if (i == 0 && j == 0)
            {
                continue;// 题目隐含了“B点和原点不重合”的信息
            }
            else if (i == 0 || j == 0)
            {
                a[i][j] = 1;
            }
            else
            {
                a[i][j] = a[i-1][j] + a[i][j-1];
            }
        }
    }
    printf("%d", a[m][n]);
}

Lesson24 链表

24.1 链表介绍

在之前，如果需要一次性存储数个数据，那么我们会使用数组。但问题是：如果这个数据量是不定的、会增加的，那我们要怎么办呢？定义一个超大长度的数组吗？且不说内存限制，在存储初期数据量较小的时候，我们的程序申请了大量内存却没有充分利用，造成严重的内存浪费。

因此，C 语言提供了一种数据结构：链表 (Linked List)，恰好和数组的缺点互补。

数组的劣势

内存空间是所有程序的公共资源，在一个复杂的系统运行环境下，空闲的内存空间可能散落在内存各处。我们知道，存储数组的内存空间必须是连续的，而当数组非常大时，内存可能无法提供如此大的连续空间。此时链表的灵活性优势就体现出来了。

——4.2 链表 - Hello 算法

向数组中插入元素的代价太高了，因为这意味着我们必须将许多元素移个位来空出位置。

——Linked List Basics - Stanford University

链表是一种线性数据结构，其中的每个元素都是一个节点 (node) 对象，各个节点通过 “引用”（在 C 语言中，就是指针）相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。

《算法竞赛入门经典（第 2 版）》提供了基于数组的链表实现，但这种实现方式不太友好，和基于指针的实现相比难度要高得多。

链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

链表的组成单位是节点对象。每个节点都包含两项数据：节点的 “值” 和指向下一节点的 “引用”，使用结构体来定义。节点对象之间相互独立。

链表的首个节点被称为 “头节点”，最后一个节点被称为 “尾节点”。尾节点指向的是空引用 NULL。
由于每个节点还需额外保存一个引用（指针）。因此在相同数据量下，链表比数组占用更多的内存空间。

（来源：4.2 链表 - Hello 算法）

一个有限链表的示例如下：

/* 链表节点结构体 */
struct node {
	int data;// 节点值
	struct node* next;// 指向下一个节点的指针
}

/* 链表体 */
struct node* BuildOneTwoThree() {
    struct node* head = NULL;
    struct node* second = NULL;
    struct node* third = NULL;
    head = malloc(sizeof(struct node)); // 在堆区分配三个节点
    second = malloc(sizeof(struct node));
    third = malloc(sizeof(struct node));
    head->data = 1; // 初始化第一个节点
    head->next = second; // 注意指针的初始化
    second->data = 2; // 初始化第二个节点
    second->next = third;
    third->data = 3; // 初始化第三个节点
    third->next = NULL;
    return head;
}

（来源：Linked List Basics - Stanford University，Chinese translated by ME）

这个例子意在说明链表的工作模式。在实践中，我们需要函数来创建节点（BuildOneTwoThree() 还是有很多重复性操作的，是不是？）：

/* 链表节点结构体 */
typedef struct ListNode {
    int val;               // 节点值
    struct ListNode *next; // 指向下一节点的指针
} ListNode;

/* 节点创建函数 */
ListNode* newListNode(int val) {
    ListNode* node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;// ->是结构体的成员访问运算符
    node->next = NULL;// 创建独立节点，节点关系之后再定义
    return node;// 返回该节点的地址
}

24.2 链表的初始化

建立链表分为两步：

初始化各个节点对象
构建节点之间的引用关系

/* 初始化链表 1 -> 3 -> 2 -> 5 -> 4 */
/*以我们上面给出的创建函数为基础*/
// 初始化各个节点
ListNode* n0 = newListNode(1);
ListNode* n1 = newListNode(3);
ListNode* n2 = newListNode(2);
ListNode* n3 = newListNode(5);
ListNode* n4 = newListNode(4);
// 构建节点之间的引用
n0->next = n1;
n1->next = n2;
n2->next = n3;
n3->next = n4;

我们通常将头节点当作链表的代称，比如以上代码中的链表可记作链表 n0 。

24.3 插入节点

假设我们想在相邻的两个节点 n0 和 n1 之间插入一个新节点 P ，则只需改变两个节点引用（指针）即可。

（来源：4.2 链表 - Hello 算法）

/* 在链表的节点 n0 之后插入节点 P */
void insert(ListNode *n0, ListNode *P) {
    P->next = n0->next;
    n0->next = P;
}

Warning

请不要更改顺序，因为先将 n0->next 指向 P 会导致链表 “断裂”。

24.4 删除节点

在链表中删除节点也非常方便，只需改变一个节点的引用（指针）即可。

请注意，尽管在删除操作完成后节点 P 仍然指向 n1 ，但实际上遍历此链表已经无法访问到 P ，这意味着 P 已经不再属于该链表了。

/* 删除链表的节点 n0 之后的首个节点 */
// 注意：stdio.h 占用了 remove 关键词
void removeItem(ListNode *n0) {
    if (!n0->next)
        return;
    // n0 -> P -> n1
    ListNode *P = n0->next;
    ListNode *n1 = P->next;
    n0->next = n1;
    // 释放内存
    free(P);
}

24.5 访问节点

在链表中访问节点的效率较低。由于无法直接访问中间节点，程序需要从头节点出发，逐个向后遍历，直至找到目标节点。也就是说，访问链表的第 $i$ 个节点需要循环 $i−1$ 轮。

/* 访问链表中索引为 index 的节点 */
ListNode *access(ListNode *head, int index) {
    for (int i = 0; i < index; i++) {
        if (head == NULL)
            return NULL;
        head = head->next;
    }
    return head;
}

24.6 查找节点

遍历链表，查找其中值为 target 的节点，输出该节点在链表中的索引。此过程也属于线性查找。

/* 在链表中查找值为 target 的首个节点 */
int find(ListNode *head, int target) {
    int index = 0;
    while (head) {
        if (head->val == target)
            return index;
        head = head->next;
        index++;
    }
    return -1;
}

24.7 特殊类型链表

到现在我们设计的是最基础的链表：单向链表。其实我们还有其他类型的链表

24.7.1 环形链表

如果我们令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。

24.7.2 双向链表

与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

/* 双向链表节点结构体 */
typedef struct ListNode {
    int val;               // 节点值
    struct ListNode *next; // 指向后继节点的指针
    struct ListNode *prev; // 指向前驱节点的指针
} ListNode;

/* 构造函数 */
ListNode *newListNode(int val) {
    ListNode *node;
    node = (ListNode *) malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    node->prev = NULL;
    return node;
}