Как найти последовательность одинаковых символов в строке

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

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

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