Einen String in C umkehren

Ich habe ein Reverse-String-Programm entwickelt. Ich frage mich, ob es einen besseren Weg gibt, dies zu tun, und ob mein Code potenzielle Probleme hat. Ich möchte einige fortgeschrittene Funktionen von C üben.

char* reverse_string(char *str)
{
    char temp;
    size_t len = strlen(str) - 1;
    size_t i;
    size_t k = len;

    for(i = 0; i < len; i++)
    {
        temp = str[k];
        str[k] = str[i];
        str[i] = temp;
        k--;

        /* As 2 characters are changing place for each cycle of the loop
           only traverse half the array of characters */
        if(k == (len / 2))
        {
            break;
        }
    }
}

Wenn Sie erweiterte Funktionen von C üben möchten, wie wäre es mit Zeigern? Wir können auch zum Spaß Makros und Xor-Swaps einwerfen!

#include <string.h> // for strlen()

// reverse the given null-terminated string in place
void inplace_reverse(char * str)
{
  if (str)
  {
    char * end = str + strlen(str) - 1;

    // swap the values in the two given variables
    // XXX: fails when a and b refer to same memory location
#   define XOR_SWAP(a,b) do\
    {\
      a ^= b;\
      b ^= a;\
      a ^= b;\
    } while (0)

    // walk inwards from both ends of the string, 
    // swapping until we get to the middle
    while (str < end)
    {
      XOR_SWAP(*str, *end);
      str++;
      end--;
    }
#   undef XOR_SWAP
  }
}

EIN Zeiger (z.B char *von rechts nach links gelesen als a Zeiger auf a char) ist ein Datentyp in C, der verwendet wird, um auf den Speicherort eines anderen Werts zu verweisen. In diesem Fall ist der Ort, an dem a char wird gelagert. Wir können Dereferenzierung
Zeiger, indem Sie ihnen ein voranstellen *, was uns den an diesem Ort gespeicherten Wert gibt. Also der gespeicherte Wert bei str ist *str.

Wir können einfache Arithmetik mit Zeigern machen. Wenn wir einen Zeiger inkrementieren (oder dekrementieren), verschieben wir ihn einfach, um auf die nächste (oder vorherige) Speicherstelle für diesen Werttyp zu verweisen. Das Erhöhen von Zeigern unterschiedlicher Typen kann den Zeiger um eine unterschiedliche Anzahl von Bytes bewegen, da unterschiedliche Werte in C unterschiedliche Bytegrößen haben.

Hier verwenden wir einen Zeiger, um auf den ersten unverarbeiteten zu verweisen
char der Saite (str) und eine andere, um auf die letzte (end). Wir tauschen ihre Werte (*str und *end) und bewegen Sie die Zeiger nach innen in die Mitte der Zeichenfolge. Einmal str >= endentweder zeigen beide auf dasselbe charwas bedeutet, dass unsere ursprüngliche Zeichenfolge eine ungerade Länge hatte (und die mittlere char muss nicht rückgängig gemacht werden) oder wir haben alles bearbeitet.

Um das Austauschen durchzuführen, habe ich a definiert Makro. Makros sind Textersetzungen, die vom C-Präprozessor durchgeführt werden. Sie unterscheiden sich stark von Funktionen, und es ist wichtig, den Unterschied zu kennen. Wenn Sie eine Funktion aufrufen, arbeitet die Funktion mit einer Kopie der Werte, die Sie ihr geben. Wenn Sie ein Makro aufrufen, führt es einfach eine textuelle Ersetzung durch – die Argumente, die Sie ihm geben, werden also direkt verwendet.

Da ich nur die benutzt habe XOR_SWAP Makro einmal, war es wahrscheinlich übertrieben, es zu definieren, aber es machte deutlicher, was ich tat. Nachdem der C-Präprozessor das Makro erweitert hat, sieht die While-Schleife so aus:

    while (str < end)
    {
      do { *str ^= *end; *end ^= *str; *str ^= *end; } while (0);
      str++;
      end--;
    }

Beachten Sie, dass die Makroargumente einmal für jede Verwendung in der Makrodefinition angezeigt werden. Das kann sehr nützlich sein – kann aber bei falscher Anwendung auch Ihren Code brechen. Wenn ich zum Beispiel die Inkrement-/Dekrement-Anweisungen und den Makroaufruf in eine einzige Zeile komprimiert hätte, wie z

      XOR_SWAP(*str++, *end--);

