第8章 字符串

1. 字符串的深入理解

1.1 字符串的基本概念

在 C 语言中，字符串是由零个或多个字符组成的序列，以空字符 '\0' 结尾。空字符是一个值为 0 的字符，用于标记字符串的结束。

1.1.1 字符串的内存表示

字符串在内存中是连续存储的字符序列，最后跟着一个空字符。

1
2
3
+---+---+---+---+---+---+
| H | e | l | l | o | \0|
+---+---+---+---+---+---+

内存布局详解：

  1. 字符串字面量：

    • 存储在只读数据段（.rodata section）
    • 编译时确定大小和内容
    • 多个相同的字符串字面量可能共享同一个内存位置（字符串池化）
    • 尝试修改会导致未定义行为（通常是段错误）
    • 硬件影响：只读数据段通常被映射到物理内存的只读区域，受 MMU 保护
    • 编译器优化：GCC 的 -fmerge-constants 选项控制字符串池化行为

  2. 字符数组：

    • 局部数组：存储在栈中，遵循栈帧布局规则
    • 全局/静态数组：存储在数据段（.data section），初始化时为 0
    • 动态数组：存储在堆中，由内存分配器管理
    • 内容可以修改（如果不是 const 修饰）
    • 栈帧布局：局部字符数组作为函数栈帧的一部分，遵循栈增长方向（通常向下）

  3. 指针与字符串：

    • 指向字符串字面量的指针：指向只读数据段，应声明为 const char *
    • 指向字符数组的指针：指向栈或堆，类型为 char *
    • 指针本身存储在栈中（局部变量）或数据段（全局变量）
    • 指针算术：支持 ++、--、+n 等操作，基于字符大小（1字节）

内存模型深度分析：

  • 代码段：存储可执行指令，通常是只读的，权限为 r-x
  • 只读数据段：存储字符串字面量、const 变量等，权限为 r–
  • 数据段：存储已初始化的全局和静态变量，权限为 rw-
  • BSS 段：存储未初始化的全局和静态变量，运行时初始化为 0，权限为 rw-
  • 栈：存储局部变量、函数参数、返回地址等，自动管理，权限为 rw-
  • 堆：存储动态分配的内存，手动管理，权限为 rw-

字符串表示的本质：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 字符串字面量
char *str1 = "Hello";
// str1 是一个指针，存储在栈中，指向只读数据段中的 "Hello\0"

// 字符数组
char str2[] = "Hello";
// str2 是一个数组，存储在栈中，包含 'H', 'e', 'l', 'l', 'o', '\0'

// 动态分配
char *str3 = (char *)malloc(6);
if (str3) {
    strcpy(str3, "Hello");
    // str3 是一个指针，存储在栈中，指向堆中分配的内存
    free(str3);
}

字符串的类型系统：

  • 字符串字面量的类型是 const char[]（C99 及以后）
  • 字符数组的类型是 char[]
  • 指向字符串的指针类型是 char * 或 const char *
  • 数组名在表达式中会衰减为指向首元素的指针（除了在 sizeof、& 和字符串字面量初始化数组的情况下）
  • 类型安全：使用 const char * 指向字符串字面量可获得编译期类型检查

汇编级实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
; x86 汇编示例
section .rodata
    hello_str: db "Hello", 0  ; 字符串字面量存储在只读数据段

section .text
global _start
_start:
    ; 方法 1: 使用指针指向字符串字面量
    mov eax, hello_str        ; 将字符串地址加载到 eax
    call print_string
    
    ; 方法 2: 使用栈上的字符数组
    sub esp, 6                ; 为字符数组分配空间
    mov dword [esp], 0x6c6c6548  ; 'Hell'
    mov word [esp+4], 0x006f     ; 'o\0'
    mov eax, esp              ; 将栈地址加载到 eax
    call print_string
    add esp, 6                ; 释放栈空间
    
    ; 退出程序
    mov eax, 1
    xor ebx, ebx
    int 0x80

内存模型深度分析：

  • 代码段：存储可执行指令，通常是只读的
  • 只读数据段：存储字符串字面量、const 变量等，只读
  • 数据段：存储已初始化的全局和静态变量，可读写
  • BSS 段：存储未初始化的全局和静态变量，运行时初始化为 0
  • 栈：存储局部变量、函数参数、返回地址等，自动管理
  • 堆：存储动态分配的内存，手动管理

字符串表示的本质：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 字符串字面量
char *str1 = "Hello";
// str1 是一个指针，存储在栈中，指向只读数据段中的 "Hello\0"

// 字符数组
char str2[] = "Hello";
// str2 是一个数组，存储在栈中，包含 'H', 'e', 'l', 'l', 'o', '\0'

// 动态分配
char *str3 = (char *)malloc(6);
if (str3) {
    strcpy(str3, "Hello");
    // str3 是一个指针，存储在栈中，指向堆中分配的内存
    free(str3);
}

字符串的类型系统：

  • 字符串字面量的类型是 const char[]（C99 及以后）
  • 字符数组的类型是 char[]
  • 指向字符串的指针类型是 char * 或 const char *
  • 数组名在表达式中会衰减为指向首元素的指针（除了在 sizeof、& 和字符串字面量初始化数组的情况下）

1.2 字符串的表示

1.2.1 字符数组

字符数组是最常用的字符串表示方式，可以修改其中的字符，具有更高的灵活性和安全性。

字符数组的高级应用：

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
// 声明字符数组
char str[10];  // 未初始化，内容不确定

// 初始化字符数组
char str1[] = "Hello";  // 自动计算大小为 6（包含空字符）
char str2[10] = "World";  // 显式指定大小，剩余空间填充 0
char str3[] = {'H', 'e', 'l', 'l', 'o', '\0'};  // 显式添加空字符
char str4[] = {'H', 'e', 'l', 'l', 'o'};  // 没有空字符，不是字符串

// 变长数组（C99 引入）
size_t length = 10;
char str5[length];  // 运行时确定大小，存储在栈中

// 柔性数组成员（C99 引入）
typedef struct {
    size_t length;
    char data[];  // 柔性数组成员，必须是最后一个成员
} StringBuffer;

// 创建带柔性数组成员的字符串缓冲区
StringBuffer *create_buffer(size_t length) {
    StringBuffer *buf = (StringBuffer *)malloc(sizeof(StringBuffer) + length + 1);
    if (buf) {
        buf->length = length;
        buf->data[0] = '\0';  // 确保字符串以空字符结尾
    }
    return buf;
}

// 静态字符数组的初始化
static char static_str[] = "Static string";  // 存储在数据段

// 全局字符数组的初始化
char global_str[] = "Global string";  // 存储在数据段

字符数组的内存布局：

  • 局部字符数组：存储在栈中，函数返回后自动释放

    • 栈帧布局：位于函数栈帧的局部变量区域，紧邻其他局部变量
    • 内存对齐：通常按照 1 字节对齐（字符大小），但可能受栈对齐规则影响
    • 访问速度：栈内存访问速度快，缓存命中率高

  • 全局字符数组：存储在数据段中，程序运行期间一直存在

    • 内存布局：位于 .data 段，与其他全局变量一起
    • 初始化：编译时初始化，未初始化部分填充 0
    • 访问速度：数据段访问速度接近栈，优于堆

  • 静态字符数组：存储在数据段中，作用域受限但生命周期整个程序

    • 内存布局：与全局变量相同，但作用域受限于声明它的块
    • 初始化：编译时初始化，未初始化部分填充 0

编译器优化策略：

  • 栈帧大小优化：GCC 的 -Os 选项会优化栈帧大小
  • 数组边界检查：GCC 的 -fstack-protector 选项提供栈溢出保护
  • 自动向量化：对于字符数组操作，现代编译器会自动使用 SIMD 指令

1.2.2 字符串字面量

字符串字面量是用双引号括起来的字符序列，存储在只读内存中，不能修改。

字符串字面量的高级特性：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
"Hello, World!"  // 普通字符串字面量
"This is a\nmultiline\nstring"  // 包含转义字符的字符串字面量
"String with\tescape\tcharacters"  // 包含制表符的字符串字面量

// 字符串字面量的连接（编译时）
"Hello, " "World!"  // 等同于 "Hello, World!"

// 原始字符串字面量（C11 引入）
R"(This is a raw string with "quotes" and \backslashes)"  // 保持原样

// 带分隔符的原始字符串字面量
R"delimiter(This is a raw string with "quotes" and \backslashes)delimiter"

// 字符串字面量的长度计算
#define STR_LEN(s) (sizeof(s) - 1)  // 编译时计算字符串字面量长度
char str[] = "Hello";
size_t len = STR_LEN("Hello");  // 编译时计算为 5

字符串字面量的优化：

  • 字符串池化：编译器会将相同的字符串字面量合并为一个，减少内存使用
    • GCC 实现：通过 -fmerge-constants 选项控制，默认开启
    • Clang 实现：类似的常量合并机制
  • 常量折叠：编译时计算字符串连接的结果
  • 只读存储：存储在只读数据段，防止意外修改
    • 内存保护：操作系统通过页表设置只读权限
    • 安全性：防止缓冲区溢出攻击修改常量数据

字符串字面量的内存布局：

1
2
3
4
; x86-64 汇编示例
section .rodata
    hello_str: db "Hello", 0  ; 字符串字面量存储在只读数据段
    world_str: db "World", 0  ; 另一个字符串字面量

1.2.3 指针和字符串

可以使用指针来指向字符串，这种方式更加灵活，适用于动态字符串处理。

指针与字符串的高级应用：

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
// 指向字符串字面量的指针（推荐使用 const）
const char *str1 = "Hello";  // 指向只读数据段

// 指向字符数组的指针
char str2[] = "World";
char *str3 = str2;  // 指向栈中的字符数组

// 动态分配的字符串
char *str4 = (char *)malloc(10 * sizeof(char));
if (str4 != NULL) {
    strcpy(str4, "Hello");
    // 可以修改内容
    str4[0] = 'h';
    printf("%s\n", str4);  // 输出 "hello"
    free(str4);
}

// 字符串指针数组
const char *messages[] = {
    "Error: Invalid input",
    "Warning: Buffer overflow",
    "Info: Operation completed"
};

// 二维字符串数组
char board[3][4] = {
    "XOX",
    "OXO",
    "XOX"
};

// 函数参数中的字符串指针
void print_string(const char *str) {
    printf("%s\n", str);
}

// 返回字符串指针的函数
const char *get_status_message(int status) {
    static const char *messages[] = {
        "Success",
        "Warning",
        "Error"
    };
    return messages[status % 3];
}

指针算术与字符串：

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
const char *str = "Hello, World!";

// 指针算术
const char *ptr = str;
while (*ptr != '\0') {
    printf("%c", *ptr);
    ptr++;  // 指针递增，指向下一个字符
}
printf("\n");

// 计算字符串长度（模拟 strlen）
size_t my_strlen(const char *s) {
    const char *p = s;
    while (*p != '\0') {
        p++;
    }
    return p - s;  // 指针减法，计算字符数
}

// 指针减法的底层原理
// 两个指针相减得到它们之间的元素个数，单位是 sizeof(char) = 1

// 指针比较
if (ptr1 < ptr2) {
    // ptr1 指向的内存地址在 ptr2 之前
}

字符串表示的性能比较：

表示方式内存位置可修改性分配开销访问速度适用场景
字符串字面量只读数据段不可修改无快固定字符串，常量
栈上字符数组栈可修改无最快临时字符串，小容量
堆上字符数组堆可修改有快动态字符串，大容量
指针指向字符串取决于指向的位置取决于指向的位置无（指针本身）快字符串处理，传递参数

性能优化策略：

  1. 小字符串优化：对于短字符串，优先使用栈上字符数组
  2. 内存池：对于频繁分配的字符串，使用内存池减少堆分配开销
  3. 字符串视图：使用指针和长度表示字符串，避免不必要的复制
  4. SIMD 优化：对于字符串操作，利用 SIMD 指令加速处理

标准合规性：

  • C89：支持基本的字符串字面量和字符数组
  • C99：引入变长数组和柔性数组成员
  • C11：引入原始字符串字面量
  • C17：无新增字符串相关特性
  • 注意：修改字符串字面量的行为在所有 C 标准中都是未定义的

1.3 字符串的特性

