Jak odwrócić ciąg w miejscu w C lub C ++?

173

Jak odwrócić ciąg w C lub C ++ bez konieczności oddzielnego bufora do przechowywania odwróconego ciągu?

Kodowanie zacieru
źródło
17
Kod w zaakceptowanej odpowiedzi jest przerażająco błędny . Aby uzyskać szczegółowe informacje, zobacz stackoverflow.com/a/21263068/88656 .
Eric Lippert

Odpowiedzi:

123

Standardowy algorytm polega na użyciu wskaźników do początku / końca i prowadzeniu ich do wewnątrz, aż spotkają się lub skrzyżują w środku. Zamień na bieżąco.


Odwrócony ciąg ASCII, tj. Tablica zakończona zerem, w której każdy znak mieści się w 1 char. (Lub inne nie-wielobajtowe zestawy znaków).

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

Ten sam algorytm działa dla tablic całkowitych o znanej długości, po prostu użyj tail = start + length - 1zamiast pętli znajdującej koniec.

(Uwaga redaktora: ta odpowiedź pierwotnie wykorzystywała zamianę XOR również dla tej prostej wersji. Naprawiono z korzyścią dla przyszłych czytelników tego popularnego pytania. Zamiana XOR jest wysoce niezalecana ; trudna do odczytania i sprawia, że ​​kod kompiluje się mniej wydajnie. można zobaczyć w eksploratorze kompilatora Godbolt, o ile bardziej skomplikowana jest treść pętli asm, gdy xor-swap jest kompilowany dla x86-64 z gcc -O3.)


Ok, dobrze, naprawmy znaki UTF-8 ...

(To jest zamiana XOR. Zwróć uwagę, że musisz unikać zamiany na siebie, ponieważ jeśli *pi *qsą w tej samej lokalizacji, wyzerujesz ją za pomocą ^ a == 0. Zamiana XOR zależy od posiadania dwóch różnych lokalizacji, używanie ich każdego jako tymczasowego przechowywania).

Uwaga redaktora: możesz zamienić SWP na bezpieczną funkcję wbudowaną za pomocą zmiennej tmp.

#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;
}
  • Dlaczego, tak, jeśli wejście jest zepsute, to wesoło zamieni się poza tym miejscem.
  • Przydatny link w przypadku wandalizacji w UNICODE: http://www.macchiato.com/unicode/chart/
  • Ponadto UTF-8 powyżej 0x10000 nie jest testowany (ponieważ nie mam do niego żadnej czcionki ani cierpliwości do korzystania z heksedytora)

Przykłady:

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

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

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

./strrev verrts/.
Anders Eurenius
źródło
162
Nie ma dobrego powodu, aby używać wymiany XOR poza konkurencją w zaciemnionym kodzie.
Chris Conway
28
Myślisz, że „na miejscu” oznacza „brak dodatkowej pamięci”, nawet pamięć O (1) dla tymczasowych? A co z miejscem na stosie na str i adres zwrotny?
Chris Conway,
55
@Bill, nie to oznacza powszechna definicja „na miejscu”. Algorytmy lokalne mogą wykorzystywać dodatkową pamięć. Jednak wielkość tej dodatkowej pamięci nie może zależeć od wejścia - tzn. Musi być stała. Dlatego wymiana wartości przy użyciu dodatkowej pamięci jest całkowicie na miejscu.
Konrad Rudolph
19
Nie głosowanie za tym, dopóki wymiana xor nie zniknie.
Adam Rosenfield
34
Zamiana XOR jest wolniejsza niż zamiana przez rejestr na nowoczesnych niedziałających procesorach.
Patrick Schlüter
465
#include <algorithm>
std::reverse(str.begin(), str.end());

To najprostszy sposób w C ++.

Greg Rogers
źródło
6
W C ++ ciąg jest reprezentowany przez klasę ciągów. Nie prosił o „gwiazdę zwarć” ani „nawiasy znaków”. Pozostań z klasą, C.
jokoon
10
@fredsbend, "absurdalnie długa" wersja wybranej odpowiedzi obsługuje przypadek, którego ta prosta odpowiedź nie dotyczy - wejście UTF-8. Pokazuje, jak ważne jest pełne sprecyzowanie problemu. Poza tym pytanie dotyczyło kodu, który będzie działał również w C.
Mark Ransom
5
Ta odpowiedź obsługuje przypadek, jeśli używasz świadomej klasy łańcuchowej UTF-8 (lub prawdopodobnie klasy znaków utf-8 ze std :: basic_string). Poza tym pytanie brzmiało „C lub C ++”, a nie „C i C ++”. Tylko C ++ to „C lub C ++”.
Taywee,
161

