C 进阶 — 字符函数和字符串函数 ( 一 )

C 进阶 — 字符函数和字符串函数 ( 一 )

主要内容

重点复习处理字符和字符串的库函数的使用和注意事项

求字符串长度

• strlen

长度不受限制的字符串函数

• strcpy
• strcat
• strcmp

长度受限制的字符串函数介绍

• strncpy
• strncat
• strncmp

字符串查找

• strstr
• strtok

错误信息报告

• strerror

字符操作

内存操作函数

• memcpy
• memmove
• memset
• memcmp

C 中对字符和字符串的处理很频繁，但 C 本身没有字符串类型，字符串通常放在

常量字符串 或者 字符数组 中

字符串常量 适用于那些对它不做修改的字符串函数

C字符串处理函数的源代码

一 函数介绍

1.1 strlen

size_t strlen ( const char * str );
//typedef unsigned __int64 size_t;

1. 字符串以 \0 作为结束标志，strlen 函数返回在字符串中 \0 前面出现的字符个数（不包含 \0 )

2. 参数指向的字符串必须以 \0 结束

3. 注意函数的返回值为 size_t，是无符号的

//示例演示, 下面的代码有什么问题
#include <stdio.h>
int main()
{
    const char*str1 = "abcdef";
    const char*str2 = "bbb";
    //相当于 (size_t) 3 - (size_t) 6
    //运算的返回值肯定大于 0
    if(strlen(str2) - strlen(str1)  > 0) 
        printf("str2 > str1\n"); 
    else
        printf("srt1 > str2\n");
    return 0;
}
//首先 CPU 没有减法操作，需要把减法转为加法运算, 3 - 6 转为加法运算. 那么 -6 对应的无符号数是 
// -1 对应的无符号数(unsigned __int64 size_t)是 0x FFFFFFFF FFFFFFFF, 因此 -6 对应的无符号数是 0x FFFFFFFF FFFFFFFA  
// 因此 (size_t) 3 - (size_t) 6 = 0x FFFFFFFF FFFFFFFD
// 小端系统因此在内存中的存储内容为 FDFFFFFFFF FFFFFF, 如下图

模拟 strlen 实现

size_t strlen(const char* str)
{
	size_t count = 0;
	assert(str);
	while (*str++ != '\0')
		++count;
	return count;
}

1.2 strcpy

char* strcpy(char * destination, const char * source);

Copies the C string pointed by source into the array pointed by destination, including the terminating null character (and stopping at that point)

1. 源字符串必须以 \0 结束
2. 会将源字符串中的 \0 拷贝到目标空间
3. 目标空间必须足够大，以确保能存放源字符串
4. 目标空间必须可变

/* strcpy example */
#include <stdio.h>
#include <string.h>

int main ()
{
  char str1[]="Sample string";
  char str2[40];
  char str3[40];
  strcpy (str2,str1);
  strcpy (str3,"copy successful");
  printf ("str1: %s\nstr2: %s\nstr3: %s\n",str1,str2,str3);
  return 0;
}

模拟 strcpy 实现

char* strcpy(char* destination, const char* source)
{
	assert(destination && source);
	char* ptr = destination;
	while (*ptr++ = *source++)
		;
	return source;
}

*ptr++ = *source++ 操作符顺序 * 优先级最高，其次为赋值操作符，最后为后置自增操作符。因此表达式中指针先和解引用操作符结合，然后和赋值操作符结合完成赋值操作，最后与自增操作符结合完成指针偏移

1.3 strcat

char * strcat ( char * destination, const char * source );

Appends a copy of the source string to the destination string. The terminating null character in destination is overwritten by the first character of source, and a null-character is included at the end of the new string formed by the concatenation of both in destination

将源字符串的副本附加到目标字符串。destination 中终止的 null 字符将被 source 的第一个字符覆盖，并且 null 字符包含在 destination 中由两者串联形成的新字符串的末尾

1. 源字符串必须以 \0 结束
2. 目标空间必须有足够的大，能容纳下源字符串的内容
3. 目标空间必须可修改