1.3.1 核心特性

  • 以空字符结尾 - 字符串必须以 '\0' 结尾，否则不是有效的 C 字符串

    • 底层原理：空字符是值为 0 的字节，用于标记字符串结束
    • 实现细节：所有字符串操作函数都依赖空字符作为结束标志
    • 安全隐患：缺少空字符会导致缓冲区溢出
    • 内存表示：空字符在内存中占用 1 字节，值为 0x00
    • 硬件影响：现代 CPU 对 0 值检测有专门优化，加速字符串结束判断

  • 连续存储 - 字符串的字符在内存中连续存储，便于随机访问

    • 硬件影响：连续存储利用了 CPU 缓存的空间局部性
    • 访问模式：支持 O(1) 时间复杂度的随机访问
    • 内存布局：连续的内存块，无间隙存储
    • 缓存优化：连续存储提高了 L1/L2 缓存命中率
    • 预取机制：现代 CPU 会自动预取连续存储的数据

  • 长度可变 - 字符串的长度由空字符的位置决定，运行时可动态调整

    • 实现方式：通过修改空字符位置或重新分配内存
    • 动态调整：使用 realloc 实现容量扩展
    • 空间管理：需要平衡预分配空间和动态扩展的开销
    • 扩容策略：通常采用 2 倍扩容策略，平衡时间和空间复杂度
    • 内存碎片：频繁的字符串扩容可能导致内存碎片

  • 字符编码 - 字符串中的字符使用 ASCII、UTF-8 或其他编码方案

    • 编码选择：取决于应用场景和国际化需求
    • 性能影响：不同编码的处理复杂度和空间开销不同
    • 兼容性：UTF-8 是最广泛使用的编码方案
    • 硬件支持：某些 CPU 提供专门的字符编码转换指令
    • SIMD 优化：现代 CPU 的 SIMD 指令集支持快速编码转换

1.3.2 字符串的哈希与散列

字符串哈希函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
// FNV-1a 哈希函数（64位）
uint64_t fnv1a_hash(const char *str) {
    const uint64_t FNV_OFFSET = 14695981039346656037ULL;
    const uint64_t FNV_PRIME = 1099511628211ULL;
    
    uint64_t hash = FNV_OFFSET;
    while (*str) {
        hash ^= (uint64_t)*str++;
        hash *= FNV_PRIME;
    }
    return hash;
}

// DJB2 哈希函数
uint32_t djb2_hash(const char *str) {
    uint32_t hash = 5381;
    int c;
    
    while ((c = *str++)) {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    
    return hash;
}

哈希表实现：

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
66
67
68
69
// 简单的字符串哈希表
#define TABLE_SIZE 1024

typedef struct HashNode {
    char *key;
    void *value;
    struct HashNode *next;
} HashNode;

typedef struct HashTable {
    HashNode *buckets[TABLE_SIZE];
} HashTable;

// 初始化哈希表
void ht_init(HashTable *ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->buckets[i] = NULL;
    }
}

// 插入键值对
void ht_insert(HashTable *ht, const char *key, void *value) {
    uint32_t hash = djb2_hash(key) % TABLE_SIZE;
    
    // 查找是否已存在
    HashNode *current = ht->buckets[hash];
    while (current) {
        if (strcmp(current->key, key) == 0) {
            current->value = value;
            return;
        }
        current = current->next;
    }
    
    // 创建新节点
    HashNode *node = (HashNode *)malloc(sizeof(HashNode));
    node->key = strdup(key);
    node->value = value;
    node->next = ht->buckets[hash];
    ht->buckets[hash] = node;
}

// 查找值
void *ht_find(HashTable *ht, const char *key) {
    uint32_t hash = djb2_hash(key) % TABLE_SIZE;
    
    HashNode *current = ht->buckets[hash];
    while (current) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }
    
    return NULL;
}

// 释放哈希表
void ht_free(HashTable *ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        HashNode *current = ht->buckets[i];
        while (current) {
            HashNode *next = current->next;
            free(current->key);
            free(current);
            current = next;
        }
    }
}

哈希函数性能优化：

  • SIMD 加速：使用 AVX2 指令并行处理多个字符
  • 分支预测：减少哈希计算中的分支操作
  • 缓存优化：提高哈希表的缓存命中率
  • 负载因子：控制哈希表的负载因子，避免链表过长

1.3.3 字符串的内存池

内存池实现：

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
// 字符串内存池
#define POOL_BLOCK_SIZE 4096

typedef struct MemPool {
    char *block;
    size_t offset;
    struct MemPool *next;
} MemPool;

// 创建内存池
MemPool *pool_create(void) {
    MemPool *pool = (MemPool *)malloc(sizeof(MemPool));
    pool->block = (char *)malloc(POOL_BLOCK_SIZE);
    pool->offset = 0;
    pool->next = NULL;
    return pool;
}

// 从内存池分配字符串
char *pool_alloc_str(MemPool *pool, const char *str) {
    size_t len = strlen(str) + 1;
    
    // 检查当前块是否有足够空间
    if (pool->offset + len > POOL_BLOCK_SIZE) {
        // 创建新块
        MemPool *new_pool = (MemPool *)malloc(sizeof(MemPool));
        new_pool->block = (char *)malloc(POOL_BLOCK_SIZE);
        new_pool->offset = 0;
        new_pool->next = pool->next;
        pool->next = new_pool;
        pool = new_pool;
    }
    
    // 分配空间
    char *ptr = pool->block + pool->offset;
    strcpy(ptr, str);
    pool->offset += len;
    
    return ptr;
}

// 释放内存池
void pool_free(MemPool *pool) {
    while (pool) {
        MemPool *next = pool->next;
        free(pool->block);
        free(pool);
        pool = next;
    }
}

内存池优势：

  • 减少内存碎片：批量分配内存，减少小块内存的碎片化
  • 提高分配速度：避免频繁的 malloc/free 调用
  • 降低开销：内存池管理开销低于标准内存分配器
  • 缓存友好：连续分配的内存提高缓存命中率

1.3.4 字符串的 SIMD 优化

SIMD 字符串长度计算：

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 <immintrin.h>

// 使用 AVX2 计算字符串长度
size_t simd_strlen(const char *s) {
    const char *ptr = s;
    
    // 对齐到 32 字节边界
    while ((uintptr_t)ptr % 32 != 0) {
        if (*ptr == '\0') {
            return ptr - s;
        }
        ptr++;
    }
    
    // 使用 AVX2 指令并行处理
    __m256i zero = _mm256_setzero_si256();
    while (1) {
        __m256i vec = _mm256_load_si256((__m256i *)ptr);
        __m256i cmp = _mm256_cmpeq_epi8(vec, zero);
        int mask = _mm256_movemask_epi8(cmp);
        
        if (mask != 0) {
            // 找到空字符
            return ptr - s + __builtin_ctz(mask);
        }
        
        ptr += 32;
    }
}

SIMD 字符串比较：

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
// 使用 AVX2 比较字符串
int simd_strcmp(const char *s1, const char *s2) {
    const char *p1 = s1, *p2 = s2;
    
    // 对齐到 32 字节边界
    while (((uintptr_t)p1 % 32 != 0 || (uintptr_t)p2 % 32 != 0)) {
        if (*p1 != *p2) {
            return *(unsigned char *)p1 - *(unsigned char *)p2;
        }
        if (*p1 == '\0') {
            return 0;
        }
        p1++;
        p2++;
    }
    
    // 使用 AVX2 指令并行处理
    __m256i zero = _mm256_setzero_si256();
    while (1) {
        __m256i vec1 = _mm256_load_si256((__m256i *)p1);
        __m256i vec2 = _mm256_load_si256((__m256i *)p2);
        
        // 检查是否到达字符串末尾
        __m256i cmp1 = _mm256_cmpeq_epi8(vec1, zero);
        int mask1 = _mm256_movemask_epi8(cmp1);
        
        __m256i cmp2 = _mm256_cmpeq_epi8(vec2, zero);
        int mask2 = _mm256_movemask_epi8(cmp2);
        
        // 检查字符是否不同
        __m256i cmp_ne = _mm256_cmpneq_epi8(vec1, vec2);
        int mask_ne = _mm256_movemask_epi8(cmp_ne);
        
        if (mask_ne != 0) {
            // 找到不同字符
            int pos = __builtin_ctz(mask_ne);
            return ((unsigned char *)p1)[pos] - ((unsigned char *)p2)[pos];
        }
        
        if (mask1 != 0 || mask2 != 0) {
            // 到达字符串末尾
            return 0;
        }
        
        p1 += 32;
        p2 += 32;
    }
}

SIMD 优化策略：

  • 数据对齐：确保内存访问对齐到 SIMD 寄存器边界
  • 批量处理：一次处理 16/32/64 字节数据
  • 减少分支：使用掩码操作替代条件分支
  • 缓存预取：使用 _mm_prefetch 提前加载数据

1.3.5 字符串的安全处理

缓冲区溢出防护：

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
// 安全的字符串处理函数
#define MAX_STRLEN 1024

// 安全的字符串复制（带长度检查）
char *safe_strncpy(char *dest, const char *src, size_t dest_size) {
    if (!dest || !src || dest_size == 0) {
        return NULL;
    }
    
    size_t src_len = strnlen(src, dest_size - 1);
    memcpy(dest, src, src_len);
    dest[src_len] = '\0';
    
    return dest;
}

// 安全的字符串拼接（带长度检查）
char *safe_strncat(char *dest, const char *src, size_t dest_size) {
    if (!dest || !src || dest_size == 0) {
        return NULL;
    }
    
    size_t dest_len = strnlen(dest, dest_size - 1);
    if (dest_len >= dest_size - 1) {
        return dest; // 目标缓冲区已满
    }
    
    size_t remaining = dest_size - dest_len - 1;
    size_t src_len = strnlen(src, remaining);
    memcpy(dest + dest_len, src, src_len);
    dest[dest_len + src_len] = '\0';
    
    return dest;
}

// 安全的字符串格式化（带长度检查）
int safe_snprintf(char *dest, size_t dest_size, const char *format, ...) {
    if (!dest || dest_size == 0) {
        return -1;
    }
    
    va_list args;
    va_start(args, format);
    int result = vsnprintf(dest, dest_size, format, args);
    va_end(args);
    
    return result;
}

安全最佳实践：

  • 输入验证：始终验证字符串输入的长度和格式
  • 边界检查：确保所有字符串操作都在缓冲区边界内
  • 使用安全函数：优先使用 strncpy、strncat、snprintf 等安全函数
  • 内存安全：避免使用已释放的字符串指针
  • 编码安全：正确处理多字节字符编码，避免注入攻击

1.3.6 编码系统深度分析

ASCII 编码：

  • 使用 7 位表示 128 个字符
  • 包含控制字符（0-31）、可打印字符（32-126）和 DEL 字符（127）
  • 是其他编码方案的基础
  • 内存表示：每个字符占 1 字节，最高位为 0
  • 硬件兼容性：所有计算机系统都支持 ASCII 编码

扩展 ASCII 编码：

  • 使用 8 位表示 256 个字符
  • 不同国家和地区有不同的扩展方案（如 ISO-8859-1、Windows-1252）
  • 存在编码冲突问题
  • 内存表示：每个字符占 1 字节，最高位可用于表示扩展字符
  • 局限性：无法表示所有语言的字符

Unicode 编码：

  • 旨在包含世界上所有的字符
  • 使用 32 位表示字符（UCS-4），但通常使用可变长度编码
  • 代码点：每个字符分配一个唯一的代码点
  • 平面划分：Unicode 分为 17 个平面，每个平面包含 65536 个代码点

UTF-8 编码：

  • 变长编码，使用 1-4 字节表示一个字符
  • 兼容 ASCII（ASCII 字符使用 1 字节）
  • 是互联网上最常用的编码方案
  • 具有自同步特性，便于错误恢复
  • 编码规则：
    • 0xxxxxxx：单字节 ASCII 字符
    • 110xxxxx 10xxxxxx：双字节字符
    • 1110xxxx 10xxxxxx 10xxxxxx：三字节字符
    • 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx：四字节字符
  • 性能优势：ASCII 字符处理速度与传统 ASCII 编码相同
  • 空间效率：对于主要包含 ASCII 字符的文本，空间开销小

UTF-16 编码：

  • 变长编码，使用 2 或 4 字节表示一个字符
  • 适合处理 Unicode 字符，但不兼容 ASCII
  • 代理对：使用两个 16 位值表示超出 BMP（基本多文种平面）的字符
  • 内存表示：每个字符占 2 或 4 字节
  • 性能考量：固定宽度的 BMP 字符访问速度快

UTF-32 编码：

  • 定长编码，使用 4 字节表示一个字符
  • 便于随机访问，但空间利用率低
  • 内存表示：每个字符占 4 字节
  • 性能考量：随机访问速度快，但内存开销大

编码转换：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
// UTF-8 到 UTF-16 的转换示例
#include <stdlib.h>
#include <string.h>

wchar_t *utf8_to_utf16(const char *utf8) {
    if (!utf8) return NULL;
    
    size_t len = strlen(utf8);
    wchar_t *utf16 = (wchar_t *)malloc((len + 1) * sizeof(wchar_t));
    if (!utf16) return NULL;
    
    size_t i = 0, j = 0;
    while (utf8[i]) {
        if ((utf8[i] & 0x80) == 0) {
            // 单字节字符
            utf16[j++] = (wchar_t)utf8[i++];
        } else if ((utf8[i] & 0xE0) == 0xC0) {
            // 双字节字符
            utf16[j++] = (wchar_t)(((utf8[i] & 0x1F) << 6) | (utf8[i+1] & 0x3F));
            i += 2;
        } else if ((utf8[i] & 0xF0) == 0xE0) {
            // 三字节字符
            utf16[j++] = (wchar_t)(((utf8[i] & 0x0F) << 12) | 
                                   ((utf8[i+1] & 0x3F) << 6) | 
                                   (utf8[i+2] & 0x3F));
            i += 3;
        } else if ((utf8[i] & 0xF8) == 0xF0) {
            // 四字节字符
            utf16[j++] = (wchar_t)(((utf8[i] & 0x07) << 18) | 
                                   ((utf8[i+1] & 0x3F) << 12) | 
                                   ((utf8[i+2] & 0x3F) << 6) | 
                                   (utf8[i+3] & 0x3F));
            i += 4;
        } else {
            // 无效编码
            utf16[j++] = '?';
            i++;
        }
    }
    utf16[j] = L'\0';
    
    return utf16;
}

