c - 健壮的字符串反转

Question

我正在尝试编写一个简单的反转字符串的面试问题。

这是我的代码：

#include <string.h>

char* rev( char* str)
{
    int i,j,l;

    l = strlen(str);

    for(i=0,j=l-1; i<l/2 ; i++, j--)
    {
        str[i] = (str[i] + str[j]);
        str[j] = str[i] - str[j];
        str[j] = str[i] - str[j];
    }

    return str;
}

int main()
{
    char *str = " hello";
    printf("\nthe reverse is %s ...", rev(str));

    return 1;
}

基本上，这个给出了分段错误。

我有以下问题：

我得到分段错误可能是因为字符加起来没有在 ascii 中定义，因此我无法将它们作为字符存储回来，我正在使用 www.codepad.org [我想知道它是否只支持 ascii !!]。我的理解是正确的还是有别的原因。
对于同一平台，我该如何解决问题[我的意思是换成 codepad.org]
在这里，我必须使用一个额外的整数 l 来计算长度。因此，通过就地交换来节省单个字符空间..我正在使用一个额外的 int ！.. 只是为了给面试官留下深刻印象:) ... 这种方法值得吗？
这个是为那些对编写单元测试/API 测试感兴趣的人准备的。我想有一个健壮的实现，所以什么是可能的测试用例。我假设如果面试官问这样一个简单的问题.. 他肯定想要一些非常健壮的实现和测试用例。我想的很少：
- 传递空字符串传递整数
- 字符串传递整数数组而不是 char 数组。
- 很长的弦，
- single char string 特殊字符的字符串。

任何建议/建议都会有所帮助。

score 8 · Accepted Answer

这一行：

char *str = " hello";

可能指向只读存储器。试试这个：

char str[] = " hello";

（您也有一些其他错误，但此更改将修复您的段错误）。

score 7 · Accepted Answer

使用临时变量而不是您的方法进行交换。由于优化，编译器可能会为临时变量使用寄存器。

无论哪种方式，您都错误地实现了交换算法。它应该是

str[i] = str[i] + str[j];
str[j] = str[i] - str[j];
str[i] = str[i] - str[j];

score 5 · Accepted Answer

Kernighan & Ritchie 的C Programming Language的第 62 页显示了一种使用临时变量进行就地字符串反转的算法。

与此类似：

char* rev_string(char* const str)
{
  int i, j;
  char tmp;
  for(i = 0, j = strlen(str)-1; i < j; i++; j--)
  {
    tmp = str[i];
    str[i] = str[j];
    str[j] = tmp;
  }
  return str;
}

这种算法比没有临时变量的算法更容易理解，恕我直言。

至于问题列表中的第 3 项：

作为一名面试官，我希望看到简单、清晰、结构良好的代码。这很让人佩服。诡计不会打动我。特别是在涉及过早优化时。顺便说一句，我的解决方案用一个额外的字符而不是一个 int 来反转字符串。感人的？:)

和项目＃4：

另一个测试用例是未终止的字符串。您的功能是否足够强大以处理这种情况？你的函数只会和它最不健壮的部分一样健壮。由于 strlen 报告的字符串长度不正确，将未终止的字符串传递到我的解决方案中会导致分段错误。不是很健壮。

关于健壮性的重要一点是，您的代码可能是健壮的，但您必须确保您使用的所有其他外部函数也是如此！

score 4 · Accepted Answer

从哪儿开始...

好的，首先您应该知道您的例程将字符串反转到位，换句话说，对原始缓冲区进行了更改。

这意味着你可以做

int main()
{
    char str[] = "hello";
    rev(str);
    printf("\nthe reverse is %s ...", str);

    return 0;
}

并且字符串将被反转。

另一种选择是创建一个新字符串，它是原始字符串的反向副本。算法有些不同，你也应该能够做到这一点。

下一点：

    str[i] = (str[i] + str[j]);
    str[j] = str[i] - str[j];
    str[j] = str[i] - str[j];

被打破。它应该是

    str[i] = str[i] + str[j];
    str[j] = str[i] - str[j];
    str[i] = str[i] - str[j];

但是，正如 ~mathepic 所说，你应该这样做：

    temp = str[i];
    str[i] = str[j];
    str[j] = temp;

另外：键盘使调试代码变得困难。在您自己的计算机上安装编译器和调试器（例如 gcc 和 gdb）。

这些字符加起来是 ascii 中未定义的内容，因此我无法将它们作为字符存储回来，我正在使用 www.codepad.org [我想知道它是否只支持 ascii !!]。我的理解是正确的还是有别的原因。