Przeczytaj Kernighan and 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;
    }
}
Eric Leschinski
źródło
8
Testowane na moim iPhonie jest to wolniejsze niż używanie surowych adresów wskaźników o około 15%
jjxtra
3
Czy zmienna „c” nie powinna być char zamiast int?
Lesswire
17
W tym przykładzie snależy zauważyć, że ciąg musi być zadeklarowany w postaci tablicy. Innymi słowy, char s[] = "this is ok"zamiast tego, char *s="cannot do this"że to drugie skutkuje stałą łańcuchową, której nie można modyfikować
user1527227
3
Z przeprosinami dla „Ojca chrzestnego”… „Zostaw broń, przynieś K&R”. Jako bigot C użyłbym wskaźników, ponieważ są one prostsze i bardziej bezpośrednie dla tego problemu, ale kod byłby mniej przenośny do C #, Java itp.
2
@Eric To nie działa w czasie O (log (n)). Działa w O (n), jeśli odnosisz się do liczby zamiany znaków, które wykonuje kod, dla n długości łańcucha, wówczas wykonywanych jest n zamian. Jeśli mówimy o ilości wykonanych pętli, to nadal jest O (n) - aczkolwiek O (n / 2), ale pomijasz stałe w notacji Big O.
Stephen Fox
62

Odwróć ciąg w miejscu (wizualizacja):

Odwróć ciąg w miejscu

slashdottir
źródło
Chłodny! Czego użyłeś do stworzenia tego? Myślę, że odpowiedź byłaby lepsza, gdybyśmy dołączyli do niej link.
Pryftan
Implementacja tego algorytmu znajduje się w tej odpowiedzi .
karlphillip
Czy możesz to trochę wyjaśnić, więc jeśli link do obrazu umiera, odpowiedź nie będzie bezużyteczna?
SS Anne
41

Niezłe C, przyjmując typowy przypadek, w którym łańcuch jest chartablicą zakończoną znakiem 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--;
  }
}
Chris Conway
źródło
Zamiast używać pętli while do znalezienia wskaźnika końcowego, nie możesz użyć czegoś takiego jak end_ptr = str + strlen (str); Wiem, że da to praktycznie to samo, ale wydaje mi się to wyraźniejsze.
Peter Kühne
Słusznie. Próbowałem (ale bezskutecznie) uniknąć błędu off-by-one w odpowiedzi @ uvote.
Chris Conway,
Oprócz potencjalnej poprawy wydajności z być może int tempto rozwiązanie wygląda najlepiej. +1
chux - Przywróć Monikę
@ chux-ReinstateMonica Tak. To jest piękne. Osobiście usunąłbym () z !(*str)chociaż.
Pryftan
@ PeterKühne Tak lub strchr()szukasz '\0'. Myślałem o obu. Nie potrzeba pętli.
Pryftan
35

Używasz std::reversealgorytmu z biblioteki standardowej C ++.

Nemanja Trifunovic
źródło
14
Biblioteka szablonów standardowych to termin przedstandardowy. Standard C ++ nie wspomina o tym, a poprzednie komponenty STL znajdują się w C ++ Standard Library.
Nemanja Trifunovic
16
dobrze. Zawsze się zastanawiam, dlaczego tak wielu ludzi wciąż nazywa to „STL”, chociaż służy to tylko zmyleniu sprawy. byłoby lepiej, gdyby więcej ludzi było takich jak Ty i nazwałoby to po prostu „C ++ Standard Library” lub STL i powiedziałoby „Standard Library” :)
Johannes Schaub - litb
27

Minęło trochę czasu i nie pamiętam, która książka nauczyła mnie tego algorytmu, ale pomyślałem, że to dość genialne i łatwe do zrozumienia:

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);
karlphillip
źródło
To interesująca odmiana tak. Technicznie powinno być size_tchociaż.
Pryftan
24

Użyj metody std :: reverse z STL :

std::reverse(str.begin(), str.end());

Trzeba będzie zawierać „Algorytm” biblioteki #include<algorithm>.