// UTF-16 到 UTF-8 的转换示例
char *utf16_to_utf8(const wchar_t *utf16) {
    if (!utf16) return NULL;
    
    size_t len = wcslen(utf16);
    // 最坏情况下，每个 UTF-16 字符需要 4 个 UTF-8 字节
    char *utf8 = (char *)malloc(len * 4 + 1);
    if (!utf8) return NULL;
    
    size_t i = 0, j = 0;
    while (utf16[i]) {
        wchar_t c = utf16[i++];
        if (c < 0x80) {
            // 单字节
            utf8[j++] = (char)c;
        } else if (c < 0x800) {
            // 双字节
            utf8[j++] = (char)(0xC0 | (c >> 6));
            utf8[j++] = (char)(0x80 | (c & 0x3F));
        } else if (c < 0x10000) {
            // 三字节
            utf8[j++] = (char)(0xE0 | (c >> 12));
            utf8[j++] = (char)(0x80 | ((c >> 6) & 0x3F));
            utf8[j++] = (char)(0x80 | (c & 0x3F));
        } else {
            // 四字节
            utf8[j++] = (char)(0xF0 | (c >> 18));
            utf8[j++] = (char)(0x80 | ((c >> 12) & 0x3F));
            utf8[j++] = (char)(0x80 | ((c >> 6) & 0x3F));
            utf8[j++] = (char)(0x80 | (c & 0x3F));
        }
    }
    utf8[j] = '\0';
    
    return utf8;
}

编码检测：

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
// 检测字符串编码（简化版）
enum Encoding {
    ENCODING_ASCII,
    ENCODING_UTF8,
    ENCODING_UNKNOWN
};

enum Encoding detect_encoding(const char *str) {
    if (!str) return ENCODING_UNKNOWN;
    
    const unsigned char *p = (const unsigned char *)str;
    while (*p) {
        if (*p < 0x80) {
            // ASCII 字符
            p++;
        } else if ((*p & 0xE0) == 0xC0) {
            // 双字节 UTF-8
            if (*(p+1) == 0) return ENCODING_UNKNOWN;
            p += 2;
        } else if ((*p & 0xF0) == 0xE0) {
            // 三字节 UTF-8
            if (*(p+1) == 0 || *(p+2) == 0) return ENCODING_UNKNOWN;
            p += 3;
        } else if ((*p & 0xF8) == 0xF0) {
            // 四字节 UTF-8
            if (*(p+1) == 0 || *(p+2) == 0 || *(p+3) == 0) return ENCODING_UNKNOWN;
            p += 4;
        } else {
            // 无效编码
            return ENCODING_UNKNOWN;
        }
    }
    
    return ENCODING_UTF8;
}

1.3.3 字符串处理的底层原理

内存访问模式：

  • 顺序访问：最常见的访问模式，如字符串遍历、复制

    • 缓存利用：顺序访问利用 CPU 缓存的预取机制
    • 性能优化：使用 SIMD 指令并行处理连续数据
    • 实现示例：strcpy、strlen 等函数

  • 随机访问：通过指针算术实现，如 str[i] 操作

    • 底层实现：str[i] 等价于 *(str + i)
    • 性能考量：随机访问可能导致缓存未命中
    • 硬件支持：现代 CPU 对随机访问有一定的优化

  • 模式匹配：如字符串查找、替换操作

    • 算法选择：根据模式串长度选择合适的算法
    • 性能优化：使用 KMP、Boyer-Moore 等高效算法
    • 硬件加速：某些 CPU 提供字符串匹配指令

字符串操作的时间复杂度：

操作时间复杂度空间复杂度说明优化策略
长度计算（strlen）O(n)O(1)需要遍历整个字符串SIMD 并行处理
字符串复制（strcpy）O(n)O(1)需要复制 n 个字符块复制、SIMD 指令
字符串比较（strcmp）O(n)O(1)最坏情况下需要比较所有字符块比较、早期退出
字符查找（strchr）O(n)O(1)最坏情况下需要遍历整个字符串SIMD 并行搜索
子串查找（strstr）O(n*m)O(1)朴素算法，KMP 算法可优化到 O(n+m)使用 Boyer-Moore 算法
字符串分割（strtok）O(n)O(1)需要遍历整个字符串使用查找表优化分隔符检查

字符串池化技术：

  • 编译时池化：编译器将相同的字符串字面量合并为一个

    • GCC 实现：通过 -fmerge-constants 选项控制
    • Clang 实现：类似的常量合并机制
    • 内存节省：减少重复字符串字面量的内存使用

  • 运行时池化：通过哈希表等数据结构管理字符串，减少重复存储

    • 实现方式：使用哈希表存储唯一字符串
    • 性能考量：查找速度快，但插入有开销
    • 适用场景：频繁使用相同字符串的场景

字符串的内存对齐：

  • 字符串通常不需要特殊对齐，因为字符是单字节的
  • 但字符串数组或包含字符串的结构体可能需要对齐以提高访问效率
  • 结构体对齐：包含字符串的结构体遵循编译器的对齐规则
  • 内存分配：动态分配的字符串通常按 8 或 16 字节对齐

缓存优化策略：

  1. 缓存友好的数据结构：将相关字符串存储在连续内存中
  2. 预取优化：使用 __builtin_prefetch 提示 CPU 预取数据
  3. 缓存阻塞：对于大字符串操作，分块处理以提高缓存命中率
  4. SIMD 指令：使用 AVX2、AVX-512 等指令加速字符串处理

1.3.4 多字节字符串处理

宽字符支持：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <wchar.h>
#include <locale.h>
#include <string.h>

int main(void) {
    setlocale(LC_ALL, "");  // 设置本地化环境
    
    // 宽字符串字面量
    wchar_t *wstr = L"你好，世界！";
    
    // 宽字符串输出
    wprintf(L"宽字符串: %ls\n", wstr);
    wprintf(L"宽字符串长度: %zu\n", wcslen(wstr));
    
    // 宽字符串操作
    wchar_t wbuf[100];
    wcscpy(wbuf, wstr);
    wprintf(L"复制后的宽字符串: %ls\n", wbuf);
    
    return 0;
}

多字节字符串函数：

  • <wchar.h>：提供宽字符和宽字符串处理函数

    • 核心函数：wcslen、wcscpy、wcscmp 等
    • 扩展函数：wcsnlen、wcsncpy、wcsncmp 等

  • <wctype.h>：提供宽字符分类和转换函数

    • 分类函数：iswalnum、iswalpha、iswdigit 等
    • 转换函数：towupper、towlower 等

  • <locale.h>：提供本地化支持

    • 核心函数：setlocale、localeconv 等
    • 本地化影响：影响宽字符的编码和处理

  • <uchar.h>：C11 引入，提供 Unicode 字符支持

    • 类型定义：char16_t、char32_t 等
    • 字符串字面量：u"..."、U"..." 等

国际化支持：

  • 使用 setlocale 设置本地化环境

    • 参数选择：空字符串表示使用环境变量设置
    • 影响范围：影响所有依赖本地化的函数

  • 使用宽字符函数处理非 ASCII 字符

    • 性能考量：宽字符操作可能比窄字符操作慢
    • 内存开销：宽字符串占用更多内存

  • 注意编码转换的正确性和性能

    • 转换开销：编码转换是 CPU 密集型操作
    • 错误处理：需要处理无效编码的情况
    • 性能优化：缓存频繁使用的转换结果

多字节字符串的性能优化：

  1. 编码选择：根据应用场景选择合适的编码

    • 主要处理 ASCII 字符：使用 UTF-8
    • 需要频繁随机访问：使用 UTF-32
    • 平衡内存和性能：使用 UTF-16

  2. 批量处理：减少函数调用开销，批量处理字符串

  3. SIMD 优化：利用 SIMD 指令加速多字节字符串处理

  4. 内存管理：合理分配内存，避免频繁重新分配

  5. 缓存策略：利用 CPU 缓存，提高数据局部性

2. 字符串库函数详解

C 语言标准库 <string.h> 提供了丰富的字符串处理函数，这些函数是字符串操作的基础。

2.1 字符串长度函数

2.1.1 strlen 函数

1
size_t strlen(const char *s);
  • 功能：计算字符串的长度，不包括空字符
  • 参数：s - 指向字符串的指针
  • 返回值：字符串的长度
  • 注意：如果 s 不是以空字符结尾，会导致未定义行为

底层实现原理：

1
2
3
4
5
6
7
8
// strlen 的典型实现
size_t strlen(const char *s) {
    const char *p = s;
    while (*p != '\0') {
        p++;
    }
    return p - s;
}

性能优化：

  • 向量化实现：使用 SIMD 指令并行处理多个字符
  • 块处理：每次处理 4 或 8 个字节，减少循环次数
  • 分支预测：利用 CPU 分支预测优化循环

汇编级优化：

1
2
3
4
5
6
7
8
9
10
11
; x86-64 汇编优化示例
strlen_optimized:
    mov rax, rdi        ; 保存字符串指针
    pxor xmm0, xmm0     ; 将 xmm0 置零（用于比较）

.loop:
    pcmpistri xmm0, [rax], 0x08  ; 比较 16 字节，寻找零字节
    jnz .loop         ; 如果没找到，继续循环
    add rax, rcx        ; rcx 包含找到的位置
    sub rax, rdi        ; 计算长度
    ret

2.1.2 strnlen 函数

1
size_t strnlen(const char *s, size_t maxlen);
  • 功能：计算字符串的长度，但最多检查 maxlen 个字符
  • 参数：s - 指向字符串的指针，maxlen - 最大检查长度
  • 返回值：字符串的长度或 maxlen（取较小值）
  • 注意：C99 引入，用于防止对非空终止字符串的无限循环

安全使用场景：

  • 处理来自不可信源的字符串
  • 处理可能没有正确终止的字符串
  • 防止缓冲区溢出攻击

实现原理：

1
2
3
4
5
6
7
8
9
// strnlen 的典型实现
size_t strnlen(const char *s, size_t maxlen) {
    const char *p = s;
    while (maxlen > 0 && *p != '\0') {
        p++;
        maxlen--;
    }
    return p - s;
}

性能考量：

  • 与 strlen 相比，strnlen 有一个额外的计数器检查
  • 但对于可能没有终止符的字符串，strnlen 更安全
  • 某些实现会对 strnlen 进行特殊优化，使其性能接近 strlen

2.1.3 自定义长度函数

高级应用：

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
// 计算 UTF-8 字符串的字符数（不是字节数）
size_t utf8_strlen(const char *s) {
    if (!s) return 0;
    
    size_t len = 0;
    while (*s) {
        if ((*s & 0x80) == 0) {
            // 单字节字符
            s++;
        } else if ((*s & 0xE0) == 0xC0) {
            // 双字节字符
            s += 2;
        } else if ((*s & 0xF0) == 0xE0) {
            // 三字节字符
            s += 3;
        } else if ((*s & 0xF8) == 0xF0) {
            // 四字节字符
            s += 4;
        } else {
            // 无效编码
            s++;
        }
        len++;
    }
    return len;
}

// 计算字符串中指定字符的出现次数
size_t count_chars(const char *s, char c) {
    if (!s) return 0;
    
    size_t count = 0;
    while (*s) {
        if (*s == c) {
            count++;
        }
        s++;
    }
    return count;
}

标准合规性：

  • C89：包含 strlen
  • C99：新增 strnlen
  • C11：无新增字符串长度函数

最佳实践：

  • 对于已知以空字符结尾的字符串，使用 strlen
  • 对于来自不可信源的字符串，使用 strnlen
  • 对于 UTF-8 字符串，使用专门的 UTF-8 长度函数
  • 避免在循环条件中重复调用 strlen，应将结果缓存

2.2 字符串复制函数

2.2.1 strcpy 函数

1
char *strcpy(char *dest, const char *src);
  • 功能：将 src 指向的字符串复制到 dest 指向的缓冲区
  • 参数：dest - 目标缓冲区，src - 源字符串
  • 返回值：指向 dest 的指针
  • 注意：
    • dest 必须有足够的空间容纳 src 字符串
    • 不检查缓冲区大小，可能导致缓冲区溢出
    • src 必须以空字符结尾

底层实现原理：

