Операции над строками

Строки

Строка – линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом. Строки обладают следующими свойствами:

- длина, как правило, переменна, хотя алфавит фиксирован;

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

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

Говоря о строках, обычно имеют в виду текстовые строки – строки, состоящие из символов, входящих в алфавит какого-либо выбранного языка, цифр, знаков препинания и других служебных символов. Однако следует иметь в виду, что символы, входящие в строку могут принадлежать любому алфавиту. Так, в языке PL/1, наряду с типом данных «символьная строка» CHAR(n) существует тип данных «битовая строка» BIT(n). Битовые строки, составляются из однобитовых символов, принадлежащих алфавиту: {0,1}. Все строковые операции применимы как к символьным, так и к битовым строкам.

Хотя строки рассматриваются в главе, посвященной полустатическим структурам данных, в тех или иных конкретных задачах изменчивость строк может варьироваться от полного ее отсутствия до практически неограниченных возможностей изменения. В большинстве языков программирования (C, PASCASL, PL/1 и др.) строки представлены полустатическими структурами.

В зависимости от назначения языка средства работы со строками занимают в языке более или менее значимое место. Язык C является языком системного программирования. Типы данных, с которыми работает язык C, максимально приближены к типам, с которыми работают машинные команды. Поскольку машинные команды не работают со строками, в языке C нет такого типа данных. Строки в C представляются в виде массивов символов. Операции над строками могут быть выполнены как операции обработки массивов или при помощи библиотечных (не встроенных) функций строковой обработки.

В языках универсального назначения строковый тип обычно является базовым: STRING в PASCAL, CHAR(n) в PL/1. Основные операции над строками реализованы как базовые операции или встроенные функции. Специальные библиотеки обеспечивают расширенный набор строковых операций.

Язык REXX ориентирован на обработку текстовой информации. Поэтому в языке нет средств описания типов данных: все данные представляются в виде символьных строк. Операции над данными, не свойственные символьным строкам, выполняются специальными функциями, либо приводят к прозрачному преобразованию типов. Например, интерпретатор REXX, встретив оператор, содержащий арифметическое выражение, сам переводит его операнды в числовой тип, вычислит выражение и преобразует результат в символьную строку. Целый ряд строковых операций является простыми операциями языка, а встроенных функций обработки строк в REXX несколько десятков.

Базовыми операциями над строками являются:

- определение длины строки;

- присваивание строк;

- конкатенация (сцепление) строк;

- выделение подстроки;

- поиск вхождения.

Операция определения длины строки есть функция, возвращаемое значение которой – целое число – текущее число символов в строке. Операция присваивания имеет тот же смысл, что и для других типов данных.

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

Результатом операции сцепления двух строк является строка, длина которой равна суммарной длине строк-операндов. Как и во всех операциях над строками, которые могут увеличивать длину строки (присваивание, сцепление, сложные операции), возможен случай, когда длина результата окажется большей, чем отведенный для него объем памяти. Проблема возникает только в тех языках, где длина строки ограничивается. Возможны три варианта решения проблемы, определяемые правилами языка или режимами компиляции:

- не контролировать превышение, возникновение такой ситуации неминуемо приведет к труднолокализуемой ошибке;

- завершать программу аварийно с локализацией и диагностикой ошибки;

- ограничивать длину результата в соответствии с объемом отведенной памяти;

Операция выделения подстроки выделяет из исходной строки последовательность символов, начиная с заданной позиции n, с заданной длиной l. В языке PASCAL соответствующая функция называется COPY. В языках PL/1, REXX соответствующая функция – SUBSTR – обладает свойством, отсутствующим в PASCAL: она может применяться в левой части оператора присваивания. Например, если исходное значение некоторой строки S – 'ABCDEFG', то выполнение оператора SUBSTR(S,3,3)='012' изменит значение строки S на – 'AB012FG'.

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

На основе базовых операций могут быть реализованы и любые другие более сложные операции. Например, операция удаления из строки символов с номерами от n1 включительно n2 может быть реализована как последовательность следующих шагов:

- выделение из исходной строки подстроки, начиная с позиции 1, длиной n1-1;

- выделение из исходной строки подстроки, начиная с позиции n2+1, длиной длина исходной строки – n2;

- сцепление подстрок, полученных на предыдущих шагах.

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

Дата добавления: 2014-01-07