如何在 C 或 C++ 中原地反转字符串? [英] How do you reverse a string in place in C or C++?

问题描述

如何在 C 或 C++ 中反转字符串而不需要单独的缓冲区来保存反转的字符串?

How do you reverse a string in C or C++ without requiring a separate buffer to hold the reversed string?

推荐答案

标准算法是使用指向开始/结束的指针，将它们向内移动，直到它们在中间相遇或交叉.随时交换.

The standard algorithm is to use pointers to the start / end, and walk them inward until they meet or cross in the middle. Swap as you go.

反向 ASCII 字符串，即一个以 0 结尾的数组，其中每个字符都适合 1 个 char.(或其他非多字节字符集).

Reverse ASCII string, i.e. a 0-terminated array where every character fits in 1 char. (Or other non-multibyte character sets).

void strrev(char *head)
{
  if (!head) return;
  char *tail = head;
  while(*tail) ++tail;    // find the 0 terminator, like head+strlen
  --tail;               // tail points to the last real char
                        // head still points to the first
  for( ; head < tail; ++head, --tail) {
      // walk pointers inwards until they meet or cross in the middle
      char h = *head, t = *tail;
      *head = t;           // swapping as we go
      *tail = h;
  }
}

// test program that reverses its args
#include <stdio.h>

int main(int argc, char **argv)
{
  do {
    printf("%s ",  argv[argc-1]);
    strrev(argv[argc-1]);
    printf("%s
", argv[argc-1]);
  } while(--argc);

  return 0;
}

相同的算法适用于已知长度的整数数组，只需使用 tail = start + length - 1 而不是结束查找循环.

The same algorithm works for integer arrays with known length, just use tail = start + length - 1 instead of the end-finding loop.

(编者注:这个答案最初也对这个简单版本使用了异或交换.为了这个流行问题的未来读者的利益而修复.XOR-swap 是强烈不推荐；难以阅读并使您的代码编译效率较低.您可以看到在 Godbolt 编译器资源管理器上 当 xor-swap 为 x86 编译时，asm 循环体有多复杂-64 与 gcc -O3.)

(Editor's note: this answer originally used XOR-swap for this simple version, too. Fixed for the benefit of future readers of this popular question. XOR-swap is highly not recommended; hard to read and making your code compile less efficiently. You can see on the Godbolt compiler explorer how much more complicated the asm loop body is when xor-swap is compiled for x86-64 with gcc -O3.)

(这是异或交换的东西.注意你必须避免与self交换，因为如果*p和*q 是相同的位置，您将使用 ^a==0 将其归零.异或交换取决于有两个不同的位置，将它们用作临时存储.)

(This is XOR-swap thing. Take care to note that you must avoid swapping with self, because if *p and *q are the same location you'll zero it with a^a==0. XOR-swap depends on having two distinct locations, using them each as temporary storage.)

编者注:您可以使用 tmp 变量将 SWP 替换为安全的内联函数.

Editor's note: you can replace SWP with a safe inline function using a tmp variable.

#include <bits/types.h>
#include <stdio.h>

#define SWP(x,y) (x^=y, y^=x, x^=y)

void strrev(char *p)
{
  char *q = p;
  while(q && *q) ++q; /* find eos */
  for(--q; p < q; ++p, --q) SWP(*p, *q);
}

void strrev_utf8(char *p)
{
  char *q = p;
  strrev(p); /* call base case */

  /* Ok, now fix bass-ackwards UTF chars. */
  while(q && *q) ++q; /* find eos */
  while(p < --q)
    switch( (*q & 0xF0) >> 4 ) {
    case 0xF: /* U+010000-U+10FFFF: four bytes. */
      SWP(*(q-0), *(q-3));
      SWP(*(q-1), *(q-2));
      q -= 3;
      break;
    case 0xE: /* U+000800-U+00FFFF: three bytes. */
      SWP(*(q-0), *(q-2));
      q -= 2;
      break;
    case 0xC: /* fall-through */
    case 0xD: /* U+000080-U+0007FF: two bytes. */
      SWP(*(q-0), *(q-1));
      q--;
      break;
    }
}

int main(int argc, char **argv)
{
  do {
    printf("%s ",  argv[argc-1]);
    strrev_utf8(argv[argc-1]);
    printf("%s
", argv[argc-1]);
  } while(--argc);

  return 0;
}

• 为什么，是的，如果输入被中断，这将在该位置之外愉快地交换.
• 在 UNICODE 中破坏时的有用链接:http://www.macchiato.com/unicode/chart/
• 此外，超过 0x10000 的 UTF-8 未经测试(因为我似乎没有任何字体，也没有耐心使用十六进制编辑器)

示例:

$ ./strrev Räksmörgås ░▒▓○◔◑◕●

░▒▓○◔◑◕● ●◕◑◔○▓▒░

Räksmörgås sågrömskäR

./strrev verrts/.

这篇关于如何在 C 或 C++ 中原地反转字符串?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！