C-Week6

21.1 字符串介绍#

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

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

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

1
char* str = "Hello";

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

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

21.2 字符串常量#

结合Lesson20 4.2&10 食用

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

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

21.3 字符串的输入输出#

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

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

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

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

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

1
char t[8];
2
scanf("%s", t);//为什么我们不用'&'了？请参考Lesson20 2.2
3
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
damedame
2
damedame
3
E:\Learning\x64\Debug\string.exe (进程 36172)已退出，代码为 -1073740791 (0xc0000409)。
4
    //这退出代码不对劲啊！

我们还有一个程序：

1
#include <stdio.h>
2

3
int main(void)
4
{
5
  char word[8];
6
  char word2[8];
7
  scanf("%s", t);
8
  scanf("%s", s);
9
  printf("%s##%s##", t, s);
10
}

输入：

1
12345678
2
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)，溢出的数据将之前写入的数据给覆盖了。在实践中，攻击者可以通过分析目标函数的地址，输入足够数量的任意字符，让程序执行目标函数（即使正常流程下根本无法执行该函数），从而达到控制/破坏目的。

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

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

输入：

1
damedame

输出：

1
damedam

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

1
char t[8];
2
char s[8];
3
scanf("%7s", t);
4
scanf("%7s", s);
5
printf("%s#%s", t, s);

本来我要输入：

1
damedame
2
dameyo

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

1
damedam#e

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

1
char* string;
2
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
char month[][15] = {
2
    "January",
3
    "February",
4
    "March",
5
    "April",
6
    "May",
7
    "June",
8
    "July",
9
    "August",
10
    "Septemper",
11
    "October",
12
    "November",
13
    "December"
14
}

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

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
#include <stdio.h>
2

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

在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
$ ls
2
a.out hi ...

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

1
$ ls -l hi
2
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
$ busybox ls
2
Desktop     Downloads   Pictures    Templates   a.out       hi
3
Documents   Music       Public      Videos      hello.c     install.sh

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

7
Usage: busybox [function [arguments]...]
8
  or: busybox --list[-full]
9
  or: busybox --install [-s] [DIR]
10
  or: function [arguments]...
11

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

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

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
#include <stdio.h>
2

3
int main(int a, const char *b[])
4
{
5
  char ch;
6
  while ((ch = getchar()) != EOF)
7
  {
8
    putchar(ch);
9
  }
10
  printf("EOF\n");
11
}

Note

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

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

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

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

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

1
char *strchr(const char *str, int c)

1
#include <stdio.h>
2
#include <string.h>
3

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

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

1
char *strrchr(const char *str, int c)

1
#include <stdio.h>
2
#include <string.h>
3

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

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

1
#include <stdio.h>
2
#include <string.h>
3

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

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

1
#include <stdio.h>
2
#include <string.h>
3

4
int main(void){
5
    char data[] = "furry";
6
    char* p = strchr(data, 'r');
7
    char* t = (char*)malloc(strlen(p) + 1);
8
    strcpy(t, p);
9
    printf("%s", t);
10
    free(t);
11
}

1
#include <stdio.h>
2
#include <string.h>
3

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

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

1
#include <stdio.h>
2
#include <string.h>
3

4

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

11
   ret = strstr(haystack, needle);
12

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

15
   return(0);
16
}

1
子字符串是： NOOB

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

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

1
char *gets(char *str)

1
#include <stdio.h>
2

3
int main()
4
{
5
   char str[50];
6

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

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

12
   return(0);
13
}

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

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

1
int puts(const char *str)

1
#include <stdio.h>
2
#include <string.h>
3

4
int main()
5
{
6
   char str1[15];
7
   char str2[15];
8

9
   strcpy(str1, "RUNOOB1");
10
   strcpy(str2, "RUNOOB2");
11

12
   puts(str1);
13
   puts(str2);
14

15
   return(0);
16
}

1
RUNOOB1
2
RUNOOB2

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

1
#include <stdio.h>
2

