c - 寻找更好的算法来插入 C 风格字符串 (char *)

Question

插入 char * 缓冲区(C 字符串)的合适算法应该是什么？

我目前正在使用如下所述的东西以及我用来实现这些功能的功能(来自 C 库) 这里我说的是 C 风格的字符串，而不是 C++ 字符串。我不允许使用它。

• 给定一个长度为 N 的字符串 S1，要将其插入另一个长度为 M 的字符串 S2 的位置 P
• 分配一个 M+N+2 长度的临时字符串 tmp//malloc
• 同时重新分配长度为 M+N+2 的 S2//重新分配
• 检查分配和重新分配是否成功
• 将 S2 复制到 tmp 直到 P//memmove
• 连接 S1 和 Tmp//strcat
• 连接 S2+P 和 Tmp//strcat
  我会使用 strcat 但是大数组会导致访问(写入)冲突(strcat)，所以我必须编写自己的 strcat 实现，它工作正常而且我完全不知道为什么它实际上这样做(strcat 的访问冲突)。
• 用 Tmp//memmove 覆盖 S2

这是有效的，但我正在处理大字符串，所以我正在寻找 任何删除 tmp 和任何其他更好的方法 替代我正在使用的功能。另外，是否有任何其他速度优化，因为我会经常使用它？

Answer 1

如果您正在调整目标字符串 S2 的大小，则根本不需要另一个缓冲区。

一种可能是:

1. 重新分配给 M+N+1 - 来自每个字符串的字符数，以及一个用于终止 NUL 的字符数。
2. 考虑到可能的重叠，使用 memmove(不是 memcpy)将所有内容从 P:N+1(包括原始尾随 NUL)移动到缓冲区的末尾。
3. 将 M 个字符从 S1 复制到从 P 开始的空间。没有重叠，因此 memcpy 可以工作。不要在此处使用 strcpy - 您不希望在此处将终止 NUL 添加到目标字符串的中间。

我个人更愿意分配一个正确大小的新缓冲区，而不是重新分配现有缓冲区。部分原因是它可以避免对 P 之后的字符串部分进行双重复制，但主要是为了避免破坏输入字符串，或者如果它们不是由 malloc 分配的则只是崩溃。

对于第 2 步，使用 void *memmove(void *dest, const void *src, size_t n);，您需要将范围 P : N+1 移动到新位置，从P+M，所以:

memmove(S2 + P + M, S2 + P, N - P + 1);

假设目标字符串包含 9 个字符加上 1 个 NUL 终止符 (N=9)，插入的字符串包含 2 个字符 (M=2)，插入位置为 7 (P=7)，这将移动 9 - 7 + 1 = 3 个字节，从位置 7 到位置 7 + 2 = 9，保留位置 7 和 8 以保留要插入的字符串中的 2 个新字符。