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

输出的是：

1

Hello

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

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

在使用 Clang 编译时，你会收到这样一条Warning：

1

warning: 'scanf' is deprecated(废弃的): This function or variable may be unsafe.

如果使用 MSVS 生成，这个Warning的性质会变成Error！

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

1

damedame

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

1

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

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

1
2
3
4

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

我们还有一个程序：

1
2
3
4
5
6
7
8
9
10

#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

输入：

1

damedame

输出：

1

damedam

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

1
2
3
4
5

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

本来我要输入：

1
2

damedame
dameyo

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

1

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'占了，又用的是静态内存分配，结果就是你再也无法对这个字符串写入任何字符。

如果要对一个字符串进行修改，也可以使用 memset：

1

void *memset( void *dest, int ch, size_t count );

将值 (unsigned char)ch 复制到由 dest 指向的数组的前 count 个字符中。

21.4 字符串数组

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

字符串数组的定义：

1

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

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

例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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。

对于以下程序：

1
2
3
4
5
6
7
8
9

#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

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

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

1
2
3
4
5
6
7
8
9
10
11

#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()。

示例：

1
2
3
4
5
6
7
8
9
10

#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。

示例：

1
2
3
4
5
6
7
8

#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

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

1
2
3
4
5
6
7
8
9

#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怎么做？

截取后半部分：

1
2
3
4
5
6
7
8
9
10
11

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

截取前半部分：

1
2
3
4
5
6
7
8
9
10
11
12
13

#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。

示例：

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

#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()一致，但前者不区分大小写。

strcasestr()的声明：

1

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

• haystack -- 被检索的字符串。

• needle -- 在 haystack 字符串内要搜索的小字符串。

示例：

1
2
3
4
5
6
7
8
9
10

#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:    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。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13

#include <stdio.h>

int main()
{
   char str[50];

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

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

   return(0);
}

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

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

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' 了，因为字符串中已经有了。

示例：

1
2
3
4
5
6
7
8
9

# 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。

示例：

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

#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

RUNOOB1
RUNOOB2

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

这是fputs()的声明：

1

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

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

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

示例：

1
2
3
4
5
6
7
8
9

#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。

1
2
3
4
5

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

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

1
2
3
4
5

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

1
2
3
4

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

1
2
3
4

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

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

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

1
2
3
4
5
6
7
8
9
10
11

#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，编译器没有输出任何信息）。

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

1
2
3
4
5
6
7
8
9
10
11
12

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

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

• 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
  

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

• 1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  

  #include <stdio.h>
  
  enum DAY
  {
        MON=1, TUE, WED, THU, FRI, SAT, SUN
  } day;
  int main()
  {
      for (day = MON; day <= SUN; day++) {
          printf("枚举元素：%d \n", day);
      }
  }

• 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
  

  #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;
  }

Lesson23 递归与分治思想

有人说，「递归」是检验编程天赋的试金石。

23.1 递归的定义

递归 (Recursion) 在数学和计算机科学中是指在函数的定义中使用函数自身的方法，在计算机科学中还额外指一种通过重复将问题分解为同类的子问题而解决问题的方法。

如果你还不理解，参考递归 & 分治 - OI Wiki

递归的基本思想是某个函数直接或者间接地调用自身，这样原问题的求解就转换为了许多性质相同但是规模更小的子问题。求解时只需要关注如何把原问题划分成符合条件的子问题，而不需要过分关注这个子问题是如何被解决的。

从实现的角度看，递归代码主要包含三个要素：

1. 终止条件：定义了最简子问题的答案。用于决定什么时候由 “递” 转 “归”。
2. 递归调用：对应 “递”，函数调用自身以解决子问题，通常输入更小或更简化的参数。
3. 返回结果：对应 “归”，将当前递归层级的结果返回至上一层。

1
2
3
4
5
6
7
8

int func(传入数值) {
  if (终止条件) {
      return 最小子问题解;
  }
  else {
      return func(缩小规模);
  }
}

23.2 用递归解决递推问题

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

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

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

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

1
2
3
4
5
6
7
8

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 的正序输出数字也可以用递归来解决

1
2
3
4
5
6
7
8
9

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

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

1
2
3
4
5
6
7
8

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 算法）

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

23.3 尾递归

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

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

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

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

1
2
3
4
5
6
7
8
9

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

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

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

可视化：

1
2
3
4
5
6
7

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

23.4 分治思想

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

• 过程

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

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

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

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

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

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 算法）

