字符串处理基础知识(III) ++++++++++++++++++++++++++++++++ 这一节我们对字符串处理的其他几个重要的基本知识点进行说明。 字典序 ^^^^^^ 在计算机编程语言里，字符串都是可以比较“大小”的，或者更准确地说，字符串是可以有序的。我们知道，实数也是有序的，实数的序依据的是数值的大小。字符串本身并没有大小的区别，比如 ``"hello"`` 和 ``"world"`` 这两个字符串谁大谁小呢？因此字符串的序依据的不是某个数值的大小，而是依据组成字符串的字符在字符表中的顺序，称为\ :strong:`字典序`\ 。 在算法编程的环境里使用的字符表是ASCII码表，共有127个字符，包括了数字、大小写字母、常见的标点符号、算术运算符号、空白符（空格、换行、tab）和其他一些控制字符，另外还有一个非常特别的空字符 ``'\0'``\ ，对应的数值编号为0，在C-string里用作字符串结尾标志。 .. attention:: C标准库 ``cstdio``\ 、\ ``cstring``\ 、\ ``cstdlib`` 中都定义了一个宏 ``#define NULL 0``\ ，如果引入过这几个库之一就可以用 ``NULL`` 来代替 ``'\0'``\ 。但C++语言认为 ``NULL`` 这个用法有很麻烦的多义性，比如它可以用来表示整数0、可以表示空字符、也可以用来表示空指针，所以不推荐使用这个符号。 在字符串处理时如果要表示空字符，建议还是使用 ``'\0'``，如果要表示空指针，则应该用 ``nullptr`` 这个符号。 字符在字符表中的顺序由它们在码表里的编码的大小来确定。所以空字符是最小的字符。在ASCII编码表中，常见的用于字符串的字符顺序如下： .. code-block:: none '\0' < '\t' < '\n' < ' ' < '0' < ... < '9' < 'A' < ... < 'Z' < 'a' < ... < 'z' 这是大多数字符串处理问题需要用到的字符顺序关系，完整的ASCII码表可以查询相关资料。知道了字符的编码顺序之后就很容易理解字符串的字典序规则了，规则一共就三条： 1. 按照从左到右的顺序逐个比较两个字符串相同位置上的字符大小，直到找到第一个字符不同的位置或有一个字符串结束。 2. 第一个字符不同的位置上，哪个字符串的字符小这个字符串的字典序就小；如果有一个字符串结束了还没有找到字符不相等的位置，那么短的那个字符串的字典序小（对于C-string，短者更小的规则是天然适应的，因为短的那个字符串在结尾处有一个天然最小的空字符）。 3. 如果一直没有找到字符不同的位置，而且两个字符串同时结束，那么二者的字典序相等（这也就是两个字符串长度相同、每一个位置上的字符都相等）。 按照这一套比较规则，我们可以举几个例子：\ ``"ABCD" < "BCD"``\ ，\ ``"AB" < "ab"``\ ，\ ``"X" < "XYZ"``\ ，\ ``"hello" < "world"``\ 。可见对于纯英文字母构成的字符串，它们的排列规则和英语词典中单词的排列规则是一致的，这也是字典序这个名称的由来。但如果是纯数字字符构成的整数形式的字符串，却并不是和它们对应的数值顺序一致的，例如 ``"87" < "9"``\ ，而整数87显然比9大。这一点一定要记住。 ``cstring`` 标准库提供 ``strcmp()`` 和 ``strncmp()`` 两个函数用于C-string的字典序比较。C++ string则简单粗暴地直接使用六种关系运算符 ``==, !=, <, >, <=, >=``\ 。 C-string小结 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 现在我们对字符串处理的一些基本概念和最基本的一些操作都已经学完了。字符串是一类重要的信息类型，字符串处理是计算机信息处理中最为重要的技术之一。从概念本身来讲，字符串就是由一连串连续字符构成的信息串，只是不同的编程语言对于字符串的表示形式各有不同，其内在本质都是相同的。 在C++语言来说，C-string和C++ string类都是其表示字符串的形式。从C语言继承而来的C-string最大的优势是速度快，所以现在许多的程序还在坚持使用C-string来进行字符串处理。常用的C-string处理都采用 ``cstring`` 库中的C语言标准库函数，前面已经看到过许多，在 ``cstdio`` 库中也提供了几套用于字符和C-string输入输出的库函数。这些库函数最大的特点也是速度非常的快，如果用C-string来进行字符串处理，就离不开这些库函数的使用。下面对它们进行一个小结。 **8个C-string常用库函数** 与C-string基本处理相关的库函数全部由 ``cstring`` 库提供，使用前必须先引入该库。 1、获取C-string ``s`` 的实际长度。 .. code-block:: c++ size_t strlen(const char *s); 2、获取C-string ``s`` 的实际长度，但以 ``maxlen`` 为上限，即如果长度超过 ``maxlen`` 则返回 ``maxlen`` 的值。 .. code-block:: c++ size_t strlen(const char *s, size_t maxlen); 3、将C-string ``src`` 的内容复制到C-string ``dst`` 中，返回值就是指向 ``dst`` 的指针。 .. code-block:: c++ char *strcpy(char * dst, const char * src); 需注意，此函数复制时并不考虑 ``dst`` 的长度是否足够，因此可能引起超限错误，需要程序员自己确保足够的空间。 4、将C-string ``src`` 中最多 ``len`` 个字符复制到C-string ``dst`` 中，返回值就是指向 ``dst`` 的指针。 .. code-block:: c++ char *strncpy(char * dst, const char * src, size_t len); 需注意，若 ``src`` 的实际长度超过 ``len``\ ，那么复制之后不会自动在 ``dst`` 中添加空字符 ``'\0'`` 作为结尾标志，因此这种情况下 ``dst`` 不保证有正确的结尾。 5、比较 ``s1`` 和 ``s2`` 的字典序，若二者相等，则返回0；若 ``s1`` 先于（小于）\ ``s2`` 则返回一个负数；若 ``s1`` 后于（大于）\ ``s2`` 则返回一个正数。 .. code-block:: c++ int strcmp(const char *s1, const char *s2); 6、比较 ``s1`` 和 ``s2`` 的字典序，返回值的规则和 ``strcmp()`` 函数相同，但是最多只比较前 ``n`` 个字符。 .. code-block:: c++ int strncmp(const char *s1, const char *s2, size_t n); 7、将 ``s2`` 的内容拼接到 ``s1`` 的后面，返回指向 ``s1`` 的指针。 .. code-block:: c++ char *strcat(char *restrict s1, const char *restrict s2); 需注意：此函数并不考虑 ``s1`` 中的长度是否足够，因此可能引起超限错误，需要程序员自己确保足够的空间。 8、将 ``s2`` 中最多 ``n`` 个字符拼接到 ``s1`` 的后面，返回指向 ``s1`` 的指针。 .. code-block:: c++ char *strncat(char *restrict s1, const char *restrict s2, size_t n); **C-string输入输出** 与C-string的输入输出相关的库函数都在 ``cstdio`` 库中提供，使用前必须先引入该库。 1、\ ``scanf()`` 和 ``printf()`` 此二者是最为常用的C-string输入输出函数，占位符为 ``%s``\ 。在输入时，可以添加长度限制 ``%ns``\ ，其中 ``n`` 是一个整数，表示最多读入 ``n`` 个字符，不包括最后的结尾标志符 ``'\0'``\ 。因此这个长度限制至少应该要比实际的字符数组长度小1。例如： .. code-block:: c++ char s[81]; scanf("%80s", s); // 请注意这里限制的长度是80而不是81 printf("You entered: %s\n", s); 优点：功能强大灵活，可以和多个别的数据同时输入输出。例如： .. code-block:: c++ char s[81]; unsigned short age; scanf("%80s %hu", s, &age); // 请注意这里限制的长度是80而不是81 printf("NAME is %s, AGE = %hu\n", s, age); 缺点：``scanf()`` 只能输入以“单词”为单位的字符串，即字符串中不能出现空白符（空格、tab、换行）。例如上面那个例子中，如果要输入的名字是Bill Gates，那么就会出错，\ ``s`` 只会读到Bill就结束了。 2、\ ``gets()`` 和 ``puts()`` 这两个函数称为“按行”读写字符串的一对函数。顾名思义，按行读写就是一行一行的读和写，所谓“行”就是以换行符 ``'\n'`` 为间隔的字符串，中间允许有空格、tab等任何只要不是 ``'\n'`` 的字符。 先看按行输入字符串的函数 ``gets()``\ ，它的函数原型是： .. code-block:: c++ char *gets(char *str); 这个函数从标准输入设备stdin，通常就是键盘，读取一行字符，存放于 ``str`` 并自动在末尾添加空字符 ``'\0'`` 以标志字符串结尾。它的返回值就是 ``str``\ 。这个函数在按行读入字符串之后，会自动把最后的换行符 ``'\n'`` 舍弃掉。 按行输出字符串的函数 ``puts()`` 的函数原型是： .. code-block:: c++ int puts(const char *s); 它将字符串 ``s`` 输出到标准输出设备stdout，通常就是终端窗口。它会自动在字符串输出完成后再额外输出一个换行符 ``'\n'``\ ，这也就是它被称为按行输出函数的原因。 下面这个简单的程序是一个复读机程序，它可以不断地复制你输入的每一行文字，直到遇到一个空行（只含一个换行符的行）： .. code-block:: c++ #include #include int main() { char s[80]; while (strlen(gets(s))) puts(s); return 0; } 看上去很好用，对不对？在过去的好时光里，\ ``gets()`` 和 ``puts()`` 是非常好用深受程序员欢迎的一对按行读写字符串的函数。然而现在C++却强烈建议不要使用这一对函数，如果编译上面这个小程序，会得到这样一句警告： ``warning: this program uses gets(), which is unsafe.``\ 。 意思是：这个程序使用了不安全的 ``gets()`` 函数。更有甚者，有些环境（例如苹果的MacOS）下编译时不会发出这条警告，而是在运行程序的时候才会出现。这样搞程序就不可能通过测试了。而且，虽然现在算法竞赛使用的C++98标准还可以使用这一对函数，但从C++11开始干脆就已经从 ``cstdio`` 库中删除了这一对函数。 为什么会这样呢？如果你对C-string处理非常熟悉，或者对编程时的常见bug非常熟悉的话，可能已经猜到了原因：\ ``gets()`` 函数对读入的字符串长度没有限制！它会傻傻地一直读直到遇见第一个换行符为止，并把所有读入的字符都存放到参数 ``char *str`` 所指向的内存里，不管是不是超限。这个漏洞已经多次被黑客利用来植入病毒、蠕虫等有害代码。所以，我们不要使用这对函数，这里对它们进行介绍只是为了认识一下它们，毕竟还有不少地方会遇到它们，见面能看懂就可以了。 .. warning:: 任何时候不要在你的程序中使用 ``gets()`` 和与之配套的 ``puts()`` 函数。如果程序需要按行读写字符串，那么使用下面介绍的这一对 ``fgets()`` 和 ``fputs()`` 函数。 3、\ ``fgets()`` 和 ``fputs()`` 这一对函数是用来替代前面所述的不安全的 ``gets()`` 和 ``puts()`` 的。它们的功能同样是按行读写字符串，但和前面那一对函数有所不同。 按行读取字符串函数： .. code-block:: c++ char *fgets(char *str, int size, FILE *stream); 现在这个函数有三个参数，第一个参数 ``str`` 指向要读入的字符串；第二个参数 ``size`` 是读字符量的上限，每次读取最多读 ``size-1`` 个字符，因为后面还要有一个位置放结尾空字符；第三个参数 ``stream`` 是输入设备，如果是标准输入设备键盘就直接写stdin，如果是从某个文件读入那么就是这个文件的指针（打开文件时返回的指针，很多教科书上管这个东西叫文件的\ :strong:`句柄`\ ）。 与之配套的按行输出字符串函数是： .. code-block:: c++ int fputs(const char *s, FILE *stream); 这个函数现在除了要输出的字符串 ``s`` 以外也多了一个 ``stream`` 参数，猜猜也知道这是表示输出设备的参数，如果是标准输出设备终端窗口就直接写stdout，如果是写入到某个文件那么就是这个文件的句柄。 ``fputs`` 函数不像它的前任 ``puts()`` 函数那样会在输出字符串之后自动添加一个换行。\ ``puts()`` 会这么做是因为它是和 ``gets()`` 配套使用的，由于 ``gets()`` 函数在读入完成后会自动删除行末的换行符，所以 ``puts()`` 觉得它有责任添加回去。但是 ``fputs()`` 函数是和 ``fgets()`` 配套的，\ ``fgets()`` 在输入完成后并不会删除行尾的换行符！如果字符串末尾是一个换行符，那么这个换行符会被保留在字符串里面！所以 ``fputs()`` 就觉得自己没必要画蛇添足去加一个换行。 现在我们可以把上面这个复读机程序改写为安全的版本了： .. code-block:: c++ #include int main() { char s[80]; while (fgets(s, 80, stdin)[0] != '\n') // size=数组长度80，无需减1，但每次最多读79个字符 fputs(s, stdout); return 0; } ``fgets()`` 读入的字符串，末尾很可能是一个换行符。如果我们认为换行符不是我们要的字符串的一部分，那么就需要自己编写代码来删除这个可能存在的 ``'\n'``\ ，代码如下： .. code-block:: c++ int last = strlen(s) - 1; if (s[last] == '\n') str[last] = '\0'; 4、\ ``getchar()`` 和 ``putchar()`` 这一对函数是用来输入和输出单个字符的。请注意是单个字符，而不是字符串，它们的参数和返回值是 ``int``\ ： .. code-block:: c++ int getchar(); int putchar(int c); ``getchar()`` 函数从标准输入设备读入一个单个的字符。这个函数没有参数，返回类型是 ``int``\ 。实际上，正常情况下返回的 ``int`` 型数值其实是一个 ``char``\ ，取值范围是0到255，所以正常情况下可以安全地将其赋值给一个 ``char`` 型变量，例如： .. code-block:: c++ char ch = getchar(); // 从标准输入设备读取一个字符给 ch 那么为什么这个库函数的设计者要把返回类型定义为 ``int`` 呢？这是为了应对“不正常”的情况，通常是指读到输入结束了，例如键盘上输入了Ctrl-D（Windows系统下是Ctrl-Z）或者是读到输入文件的末尾了，也有可能是读入过程出错了。这种时候需要返回一个标志性的数值来表示读入出现了异常，这个标志显然不能和任何ASCII字符相同。在 ``cstdio`` 库中定义了这样一个标志 ``EOF``\ ，其值通常是-1，这就在 ``int`` 型的范围之内了。所以如果 ``getchar()`` 返回了 ``EOF``\ ，那么表示输入该结束了。 与之相对应的是单个字符输出函数 ``putchar()``\ 。这个函数以ASCII字符的方式输出它的参数 ``c`` 到标准输出设备，正常情况下仍然返回 ``c`` 的值。异常情况，通常是输出设备故障等出错情况时，返回 ``EOF``\ 。 比如下面这个程序，就是用这一对函数实现的另一个版本的复读机程序： .. code-block:: c++ // copy.cpp - a very simple but very powerful tool #include int main() { int ch; while ((ch = getchar()) != EOF) putchar(ch); return 0; } 这个复读机程序比前面两个版本都更加完善。前两个版本的复读机都以遇到一个空行为输入结束标志，所以如果输入中确实需要有空行就不行了。但是这个版本通过判断是否读到 ``EOF`` 来判断输入是否结束，所以可以适用于任何格式的ASCII文本输入。把这个程序编译一下，可执行文件命名为copy，结合输入输出重定向功能，它可以有以下用途： * ``./copy``\ ：按行复读从键盘输入的任何文本，在Linux/MacOS/Unix系统下，输入Ctrl-D表示输入结束，在Windows系统下则是输入Ctrl-Z表示输入结束。 * ``./copy < aaa.txt``\ ：在终端屏幕上输出文本文件aaa.txt的内容。 * ``./copy > bbb.txt``\ ：通过键盘输入多行文本，将输入的内容照原样保存到文本文件bbb.txt中，同样地以Ctrl-D或Ctrl-Z来结束输入。这就是一个最最简单的文本编辑器了。 * ``./copy < ccc > ddd``\ ：复制文件ccc为ddd，这就是一个文件复制工具，神奇的是它不仅限于能复制ASCII字符构成的文本文件，而是能复制任何文件！ .. hint:: ``getchar()`` 和 ``putchar()`` 是C++语言中速度最快的输入输出函数，比 ``cin >>`` 和 ``cout <<`` 快，比 ``scanf()`` 和 ``printf()`` 快，比任何其他输入输出方法都要快！如果遇到单个字符输入输出的情况，请务必使用它们。 由于 ``getchar()`` 的速度实在太快，所以有人很喜欢抛弃其他输入方法，基于 ``getchar()`` 来自行编写一些快速的输入函数，称之为“快读”。例如下面这个程序利用一个自定义的整数快读函数 ``readint()`` 来连续读取5个整数，然后用反转顺序依次输出： .. literalinclude:: ../../codes/233_readint.cpp :language: c++ 这个快读函数的强大之处是它可以剔除所有不构成一个 ``int`` 型数值的字符，所以我们的输入甚至可以是这样的： .. code-block:: none 1 abc22efg333 hello +4444 world-55555 上面的输入，程序会从这一串杂乱的文本中挑出五个合法整数，然后得到下面的输出： .. code-block:: none -55555 4444 333 22 1 .. warning:: 然而在实际解决问题时，输入的格式是多种多样的。一味迷信快读，需要给每一个不同的程序编写各自不同的快读函数，这会增加许多代码量，更有可能引入意想不到的bug。例如我们前面这个 ``readint()`` 函数，如果遇到输入中有连续的正负号，\ ``+++12++123`` 或者 ``----`` 这样的情况时，就会出问题。 而且在这个世界上几乎没有用 ``scanf()`` 输入数据会TLE的算法编程题。偶尔遇到用 ``cin >>`` 会出问题的题目，改成 ``scanf()`` 一定没问题。 所以，编写快读函数可以作为锻炼编程技巧、探究输入输出细节知识的一种练习，但是绝不推荐在实际解题时使用！ 5、\ ``fgetc()`` 和 ``fputc()`` 最后是一对最不常用的单字符输入输出函数，它们用来从文件中读入单个字符和将单个字符写入文件中去： .. code-block:: c++ int fgetc(FILE *stream); int fputc(int c, FILE *stream); 它们和 ``getchar()``\ 、\ ``putchar()`` 的区别就是多了一个文件句柄参数，表示要从那个文件里读、要向哪个文件里写，其他都是一模一样的。实际上 ``getchar()`` 和 ``putchar()`` 就是用它们俩来实现的，因为标准输入设备stdin和标准输出设备stdout本身也是文件句柄。 .. code-block:: c++ int ch; ch = fgetc(stdin); // 这其实就是 ch = getchar(); fputc(ch, stdout); // 这其实就是 putchar(ch);