11

在一次采访中，我被要求编写一个实现strcpy然后修复它，以便它正确处理重叠的字符串。我的实现如下，非常幼稚。我该如何解决它，以便：

  1. 它检测重叠的字符串和
  2. 检测到后，我们如何处理重叠并继续？
char* my_strcpy(char *a, char *b) {

     if (a == NULL || b == NULL) {
         return NULL;
     }
     if (a > b) {
         //we have an overlap?
         return NULL;
     }
     char *n = a;

     while (*b != '\0') {
         *a = *b;
         a++;
         b++;
     }
     *a = '\0';
     return n;
}

int main(int argc, char *argv[])
{
    char str1[] = "wazzupdude";
    char *after_cpy = my_strcpy(str1 + 2, str1);
    return 0;
}

编辑：

因此，基于@Secure 的答案的一种可能实现是：

char* my_strcpy(char *a, char *b) {

    if (a == NULL || b == NULL) {
        return NULL;
    }

    memmove(a, b, strlen(b) + 1);
    return a;
}

如果我们不依赖memmove，那么

char* my_strcpy(char *a, char *b) {

    if (a == NULL || b == NULL) {
        return NULL;
    }

    if (a == b) {
        return a;
    }

    // case1: b is placed further in the memory
    if ( a <= b && a + strlen(a) > b ) {
        char *n = a;

        while(*b != '\0') {
            *a = *b;
            a++; b++;
        }
        *a = '\0';
        return n;
    }

    // case 2: a is further in memory
    else if ( b <= a && b + strlen(b) > a ) { 
        char *src = b + strlen(b) - 1; // src points to end of b
        char *dest = a;

        while(src != b) {
            *dest = *src;
            dest--; src--;  // not sure about this..
        }
        *a = '\0';
        return a;
    }
}
4

9 回答 9

12

没有便携式方法可以检测到这一点。您必须进行指针比较，并且这些仅在同一个对象中定义。即，如果两个字符串不重叠并且实际上是不同的对象，那么指针比较会给您未定义的行为。

我会让标准库处理这个，通过使用memmove(a, b, strlen(b) + 1).

编辑：

正如史蒂夫杰索普在评论中指出的那样，在这种情况下，实际上有一种可移植但缓慢的方法来检测重叠。比较 b 中的每个地址与 a 的第一个和最后一个地址是否相等。与的相等比较==总是很好定义的。

所以你有这样的事情：

l = strlen(b);
isoverlap = 0;
for (i = 0; i <= l; i++)
{
    if ((b + i == a) || (b + i == a + l))        
    {
        isoverlap = 1;
        break;
    }
}

编辑 2：案例 2 的可视化

您有类似以下数组和指针的内容：

S t r i n g 0 _ _ _ _ _ _ _
^       ^
|       |
b       a

请注意，这b + strlen(b)会导致指向终止 \0 的指针。从后面开始，否则您需要额外处理边缘情况。在那里设置指针是有效的，只是不能取消引用它们。

src = b + strlen(b) + 1;
dst = a + strlen(b) + 1;

S t r i n g 0 _ _ _ _ _ _ _
^       ^     ^       ^  
|       |     |       |
b       a     src     dst

现在也复制了 \0 的复制循环。

while (src > b)
{
    src--; dst--;
    *dst = *src;
}

第一步给出了这个：

src--; dst--;

S t r i n g 0 _ _ _ _ _ _ _
^       ^   ^       ^  
|       |   |       |
b       a   src     dst

*dst = *src;

S t r i n g 0 _ _ _ 0 _ _ _
^       ^   ^       ^  
|       |   |       |
b       a   src     dst

依此类推，直到src最终等于b：

S t r i S t r i n g 0 _ _ _
^       ^              
|       |            
b       a          
src     dst

如果你想要它更hackish，你可以进一步压缩它，但我不推荐这样：

while (src > b)
    *(--dst) = *(--src);
于 2011-09-15T08:15:43.937 回答
4

如果您希望字符串重叠，您可能可以使用 memmove() 。

char* my_strcpy(char *a, char *b)
{
    memmove(a, b, strlen(b) + 1);
    return a;
}
于 2011-09-15T08:16:26.120 回答
4

注意：这里，b是源字符串a的地址，是目标的地址。

与a > b您不一定有重叠。如果

(a <= b && a+strlen(a) >= b) || (b <= a && b+strlen(b) >= a)

那么你有一个重叠。

但是，除了为了采访而检测重叠之外，a > b对于strcpy. 这个想法是这样的：

如果b放在内存中更远的地方（b > a），那么您可以正常复制b到a. 的部分b将被覆盖，但您已经超过了该部分。

如果a放在内存中更远的位置 ( a > b)，则意味着可能通过写入 的第一个位置a，您已经覆盖了b具有更高索引的位置。在这种情况下，您应该向相反的方向复制。所以不要从索引复制0到strlen(b)-1，你应该从复制strlen(b)-1到0。

