Переворот строки c помощью указателей

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

Вот мой вариант ответа:

#include <stdio.h>

void reverse(char *str)
{
 char *p = str;

 while (*p && *(p + 1) && *p++)
  ;

 while ((p > str) && (*str += *p) && (*p = *str - *p) && (*str++ -= *p--))
  ;
}

int main(int argc, char **argv)
{
 char *str = argv[1];
 reverse(str);
 printf("desrever -- %s\n", str);
 return 0;
}

И, разумеется, "hello world":

$ gcc reverse.c -o reverse
$ ./reverse "hello world"
desrever -- dlrow olleh

- Артём

Нахождение последовательностей одинаковых символов в строке с помощью указателей

Понадобилось мне для одной программы найти в строке все последовательности одинаковых символов, и провести с ними необходимые операции (допустим, посчитать и вывести на экран - сейчас это не важно).

Я хочу написать функцию, которой можно было бы скормить передать строку, адрес массива указателей - и получить заполненный массив указателей, каждый элемент которого указывал бы на начало каждой последовательности в строке. Раз уж так, почему бы не посчитать заодно количество последовательностей в строке? Пусть эта функция возвращает значение типа integer - количество найденных последовательностей.

Отлично, теперь пора перейти к реализации.

Считываю строку в массив

Мне понадобится символьный массив размером N, массив указателей на тип char (тоже размером N), переменная для хранения количества последовательностей, счётчик для цикла вывода последовательностей и... всё.

#include <stdio.h>

#define N 256

/* Прототип будущей функции */
int findSequences(const char *arr, char **arrPtr);

int main() {
  char charray[N];
  char *sequence[N];
  int count = 0;
  int i;

  printf("Please enter string:\n> ");
  fgets(charray, N, stdin);

  count = findSequences(charray, sequence);

  // ...

  return 0;
}

/* Полное описание функции */
int findSequences(const char *arr, char **arrPtr) {
  // невидимый текст ;)
}

Кое-что о функциях и их прототипах

Прототип функции не является обязательным элементом программы. Он необходим, если нужно обратиться к функции до её полного объявления, и для проверки передаваемых функции параметров. Например, я мог бы написать полное объявление функции findSequences() до функции main() - в таком случае, мне не потребовался бы её прототип. Но у данного способа объявления функций есть два недостатка:

• Во-первых, если функций много, то главная функция main(), с которой начинается выполнеие любой программы на Си, оказывается где-то далеко в конце файла исходника. Читать такой код стороннему человеку, да и самому тоже, неудобно.
• Во-вторых,иногда нужно сделать так, чтобы функция f1 вызывала функцию f2, а дать полное описание функции f2 до её использования в функции f1 не представляется возможным. А если из функции f1 нужно вызвать f2, а из f2 - f1 (т.е. необходима косвенная рекурсия)? Тогда без прототипов никак не обойтись.

Но при использовании прототипов функций есть одна вещь, которую нужно всегда держать в голове - если я изменил название функции, тип/количество/название принимаемых параметров, тип возвращаемого функцией значения и т.п. - нужно будет изменить и прототип этой функции. Таким образом, мне нужно будет производить изменения в двух местах программы.

Разумеется, никто не требует давать полное описание всех функций до main(), или же после - и использовать прототипы. Можно комбинировать эти два метода, в зависимости от удобства и задачи.

Всё это, конечно, хорошо, но... что насчёт функции findSequences()?

В поисках последовательностей...

Посмотрим ещё раз на прототип функции findSequences():


int findSequences(const char *arr, char **arrPtr);


Ясно, что она возвращает значение типа integer. А в качестве параметров принимает ссылку на начало строки (т.е. на начало символьного массива charray, в котором хранится строка), и указатель на массив указателей. Причём, ключевое слово const перед типом параметра говорит, что этот параметр ни за что, ни при каких условиях не должен (и не будет) изменяться. Что мне и нужно - я хочу, чтобы функция только искала и считала последовательности в строке, а не портила её.

Пришло время заглянуть внутрь функции.

int findSequences(const char *arr, char **arrPtr) {
  char *p = arr;
  int count = 0;

  arrPtr[0] = p;
  while(*p && ('\n' != *p))
    if(*p != *(p+1)) 
      arrPtr[++count] = ++p;
    else
      p++;

  return count;
}