user2628229
źródło
1
Którą bibliotekę należy uwzględnić?
Don Cruickshank
#include <algorithm> Zapomniałem go napisać, a następnie zredagowałem odpowiedź, ale nie została zapisana, dlatego brakowało nazwy ..
user2628229
Chociaż byłaby to również moja odpowiedź, po prostu ciekawa, ponieważ OP zapytał „bez bufora do przechowywania odwróconego łańcucha” (w zasadzie zamiana na miejscu), jak można udowodnić, że to robi? Czy wystarczy wyjaśnić, że wewnętrznie używa std :: iter_swap <>, iterując do środka bufora z obu punktów końcowych? Ponadto OP poprosił o C i C ++, to jest tylko dla C ++ (czy możemy mieć nadzieję, że <string.h> ma metodę strrev ()?)
HidekiAI
21

Zauważ, że piękno std :: reverse polega na tym, że działa on ze char *stringami i std::wstrings tak samo dobrze jak std::strings

void strrev(char *str)
{
    if (str == NULL)
        return;
    std::reverse(str, str + strlen(str));
}
Zaćmienie
źródło
1
Z jednej strony chcę zwymiotować, ponieważ używałeś C ++, ale z drugiej strony jest to piękna, piękna, absolutnie piękna rzecz widzieć kogoś używającego C ++, który nie umieszcza znaku *według typu, a raczej umieszcza go po nazwie. Wspaniale. Przyznaję, że jestem purystą, ale wzdrygam się za każdym razem, gdy widzę kod char* str;.
Pryftan
11

Jeśli szukasz odwracania buforów zakończonych wartością NULL, większość opublikowanych tutaj rozwiązań jest w porządku. Ale, jak już zauważył Tim Farley, te algorytmy będą działać tylko wtedy, gdy będzie można założyć, że ciąg jest semantycznie tablicą bajtów (tj. Ciągami jednobajtowymi), co, jak sądzę, jest błędnym założeniem.

Weźmy na przykład ciąg „año” (rok w języku hiszpańskim).

Punkty kodowe Unicode to 0x61, 0xf1, 0x6f.

Rozważ niektóre z najczęściej używanych kodowań:

Latin1 / iso-8859-1 (kodowanie jednobajtowe, 1 znak to 1 bajt i odwrotnie):

Oryginalny:

0x61, 0xf1, 0x6f, 0x00

Odwrócić:

0x6f, 0xf1, 0x61, 0x00

Wynik jest OK

UTF-8:

Oryginalny:

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

Odwrócić:

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

Rezultatem jest bełkot i niedozwolona sekwencja UTF-8

UTF-16 Big Endian:

Oryginalny:

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

Pierwszy bajt będzie traktowany jako terminator NUL. Żadne cofanie nie nastąpi.

UTF-16 Little Endian:

Oryginalny:

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

Drugi bajt będzie traktowany jako terminator NUL. Rezultatem będzie 0x61, 0x00, ciąg zawierający znak „a”.

Juan Pablo Califano
źródło
std :: reverse będzie działać dla dwubajtowych typów Unicode, o ile używasz wstring.
Eclipse
Nie jestem zbyt zaznajomiony z C ++, ale przypuszczam, że każda szanowana standardowa funkcja biblioteki zajmująca się ciągami znaków będzie w stanie obsłużyć różne kodowania, więc zgadzam się z tobą. Przez „te algorytmy” rozumiałem zamieszczone tutaj funkcje odwracania ad-hoc.
Juan Pablo Califano
Niestety, w standardowym C ++ nie ma czegoś takiego jak „przyzwoita funkcja obsługująca ciągi znaków”.
Jem
@Eclipse Jeśli odwróci parę zastępczą, wynik nie będzie już poprawny. Unicode nie jest w rzeczywistości zestawem znaków o stałej szerokości
phuclv
W tej odpowiedzi podoba mi się to, że pokazuje rzeczywistą kolejność bajtów (chociaż endianness może być czymś - ach, widzę, że rzeczywiście to rozważyłeś) i jak jest poprawny lub niepoprawny. Ale myślę, że odpowiedź byłaby lepsza, gdybyś włączył jakiś kod demonstrujący to.
Pryftan
11

W celu uzyskania kompletności należy zauważyć, że na różnych platformach istnieją reprezentacje łańcuchów, w których liczba bajtów na znak różni się w zależności od znaku. Programiści ze starej szkoły określaliby to jako DBCS (zestaw znaków dwubajtowych) . Współcześni programiści częściej spotykają się z tym w UTF-8 (a także UTF-16 i innych). Istnieją również inne takie kodowania.