1
2
3
4
5
6
7
8
// strcpy 的典型实现
char *strcpy(char *dest, const char *src) {
    char *ret = dest;
    while ((*dest++ = *src++) != '\0') {
        ;
    }
    return ret;
}

性能优化：

  • 向量化复制：使用 SIMD 指令并行复制多个字节
  • 块复制：对于长字符串，使用 memcpy 进行块复制
  • 分支预测：优化循环条件，提高分支预测准确率

汇编级优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
; x86-64 汇编优化示例
strcpy_optimized:
    mov rax, rdi        ; 保存目标地址
    mov rcx, rsi        ; 源地址

.loop:
    mov dl, byte [rcx]  ; 加载一个字节
    mov byte [rdi], dl  ; 存储一个字节
    test dl, dl         ; 检查是否为零
    jz .done            ; 如果是零，结束
    inc rcx             ; 源指针递增
    inc rdi             ; 目标指针递增
    jmp .loop           ; 继续循环

.done:
    ret

2.2.2 strncpy 函数

1
char *strncpy(char *dest, const char *src, size_t n);
  • 功能：将 src 指向的字符串的前 n 个字符复制到 dest 指向的缓冲区
  • 参数：dest - 目标缓冲区，src - 源字符串，n - 要复制的最大字符数
  • 返回值：指向 dest 的指针
  • 注意：
    • 如果 src 的长度小于 n，会用空字符填充到 n 个字符
    • 如果 src 的长度大于或等于 n，不会在 dest 末尾添加空字符

底层实现原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// strncpy 的典型实现
char *strncpy(char *dest, const char *src, size_t n) {
    char *ret = dest;
    size_t i;
    
    // 复制 src 到 dest，直到遇到空字符或复制了 n 个字符
    for (i = 0; i < n && *src != '\0'; i++) {
        *dest++ = *src++;
    }
    
    // 如果 src 长度小于 n，用空字符填充剩余空间
    for (; i < n; i++) {
        *dest++ = '\0';
    }
    
    return ret;
}

安全使用指南：

  • 始终指定正确的缓冲区大小：确保 n 不大于 dest 的大小
  • 手动添加空字符：当 src 长度大于或等于 n 时，手动添加空字符
  • 使用 strlcpy：如果可用，使用更安全的 strlcpy 函数

性能考量：

  • strncpy 比 strcpy 慢，因为需要检查计数器
  • 当 src 长度小于 n 时，需要填充空字符，这会增加开销
  • 对于已知长度的字符串，使用 memcpy 可能更快

2.2.3 安全的字符串复制函数

C11 安全函数：

1
2
3
4
5
6
// strcpy_s 函数
errno_t strcpy_s(char *dest, rsize_t destsz, const char *src);

// 使用示例
char dest[10];
strcpy_s(dest, sizeof(dest), "Hello");

自定义安全复制函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 安全的字符串复制函数
char *safe_strcpy(char *dest, size_t dest_size, const char *src) {
    if (!dest || !src || dest_size == 0) {
        return NULL;
    }
    
    size_t src_len = strlen(src);
    if (src_len >= dest_size) {
        // 缓冲区不够大，只复制 dest_size-1 个字符并添加空字符
        strncpy(dest, src, dest_size - 1);
        dest[dest_size - 1] = '\0';
        return NULL;  // 返回 NULL 表示发生了截断
    }
    
    strcpy(dest, src);
    return dest;
}

性能优化策略：

  1. 短字符串优化：对于短字符串，使用内联汇编或手写循环
  2. 长字符串优化：对于长字符串，使用 SIMD 指令或 memcpy
  3. 重叠检测：如果源和目标内存重叠，使用 memmove 代替
  4. 分支预测：优化循环条件，提高分支预测准确率

标准合规性：

  • C89：包含 strcpy、strncpy
  • C99：无新增字符串复制函数
  • C11：新增 strcpy_s 等安全函数

最佳实践：

  • 对于已知大小的缓冲区，使用 strncpy 并手动添加空字符
  • 对于来自不可信源的字符串，使用安全的字符串复制函数
  • 对于性能关键路径，考虑使用汇编优化或 SIMD 指令
  • 避免在循环中重复调用字符串复制函数，应批量处理

2.3 字符串拼接函数

2.3.1 strcat 函数

1
char *strcat(char *dest, const char *src);
  • 功能：将 src 指向的字符串拼接到 dest 指向的字符串末尾
  • 参数：dest - 目标字符串，src - 要拼接的字符串
  • 返回值：指向 dest 的指针
  • 注意：
    • dest 必须有足够的空间容纳拼接后的字符串
    • dest 和 src 都必须以空字符结尾

底层实现原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// strcat 的典型实现
char *strcat(char *dest, const char *src) {
    char *ret = dest;
    
    // 找到 dest 的末尾
    while (*dest != '\0') {
        dest++;
    }
    
    // 复制 src 到 dest 末尾
    while ((*dest++ = *src++) != '\0') {
        ;
    }
    
    return ret;
}

性能优化：

  • 缓存目标末尾：如果已经知道 dest 的长度，直接跳到末尾
  • 批量复制：对于长字符串，使用 memcpy 进行块复制
  • 向量化操作：使用 SIMD 指令并行处理多个字符

性能瓶颈：

  • 每次调用 strcat 都需要重新遍历 dest 找到末尾，这是 O(n) 的开销
  • 对于多次拼接操作，时间复杂度会累积到 O(n²)

2.3.2 strncat 函数

1
char *strncat(char *dest, const char *src, size_t n);
  • 功能：将 src 指向的字符串的前 n 个字符拼接到 dest 指向的字符串末尾
  • 参数：dest - 目标字符串，src - 要拼接的字符串，n - 要拼接的最大字符数
  • 返回值：指向 dest 的指针
  • 注意：
    • 总是在拼接后的字符串末尾添加空字符
    • dest 必须以空字符结尾

底层实现原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// strncat 的典型实现
char *strncat(char *dest, const char *src, size_t n) {
    char *ret = dest;
    size_t i;
    
    // 找到 dest 的末尾
    while (*dest != '\0') {
        dest++;
    }
    
    // 复制 src 的前 n 个字符到 dest 末尾
    for (i = 0; i < n && *src != '\0'; i++) {
        *dest++ = *src++;
    }
    
    // 添加空字符
    *dest = '\0';
    
    return ret;
}

安全使用指南：

  • 计算剩余空间：在拼接前计算 dest 中剩余的空间
  • 限制拼接长度：确保 n 不超过剩余空间
  • 使用 strlcat：如果可用，使用更安全的 strlcat 函数

性能优化策略：

  1. 预分配足够空间：对于多次拼接操作，预分配足够的空间，避免多次重新分配
  2. 使用 StringBuilder 模式：维护一个缓冲区和当前长度，避免每次都遍历到末尾
  3. 批量拼接：将多个字符串一次性拼接，减少函数调用开销

StringBuilder 实现：

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
// 简单的 StringBuilder 实现
typedef struct {
    char *buffer;
    size_t size;
    size_t length;
} StringBuilder;

// 初始化 StringBuilder
void sb_init(StringBuilder *sb, size_t initial_size) {
    sb->buffer = (char *)malloc(initial_size);
    if (sb->buffer) {
        sb->size = initial_size;
        sb->length = 0;
        sb->buffer[0] = '\0';
    }
}

// 拼接字符串
void sb_append(StringBuilder *sb, const char *str) {
    if (!sb->buffer || !str) return;
    
    size_t str_len = strlen(str);
    size_t new_length = sb->length + str_len;
    
    // 如果空间不够，扩展缓冲区
    if (new_length >= sb->size) {
        size_t new_size = sb->size * 2;
        if (new_size < new_length + 1) {
            new_size = new_length + 1;
        }
        
        char *new_buffer = (char *)realloc(sb->buffer, new_size);
        if (new_buffer) {
            sb->buffer = new_buffer;
            sb->size = new_size;
        } else {
            return;  // 内存分配失败
        }
    }
    
    // 拼接字符串
    strcat(sb->buffer + sb->length, str);
    sb->length = new_length;
}

// 获取结果
const char *sb_get(StringBuilder *sb) {
    return sb->buffer;
}

// 释放资源
void sb_free(StringBuilder *sb) {
    if (sb->buffer) {
        free(sb->buffer);
        sb->buffer = NULL;
    }
    sb->size = 0;
    sb->length = 0;
}

C11 安全函数：

1
2
3
4
5
6
// strcat_s 函数
errno_t strcat_s(char *dest, rsize_t destsz, const char *src);

// 使用示例
char dest[20] = "Hello, ";
strcat_s(dest, sizeof(dest), "World!");

性能比较：

方法时间复杂度适用场景
多次 strcatO(n²)少量短字符串拼接
sprintf/snprintfO(n)格式化字符串拼接
StringBuilderO(n)多次字符串拼接
预分配 + memcpyO(n)已知总长度的拼接

最佳实践：

  • 对于少量字符串拼接，使用 strcat 或 snprintf
  • 对于多次字符串拼接，使用 StringBuilder 模式
  • 对于格式化字符串，使用 snprintf
  • 始终确保目标缓冲区有足够的空间
  • 对于来自不可信源的字符串，使用安全的字符串拼接函数

2.4 字符串比较函数

2.4.1 strcmp 函数

1
int strcmp(const char *s1, const char *s2);
  • 功能：比较两个字符串
  • 参数：s1 - 第一个字符串，s2 - 第二个字符串
  • 返回值：
    • 小于 0：s1 小于 s2
    • 等于 0：s1 等于 s2
    • 大于 0：s1 大于 s2
  • 注意：比较是基于字符的 ASCII 值

底层实现原理：

1
2
3
4
5
6
7
8
// strcmp 的典型实现
int strcmp(const char *s1, const char *s2) {
    while (*s1 && (*s1 == *s2)) {
        s1++;
        s2++;
    }
    return *(unsigned char *)s1 - *(unsigned char *)s2;
}

性能优化：

  • 向量化比较：使用 SIMD 指令并行比较多个字符
  • 块处理：每次处理 4 或 8 个字节，减少循环次数
  • 分支预测：优化循环条件，提高分支预测准确率
  • 内存对齐：确保内存访问对齐到 CPU 缓存行边界
  • 预取优化：使用 __builtin_prefetch 提示 CPU 预取数据

汇编级优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
; x86-64 汇编优化示例
strcmp_optimized:
    mov rcx, rdi        ; s1
    mov rdx, rsi        ; s2

.loop:
    mov al, byte [rcx]  ; 加载 s1 的一个字节
    mov dl, byte [rdx]  ; 加载 s2 的一个字节
    cmp al, dl          ; 比较
    jne .done           ; 如果不相等，结束
    test al, al         ; 检查是否到达字符串末尾
    jz .done            ; 如果到达末尾，结束
    inc rcx             ; s1 指针递增
    inc rdx             ; s2 指针递增
    jmp .loop           ; 继续循环

.done:
    movzx eax, al       ; 扩展 al 到 eax
    movzx edx, dl       ; 扩展 dl 到 edx
    sub eax, edx        ; 计算差值
    ret

SIMD 优化实现：

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

// 使用 AVX2 优化的 strcmp 实现
int simd_strcmp(const char *s1, const char *s2) {
    const char *p1 = s1, *p2 = s2;
    
    // 对齐到 32 字节边界
    while (((uintptr_t)p1 % 32 != 0 || (uintptr_t)p2 % 32 != 0)) {
        if (*p1 != *p2) {
            return *(unsigned char *)p1 - *(unsigned char *)p2;
        }
        if (*p1 == '\0') {
            return 0;
        }
        p1++;
        p2++;
    }
    
    // 使用 AVX2 指令并行处理
    __m256i zero = _mm256_setzero_si256();
    while (1) {
        __m256i vec1 = _mm256_load_si256((__m256i *)p1);
        __m256i vec2 = _mm256_load_si256((__m256i *)p2);
        
        // 检查是否到达字符串末尾
        __m256i cmp1 = _mm256_cmpeq_epi8(vec1, zero);
        int mask1 = _mm256_movemask_epi8(cmp1);
        
        __m256i cmp2 = _mm256_cmpeq_epi8(vec2, zero);
        int mask2 = _mm256_movemask_epi8(cmp2);
        
        // 检查字符是否不同
        __m256i cmp_ne = _mm256_cmpneq_epi8(vec1, vec2);
        int mask_ne = _mm256_movemask_epi8(cmp_ne);
        
        if (mask_ne != 0) {
            // 找到不同字符
            int pos = __builtin_ctz(mask_ne);
            return ((unsigned char *)p1)[pos] - ((unsigned char *)p2)[pos];
        }
        
        if (mask1 != 0 || mask2 != 0) {
            // 到达字符串末尾
            return 0;
        }
        
        p1 += 32;
        p2 += 32;
    }
}

2.4.2 strncmp 函数

1
int strncmp(const char *s1, const char *s2, size_t n);
  • 功能：比较两个字符串的前 n 个字符
  • 参数：s1 - 第一个字符串，s2 - 第二个字符串，n - 要比较的最大字符数
  • 返回值：与 strcmp 相同

