Wie kehrt man eine Zeichenfolge in C oder C++ um?

Lesezeit: 8 Minuten

Wie kehren Sie eine Zeichenfolge in C oder C++ um, ohne dass ein separater Puffer für die umgekehrte Zeichenfolge erforderlich ist?

Wie kehrt man eine Zeichenfolge in C oder C um
Greg Rogers

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

Dies ist der einfachste Weg in C++.

  • In C++ wird ein String durch die String-Klasse dargestellt. Er hat nicht nach “Zeichenstern” oder “Zeichenklammern” gefragt. Bleib edel, C.

    – Jokon

    30. August 2011 um 21:53 Uhr

  • @fredsbend, die “lächerlich lange” Version der ausgewählten Antwort behandelt einen Fall, den diese einfache Antwort nicht hat – UTF-8-Eingabe. Es zeigt, wie wichtig es ist, das Problem vollständig zu spezifizieren. Außerdem ging es um Code, der auch in C funktionieren würde.

    – Markieren Sie Lösegeld

    16. August 2013 um 14:45 Uhr


  • Diese Antwort behandelt den Fall, wenn Sie eine UTF-8-fähige Zeichenfolgenklasse (oder möglicherweise eine UTF-8-Zeichenklasse mit std::basic_string) verwenden. Außerdem lautete die Frage “C oder C++”, nicht “C und C++”. Nur C++ ist “C oder C++”.

    – Taiwee

    5. Juli 2016 um 18:54 Uhr

  • Dies wird UTF-8-Multibyte-Strings vollständig brechen und in der heutigen Zeit ein totaler Nichtstarter sein.

    – Cameron Lowell Palmer

    27. Januar 2021 um 19:18 Uhr

Lesen Sie Kernighan und 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;
    }
}

  • Getestet auf meinem iPhone ist dies um etwa 15% langsamer als die Verwendung von Rohzeigeradressen

    – jjxtra

    29. April 2013 um 20:16 Uhr

  • Sollte die Variable “c” nicht ein char statt ein int sein?

    – Weniger Draht

    17. November 2013 um 17:25 Uhr

  • Es ist wichtig, in diesem Beispiel zu beachten, dass die Zeichenfolge s muss in Form eines Arrays deklariert werden. Mit anderen Worten, char s[] = "this is ok" eher, als char *s="cannot do this" weil letzteres zu einer String-Konstante führt, die nicht geändert werden kann

    – Benutzer1527227

    9. April 2014 um 1:50 Uhr

  • Mit einer Entschuldigung bei “The Godfather” …. “Leave the guns, bring the K&R”. Als C-Fanatiker würde ich Zeiger verwenden, da sie für dieses Problem einfacher und unkomplizierter sind, aber der Code wäre weniger portierbar für C #, Java usw.

    Benutzer1899861

    27. November 2014 um 2:14 Uhr

  • @Eric Dies läuft nicht in O(log(n))-Zeit. Es wird in O (n) ausgeführt, wenn Sie sich auf die Anzahl der Zeichenvertauschungen beziehen, die der Code ausführt, für n der Zeichenfolgenlänge werden n Vertauschungen durchgeführt. Wenn Sie über die Anzahl der ausgeführten Schleifen sprechen, ist es immer noch O (n) – wenn auch O (n / 2), aber Sie lassen die Konstanten in Big O-Notation fallen.

    – Stefan Fuchs

    18. Dezember 2016 um 18:43 Uhr

1647197409 944 Wie kehrt man eine Zeichenfolge in C oder C um
Anders Eurenius

Der Standardalgorithmus besteht darin, Zeiger auf den Start / das Ende zu verwenden und sie nach innen zu führen, bis sie sich in der Mitte treffen oder kreuzen. Wechseln Sie unterwegs.


Umgekehrter ASCII-String, dh ein 0-terminiertes Array, in dem jedes Zeichen in 1 passt char. (Oder andere Nicht-Multibyte-Zeichensätze).

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;
}