/* strcat example */
#include <stdio.h>
#include <string.h>

int main ()
{
    char str[80];
    strcpy (str,"these ");
    strcat (str,"strings ");
    strcat (str,"are ");
    strcat (str,"concatenated.");
    puts (str);
    return 0;
}

error C4996: ‘strcpy’: This function or variable may be unsafe. Consider using strcpy_s instead

在预处理定义中添加：_CRT_SECURE_NO_WARNINGS

字符串自己给自己追加会怎么样？

在预期程序结果时，首先要把对应的实现写出来

模拟 strcat 实现

char* strcat(char* destination, const char* source)
{
	assert(destination && source);
	char* ptr = destination;
	while (*ptr != '\0')
		ptr++;
	while (*ptr++ = *source++)
		;
	return destination;
}

注意这里第一个 while 循环不能直接写成 *ptr++ != '\0' ，否则 ptr 会移动到 '\0' 的后一个位置

strcat在追加自身时，程序会挂掉，实际上追加自身会造成死循环。指针 dest 找到\0 后停止，然后 src 用首元素覆盖，导致源数据被更改（自身的 \0 被覆盖掉了），所以导致死循环（最后内存访问越界）

结论 strcat不能追加自身，否则会造成死循环

1.4 strcmp

int strcmp ( const char * str1, const char * str2 );

This function starts comparing the first character of each string. If they are equal to each other, it continues with the following pairs until the characters differ or until a terminating null-character is reached.

标准规定：

1. 第一个字符串大于第二个字符串，则返回大于 0 的数字
2. 第一个字符串等于第二个字符串，则返回 0
3. 第一个字符串小于第二个字符串，则返回小于 0 的数字

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

int main ()
{
  char key[] = "apple";
  char buffer[80];
  do {
     printf ("Guess my favorite fruit? ");
     fflush (stdout);
     scanf ("%79s",buffer);
  } while (strcmp (key,buffer) != 0);
  puts ("Correct answer!");
  return 0;
}

fflush(stdout) 是 C 中的一个函数调用，用于清空（或刷新）输出缓冲区。具体来说，这个调用确保所有之前写入 stdout（标准输出，通常是终端或控制台）但尚未实际发送到目标设备的数据都被立即发送

%79s 是 scanf 函数的一个格式控制字符串，用于从输入流中读取字符串。这里的数字 79 表示要读取的最大字符数

模拟 strcmp 实现

int strcmp(const char* str1, const char* str2)
{
	assert(str1 && str2);
	while (*str1 && *str2 && (*str1 == *str2))
		str1++, str2++;
	//两个字符串此位置不同, 或是有一方提前到达字符串末尾
	return *str1 - *str2;
}

结尾的 *str1 - *str2 很巧妙，因为 char 字符在内存存储的是 ASCII 码数值，因此可以用整数减法运算符来判断两个字符串哪个大

1.5 strncpy

char * strncpy ( char * destination, const char * source, size_t num );

Copies the first num characters of source to destination. If the end of the source C string (which is signaled by a null-character) is found before num characters have been copied, destination is padded with zeros until a total of num characters have been written to it.

将源前 number 个字符复制到目标。如果在复制 num 个字符之前找到源 C 字符串的末尾（由 null 字符表示），则目标将填充零，直到写入总数 num 个字符为止

No null-character is implicitly appended at the end of destination if source is longer than num. Thus, in this case, destination shall not be considered a null terminated C string (reading it as such would overflow).

如果 source 长于 num，则不会在 destination 的末尾隐式附加 null 字符。因此，在这种情况下， destination 不应被视为以 null 结尾的 C 字符串（因此读取它会溢出）

1. 拷贝 num 个字符从源字符串到目标空间
2. 如果源字符串的长度小于 num，则拷贝完源字符串之后，在目标的后边追加 0，直到 num 个

/* strncpy example */
#include <stdio.h>
#include <string.h>