如果您对这有什么帮助感到困惑，请在纸上绘制两个重叠的数组，并尝试从数组的开头复制一次，从结尾复制一次。在 casea > b和a < b.

请注意，如果a == b，您不需要实际复制任何内容，您只需返回即可。

编辑：我不确定，但阅读其他解决方案，似乎这个答案可能不是完全可移植的。小心那个。

于 2011-09-15T08:23:09.573 回答
3 
if a > b; then
    copy a from the beginning
else if a < b; then
    copy a from the ending
else // a == b
    do nothing

你可以参考一个实现，memmove和我说的很像。

于 2011-09-15T08:14:56.693 回答
1 
if (a>= b && a <= b+strlen(b))) || (b+strlen(b) >= a && b+strlen(b) <= a + strlen(b))

(*) 你应该缓存 strlen(b) 以提高性能

它的作用：
检查a+len[address of a + extra len bytes] 是否在字符串内，或a[address of a] 在字符串内，这些是字符串重叠的唯一可能性。

于 2011-09-15T08:17:06.603 回答
1

我在最近的一次采访中被问到这个问题。我们不必“检测”重叠。我们可以用strcpy这样一种方式来编写重叠地址。关键是从源字符串的末尾而不是从开头复制。

这是一个快速代码。

void str_copy(const char *src, char *dst) 
{
    /* error checks */

    int i = strlen(a); /* may have to account for null character */

    while(i >= 0) 
    {
        dst[i] = src[i];  
        i--; 
    }
}

编辑：这仅在 a < b 时有效。对于 a > b，从头开始复制。

于 2011-09-15T08:18:29.127 回答
1

如果这两个字符串重叠，那么，在复制时，您将在原始字符串a或b指针上运行。

假设strcpy(a, b) 大致意思是a <- b，即第一个参数是拷贝的目的地，那么你只检查拷贝指针是否到达b'''的位置。

您只需要保存b原始位置，并在复制时检查您没有到达它。此外，如果您已到达该位置，请勿写入尾随零。

 char* my_strcpy(char *a, const char *b)
 {

    if ( a == NULL
      || b == NULL )
    {
        return NULL;
    }

    char *n = a;
    const char * oldB = b;

    while( *b != '\0'
       &&  a != oldB )
    {
        *a = *b;
        a++;
        b++;
    }

    if ( a != oldB ) {
        *a = '\0';
    }

    return n;
 }

该算法只是停止复制。也许您想做其他事情，例如标记错误条件，或者在前一个位置添加一个字符串结尾标记（尽管静默失败（就像算法目前所做的那样）不是最好的选择）。

希望这可以帮助。

于 2011-09-15T08:24:21.247 回答
1

即使不使用关系指针比较、memmove或等价物，也可以编写一个版本，在不重叠的情况下strcpy将作为strlenand执行，memcpy在重叠的情况下作为自上而下的副本执行。关键是要利用这样一个事实，即如果读取目标的第一个字节然后用零替换，调用strlen源并将返回的值添加到源指针将产生一个合法的指针，它将等于“麻烦的重叠”案例中的目的地。如果源和目标是不同的对象，则可以安全地计算“源加 strlen”指针并观察到不等于目标。

如果将字符串长度添加到源指针产生目标指针，则用较早读取的值替换零字节并在目标上调用 strlen 将允许代码确定源和目标字符串的结束地址。此外，源字符串的长度将指示指针之间的距离。如果这个值很大（可能大于 16 左右），代码可以有效地将“移动”操作细分为自上而下的 memcpy 操作序列。否则，可以使用自上而下的单字节复制操作循环复制字符串，或者使用“memcpy 到源到缓冲区”/“memcpy 缓冲区到目标”操作的序列[如果大型 memcpy 的每字节成本小于单个字符复制循环的一半，

于 2015-07-09T23:32:12.283 回答
0

这个 SO 条目已经很老了，但我目前正在处理一段旧代码，它用strcpy(). 日志输出中缺少字符。我决定使用以下紧凑的解决方案，该解决方案char由char.

static char *overlapped_strcpy(char *dest, const char *src)
{
  char *dst = dest;

  if (dest == NULL || src == NULL || dest == src)
    return dest;

  do {
    *dst++ = *src;
  } while (*src++);

  return dest;
}

编辑：

正如@Gerhardh 指出的那样，上面的代码仅在dest <= src（我只需要解决这种情况）时才有效。对于这种情况dest > src，情况更复杂。但是，正如其他答案已经提到的那样，从后面复制会导致成功。例如：

if (dest <= src) {
  /* do the above */
} else {
  int i = (int)strlen(src);
  while (i >= 0) {
    dst[i] = src[i];
    i--;
  }
}
于 2020-11-19T16:10:22.947 回答