在大多数 C 实现中（无论如何都在 32 位 PC 上运行），achar是一个 8 位整数。Anint是一个 32 位整数。当你添加或减去两个chars 并且结果超过 8 位时，它会“环绕”到某个其他值，但这个过程是可逆的。

例如，255 + 1 给出 0，但 0 - 1 = 255。（只是一个说明性示例。）这意味着“我不能将它们作为字符存储回来”不是这里的问题。

我想要一个健壮的实现

您想表明您考虑了不同设计选择的成本和收益。如果为您的例程提供 NULL，可能最好引起分段错误，因为这会很快提醒程序员其代码中的错误。

传递空字符串

您必须确保您的代码在这种情况下有效。

传递整数传递整数数组

您不能将整数或a 传递int []给期望 a 的函数char *。在 C 中，您无法判断 a 是否char *真的是字符串或其他东西。

单字符字符串

确保您的例程适用于单个字符字符串，也适用于奇数和偶数字符的字符串。

一串特殊字符

C中没有特殊char的 s（按照惯例，空终止符 '\0' 除外）。但是，多char序列是必须考虑的（反转 UTF-8 字符串与反转常规字符串不同）。但是，如果问题没有具体说明，我认为您不应该担心这一点。

最后三点：

在main()中，return 1;通常表示您的程序失败。return 0;更常见但return EXIT_SUCCESS;最好，尽管您可能需要#include <stdlib.h>.
考虑使用更具描述性的变量名称。
考虑制作一个strnrev()类似于 the和类似函数的函数，如果在那里找不到空终止符，则strncpy()该函数不会超出字符。n

score 2 · Accepted Answer

如果您要在没有临时变量的情况下实现两个字符的交换（这是一个巧妙的技巧，但不是您应该在实践中实际使用的东西），使用“按位异或”而不是加法/减法，或使用unsigned char而不是char，因为有符号算术中的溢出在 C99 标准中是未定义的，猜猜看，gcc 开始利用这种未定义性进行优化。我只是在另一个问题中抱怨另一个不需要的优化案例。

score 0 · Accepted Answer

至于测试：

空参数
空字符串参数
长度 1 个字符串参数
各种其他长度 - 可能是一根长字符串

您当然可以使用以下策略实现测试方法：

通用验证方法

verifyEquals( expected, actual ) { ... }

各种情况下的测试方法：

testReverse() {
    verifyEquals(NULL, rev(NULL));
    verifyEquals("", rev(""));
    verifyEquals("a", rev("a"));
    verifyEquals("ba", rev("ab"));
    verifyEquals("zyx", rev("xyz"));
    verifyEquals("edcba", rev("abcde"));
}

您还可以将交换“算法”重构为单独的过程并对其进行单元测试。

score 0 · Accepted Answer

我得到分段错误可能是因为字符加起来没有在 ascii 中定义，因此我无法将它们作为字符存储回来

我不这么认为。它们都只是 C 中的数字（尽管只有 1 个字节长），但你不应该有任何问题。

我认为（但我不确定）问题出在这个：

char *str = " hello";
printf("\nthe reverse is %s ...", rev(str));

您实际上在做的是创建 char 数组“hello”，它是一个常量数组。这意味着，基本上，你不应该改变它。当您调用 rev 时，它实际上就地更改了数组，因此它试图将新值分配给常量 char。

由于您执行 char* str = "hello"，因此您实际上是在将 "hello" 转换为无符号字符，因此这不会被视为编译时错误。但是因为“hello”是所谓的“字符串文字”，它被创建为可执行文件本身的一部分，即它不在您的程序可以自由更改的内存中。这就是为什么您实际上得到的是运行时段错误，而不是编译时错误（尽管您可能应该收到关于此的警告）。

score 0 · Accepted Answer

谢谢大家的回复。这是每个人都建议更改的代码：

#include <string.h>

char* rev( char* str)
{

int start ,end ,len;

    len = strlen(str);

    for(start =0,end =len-1; start <len/2 ; start ++, end --)
    {
        str[start ] = str[start ] + str[end ];
        str[end ] = str[start ] - str[end ];
        str[start] = str[start ] - str[end ];
    }

    return str;
}

int main()
{

   char str[] = " hello there !";

printf("\n the reverse string is %s ...", rev(str));

    return 1;
}

分段错误是因为 *str 指向只读内存，将其更改为 str[]。感谢卡尔·诺鲁姆指出这一点。

任何测试用例[专门用于 API 测试]？

c - 健壮的字符串反转

8 回答 8

Related

Reference