int main ()
{
  char str1[]= "To be or not to be";
  char str2[40];
  char str3[40];

  /* copy to sized buffer (overflow safe): */
  strncpy ( str2, str1, sizeof(str2) );
  //当拷贝的 num 大于源字符串长度, 不用担心, 会自动补 '\0'

  /* partial copy (only 5 chars): */
  strncpy ( str3, str2, 5 );
  str3[5] = '\0';   /* null character manually added */
  //需要手动补 '\0', 当拷贝的 num 小于源字符串长度
    
  puts (str1);
  puts (str2);
  puts (str3);

  return 0;
}

模拟 strncpy 实现

char* strncpy(char* destination, const char* source, size_t num)
{
	assert(destination && source);
	char* ptr = destination;
	//拷贝的条目数够了或到达 source 末尾
	while (num && (*ptr = *source))
		num--, ptr++, source++;
	while (num)
		num--, *ptr++ = 0;
	return destination;
}

注意，在第一个 while 循环内不能使用 *ptr++ = *source++，这样当到达 source 末尾时，num 的数值没有改变，而 ptr 的指针会往后偏移一个单位，最终导致在第二个 while 循环内 *ptr 内存访问越界

1.6 strncat

char * strncat ( char * destination, const char * source, size_t num );

Appends the first num characters of source to destination, plus a terminating null-character

将 source 的前 num 个字符附加到 destination，外加一个终止 null 字符

If the length of the C string in source is less than num, only the content up to the terminating null-character is copied.

如果 source 中 C 字符串的长度小于 num，则仅复制终止 null 字符之前的内容

/* strncat example */
#include <stdio.h>
#include <string.h>

int main ()
{
  char str1[20];
  char str2[20];
  strcpy (str1,"To be ");
  strcpy (str2,"or not to be");
  strncat (str1, str2, 6);
  puts (str1);
  return 0;
}

模拟 strncat 实现

char* my_strncat(char* destination, const char* source, size_t num) 
{
	assert(destination && source);
	char* ptr = destination;

	while (*ptr)
		ptr++;

	/*
		source 小于或等于 num, 拷贝到 source 最后一个元素, 末尾补 null
		source 大于 num, 拷贝 source 前 num 个元素, 末尾补 null
	*/
	while (num-- && (*ptr = *source))
		ptr++, source++;
	*ptr = 0;
	return destination;
}

1.7 strncmp

比较到出现另个字符不一样或者一个字符串结束或者 num 个字符全部比较完

int strncmp ( const char * str1, const char * str2, size_t num );

Compares up to num characters of the C string str1 to those of the C string str2.
比较 C 字符串 str1 的字符数与 C 字符串 str2 的字符数

This function starts comparing the first character of each string. If they are equal to each other, it continues with the following pairs until the characters differ, until a terminating null-character is reached, or until num characters match in both strings, whichever happens first.

此函数开始比较每个字符串的第一个字符。如果它们彼此相等，则继续处理以下对，直到字符不同，直到到达终止 null 字符，或者直到两个字符串中的 num 个字符匹配，以先发生者为准

/* strncmp example */
#include <stdio.h>
#include <string.h>
int main ()
{
    char str[][5] = { "R2D2" , "C3PO" , "R2A6" };
    int n;
    puts ("Looking for R2 astromech droids...");
    for (n=0 ; n<3 ; n++)
        if (strncmp (str[n],"R2xx",2) == 0)
        {
            printf ("found %s\n",str[n]);
        }
    return 0;
}

模拟 strncmp 实现

int strncmp(const char* str1, const char* str2, size_t num)
{
	assert(str1 && str2);
	while (num && *str1 && *str2 && (*str1 == *str2))
		num--, str1++, str2++;
	return num == 0 ? 0 : *str1 - *str2;
}

1.8 strstr

查找子字符串

char * strstr ( const char *str1, const char * str2);

Returns a pointer to the first occurrence of str2 in str1, or a null pointer if str2 is not part of str1
返回指向 str1 中第一次出现的 str2 的指针，如果 str2 不是 str1 的一部分，则返回 null 指针

