1.8. Строки и операции над ними Си
 

Строки относятся к фундаментальным типам данных. Строка это последовательность символов, принадлежащих конечному множеству символов (алфавиту). Представление строк в языке программирования определяется стандартами этого языка.

В языке Паскаль предусмотрен строковый тип STRING. Максимальная длина строки равна 255. текущая длина строки S находится в начальном байте строки S[0].

В языке Си строковый тип не предусмотрен, строкой служит массив данных символьного типа char, определяется как char S[n], где n – максимальный размер строки типа unsigned. Заметим, что в прототипах стандартных функций Си используется другое определение этого типа: typedef unsigned size_t. Конец строки определяется нулевым символом '\0' (байт, все биты которого нулевые), текущая длина строки равна числу символов до символа '\0' исключая его. Массив символов без конечного символа '\0' не можем рассматриваться как строка, это просто массив символьных данных. В языке предусмотрена строковая константа (литерал) это последовательность символов, заключенная в двойные кавычки, например "Структуры данных". Строковая константа заканчивается нулевым символом '\0'

Для эффективного манипулирования строками современные системы программирования содержат обширные средства и функции.

Рассмотрим алгоритмы выполнения некоторых операций над строками применительно к языку Си и прототипы соответствующих стандартных функций.

Создание и инициализация строки. Строка определяется как массив данных символьного типа, например char S[80]. Транслятор выделяет под массив 80 байт, значит, максимальная длина строки будет 79 символов. В Си не предусмотрен механизм контроля выхода за пределы массива (строки), поэтому ответственность за правильность использования строки несет программист. Если массив определен как автоматический (в пределах функции), то выделенную область памяти транслятор не очищает, статические массивы инициализируются нулевыми байтами, а это означает, что текущая длина строки равна нулю.
Строка может быть инициализирована при ее определении: char S[40]="ЭTO стро-ка данных"; здесь оставшиеся свободными байты инициализируются нулями. Од-нако нельзя присвоить та¬кой строке новое значение оператором присваивания, например, оператор S="Hовая строка" является ошибочным. Можно определить динамическую строку:
char* S1; Sl=(char*) calloc(40,sizeof(char)):

Только такой строке в любой момент оператором присваивания можно присвоить значение строковой константы: S1="Иванов Иван Иванович".

Определение длины строки S. Осуществляемся последовательным просмотром и подсчётом символов S[i], пока не встретится символ конца строки '\0'. Прототип функции:
size_t strlen(const char *S): результат (возвращаемое значение) - длина строки в байтах.

Заполнение строки заданным символом. Осуществляется только в пределах текущей длины строки, т.е. все символы строки от начала до конечного символа “\0” заменяются заданным символом, при этом длина строки остается прежней. Прототип функции: char* strset(char *S, int с), результат — указатель на начале строки S.

Заполнение части строки заданным символом. Отличается тем что заполняется только заданное число n символов, но в пределах текущей длины строки. Прото-тип функции: char* strnset(char *S, int c, size_t n).

Копирование строки S2 в строку S1. Строка S1 заполняетcz символами из строки S2, включая символ конца строки '\0'. Контроль выхода за пределы массива под строку S1 не осуществляется, это возлагается на программиста. Прототип функции: char* strcpy(char *S1, char *S2), результат — указатель на строку S1.

Соединение (конкатенация) строк S1 и S2. К концу строки S1 начиная с символа конца строки '\0' копируется строка S2. Строка S2 сохраняется. Длина строки S1 становится равной сумме длин строк S1 и S2, поэтому память, выделенная под S1, должна быть не меньше этой длины. Прототип функции: char* strcat(char S1, const char* S2), возвращаемое значение указатель на строку S1.

Можно предложить другой вариант этой операции, когда соединением двух строк создается новая строка в динамической памяти.

Сравнение двух строк S1 и S2. Осуществляется посимвольным сравнением строк. Так как длины строк L1 и L2 могут отличаться, то число сравниваемых символов ограничивается значением min(L1,L2)+l. В этом случае последними сравниваются символ из более длинной строки и нулевой символ "\0" замыкающий короткую строку. Сравнение строк заканчивается, когда будут исчерпаны все сравниваемые символы либо при неравенстве очередной пары символов. Результат операции определяется результатом последнего сравнения:
(S1[i] == S2[i]) - равен нулю.
(S1[i] < S2[i]) - меньше нуля.
(S1[i] > S2[i]) - больше нуля.
Прототип функции:
int strcmp(const char *S1, const char *S2). В ранних версиях TCи сравнение проводится в предположении, что символы принадлежат к типу signed char. Это приводит к ошибочным результатам при сравнении строк типа «Иванов» и «Иван», когда начальные символы совпадают, а последний сравниваемый символ более длинной строки является символом из второй половины кодовой таблицы.

Поиск и выделение лексических единиц в строке. Является полезной операцией для выделения отдельных частей строки, разделенных заданными символами- ограничителями. Прототип функции:
char* strtok(char *S1, const char *S2); в строке S1 осуществляется поиск до первого любого символа-ограничителя, заданного строкой S2. Найденный символ- ограничитель в строке S1 заменяется символом конца строки '\0'. Возвращаемое значение — указатель на начало строки. Таким образом, в виде урезанной начальной строки выделяется первая лексическая единица, а исходная строка оказывается разбитой на две строки по месту первого найденного символа-ограничителя, но этого символа в строке S1 уже нет. Если нужно выделить все лексические единицы в строке S1, то достаточно вызывать функцию strtok с первым аргументом, равным NULL, до тех пор, пока возвращаемое значение не станет равным нулю (NULL). Если в строке S1 встретится несколько подряд идущих символов из строки S2, то первый из них заменился символом '\0' остальные останутся на месте, однако следующий оператор strtok пропустит их и вернет указатель на следующую лексему.

