如何在 C 或 C + + 中逆转字符串？

如何在不需要单独缓冲区来保存反向字符串的情况下在 C 或 C + + 中反向字符串？

336249 次浏览
小开 
#include <cstdio>
#include <cstdlib>
#include <string>


void strrev(char *str)
{
if( str == NULL )
return;


char *end_ptr = &str[strlen(str) - 1];
char temp;
while( end_ptr > str )
{
temp = *str;
*str++ = *end_ptr;
*end_ptr-- = temp;
}
}


int main(int argc, char *argv[])
{
char buffer[32];


strcpy(buffer, "testing");
strrev(buffer);
printf("%s\n", buffer);


strcpy(buffer, "a");
strrev(buffer);
printf("%s\n", buffer);


strcpy(buffer, "abc");
strrev(buffer);
printf("%s\n", buffer);


strcpy(buffer, "");
strrev(buffer);
printf("%s\n", buffer);


strrev(NULL);


return 0;
}

这段代码产生以下输出:

gnitset
a
cba
小开 
#include <algorithm>
std::reverse(str.begin(), str.end());

这是 C + + 中最简单的方法。

小开
最佳答案

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

反向 ASCII 字符串，即一个以0结尾的数组，其中每个字符符合1个 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代替终端查找循环即可。

(编者按: 这个答案最初也使用了 XOR 交换来实现这个简单的版本。修正了这个流行问题对未来读者的好处。难以阅读，使代码编译效率降低。当用 gcc-O3为 x86-64编译 xor-swap 时，您可以看到 在 Godbolt 编译器浏览器上的 asm 循环体要复杂得多。)

好吧，让我们修复 UTF-8字符..。

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

编者按: 您可以使用 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;
}
  • 为什么，是的，如果输入阻塞，这将愉快地交换外的地方。
  • 在联合编码中破坏时的有用链接: http://www.macchiato.com/unicode/chart/
  • 另外，UTF-8 over 0x10000是未经测试的(因为我似乎没有任何字体，也没有耐心使用一个己读编辑器)

例子:

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


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


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


./strrev verrts/.
小开

无害的 C，假设字符串是以空结尾的 char数组的常见情况:

#include <stddef.h>
#include <string.h>


/* PRE: str must be either NULL or a pointer to a
* (possibly empty) null-terminated string. */
void strrev(char *str) {
char temp, *end_ptr;


/* If str is NULL or empty, do nothing */
if( str == NULL || !(*str) )
return;


end_ptr = str + strlen(str) - 1;


/* Swap the chars */
while( end_ptr > str ) {
temp = *str;
*str = *end_ptr;
*end_ptr = temp;
str++;
end_ptr--;
}
}
小开

为了完整起见，应该指出，在不同的平台上有字符串的表示，其中每个字符 变化的字节数取决于字符。老派的程序员会把这个称为 双字节字符集。现代程序员在 UTF-8(以及 UTF-16等)中更常遇到这种情况。还有其他类似的编码。

在这些可变宽度编码方案中，这里提供的简单算法(邪恶、 非邪恶或 否则)根本不能正常工作！事实上，它们甚至可能导致字符串变得难以辨认，甚至在编码方案中变成非法字符串。请参阅 胡安 · 帕布罗 · 卡利法诺的回答以获得一些好的示例。

只要您的平台实现的标准 C + + 库(特别是字符串迭代器)适当地考虑到了这一点，那么在这种情况下，return ()可能仍然有效。

小开

请注意，std: : return 的优点在于它可以很好地处理 char *字符串和 std::wstring，就像处理 std::string一样

void strrev(char *str)
{
if (str == NULL)
return;
std::reverse(str, str + strlen(str));
}
小开

如果您正在寻找反向 NULL 终止缓冲区，大多数解决方案张贴在这里是确定的。但是，正如 Tim Farley 已经指出的，这些算法只有在假设字符串在语义上是一个字节数组(即单字节字符串)的情况下才有效，我认为这是一个错误的假设。

以字符串“ año”(西班牙语 year)为例。

Unicode 代码点是0x61,0xf1,0x6f。

考虑一些最常用的编码:

Latin1/iso-8859-1 (单字节编码，1个字符等于1个字节，反之亦然) :

原文:

