Алгоритмы обработки символьной информации. 1

Оглавление

Алгоритмы обработки символьной информации. 1

Операция присваивания. 3

Операция сцепления. 3

Операции отношения. 3

Функции и команды обработки строк. 3

Процедуры.. 3

Функции. 4

Примеры программ работы со строковыми данными. 5

Записи. 7

Множества. 8

Операции над множествами. 9

Контрольные вопросы.. 11

Комбинированный урок №12

Тема:Символьные переменные и строки. Организация и размещение в памяти. Процедуры и функции обработки строк

Цель: изучить приемы работы с данными типа «строка», приобрести навыки использования строковых процедур и функций Паскаля.

Алгоритмы обработки символьной информации

Символы с кодами от 0 до 127 построены по стандарту ASCII(American Standard Code for Information Interchange — Американский стандартный код обмена…  

Типы данных, используемые для обработки символьной информации

Для данных символьного и литерного типов применимы операции сцепки (соединения, конкатенации) и сравнения (<, >, <=, >=, =, <>).… Операция присваивания Общий вид: Имя строковой переменной := строковое выражение;

Begin

Read(S1,C);

S2:=S1+C+’Yes’;

Write(‘S2=’,S2);

End.

Пусть была введена строка No i. Тогда после выполнения этой программы получим результат: S2=No i Yes.

Операции отношения

Над строковыми данными допустимы следующие операции отношения: =, <>, >, <, >=, <=.Эти операции имеют приоритет более низкий, чем операция сцепления, т.е. вначале всегда выполняются все операции сцепления, если они присутствуют, и лишь потом реализуются операции отношения. Сравнение строк с помощью операций отношения производится слева направо до первого несовпадающего символа. Строка считается больше, если в ней первый несовпадающий символ имеет больший номер в стандартной кодовой таблице.

Результат выполнения операций отношения над строковыми операндами всегда относится к булевскому типу и принимает значение True, если выражение истинно, и False, если выражение ложно. Строки считаются равными, если они полностью совпадают по текущей, а не по объявленной длине и содержат одни и те же символы.

Функции и команды обработки строк

Delete (Var S:String; Poz, L:Integer) видоизменяет строку S, стирая L символов, начиная с символа с номером Poz. Пример: Var S:String[10]; . . .

Примеры программ работы со строковыми данными

Пример 1. Определить количество слов в заданном тексте.

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

Вариант 1. Слова в тексте разделены одним пробелом.

Тест

Данные	Результат
"Кот на крыше"	N=3

Program Probel; Uses Crt; Var Text : String; {заданный непустой текст} i, Number : Integer; {Number — количество слов в тексте} Letter : Char; {текущая буква }BEGIN ClrScr; WriteLn('Введите текст :'); ReadLn(Text); Number:=1; For i:=1 to Length(Text) do {цикл по буквам текста} begin Letter:=Text[i]; If (Letter = ' ') then Number:=Number+1; end; WriteLn('О т в е т : количество слов в тексте равно ', Number);END.

Вариант 2. Слова в тексте разделены произвольным количеством пробелов.

Тест

Данные	Результат
"Кот на крыше"	N=3

 

Program KolSlov;

Uses Crt; Var Text : String; {заданный текст} i, Number : Integer; {Number - количество слов в тексте} Flag : Boolean; Letter : Char; {текущая буква }BEGIN ClrScr; WriteLn('Введите текст :'); ReadLn(Text); Number := 0; Flag := TRUE; For i := 1 to Length(Text) do {цикл по буквам текста} begin Letter := Text[i]; {текущая буква текста } If (Letter <> ' ') and Flag then Number := Number+1; Flag := (Letter=' ') {(Letter=' ') — логическое выражение,} end; {принимающее значения TRUE или FALSE } WriteLn; WriteLn('О т в е т : количество слов в тексте равно ', Number); ReadLnEND. Пример 2. Определить, является ли заданное слово "перевёртышем" (слово называется "перевёртышем", если совпадает с собой после переворачивания).

Система тестов

  Пример 3. B заданном тексте одно заданное слово везде заменить на другое…

Тест

Данные	Результат
Текст	Слово1	Слово2
''2sinx+siny''	''sin''	''cos''	''2cosx+cosy''

Эта программа, использующая стандартную функцию Pos , не требует, чтобы длины заменяемого и вставляемого слов были одинаковыми.

Program Replace; Uses Crt; Var Text, Slovo1, Slovo2 : String; i, DlinaSlova, P : Integer;BEGIN ClrScr; Write('Введите строку : '); ReadLn(Text); Write('Какое слово заменить ? '); ReadLn(Slovo1); Write('На какое слово заменить ? '); ReadLn(Slovo2); WriteLn; WriteLn('О т в е т : '); WriteLn('Исходный текст: ', Text); DlinaSlova:=Length(Slovo1); DlinaSlova:=Length(Slovo1); P:=Pos(Slovo1,Text); {номер позиции, с которой в строке Text } {в первый раз встречается подстрока Slovo1 } While P>0 do {цикл продолжается до тех пор,пока подстрока} {Slovo1 встречается в строке Text } begin Delete(Text, P, DlinaSlova); {удаление подстроки Slovo1, начинаю-} {щейся с позиции P, из строки Text } Insert(Slovo2, Text, P); {вставка подстроки Slovo2 } { в строку Text с позиции Р} P:=Pos(Slovo1, Text); {номер позиции, с которой подстрока Slovo1} {встречается в строке Text в очередной раз} end; WriteLn('Новый текст: ', Text); ReadLnEND.

Пример 4. Заданную последовательность слов переупорядочить в алфавитном порядке (то есть выполнить лексикографическое упорядочение).

Тест

Данные	Результат
Words=(''стул'', ''гора'', ''яма'', ''стол'')	Words=("гора", "стол", "стул", "яма")

Program LexOrder;

Uses Crt; Var Words : Array[1..10] of String; {массив слов} Tmp : String; {Tmp — вспомогательная переменная} i, j, NWords : Integer; {NWords — количество слов}BEGIN ClrScr; Write('Количество слов в тексте — '); ReadLn(NWords); For i := 1 to NWords do begin Write(i, '-ое слово : '); ReadLn(Words[i]) end; For i := 1 to NWords-1 do {лексикографическое упорядочение слов} For j := i+1 to NWords do If Words[i]>Words[j] then begin Tmp := Words[i]; Words[i]:=Words[j]; Words[j]:=Tmp end; WriteLn; WriteLn('О т в е т'); WriteLn('Лексикографически упорядоченный массив слов:'); For i := 1 to NWords do Write(Words[i], ' '); WriteLn; ReadLnEND.

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

Система тестов

END

Записи

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

Запись - это структурированный тип данных, состоящий из фиксированного числа компонентов одного или нескольких типов, называемых полями записи. Определение типа записи начинается идентификатором Record и заканчивается зарезервированным словом end. Между ними заключен список компонентов, называемых полями, с указанием имен полей и типа каждого поля. Структура объявления типа записи такова:

Type <имя типа> = Record

<имя поля1>: <тип компонентов>;

…

<имя поляN>: <тип компонентов>;

End;

VAR <имя переменной>: <имя типа>;

Пример описания записи:

Type Car=Record

Number:Integer;

Marka:String[20];

FIO:String[40];

Address:String[60];

End;

Var Mashina, Mash : Car;

В данном примере была объявлена запись с именем Car, у которой имеется 4 поля: номер, название марки машины, ФИО владельца и его адрес.

Идентификатор поля должен быть уникален только в пределах записи, однако лучше его сделать уникальным в пределах всей программы. Объем памяти, необходимый для записи, складывается из длин полей. Значения полей записи могут быть использованы в выражениях. Обращение к значению поля осуществляется с помощью идентификатора переменной и идентификатора поля, разделенных точкой. Такая комбинация называется составным именем.

Например, доступ к полям записи Car осуществляется как: Mashina.Marka, Mashina.FIO, Mashina.Number. Составное имя можно использовать везде, где допустимо применение типа поля. Для присваивания полям значений используется оператор присваивания, например:

Mashina. Number:=1645365;

Mashina.Marka:=’Volvo’;

Mashina.FIO:=’Иванов И.И.’;

Mashina. Address:=’ул.Пушкина 12-30’;

Составные имена можно использовать в операторах ввода-вывода:

Read (Mashina. Number, Mashina. FIO, Mashina. Address);

Write(Mashina. Number:4, Mashina. FIO:12, Mashina. Address:25);

Допускается применение оператора присваивания и к записям в целом, если они имеют один и тот же тип. Например, Mash:=Mashina;

После выполнения этого оператора значения полей записи Mash станут равны значениям соответствующих полей записи Mashina.

В ряде задач удобно пользоваться массивами из записей. Их можно описать следующим образом:

Type Car=Record

Number:Integer;

Marka:String[20];

FIO:String[40];

Address:String[60];

End;

Var Mashins : array [1..20] of Car;

Обращение к полям такой записи имеет громоздкий вид. Для решения этой проблемы в языке Паскаль предназначен оператор With, который имеет следующий формат:

With <переменная типа запись> do <оператор>;

Один раз, указав переменную типа запись в операторе With, можно работать с именами полей как с обычными переменными,например:

With Mashina do

Begin

Number:=164536l;

Marka:=’Volvo’;;

FIO:=’Иванов И.И’;

Address:=’ул.Пушкина 12-30’;

End;

Множества

Все элементы множества должны принадлежать одному из скалярных типов, кроме вещественного. Этот тип называется базовым типом множества. Базовый тип… Формат записи множественных типов: Type <имя типа> = set of <элемент 1,…., элементN>;

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

При работе с множествами допускается использование операций отношения “=”, “<>”, “>=”, “<=”, объединения, пересечения, разности множеств и операции in. Результатом выражения с применением этих операций является значение True или False.

Операция “равно” (=). Два множества А и В считаются равными, если состоят из одних и тех же элементов. Порядок следования элементов в сравниваемых множествах значения не имеет.

Значение А	Значение В	Выражение	Результат
[1,2,3,4] [‘a’, ’b’, ’c’] [‘a’..’z’]	[1,2,3,4] [‘c’, ‘a’] [‘z’..’a’]	A=B A=B A=B	True False True

Операция “не равно” (<>). Два множества А и В считаются не равными, если они отличаются по мощности или по значению хотя бы одного элемента.

Значение А	Значение В	Выражение	Результат
[1,2,3] [‘a’..’z’] [‘c’..’t’]	[3,1,2,4] [‘b’.. ‘z’] [‘t’..’c’]	A<>B A<>B A<>B	True True False

Операция “больше или равно” (>=). Операция “больше или равно” (>=) используется для определения принадлежности множеств. Результат операции А >=В равен True, если все элементы множества В содержаться в множестве А. В противном случае результат равен False.

Значение А	Значение В	Выражение	Результат
[1,2,3,4] [‘a’..’z’] [‘z’,’x’,’c’]	[2,3,4] [‘b’.. ‘t’] [‘c’,’x’]	A>=B A>=B A>=B	True True True

Операция “меньше или равно” (<=). Эта операция используется аналогично предыдущей операции, но результат выражения А<=В равен True, если все элементы множества А содержаться во множестве В. В противном случае результат равен False.

Значение А	Значение В	Выражение	Результат
[1,2,3] [‘d’..’h’] [‘a’,’v’]	[1,2,3,4] [‘z’.. ‘a’] [‘a’,’n’,’v’]	A<=B A<=B A<=B	True True True

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

Значение А	Значение В		Результат
‘v’ X1	if A in [1,2,3] then.. if A in [‘a’..’n’] then.. if A in [X0,X1,X2,X3] then..		True False True

При использовании операции in проверяемое на принадлежность значение и множество в квадратных скобках не обязательно предварительно описывать в разделе описаний. Операция in позволяет эффективно и наглядно производить сложные проверки условий, заменяя иногда десятки других операций. Например, выражение if(a=1) or (a=2) or (a=3) or (a=4) or (a=5) or (a=6) then…можно заменить более коротким выражением if a in [1..6] then… .

Часто операцию in пытаются записать с отрицанием: X NOT in M. Такая запись является ошибочной, так как две операции следуют подряд; правильная инструкция имеет вид: NOT (X in M).

Объединение множеств (+). Объединением двух множеств является третье множество, содержащее элементы обоих множеств.

Значение А	Значение В	Выражение	Результат
[1,2,3] [‘A’..’D’] []	[1,4,5] [‘E’.. ‘Z’] []	A+B A+B A+B	[1,2,3,4,5] [‘A’..’Z’] []

Пересечение множеств (*). Пересечением двух множеств является третье множество, которое содержит элементы, входящие одновременно в оба множества.

Значение А	Значение В	Выражение	Результат
[1,2,3] [‘A’..’Z’] []	[1,4,2,5] [‘B’.. ‘R’] []	A*B A*B A*B	[1,2] [‘B’..’R’] []

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

Например:

Значение А	Значение В	Выражение	Результат
[1,2,3,4] [‘A’..’Z’] [X1,X2,X3,X4]]	[3,4,1] [‘D’.. ‘Z’] [X4,X1]	A-B A-B A-B	[2] [‘A’..’C’] [X2,X3]

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