底层实现原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// strncmp 的典型实现
int strncmp(const char *s1, const char *s2, size_t n) {
    if (n == 0) {
        return 0;
    }
    
    while (n > 1 && *s1 && (*s1 == *s2)) {
        s1++;
        s2++;
        n--;
    }
    
    return *(unsigned char *)s1 - *(unsigned char *)s2;
}

安全使用指南：

  • 始终指定合理的比较长度：确保 n 不超过任一字符串的长度
  • 处理空字符串：当 n 为 0 时，函数直接返回 0
  • 注意返回值：返回值的具体数值可能因实现而异，应只关注其符号

性能优化策略：

  1. 短字符串优化：对于短字符串，使用内联汇编或手写循环
  2. 长字符串优化：对于长字符串，使用 SIMD 指令并行比较
  3. 早期退出：一旦发现不同字符，立即返回结果
  4. 分支预测：利用 CPU 分支预测优化循环
  5. 批量比较：对于大 n 值，使用块比较减少循环次数

高级比较函数：

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
// 忽略大小写的字符串比较
int strcasecmp(const char *s1, const char *s2) {
    while (*s1 && (*s1 == *s2 || tolower(*(unsigned char *)s1) == tolower(*(unsigned char *)s2))) {
        s1++;
        s2++;
    }
    return tolower(*(unsigned char *)s1) - tolower(*(unsigned char *)s2);
}

// 带长度限制的忽略大小写比较
int strncasecmp(const char *s1, const char *s2, size_t n) {
    if (n == 0) {
        return 0;
    }
    
    while (n > 1 && *s1 && (*s1 == *s2 || tolower(*(unsigned char *)s1) == tolower(*(unsigned char *)s2))) {
        s1++;
        s2++;
        n--;
    }
    
    return tolower(*(unsigned char *)s1) - tolower(*(unsigned char *)s2);
}

// 基于 collation 的字符串比较（支持本地化）
#include <locale.h>
#include <string.h>

int collate_strcmp(const char *s1, const char *s2) {
    return strcoll(s1, s2);
}

// 自定义比较函数（例如，自然排序）
int natural_strcmp(const char *s1, const char *s2) {
    const char *p1 = s1, *p2 = s2;
    
    while (*p1 && *p2) {
        if (isdigit(*p1) && isdigit(*p2)) {
            // 比较数字部分
            long num1 = strtol(p1, (char **)&p1, 10);
            long num2 = strtol(p2, (char **)&p2, 10);
            
            if (num1 != num2) {
                return num1 - num2;
            }
        } else {
            // 比较非数字部分
            if (*p1 != *p2) {
                return *(unsigned char *)p1 - *(unsigned char *)p2;
            }
            p1++;
            p2++;
        }
    }
    
    return *(unsigned char *)p1 - *(unsigned char *)p2;
}

比较函数性能分析：

函数时间复杂度空间复杂度适用场景性能瓶颈
strcmpO(n)O(1)一般字符串比较分支预测失败
strncmpO(min(n, len))O(1)有限长度比较计数器检查
strcasecmpO(n)O(1)忽略大小写比较字符转换开销
strcollO(n)O(1)本地化比较复杂的排序规则
natural_strcmpO(n)O(1)自然排序数字解析开销

最佳实践：

  • 对于一般字符串比较，使用 strcmp
  • 对于有限长度比较，使用 strncmp
  • 对于忽略大小写比较，使用 strcasecmp 或 strncasecmp
  • 对于需要本地化支持的比较，使用 strcoll
  • 对于包含数字的字符串比较，使用 natural_strcmp
  • 对于性能关键路径，考虑使用 SIMD 优化的比较函数
  • 避免在循环条件中重复调用比较函数，应缓存比较结果

标准合规性：

  • C89：包含 strcmp、strncmp
  • C99：无新增比较函数
  • C11：无新增比较函数
  • 注意：strcasecmp 和 strncasecmp 是 POSIX 扩展，不是 C 标准的一部分
函数时间复杂度适用场景
strcmpO(n)比较整个字符串
strncmpO(n)比较字符串的前 n 个字符
strcasecmpO(n)忽略大小写的字符串比较
strncasecmpO(n)忽略大小写的有限长度字符串比较

最佳实践：

  • 对于完整字符串比较，使用 strcmp
  • 对于前缀比较，使用 strncmp
  • 对于忽略大小写的比较，使用 strcasecmp 或 strncasecmp
  • 对于性能关键路径，考虑使用汇编优化或 SIMD 指令
  • 避免在循环中重复调用字符串比较函数，应缓存比较结果

2.5 字符串查找函数

字符串查找是字符串处理中的核心操作，涉及多种算法和优化策略。本节将深入探讨字符串查找函数的实现原理、性能优化和实际应用。

2.5.1 strchr 函数

1
char *strchr(const char *s, int c);
  • 功能：在字符串 s 中查找字符 c 的第一次出现
  • 参数：s - 要搜索的字符串，c - 要查找的字符（转换为 unsigned char）
  • 返回值：指向找到的字符的指针，如果未找到则返回 NULL

底层实现原理：

1
2
3
4
5
6
7
8
9
10
11
// strchr 的典型实现
char *strchr(const char *s, int c) {
    unsigned char uc = (unsigned char)c;
    while (*s) {
        if (*(unsigned char *)s == uc) {
            return (char *)s;
        }
        s++;
    }
    return (uc == '\0') ? (char *)s : NULL;
}

性能优化：

  • 向量化搜索：使用 SIMD 指令并行搜索多个字符
  • 块处理：每次处理 4 或 8 个字节，减少循环次数
  • 分支预测：优化循环条件，提高分支预测准确率
  • 内存对齐：确保内存访问对齐到 CPU 缓存行边界

SIMD 优化实现：

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

// 使用 AVX2 优化的 strchr 实现
char *simd_strchr(const char *s, int c) {
    const char *ptr = s;
    unsigned char uc = (unsigned char)c;
    
    // 对齐到 32 字节边界
    while ((uintptr_t)ptr % 32 != 0) {
        if (*ptr == uc) {
            return (char *)ptr;
        }
        if (*ptr == '\0') {
            return NULL;
        }
        ptr++;
    }
    
    // 使用 AVX2 指令并行搜索
    __m256i target = _mm256_set1_epi8(uc);
    while (1) {
        __m256i vec = _mm256_load_si256((__m256i *)ptr);
        __m256i cmp = _mm256_cmpeq_epi8(vec, target);
        int mask = _mm256_movemask_epi8(cmp);
        
        if (mask != 0) {
            // 找到目标字符
            int pos = __builtin_ctz(mask);
            return (char *)ptr + pos;
        }
        
        // 检查是否到达字符串末尾
        __m256i zero = _mm256_setzero_si256();
        __m256i cmp_zero = _mm256_cmpeq_epi8(vec, zero);
        int mask_zero = _mm256_movemask_epi8(cmp_zero);
        
        if (mask_zero != 0) {
            // 到达字符串末尾
            return NULL;
        }
        
        ptr += 32;
    }
}

汇编级优化：

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
; x86-64 汇编优化示例
strchr_optimized:
    mov rax, rdi        ; 保存字符串指针
    movzx edx, sil      ; 扩展字符到 32 位
    
    ; 对齐到 16 字节边界
.align_loop:
    test rax, 0xf       ; 检查是否对齐到 16 字节
    jz .main_loop
    mov cl, byte [rax]  ; 加载一个字节
    cmp cl, dl          ; 比较
    je .found
    test cl, cl         ; 检查是否到达字符串末尾
    jz .not_found
    inc rax             ; 指针递增
    jmp .align_loop
    
.main_loop:
    ; 使用 SSE2 指令并行搜索
    movd xmm0, edx      ; 将字符加载到 xmm0
    pshufb xmm0, xmm0   ; 广播字符到所有 16 个字节
    
.loop:
    movdqa xmm1, [rax]  ; 加载 16 个字节
    pcmpeqb xmm1, xmm0  ; 比较
    pmovmskb eax, xmm1  ; 将比较结果转换为掩码
    test eax, eax       ; 检查是否找到
    jnz .process_mask
    
    ; 检查是否到达字符串末尾
    movdqa xmm2, xmm1   ; 保存比较结果
    pxor xmm3, xmm3     ; 置零
    pcmpeqb xmm1, xmm3  ; 比较是否为零
    pmovmskb eax, xmm1  ; 将比较结果转换为掩码
    test eax, eax       ; 检查是否有零字节
    jnz .not_found
    
    add rax, 16         ; 指针递增 16
    jmp .loop
    
.process_mask:
    bsfl eax, eax       ; 找到第一个匹配位的位置
    add rax, rdi        ; 计算最终指针
    ret
    
.found:
    mov rax, rdi        ; 返回找到的指针
    ret
    
.not_found:
    xor rax, rax        ; 返回 NULL
    ret

2.5.2 strrchr 函数

1
char *strrchr(const char *s, int c);
  • 功能：在字符串 s 中查找字符 c 的最后一次出现
  • 参数：s - 要搜索的字符串，c - 要查找的字符（转换为 unsigned char）
  • 返回值：指向找到的字符的指针，如果未找到则返回 NULL

底层实现原理：

1
2
3
4
5
6
7
8
9
10
11
// strrchr 的典型实现
char *strrchr(const char *s, int c) {
    unsigned char uc = (unsigned char)c;
    const char *last = NULL;
    do {
        if (*(unsigned char *)s == uc) {
            last = s;
        }
    } while (*s++);
    return (char *)last;
}

性能优化策略：

  1. 从后向前搜索：对于长字符串，可以考虑从后向前搜索
  2. 块处理：每次处理多个字节，减少循环次数
  3. SIMD 优化：使用 SIMD 指令并行搜索
  4. 缓存优化：提高缓存命中率，减少缓存未命中

高级实现：

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
// 优化的 strrchr 实现
char *optimized_strrchr(const char *s, int c) {
    unsigned char uc = (unsigned char)c;
    const char *last = NULL;
    const char *ptr = s;
    
    // 快速路径：处理短字符串
    for (int i = 0; i < 16 && *ptr; i++) {
        if (*(unsigned char *)ptr == uc) {
            last = ptr;
        }
        ptr++;
    }
    
    if (!*ptr) {
        return (char *)last;
    }
    
    // 对齐到 16 字节边界
    while ((uintptr_t)ptr % 16 != 0) {
        if (*(unsigned char *)ptr == uc) {
            last = ptr;
        }
        if (!*ptr) {
            return (char *)last;
        }
        ptr++;
    }
    
    // 块处理：每次处理 16 字节
    while (1) {
        // 检查是否到达字符串末尾
        const char *end = memchr(ptr, '\0', 16);
        if (end) {
            // 处理剩余部分
            for (const char *p = ptr; p <= end; p++) {
                if (*(unsigned char *)p == uc) {
                    last = p;
                }
            }
            return (char *)last;
        }
        
        // 搜索当前块
        for (int i = 0; i < 16; i++) {
            if (*(unsigned char *)(ptr + i) == uc) {
                last = ptr + i;
            }
        }
        
        ptr += 16;
    }
}

2.5.3 strstr 函数

1
char *strstr(const char *haystack, const char *needle);
  • 功能：在字符串 haystack 中查找字符串 needle 的第一次出现
  • 参数：haystack - 要搜索的字符串，needle - 要查找的子字符串
  • 返回值：指向找到的子字符串的指针，如果未找到则返回 NULL

底层实现原理：

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
// strstr 的典型实现（朴素算法）
char *strstr(const char *haystack, const char *needle) {
    if (!*needle) {
        return (char *)haystack;
    }
    
    const char *h = haystack;
    const char *n = needle;
    
    while (*h) {
        const char *hh = h;
        const char *nn = n;
        
        while (*hh && *nn && *hh == *nn) {
            hh++;
            nn++;
        }
        
        if (!*nn) {
            return (char *)h;
        }
        
        h++;
    }
    
    return NULL;
}