В начале, я создаю указатель на тип char и присваиваю ему адрес первого элемента массива arr. Соответственно, первый элемент массива указателей arrPtr должен содержать ссылку на первый элемент arr (т.к. начало массива - это начало последовательности).

В цикле я перемещаюсь по массиву arr слева направо, перемещая указатель вправо с каждой итерацией. То есть, я прибавляю к указателю единицу, и он смещается вправо по массиву... нет, не на единицу. Он смещается на одну ячейку массива, т.е. на длину типа char.

Цикл while() работает, пока символ по адресу p не равен 0 (т.е. не достигнут конец строки) и не равен '\n' (т.е. символу перевода строки). Звёздочка '*' перед указателем p говорит о том, что я работаю не самим указателем, а с данными, на которые он указывает. В цикле я делаю проверку на определённое событие - если символ *p не равен символу *(p+1), т.е. символу в следующей ячейке массива, то я увеличиваю счётчик найденных последовательностей на 1, передвигаю указатель вправо, чтобы он указывал на следующую ячейку массива, и сохраняю его адрес в массиве указателей. Поскольку знак инкремента '++' стоит до переменной, которую он увеличивает - то действие инкремента, т.е. увеличения значения переменной на единицу, происходит до того, как её значение будет использовано в выражении.

По завершению цикла, я возвращаю значение count, т.е. количество найденных последовательностей в строке.

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

Удаление из строки "лишних" пробелов

У меня есть программа, которая должна запросить у пользователя строку, и произвести с полученной строкой определённые действия. Но вот ведь незадача - некоторые очень неаккуратно работают с клавиатурой, и при вводе данных могут случайно нажать пробел несколько раз вместо одного, добавить совершенно ненужных пробелов в начале строки, или даже в конце. А представьте, что будет, если по клавиатуре пройдётся ваш любимый кот? Это будет катастрофа! Но спокойно, можно предусмотреть и это. Далее я хочу рассмотреть метод (несомненно, один из многих) удаления лишних пробелов из строки.

Для начала определим, какие пробелы считаются лишними. Лишними считаются

1. все пробелы, которые стоят в начале строки (т. е. перед первым символом строки, не являющегося пробелом);
2. пробелы между символами, если количество идущих подряд пробелов равно двум или более;
3. все пробелы в конце строки.

По условию задачи, нельзя пользоваться дополнительными массивами, кроме как массивом для хранения введённой пользователем строки.

Копать или не копать?

Для решения этой задачи удобно использовать так называемый конечный автомат. То есть, некий абстрактный автомат, который может пребывать в конечном количестве состояний. Например, в двух: "копать" или "не копать". Этот автомат будет переключаться из одного состояния в другое, в зависимости от выполнения каких-то условий.

Итак, звучит неплохо. Осталось придумать, как это использовать для решения задачи удаления пробелов.

Но прежде, чем что-то удалять из строки, мне нужна сама строка.

Получаю строку c помощью функции fgets()

Напишем работающую программу, которая считывает строку.

#include <stdio.h>
#include <string.h>
#define N 256

int main() {
  int charray[N];

  printf("Please enter string:\n> ");
  fgets(charray, N, stdin);
  
  return 0;
}

Эта программа пока только считывает строку со стандартного ввода (stdin) с помощью функции fgets() в массив символов размером N.

У функции fgets() есть замечательное свойство - используя её, я никогда не выйду за границу массива, если попытаюсь ввести строку длиннее, чем размер массива. Однако, у неё есть одна особенность: стоит мне ввести строку и нажать [Enter], как в конец введённой строки добавиться знак "\n", т.е. символ перехода на новую строку. Эта проблема решается гениально просто. Нужно лишь узнать длину введённой строки с помощью strlen():

len = strlen(charray); // Определяем длину строки
if('\n' == charray[len-1]) // Если предпоследний символ в строке='\n'
  charray[len-1] = 0;      // то заменяем его на нулевой символ, 
                           // т.е. символ конца строки, он же '\0'

Теперь у меня есть строка, готовая к дальнейшей обработке.

Реализация конечного автомата

Для удаления одного лишнего пробела, нужно сдвинуть элементы массива влево на 1. То есть, если пробел находится на позиции S, то на его место запишется символ из ячейки S+1, вместо S+1 запишется S+2 и т.д.