3
int main(void)
4
{
5
    int rc = fputs("Hello World", stdout);
6

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

1
Hello World

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
enum DAY
2
{
3
      MON, TUE, WED, THU, FRI, SAT, SUN
4
};
5
//MON = 0; TUE = 1; WED = 2; THU = 3; FRI = 4; SAT = 5; SUN = 6

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

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

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

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

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

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

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

1
#include <stdio.h>
2

3
enum DAY
4
{
5
      MON=1, TUE, WED, THU, FRI, SAT, SUN
6
};
7
int main(void){
8
  enum DAY p = TUE;
9
    scanf("%d", &p);
10
    printf("%d\n", p);
11
}

1
>>12
2
12

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

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

1
//连续的枚举类型
2
enum DAY
3
{
4
      MON=1, TUE, WED, THU, FRI, SAT, SUN
5
};
6
//不连续的枚举类型
7
enum
8
{
9
    ENUM_0,
10
    ENUM_10 = 10,
11
    ENUM_11
12
};

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

• 1
  #include <stdio.h>
  2
  
  3
  enum Color {red, yellow, blue, green, orange, NumColors};
  4
  
  5
  int main(void){
  6
      int color = -1;
  7
      char* ColorName[NumColors] = {
  8
          "red",
  9
          "yellow",
  10
          "blue",
  11
          "green",
  12
          "orange"
  13
      };
  14
      char* colorName = NULL;
  15
      printf("Enter a code of your favorite color:")
  16
      scanf("%d", &color);
  17
      if (color >= 0 && color <= NumColors);
  18
      {
  19
          colorName = ColorName[color];
  20
      }
  21
      else
  22
      {
  23
          colorName = "unknown";
  24
      }
  25
      printf("Your favorite color is %s\n", colorName);
  26
  }

  展开收起

• 1
  #include <stdio.h>
  2
  
  3
  enum DAY
  4
  {
  5
        MON=1, TUE, WED, THU, FRI, SAT, SUN
  6
  } day;
  7
  int main()
  8
  {
  9
      for (day = MON; day <= SUN; day++) {
  10
          printf("枚举元素：%d \n", day);
  11
      }
  12
  }

• 1
  #include <stdio.h>
  2
  #include <stdlib.h>
  3
  int main()
  4
  {
  5
  
  6
      enum color { red=1, green, blue };
  7
  
  8
      enum  color favorite_color;
  9
  
  10
      /* 用户输入数字来选择颜色 */
  11
      printf("请输入你喜欢的颜色: (1. red, 2. green, 3. blue): ");
  12
      scanf("%u", &favorite_color);
  13
  
  14
      /* 输出结果 */
  15
      switch (favorite_color)
  16
      {
  17
      case red:
  18
          printf("你喜欢的颜色是红色");
  19
          break;
  20
      case green:
  21
          printf("你喜欢的颜色是绿色");
  22
          break;
  23
      case blue:
  24
          printf("你喜欢的颜色是蓝色");
  25
          break;
  26
      default:
  27
          printf("你没有选择你喜欢的颜色");
  28
      }
  29
  
  30
      return 0;
  31
  }

  展开收起

23.1 递归的定义#

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

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

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

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

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

1
int func(传入数值) {
2
  if (终止条件) {
3
      return 最小子问题解;
4
  }
5
  else {
6
      return func(缩小规模);
7
  }
8
}

23.2 用递归解决递推问题#

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

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

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

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

1
int f(int n){
2
    if (n == 0){
3
        return 1;
4
    }
5
    else{
6
        return f(n - 1) * n;
7
    }
8
}

如果要计算$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
void print_number (int n)
2
{
3
    int x = n / 10;
4
    if (x != 0)
5
    {
6
        print_number(x);
7
    }
8
    printf("%d\n", n % 10);
9
}

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

1
int fibonacci(int n) {
2
    if (n == 0 || n == 1) {
3
        return 1; // base cases
4
    }
5
    else {
6
        return fibonacci(n-1) + fibonacci(n-2); // recursive step
7
    }
8
}

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

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

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

23.3 尾递归#

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

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

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

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

1
/* 尾递归 */
2
int tailRecur(int n, int res) {
3
    // 终止条件
4
    if (n == 0)
5
        return res;
6
    // 尾递归调用
7
    return tailRecur(n - 1, res + n);
8
    /*
9
}

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

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

可视化：

1
int g(int x) {
2
  if (x == 1) {
3
    return 1;
4
  }
5
  int y = g(x-1);
6
  return x*y;
7
}

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
  void move(int *src, int *srcSize, int *tar, int *tarSize) {
  3
      // 从 src 顶部拿出一个圆盘
  4
      int pan = src[*srcSize - 1];
  5
      src[*srcSize - 1] = 0;
  6
      (*srcSize)--;
  7
      // 将圆盘放入 tar 顶部
  8
      tar[*tarSize] = pan;
  9
      (*tarSize)++;
  10
  }
  11
  
  12
  /* 求解汉诺塔问题 f(i) */
  13
  void dfs(int i, int *src, int *srcSize, int *buf, int *bufSize, int *tar, int *tarSize) {
  14
      // 若 src 只剩下一个圆盘，则直接将其移到 tar
  15
      if (i == 1) {
  16
          move(src, srcSize, tar, tarSize);
  17
          return;
  18
      }
  19
      // 子问题 f(i-1) ：将 src 顶部 i-1 个圆盘借助 tar 移到 buf
  20
      dfs(i - 1, src, srcSize, tar, tarSize, buf, bufSize);
  21
      // 子问题 f(1) ：将 src 剩余一个圆盘移到 tar
  22
      move(src, srcSize, tar, tarSize);
  23
      // 子问题 f(i-1) ：将 buf 顶部 i-1 个圆盘借助 src 移到 tar
  24
      dfs(i - 1, buf, bufSize, src, srcSize, tar, tarSize);
  25
  }
  26
  
  27
  /* 求解汉诺塔问题 */
  28
  void solveHanota(int *A, int *ASize, int *B, int *BSize, int *C, int *CSize) {
  29
      // 将 A 顶部 n 个圆盘借助 B 移到 C
  30
      dfs(*ASize, A, ASize, B, BSize, C, CSize);
  31
  }

  展开收起

  使用的示例程序：

  1
  #include <stdio.h>
  2
  #include <stdlib.h>
  3
  
  4
  // 移动一个圆盘
  5
  void move(int *src, int *srcSize, int *tar, int *tarSize) {
  6
      // 从 src 顶部拿出一个圆盘
  7
      int pan = src[*srcSize - 1];
  8
      src[*srcSize - 1] = 0;
  9
      (*srcSize)--;
  10
      // 将圆盘放入 tar 顶部
  11
      tar[*tarSize] = pan;
  12
      (*tarSize)++;
  13
      printf("Move disk %d from %p to %p\n", pan, (void*)src, (void*)tar);
  14
  }
  15
  
  16
  // 求解汉诺塔问题 f(i)
  17
  void dfs(int i, int *src, int *srcSize, int *buf, int *bufSize, int *tar, int *tarSize) {
  18
      // 若 src 只剩下一个圆盘，则直接将其移到 tar
  19
      if (i == 1) {
  20
          move(src, srcSize, tar, tarSize);
  21
          return;
  22
      }
  23
      // 子问题 f(i-1) ：将 src 顶部 i-1 个圆盘借助 tar 移到 buf
  24
      dfs(i - 1, src, srcSize, tar, tarSize, buf, bufSize);
  25
      // 子问题 f(1) ：将 src 剩余一个圆盘移到 tar
  26
      move(src, srcSize, tar, tarSize);
  27
      // 子问题 f(i-1) ：将 buf 顶部 i-1 个圆盘借助 src 移到 tar
  28
      dfs(i - 1, buf, bufSize, src, srcSize, tar, tarSize);
  29
  }
  30
  
  31
  // 求解汉诺塔问题
  32
  void solveHanota(int *A, int *ASize, int *B, int *BSize, int *C, int *CSize) {
  33
      // 将 A 顶部 n 个圆盘借助 B 移到 C
  34
      dfs(*ASize, A, ASize, B, BSize, C, CSize);
  35
  }
  36
  
  37
  int main() {
  38
      int n = 3; // 圆盘数量
  39
      int *A = (int *)malloc(n * sizeof(int)); // 源柱子
  40
      int *B = (int *)malloc(n * sizeof(int)); // 辅助柱子
  41
      int *C = (int *)malloc(n * sizeof(int)); // 目标柱子
  42
      int *ASize = (int *)malloc(sizeof(int)); // 源柱子圆盘数量
  43
      int *BSize = (int *)malloc(sizeof(int)); // 辅助柱子圆盘数量
  44
      int *CSize = (int *)malloc(sizeof(int)); // 目标柱子圆盘数量
  45
  
  46
      // 初始化圆盘
  47
      for (int i = 0; i < n; i++) {
  48
          A[i] = n - i;
  49
      }
  50
      *ASize = n;
  51
      *BSize = 0;
  52
      *CSize = 0;
  53
  
  54
      printf("Solving Tower of Hanoi with %d disks:\n", n);
  55
      solveHanota(A, ASize, B, BSize, C, CSize);
  56
  
  57
      free(A);
  58
      free(B);
  59
      free(C);
  60
      free(ASize);
  61
      free(BSize);
  62
      free(CSize);
  63
  
  64
      return 0;
  65
  }

  展开收起

  （由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
  int binarySearch(int *nums, int len, int target) {
  3
      // 初始化双闭区间 [0, n-1] ，即 i, j 分别指向数组首元素、尾元素
  4
      int i = 0, j = len - 1;
  5
      // 循环，当搜索区间为空时跳出（当 i > j 时为空）
  6
      while (i <= j) {
  7
          int m = i + (j - i) / 2; // 计算中点索引 m
  8
          if (nums[m] < target)    // 此情况说明 target 在区间 [m+1, j] 中
  9
              i = m + 1;
  10
          else if (nums[m] > target) // 此情况说明 target 在区间 [i, m-1] 中
  11
              j = m - 1;
  12
          else // 找到目标元素，返回其索引
  13
              return m;
  14
      }
  15
      // 未找到目标元素，返回 -1
  16
      return -1;
  17
  }

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

  用递归实现二分查找

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

  ——《算法竞赛入门经典（第 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
  /* 二分查找：问题 f(i, j) */
  2
  int dfs(int nums[], int target, int i, int j) {
  3
      // 若区间为空，代表无目标元素，则返回 -1
  4
      if (i > j) {
  5
          return -1;
  6
      }
  7
      // 计算中点索引 m
  8
      int m = (i + j) / 2;
  9
      if (nums[m] < target) {
  10
          // 递归子问题 f(m+1, j)
  11
          return dfs(nums, target, m + 1, j);
  12
      } else if (nums[m] > target) {
  13
          // 递归子问题 f(i, m-1)
  14
          return dfs(nums, target, i, m - 1);
  15
      } else {
  16
          // 找到目标元素，返回其索引
  17
          return m;
  18
      }
  19
  }
  20
  
  21
  /* 二分查找 */
  22
  int binarySearch(int nums[], int target, int numsSize) {
  23
      int n = numsSize;
  24
      // 求解问题 f(0, n-1)
  25
      return dfs(nums, target, 0, n - 1);
  26
  }

  展开收起

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

• 注意事项

  • 二分查找仅适用于有序数据。若输入数据无序，为了使用二分查找而专门进行排序，得不偿失。因为排序算法的时间复杂度通常为 $O(nlog⁡n)$ ，比线性查找和二分查找都更高。对于频繁插入元素的场景，为保持数组有序性，需要将元素插入到特定位置，时间复杂度为 $O(n)$ ，也是非常昂贵的。

  • 二分查找仅适用于数组。二分查找需要跳跃式（非连续地）访问元素。

  • 小数据量下，线性查找性能更佳。在线性查找中，每轮只需 1 次判断操作；而在二分查找中，需要 1 次加法、1 次除法、1 ~ 3 次判断操作、1 次加法（减法），共 4 ~ 6 个单元操作；因此，当数据量 n 较小时，线性查找反而比二分查找更快。

    线性查找就是按顺序遍历整个数组。

    1
    /* 在数组中查找指定元素 */
    2
    int find(int *nums, int size, int target) {
    3
        for (int i = 0; i < size; i++) {
    4
            if (nums[i] == target)
    5
                return i;
    6
        }
    7
        return -1;
    8
    }