高级算法实现：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
// Boyer-Moore 算法实现
char *boyer_moore_strstr(const char *haystack, const char *needle) {
    size_t haystack_len = strlen(haystack);
    size_t needle_len = strlen(needle);
    
    if (needle_len == 0) {
        return (char *)haystack;
    }
    
    if (needle_len > haystack_len) {
        return NULL;
    }
    
    // 构建坏字符表
    int bad_char[256];
    for (int i = 0; i < 256; i++) {
        bad_char[i] = needle_len;
    }
    
    for (size_t i = 0; i < needle_len - 1; i++) {
        bad_char[(unsigned char)needle[i]] = needle_len - 1 - i;
    }
    
    // 构建好后缀表
    int *good_suffix = (int *)malloc(needle_len * sizeof(int));
    if (!good_suffix) {
        return NULL;
    }
    
    // 初始化好后缀表
    for (size_t i = 0; i < needle_len; i++) {
        good_suffix[i] = needle_len;
    }
    
    // 计算好后缀表
    int *suffix = (int *)malloc(needle_len * sizeof(int));
    if (!suffix) {
        free(good_suffix);
        return NULL;
    }
    
    suffix[needle_len - 1] = needle_len;
    size_t f = 0, g = needle_len - 1;
    
    for (size_t i = needle_len - 2; i >= 0; i--) {
        if (i > g && suffix[i + needle_len - 1 - f] < i - g) {
            suffix[i] = suffix[i + needle_len - 1 - f];
        } else {
            if (i < g) {
                g = i;
            }
            f = i;
            while (g >= 0 && needle[g] == needle[g + needle_len - 1 - f]) {
                g--;
            }
            suffix[i] = f - g;
        }
    }
    
    // 计算好后缀表
    for (size_t i = 0; i < needle_len - 1; i++) {
        good_suffix[needle_len - 1 - suffix[i]] = needle_len - 1 - i;
    }
    
    // 搜索
    size_t i = 0;
    while (i <= haystack_len - needle_len) {
        size_t j = needle_len - 1;
        while (j >= 0 && haystack[i + j] == needle[j]) {
            j--;
        }
        
        if (j < 0) {
            free(suffix);
            free(good_suffix);
            return (char *)&haystack[i];
        }
        
        // 计算移动距离
        int bad_char_shift = bad_char[(unsigned char)haystack[i + j]];
        int good_suffix_shift = good_suffix[j];
        i += (bad_char_shift > good_suffix_shift) ? bad_char_shift : good_suffix_shift;
    }
    
    free(suffix);
    free(good_suffix);
    return NULL;
}