• 代码实现（仅算法）

  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
  

  /* 移动一个圆盘 */
  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);
  }

  使用的示例程序：

  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
  

  #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 算法）

• 代码实现

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

  /* 二分查找（双闭区间） */
  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;
  }

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

  /* 二分查找（左闭右开区间） */
  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)$ 为起始点，通过以下步骤进行二分查找：

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

  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
  

  /* 二分查找：问题 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) 是一种基于分治策略的排序算法，运行高效，应用广泛。

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

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

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

“哨兵划分” 的 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

/* 元素交换 */
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. 首先，对原数组执行一次 “哨兵划分”，得到未排序的左子数组和右子数组。
2. 然后，对左子数组和右子数组分别递归执行 “哨兵划分”。
3. 持续递归，直至子数组长度为 1 时终止，从而完成整个数组的排序。

快速排序的 C 语言实现：

1
2
3
4
5
6
7
8
9
10
11
12

/* 快速排序 */
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 点的路径条数。

  

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

  

  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
  

  #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)，恰好和数组的缺点互补。

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

——Linked List Basics - Stanford University

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

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

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

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

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

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

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

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

/* 链表节点结构体 */
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()还是有很多重复性操作的，是不是？）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14

/* 链表节点结构体 */
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
2
3
4
5
6
7
8
9
10
11
12
13

/* 初始化链表 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 算法）

1
2
3
4
5

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

24.4 删除节点

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

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

1
2
3
4
5
6
7
8
9
10
11
12

/* 删除链表的节点 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$ 轮。

1
2
3
4
5
6
7
8
9

/* 访问链表中索引为 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 的节点，输出该节点在链表中的索引。此过程也属于线性查找。

1
2
3
4
5
6
7
8
9
10
11

/* 在链表中查找值为 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 双向链表

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

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

/* 双向链表节点结构体 */
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;
}

Lesson25 文件操作

到目前为止，我们的程序还停留在 “你问我答” 的阶段。输入和输出都是一次性的，除非我们自己记录——但这很奇怪，不是么？你在玩游戏的时候调整的那些设置可是一直保存的，不会说你打完一晚上游戏退出，第二天又要调整设置。我们的输入或者程序的响应状况一定是被持久化保存在某处的。

你可能会说：“配置文件啊！” 那么配置文件是如何被创建、记录程序信息并被程序读取的呢？接下来我们将学习 C 语言的文件操作函数。

头文件 stdio.h 提供通用的文件操作支持。

25.1 文件访问

命令行是标准输入输出流，因此为了对文件进行操作，我们需要新的输入输出流。这需要使用一个特殊的指针——文件指针，声明为：

1

FILE* fp

文件指针初始化时，指向文件开头。

C 的文件读取 / 创建函数是：

1

FILE *fopen( const char *filename, const char *mode );

如果成功，返回指向新文件流的指针。出错时，返回空指针。

filename 可以是绝对路径，也可以是相对路径，这需要看你系统的支持情况。

以下是模式字符串的说明：

文件访问模式标志 "b" 指定以二进制模式打开文件，如果需要，将其加到上述模式字符串之后。

+ 表示更新模式，可以在读取和写入两种模式间切换，但需要重新定位文件指针，清空或重置内部缓冲区，让系统知道你要在一个新的、明确的位置开始操作。

示例：

1

FILE* file_ptr = fopen("fileName.txt", "w"); // 在程序当前同级目录下以写入模式打开 fileName.txt

请注意，在文件完全使用完毕后，需要关闭文件流：

1

fclose((FILE*)fp);

fclose() 将会强制刷新缓冲区，把所有未写入文件的缓冲区数据刷新到操作系统（系统会尽快将这些数据写入磁盘），其余未写入缓冲区的数据则丢弃（释放空间）。

25.2 文件写入与读取

文件流也有对应的格式化与非格式化输出。

• fscanf 和 fprintf。由于文件流是我们创建的，因此需要传递给它们。其他则参考一般的 scanf 和 printf 即可：

1
2
3

int fscanf( FILE *stream, const char *format, ... );

int fprintf( FILE* stream, const char* format, ... );

• fgetc、fgets 和 fputc、fputs。

1
2
3
4
5
6
7

int fgetc(FILE* stream);

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

int fputc( int ch, FILE* stream );

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

以上是对文本文件的读写。对于二进制文件，C 也提供了直接读写的能力：

1
2
3

size_t fread( void *buffer, size_t size, size_t count, FILE *stream );

size_t fwrite( const void* buffer, size_t size, size_t count, FILE* stream );

