在C中反转一个字符串

Question

我开发了一个反向字符串程序.我想知道是否有更好的方法来做到这一点,如果我的代码有任何潜在的问题.我期待练习C的一些高级功能.

char* reverse_string(char *str)
{
    char temp;
    size_t len = strlen(str) - 1;
    size_t i;
    size_t k = len;

    for(i = 0; i < len; i++)
    {
        temp = str[k];
        str[k] = str[i];
        str[i] = temp;
        k--;

        /* As 2 characters are changing place for each cycle of the loop
           only traverse half the array of characters */
        if(k == (len / 2))
        {
            break;
        }
    }
}

Answer 1

如果你想练习C的高级功能,指针怎么样？我们可以投入宏和xor-swap以获得乐趣!

#include <string.h> // for strlen()

// reverse the given null-terminated string in place
void inplace_reverse(char * str)
{
  if (str)
  {
    char * end = str + strlen(str) - 1;

    // swap the values in the two given variables
    // XXX: fails when a and b refer to same memory location
#   define XOR_SWAP(a,b) do\
    {\
      a ^= b;\
      b ^= a;\
      a ^= b;\
    } while (0)

    // walk inwards from both ends of the string, 
    // swapping until we get to the middle
    while (str < end)
    {
      XOR_SWAP(*str, *end);
      str++;
      end--;
    }
#   undef XOR_SWAP
  }
}

甲指针(例如char *,从右到左为读指针char)是用来指位置的另一值的存储器在C数据类型.在这种情况下,char存储a的位置.我们可以 通过在前面添加一个指针来取消引用指针*,它为我们提供存储在该位置的值.所以存储的值str是*str.

我们可以使用指针进行简单的算术运算.当我们递增(或递减)指针时,我们只需将其移动以引用该类型值的下一个(或前一个)内存位置.增加不同类型的指针可能会将指针移动不同的字节数,因为不同的值在C中具有不同的字节大小.

这里,我们使用一个指针来引用charstring(str)的第一个未处理 的,而另一个引用指向last(end).我们交换它们的值(*str和*end),并将指针向内移动到字符串的中间.一次str >= end,要么它们都指向相同char,这意味着我们的原始字符串有一个奇数长度(中间char不需要反转),或者我们已经处理了所有内容.

为了进行交换,我已经定义了一个宏.宏是由C预处理器完成的文本替换.它们与功能非常不同,了解差异非常重要.当您调用函数时,该函数将对您提供的值的副本进行操作.当你调用一个宏时,它只是进行文本替换 - 所以你给它的参数是直接使用的.

由于我只使用了XOR_SWAP一次宏,因此定义它可能有点过头了,但它更清楚我在做什么.在C预处理器扩展宏之后,while循环如下所示:

    while (str < end)
    {
      do { *str ^= *end; *end ^= *str; *str ^= *end; } while (0);
      str++;
      end--;
    }

请注意,宏参数每次在宏定义中使用时都会显示一次.这可能非常有用 - 但如果使用不当也会破坏您的代码.例如,如果我已将增量/减量指令和宏调用压缩为单行,例如

      XOR_SWAP(*str++, *end--);

然后这会扩展到

      do { *str++ ^= *end--; *end-- ^= *str++; *str++ ^= *end--; } while (0);

其中增量/减量操作增加了三倍,并且实际上并没有进行它应该执行的交换.

当我们讨论这个主题时,您应该知道xor(^)的含义.这是一个基本的算术运算 - 如加法,减法,乘法,除法,除非它通常不在小学教授.它将两个整数一点一点地组合在一起 - 就像添加一样,但我们并不关心结转. 1^1 = 0,1^0 = 1, 0^1 = 1,0^0 = 0.

一个众所周知的技巧是使用xor来交换两个值.这是因为xor的三个基本属性x ^ 0 = x,x ^ x = 0以及x ^ y = y ^ x所有值x和y.所以说,我们有两个变量a,并b与起初存储两个值 和.vavb

  // initially:
  // a == va
  // b == vb
  a ^= b;
  // now: a == va ^ vb
  b ^= a;
  // now: b == vb ^ (va ^ vb)
  //        == va ^ (vb ^ vb)
  //        == va ^ 0
  //        == va
  a ^= b;
  // now: a == (va ^ vb) ^ va
  //        == (va ^ va) ^ vb
  //        == 0 ^ vb
  //        == vb

所以这些值都是交换的.这确实有一个错误 - 何时a和b是相同的变量:

  // initially:
  // a == va
  a ^= a;
  // now: a == va ^ va
  //        == 0
  a ^= a;
  // now: a == 0 ^ 0
  //        == 0
  a ^= a;
  // now: a == 0 ^ 0
  //        == 0

由于我们str < end,这在上面的代码中从未发生过,所以我们没事.

虽然我们关注正确性,但我们应该检查边缘情况.该if (str)行应确保我们没有给出NULL字符串指针.空字符串""怎么样？那么strlen("") == 0,我们将初始化end为str - 1,这意味着while (str < end)条件永远不会成立,所以我们什么都不做.哪个是对的.

