¿Cómo se invierte una cadena en su lugar en C o C++?
¿Cómo se invierte una cadena en C o C++ sin requerir un búfer separado para contener la cadena invertida?
Oct 13
'08 23:10
#include <algorithm>
std::reverse(str.begin(), str.end());
Esta es la forma más sencilla en C++.
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;
}
}
El algoritmo estándar es utilizar punteros al inicio/final y recorrerlos 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 de números enteros con longitud conocida, solo utilícelo tail = start + length - 1en lugar del bucle de búsqueda final.
(Nota del editor: esta respuesta originalmente también usaba XOR-swap para esta versión simple. Se corrigió para beneficio de futuros lectores de esta pregunta popular. No se recomienda XOR-swap ; es difícil de leer y hace que su código se compile de manera menos eficiente. Puede 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 XOR. Tenga en cuenta que debe evitar el intercambio con uno mismo, porque si *py *qson la misma ubicación, lo pondrá a cero con a^a==0. El intercambio XOR depende de tener dos ubicaciones distintas, usándolos cada uno 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;
}
- Vaya, sí, si la entrada está bloqueada, esto se intercambiará alegremente fuera del lugar.
- Enlace útil al vandalismo en UNICODE: http://www.macchiato.com/unicode/chart/
- Además, UTF-8 superior a 0x10000 no se ha 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/.
C no malvado, suponiendo el caso común en el que la cadena es una charmatriz terminada en nulo:
#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--;
}
}
