如何在 C 或 C++ 中反转字符串而不需要单独的缓冲区来保存反转的字符串?
标准算法是使用指向开始/结束的指针,并将它们向内移动,直到它们在中间相遇或交叉。随走随换。
反转 ASCII 字符串,即一个以 0 结尾的数组,其中每个字符都适合 1 char。(或其他非多字节字符集)。
char
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\n", argv[argc-1]); } while(--argc); return 0; }
相同的算法适用于已知长度的整数数组,只是使用tail = start + length - 1而不是结束查找循环。
tail = start + length - 1
(编者注:这个答案最初也为这个简单的版本使用了 XOR-swap。为了这个热门问题的未来读者的利益而修复。 强烈不推荐XOR-swap;难以阅读并使您的代码编译效率降低。你可以在 Godbolt 编译器资源管理器上看到,当使用 gcc -O3 为 x86-64 编译 xor-swap 时,asm 循环体要复杂得多。)
(这是 XOR-swap 的事情。请注意,您必须避免与 self 交换,因为如果*p和*q是相同的位置,您将使用 a^a==0 将其归零。XOR-swap 取决于具有两个不同的位置,将它们分别用作临时存储。)
*p
*q
编者注:您可以使用 tmp 变量将 SWP 替换为安全的内联函数。
#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\n", argv[argc-1]); } while(--argc); return 0; }
例子:
$ ./strrev Räksmörgås ░▒▓○◔◑◕● ░▒▓○◔◑◕● ●◕◑◔○▓▒░ Räksmörgås sågrömskäR ./strrev verrts/.