Обработка строк текста
9.1. Типы данных CHAR и STRING
В Turbo Pascal имеется два типа данных для работы с текстами: О char — литерный или символьный тип;
П String — СТрОКОВЫЙ ТИП ИЛИ ПрОСТО СТрОКЭ.
Символьный тип
Значением переменных символьного типа char является один символ. Каждому символу соответствует код символа — целое число в диапазоне от О до 255. Из этого следует, что символьный тип является порядковым. В некоторых языках программирования (С, Java) тип char относят к целым типам, что разумно, т. к. в памяти компьютера нет символов —- есть только их числовые коды. Это первый момент, который важно уяснить — все действия по обработке символов, в конечном счете, сводятся к действиям над целыми числами, расположенными строго по порядку.
Над данными символьного типа определены следующие операции отношения: =, о, <, >, <=, >=, вырабатывающие результат логического типа.
Обратите внимание — при выполнении всех операций сравнения коды символов сравниваются как обычные целые числа. При этом получается, что любая заглавная буква всегда меньше соответствующей ей строчной, т. к. в кодовой таблице сначала располагаются все заглавные буквы, а затем строчные (см. приложение 2). Точно так же любая буква латинского алфавита всегда меньше любой буквы русского алфавита, даже если их изображения на экране практически неразличимы (А латинская, А русская).
Для данных символьного типа определены следующие стандартные функции: П chr(x) — возвращает значение символа по его коду;
П ordfch) —- возвращает код заданного символа ch; П pred(ch) — возвращает предыдущий символ; О succ(ch) — возвращает следующий символ;
П upcase(ch) — преобразует строчную букву в заглавную. Обрабатывает буквы только латинского алфавита.
Например:
П ord('A')=65
О спг(128)='Б'
О pred('B'}='A>
CJ succ(T') = 'flr
upcase('n')='N'
Строковый тип
Строка — это последовательность символов. Максимальное количество символов в строке (длина строки) может изменяться от I до 255. Переменную строкового типа можно определить через описание типа в разделе определения типов или непосредственно в разделе объявления переменных.
Type
ИмяТипа = string [максимальная длина строки];
Var
Идентификатор,
ИмяТипа;
Строковую переменную можно задать и без предварительного объявления
типа:
var
Идентификатор,
string[MaKc. длина строки];
ИЛИ var
Идентификатор,...: string;
Если максимальная длина строки не указывается, то она равна 255 байт.
Строковые данные могут использоваться в программе также в качестве констант.
Например:
const stradres = 'ул. Мира, 35'; { строковая константа }
sadr: string[12] = ' ул. Мира' { типизированная константа, ее можно использовать как обычную переменную ]
type str!25 = string [125];
var strl:str!25; { описание с заданием типа }
stl: string; { по умолчанию длина строки = 255 |
st2,st3: string[50];
strnazv: string[280]; { ошибка, длина больше 255 }
В дальнейшем во всех примерах для удобства будем начинать имена всех переменных строкового типа с буквы з.
Строка в языке Turbo Pascal трактуется как массив символов. Для строки из п символов в памяти отводится п+l байт; п байтов — для хранения символов строки, а один дополнительный байт — для значения текущей длины строки. Этот дополнительный байт имеет номер 0, соответственно первый символ строки имеет номер 1, второй — номер 2 и т. д.
Например, переменная sadr типа string [12] хранится в памяти таким образом (табл. 9.1).
Таблица 9.1. Распределение памяти для хранения переменной
Всего строка занимает 13 байтов, из них последние 4 байта оказались незанятыми, т. к. реальная длина строки составляет 8 символов, это значение и хранится в нулевом байте строки. Незанятые байты составляют "хвост" строки, в котором может быть любой "мусор", однако программа не будет обращаться к "хвосту", т. к. реальный размер строки ей известен.
(Замечание ~^)
Из этого представления понятно и ограничение на максимальную длину строки — 255 символов, т. к. для хранения длины строки отведен всего один байт (максимальное двоичное число, которое можно уместить в один байт, — восемь подряд идущих единиц, что соответствует десятичному числу 255).
К любому символу в строке можно обратиться как к элементу одномерного массива
array [0.. n] of char
по номеру (индексу) данного символа в строке. Индекс определяется выражением целочисленного типа, которое записывается в квадратных скобках, как для массива.
Обратите внимание — в отличие от массивов переменные строкового типа могут участвовать целиком в операторах ввода/вывода.
Например, readln(stl); writeln(st2>;
При вводе строки количество символов в ней определяется автоматически, при этом автоматически заполняется нулевой байт. Для получения длины строки имеется функция length, которая возвращает значение нулевого байта строки (см. разд. 9.3).
Разумеется, никто не запрещает вводить и выводить строки по отдельным символам, как массивы, используя любой из операторов цикла. Однако такая необходимость возникает редко. Посимвольный ввод строки стоит реализовать только в том случае, если необходимо совместить ввод и какую-то обработку символов (см. листинг 9.9). Посимвольный вывод также удобно использовать для какой-либо нестандартной формы вывода.
Приведем пример, в котором исходная строка вводится целиком, а выводится по отдельным символам (листинг 9.1). В данном случае программа сначала выводит строку в "перевернутом" виде (например, вводим РОЗА, а выводится АЗОР). Затем та же строка выводится в прямом виде, но каждое слово с новой строки. Считаем, что слова разделены пробелами, причем не обязательно одиночными. Обратите внимание на условие, которое проверяет начало нового слова. Разбивка строки на слова — это типовое действие со строками.
Листинг 9.1. Вывод строки в перевернутом виде и по отдельным словам
var s:string;
i: integer; begin
write('Введите строку');readln(s);
for i:=length(s) ciownto 1 do write (s[i]);
for i:=l to length(s)-l do
if (s[i]) = ' ') and (s[i+l]<>' ') then writeln
else write(s[i]); readln; end
Еще один пример, в котором выполняется обработка строки как массива символов. Данная программа (листинг 9.2) проверяет правильность расстановки скобок в выражении (можно считать ее маленькой частичкой компилятора, т. к. перед преобразованием любого выражения в исполнимый код всегда проверяется правильность расстановки скобок). В последней главе (см. листинг 13.3) приводится пример программы для решения аналогичной задачи в более сложной постановке.
;•.......... -.................................:................ •;•"".............;•'-'................ '•........... """'.'..............................................................,,,.,..„..................................................... j
^Листинг 9.2. Проверка баланса скобок в скобочном выражении
var k,i:integer;{ k — номер символа, i — для определения баланса скобок)
s:string;
begin
writeln('Введите скобочное выражение:']; readln(s);
k:=l; i:=0;
while (k<=length(s)) and (i>=0) do
begin
{ если i<0, то выражение неправильно: ')' предшествует '(' }
if s[k]-'(' then i:=i+l;
if s[k]='} ' then i:=i-l,-
k:=k+l; ehd;
if i=0 then writeln('Скобки расставлены правильно.')
{ если i>0, то не хватает закрывающихся скобок }
else writeln{'Скобки расставлены неправильно'};
readln * *
end.
Операции над строками
Над строковыми данными допустимы операция сцепления (конкатенации) и операции отношения. Используя строковые переменные, константы, функции и операцию сцепления, можно строить строковые выражения.
9.2.1. Операция сцепления (+)
Применяется для соединения нескольких строк.
Например:
Выражение: 'Turbo' + ' Pascal' + '7.0'
Результат: Turbo Pascal 7.0'
Обратите внимание— операция конкатенации, в отличие от операции сложения в математике, не подчиняется известному правилу: "от перестановки слагаемых сумма не меняется", в этой операции каждый из операндов должен находиться строго на своем месте.
Замечание j
Для того чтобы предоставить программистам возможность использовать один и тот же знак операции "+" для работы с данными разных типов, разработчикам компилятора Turbo Pascal пришлось изрядно потрудиться. При обработке текста программы компилятор анализирует типы операндов и формирует для операции "+" различные машинные коды для целых, вещественных и строковых типов. Такое явление в программировании принято называть полиморфизмом. Запомните этот термин— он пригодится на следующих этапах постижения искусства программирования.
Для присваивания строковой переменной результата строкового выражения используется оператор присваивания.
Например: strl:= Труппа учащихся'; str2:= strl + ' школы-лицея';
Приведем пример использования операции конкатенации (листинг 9.3). Допустим, необходимо дополнить исходную строку справа символом '*' до заданной длины. Такое действие иногда выполняют при формировании важных денежных документов, чтобы нельзя было ничего вписать в пустые места.
[Листинг 9.3.Дополнение строки звездочками '
!...-..;.-...:.........-•.;.!.'..:.:....:... :..:.'...... -...
var s:string;
procedure dopstr(var s:string; n:integer);.
begin
while length(s)<n do s:=s+'*'; end; begin
writeln('Введите строку:');readln(s};
dopstr(s,80); writeln(s); readln end.
Если в тексте процедуры поменять s+' *' на ' *' +s, то строка будет дополняться пробелами не справа, а слева. Было бы разумно добавить в процедуру dopstr еще два параметра: символ, которым следует дополнять строку, и способ дополнения строки (слева, справа, слева и справа равномерно).
Обратите внимание — все строковые типы считаются совместимыми по присваиванию, т. е. можно присваивать друг другу значения строк различного размера. К сожалению, размеры строк при этом не контролируются. Если значение переменной после выполнения оператора присваивания превышает по длине максимальный размер, указанный при объявлении, все лишние символы справа отбрасываются, что важно!
Например:
const si:string[13]='Turbo Pascal';
var s2:string[5];
begin
s2:=sl;...
Переменная s2 при этом получит значение 'Turbo', т. к. присваиваемое значение 'Turbo Pascal1 не разместить в тех пяти байтах, которые отведены под символы переменной s2. Фактически операция присваивания будет выполнена неверно, хотя никакого сообщения об ошибке не будет выдано.
Замечание
При отладке задач со строками целесообразно помещать в программу директиву {$R+}, которая проверяет выход за пределы диапазона изменения индекса. Однако в приведенном выше случае и это не поможет. Остается надеяться только на свою внимательность!
При передаче строки в качестве параметра процедуры совместимость строк разной длины возможна только при отключенной директиве компилятора строгой проверки типов строк ($v-). По умолчанию она включена — {$v+}, поэтому строковые параметры (и формальный, и фактический) должны бьЕТЬ одного размера. Рекомендуем использовать данную директиву, но с осторожностью, т. к. есть риск потери символов справа, если не хватит места в той строке, которая передается в качестве фактического параметра.
Операции отношения
Операции =, <>, >, <, >=, <= выполняют сравнение двух строковых операндов и используются в основном при проверке условий. Сравнение строк производится слева направо до первого несовпадающего символа, и та строка считается большей, в которой код первого несовпадающего символа больше. Такой способ сравнения строк называют лексикографическим. Строки считаются равными, если они совпадают по длине и содержат одни и те же символы.
Например:
Выражение: Результат:
'Иванов '='Иванов И.И. ' false
'Иванов'<'Иванов И.И.' true
'program1 >' PROGRAM1 true
Операции отношения над строковыми данными широко используются при обработке массивов строк. Наиболее важными действиями над такими массивами являются:
П сортировка массива в лексикографическом порядке; П быстрый поиск данных в отсортированном массиве; П слияние двух отсортированных массивов.
При решении данных задач используются те же самые алгоритмы, что и для числовых массивов (см. разд. 4.2.3), достаточно только заменить тип элементов массива на тип string. Например, при организации электронного телефонного справочника огромный массив абонентов обычно сортируется, и за счет этого можно в считанные секунды найти телефон абонента по его фамилии.
В данном разделе приведем в качестве примера алгоритм слияния двух отсортированных массивов строк (листинг 9.4). Допустим, происходит слияние двух предприятий и требуется объединить списки сотрудников таким образом, чтобы не нарушить алфавитного (лексикографического) порядка.
I Листинг 9.4. Слияние двух отсортированных массивов строк,
const m=4; n=3;
a: array [1..m] of string=('Абрамов1, 'Григорьев', 'Иванов', 'Сидоров' b:array [l..n] of string= ('Васильев', 'Петров ', 'Яковлев');
var crarray [1..m+n] of string;
k, i, j: integer; (индексы трех массивов}
begin
э.
for k:=l to m+n do
{ если индекс i вышел за пределы массива а или b[j]<a[i] }
if (i>ra) or (b[j]<a[ij) then
begin
c[k]:=b[j]; j:=j+l; end else begin
c[k]:=a[i]; i:=i+l; end;
writelnf 'Массив с:');
for k:=l to m+n do write (c[k],' '); readln end.