有一堆C要探索.玩得开心!

更新: mmw提出了一个很好的观点,你必须要小心谨慎地调用它,因为它确实可以就地运行.

 char stack_string[] = "This string is copied onto the stack.";
 inplace_reverse(stack_string);

这样可以正常工作,因为它stack_string是一个数组,其内容初始化为给定的字符串常量.然而

 char * string_literal = "This string is part of the executable.";
 inplace_reverse(string_literal);

将导致您的代码在运行时火焰和死亡.这是因为string_literal仅指向作为可执行文件一部分存储的字符串 - 通常是操作系统不允许编辑的内存.在一个更幸福的世界中,您的编译器会知道这一点,并在您尝试编译时发出错误,告诉您string_literal需要类型,char const *因为您无法修改内容.但是,这不是我的编译器所处的世界.

有一些黑客可以尝试确保某些内存在堆栈上或堆中(因此可编辑),但它们不一定是可移植的,而且可能非常难看.但是,我非常乐意将此责任交给函数调用者.我已经告诉他们这个函数可以实现内存操作,他们有责任给我一个允许这样做的参数.

Answer 2

只是重新安排和安全检查.我还删除了你未使用的返回类型.我认为这是安全和干净的:

#include <stdio.h>
#include <string.h>

void reverse_string(char *str)
{
    /* skip null */
    if (str == 0)
    {
        return;
    }

    /* skip empty string */
    if (*str == 0)
    {
        return;
    }

    /* get range */
    char *start = str;
    char *end = start + strlen(str) - 1; /* -1 for \0 */
    char temp;

    /* reverse */
    while (end > start)
    {
        /* swap */
        temp = *start;
        *start = *end;
        *end = temp;

        /* move */
        ++start;
        --end;
    }
}


int main(void)
{
    char s1[] = "Reverse me!";
    char s2[] = "abc";
    char s3[] = "ab";
    char s4[] = "a";
    char s5[] = "";

    reverse_string(0);

    reverse_string(s1);
    reverse_string(s2);
    reverse_string(s3);
    reverse_string(s4);
    reverse_string(s5);

    printf("%s\n", s1);
    printf("%s\n", s2);
    printf("%s\n", s3);
    printf("%s\n", s4);
    printf("%s\n", s5);

    return 0;
}

编辑使得当strlen为0时end不会指向可能错误的内存位置.

Answer 3

您可以将(len/2)测试置于for循环中:

for(i = 0,k=len-1 ; i < (len/2); i++,k--)
{
        temp = str[k];
        str[k] = str[i];
        str[i] = temp;

}

Answer 4

这个完整的程序显示了我将如何做到这一点.请记住,当你们大多数的鞭子被你母亲的眼睛闪烁时,我正在写C,所以这是老式的,有做事的,长期名字都是为了懦夫.修复如果你愿意,我对代码的正确性更感兴趣.

它处理NULL,空字符串和所有字符串大小.我没有用最大尺寸的字符串(max(size_t))测试它但它应该工作,如果你处理大字符串,你仍然是疯了:-)

#include <stdio.h>
#include <string.h>

char *revStr (char *str) {
    char tmp, *src, *dst;
    size_t len;
    if (str != NULL)
    {
        len = strlen (str);
        if (len > 1) {
            src = str;
            dst = src + len - 1;
            while (src < dst) {
                tmp = *src;
                *src++ = *dst;
                *dst-- = tmp;
            }
        }
    }
    return str;
}

char *str[] = {"", "a", "ab", "abc", "abcd", "abcde"};

int main(int argc, char *argv[]) {
    int i;
    char s[10000];
    for (i=0; i < sizeof(str)/sizeof(str[0]); i++) {
        strcpy (s, str[i]);
        printf ("'%s' -> '%s'\n", str[i], revStr(s));
    }
    return 0;
}

输出是:

'' -> ''
'a' -> 'a'
'ab' -> 'ba'
'abc' -> 'cba'
'abcd' -> 'dcba'
'abcde' -> 'edcba'

Answer 5

试试这个:

reverse_string(NULL);
reverse_string("");

Answer 6

您可以更改for循环声明以缩短代码:

char* reverse_string(char *str)
{
    char temp;
    size_t len = strlen(str) - 1;
    size_t stop = len/2;
    size_t i,k;

    for(i = 0, k = len; i < stop; i++, k--)
    {
        temp = str[k];
        str[k] = str[i];
        str[i] = temp;
    }
    return str;
}

Answer 7

没有人再使用指针吗？

void inplace_rev( char * s ) {
  char t, *e = s + strlen(s);
  while ( --e > s ) { t = *s;*s++=*e;*e=t; }
}

编辑:对不起,刚刚注意到上面的XOR示例......

Answer 8

void reverse(char *s)
{
  char *end,temp;
  end = s;
  while(*end != '\0'){
    end++;
  }
  end--;  //end points to last letter now
  for(;s<end;s++,end--){
    temp = *end;
    *end = *s;
    *s = temp; 
  }
}