The matching process does not include the terminating null-characters, but it stops there
匹配过程不包括终止 null 字符，但会在此处停止

/* strstr example */
#include <stdio.h>
#include <string.h>
int main ()
{
  char str[] ="This is a simple string";
  char * pch;
  pch = strstr (str,"simple");
  strncpy (pch,"sample",6);
  puts (str);
  return 0;
}

模拟 strstr 实现

暴力匹配实现 查找子字符串，参考库函数 strstr 实现方式

库函数 strstr 的基本思路
	用两层循环来实现，外层循环用一个循环变量 s 遍历主字符串 str1, 每当在主字符串中找到子字符串的首元素就进入第二层循环进行两个字符串的匹配. 若匹配失败, 指针 s 回溯到匹配的起始位置继续寻找下一个子字符串首字符, 同时 t 指针也回到子字符串的首地址, 重复上述步骤
	内层循环以两个字符串的终止符或不相等的对应字符为结束标志
	匹配成功的标志是内层循环维护子串 str2 的指针指向子串 str2 的终止符

char* strstr(const char* str1, const char* str2) 
{
	assert(str1 && str2);
	const char* s = str1;
	const char* t = str2;

   /*
	*	外层循环不断移动 str1 指针, 遍历 str1 字符串
	* 
	*	到 str1 末尾还没有查找到子字符串, 则查找子串失败
	*	内层匹配失败, 向前移动 str1 指向位置
	*/
	for (;*str1;++str1)		
	{
	    /*
			内层循环匹配判断, 当前 str1 位置是否存在 str2 子串
			s = str1, t = str2 指向当前 str1 和 str2 的位置
			
			*s && (*s == *t)   内层循环结束条件是任意子符串结束, 或不匹配. 因 *s 不为 \0 , 故 *t 为 \0 时循环必结束, 所以可省略

			s++, t++ 移动两指针比较下一位置
		*/
		for (s = str1, t = str2; *s && (*s == *t); s++, t++)
			;

		/* 比较至 str2 末尾, 则匹配结束.当前 str1 位置存在 str2 子串 */
		if (!*t) return str1;
	}
	return NULL;
}

KMP 算法

参考资料，KMP算法–子串查找问题

在暴力匹配算法中，每次主串和模式串匹配失败后， 维护主串和模式串的指针都要回退到匹配的起始位置,这样的处理导致查找效率十分低下。

KMP 算法在主串和模式串匹配失败时，会利用匹配过程中已经成功匹配的部分字符(上图中绿色的部分)的相关信息(字符串最大相等前后缀长度)，让维护模式串的指针回退到合适的位置而维护主串的指针不进行回退操作，继续向后匹配。

kmp 算法中维护主串的指针只递增不回退，从而使查找的时间复杂度降为线性复杂度 (此后统一称待查找的子串为模式串)

视频讲解 KMP 算法

关键概念一 字符串的前后缀

字符串的前缀：假设一个字符串的长度为 n，从该字符串的第 1 个字符到第 i 个字符(其中 1 <= i < n ) 构成的子串称为该字符串的前缀

字符串的后缀：假设一个字符串的长度为 n，从该字符串的第 j 个字符到第 n 个字符 (其中 n => j > 1 ) 构成的子串称为该字符串的后缀

关于前后缀定义需要注意一下两点：

1. 一个字符串的前后缀不包含该字符串本身（没有意义）
2. 字符串的前缀和后缀都是从左向右读取的

关键概念二 字符串最长相等前后缀长度

该字符串最长相等前后缀长度为 2

该字符串最长相等前后缀长度为 0

关键概念三 NEXT 数组

假设现在有一个模式字符串(待查找的字符串)：ABABA.

则该模式子串有 4 个子串分别为

每个子串都有一个自身的最长相等前后缀长度 (注意由于单个字符没有前后缀因此默认其最长相等前后缀长度为 0)

将每个子串的最长相等前后缀长度存入一个命名为 Next 的数组中

得到对应结果如下