Объединение Пересечение Разность

Имеются и отрицательные моменты, основной из них – отсутствие в языке Паскаль средств ввода-вывода элементов множества, поэтому программист сам… Пример. Операции над множествами. uses crt;

Begin

k:=[];

for i:=0 to 20 do if (i in m) and (i mod ch=0) then k:=k+[i];

end;

{процедура вывода множества set_}

procedure out_set(set_:digits);

var i:integer;

Begin

For i:=0 to 20 do

if (i in set_) then write(i:3);

writeln;

end;

Begin

clrscr;

{формирование множества 1}

writeln('Введите последовательность чисел [0..20] (признак конца - 0)');

m0:=[];

read(i);

if i<>0 then m0:=m0+[i];

While (i<>0) do

Begin

read(i);

m0:=m0+[i]

end;

{формирование множества 2}

write ('vvedite chislo '); read(ch1);

Form_Set(ch1,m0,m1);

m2:=[2,4,6,8,10,12,14,16,18,20]; {формирование множества 3}

l:=m1+m2;

f:=m1*m2;

t:=m1-m2;

{вывод множеств}

writeln;

writeln('set m0:'); out_set(m0);

writeln('set m1:'); out_set(m1);

writeln('set m2:'); out_set(m2);

writeln('set m1+m2:'); out_set(l);

writeln('set m1*m2:'); out_set(f);

writeln('set m1-m2:'); out_set(t);

End.

Протокол работы:

Введите последовательность чисел [0..20] (признак конца - 0)

4 3 5 15 18 16 3 0

Введите число 3

Множество m0: 0 3 4 5 15 16 18

Множество m1: 0 3 15 18

Множество m2: 2 4 6 8 10 12 14 16 18 20

Множество m1+m2: 0 2 3 4 6 8 10 12 14 15 16 18 20

Множество m1*m2: 18

Множество m1-m2: 0 3 15

Контрольные вопросы

1. Как описываются строковые данные?
2. Чему равна максимальная длина строковой переменной?
3. Какие операции допустимы над строковыми данными, их приоритет, какие выражения называются строковыми?
4. Какие стандартные процедуры и функции существуют в Паскале для работы со строковыми данными?
5. Что такое запись? Основные операции с записями.
6. Оператор With для обращения к полям записи. Формат записи.
7. Что такое множество? Какие операции используются над множествами?