W żadnym z tych schematów kodowania o zmiennej szerokości, zamieszczone tutaj proste algorytmy ( złe , nie-złe lub inne ) w ogóle nie działałyby poprawnie! W rzeczywistości mogą nawet spowodować, że ciąg stanie się nieczytelny lub nawet nielegalny ciąg w tym schemacie kodowania. Zobacz odpowiedź Juana Pablo Califano, aby zobaczyć kilka dobrych przykładów.

Std :: reverse () potencjalnie nadal by działało w tym przypadku, o ile implementacja standardowej biblioteki C ++ na Twojej platformie (w szczególności iteratory ciągów znaków) prawidłowo to uwzględniła.

Tim Farley
źródło
6
std :: reverse NIE bierze tego pod uwagę. Odwraca wartość_typ_wartości. W przypadku std :: string odwraca znaki char. Nie postacie.
MSalters
Powiedz raczej, że my, programiści ze starej szkoły, znamy DBCS, ale znamy również UTF-8: wszyscy wiemy, że programiści są jak nałogowcy, kiedy mówią „jeszcze jedna linijka i rzucę!”. Jestem pewien, że niektórzy programiści w końcu zrezygnowali, ale szczerze mówiąc programowanie jest dla mnie jak nałóg; Otrzymuję wypłaty z braku programowania. Warto tutaj dodać. Nie lubię C ++ (bardzo się starałem, żeby go polubić, nawet napisałem całkiem sporo, ale nadal jest to dla mnie co najmniej nieatrakcyjne estetycznie), więc nie mogę tego komentować, ale i tak masz rację, więc mieć +1.
Pryftan
5

Inny sposób w C ++ (choć prawdopodobnie sam użyłbym std :: reverse () :) jako bardziej wyrazisty i szybszy)

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

Sposób C (mniej więcej :)) i proszę uważaj na sztuczkę XOR do zamiany, kompilatory czasami nie mogą tego zoptymalizować.

W takim przypadku jest zwykle dużo wolniejszy.

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
pprzemek
źródło
Użyłbym strlendo znalezienia końca łańcucha, jeśli jest potencjalnie długi. Dobra implementacja biblioteki będzie wykorzystywać wektory SIMD do wyszukiwania szybciej niż 1 bajt na iterację. Ale dla bardzo krótkich łańcuchów, while (*++end);zostanie wykonane zanim wywołanie funkcji biblioteki rozpocznie wyszukiwanie.
Peter Cordes,
@PeterCordes dobrze, zgodziłam się, strlen powinien być używany tak czy inaczej dla czytelności. W przypadku dłuższych sznurków i tak należy zawsze utrzymywać długość w różnym stopniu. strlen na SIMD jest zwykle podawany jako przykład z tym zastrzeżeniem, który nie jest prawdziwą aplikacją, a przynajmniej było to 5 lat temu, kiedy kod został napisany. ;)
pprzemek
1
Jeśli chcesz, aby to działało szybko na prawdziwych procesorach, użyłbyś tasowania SIMD, aby zrobić odwrotnie w fragmentach 16B. : P np. Na x86, _mm_shuffle_epi8(PSHUFB) może odwrócić kolejność wektora 16B, biorąc pod uwagę prawy wektor sterujący tasowania. Prawdopodobnie może działać z szybkością prawie memcpy z pewną staranną optymalizacją, szczególnie z AVX2.
Peter Cordes,
char* beg = s-1ma niezdefiniowane zachowanie (przynajmniej jeśli swskazuje na pierwszy element tablicy, co jest najczęstszym przypadkiem). while (*++end);ma niezdefiniowane zachowanie, jeśli sjest pustym łańcuchem.
melpomene
@pprzemek Cóż, twierdzisz, że s-1ma zdefiniowane zachowanie, nawet jeśli swskazuje na pierwszy element tablicy, więc to Ty powinieneś móc zacytować standard jako wsparcie.
melpomene
4
#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;
}

Ten kod generuje następujące dane wyjściowe:

gnitset
a
cba