Важнейшими операциями для манипулирования строками являются операции поиска по образцу. Поиск по образцу в строке считается успешным, если в ней найдена подстрока или символ, соответствующие образцу с точки зрения заданного условия или совокупности условий.

Поиск заданного символа в строке. Имеет две разновидности. Поиск первого вхождения символа oпределяет позицию, в которой встретился заданный символ при последовательном просмотре символов с начала строки. Поиск последнего вхожденияОтличается тем, что просмотр символов идет от конца строки к ее началу. Прототипы функций:
char* strchr(const char *S, int с) и char* strrchr(const char *S, int c), возвращаемое значение указатель на найденный символ или NULL, если символ не найден.

Поиск в основной строке S1 символов, заданных в строке S2. Имеются три разновидности операции. Первая из них — поиск в строке S1 первого вхождения одного из символов, заданных в строке S2. Осуществляется просмотр символов Sl[i], начиная с начала строки и до ее конца. Если очередной символ Sl[i] совпадает с любым из символов строки S2, то поиск прекращается. Возвращаемое значение — указатель на найденный символ или NULL, если в строке не оказалось символов из строки S2. Алгоритм основан на простом переборе: с каждым символом S[i] сравниваются все символы из строки S2, следовательно, временная сложность в худшем случае O(L1*L2), где L1 и L2 — длины строк S1 и S2 соответственно. Прототип функции:
char* strpbrk(const char *S1, const char *S2).

Вторая операция отличается от первой только тем, что определяется длина начальной части строки S1, в которой нет символов из строки S2. Прототип функции:
size_t strspn(const char *S1, const char *S2).

Третья операция отличается от второй тем, что определяется длина начальной части строки S1, в которой содержатся только такие символы, которые принадлежат множеству символов из строки S2. Прототип функции:
size_t strcspn(const char *S1, const char *S2).

Поиск подстроки (образа) S2 в строке S1. Является наиболее широко используемой операцией. Очевидно, что длина L2 подстроки S2 не может быть больше длины L1 строки S1. Прототип функции:
char* strstr(const char *S1,const char *S2). Возвращаемое значение указатель на первый символ найденной в S1 подстроки.

Известно несколько алгоритмов поиска подстроки в строке. В алгоритме прямого перебора сначала первые L2 символа строки S1 сравниваются с соответствующими символами образа S2. Если все символы в парах окажутся равными, то на этом поиск заканчивается. В противном случае образ S2 сдвигается в строке S1 на одну позицию вправо и осуществляется сравнение следующих L2 символов и так до тех пор, пока либо все символы не совпадут, либо после (L1-L2) сдвигов не будет достигнут конец строки S1. Результатом является указатель на первый символ в строке S1, с которого начинается искомая подстрока в случае удачи, либо NULL. если подстрока не найдена. Этот алгоритм достаточно эффективен в том случае, когда несовпадение пары символов происходит после всего лишь нескольких сравнений.

Улучшением рассмотренного алгоритма являются алгоритм Кнута, Мориса и Пратта (1970 г.) и алгоритм Боуера и Мура (1975 г.). Эти алгоритмы основаны на том, что после неудачного поиска на очередном интервале сдвиг образа S2 может осуществляться не на одну, а на несколько позиций вправо в зависимости от некоторых условий.

Алгоритм Кнута, Мориса и Пратта базируется на том, что после частичного совпадения начальной части образа S2 с соответствующими символами строки S1 и при несовпадении очередной пары символов образ S2 сдвигается в строке S1 на пройденное расстояние, если в нем нет начального символа образа S2, либо до позиции с начальным символом. Этот алгоритм дает выигрыш только тогда, когда после очередного сдвига неудаче предшествует некоторое число совпадений символов. Лишь в этом случае образ может быть сдвинут более чем на единицу.

Алгоритм Боуера и Мура отличается от алгоритма Кнута и К* тем, что сравнение символов начинается с конца образа и идет к его началу. Длина сдвига в случае неудачи, т.е. при несовпадении сравниваемых символов S1_j и S2k, может лежать в пределах от 1 до длины образа-строки М. Это зависит от наличия и места расположения символа S1_j в образе S2.

Для всех символов, входящих в образ S2, кроме последнего, длина сдвига образа устанавливается так: для предпоследнего символа она равна 1, для следующего от конца - 2, затем --- 3 и т.д., для первого (М-1), где М -— длина образа S2. Если в образе один и тот же символ встречается несколько раз (без учета последнего символа), то для него устанавливается наименьшее значение. Для всех остальных символов алфавита, который используется для представления строк S2 и S1, в том числе и для последнею символа, если он не повторяется в образе, длина сдвига устанавливается равной длине образа S2.

При несовпадении любой пары символов S1_j и S2k осуществляется сдвиг на величину, установленную для первого с конца символа сравниваемой части строки S1_j. Таким образом, если сравнение началось с символа S1_j, а несовпавшим символом является любой сравниваемый символ S1_j, то сдвиг будет на одну и ту же величину, установленную для символа S1_j.