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

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

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/.

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

To najprostszy sposób w C ++.

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

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

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

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

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

Użyj metody std :: reverse z STL :

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

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

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

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”.

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.

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

#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

Jeśli używasz GLib, ma do tego dwie funkcje, g_strreverse () i g_utf8_strreverse ()

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

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

Posługiwać się std::reverse()

reverse(begin(str), end(str));

I to wszystko.

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

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

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

}

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

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

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

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

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

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

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

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.

#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 ...