Dann würde sich dies erweitern

      do { *str++ ^= *end--; *end-- ^= *str++; *str++ ^= *end--; } while (0);

Was hat verdreifachen die Inkrement/Dekrement-Operationen und führt nicht wirklich den Austausch durch, den es tun soll.

Wo wir gerade beim Thema sind, Sie sollten wissen was xoder (^) meint. Es ist eine grundlegende arithmetische Operation – wie Addition, Subtraktion, Multiplikation, Division, außer dass es normalerweise nicht in der Grundschule gelehrt wird. Es kombiniert zwei ganze Zahlen Stück für Stück – wie eine Addition, aber wir kümmern uns nicht um die Überträge. 1^1 = 0, 1^0 = 1,
0^1 = 1, 0^0 = 0.

Ein bekannter Trick besteht darin, xor zu verwenden, um zwei Werte zu vertauschen. Dies funktioniert aufgrund von drei grundlegenden Eigenschaften von xor: x ^ 0 = x, x ^ x = 0 und x ^ y = y ^ x für alle Werte x und y. Angenommen, wir haben zwei Variablen a und b die zunächst zwei Werte speichern
va und vb.

  // initially:
  // a == va
  // b == vb
  a ^= b;
  // now: a == va ^ vb
  b ^= a;
  // now: b == vb ^ (va ^ vb)
  //        == va ^ (vb ^ vb)
  //        == va ^ 0
  //        == va
  a ^= b;
  // now: a == (va ^ vb) ^ va
  //        == (va ^ va) ^ vb
  //        == 0 ^ vb
  //        == vb

Die Werte werden also vertauscht. Dies hat einen Fehler – wann a und b sind die gleiche Variable:

  // initially:
  // a == va
  a ^= a;
  // now: a == va ^ va
  //        == 0
  a ^= a;
  // now: a == 0 ^ 0
  //        == 0
  a ^= a;
  // now: a == 0 ^ 0
  //        == 0

Seit wir str < enddas passiert im obigen Code nie, also sind wir in Ordnung.

Während wir um die Korrektheit besorgt sind, sollten wir unsere Grenzfälle überprüfen. Das if (str) Linie sollte sicherstellen, dass uns keine gegeben wurde NULL Zeiger für Zeichenfolge. Was ist mit der leeren Zeichenfolge ""? Brunnen strlen("") == 0also werden wir initialisieren end wie str - 1was bedeutet, dass die while (str < end) Bedingung ist nie wahr, also tun wir nichts. Welches ist richtig.

Es gibt eine Menge C zu entdecken. Viel Spass damit!

Aktualisieren: mmw spricht einen guten Punkt an, nämlich dass Sie etwas vorsichtig sein müssen, wie Sie dies aufrufen, da es an Ort und Stelle funktioniert.

 char stack_string[] = "This string is copied onto the stack.";
 inplace_reverse(stack_string);

Das funktioniert gut, da stack_string ist ein Array, dessen Inhalt mit der gegebenen String-Konstante initialisiert wird. Jedoch

 char * string_literal = "This string is part of the executable.";
 inplace_reverse(string_literal);

Wird dazu führen, dass Ihr Code zur Laufzeit flammt und stirbt. Das ist, weil string_literal zeigt lediglich auf die Zeichenfolge, die als Teil Ihrer ausführbaren Datei gespeichert ist – was normalerweise Speicher ist, den Sie vom Betriebssystem nicht bearbeiten dürfen. In einer glücklicheren Welt würde Ihr Compiler dies wissen und beim Kompilieren einen Fehler ausgeben, der Ihnen das mitteilt string_literal muss vom Typ sein char const * da Sie den Inhalt nicht ändern können. Dies ist jedoch nicht die Welt, in der mein Compiler lebt.

Es gibt einige Hacks, die Sie ausprobieren könnten, um sicherzustellen, dass sich etwas Speicher auf dem Stack oder im Heap befindet (und daher bearbeitet werden kann), aber sie sind nicht unbedingt portabel, und es könnte ziemlich hässlich sein. Ich bin jedoch mehr als glücklich, die Verantwortung dafür dem Funktionsaufrufer zu überlassen. Ich habe ihnen gesagt, dass diese Funktion an Ort und Stelle Speicher manipuliert, es liegt in ihrer Verantwortung, mir ein Argument zu liefern, das dies zulässt.

