¿Cómo se invierte una cadena en su lugar en C o C++?

10 minutos de lectura

¿Cómo se invierte una cadena en C o C++ sin requerir un búfer separado para contener la cadena invertida?

¿Como se invierte una cadena en su lugar en C
greg rogers

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

Esta es la forma más sencilla en C++.

  • En C++, una cadena está representada por la clase de cadena. No pidió “estrella de carbón” o “paréntesis de carbón”. Mantente elegante, C.

    – jokoon

    30 de agosto de 2011 a las 21:53

  • @fredsbend, la versión “ridículamente larga” de la respuesta seleccionada maneja un caso que esta respuesta simple no maneja: entrada UTF-8. Muestra la importancia de especificar completamente el problema. Además, la pregunta era sobre el código que también funcionaría en C.

    – Mark Ransom

    16 de agosto de 2013 a las 14:45


  • Esta respuesta maneja el caso si usa una clase de cadena compatible con UTF-8 (o posiblemente una clase de caracteres utf-8 con std::basic_string). Además, la pregunta decía “C o C++”, no “C y C++”. C++ solo es “C o C++”.

    – Taywee

    5 de julio de 2016 a las 18:54

  • Esto romperá por completo las cadenas multibyte UTF-8 y, en la actualidad, es un no iniciador total.

    –Cameron Lowell Palmer

    27 de enero de 2021 a las 19:18

Leer Kernighan y 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;
    }
}

  • Probado en mi iPhone, esto es más lento que usar direcciones de puntero sin procesar en aproximadamente un 15%

    – jjxtra

    29/04/2013 a las 20:16

  • ¿La variable “c” no debería ser un carácter en lugar de un int?

    – Lesswire

    17 de noviembre de 2013 a las 17:25

  • Es importante notar en este ejemplo que la cadena s debe declararse en forma de matriz. En otras palabras, char s[] = "this is ok" en vez de char *s="cannot do this" porque este último da como resultado una constante de cadena que no se puede modificar

    – usuario1527227

    9 de abril de 2014 a las 1:50

  • Con disculpas a “El Padrino” …. “Deja las armas, trae el K&R”. Como fanático de C, usaría punteros, ya que son más simples y directos para este problema, pero el código sería menos portátil para C #, Java, etc.

    usuario1899861

    27 de noviembre de 2014 a las 2:14

  • @Eric Esto no se ejecuta en tiempo O (log (n)). Se ejecuta en O (n) si se refiere a la cantidad de intercambios de caracteres que realiza el código, para n de longitud de cadena, luego se realizan n intercambios. Si estamos hablando de la cantidad de bucles realizados, entonces sigue siendo O (n), aunque O (n/2), pero elimina las constantes en notación Big O.

    – Esteban Fox

    18 dic 2016 a las 18:43

1647546251 839 ¿Como se invierte una cadena en su lugar en C
Anders Eurenio

El algoritmo estándar es usar punteros al inicio/final, y llevarlos hacia adentro hasta que se encuentren o se crucen en el medio. Intercambia sobre la marcha.


Cadena ASCII inversa, es decir, una matriz terminada en 0 donde cada carácter cabe en 1 char. (U otros conjuntos de caracteres que no sean multibyte).

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

El mismo algoritmo funciona para matrices enteras con longitud conocida, solo use tail = start + length - 1 en lugar del bucle de búsqueda de extremos.

(Nota del editor: esta respuesta también usó originalmente XOR-swap para esta versión simple. Se corrigió para beneficio de los futuros lectores de esta popular pregunta. XOR-swap es muy no recomendado; difícil de leer y hacer que su código se compile de manera menos eficiente. Puedes ver en el explorador del compilador Godbolt cuánto más complicado es el cuerpo del bucle asm cuando se compila xor-swap para x86-64 con gcc -O3).


Ok, bien, arreglemos los caracteres UTF-8…

(Esto es algo de intercambio de XOR. Tenga cuidado de tener en cuenta que usted debe evitar intercambiando con uno mismo, porque si *p y *q son la misma ubicación, lo pondrás a cero con a^a==0. XOR-swap depende de tener dos ubicaciones distintas, usándolas cada una como almacenamiento temporal).

Nota del editor: puede reemplazar SWP con una función en línea segura usando una variable 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;
}
  • Por qué, sí, si la entrada está borrada, esto cambiará alegremente fuera del lugar.
  • Enlace útil a la hora de vandalizar en el UNICODE: http://www.macchiato.com/unicode/chart/
  • Además, UTF-8 sobre 0x10000 no está probado (ya que parece que no tengo ninguna fuente, ni la paciencia para usar un editor hexadecimal)

Ejemplos:

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

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

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

./strrev verrts/.

  • No hay una buena razón para usar el intercambio XOR fuera de una competencia de código ofuscado.

    – Chris Conway

    13 de octubre de 2008 a las 17:02

  • ¿Crees que “en el lugar” significa “sin memoria adicional”, ni siquiera memoria O (1) para los temporales? ¿Qué pasa con el espacio en la pila para str y la dirección de retorno?

    – Chris Conway

    13/10/2008 a las 17:30

  • @Bill, eso no es lo que significa la definición común de “en el lugar”. Algoritmos en el lugar mayo utilizar memoria adicional. Sin embargo, la cantidad de esta memoria adicional no debe depender de la entrada, es decir, debe ser constante. Por lo tanto, el intercambio de valores utilizando almacenamiento adicional está completamente en su lugar.

    – Konrad Rodolfo

    13 de octubre de 2008 a las 17:31

  • No votar esto hasta que desaparezca el intercambio de xor.

    – Adam Rosenfield

    23 de enero de 2010 a las 21:42

  • El intercambio XOR es más lento que el intercambio a través del registro en los procesadores modernos fuera de servicio.

    – Patrick Schlüter

    15 de agosto de 2011 a las 17:42

