186

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

4

20 回答 20

484 
#include <algorithm>
std::reverse(str.begin(), str.end());

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

于 2008-10-13T16:39:29.277 回答
167

阅读 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;
    }
}
于 2008-10-14T03:09:24.823 回答
130

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

反转 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-swap。为了这个热门问题的未来读者的利益而修复。 强烈不推荐XOR-swap；难以阅读并使您的代码编译效率降低。你可以在 Godbolt 编译器资源管理器上看到，当使用 gcc -O3 为 x86-64 编译 xor-swap 时，asm 循环体要复杂得多。）

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

（这是 XOR-swap 的事情。请注意，您必须避免与 self 交换，因为如果*p和*q是相同的位置，您将使用 a^a==0 将其归零。XOR-swap 取决于具有两个不同的位置，将它们分别用作临时存储。）

编者注：您可以使用 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;
}
  • 为什么，是的，如果输入是 borked，这会很高兴地在这个地方交换。
  • 破坏 UNICODE 时的有用链接：http: //www.macchiato.com/unicode/chart/
  • 此外，UTF-8 over 0x10000 未经测试（因为我似乎没有任何字体，也没有耐心使用 hexeditor）

例子：

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

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

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

./strrev verrts/.
于 2008-10-13T16:58:34.760 回答
43

char非邪恶的 C，假设字符串是一个以 null 结尾的数组的常见情况：

#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--;
  }
}
于 2008-10-13T17:00:05.553 回答
31

已经有一段时间了，我不记得哪本书教过我这个算法，但我认为它非常巧妙且易于理解：

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提供：

将字符串反转到位的算法的可视化

于 2011-07-03T00:16:19.170 回答
23

请注意，std::reverse 的美妙之处在于它可以与char *字符串和std::wstrings 以及std::strings一起使用

void strrev(char *str)
{
    if (str == NULL)
        return;
    std::reverse(str, str + strlen(str));
}
于 2008-10-13T18:26:36.157 回答
12

为了完整起见，应该指出，在各种平台上都有字符串的表示形式，其中每个字符的字节数根据字符而变化。老派程序员将其称为DBCS（双字节字符集）。现代程序员在UTF-8（以及UTF-16等）中更常遇到这种情况。还有其他这样的编码。

在任何这些可变宽度编码方案中，这里发布的简单算法（邪恶、非邪恶或其他）根本无法正常工作！事实上，它们甚至可能导致字符串变得难以辨认，甚至是该编码方案中的非法字符串。有关一些很好的例子，请参阅Juan Pablo Califano 的回答。

std::reverse() 在这种情况下可能仍然有效，只要您的平台对标准 C++ 库（特别是字符串迭代器）的实现正确考虑到这一点。

于 2008-10-13T18:05:57.243 回答
12

如果您正在寻找反转 NULL 终止的缓冲区，这里发布的大多数解决方案都可以。但是，正如 Tim Farley 已经指出的那样，这些算法只有在假设一个字符串在语义上是一个字节数组（即单字节字符串）是有效的情况下才有效，我认为这是一个错误的假设。

例如，字符串“año”（西班牙语中的年份）。

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 终止符。不会发生逆转。

UTF-16 小端：

原来的：

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

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

于 2008-10-13T18:55:29.830 回答
8

另一种 C++ 方式（虽然我自己可能会使用 std::reverse() :) 更具表现力和更快）

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

C方式（或多或少:)）请注意交换的XOR技巧，编译器有时无法优化它。

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

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
于 2012-09-28T13:10:54.460 回答
6 
#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
于 2008-10-13T16:36:32.480 回答
4

如果您使用 GLib，它有两个函数，g_strreverse()和g_utf8_strreverse()

于 2008-10-14T05:24:47.780 回答
4

我喜欢 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;
}
于 2011-03-15T17:33:27.910 回答
4

用于反转字符串的递归函数（没有额外的缓冲区，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;
}
于 2012-02-22T10:39:46.120 回答
2

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

于 2013-10-31T21:40:22.267 回答
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);

}
于 2012-06-08T19:40:47.697 回答
0 
#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");
}
于 2013-10-30T05:09:46.153 回答
0

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;
  }
}
于 2021-01-27T21:27:24.623 回答
0 
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;
}
于 2021-02-05T21:00:06.750 回答
0

在 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());
    }
}
于 2021-11-14T11:09:42.017 回答
-1

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

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");
}
于 2014-05-17T01:46:58.323 回答