NEXT 数组在算法中的应用和原理

资源参考上述视频链接

kmp 算法会根据已完成匹配的子串(比如图中模式串的 0 到 3 的子串) 的最长相等前后缀长度(记录在 Next 数组中的对应位置)，保持维护主串的指针位置不变去调整维护子串的指针位置

对于 A 和 C 比较时发现不匹配，这时算法会去查 C 的上一个元素对应的 NEXT 数组（值为 2），然后让子串从 首元素跳过 2 个元素，即模式串指向第二个 A 的位置。之后主串的 A 会再次和子串的第二个 A 进行比较

算法说明（关于子串可以跳过前两个元素），首先 NEXT 数组记录的是每个元素的最长相等前后缀，当 NEXT 值不为 0 时，在子串必然有与之可匹配的前缀。那么此时主串上可以匹配的部分就可以看做子串的后缀，相当于是拿最长相等的后缀和子串最长相等前缀匹配（当然相等），故可以跳过 NEXT 数值个元素

上述描述的是子串中存在最长相等前后缀的场景，对于不存在（都是 0）最长相等前后缀的场景，更容易理解。主串当前元素直接和首元素比较即可（NEXT 数组都是 0）

NEXT 数组的构建

同样也是递推的方式求解，它的巧妙在于不断利用已掌握的信息来避免重复的计算

假设已知当前的最长相等前后缀，长度为 2，接下来分两种情况讨论

如果下一个字符依然相同，很明显它就等于之前的最长相等前后缀 + 1

但如果下一个字符不同

即 ABA 无法与下个字符构成相等前后缀，那就看下有没有更短的相等前后缀。显然 AB 是可以的。这一步其实和之前主串匹配类似，因为之前的比较信息，可以知道 前缀 ABAC 和 ABAB 在 ABA 是相同的。那么是不是对于 B 点的最长相等前后缀在已知和 C 不匹配时，就等同于把 C 位置上的值替换为 B，求最长相等前后缀

也就是 ABAB 在 B 的位置寻找最长相等前后缀，对于 B 的左边是已经比较过的。因为一切回到了原点，因为第二个 A 位置是 1，所以直接比较 下一个位置即 B 和 B 进行比较，匹配成功，所以最终 B 的 NEXT 值为 2

模拟 strstr（KMP 实现）

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

#define kmpLen 100
 
char* kmpstrstr(const char* str1, const char* str2)
{
    assert(str1 && str2);
    
	if (!str2[0]) return str1;
    
    //构建 Next 数组                 
	int next[kmpLen] = { 0 };
	int i = 1, prefix = 0;     
    while (str2[i])
    {
        /*
		 	prefix 除了作为 NEXT 结果, 还有个作用是作为比较前缀
		 	的下标
	
			前缀相等的比较过程中, 有个位置不匹配时
			prefix - 1 表示在前缀 ABA 中找最长相等前后缀
			
			prefix = next[prefix - 1]; 表示等同于把 C 位置上
			的值替换为 B，求最长相等前后缀
		*/
       while (prefix && str2[i] != str2[prefix])
			prefix = next[prefix - 1];
        
        /*
			已知当前的最长相等前后缀,下一个字符依然相同, 
			很明显它就等于之前的最长相等前后缀 + 1
		*/
        if (str2[i] == str2[prefix])
			++prefix;
		next[i] = prefix;
		++i;          
    }   
    
    //利用 Next 数组完成模式串查找
    i = 0;   
    prefix = 0;
    while (str1[i])
    {
        /* 
        	前面匹配, 但当前不匹配
        	使用 NEXT 使子串回退, 继续比较直至到子串首元素
    	*/
        while (prefix && str1[i] != str2[prefix])
            prefix = next[prefix - 1];

        //当前匹配
        if (str1[i] == str2[prefix])
            ++prefix;
        //前面不匹配, 当前也不匹配
        ++i;
        
        //结束循环条件
        if (!str2[prefix])
			return (char*)(str1 +i - prefix);
    }
	return NULL;
}