Сторнирование строки в C

Question

Я разработал программу обратной строки. Мне интересно, есть ли лучший способ сделать это, и если мой код имеет какие-либо потенциальные проблемы. Я хочу попрактиковаться в некоторых расширенных функциях C.

char* reverse_string(char *str)
{
    char temp;
    size_t len = strlen(str) - 1;
    size_t i;
    size_t k = len;

    for(i = 0; i < len; i++)
    {
        temp = str[k];
        str[k] = str[i];
        str[i] = temp;
        k--;

        /* As 2 characters are changing place for each cycle of the loop
           only traverse half the array of characters */
        if(k == (len / 2))
        {
            break;
        }
    }
}

Answer 1

Если вы хотите попрактиковаться в расширенных функциях C, как насчет указателей? Мы можем добавить макросы и xor-swap для удовольствия!

#include <string.h> // for strlen()

// reverse the given null-terminated string in place
void inplace_reverse(char * str)
{
  if (str)
  {
    char * end = str + strlen(str) - 1;

    // swap the values in the two given variables
    // XXX: fails when a and b refer to same memory location
#   define XOR_SWAP(a,b) do\
    {\
      a ^= b;\
      b ^= a;\
      a ^= b;\
    } while (0)

    // walk inwards from both ends of the string, 
    // swapping until we get to the middle
    while (str < end)
    {
      XOR_SWAP(*str, *end);
      str++;
      end--;
    }
#   undef XOR_SWAP
  }
}

A указатель (например, char *, читаемый справа налево как указатель на char) - это тип данных в C, который используется ссылаться на местоположение в памяти другого значения. В этом случае, место, где хранится char. Мы можем разыменование указатели с префиксом *, что дает нам значение хранится в этом месте. Таким образом, значение, хранящееся в str, равно *str.

Мы можем сделать простую арифметику с указателями. Когда мы увеличиваем (или уменьшаем) указатель, мы просто перемещаем его для ссылки на следующий (или предыдущий) место в памяти для этого типа значения. Увеличивающие указатели разные типы могут перемещать указатель на разное число байты, потому что разные значения имеют разные размеры байтов в C.

Здесь мы используем один указатель для ссылки на первый необработанный char строки (str) и другой для ссылки на последний (end). Мы меняем их значения (*str и *end) и перемещаем указатели внутрь к середине строки. Однажды str >= end, либо они оба указывают на один и тот же char, что означает, что наша оригинальная строка имела нечетная длина (и середина char не должна быть обращена), или мы обработали все.

Чтобы выполнить обмен, я определил макрос . Макросы текстовые подстановки сделано препроцессором C. Они очень отличаются от функций, и важно знать разницу. Когда вы вызываете функцию, функция работает с копией значений, которые вы ей даете. Когда вы звоните макрос, он просто делает текстовую подстановку - поэтому аргументы вы даете используются напрямую.

Поскольку я использовал макрос XOR_SWAP только один раз, вероятно, было излишним определять его, но это сделало более ясным, что я делал. После того, как препроцессор C расширяет макрос, цикл while выглядит так:

    while (str < end)
    {
      do { *str ^= *end; *end ^= *str; *str ^= *end; } while (0);
      str++;
      end--;
    }

Обратите внимание, что аргументы макроса отображаются один раз при каждом использовании в макроопределение. Это может быть очень полезно - но может также сломать ваш код если используется неправильно. Например, если бы я сжал увеличение / уменьшение инструкции и вызов макроса в одну строку, например

      XOR_SWAP(*str++, *end--);

Тогда это расширится до

      do { *str++ ^= *end--; *end-- ^= *str++; *str++ ^= *end--; } while (0);

Имеет тройные операции увеличения / уменьшения, но на самом деле не имеет сделайте обмен, который он должен сделать.

Пока мы говорим на эту тему, вы должны знать, что означает xor (^). Это основной арифметическая операция - как сложение, вычитание, умножение, деление, кроме это обычно не преподается в начальной школе. Он объединяет два целых по крупицам - как дополнение, но нас не волнуют переходы. 1^1 = 0, 1^0 = 1, 0^1 = 1, 0^0 = 0.

Хорошо известный трюк - использовать xor для обмена двумя значениями. Это работает из-за трех основных свойства xor: x ^ 0 = x, x ^ x = 0 и x ^ y = y ^ x для всех значений x и y. Скажем, у нас есть два переменные a и b, которые изначально хранят два значения v<sub>a</sub> и v<sub>b</sub>.

  // initially:
  // a == v<sub>a</sub>
  // b == v<sub>b</sub>
  a ^= b;
  // now: a == v<sub>a</sub> ^ v<sub>b</sub>
  b ^= a;
  // now: b == v<sub>b</sub> ^ (v<sub>a</sub> ^ v<sub>b</sub>)
  //        == v<sub>a</sub> ^ (v<sub>b</sub> ^ v<sub>b</sub>)
  //        == v<sub>a</sub> ^ 0
  //        == v<sub>a</sub>
  a ^= b;
  // now: a == (v<sub>a</sub> ^ v<sub>b</sub>) ^ v<sub>a</sub>
  //        == (v<sub>a</sub> ^ v<sub>a</sub>) ^ v<sub>b</sub>
  //        == 0 ^ v<sub>b</sub>
  //        == v<sub>b</sub>

Значит, значения меняются местами. Это имеет одну ошибку - когда a и b являются одной и той же переменной:

  // initially:
  // a == v<sub>a</sub>
  a ^= a;
  // now: a == v<sub>a</sub> ^ v<sub>a</sub>
  //        == 0
  a ^= a;
  // now: a == 0 ^ 0
  //        == 0
  a ^= a;
  // now: a == 0 ^ 0
  //        == 0

Так как мы str < end, в вышеприведенном коде этого не происходит, поэтому мы в порядке.

Пока мы обеспокоены правильностью, мы должны проверить наши крайние случаи. Строка if (str) должна гарантировать, что нам не был дан указатель NULL для строки. Как насчет пустой строки ""? Хорошо strlen("") == 0, поэтому мы инициализируем end как str - 1, что означает, что условие while (str < end) никогда не выполняется, поэтому мы ничего не делаем. Что правильно.

Есть куча Си для изучения. Веселитесь вместе с ним!

Обновление: mmw поднимает хороший вопрос, который вы должны быть немного осторожны, как вы вызываете это, поскольку он работает на месте.

 char stack_string[] = "This string is copied onto the stack.";
 inplace_reverse(stack_string);

Это прекрасно работает, так как stack_string - это массив, содержимое которого инициализируется заданной строковой константой. Тем не менее

 char * string_literal = "This string is part of the executable.";
 inplace_reverse(string_literal);

Заставит ваш код загореться и умереть во время выполнения. Это потому, что string_literal просто указывает на строку, которая хранится как часть вашего исполняемого файла - обычно это память, которую вы не можете редактировать в ОС. В более счастливом мире ваш компилятор знает об этом и выдает ошибку, когда вы пытаетесь скомпилировать, сообщая вам, что string_literal должен иметь тип char const *, поскольку вы не можете изменять содержимое. Однако, это не тот мир, в котором живет мой компилятор.

Есть несколько хаков, которые вы можете попытаться убедиться, что некоторая память находится в стеке или в куче (и, следовательно, редактируема), но они не обязательно переносимы, и это может быть довольно уродливо. Тем не менее, я более чем счастлив переложить ответственность за это на функцию invoker. Я сказал им, что эта функция заменяет память, и они обязаны дать мне аргумент, который это позволяет.

Answer 2

Просто перестановка и проверка безопасности. Я также удалил ваш неиспользуемый тип возврата. Я думаю, что это безопасно и чисто, как это получается:

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

void reverse_string(char *str)
{
    /* skip null */
    if (str == 0)
    {
        return;
    }

    /* skip empty string */
    if (*str == 0)
    {
        return;
    }

    /* get range */
    char *start = str;
    char *end = start + strlen(str) - 1; /* -1 for \0 */
    char temp;

    /* reverse */
    while (end > start)
    {
        /* swap */
        temp = *start;
        *start = *end;
        *end = temp;

        /* move */
        ++start;
        --end;
    }
}


int main(void)
{
    char s1[] = "Reverse me!";
    char s2[] = "abc";
    char s3[] = "ab";
    char s4[] = "a";
    char s5[] = "";

    reverse_string(0);

    reverse_string(s1);
    reverse_string(s2);
    reverse_string(s3);
    reverse_string(s4);
    reverse_string(s5);

    printf("%s\n", s1);
    printf("%s\n", s2);
    printf("%s\n", s3);
    printf("%s\n", s4);
    printf("%s\n", s5);

    return 0;
}

Отредактировано так, что end не будет указывать на возможно плохую область памяти, когда strlen равен 0.

Answer 3

Вы можете поместить свой (len/2) тест в цикл for:

for(i = 0,k=len-1 ; i < (len/2); i++,k--)
{
        temp = str[k];
        str[k] = str[i];
        str[i] = temp;

}

Answer 4

Эта полная программа показывает, как я это сделаю. Имейте в виду, что я писал «С», когда большинство из вас, бродяги, были блеском в глазах вашей матери, так что это старая школа, «делайте работу», «длинные имена для слабаков». Исправьте это, если хотите, меня больше интересует правильность кода.

Он обрабатывает NULL, пустые строки и все размеры строк. Я не проверял его на строках максимального размера (max (size_t)), но он должен работать, и если вы обрабатываете строки такого большого размера, вы все равно безумны: -)

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

char *revStr (char *str) {
    char tmp, *src, *dst;
    size_t len;
    if (str != NULL)
    {
        len = strlen (str);
        if (len > 1) {
            src = str;
            dst = src + len - 1;
            while (src < dst) {
                tmp = *src;
                *src++ = *dst;
                *dst-- = tmp;
            }
        }
    }
    return str;
}

char *str[] = {"", "a", "ab", "abc", "abcd", "abcde"};

int main(int argc, char *argv[]) {
    int i;
    char s[10000];
    for (i=0; i < sizeof(str)/sizeof(str[0]); i++) {
        strcpy (s, str[i]);
        printf ("'%s' -> '%s'\n", str[i], revStr(s));
    }
    return 0;
}

Вывод этого:

'' -> ''
'a' -> 'a'
'ab' -> 'ba'
'abc' -> 'cba'
'abcd' -> 'dcba'
'abcde' -> 'edcba'

Answer 5

Попробуйте это:

reverse_string(NULL);
reverse_string("");

Answer 6

Больше никто не использует указатели?

void inplace_rev( char * s ) {
  char t, *e = s + strlen(s);
  while ( --e > s ) { t = *s;*s++=*e;*e=t; }
}

РЕДАКТИРОВАТЬ: Извините, только что заметил приведенный выше пример XOR ...

Answer 7

Вы можете изменить объявление цикла for, чтобы сделать код короче:

char* reverse_string(char *str)
{
    char temp;
    size_t len = strlen(str) - 1;
    size_t stop = len/2;
    size_t i,k;

    for(i = 0, k = len; i < stop; i++, k--)
    {
        temp = str[k];
        str[k] = str[i];
        str[i] = temp;
    }
    return str;
}

Answer 8

Я не вижу оператора возврата, и вы меняете входную строку, что может быть проблемой для программиста. Вы можете захотеть, чтобы входная строка была неизменной.

Кроме того, это может быть придирчиво, но len / 2 следует рассчитывать только один раз, IMO.

Кроме того, он будет работать, если вы позаботитесь о проблемных случаях, упомянутых rossfabricant.

Answer 9

void reverse(char *s)
{
  char *end,temp;
  end = s;
  while(*end != '\0'){
    end++;
  }
  end--;  //end points to last letter now
  for(;s<end;s++,end--){
    temp = *end;
    *end = *s;
    *s = temp; 
  }
}

Answer 10

rev {
int len = strlen(str)-1;
for ( int i =0; i< len/2 ; i++ ) {
        char t = str[i];
        str[i] = str[len-i];
        str[len-i] = t;
        }

}