źródło
2
@uvote, nie używaj strcpy. Zawsze. Jeśli musisz użyć czegoś takiego jak strcpy, użyj strncpy. strcpy jest niebezpieczny. Nawiasem mówiąc, C i C ++ to dwa oddzielne języki z osobnymi udogodnieniami. Myślę, że używasz plików nagłówkowych dostępnych tylko w C ++, więc czy naprawdę potrzebujesz odpowiedzi w C?
Onorio Catenacci
6
strcpy jest całkowicie bezpieczny, jeśli programista może śledzić rozmiar swoich tablic, wielu twierdzi, że strncpy jest mniej bezpieczny, ponieważ nie gwarantuje, że wynikowy łańcuch zostanie zakończony wartością null. W każdym razie nie ma nic złego w używaniu tutaj strcpy przez uvote.
Robert Gamble,
1
@Onorio Catenacci, strcpy nie jest niebezpieczne, jeśli wiesz, że ciąg źródłowy zmieści się w buforze docelowym, tak jak w przypadkach podanych w powyższym kodzie. Ponadto strncpy zero-wypełnia do liczby znaków określonej w parametrze size, jeśli pozostało miejsce, co może nie być pożądane.
Chris Young,
3
Każdy, kto nie potrafi poprawnie używać strcpy, nie powinien programować w języku C.
Robert Gamble
2
@Robert Gamble, zgadzam się. Jednak ponieważ nie znam żadnego sposobu na powstrzymanie ludzi przed programowaniem w C, niezależnie od ich kompetencji, zwykle odradzam to.
Onorio Catenacci
3

Podoba mi się odpowiedź Evgeny K&R. Jednak miło jest zobaczyć wersję używającą wskaźników. W przeciwnym razie jest w zasadzie to samo:

#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;
}
Obrabować
źródło
3

Funkcja rekurencyjna do odwracania łańcucha w miejscu (bez dodatkowego bufora, malloc).

Krótki, seksowny kod. Złe, złe wykorzystanie stosu.

#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;
}
Simon Peverett
źródło
1
To całkiem fajne rozwiązanie, powinieneś dodać śledzenie, takie jak printf ("% * s> [% d] reverse_r ('% c',% p = \"% s \ ",% p = \"% s \ ") \ n ", głębokość," ", głębokość, val, s, (s? s:" null "), n, (n? n:" null ")); na początku i <na końcu.
Benoît
Wepchnięcie każdego charna stos nie liczy się jako „na miejscu”. Zwłaszcza, gdy faktycznie wypychasz 4 * 8B na znak (na komputerze 64-bitowym: 3 argumenty + adres zwrotny).
Peter Cordes,
Pierwotne pytanie brzmi „Jak odwrócić ciąg znaków w C lub C ++ bez konieczności oddzielnego bufora do przechowywania odwróconego ciągu?” - nie było wymogu zamiany „na miejscu”. Również to rozwiązanie wspomina o złym wykorzystaniu stosu od samego początku. Czy mój głos został odrzucony z powodu słabego rozumienia czytania przez innych ludzi?
Simon Peverett
1
Nie nazwałbym tego „seksownym”, ale powiedziałbym, że jest to demonstracyjne i instruktażowe. Jeśli rekursja jest używana prawidłowo, może być bardzo cenna. Należy jednak zaznaczyć, że - ostatnio wiedziałem - C nie wymaga nawet stosu jako takiego; jednak robi rekurencję. Tak czy inaczej jest to przykład rekurencji, która, jeśli jest właściwie używana, może być bardzo przydatna i wartościowa. Chyba nigdy nie widziałem, żeby służyło do odwracania struny.
Pryftan
1

Udostępnij mój kod. Jako osoba ucząca się C ++, w ramach opcji swap (), pokornie proszę o komentarze.

void reverse(char* str) {
    int length = strlen(str);
    char* str_head = str;
    char* str_tail = &str[length-1];
    while (str_head < str_tail) 
        swap(*str_head++, *str_tail--);
}
Widmowy
źródło
1

Jeśli używasz ATL / MFC CString, po prostu zadzwoń CString::MakeReverse().

Michael Haephrati
źródło
0

Jeszcze inny:

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

}
Mike Marrotte
źródło
To pokazuje arytmetykę wskaźników, podobnie jak moja odpowiedź, ale łączy ją z zamianą. Uważam, że ta odpowiedź naprawdę wiele dodaje. Powinieneś być w stanie zrozumieć ten typ kodu przed dodaniem miliarda bibliotek jako zależności tylko po to, aby uzyskać proste pole tekstowe (coś, co widzę zbyt często w nowoczesnych aplikacjach, z którymi pracuję)
Stephen J
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");
}
masakielastic
źródło
0

Z lambda C ++:

 auto reverse = [](std::string& s) -> std::string {
        size_t start = 0, end = s.length() -1;
        char temp;

        while (start < end) {
          temp = s[start];
          s[start++] = s[end];
          s[end--] = temp;
        } 

        return s;
   };
adem
źródło
0

Moja odpowiedź byłaby podobna do większości z nich, ale proszę znaleźć mój kod tutaj.

//Method signature to reverse string
string reverseString(string str);