Derselbe Algorithmus funktioniert für Integer-Arrays mit bekannter Länge, verwenden Sie einfach tail = start + length - 1 anstelle der Endfindungsschleife.

(Anmerkung des Herausgebers: Diese Antwort verwendete ursprünglich XOR-Swap auch für diese einfache Version. Zum Nutzen zukünftiger Leser dieser beliebten Frage behoben. XOR-Swap ist höchst nicht empfohlen; schwer zu lesen und Ihren Code weniger effizient kompilieren. Du kannst sehen im Godbolt-Compiler-Explorer wie viel komplizierter der Rumpf der asm-Schleife ist, wenn xor-swap für x86-64 mit gcc -O3 kompiliert wird.)


Ok, gut, reparieren wir die UTF-8-Zeichen …

(Dies ist eine XOR-Swap-Sache. Beachten Sie, dass Sie vermeiden muss Austausch mit sich selbst, denn wenn *p und *q an der gleichen Stelle sind, nullen Sie sie mit a^a==0. XOR-Swap hängt davon ab, zwei unterschiedliche Speicherorte zu haben, die jeweils als temporärer Speicher verwendet werden.)

Anmerkung des Herausgebers: Sie können SWP mithilfe einer tmp-Variablen durch eine sichere Inline-Funktion ersetzen.

#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;
}
  • Warum, ja, wenn der Eingang gebohrt ist, wird dieser fröhlich außerhalb des Ortes tauschen.
  • Nützlicher Link bei Vandalismus im UNICODE: http://www.macchiato.com/unicode/chart/
  • Außerdem ist UTF-8 über 0x10000 nicht getestet (da ich anscheinend weder eine Schriftart dafür noch die Geduld habe, einen Hexeditor zu verwenden).

Beispiele:

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

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

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

./strrev verrts/.

  • Es gibt keinen guten Grund, XOR-Swap außerhalb eines Wettbewerbs mit verschleiertem Code zu verwenden.

    – Chris Conway

    13. Oktober 2008 um 17:02 Uhr

  • Sie denken, “in-place” bedeutet “kein zusätzlicher Speicher”, nicht einmal O(1)-Speicher für Temporäre? Was ist mit dem Platz auf dem Stack für str und die Absenderadresse?

    – Chris Conway

    13. Oktober 2008 um 17:30 Uhr

  • @Bill, das ist nicht das, was die gängige Definition von „vor Ort“ bedeutet. In-Place-Algorithmen dürfen zusätzlichen Speicher verwenden. Die Größe dieses zusätzlichen Speichers darf jedoch nicht von der Eingabe abhängen, dh sie muss konstant sein. Daher ist das Austauschen von Werten unter Verwendung von zusätzlichem Speicher vollständig vorhanden.

    – Konrad Rudolf

    13. Oktober 2008 um 17:31 Uhr

  • Dies nicht positiv bewerten, bis der xor-Swap verschwindet.

    – Adam Rosenfield

    23. Januar 2010 um 21:42 Uhr

  • Das XOR-Swapping ist langsamer als das Swappen über Register auf modernen Out-of-Order-Prozessoren.

    – Patrick Schlüter

    15. August 2011 um 17:42 Uhr

Wie kehrt man eine Zeichenfolge in C oder C um
Chris Conway

Non-Evil C, unter der Annahme des üblichen Falls, in dem die Zeichenfolge nullterminiert ist char Array:

#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--;
  }
}

1647197409 455 Wie kehrt man eine Zeichenfolge in C oder C um
Karl Philipp

Es ist schon eine Weile her und ich weiß nicht mehr, welches Buch mir diesen Algorithmus beigebracht hat, aber ich fand ihn ziemlich genial und einfach zu verstehen:

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);

Eine Visualisierung dieses Algorithmus, mit freundlicher Genehmigung von slashdottir:

Visualisierung des Algorithmus zum Umkehren einer Zeichenfolge an Ort und Stelle

  • Es ist eine interessante Variante, ja. Sollte technisch eine sein size_t obwohl.

    – Pryftan

    21. Februar 2020 um 17:14 Uhr

Beachten Sie, dass das Schöne an std::reverse ist, dass es damit funktioniert char * Saiten und std::wstringist genauso gut wie std::stringS

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

  • Es ist eine interessante Variante, ja. Sollte technisch eine sein size_t obwohl.

    – Pryftan

    21. Februar 2020 um 17:14 Uhr

1647197410 464 Wie kehrt man eine Zeichenfolge in C oder C um
Juan Pablo Califano

Wenn Sie nach NULL-terminierten Puffern suchen, sind die meisten hier veröffentlichten Lösungen in Ordnung. Aber, wie Tim Farley bereits betont hat, funktionieren diese Algorithmen nur, wenn man davon ausgehen kann, dass ein String semantisch ein Array von Bytes ist (dh Single-Byte-Strings), was meiner Meinung nach eine falsche Annahme ist.

Nehmen Sie zum Beispiel die Zeichenfolge „año“ (Jahr auf Spanisch).

Die Unicode-Codepunkte sind 0x61, 0xf1, 0x6f.

Betrachten Sie einige der am häufigsten verwendeten Codierungen:

Latin1 / iso-8859-1 (Single-Byte-Codierung, 1 Zeichen ist 1 Byte und umgekehrt):

Original:

0x61, 0xf1, 0x6f, 0x00

Umkehren:

0x6f, 0xf1, 0x61, 0x00

Das Ergebnis ist in Ordnung

UTF-8:

Original:

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

Umkehren:

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

Das Ergebnis ist Kauderwelsch und eine illegale UTF-8-Sequenz

UTF-16-Big-Endian:

Original:

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

Das erste Byte wird als NUL-Terminator behandelt. Es findet keine Rückfahrt statt.

UTF-16-Little-Endian:

Original:

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

Das zweite Byte wird als NUL-Terminator behandelt. Das Ergebnis ist 0x61, 0x00, eine Zeichenfolge, die das Zeichen „a“ enthält.

  • std::reverse funktioniert für Zwei-Byte-Unicode-Typen, solange Sie wstring verwenden.

    – Sonnenfinsternis

    13. Oktober 2008 um 19:02 Uhr

  • Ich bin mit C++ nicht sehr vertraut, aber ich vermute, dass jede seriöse Standardbibliotheksfunktion, die sich mit Zeichenfolgen befasst, in der Lage sein wird, mit verschiedenen Codierungen umzugehen, also stimme ich Ihnen zu. Mit “diesen Algorithmen” meinte ich die hier geposteten Ad-hoc-Reverse-Funktionen.

    – Juan Pablo Califano

    13. Oktober 2008 um 19:10 Uhr

  • Leider gibt es in Standard-C++ keine “respektable Funktion, die mit Strings umgeht”.

    – Jem

    30. März 2012 um 14:08 Uhr

  • @Eclipse Wenn es ein Ersatzpaar umkehrt, ist das Ergebnis nicht mehr korrekt. Unicode ist eigentlich kein Zeichensatz mit fester Breite

    – phuklv

    17. Mai 2014 um 3:55 Uhr

  • Was ich an dieser Antwort mag, ist, dass sie die tatsächliche Reihenfolge der Bytes zeigt (obwohl Endianness etwas sein könnte – ah, ich sehe, Sie haben es tatsächlich in Betracht gezogen) und wie es entweder richtig oder falsch ist. Aber ich denke, die Antwort würde verbessert, wenn Sie Code einfügen würden, der dies demonstriert.

    – Pryftan

    21. Februar 2020 um 17:19 Uhr

998730cookie-checkWie kehrt man eine Zeichenfolge in C oder C++ um?

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy