пятница, 15 июля 2011 г.

Реверс строки на Си без использования дополнительного буфера

  В интернете прочитал, что в одной компании при собеседовании с программистом (на тему приёма на работу), ему, помимо всего прочего, задают небольшую задачку на Си, которую нужно быстро решить (автор пишет, что должно быть не более 5 строк кода).
Одна из таких задач: выполнить реверс строки, без использования дополнительного буфера. Мне нравится решать задачи, поэтому сел пробовать...
  Первое, что пришло на ум - вместо дополнительного буфера использовать ячейку, в которой хранится '/0' реверсируемой строки.

Визуально такой алгоритм решения задачи будет выглядеть так:


На Си у меня алгоритм получился таким:


//Язык Си, стандарт C89.
//Автор: Андрей Бушман
//Дата: 14 июля 2011, Санкт-Петербург.
#include<stdio.h>
#include<string.h>

//Объявляем функцию реверса
void revstr(register char * str);

int main(){
    int max = 50;
    char x[max];
    printf("Введите строку (не более %d символов): ", max);  
    fgets(x, max, stdin);
    x[strlen(x)-1] = '\0';//Убираем '\n'.
    revstr (x); 
    printf("%s\n", x);
    return 0;
}

//Реверс строки без использования дополнительного буфера
void revstr(register char * str){
    register int i, len = 0;
    //Определяем длину строки
    len = strlen(str);
    //Выполняем реверс символов в строке
    for (i = 0; i <= len / 2; i++){
        *(str + len - i) = *(str + i);  
        *(str + i) = *(str + len - i - 1);
    } 

    //Сдвигаем вторую половину символов влево на 1 символ
    for (i = len / 2; i <= len; i++)
        *(str + i) = *(str + i + 1);
        
    //Устанавливаем символ завершения строки
    *(str + len) = '\0';
}


К сожалению в 5 строк кода уложиться мне не удалось: даже если не считать строки комментариев и строки, содержащие закрывающую фигурную скобку - получилось 9 строк, т.е. почти в два раза больше пяти (я говорю о функции revstr)...
  Подумаю, может удастся сократить объём кода используя рекурсию...

2 комментария:

настя комментирует...

имеется ввиду операция ^(исключающее ИЛИ) она позволяет этот фокус

Анонимный комментирует...

void rev_string(string &str) {
long length = str.length();

for (int j = 0; j < length / 2; ++j) {

str[j] = str[j] + str[length - j - 1];
str[length - j - 1] = str[j] - str[length - j - 1];
str[j] = str[j] - str[length - j - 1];
}
}