Nur eine Neuordnung und Sicherheitsüberprüfung. Ich habe auch Ihren nicht verwendeten Rückgabetyp entfernt. Ich denke, das ist sicher und sauber, wie es wird:

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

void reverse_string(char *str)
{
    /* skip null */
    if (str == 0)
    {
        return;
    }

    /* skip empty string */
    if (*str == 0)
    {
        return;
    }

    /* get range */
    char *start = str;
    char *end = start + strlen(str) - 1; /* -1 for \0 */
    char temp;

    /* reverse */
    while (end > start)
    {
        /* swap */
        temp = *start;
        *start = *end;
        *end = temp;

        /* move */
        ++start;
        --end;
    }
}


int main(void)
{
    char s1[] = "Reverse me!";
    char s2[] = "abc";
    char s3[] = "ab";
    char s4[] = "a";
    char s5[] = "";

    reverse_string(0);

    reverse_string(s1);
    reverse_string(s2);
    reverse_string(s3);
    reverse_string(s4);
    reverse_string(s5);

    printf("%s\n", s1);
    printf("%s\n", s2);
    printf("%s\n", s3);
    printf("%s\n", s4);
    printf("%s\n", s5);

    return 0;
}

Bearbeitet, sodass end nicht auf einen möglicherweise fehlerhaften Speicherort zeigt, wenn strlen 0 ist.

Sie können Ihre setzen (len/2) Test in der for-Schleife:

for(i = 0,k=len-1 ; i < (len/2); i++,k--)
{
        temp = str[k];
        str[k] = str[i];
        str[i] = temp;

}

Dieses komplette Programm zeigt, wie ich es machen würde. Denken Sie daran, dass ich C geschrieben habe, als die meisten von Ihnen Whippersnappers ein Glitzern in den Augen Ihrer Mutter waren, also ist es altmodisch, macht den Job, lange Var-Namen sind für Weicheier. Korrigieren Sie das, wenn Sie möchten, ich bin mehr an der Korrektheit des Codes interessiert.

Es verarbeitet NULLen, leere Zeichenfolgen und alle Zeichenfolgengrößen. Ich habe es nicht mit Strings der maximalen Größe (max(size_t)) getestet, aber es sollte funktionieren, und wenn Sie mit so großen Strings umgehen, sind Sie sowieso verrückt 🙂

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

char *revStr (char *str) {
    char tmp, *src, *dst;
    size_t len;
    if (str != NULL)
    {
        len = strlen (str);
        if (len > 1) {
            src = str;
            dst = src + len - 1;
            while (src < dst) {
                tmp = *src;
                *src++ = *dst;
                *dst-- = tmp;
            }
        }
    }
    return str;
}

char *str[] = {"", "a", "ab", "abc", "abcd", "abcde"};

int main(int argc, char *argv[]) {
    int i;
    char s[10000];
    for (i=0; i < sizeof(str)/sizeof(str[0]); i++) {
        strcpy (s, str[i]);
        printf ("'%s' -> '%s'\n", str[i], revStr(s));
    }
    return 0;
}

Die Ausgabe davon ist:

'' -> ''
'a' -> 'a'
'ab' -> 'ba'
'abc' -> 'cba'
'abcd' -> 'dcba'
'abcde' -> 'edcba'

Versuche dies:

reverse_string(NULL);
reverse_string("");

Sie könnten Ihre for-Schleife-Deklaration ändern, um den Code kürzer zu machen:

char* reverse_string(char *str)
{
    char temp;
    size_t len = strlen(str) - 1;
    size_t stop = len/2;
    size_t i,k;

    for(i = 0, k = len; i < stop; i++, k--)
    {
        temp = str[k];
        str[k] = str[i];
        str[i] = temp;
    }
    return str;
}

Benutzt niemand mehr Pointer?

void inplace_rev( char * s ) {
  char t, *e = s + strlen(s);
  while ( --e > s ) { t = *s;*s++=*e;*e=t; }
}

EDIT: Entschuldigung, habe gerade das obige XOR-Beispiel bemerkt …