KMP 算法实现：

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
// KMP 算法实现
char *kmp_strstr(const char *haystack, const char *needle) {
    size_t haystack_len = strlen(haystack);
    size_t needle_len = strlen(needle);
    
    if (needle_len == 0) {
        return (char *)haystack;
    }
    
    if (needle_len > haystack_len) {
        return NULL;
    }
    
    // 构建部分匹配表（next 数组）
    int *next = (int *)malloc(needle_len * sizeof(int));
    if (!next) {
        return NULL;
    }
    
    // 计算 next 数组
    next[0] = -1;
    int j = -1, i = 0;
    while (i < needle_len - 1) {
        if (j == -1 || needle[i] == needle[j]) {
            i++;
            j++;
            next[i] = (needle[i] != needle[j]) ? j : next[j];
        } else {
            j = next[j];
        }
    }
    
    // 搜索
    i = 0, j = 0;
    while (i < (int)haystack_len && j < (int)needle_len) {
        if (j == -1 || haystack[i] == needle[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    
    free(next);
    
    if (j == (int)needle_len) {
        return (char *)&haystack[i - j];
    }
    
    return NULL;
}

算法性能比较：

算法时间复杂度（最好）时间复杂度（最坏）空间复杂度适用场景
朴素算法O(n+m)O(n*m)O(1)短模式串
KMP 算法O(n+m)O(n+m)O(m)长文本，重复模式
Boyer-Moore 算法O(n/m)O(n+m)O(m+σ)长模式串，实际应用中最快
Rabin-Karp 算法O(n+m)O(n*m)O(1)多模式匹配

最佳实践：

  • 对于短模式串，使用朴素算法或内联汇编
  • 对于长文本和重复模式，使用 KMP 算法
  • 对于实际应用中的字符串查找，使用 Boyer-Moore 算法
  • 对于性能关键路径，考虑使用 SIMD 优化的实现
  • 避免在循环中重复调用字符串查找函数，应缓存查找结果

标准合规性：

  • C89：包含 strchr、strrchr、strstr
  • C99：无新增查找函数
  • C11：无新增查找函数

2.5.4 其他字符串查找函数

strpbrk 函数：

1
char *strpbrk(const char *s, const char *accept);
  • 功能：在字符串 s 中查找 accept 中任何字符的第一次出现
  • 参数：s - 要搜索的字符串，accept - 包含要查找的字符的字符串
  • 返回值：指向找到的字符的指针，如果未找到则返回 NULL

strspn 函数：

1
size_t strspn(const char *s, const char *accept);
  • 功能：计算字符串 s 开头连续包含 accept 中字符的长度
  • 参数：s - 要检查的字符串，accept - 包含可接受字符的字符串
  • 返回值：s 开头连续包含 accept 中字符的长度

strcspn 函数：

1
size_t strcspn(const char *s, const char *reject);
  • 功能：计算字符串 s 开头连续不包含 reject 中字符的长度
  • 参数：s - 要检查的字符串，reject - 包含要拒绝的字符的字符串
  • 返回值：s 开头连续不包含 reject 中字符的长度

高级查找函数：

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
// 查找字符串中所有出现的子串
size_t find_all_occurrences(const char *haystack, const char *needle, char **occurrences, size_t max_occurrences) {
    size_t count = 0;
    const char *ptr = haystack;
    
    while ((ptr = strstr(ptr, needle)) && count < max_occurrences) {
        occurrences[count++] = (char *)ptr;
        ptr++;
    }
    
    return count;
}

// 查找字符串中第 n 次出现的子串
char *find_nth_occurrence(const char *haystack, const char *needle, size_t n) {
    const char *ptr = haystack;
    size_t count = 0;
    
    while ((ptr = strstr(ptr, needle)) && ++count < n) {
        ptr++;
    }
    
    return (count == n) ? (char *)ptr : NULL;
}

// 不区分大小写的字符串查找
char *strcasestr(const char *haystack, const char *needle) {
    if (!*needle) {
        return (char *)haystack;
    }
    
    const char *h = haystack;
    const char *n = needle;
    
    while (*h) {
        const char *hh = h;
        const char *nn = n;
        
        while (*hh && *nn && tolower(*(unsigned char *)hh) == tolower(*(unsigned char *)nn)) {
            hh++;
            nn++;
        }
        
        if (!*nn) {
            return (char *)h;
        }
        
        h++;
    }
    
    return NULL;
}

性能优化策略：

  1. 查找表优化：对于 strpbrk、strspn、strcspn，使用查找表加速字符检查
  2. 向量化实现：使用 SIMD 指令并行处理多个字符
  3. 缓存优化：提高缓存命中率，减少缓存未命中
  4. 分支预测：优化循环条件，提高分支预测准确率

查找表优化示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 使用查找表优化的 strpbrk 实现
char *optimized_strpbrk(const char *s, const char *accept) {
    // 构建查找表
    unsigned char table[256] = {0};
    const unsigned char *a = (const unsigned char *)accept;
    
    while (*a) {
        table[*a++] = 1;
    }
    
    // 搜索
    const unsigned char *p = (const unsigned char *)s;
    while (*p) {
        if (table[*p]) {
            return (char *)p;
        }
        p++;
    }
    
    return NULL;
}

最佳实践：

  • 对于单个字符查找，使用 strchr 或 strrchr
  • 对于多个字符查找，使用 strpbrk
  • 对于子串查找，使用 strstr 或其优化版本
  • 对于前缀检查，使用 strspn 或 strcspn
  • 对于性能关键路径，考虑使用汇编优化或 SIMD 指令
  • 避免在循环中重复调用字符串查找函数，应缓存查找结果
  • 对于多线程环境，使用 strtok_r
  • 对于需要保留原始字符串的场景，先复制一份再分割
  • 对于复杂的分割需求，使用自定义分割函数
  • 避免在循环中重复分割相同的字符串，应缓存分割结果

2.7 内存操作函数

2.7.1 memset 函数

1
void *memset(void *s, int c, size_t n);
  • 功能：将内存块的前 n 个字节设置为值 c
  • 参数：s - 指向内存块的指针，c - 要设置的值，n - 要设置的字节数
  • 返回值：指向 s 的指针

底层实现原理：

1
2
3
4
5
6
7
8
9
10
11
12
// memset 的典型实现
void *memset(void *s, int c, size_t n) {
    unsigned char *p = (unsigned char *)s;
    unsigned char value = (unsigned char)c;
    
    while (n > 0) {
        *p++ = value;
        n--;
    }
    
    return s;
}

性能优化：

  • 块处理：每次处理 4 或 8 个字节，减少循环次数
  • 向量化：使用 SIMD 指令并行设置多个字节
  • 分支预测：利用 CPU 分支预测优化循环

汇编级优化：

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
; x86-64 汇编优化示例
memset_optimized:
    mov rax, rdi        ; 返回值
    movzx edx, sil      ; 将 c 扩展为 32 位
    mov rcx, rdx        ; 复制 c 到 rcx
    shl rdx, 8          ; 左移 8 位
    or rcx, rdx         ; 合并到 rcx
    mov rdx, rcx        ; 复制到 rdx
    shl rdx, 16         ; 左移 16 位
    or rcx, rdx         ; 合并到 rcx，现在 rcx 包含 4 个 c
    mov rdx, rcx        ; 复制到 rdx
    shl rdx, 32         ; 左移 32 位
    or rcx, rdx         ; 合并到 rcx，现在 rcx 包含 8 个 c
    mov rdx, r8         ; 复制 n 到 rdx

    ; 处理单字节
    test rdx, rdx
    jz .done

    ; 对齐到 8 字节边界
    test rax, 7
    jz .aligned

.byte_loop:
    mov byte [rax], sil
    inc rax
    dec rdx
    test rax, 7
    jnz .byte_loop

.aligned:
    ; 处理 8 字节块
    mov r8, rdx
    shr r8, 3          ; 计算 8 字节块数
    test r8, r8
    jz .remaining

.loop:
    mov qword [rax], rcx
    add rax, 8
    dec r8
    jnz .loop

.remaining:
    ; 处理剩余的字节
    and rdx, 7
    test rdx, rdx
    jz .done

.remainder_loop:
    mov byte [rax], sil
    inc rax
    dec rdx
    jnz .remainder_loop

.done:
    ret
1
2
char str[10];
memset(str, '0', 10);  // 将 str 的前 10 个字节设置为 '0'

2.7.2 memcpy 函数

1
void *memcpy(void *dest, const void *src, size_t n);
  • 功能：将 src 指向的内存块的前 n 个字节复制到 dest 指向的内存块
  • 参数：dest - 目标内存块，src - 源内存块，n - 要复制的字节数
  • 返回值：指向 dest 的指针
  • 注意：dest 和 src 不能重叠

底层实现原理：

1
2
3
4
5
6
7
8
9
10
11
12
// memcpy 的典型实现
void *memcpy(void *dest, const void *src, size_t n) {
    unsigned char *d = (unsigned char *)dest;
    const unsigned char *s = (const unsigned char *)src;
    
    while (n > 0) {
        *d++ = *s++;
        n--;
    }
    
    return dest;
}

性能优化：

  • 块处理：每次处理 4 或 8 个字节，减少循环次数
  • 向量化：使用 SIMD 指令并行复制多个字节
  • 内存对齐：优化内存访问对齐，提高缓存命中率
  • 分支预测：利用 CPU 分支预测优化循环

汇编级优化：

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
66
67
68
69
70
71
; x86-64 汇编优化示例
memcpy_optimized:
    mov rax, rdi        ; 返回值
    mov rcx, rdx        ; 复制 n 到 rcx
    test rcx, rcx
    jz .done

    ; 对齐到 8 字节边界
    test rax, 7
    jz .dest_aligned

.dest_unaligned:
    mov dl, byte [rsi]
    mov byte [rax], dl
    inc rax
    inc rsi
    dec rcx
    test rax, 7
    jnz .dest_unaligned

.dest_aligned:
    ; 检查源是否对齐
    test rsi, 7
    jz .both_aligned

    ; 源未对齐，使用字节复制
    mov r8, rcx
    mov r9, rsi
    mov r10, rax

.byte_loop:
    mov dl, byte [r9]
    mov byte [r10], dl
    inc r9
    inc r10
    dec r8
    jnz .byte_loop

    jmp .done

.both_aligned:
    ; 处理 8 字节块
    mov r8, rcx
    shr r8, 3          ; 计算 8 字节块数
    test r8, r8
    jz .remaining

.loop:
    mov rdx, qword [rsi]
    mov qword [rax], rdx
    add rax, 8
    add rsi, 8
    dec r8
    jnz .loop

.remaining:
    ; 处理剩余的字节
    and rcx, 7
    test rcx, rcx
    jz .done

.remainder_loop:
    mov dl, byte [rsi]
    mov byte [rax], dl
    inc rax
    inc rsi
    dec rcx
    jnz .remainder_loop

.done:
    ret
1
2
3
char src[] = "Hello";
char dest[10];
memcpy(dest, src, 6);  // 复制包括空字符在内的 6 个字节

2.7.3 memmove 函数

1
void *memmove(void *dest, const void *src, size_t n);
  • 功能：与 memcpy 类似，但可以处理 dest 和 src 重叠的情况
  • 参数：与 memcpy 相同
  • 返回值：指向 dest 的指针

底层实现原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// memmove 的典型实现
void *memmove(void *dest, const void *src, size_t n) {
    unsigned char *d = (unsigned char *)dest;
    const unsigned char *s = (const unsigned char *)src;
    
    if (d < s) {
        // 从前往后复制
        while (n > 0) {
            *d++ = *s++;
            n--;
        }
    } else if (d > s) {
        // 从后往前复制
        d += n;
        s += n;
        while (n > 0) {
            *--d = *--s;
            n--;
        }
    }
    
    return dest;
}

性能优化：

  • 块处理：每次处理 4 或 8 个字节，减少循环次数
  • 向量化：使用 SIMD 指令并行复制多个字节
  • 内存对齐：优化内存访问对齐，提高缓存命中率
  • 分支预测：利用 CPU 分支预测优化循环

高级应用：

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
// 安全的内存复制，处理 NULL 指针
void *safe_memcpy(void *dest, const void *src, size_t n) {
    if (!dest || !src) {
        return NULL;
    }
    return memcpy(dest, src, n);
}

// 内存比较函数
int memcmp(const void *s1, const void *s2, size_t n) {
    const unsigned char *p1 = (const unsigned char *)s1;
    const unsigned char *p2 = (const unsigned char *)s2;
    
    while (n > 0) {
        if (*p1 != *p2) {
            return *p1 - *p2;
        }
        p1++;
        p2++;
        n--;
    }
    
    return 0;
}

// 内存查找函数
void *memchr(const void *s, int c, size_t n) {
    const unsigned char *p = (const unsigned char *)s;
    unsigned char uc = (unsigned char)c;
    
    while (n > 0) {
        if (*p == uc) {
            return (void *)p;
        }
        p++;
        n--;
    }
    
    return NULL;
}

性能比较：

函数时间复杂度适用场景
memsetO(n)内存初始化
memcpyO(n)不重叠内存复制
memmoveO(n)可能重叠的内存复制
memcmpO(n)内存比较
memchrO(n)内存中查找字符

最佳实践：

  • 对于内存初始化，使用 memset
  • 对于不重叠的内存复制，使用 memcpy
  • 对于可能重叠的内存复制，使用 memmove
  • 对于内存比较，使用 memcmp
  • 对于内存中查找字符，使用 memchr
  • 对于性能关键路径，考虑使用汇编优化或 SIMD 指令
  • 避免在循环中重复调用内存操作函数，应批量处理
1
2
char str[] = "Hello, World!";
memmove(str + 7, str + 0, 5);  // 重叠复制，结果为 "Hello, Hello!"

2.7.4 memcmp 函数

1
int memcmp(const void *s1, const void *s2, size_t n);
  • 功能：比较两个内存块的前 n 个字节
  • 参数：s1 - 第一个内存块，s2 - 第二个内存块，n - 要比较的字节数
  • 返回值：
    • 小于 0：s1 小于 s2
    • 等于 0：s1 等于 s2
    • 大于 0：s1 大于 s2

底层实现原理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// memcmp 的典型实现
int memcmp(const void *s1, const void *s2, size_t n) {
    const unsigned char *p1 = (const unsigned char *)s1;
    const unsigned char *p2 = (const unsigned char *)s2;
    
    while (n > 0) {
        if (*p1 != *p2) {
            return *p1 - *p2;
        }
        p1++;
        p2++;
        n--;
    }
    
    return 0;
}

性能优化：

  • 块处理：每次处理 4 或 8 个字节，减少循环次数
  • 向量化：使用 SIMD 指令并行比较多个字节
  • 分支预测：利用 CPU 分支预测优化循环
  • 早期退出：一旦发现不同字节，立即返回结果

汇编级优化：

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
; x86-64 汇编优化示例
memcmp_optimized:
    mov rcx, rdx        ; 复制 n 到 rcx
    test rcx, rcx
    jz .equal

    mov r8, rdi        ; 复制 s1 到 r8
    mov r9, rsi        ; 复制 s2 到 r9

    ; 对齐到 8 字节边界
    test r8, 7
    jz .aligned

.byte_loop:
    mov al, byte [r8]
    cmp al, byte [r9]
    jne .not_equal
    inc r8
    inc r9
    dec rcx
    jz .equal
    test r8, 7
    jnz .byte_loop

.aligned:
    ; 处理 8 字节块
    mov r10, rcx
    shr r10, 3          ; 计算 8 字节块数
    test r10, r10
    jz .remaining

.loop:
    mov rax, qword [r8]
    cmp rax, qword [r9]
    jne .block_not_equal
    add r8, 8
    add r9, 8
    dec r10
    jnz .loop

.remaining:
    ; 处理剩余的字节
    and rcx, 7
    test rcx, rcx
    jz .equal

.remainder_loop:
    mov al, byte [r8]
    cmp al, byte [r9]
    jne .not_equal
    inc r8
    inc r9
    dec rcx
    jnz .remainder_loop

.equal:
    xor eax, eax
    ret

.not_equal:
    movzx eax, al
    movzx edx, byte [r9]
    sub eax, edx
    ret

.block_not_equal:
    ; 找出第一个不同的字节
    mov rcx, 8

.find_diff:
    mov al, byte [r8]
    cmp al, byte [r9]
    jne .not_equal
    inc r8
    inc r9
    dec rcx
    jnz .find_diff

    ; 所有字节都相同，这应该不会发生
    xor eax, eax
    ret

高级应用：

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
// 安全的内存比较，处理 NULL 指针
int safe_memcmp(const void *s1, const void *s2, size_t n) {
    if (!s1 || !s2) {
        return s1 - s2;  // 如果任一指针为 NULL，根据指针值比较
    }
    return memcmp(s1, s2, n);
}

// 大小写不敏感的内存比较
int memicmp(const void *s1, const void *s2, size_t n) {
    const unsigned char *p1 = (const unsigned char *)s1;
    const unsigned char *p2 = (const unsigned char *)s2;
    
    while (n > 0) {
        unsigned char c1 = tolower(*p1);
        unsigned char c2 = tolower(*p2);
        if (c1 != c2) {
            return c1 - c2;
        }
        p1++;
        p2++;
        n--;
    }
    
    return 0;
}

// 比较内存块的前 n 个字节，返回第一个不同的位置
ssize_t memcmp_pos(const void *s1, const void *s2, size_t n) {
    const unsigned char *p1 = (const unsigned char *)s1;
    const unsigned char *p2 = (const unsigned char *)s2;
    
    for (size_t i = 0; i < n; i++) {
        if (*p1 != *p2) {
            return i;
        }
        p1++;
        p2++;
    }
    
    return -1;  // 所有字节都相同
}

性能比较：

函数时间复杂度适用场景
memcmpO(n)内存块比较
memicmpO(n)大小写不敏感的内存块比较
memcmp_posO(n)查找内存块中第一个不同的位置

最佳实践：

  • 对于内存块比较，使用 memcmp
  • 对于大小写不敏感的内存块比较，使用 memicmp
  • 对于需要知道第一个不同位置的场景，使用 memcmp_pos
  • 对于性能关键路径，考虑使用汇编优化或 SIMD 指令
  • 避免在循环中重复调用内存比较函数，应缓存比较结果
1
2
3
char str1[] = "Hello";
char str2[] = "Hello";
int result = memcmp(str1, str2, 5);  // result = 0

2.8 安全的字符串函数

C11 标准引入了一些安全的字符串函数，它们在 <string.h> 中声明。

2.8.1 strcpy_s 函数

1
errno_t strcpy_s(char *dest, rsize_t destsz, const char *src);
  • 功能：安全地复制字符串
  • 参数：dest - 目标缓冲区，destsz - 目标缓冲区的大小，src - 源字符串
  • 返回值：成功返回 0，失败返回错误码
  • 注意：如果 destsz 不够大，会调用约束处理函数
1
2
char dest[10];
strcpy_s(dest, sizeof(dest), "Hello");

2.8.2 strcat_s 函数

1
errno_t strcat_s(char *dest, rsize_t destsz, const char *src);
  • 功能：安全地拼接字符串
  • 参数：dest - 目标字符串，destsz - 目标缓冲区的大小，src - 要拼接的字符串
  • 返回值：成功返回 0，失败返回错误码
1
2
char dest[20] = "Hello, ";
strcat_s(dest, sizeof(dest), "World!");

2.8.3 strnlen_s 函数

1
size_t strnlen_s(const char *s, rsize_t maxlen);
  • 功能：安全地计算字符串长度
  • 参数：s - 要计算长度的字符串，maxlen - 最大检查长度
  • 返回值：字符串的长度或 maxlen（取较小值）
1
2
char str[] = "Hello";
size_t len = strnlen_s(str, 10);

2.8.4 strtok_s 函数

1
char *strtok_s(char *str, const char *delimiters, char **context);
  • 功能：安全地分割字符串
  • 参数：str - 要分割的字符串（第一次调用）或 NULL（后续调用），delimiters - 分隔符字符串，context - 用于存储分割状态的指针
  • 返回值：指向下一个标记的指针，如果没有更多标记则返回 NULL
1
2
3
4
5
6
7
8
char str[] = "apple,banana,orange";
char *context;
char *token = strtok_s(str, ",", &context);
while (token != NULL)
{
    printf("%s\n", token);
    token = strtok_s(NULL, ",", &context);
}

3. 字符串操作的高级技巧

3.1 字符串反转

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

void reverse_string(char *str)
{
    if (str == NULL)
    {
        return;
    }
    
    int length = strlen(str);
    char *start = str;
    char *end = str + length - 1;
    
    while (start < end)
    {
        // 交换字符
        char temp = *start;
        *start = *end;
        *end = temp;
        
        // 移动指针
        start++;
        end--;
    }
}

int main(void)
{
    char str[] = "Hello, World!";
    printf("原字符串：%s\n", str);
    reverse_string(str);
    printf("反转后：%s\n", str);
    return 0;
}

3.2 字符串大小写转换

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

void to_upper(char *str)
{
    if (str == NULL)
    {
        return;
    }
    
    while (*str != '\0')
    {
        *str = toupper((unsigned char)*str);
        str++;
    }
}

void to_lower(char *str)
{
    if (str == NULL)
    {
        return;
    }
    
    while (*str != '\0')
    {
        *str = tolower((unsigned char)*str);
        str++;
    }
}

int main(void)
{
    char str1[] = "Hello, World!";
    char str2[] = "HELLO, WORLD!";
    
    to_upper(str1);
    printf("转换为大写：%s\n", str1);
    
    to_lower(str2);
    printf("转换为小写：%s\n", str2);
    
    return 0;
}

3.3 字符串去空格

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

char *trim_whitespace(char *str)
{
    if (str == NULL)
    {
        return NULL;
    }
    
    // 去除前导空格
    while (isspace((unsigned char)*str))
    {
        str++;
    }
    
    if (*str == '\0')
    {
        return str;
    }
    
    // 去除尾随空格
    char *end = str + strlen(str) - 1;
    while (end > str && isspace((unsigned char)*end))
    {
        end--;
    }
    
    // 添加结束符
    *(end + 1) = '\0';
    
    return str;
}

int main(void)
{
    char str[] = "   Hello, World!   ";
    printf("原字符串：'%s'\n", str);
    printf("去空格后：'%s'\n", trim_whitespace(str));
    return 0;
}

3.4 字符串替换

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char *replace_string(const char *src, const char *old_str, const char *new_str)
{
    if (src == NULL || old_str == NULL || new_str == NULL)
    {
        return NULL;
    }
    
    size_t src_len = strlen(src);
    size_t old_len = strlen(old_str);
    size_t new_len = strlen(new_str);
    
    if (old_len == 0)
    {
        return strdup(src);
    }
    
    // 计算需要替换的次数
    int count = 0;
    const char *p = src;
    while ((p = strstr(p, old_str)) != NULL)
    {
        count++;
        p += old_len;
    }
    
    // 计算新字符串的长度
    size_t new_str_len = src_len + count * (new_len - old_len);
    
    // 分配内存
    char *result = (char *)malloc(new_str_len + 1);
    if (result == NULL)
    {
        return NULL;
    }
    
    // 执行替换
    char *q = result;
    p = src;
    while ((p = strstr(p, old_str)) != NULL)
    {
        // 复制旧字符串之前的部分
        size_t len = p - src;
        memcpy(q, src, len);
        q += len;
        
        // 复制新字符串
        memcpy(q, new_str, new_len);
        q += new_len;
        
        // 跳过旧字符串
        src = p + old_len;
        p = src;
    }
    
    // 复制剩余部分
    strcpy(q, src);
    
    return result;
}

int main(void)
{
    const char *src = "Hello, World! World is beautiful.";
    const char *old_str = "World";
    const char *new_str = "C Language";
    
    char *result = replace_string(src, old_str, new_str);
    if (result != NULL)
    {
        printf("原字符串：%s\n", src);
        printf("替换后：%s\n", result);
        free(result);
    }
    
    return 0;
}

4. 字符串的内存管理

4.1 字符串的内存分配

4.1.1 栈上分配

1
char str[100];  // 在栈上分配 100 字节的空间
  • 优点：分配和释放速度快
  • 缺点：空间大小固定，可能不够用

4.1.2 堆上分配

1
2
3
4
5
6
char *str = (char *)malloc(100 * sizeof(char));  // 在堆上分配 100 字节的空间
if (str != NULL)
{
    // 使用字符串
    free(str);  // 释放内存
}
  • 优点：空间大小可以动态调整
  • 缺点：需要手动管理内存，容易导致内存泄漏

4.1.3 静态存储区分配

1
static char str[100];  // 在静态存储区分配 100 字节的空间
  • 优点：生命周期长，不需要手动释放
  • 缺点：空间大小固定，可能导致内存浪费

4.2 字符串的内存泄漏

字符串操作中常见的内存泄漏情况：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 错误：内存泄漏
char *get_string(void)
{
    char *str = (char *)malloc(100 * sizeof(char));
    if (str != NULL)
    {
        strcpy(str, "Hello");
    }
    return str;  // 调用者可能忘记释放
}

// 正确的做法
void use_string(void)
{
    char *str = get_string();
    if (str != NULL)
    {
        printf("%s\n", str);
        free(str);  // 手动释放
    }
}

4.3 字符串的缓冲区溢出

字符串操作中常见的缓冲区溢出情况：

1
2
3
4
5
6
7
8
// 错误：缓冲区溢出
char str[10];
strcpy(str, "Hello, World!");  // 字符串长度超过缓冲区大小

// 正确的做法
char str[10];
strncpy(str, "Hello, World!", sizeof(str) - 1);
str[sizeof(str) - 1] = '\0';  // 确保字符串以空字符结尾

5. 字符串的编码和国际化

5.1 ASCII 编码

ASCII（American Standard Code for Information Interchange）是最基本的字符编码，使用 7 位表示 128 个字符。

5.2 扩展 ASCII 编码

扩展 ASCII 使用 8 位表示 256 个字符，包含了一些特殊符号和非英语字符。

5.3 Unicode 编码

Unicode 是一种国际标准编码，旨在包含世界上所有的字符。

5.3.1 UTF-8 编码

UTF-8 是一种变长编码，使用 1-4 个字节表示一个字符：

  • ASCII 字符使用 1 个字节
  • 欧洲和中东字符使用 2 个字节
  • 东亚字符使用 3 个字节
  • 其他字符使用 4 个字节

5.3.2 UTF-16 编码

UTF-16 使用 2 或 4 个字节表示一个字符。

5.3.3 UTF-32 编码

UTF-32 使用 4 个字节表示一个字符。

5.4 多字节字符串

C 语言提供了 <wchar.h> 头文件，用于处理宽字符和多字节字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include <wchar.h>
#include <locale.h>

int main(void)
{
    setlocale(LC_ALL, "");  // 设置本地化环境
    
    wchar_t wstr[] = L"你好，世界！";
    wprintf(L"%ls\n", wstr);
    
    return 0;
}

6. 字符串处理的性能优化

6.1 避免不必要的字符串复制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// 低效：不必要的字符串复制
char *process_string(const char *str)
{
    char *copy = strdup(str);
    // 处理 copy
    free(copy);
    return strdup(str);  // 再次复制
}

// 高效：直接使用原字符串
const char *process_string(const char *str)
{
    // 处理 str（不修改）
    return str;
}

6.2 使用适当的字符串函数

1
2
3
4
5
6
7
8
9
// 低效：使用 strcat 拼接多个字符串
char str[100] = "";
strcat(str, "Hello");
strcat(str, ", ");
strcat(str, "World!");

// 高效：使用 sprintf 或 snprintf
char str[100];
snprintf(str, sizeof(str), "%s%s%s", "Hello", ", ", "World!");

6.3 预分配足够的内存

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
// 低效：频繁重新分配内存
char *build_string(void)
{
    char *str = NULL;
    size_t len = 0;
    
    for (int i = 0; i < 100; i++)
    {
        char temp[10];
        sprintf(temp, "%d", i);
        size_t temp_len = strlen(temp);
        char *new_str = (char *)realloc(str, len + temp_len + 1);
        if (new_str == NULL)
        {
            free(str);
            return NULL;
        }
        str = new_str;
        strcat(str, temp);
        len += temp_len;
    }
    
    return str;
}

// 高效：预分配足够的内存
char *build_string(void)
{
    char *str = (char *)malloc(1000 * sizeof(char));  // 预分配足够的内存
    if (str == NULL)
    {
        return NULL;
    }
    
    str[0] = '\0';
    for (int i = 0; i < 100; i++)
    {
        sprintf(str + strlen(str), "%d", i);
    }
    
    return str;
}

6.4 使用指针操作替代数组下标

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
// 低效：使用数组下标
int count_vowels(const char *str)
{
    int count = 0;
    for (size_t i = 0; i < strlen(str); i++)
    {
        char c = str[i];
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
        {
            count++;
        }
    }
    return count;
}

// 高效：使用指针操作
int count_vowels(const char *str)
{
    int count = 0;
    while (*str != '\0')
    {
        char c = *str;
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u')
        {
            count++;
        }
        str++;
    }
    return count;
}

7. 常见的字符串相关错误和调试

7.1 常见错误

7.1.1 缓冲区溢出

1
2
3
// 错误：缓冲区溢出
char str[10];
strcpy(str, "Hello, World!");  // 字符串长度超过缓冲区大小

7.1.2 空指针解引用

1
2
3
// 错误：空指针解引用
char *str = NULL;
strlen(str);  // 未定义行为

7.1.3 字符串没有以空字符结尾

1
2
3
// 错误：字符串没有以空字符结尾
char str[5] = {'H', 'e', 'l', 'l', 'o'};
strlen(str);  // 未定义行为，会一直搜索直到找到空字符

7.1.4 修改字符串字面量

1
2
3
// 错误：修改字符串字面量
char *str = "Hello";
str[0] = 'h';  // 未定义行为，字符串字面量存储在只读内存中

7.1.5 内存泄漏

1
2
3
4
5
6
7
// 错误：内存泄漏
char *get_string(void)
{
    char *str = (char *)malloc(100 * sizeof(char));
    strcpy(str, "Hello");
    return str;  // 调用者可能忘记释放
}

7.2 调试技巧

7.2.1 使用断言

1
2
3
4
5
6
7
8
9
10
11
#include <assert.h>

char *safe_strcpy(char *dest, size_t dest_size, const char *src)
{
    assert(dest != NULL);
    assert(src != NULL);
    assert(dest_size > 0);
    
    // 函数实现
    // ...
}

7.2.2 使用调试宏

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

#if DEBUG
#define LOG_STRING(str) printf("%s: %s\n", #str, str)
#else
#define LOG_STRING(str) do { } while (0)
#endif

int main(void)
{
    char str[] = "Hello";
    LOG_STRING(str);  // 在调试模式下输出字符串
    return 0;
}

7.2.3 使用内存调试工具

  • Valgrind - 用于检测内存泄漏和内存错误
  • AddressSanitizer - 用于检测内存错误
  • LeakSanitizer - 用于检测内存泄漏

8. 字符串的高级应用示例

8.1 示例 1：简单的字符串解析器

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

// 解析键值对
void parse_key_value(const char *str)
{
    char *copy = strdup(str);
    if (copy == NULL)
    {
        return;
    }
    
    char *token = strtok(copy, ",");
    while (token != NULL)
    {
        char *key = token;
        char *value = strchr(token, '=');
        if (value != NULL)
        {
            *value = '\0';
            value++;
            printf("键: %s, 值: %s\n", key, value);
        }
        token = strtok(NULL, ",");
    }
    
    free(copy);
}

int main(void)
{
    const char *str = "name=John,age=30,city=New York";
    parse_key_value(str);
    return 0;
}

8.2 示例 2：简单的字符串加密

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

// 简单的 Caesar 密码加密
void caesar_encrypt(char *str, int shift)
{
    if (str == NULL)
    {
        return;
    }
    
    while (*str != '\0')
    {
        if (isalpha((unsigned char)*str))
        {
            char base = islower((unsigned char)*str) ? 'a' : 'A';
            *str = (char)(((*str - base + shift) % 26 + 26) % 26 + base);
        }
        str++;
    }
}

// 简单的 Caesar 密码解密
void caesar_decrypt(char *str, int shift)
{
    caesar_encrypt(str, 26 - shift);
}

int main(void)
{
    char str[] = "Hello, World!";
    int shift = 3;
    
    printf("原字符串：%s\n", str);
    caesar_encrypt(str, shift);
    printf("加密后：%s\n", str);
    caesar_decrypt(str, shift);
    printf("解密后：%s\n", str);
    
    return 0;
}

8.3 示例 3：简单的 JSON 解析器

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// 简单的 JSON 解析器（仅支持基本的键值对）
void parse_json(const char *str)
{
    // 跳过空白字符
    while (isspace((unsigned char)*str))
    {
        str++;
    }
    
    // 检查是否是对象
    if (*str != '{')
    {
        printf("不是有效的 JSON 对象\n");
        return;
    }
    str++;
    
    // 解析键值对
    while (*str != '}')
    {
        // 跳过空白字符
        while (isspace((unsigned char)*str))
        {
            str++;
        }
        
        // 解析键
        if (*str != '"')
        {
            printf("无效的键\n");
            return;
        }
        str++;
        
        const char *key_start = str;
        while (*str != '"')
        {
            str++;
        }
        size_t key_len = str - key_start;
        char *key = (char *)malloc(key_len + 1);
        if (key == NULL)
        {
            return;
        }
        strncpy(key, key_start, key_len);
        key[key_len] = '\0';
        str++;
        
        // 跳过冒号和空白字符
        while (isspace((unsigned char)*str))
        {
            str++;
        }
        if (*str != ':')
        {
            printf("缺少冒号\n");
            free(key);
            return;
        }
        str++;
        while (isspace((unsigned char)*str))
        {
            str++;
        }
        
        // 解析值
        const char *value_start = str;
        if (*str == '"')
        {
            // 字符串值
            str++;
            while (*str != '"')
            {
                str++;
            }
        }
        else if (isdigit((unsigned char)*str) || *str == '-')
        {
            // 数字值
            while (isdigit((unsigned char)*str) || *str == '.' || *str == 'e' || *str == 'E' || *str == '+' || *str == '-')
            {
                str++;
            }
        }
        else if (*str == 't' || *str == 'f' || *str == 'n')
        {
            // 布尔值或 null
            if (strncmp(str, "true", 4) == 0)
            {
                str += 4;
            }
            else if (strncmp(str, "false", 5) == 0)
            {
                str += 5;
            }
            else if (strncmp(str, "null", 4) == 0)
            {
                str += 4;
            }
        }
        
        size_t value_len = str - value_start;
        char *value = (char *)malloc(value_len + 1);
        if (value == NULL)
        {
            free(key);
            return;
        }
        strncpy(value, value_start, value_len);
        value[value_len] = '\0';
        
        // 打印键值对
        printf("键: %s, 值: %s\n", key, value);
        
        // 释放内存
        free(key);
        free(value);
        
        // 跳过逗号和空白字符
        while (isspace((unsigned char)*str))
        {
            str++;
        }
        if (*str == ',')
        {
            str++;
        }
        while (isspace((unsigned char)*str))
        {
            str++;
        }
    }
}

int main(void)
{
    const char *json = "{\"name\": \"John\", \"age\": 30, \"city\": \"New York\"}";
    parse_json(json);
    return 0;
}

9. 小结

本章深入介绍了 C 语言中字符串的概念、表示方法、操作技巧以及高级应用。字符串是 C 语言中非常重要的数据类型，在实际编程中经常使用。

9.1 关键知识点

  • 字符串的本质：以空字符 '\0' 结尾的字符序列
  • 字符串的表示：字符数组、字符串字面量、指针
  • 字符串库函数：strlen、strcpy、strcat、strcmp、strchr、strstr 等
  • 安全的字符串函数：strcpy_s、strcat_s、strnlen_s、strtok_s 等
  • 字符串的内存管理：栈分配、堆分配、静态存储区分配
  • 字符串的编码：ASCII、UTF-8、UTF-16、UTF-32
  • 字符串的性能优化：避免不必要的复制、使用适当的函数、预分配内存、使用指针操作
  • 常见错误：缓冲区溢出、空指针解引用、字符串没有以空字符结尾、修改字符串字面量、内存泄漏

9.2 学习建议

  • 多写代码：通过实际编程练习掌握字符串的使用
  • 理解原理：理解字符串的内存表示和库函数的实现原理
  • 注意安全：始终使用安全的字符串函数，避免缓冲区溢出等问题
  • 学习调试：掌握使用调试工具检测和修复字符串相关错误的技巧
  • 关注性能：了解字符串操作的性能特性，编写高效的字符串处理代码

字符串处理是 C 语言编程的基础，掌握好字符串处理技巧对于编写高质量的 C 程序至关重要。通过本章的学习，希望读者能够深入理解字符串的概念，掌握字符串库函数的使用，以及编写安全、高效的字符串处理代码。

在后续章节中，我们将学习结构体和其他复合数据类型，以及文件输入/输出等内容。