Der Standardalgorithmus besteht darin, Zeiger auf den Anfang / das Ende zu verwenden und sie nach innen zu bewegen, bis sie sich in der Mitte treffen oder kreuzen. Tauschen Sie, während Sie gehen.
Reverse ASCII-Zeichenfolge, dh ein Array mit 0-Terminierung, bei 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 firstfor(; head < tail;++head,--tail){// walk pointers inwards until they meet or cross in the middlechar 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);return0;}
Der gleiche Algorithmus funktioniert für ganzzahlige Arrays mit bekannter Länge. Verwenden Sie einfach tail = start + length - 1anstelle der Endfindungsschleife.
(Anmerkung des Herausgebers: Diese Antwort verwendete ursprünglich XOR-Swap auch für diese einfache Version. Behoben zum Nutzen zukünftiger Leser dieser beliebten Frage. XOR-Swap wird dringend nicht empfohlen ; schwer zu lesen und das Kompilieren Ihres Codes weniger effizient. Sie kann im Godbolt-Compiler-Explorer sehen, wie viel komplizierter der asm-Schleifenkörper ist, wenn xor-swap für x86-64 mit gcc -O3 kompiliert wird.)
Ok, gut, lass uns die UTF-8-Zeichen reparieren ...
(Dies ist eine XOR-Swap-Sache. Beachten Sie, dass Sie das Tauschen mit sich selbst vermeiden müssen , denn wenn *pund an *qderselben Stelle, werden Sie sie mit einem ^ a == 0 auf Null setzen. XOR-Swap hängt von zwei unterschiedlichen Orten ab. jeweils als temporäre Speicherung verwenden.)
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){case0xF:/* U+010000-U+10FFFF: four bytes. */
SWP(*(q-0),*(q-3));
SWP(*(q-1),*(q-2));
q -=3;break;case0xE:/* U+000800-U+00FFFF: three bytes. */
SWP(*(q-0),*(q-2));
q -=2;break;case0xC:/* fall-through */case0xD:/* 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);return0;}
Warum, ja, wenn die Eingabe verzerrt ist, wird dies fröhlich außerhalb des Ortes ausgetauscht.
Außerdem ist UTF-8 über 0x10000 nicht getestet (da ich anscheinend keine Schriftart dafür habe und auch nicht die Geduld, einen Hexeditor zu verwenden).
Es gibt keinen guten Grund, XOR-Swap außerhalb eines verschleierten Code-Wettbewerbs zu verwenden.
Chris Conway
28
Sie denken, "an Ort und Stelle" bedeutet "kein zusätzlicher Speicher", nicht einmal O (1) Speicher für Provisorien? Was ist mit dem Platz auf dem Stapel für str und der Absenderadresse?
Chris Conway
55
@ Bill, das ist nicht das, was die übliche Definition von "an Ort und Stelle" bedeutet. In-Place-Algorithmen können 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 durch zusätzlichen Speicher vollständig vorhanden.
Konrad Rudolph
19
Nicht abstimmen, bis der XOR-Tausch weg ist.
Adam Rosenfield
34
Der XOR-Austausch ist langsamer als der Austausch über das Register auf modernen Prozessoren, die nicht in Ordnung sind.
In C ++ wird eine Zeichenfolge durch die Zeichenfolgenklasse dargestellt. Er fragte nicht nach "Char Star" oder "Char Brackets". Bleiben Sie edel, C.
Jokoon
10
@fredsbend, die "lächerlich lange" Version der ausgewählten Antwort behandelt einen Fall, den diese einfache Antwort nicht tut - 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.
Mark Ransom
5
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 ++".
Taywee
161
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 langsamer als die Verwendung von rohen
Zeigeradressen
3
Sollte die Variable "c" nicht ein Zeichen anstelle eines int sein?
Lesswire
17
In diesem Beispiel ist zu beachten, dass die Zeichenfolge sin einer Array-Form deklariert werden muss. Mit anderen Worten, char s[] = "this is ok"anstatt char *s="cannot do this"weil letztere zu einer Zeichenfolgenkonstante führt, die nicht geändert werden kann
user1527227
3
Mit entschuldigt sich bei "The Godfather" .... "Lass die Waffen, bring den K & R". Als C-Fanatiker würde ich Zeiger verwenden, da diese für dieses Problem einfacher und unkomplizierter sind, aber der Code wäre für C #, Java usw. weniger portabel.
2
@Eric Dies wird nicht in der Zeit O (log (n)) ausgeführt. Es wird in O (n) ausgeführt, wenn Sie sich auf die Anzahl der Zeichenwechsel beziehen, die der Code ausführt. Für n Zeichenfolgenlänge werden n Auslagerungen durchgeführt. Wenn Sie über die Anzahl der durchgeführten Schleifen sprechen, ist es immer noch O (n) - wenn auch O (n / 2), aber Sie lassen die Konstanten in der Big O-Notation fallen.
Stephen Fox
62
Umkehren einer Zeichenfolge an Ort und Stelle (Visualisierung):
Cool! Womit haben Sie das erstellt? Ich denke, die Antwort würde verbessert, wenn ein Link dazu eingefügt würde.
Pryftan
Die Implementierung dieses Algorithmus ist tatsächlich in dieser Antwort .
Karlphillip
Können Sie das ein wenig erklären, damit die Antwort nicht unbrauchbar wird, wenn der Bildlink stirbt?
SS Anne
41
Nicht böses C, unter der Annahme, dass die Zeichenfolge ein nullterminiertes charArray ist:
#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--;}}
Anstatt eine while-Schleife zum Suchen des Endzeigers zu verwenden, können Sie nicht so etwas wie end_ptr = str + strlen (str) verwenden. Ich weiß, dass das praktisch dasselbe tun wird, aber ich finde es klarer.
Peter Kühne
Meinetwegen. Ich habe versucht (und bin gescheitert), den Fehler in der Antwort von @ uvote zu vermeiden.
Chris Conway
Abgesehen von einer möglichen Leistungsverbesserung mit vielleicht int tempsieht diese Lösung am besten aus. +1
chux - Monica am
@ chux-ReinstateMonica Ja. Es ist wunderschön. Persönlich würde ich die () s aus dem !(*str)obwohl entfernen .
Pryftan
@ PeterKühne Ja oder auf der strchr()Suche nach '\0'. Ich dachte an beides. Keine Notwendigkeit für eine Schleife.
Pryftan
35
Sie verwenden einen std::reverseAlgorithmus aus der C ++ Standard Library.
Die Standardvorlagenbibliothek ist ein vorstandardisierter Begriff. Der C ++ - Standard erwähnt dies nicht und frühere STL-Komponenten befinden sich in der C ++ - Standardbibliothek.
Nemanja Trifunovic
16
richtig. Ich frage mich immer, warum so viele Leute es immer noch "STL" nennen, obwohl es nur dazu dient, die Sache zu verwirren. wäre schöner, wenn mehr Leute wie Sie wären und es einfach "C ++ Standard Library" oder STL nennen und "STandard Library" sagen :)
Johannes Schaub - litb
27
Es ist eine Weile her und ich erinnere mich nicht, welches Buch mir diesen Algorithmus beigebracht hat, aber ich fand ihn ziemlich genial und einfach zu verstehen:
#include <Algorithmus> Ich habe vergessen, es zu schreiben und dann die Antwort bearbeitet, aber es wurde nicht gespeichert, deshalb fehlte der Name.
user2628229
Obwohl dies auch meine Antwort gewesen wäre, nur neugierig, weil das OP gefragt hat "ohne Puffer, um die umgekehrte Zeichenfolge zu halten" (im Grunde genommen In-Place-Swap), wie kann man beweisen, dass dies der Fall ist? Erklärt man nur, dass es intern std :: iter_swap <> verwendet und von beiden Endpunkten bis zur Mitte des Puffers iteriert? OP fragte sowohl nach C als auch nach C ++, dies ist nur für C ++ (können wir nur hoffen, dass <string.h> die Methode strrev () hat?)
HidekiAI
21
Beachten Sie, dass das Schöne an std :: reverse ist, dass es mit char *Strings und std::wstrings genauso gut funktioniert wie mit std::strings
Einerseits möchte ich mich übergeben, weil Sie C ++ verwendet haben, andererseits ist es eine schöne, schöne, absolut schöne Sache, jemanden zu sehen, der C ++ verwendet, der das nicht *nach Typ und sondern nach Namen schreibt . Wunderbar. Ich gebe zu, dass ich so etwas wie ein Purist bin, aber ich erschrecke jedes Mal, wenn ich Code wie sehe char* str;.
Pryftan
11
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 angenommen werden kann, dass eine Zeichenfolge semantisch ein Array von Bytes (dh Einzelbyte-Zeichenfolgen) ist, 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 ( Einzelbyte- Codierung, 1 Zeichen ist 1 Byte und umgekehrt):
Original:
0x61, 0xf1, 0x6f, 0x00
Umkehren:
0x6f, 0xf1, 0x61, 0x00
Das Ergebnis ist OK
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 Umkehrung 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.
Eclipse
Ich bin mit C ++ nicht sehr vertraut, aber ich vermute, dass jede seriöse Standardbibliotheksfunktion, die sich mit Zeichenfolgen befasst, unterschiedliche Codierungen verarbeiten kann, daher stimme ich Ihnen zu. Mit "diesen Algorithmen" meinte ich die hier veröffentlichten Ad-hoc-Umkehrfunktionen.
Juan Pablo Califano
Leider gibt es in Standard-C ++ keine "seriöse Funktion, die sich mit Strings befasst".
Jem
@Eclipse Wenn ein Ersatzpaar umgekehrt wird, ist das Ergebnis nicht mehr korrekt. Unicode ist eigentlich kein Zeichensatz mit fester Breite
phuclv
Was mir an dieser Antwort gefällt, 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 sich verbessern, wenn Sie einen Code einbauen würden, der dies demonstriert.
Pryftan
11
Der Vollständigkeit halber sei darauf hingewiesen, dass es auf verschiedenen Plattformen Darstellungen von Zeichenfolgen gibt, bei denen die Anzahl der Bytes pro Zeichen je nach Zeichen variiert . Old-School-Programmierer würden dies als DBCS (Double Byte Character Set) bezeichnen . Moderne Programmierer begegnen diesem häufiger in UTF-8 (sowie in UTF-16 und anderen). Es gibt auch andere solche Codierungen.
In jedem dieser Codierungsschemata mit variabler Breite würden die hier veröffentlichten einfachen Algorithmen ( böse , nicht böse oder auf andere Weise ) überhaupt nicht richtig funktionieren! Tatsächlich könnten sie sogar dazu führen, dass die Zeichenfolge unleserlich wird oder sogar eine unzulässige Zeichenfolge in diesem Codierungsschema. In der Antwort von Juan Pablo Califano finden Sie einige gute Beispiele.
std :: reverse () würde in diesem Fall möglicherweise immer noch funktionieren, solange die Implementierung der Standard-C ++ - Bibliothek durch Ihre Plattform (insbesondere String-Iteratoren) dies ordnungsgemäß berücksichtigt.
std :: reverse berücksichtigt dies NICHT. Es kehrt den Werttyp um. Im Fall std :: string werden die Zeichen umgekehrt. Keine Charaktere.
MSalters
Sagen Sie lieber, dass wir Programmierer der alten Schule DBCS kennen, aber auch UTF-8: denn wir alle wissen, dass Programmierer wie Süchtige sind, wenn sie sagen: "Noch eine Zeile und ich werde aufhören!" Ich bin mir sicher, dass einige Programmierer irgendwann aufhören, aber ehrlich gesagt ist das Programmieren für mich wirklich eine Sucht. Ich bekomme Abhebungen, wenn ich nicht programmiere. Es ist ein guter Punkt, den Sie hier hinzufügen. Ich mag C ++ nicht (ich habe mich wirklich sehr bemüht, es zu mögen, auch wenn ich einiges davon schreibe, aber es ist für mich, gelinde gesagt, immer noch ästhetisch unattraktiv), also kann ich dort keinen Kommentar abgeben, aber Sie machen trotzdem einen guten Punkt habe eine +1.
Pryftan
5
Ein anderer C ++ - Weg (obwohl ich wahrscheinlich selbst std :: reverse () verwenden würde :) als ausdrucksstärker und schneller)
str = std::string(str.rbegin(), str.rend());
Der C-Weg (mehr oder weniger :)) und bitte seien Sie vorsichtig mit dem XOR-Trick zum Tauschen, Compiler können das manchmal nicht optimieren.
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
Ich würde verwenden strlen, um das Ende der Zeichenfolge zu finden, wenn es möglicherweise lang ist. Eine gute Bibliotheksimplementierung verwendet SIMD-Vektoren, um schneller als 1 Byte pro Iteration zu suchen. Bei sehr kurzen Zeichenfolgen while (*++end);wird dies jedoch durchgeführt, bevor ein Bibliotheksfunktionsaufruf mit der Suche beginnt.
Peter Cordes
@PeterCordes gut, stimmte zu, strlen sollte sowieso für die Lesbarkeit verwendet werden. Für längere Saiten sollten Sie die Länge trotzdem immer in einer Varialbe halten. strlen on SIMD wird normalerweise als Beispiel mit diesem Haftungsausschluss angegeben, der keine echte Anwendung ist, oder zumindest vor 5 Jahren, als der Code geschrieben wurde. ;)
pprzemek
1
Wenn Sie möchten, dass dies auf echten CPUs schnell läuft, verwenden Sie SIMD-Shuffles, um in 16B-Blöcken das Gegenteil zu tun. : P zB auf x86 kann _mm_shuffle_epi8(PSHUFB) die Reihenfolge eines 16B-Vektors umkehren, wenn der richtige Shuffle-Kontrollvektor gegeben ist. Es kann wahrscheinlich mit einer gewissen Geschwindigkeit mit nahezu sorgfältiger Optimierung ausgeführt werden, insbesondere mit AVX2.
Peter Cordes
char* beg = s-1hat undefiniertes Verhalten (zumindest wenn es sauf das erste Element eines Arrays zeigt, was der häufigste Fall ist). while (*++end);hat undefiniertes Verhalten, wenn ses sich um eine leere Zeichenfolge handelt.
Melpomene
@pprzemek Nun, Sie machen die Behauptung, dass s-1das Verhalten definiert wurde, auch wenn es sauf das erste Element eines Arrays verweist. Sie sollten also in der Lage sein, den Standard zur Unterstützung zu zitieren.
@uvote, benutze nicht strcpy. Je. Wenn Sie so etwas wie strcpy verwenden müssen, verwenden Sie strncpy. strcpy ist gefährlich. Übrigens sind C und C ++ zwei separate Sprachen mit separaten Funktionen. Ich denke, Sie verwenden Header-Dateien, die nur in C ++ verfügbar sind. Brauchen Sie also wirklich eine Antwort in C?
Onorio Catenacci
6
strcpy ist absolut sicher, wenn der Programmierer die Größe seiner Arrays verfolgen kann. Viele würden argumentieren, dass strncpy weniger sicher ist, da es nicht garantiert, dass die resultierende Zeichenfolge nullterminiert ist. Auf jeden Fall ist hier nichts falsch daran, dass uvote strcpy verwendet.
Robert Gamble
1
@Onorio Catenacci, strcpy ist nicht gefährlich, wenn Sie wissen, dass die Quellzeichenfolge in den Zielpuffer passt, wie in den im obigen Code angegebenen Fällen. Außerdem füllt strncpy die bis zu der im Größenparameter angegebene Anzahl von Zeichen auf Null, wenn noch Platz übrig ist, was möglicherweise nicht erwünscht ist.
Chris Young
3
Jeder, der strcpy nicht richtig verwenden kann, sollte nicht in C programmieren.
Robert Gamble
2
@ Robert Gamble, ich stimme zu. Da ich jedoch keine Möglichkeit kenne, Leute davon abzuhalten, in C zu programmieren, unabhängig von ihrer Kompetenz, empfehle ich normalerweise dagegen.
#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");return0;}
aString = argv[1];
printf("String to reverse: %s\n", aString );
reverse_r(*aString, aString, aString+1);
printf("Reversed String: %s\n", aString );return0;}
Das ist eine ziemlich unterhaltsame Lösung. Sie sollten eine Ablaufverfolgung wie printf hinzufügen ("% * s> [% d] reverse_r ('% c',% p ="% s ",% p ="% s "). \ n ", Tiefe," ", Tiefe, Wert, s, (s? s:" null "), n, (n? n:" null ")); am Anfang und <am Ende.
Benoît
Das Drücken charauf den Stapel zählt nicht als "an Ort und Stelle". Vor allem nicht, wenn Sie tatsächlich 4 * 8B pro Zeichen drücken (auf einem 64-Bit-Computer: 3 Argumente + eine Absenderadresse).
Peter Cordes
Die ursprüngliche Frage lautet: "Wie können Sie eine Zeichenfolge in C oder C ++ umkehren, ohne dass ein separater Puffer für die umgekehrte Zeichenfolge erforderlich ist?" - Es war nicht erforderlich, „an Ort und Stelle“ zu tauschen. Diese Lösung erwähnt auch die schlechte Stapelverwendung von Anfang an. Werde ich wegen des schlechten Leseverständnisses anderer Leute abgewählt?
Simon Peverett
1
Ich würde es nicht "sexy" nennen, aber ich würde sagen, dass es demonstrativ und lehrreich ist. Wenn die Rekursion richtig verwendet wird, kann sie sehr wertvoll sein. Es sollte jedoch darauf hingewiesen werden, dass - zuletzt wusste ich - C nicht einmal einen Stapel an sich benötigt; es macht jedoch Rekursion. In beiden Fällen handelt es sich um ein Beispiel für eine Rekursion, die bei richtiger Verwendung sehr nützlich und wertvoll sein kann. Ich glaube nicht, dass ich jemals gesehen habe, wie es verwendet wurde, um eine Zeichenfolge umzukehren.
Dies demonstriert die Zeigerarithmetik, ähnlich wie meine Antwort, kombiniert sie jedoch mit Swap. Ich glaube, diese Antwort trägt tatsächlich viel dazu bei. Sie sollten in der Lage sein, diese Art von Code zu verstehen, bevor Sie eine Milliarde Bibliotheken als Abhängigkeiten hinzufügen, um ein einfaches Textfeld zu erhalten (etwas, das ich in modernen Anwendungen, mit denen ich arbeiten kann, viel zu oft sehe)
Stimmt, aber dies druckt nur die umgekehrte Reihenfolge aus, oder? (Ich benutze kein C ++, also macht die .put () vielleicht nicht das, was ich denke).
Pryftan
-1
Wenn Sie es nicht speichern müssen, können Sie den Zeitaufwand folgendermaßen reduzieren:
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 memoryfor(; length >0; length--){
printf("%c",*(s+ length-1));}
printf("\n");}
Ich scheine die einzige Antwort zu sein, die keinen Puffer oder keine temporäre Variable hat. Ich benutze die Länge der Schnur, aber die anderen, die dies tun, fügen eine weitere für den Kopf (gegen den Schwanz) hinzu. Ich gehe davon aus, dass die Standard-Rückwärtsfunktion die Variable über einen Swap oder etwas anderes speichert. Daher habe ich den Eindruck, dass dies unter der Annahme von Zeigermathematik und UTF-Typ-Aufstellung möglicherweise die einzige Antwort ist, die die Frage tatsächlich beantwortet. Die hinzugefügten printf () können herausgenommen werden. Ich habe es nur getan, um das Ergebnis besser zu sehen. Ich habe das aus Geschwindigkeitsgründen geschrieben. Keine zusätzlichen Zuweisungen oder Vars. Wahrscheinlich der schnellste Algorithmus zum Anzeigen von reverse str ()
Stephen J
-3
Hier ist meine Einstellung zu C. Habe es zum Üben gemacht und versucht, so präzise wie möglich zu sein! Sie geben eine Zeichenfolge über die Befehlszeile ein, dh ./Programmname "Geben Sie hier eine Zeichenfolge ein"
Es ist ein unlesbares Durcheinander, aber Sie werden anscheinend nicht den kürzestmöglichen Code ( Code Golf ) verwenden, da einige Variablennamen mehr als ein Zeichen enthalten.
Peter Cordes
-4
Aber ich denke, der XOR-Swap-Algorithmus ist der beste ...
char str[]={"I am doing reverse string"};char* pStr = str;for(int i =0; i !=((int)strlen(str)-1)/2; i++){char b =*(pStr+i);*(pStr+i)=*(pStr+strlen(str)-1-i);*(pStr+strlen(str)-1-i)= b;}
Ein Aufruf von strlen()in der Schleifenbedingung und im Schleifenkörper wird möglicherweise nicht optimiert.
Peter Cordes
-5
Hier ist der sauberste, sicherste und einfachste Weg, einen String in C ++ umzukehren (meiner Meinung nach):
#include<string>void swap(std::string& str,int index1,int index2){char temp = str[index1];
str[index1]= str[index2];
str[index2]= temp;}void reverse(std::string& str){for(int i =0; i < str.size()/2; i++)
swap(str, i, str.size()- i -1);}
Eine Alternative ist die Verwendung std::swap, aber ich mag es, meine eigenen Funktionen zu definieren - es ist eine interessante Übung und Sie brauchen includenichts extra.
Dies ist optimierter Code in der Sprache C zum Umkehren einer Zeichenfolge ... Und es ist einfach; Verwenden Sie einfach einen einfachen Zeiger, um die Arbeit zu erledigen ...
Antworten:
Der Standardalgorithmus besteht darin, Zeiger auf den Anfang / das Ende zu verwenden und sie nach innen zu bewegen, bis sie sich in der Mitte treffen oder kreuzen. Tauschen Sie, während Sie gehen.
Reverse ASCII-Zeichenfolge, dh ein Array mit 0-Terminierung, bei dem jedes Zeichen in 1 passt
char
. (Oder andere Nicht-Multibyte-Zeichensätze).Der gleiche Algorithmus funktioniert für ganzzahlige 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. Behoben zum Nutzen zukünftiger Leser dieser beliebten Frage. XOR-Swap wird dringend nicht empfohlen ; schwer zu lesen und das Kompilieren Ihres Codes weniger effizient. Sie kann im Godbolt-Compiler-Explorer sehen, wie viel komplizierter der asm-Schleifenkörper ist, wenn xor-swap für x86-64 mit gcc -O3 kompiliert wird.)
Ok, gut, lass uns die UTF-8-Zeichen reparieren ...
(Dies ist eine XOR-Swap-Sache. Beachten Sie, dass Sie das Tauschen mit sich selbst vermeiden müssen , denn wenn
*p
und an*q
derselben Stelle, werden Sie sie mit einem ^ a == 0 auf Null setzen. XOR-Swap hängt von zwei unterschiedlichen Orten ab. jeweils als temporäre Speicherung verwenden.)Anmerkung des Herausgebers: Sie können SWP mithilfe einer tmp-Variablen durch eine sichere Inline-Funktion ersetzen.
Beispiele:
quelle
Dies ist der einfachste Weg in C ++.
quelle
Lesen Sie Kernighan und Ritchie
quelle
s
in einer Array-Form deklariert werden muss. Mit anderen Worten,char s[] = "this is ok"
anstattchar *s="cannot do this"
weil letztere zu einer Zeichenfolgenkonstante führt, die nicht geändert werden kannUmkehren einer Zeichenfolge an Ort und Stelle (Visualisierung):
quelle
Nicht böses C, unter der Annahme, dass die Zeichenfolge ein nullterminiertes
char
Array ist:quelle
int temp
sieht diese Lösung am besten aus. +1!(*str)
obwohl entfernen .strchr()
Suche nach'\0'
. Ich dachte an beides. Keine Notwendigkeit für eine Schleife.Sie verwenden einen
std::reverse
Algorithmus aus der C ++ Standard Library.quelle
Es ist eine Weile her und ich erinnere mich nicht, welches Buch mir diesen Algorithmus beigebracht hat, aber ich fand ihn ziemlich genial und einfach zu verstehen:
quelle
size_t
obwohl sein.Verwenden Sie die Methode std :: reverse von STL :
Sie müssen die "Algorithmus" -Bibliothek einschließen
#include<algorithm>
.quelle
Beachten Sie, dass das Schöne an std :: reverse ist, dass es mit
char *
Strings undstd::wstring
s genauso gut funktioniert wie mitstd::string
squelle
*
nach Typ und sondern nach Namen schreibt . Wunderbar. Ich gebe zu, dass ich so etwas wie ein Purist bin, aber ich erschrecke jedes Mal, wenn ich Code wie sehechar* str;
.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 angenommen werden kann, dass eine Zeichenfolge semantisch ein Array von Bytes (dh Einzelbyte-Zeichenfolgen) ist, 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 ( Einzelbyte- Codierung, 1 Zeichen ist 1 Byte und umgekehrt):
UTF-8:
UTF-16 Big Endian:
UTF-16 Little Endian:
quelle
Der Vollständigkeit halber sei darauf hingewiesen, dass es auf verschiedenen Plattformen Darstellungen von Zeichenfolgen gibt, bei denen die Anzahl der Bytes pro Zeichen je nach Zeichen variiert . Old-School-Programmierer würden dies als DBCS (Double Byte Character Set) bezeichnen . Moderne Programmierer begegnen diesem häufiger in UTF-8 (sowie in UTF-16 und anderen). Es gibt auch andere solche Codierungen.
In jedem dieser Codierungsschemata mit variabler Breite würden die hier veröffentlichten einfachen Algorithmen ( böse , nicht böse oder auf andere Weise ) überhaupt nicht richtig funktionieren! Tatsächlich könnten sie sogar dazu führen, dass die Zeichenfolge unleserlich wird oder sogar eine unzulässige Zeichenfolge in diesem Codierungsschema. In der Antwort von Juan Pablo Califano finden Sie einige gute Beispiele.
std :: reverse () würde in diesem Fall möglicherweise immer noch funktionieren, solange die Implementierung der Standard-C ++ - Bibliothek durch Ihre Plattform (insbesondere String-Iteratoren) dies ordnungsgemäß berücksichtigt.
quelle
Ein anderer C ++ - Weg (obwohl ich wahrscheinlich selbst std :: reverse () verwenden würde :) als ausdrucksstärker und schneller)
Der C-Weg (mehr oder weniger :)) und bitte seien Sie vorsichtig mit dem XOR-Trick zum Tauschen, Compiler können das manchmal nicht optimieren.
In diesem Fall ist es normalerweise viel langsamer.
quelle
strlen
, um das Ende der Zeichenfolge zu finden, wenn es möglicherweise lang ist. Eine gute Bibliotheksimplementierung verwendet SIMD-Vektoren, um schneller als 1 Byte pro Iteration zu suchen. Bei sehr kurzen Zeichenfolgenwhile (*++end);
wird dies jedoch durchgeführt, bevor ein Bibliotheksfunktionsaufruf mit der Suche beginnt._mm_shuffle_epi8
(PSHUFB) die Reihenfolge eines 16B-Vektors umkehren, wenn der richtige Shuffle-Kontrollvektor gegeben ist. Es kann wahrscheinlich mit einer gewissen Geschwindigkeit mit nahezu sorgfältiger Optimierung ausgeführt werden, insbesondere mit AVX2.char* beg = s-1
hat undefiniertes Verhalten (zumindest wenn ess
auf das erste Element eines Arrays zeigt, was der häufigste Fall ist).while (*++end);
hat undefiniertes Verhalten, wenns
es sich um eine leere Zeichenfolge handelt.s-1
das Verhalten definiert wurde, auch wenn ess
auf das erste Element eines Arrays verweist. Sie sollten also in der Lage sein, den Standard zur Unterstützung zu zitieren.Dieser Code erzeugt diese Ausgabe:
quelle
Wenn Sie GLib verwenden, hat es zwei Funktionen dafür, g_strreverse () und g_utf8_strreverse ()
quelle
Ich mag Evgenys K & R-Antwort. Es ist jedoch schön, eine Version mit Zeigern zu sehen. Ansonsten ist es im Wesentlichen dasselbe:
quelle
Rekursive Funktion zum Umkehren einer Zeichenfolge (kein zusätzlicher Puffer, malloc).
Kurzer, sexy Code. Schlechte, schlechte Stapelnutzung.
quelle
char
auf den Stapel zählt nicht als "an Ort und Stelle". Vor allem nicht, wenn Sie tatsächlich 4 * 8B pro Zeichen drücken (auf einem 64-Bit-Computer: 3 Argumente + eine Absenderadresse).Verwenden
std::reverse()
reverse(begin(str), end(str));
Und das ist es.
quelle
Teile meinen Code. Als C ++ - Lernender, als Option zur Verwendung von swap (), bitte ich demütig um Kommentare.
quelle
Wenn Sie ATL / MFC verwenden
CString
, rufen Sie einfach anCString::MakeReverse()
.quelle
Noch ein anderer:
quelle
quelle
Mit C ++ Lambda:
quelle
Meine Antwort wäre den meisten ähnlich, aber bitte finden Sie meinen Code hier.
quelle
Ich denke, es gibt eine andere Möglichkeit, die Zeichenfolge umzukehren. Holen Sie sich die Eingabe vom Benutzer und kehren Sie sie um.
quelle
Wenn Sie es nicht speichern müssen, können Sie den Zeitaufwand folgendermaßen reduzieren:
quelle
Hier ist meine Einstellung zu C. Habe es zum Üben gemacht und versucht, so präzise wie möglich zu sein! Sie geben eine Zeichenfolge über die Befehlszeile ein, dh ./Programmname "Geben Sie hier eine Zeichenfolge ein"
quelle
Aber ich denke, der XOR-Swap-Algorithmus ist der beste ...
quelle
strlen()
in der Schleifenbedingung und im Schleifenkörper wird möglicherweise nicht optimiert.Hier ist der sauberste, sicherste und einfachste Weg, einen String in C ++ umzukehren (meiner Meinung nach):
Eine Alternative ist die Verwendung
std::swap
, aber ich mag es, meine eigenen Funktionen zu definieren - es ist eine interessante Übung und Sie braucheninclude
nichts extra.quelle
Dies ist optimierter Code in der Sprache C zum Umkehren einer Zeichenfolge ... Und es ist einfach; Verwenden Sie einfach einen einfachen Zeiger, um die Arbeit zu erledigen ...
quelle