0x61,0xf1,0x6f，0x00

相反:

0x6f，0xf1,0x61,0x00

结果还可以

UTF-8:

原文:

0x61,0xc3,0xb1,0x6f，0x00

相反:

0x6f，0xb1,0xc3,0x61,0x00

结果是胡言乱语和非法的 UTF-8序列

UTF-16大恩迪安:

原文:

0x00,0x61,0x00,0xf1,0x00,0x6f，0x00,0x00

第一个字节将被视为 NUL 终止符。不会发生任何逆转。

小恩迪安:

原文:

0x61,0x00,0xf1,0x00,0x6f，0x00,0x00,0x00

第二个字节将被视为 NUL 终止符。结果是0x61,0x00，一个包含‘ a’字符的字符串。

小开

读读 Kernighan 和 Ritchie

#include <string.h>


void reverse(char s[])
{
int length = strlen(s) ;
int c, i, j;


for (i = 0, j = length - 1; i < j; i++, j--)
{
c = s[i];
s[i] = s[j];
s[j] = c;
}
}
小开

如果您正在使用 GLib，它有两个函数: G _ strverse ()和 G _ utf8 _ strverse ()

小开

我喜欢 Evgeny 的 K & R 回答。但是，看到一个使用指针的版本是很好的。否则，它本质上是一样的:

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


char *reverse(char *str) {
if( str == NULL || !(*str) ) return NULL;
int i, j = strlen(str)-1;
char *sallocd;
sallocd = malloc(sizeof(char) * (j+1));
for(i=0; j>=0; i++, j--) {
*(sallocd+i) = *(str+j);
}
return sallocd;
}


int main(void) {
char *s = "a man a plan a canal panama";
char *sret = reverse(s);
printf("%s\n", reverse(sret));
free(sret);
return 0;
}
小开

已经有一段时间了，我不记得是哪本书告诉我这个算法的，但我认为它相当巧妙，也很容易理解:

char input[] = "moc.wolfrevokcats";


int length = strlen(input);
int last_pos = length-1;
for(int i = 0; i < length/2; i++)
{
char tmp = input[i];
input[i] = input[last_pos - i];
input[last_pos - i] = tmp;
}


printf("%s\n", input);

这个算法的可视化，由 Slashdottir提供:

Visualization of the algorithm to reverse a string in place

小开

递归函数在适当的位置反转字符串(没有额外的缓冲区，malloc)。

简短，性感的代码，糟糕，糟糕的堆栈使用。

#include <stdio.h>


/* Store the each value and move to next char going down
* the stack. Assign value to start ptr and increment
* when coming back up the stack (return).
* Neat code, horrible stack usage.
*
* val - value of current pointer.
* s - start pointer
* n - next char pointer in string.
*/
char *reverse_r(char val, char *s, char *n)
{
if (*n)
s = reverse_r(*n, s, n+1);
*s = val;
return s+1;
}


/*
* expect the string to be passed as argv[1]
*/
int main(int argc, char *argv[])
{
char *aString;


if (argc < 2)
{
printf("Usage: RSIP <string>\n");
return 0;
}


aString = argv[1];
printf("String to reverse: %s\n", aString );


reverse_r(*aString, aString, aString+1);
printf("Reversed String:   %s\n", aString );


return 0;
}
小开

还有一个:

#include <stdio.h>
#include <strings.h>


int main(int argc, char **argv) {


char *reverse = argv[argc-1];
char *left = reverse;
int length = strlen(reverse);
char *right = reverse+length-1;
char temp;


while(right-left>=1){


temp=*left;
*left=*right;
*right=temp;
++left;
--right;


}


printf("%s\n", reverse);


}
小开

另一种 C + + 方式(尽管我可能会使用 std: : return () myself:) ，因为它更具表现力和更快速)

str = std::string(str.rbegin(), str.rend());

C 方式(或多或少:) 请注意交换异或的技巧, 编译器有时无法优化。

在这种情况下，它通常要慢得多。

char* reverse(char* s)
{
char* beg = s, *end = s, tmp;
while (*end) end++;
while (end-- > beg)
{
tmp  = *beg;
*beg++ = *end;
*end =  tmp;
}
return s;
} // fixed: check history for details, as those are interesting ones
小开 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>