这两个函数都是用于存储块（通常是数组或结构体）的读写。

请注意，在标准的 I/O 函数中，写入操作总是会覆盖从当前位置开始的内容。插入操作涉及到数据的移动（参考数组），实现要更复杂。

25.3 文件内部的定位

ftell 函数用于指示当前文件指针的位置。

1

long ftell( FILE* stream );

如果流以二进制模式打开，此函数返回的值是从文件开头开始的字节数。

如果流以文本模式打开，此函数返回的值是不确定的，并且仅在作为 fseek() 的输入时才有意义。

fseek 函数用于将文件指针设置到指定的偏移量，并将数据写入文件。

1

int fseek( FILE* stream, long offset, int origin );

如果流以二进制模式打开，当 origin 为 SEEK_SET 时，新位置是从文件开头测量的 offset 字节处；当 origin 为 SEEK_CUR 时，新位置是从当前文件位置处测量；当 origin 为 SEEK_END 时，新位置是从文件末尾处测量。二进制流不一定需要支持 SEEK_END，特别是如果输出额外的空字节时。

如果流以文本模式打开，offset 的唯一（确保）支持的值是 0（适用于任何 origin）以及先前对与同一文件关联的流调用 ftell() 返回的值（仅适用于 SEEK_SET）。

例如：

1
2
3

fputs("Welcome to GeeksforGeeks", ptr);

fseek(ptr, 11, SEEK_SET); // 现在文件指针位于相对于文件开头的偏移值为 11 字节的位置，即第一个 'G'

rewind 函数将文件指针设置到文件的开始处。

1

void rewind( FILE *stream );

Lesson26 多文件编译

我们都知道，要使用函数，需要先声明并定义，但是当我们写下 printf() 的时候，我们可没有去定义它，那么 printf() 在哪里定义的？

在单文件编程中，函数声明和定义挤在主文件里。我很想将它们 “隐藏” 掉。编辑器折叠？不不不，那只是掩耳盗铃罢了，但不放主文件，还能放哪里呢？

26.1 c 文件

.c 文件可以单独存放函数的定义。对于函数声明，要么在主文件中声明，要么在后文提及的头文件中声明。

1
2
3
4
5
6
7
8
9
10

#include <cstdio>

int add(int a, int b);

int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", add(a, b));
}

1
2
3
4

int add(int a, int b)
{
    return a + b;
}

在命令行中，需要将关联文件一起输入编译：

1

gcc main.c add.c -o main

因为编译器会单独编译每个 .c 文件。它不知道其他代码文件的内容，也不记得它从以前编译的代码文件中看到的任何内容。因此，即使编译器之前可能已经看到了函数添加的定义（如果先编译 add.c），它也不记得。

因此，如果源码文件中使用了其他库的内容，仍然需要引入，无论在主文件中是否引入。

1
2
3
4
5
6

#include <math.h>

double op(double a, double b)
{
    return sqrt(a) + sqrt(b);
}

由于 .c 文件在编译时独立于主文件编译，因此我们不能 include .c 文件，这样会出现双重定义。即使假设我们不编译 .c，而是将函数定义直接在主文件内展开，也会出现问题：一旦 .c 有改动，那么我们就得重新编译主文件，而主文件很可能还 include 了其他没有改动的库。这样每一次编译，编译器都得基本重新编译一次整个项目，对于大型项目是绝不可接受的（Chromium 一次完整编译的用时往往在数小时到数天不等）。

因此我们使用头文件，只告诉主文件有这个函数存在，编译时编译器会将函数定义链接到对应 .c 文件的编译产物，这样修改后就只需要编译这一个 .c 文件就行。

26.2 头文件

头文件用于存放函数的声明。

1

int add(int a, int b);

1
2
3
4
5
6
7
8
9

#include <cstdio>
#include "add.h"

int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d\n", add(a, b));
}

#include 表示预处理器，在编译期间将函数声明和定义复制到主文件中。

使用 <> 突出所处理的头文件不是用户编写的。预处理器将仅在 include directories（包含目录）指定的目录中搜索头文件。include directories 配置为项目/IDE 设置/编译器设置的一部分，通常默认为包含编译器和/或作系统附带的头文件的目录。预处理器不会在项目的源代码目录中搜索头文件。

"" 主要用于用户头文件的引入，会在当前目录搜索引用的头文件；如果找不到，它将搜索 include directories。

头文件通过预处理器自动引用，不需要在命令行中手动引入：

1

gcc main.c add.c <add.h> -o main

在命名头文件时首选 .h 后缀。