为什么需要动态字符串？
#include <stdio.h> #include <string.h> void static_string_limitations() { // 问题1：固定大小，无法扩展 char fixed_buffer[50]; strcpy(fixed_buffer, "Hello"); printf("问题1：固定大小限制\n"); printf("当前字符串: %s\n", fixed_buffer); printf("当前长度: %zu\n", strlen(fixed_buffer)); // strcat(fixed_buffer, ", this is a very long string that will cause problems!"); printf("\n问题2：频繁的内存重新分配\n"); char *ptr = malloc(10); strcpy(ptr, "short"); // 需要更长的空间怎么办？ // char *new_ptr = realloc(ptr, 100); // 需要手动管理 printf("\n问题3：性能问题\n"); printf("每次扩展都需要：\n"); printf("1. 分配新内存\n"); printf("2. 复制原内容\n"); printf("3. 释放旧内存\n"); printf("4. 更新指针\n"); }核心思想
动态字符串的核心思想：以空间换时间，减少内存重新分配。
// 基础动态字符串结构 typedef struct { char *data; // 实际存储数据的缓冲区 size_t length; // 当前字符串长度（不包括'\0'） size_t capacity; // 缓冲区总容量（包括'\0'） } DynamicString; // 设计原则： // 1. 容量 >= 长度 + 1（为'\0'留空间） // 2. 指数增长策略：避免频繁重新分配 // 3. 惰性收缩：不会立即缩小，避免震荡基础动态字符串实现
核心函数实现
#include <stdlib.h> #include <string.h> #include <stdarg.h> #include <ctype.h> // 创建动态字符串 DynamicString* ds_create(size_t initial_capacity) { DynamicString *ds = (DynamicString*)malloc(sizeof(DynamicString)); if (ds == NULL) { return NULL; } // 最小容量保证 if (initial_capacity < 16) { initial_capacity = 16; } ds->capacity = initial_capacity; ds->length = 0; ds->data = (char*)malloc(ds->capacity); if (ds->data == NULL) { free(ds); return NULL; } // 初始化为空字符串 ds->data[0] = '\0'; return ds; } // 销毁动态字符串 void ds_destroy(DynamicString *ds) { if (ds == NULL) return; // 安全清除：先清除内容再释放内存 if (ds->data != NULL) { memset(ds->data, 0, ds->capacity); // 清除敏感数据 free(ds->data); } memset(ds, 0, sizeof(DynamicString)); // 清除结构体 free(ds); } // 确保有足够容量（核心函数） static int ds_ensure_capacity(DynamicString *ds, size_t needed) { if (ds == NULL) return 0; // 计算实际需要的大小（包括'\0'） size_t required = needed + 1; // +1 for '\0' if (required <= ds->capacity) { return 1; // 容量足够 } // 指数增长策略：新容量 = 旧容量 * 增长因子 size_t new_capacity = ds->capacity; while (new_capacity < required) { // 增长因子：1.5倍，平衡内存使用和性能 new_capacity = new_capacity + (new_capacity >> 1); // *1.5 // 防止溢出 if (new_capacity < ds->capacity) { new_capacity = required; // 溢出时直接设置为所需大小 break; } } // 分配新内存 char *new_data = (char*)realloc(ds->data, new_capacity); if (new_data == NULL) { return 0; // 内存分配失败 } ds->data = new_data; ds->capacity = new_capacity; printf("容量扩展：%zu -> %zu (需要: %zu)\n", ds->capacity - (new_capacity - ds->capacity), new_capacity, required); return 1; } // 设置字符串内容 int ds_set(DynamicString *ds, const char *str) { if (ds == NULL || str == NULL) return 0; size_t len = strlen(str); // 确保有足够容量 if (!ds_ensure_capacity(ds, len)) { return 0; } // 复制字符串 strcpy(ds->data, str); ds->length = len; return 1; } // 追加字符串 int ds_append(DynamicString *ds, const char *str) { if (ds == NULL || str == NULL) return 0; size_t append_len = strlen(str); size_t new_length = ds->length + append_len; // 确保有足够容量 if (!ds_ensure_capacity(ds, new_length)) { return 0; } // 追加字符串 strcpy(ds->data + ds->length, str); ds->length = new_length; return 1; } // 获取C风格字符串 const char* ds_cstr(const DynamicString *ds) { return (ds == NULL) ? NULL : ds->data; } // 获取长度 size_t ds_length(const DynamicString *ds) { return (ds == NULL) ? 0 : ds->length; } // 获取容量 size_t ds_capacity(const DynamicString *ds) { return (ds == NULL) ? 0 : ds->capacity; }内存增长对比
void growth_strategy_comparison() { const size_t FINAL_SIZE = 1000000; // 目标大小 // 策略1：固定增量（每次增加固定大小） printf("策略1：固定增量（每次+100）\n"); size_t capacity1 = 16; int allocations1 = 0; while (capacity1 < FINAL_SIZE) { capacity1 += 100; allocations1++; } printf("重新分配次数: %d\n", allocations1); printf("最终容量/所需容量: %.2f\n\n", (double)capacity1 / FINAL_SIZE); // 策略2：倍数增长（每次翻倍） printf("策略2：倍数增长（每次*2）\n"); size_t capacity2 = 16; int allocations2 = 0; while (capacity2 < FINAL_SIZE) { capacity2 *= 2; allocations2++; } printf("重新分配次数: %d\n", allocations2); printf("最终容量/所需容量: %.2f\n\n", (double)capacity2 / FINAL_SIZE); // 策略3：1.5倍增长（我们的选择） printf("策略3：1.5倍增长\n"); size_t capacity3 = 16; int allocations3 = 0; while (capacity3 < FINAL_SIZE) { capacity3 = capacity3 + (capacity3 >> 1); // *1.5 allocations3++; } printf("重新分配次数: %d\n", allocations3); printf("最终容量/所需容量: %.2f\n\n", (double)capacity3 / FINAL_SIZE); // 总结 printf("=== 总结 ===\n"); printf("固定增量：内存利用率高，但重新分配次数多\n"); printf("倍数增长：重新分配次数少，但内存浪费严重\n"); printf("1.5倍增长：平衡了性能和内存利用率\n"); }高级功能实现
格式化操作
// 格式化追加（类似sprintf） int ds_append_format(DynamicString *ds, const char *format, ...) { if (ds == NULL || format == NULL) return 0; va_list args; va_start(args, format); // 第一次调用：计算所需长度 va_list args_copy; va_copy(args_copy, args); int needed = vsnprintf(NULL, 0, format, args_copy); va_end(args_copy); if (needed < 0) { va_end(args); return 0; // 格式错误 } size_t new_length = ds->length + needed; // 确保有足够容量 if (!ds_ensure_capacity(ds, new_length)) { va_end(args); return 0; } // 第二次调用：实际格式化 int written = vsnprintf(ds->data + ds->length, ds->capacity - ds->length, format, args); va_end(args); if (written >= 0) { ds->length += written; return 1; } return 0; } // 插入字符串 int ds_insert(DynamicString *ds, size_t pos, const char *str) { if (ds == NULL || str == NULL) return 0; // 验证位置 if (pos > ds->length) { pos = ds->length; // 插入到末尾 } size_t insert_len = strlen(str); size_t new_length = ds->length + insert_len; // 确保有足够容量 if (!ds_ensure_capacity(ds, new_length)) { return 0; } // 移动现有数据，为插入腾出空间 if (pos < ds->length) { memmove(ds->data + pos + insert_len, ds->data + pos, ds->length - pos + 1); // +1 for '\0' } // 插入新字符串 memcpy(ds->data + pos, str, insert_len); ds->length = new_length; // 确保以'\0'结尾 ds->data[ds->length] = '\0'; return 1; } // 删除子串 int ds_erase(DynamicString *ds, size_t pos, size_t count) { if (ds == NULL) return 0; // 验证位置 if (pos >= ds->length) { return 0; // 位置超出范围 } // 调整删除数量 if (pos + count > ds->length) { count = ds->length - pos; } if (count == 0) { return 1; // 没有要删除的 } // 移动数据覆盖要删除的部分 size_t remaining = ds->length - (pos + count); if (remaining > 0) { memmove(ds->data + pos, ds->data + pos + count, remaining); } ds->length -= count; ds->data[ds->length] = '\0'; return 1; } // 子串提取（返回新的动态字符串） DynamicString* ds_substr(const DynamicString *ds, size_t pos, size_t count) { if (ds == NULL) return NULL; // 验证位置 if (pos >= ds->length) { return ds_create(0); // 返回空字符串 } // 调整提取数量 if (pos + count > ds->length) { count = ds->length - pos; } // 创建新的动态字符串 DynamicString *result = ds_create(count + 1); if (result == NULL) return NULL; // 复制子串 strncpy(result->data, ds->data + pos, count); result->data[count] = '\0'; result->length = count; return result; }搜索与替换
// 查找子串（返回位置，未找到返回-1） int ds_find(const DynamicString *ds, const char *substr, size_t start_pos) { if (ds == NULL || substr == NULL) return -1; if (start_pos >= ds->length) { return -1; } char *pos = strstr(ds->data + start_pos, substr); if (pos == NULL) { return -1; } return (int)(pos - ds->data); } // 查找字符（返回位置，未找到返回-1） int ds_find_char(const DynamicString *ds, char ch, size_t start_pos) { if (ds == NULL) return -1; if (start_pos >= ds->length) { return -1; } char *pos = strchr(ds->data + start_pos, ch); if (pos == NULL) { return -1; } return (int)(pos - ds->data); } // 替换所有匹配的子串 int ds_replace_all(DynamicString *ds, const char *old_str, const char *new_str) { if (ds == NULL || old_str == NULL || new_str == NULL) { return 0; } size_t old_len = strlen(old_str); size_t new_len = strlen(new_str); // 如果新旧字符串长度相同，可以原地替换 if (old_len == new_len) { int count = 0; int pos = 0; while ((pos = ds_find(ds, old_str, pos)) != -1) { memcpy(ds->data + pos, new_str, new_len); pos += new_len; count++; } return count; } // 长度不同，需要创建新字符串 // 计算需要多少次替换和最终长度 int replace_count = 0; int pos = 0; while ((pos = ds_find(ds, old_str, pos)) != -1) { replace_count++; pos += old_len; } if (replace_count == 0) { return 0; // 没有需要替换的 } // 计算新长度 size_t length_diff = new_len - old_len; // 可能为负数 size_t new_length = ds->length + (length_diff * replace_count); // 创建临时缓冲区 char *temp = (char*)malloc(new_length + 1); if (temp == NULL) return 0; // 执行替换 char *src = ds->data; char *dest = temp; pos = 0; int next_pos; while ((next_pos = ds_find(ds, old_str, pos)) != -1) { // 复制旧字符串之前的部分 size_t chunk_len = next_pos - pos; memcpy(dest, src + pos, chunk_len); dest += chunk_len; // 复制新字符串 memcpy(dest, new_str, new_len); dest += new_len; // 跳过旧字符串 pos = next_pos + old_len; } // 复制剩余部分 size_t remaining = ds->length - pos; if (remaining > 0) { memcpy(dest, src + pos, remaining); dest += remaining; } // 以'\0'结尾 *dest = '\0'; // 替换原字符串 free(ds->data); ds->data = temp; ds->length = new_length; ds->capacity = new_length + 1; // 更新容量 return replace_count; } // 去除首尾空白字符 void ds_trim(DynamicString *ds) { if (ds == NULL || ds->length == 0) return; // 找到第一个非空白字符 char *start = ds->data; while (*start && isspace((unsigned char)*start)) { start++; } // 找到最后一个非空白字符 char *end = ds->data + ds->length - 1; while (end > start && isspace((unsigned char)*end)) { end--; } // 计算新长度 size_t new_length = (end >= start) ? (end - start + 1) : 0; if (start > ds->data) { // 需要移动数据 memmove(ds->data, start, new_length); } ds->data[new_length] = '\0'; ds->length = new_length; }