unsigned char * utf8_reverse(const unsigned char *, int);
void assert_true(bool);


int main(void)
{
unsigned char str[] = "mañana mañana";
unsigned char *ret = utf8_reverse(str,  strlen((const char *) str) + 1);


printf("%s\n", ret);
assert_true(0 == strncmp((const char *) ret, "anãnam anañam", strlen("anãnam anañam") + 1));


free(ret);


return EXIT_SUCCESS;
}


unsigned char * utf8_reverse(const unsigned char *str, int size)
{
unsigned char *ret = calloc(size, sizeof(unsigned char*));
int ret_size = 0;
int pos = size - 2;
int char_size = 0;


if (str ==  NULL) {
fprintf(stderr, "failed to allocate memory.\n");
exit(EXIT_FAILURE);
}


while (pos > -1) {


if (str[pos] < 0x80) {
char_size = 1;
} else if (pos > 0 && str[pos - 1] > 0xC1 && str[pos - 1] < 0xE0) {
char_size = 2;
} else if (pos > 1 && str[pos - 2] > 0xDF && str[pos - 2] < 0xF0) {
char_size = 3;
} else if (pos > 2 && str[pos - 3] > 0xEF && str[pos - 3] < 0xF5) {
char_size = 4;
} else {
char_size = 1;
}


pos -= char_size;
memcpy(ret + ret_size, str + pos + 1, char_size);
ret_size += char_size;
}


ret[ret_size] = '\0';


return ret;
}


void assert_true(bool boolean)
{
puts(boolean == true ? "true" : "false");
}
小开

如果使用 ATL/MFC CString，只需调用 CString::MakeReverse()。

小开

如果你不需要储存它，你可以减少这样花费的时间:

void showReverse(char s[], int length)
{
printf("Reversed String without storing is ");
//could use another variable to test for length, keeping length whole.
//assumes contiguous memory
for (; length > 0; length--)
{
printf("%c", *(s+ length-1) );
}
printf("\n");
}
小开

C + + 多字节 UTF-8逆变器

我的想法是，你永远不能只是交换结束，你必须始终移动从开始到结束，通过字符串移动，并寻找“多少字节，这个字符将需要?”我将字符从原始结束位置开始附加，然后将字符从字符串的前面移除。

void StringReverser(std::string *original)
{
int eos = original->length() - 1;
while (eos > 0) {
char c = (*original)[0];
int characterBytes;
switch( (c & 0xF0) >> 4 ) {
case 0xC:
case 0xD: /* U+000080-U+0007FF: two bytes. */
characterBytes = 2;
break;
case 0xE: /* U+000800-U+00FFFF: three bytes. */
characterBytes = 3;
break;
case 0xF: /* U+010000-U+10FFFF: four bytes. */
characterBytes = 4;
break;
default:
characterBytes = 1;
break;
}


for (int i = 0; i < characterBytes; i++) {
original->insert(eos+i, 1, (*original)[i]);
}
original->erase(0, characterBytes);
eos -= characterBytes;
}
}
小开 
void reverseString(vector<char>& s) {
int l = s.size();
char ch ;
int i = 0 ;
int j = l-1;
while(i < j){
s[i] = s[i]^s[j];
s[j] = s[i]^s[j];
s[i] = s[i]^s[j];
i++;
j--;
}
for(char c : s)
cout <<c ;
cout<< endl;
}
小开

在 C + + 中，反过来可以在函数中完成:

#include <algorithm>
#include <string>


void backwards(vector<string> &inputs_ref) {
for (auto i = inputs_ref.begin(); i != inputs_ref.end(); ++i) {
reverse(i->begin(), i->end());
}
}
小开

输入字符串，返回字符串，不需要其他库

std::string reverse_string(std::string &str)
{
const char*buf = str.c_str();
char *start = const_cast<char*>(buf);
char *end = start + strlen(buf) - 1;
char t;


while(start < end)
{
t = *start;
*start = *end;
*end = t;
start ++;
end --;
}
str = buf;
return str;
}

std::string md1 = "abcdefghijklmnopqrstuvwxyz0123456789";
std::cout << reverse_string(md1) << std::endl;


//9876543210zyxwvutsrqponmlkjihgfedcba

提交答案