1647546251 206 ¿Como se invierte una cadena en su lugar en C
karlphillip

Ha pasado un tiempo y no recuerdo en qué libro me enseñaron este algoritmo, pero me pareció bastante ingenioso y sencillo de entender:

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

Una visualización de este algoritmo, cortesía de slashdottir:

Visualización del algoritmo para invertir una cadena en su lugar

  • En lugar de usar un bucle while para encontrar el puntero final, ¿no puede usar algo como end_ptr = str + strlen (str); Sé que hará prácticamente lo mismo, pero lo encuentro más claro.

    – Peter Kuhne

    13 de octubre de 2008 a las 17:43

  • Lo suficientemente justo. Estaba intentando (y fallando) evitar el error de uno en la respuesta de @ uvote.

    – Chris Conway

    13 de octubre de 2008 a las 19:57

  • Aparte de un potencial mejora del rendimiento con quizás int temp, esta solución se ve mejor. +1

    – chux – Reincorporar a Monica

    13 de junio de 2014 a las 22:17

  • @chux-ReinstateMonica Sí. Es bonito. Personalmente quitaría los ()s del !(*str) aunque.

    – Priftan

    21 de febrero de 2020 a las 17:08

  • @PeterKühne Sí o strchr() buscando '\0'. Pensé en ambos. No es necesario un bucle.

    – Priftan

    21 de febrero de 2020 a las 17:10

¿Como se invierte una cadena en su lugar en C
Eclipse

Tenga en cuenta que la belleza de std::reverse es que funciona con char * cuerdas y std::wstringes tan bueno como std::strings

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

1647546253 125 ¿Como se invierte una cadena en su lugar en C
Juan Pablo Califano

Si está buscando revertir los búferes terminados en NULL, la mayoría de las soluciones publicadas aquí están bien. Pero, como Tim Farley ya señaló, estos algoritmos funcionarán solo si es válido suponer que una cadena es semánticamente una matriz de bytes (es decir, cadenas de un solo byte), lo cual creo que es una suposición incorrecta.

Tomemos, por ejemplo, la cadena “año” (año en español).

Los puntos de código Unicode son 0x61, 0xf1, 0x6f.

Considere algunas de las codificaciones más utilizadas:

Latín1 / iso-8859-1 (codificación de un solo byte, 1 carácter es 1 byte y viceversa):

Original:

0x61, 0xf1, 0x6f, 0x00

Contrarrestar:

0x6f, 0xf1, 0x61, 0x00

el resultado esta bien

UTF-8:

Original:

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

Contrarrestar:

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

El resultado es un galimatías y una secuencia UTF-8 ilegal

UTF-16 Big Endian:

Original:

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

El primer byte se tratará como un terminador NUL. No se realizará ninguna inversión.

UTF-16 Little Endian:

Original:

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

El segundo byte se tratará como un terminador NUL. El resultado será 0x61, 0x00, una cadena que contiene el carácter ‘a’.

1647546253 810 ¿Como se invierte una cadena en su lugar en C
Comunidad

En aras de la exhaustividad, debe señalarse que existen representaciones de cadenas en varias plataformas en las que el número de bytes por carácter varía dependiendo del personaje. Los programadores de la vieja escuela se referirían a esto como DBCS (juego de caracteres de doble byte). Los programadores modernos encuentran esto más comúnmente en UTF-8 (así como también UTF-16 y otros). Hay otras codificaciones similares también.

En cualquiera de estos esquemas de codificación de ancho variable, los algoritmos simples publicados aquí (malos, no malos o de otro tipo) no funcionarían correctamente en absoluto. De hecho, incluso podrían hacer que la cadena se volviera ilegible o incluso ilegal en ese esquema de codificación. Vea la respuesta de Juan Pablo Califano para ver algunos buenos ejemplos.

std::reverse() potencialmente seguiría funcionando en este caso, siempre que la implementación de la biblioteca estándar de C++ de su plataforma (en particular, los iteradores de cadenas) lo tuviera en cuenta correctamente.

  • std::reverse NO tiene esto en cuenta. Invierte value_type’s. En el caso de std::string, invierte char’s. No personajes.

    – MSalters

    14 de octubre de 2008 a las 7:24

  • Digamos más bien que nosotros, los programadores de la vieja escuela, conocemos DBCS pero también conocemos UTF-8: porque todos sabemos que los programadores son como adictos cuando dicen ‘¡una línea más y renuncio!’ Estoy seguro de que algunos programadores finalmente se dan por vencidos pero, francamente, la programación es realmente como una adicción para mí; Recibo retiros por no programar. Es un buen punto que agregas aquí. No me gusta C ++ (me esforcé mucho para que me gustara incluso escribiendo un poco, pero todavía es estéticamente poco atractivo para mí, por decir lo menos), así que no puedo comentar allí, pero de todos modos tienes un buen punto así que tener un +1.

    – Priftan

    21 de febrero de 2020 a las 17:23


¿Ha sido útil esta solución?

Esta web utiliza cookies propias y de terceros para su correcto funcionamiento y para fines analíticos y para mostrarte publicidad relacionada con sus preferencias en base a un perfil elaborado a partir de tus hábitos de navegación. Al hacer clic en el botón Aceptar, acepta el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Configurar y más información
Privacidad