Идея состоит в следующем: можно использовать один и тот же алгоритм для удаления лишних пробелов в любом месте строки. А раз так, почему бы не вынести действие по удалению пробелов в отдельную функцию, и обращаться к ней, когда потребуется?.. Сказано - сделано.

int remove_spc(char *arr, int len, int pos) {
  int i;
  int len2 = len-1;

  for(i = pos; i <= len2; i++)
    arr[i] = arr[i + 1];

  return 0;
}

Эта функция принимает в качестве аргументов указатель на массив (точнее, на его первый элемент - имя массива всегда указывает на адрес его первого элемента в памяти), длину массива и позицию, начиная с которой нужно начать сдвигать элементы массива.

Самое забавное, что функции remove_spc() всё равно, какой элемент стоит после позиции pos - она так же будет сдвигать все пробелы, которые следуют за этой позицией. Более того, этой функции безразлично, какой элемент стоит на текущей позиции pos

Поэтому мне требуется что-то большее, чем эта функция. Лучше всего подходит для этой цели бесконечный цикл. В него я и помещу свой автомат. К слову, сейчас самое время подумать над его реализацией. Конечному автомату для решения этой задачи потребуется только два состояния, назову их STATE_1 и STATE_2. Находясь в состоянии STATE_1 автомат будет просто проверять, является ли текущий символ в просматриваемом массиве пробелом. Если пробел обнаруживается, автомат переключается в состояние STATE_2. В этом состоянии он будет копать удалять лишние пробелы.

Работу автомата удобно представить ввиде ленты и считывающей/записывающей головки над ней. Пустые ячейки - это пробелы, звёздочками отмечены занятые ячейки, т.е. в которых присутствуют символы, не являющиеся пробелами.

   _______________________________
1 | * | * |   |   |   | * | * | * |
   -------------------------------
        ^
   _______________________________
2 | * | * |   |   |   | * | * | * |
   -------------------------------
            ^
   _______________________________
3 | * | * |   |   |   | * | * | * |
   -------------------------------
                ^
   _______________________________
4 | * | * |   |   | * | * | * |   |
   -------------------------------
                ^
   _______________________________
5 | * | * |   | * | * | * |   |   |
   -------------------------------
                ^

На шаге 1 автомат находится в состоянии STATE_1. Ячейка занята, так что считывающая головка передвигается вправо на одну клетку.

На шаге 2 автомат всё ещё пребывает в состоянии STATE_1. Считывающая головка находится над пустой ячейкой, поэтому автомат перемещает считывающую головку вправо на одну ячейку и переключается в состояние STATE_2. Но здесь не всё так просто. Если мы хотим удалить пустую ячейку в начале строки, то нам не нужно перемещать считывающую головку на следующую ячейку перед переключением в STATE_2.

Теперь посмотрим, что же происходит, когда автомат находится в состоянии STATE_2. А происходит вот что: автомат начинает выкидывать пробелы из строки, вызывая функцию remove_spc (шаг 4). При этом, сама "считывающая головка" остаётся неподвижной, и после каждого вызова функции проверяет содержимое ячейки, над которой она находится.
Как только в ней оказывается какой-либо символ (шаг 5), не являющийся пробелом, автомат переключается вновь в состояние STATE_1.

Вот, как это выглядит в программном коде:

#define STATE_1 1
#define STATE_2 2

...

while(1) {
  switch(state) {
  
  case STATE_1:
    if(' ' == charray[i]) {
      state = STATE_2;
      if(0 == i)
        continue;
    }
    break;

  case STATE_2:
    if(' ' != charray[i])
      state = STATE_1;
    else {
      remove_spc(charray, len, i);
      continue;
    }
    break;

  } // end switch

  i++;

  if(i == len)
    break;

} // end while

А теперь плохая новость. После работы автомата, при количестве лишних пробелов в конце строки больше одного, после последнего символа всё равно оставался один пробел. Я не смог пока разобраться, почему так происходит. Поэтому, после завершения бесконечного цикла while(1), пришлось использовать костыль в виде следующих строчек:

len = strlen(charray);
if(' ' == charray[len-1])
  charray[len-1] = 0;

Этот кусок кода удаляет самый последний пробел, если он остаётся после работы автомата.

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

Исходник:
remove-spaces.c