int main(void){
    string str;
    getline(cin, str);
    str =  reverseString(str);
    cout << "The reveresed string is : " << str;
    return 0;
}

/// <summary>
///     Reverses the input string.
/// </summary>
/// <param name="str">
///    This is the input string which needs to be reversed.
/// </param>
/// <return datatype = string>
///     This method would return the reversed string
/// </return datatype>

string reverseString(string str){
    int length = str.size()-1;
    char temp;
    for( int i=0 ;i<(length/2);i++)
    {
        temp = str[i];
        str[i] = str[length-i];
        str[length-i] = temp;
    }
    return str;
}
GANESH BK
źródło
0

Myślę, że jest inny sposób na odwrócenie struny. uzyskać dane wejściowe od użytkownika i odwrócić je.

void Rev() {
    char ch;
    cin.get(ch);
    if(ch != '\n') {
        Rev();
        cout.put(ch);
    }
}
Alok
źródło
To prawda, ale to tylko wypisuje odwrotną kolejność, prawda? (Nie używam C ++, więc może .put () nie robi tego, co myślę, że robi).
Pryftan
-1

Jeśli nie musisz go przechowywać, możesz skrócić czas spędzony w ten sposób:

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");
}
Stephen J.
źródło
Wydaje mi się, że jestem jedyną odpowiedzią, która nie ma bufora ani zmiennej tymczasowej. Używam długości sznurka, ale inni, którzy to robią, dodają kolejną na głowę (vs ogon). Zakładam, że standardowa funkcja reverse func przechowuje zmienną, poprzez zamianę lub coś w tym rodzaju. Dlatego mam wrażenie, zakładając, że matematyka wskaźnikowa i typ UTF pokrywają się, że jest to prawdopodobnie jedyna odpowiedź, która faktycznie odpowiada na to pytanie. Dodane printf () można usunąć, po prostu zrobiłem to, aby ładniej wyglądać na wyniku. Napisałem to dla szybkości. Brak dodatkowych przydziałów lub zmiennych. Prawdopodobnie najszybszy algorytm do wyświetlania odwrotnej str ()
Stephen J
-3

Oto moje spojrzenie na to w C. Zrobiłem to dla praktyki i starałem się być tak zwięzłe, jak to tylko możliwe! Wprowadzasz ciąg z linii poleceń, np ./nazwa_programu "tu wpisz ciąg"

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

void reverse(int s,int e,int len,char t,char* arg) {
   for(;s<len/2;t=arg[s],arg[s++]=arg[e],arg[e--]=t);
}

int main(int argc,char* argv[]) {
  int s=0,len=strlen(argv[1]),e=len-1; char t,*arg=argv[1];
  reverse(s,e,len,t,arg);
  for(s=0,e=0;e<=len;arg[e]==' '||arg[e]=='\0'?reverse(s,e-1,e+s,t,arg),s=++e:e++);
  printf("%s\n",arg);
}
Kevin Heffernan
źródło
1
To nieczytelny bałagan, ale najwyraźniej nie wybierasz najkrótszego możliwego kodu ( kodu golfowego ), ponieważ niektóre nazwy zmiennych mają więcej niż jeden znak.
Peter Cordes
-4

Ale myślę, że algorytm wymiany XOR jest najlepszy ...

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;
}
Hasenbeck
źródło
Wywołanie strlen()w warunku pętli iw treści pętli może nie zostać zoptymalizowane.
Peter Cordes
-5

Oto najczystszy, najbezpieczniejszy i najłatwiejszy sposób na odwrócenie ciągu w C ++ (moim zdaniem):

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

}

Alternatywą jest użycie std::swap, ale lubię definiować własne funkcje - to ciekawe ćwiczenie i nie potrzebujesz includenic więcej.

Oleksiy
źródło
-5
#include<stdio.h>
#include<conio.h>

int main()
{
    char *my_string = "THIS_IS_MY_STRING";
    char *rev_my_string = my_string;

    while (*++rev_my_string != '\0')
        ;

    while (rev_my_string-- != (my_string-1))
    {
        printf("%c", *rev_my_string);
    }

    getchar();
    return 0;
}

Jest to zoptymalizowany kod w języku C do odwracania łańcucha… I to jest proste; po prostu użyj prostego wskaźnika, aby wykonać zadanie ...

Nit kt
źródło
Spowoduje to wyświetlenie ciągu po jednym znaku na raz. Nie odwraca tego na miejscu. Oczekuje również na dane wejściowe użytkownika bez powodu.
Peter Cordes