Иванова Г.С. - Основы программирования
.pdf4. Структурные типы данных
[*а% 'Ь'] = ['Ь% 'а'] - результат операции TRUE; [4, 5, 6] = [4..6] - результат операции TRUE;
['c%'b'] = ['с% 'b% М'] - результат операции FALSE; [2,3, 5,7] <= I1-9] - результат операции TRUE;
[3, 6..8] <= [2..7, 9] - результат операции TRUE; [3, 6..8] <= [2..7, 9] - результат операции FALSE;
[5..8, 9.Л2] >= [6, 8,11] - результат операции TRUE; 10 in [2, 4, 6, 8,10,12,14] - результат операции TRUE;
к in [1, 3, 5, 7, 9] - результат операции TRUE при к=1,3,5 и FALSE при к=2,4,6
Следует помнить, что значения мноэюественного типа нельзя вводить и выводить. Однако можно ввести значения элементов множества и добавить их к множеству, используя операцию объединения множеств, например:
*^«~/У/ |
{исходное множество пусто} |
Read(n); |
|
while not |
Eofdo |
begin |
|
S:=S+[n]; {объединяем исходное множество с элементом} Read(n); {вводим следующий элемент}
end;...
Для того чтобы вывести элементы множества, используют специальный прием: в цикле проверяют вхождение во множество всех элементов базового типа и выводят те, которые входят во множество, например:
fori:='a4o 'z'do
if i in S then Write(i:3);
Рассмотрим несколько примеров решения задач с использованием мно жеств.
Пример 4.20. Разработать программу, которая определяет, является ли введенное слово идентификатором, т.е. начинается ли оно с буквы или знака подчеркивания и не содержит ли специальных символов.
Строим множество символов, которые допустимы в качестве первого: это строчные и прописные буквы латинского алфавита и символ подчеркива ния:
rA'..'Z','a'..'z','J] .
Аналогично определяем множество допустимых символов, которые мо гут встретиться, начиная со второго символа слова:
['A'..'Z','a'..V,'J/0'..'9'].
Программа должна вводить строку, проверять допустимость первого символа, а затем в цикле проверять допустимость остальных символов.
131
Часть 1. Основы алгоритмизации и процедурное программирование
Program ex; |
|
|
|
Var St:string; |
|
|
|
key:boolean; |
|
|
|
i:integer; |
|
|
|
Begin |
|
|
|
WriteLn(*Введите строку'); |
|
|
|
ReadLn(st); |
|
|
|
ifstflj in f^A\. 'Z^'a\, 'z\^__7 then |
{проверка первого символа} |
||
begin |
|
|
|
i:=2; |
|
|
|
key:=true; |
|
|
|
while (i<=length(st)) and key do {проверка остальных символов} |
|||
ifst[i] in ГА\. 'Z\'a\. |
'z\ 1 ^'0\. 'Г] |
then inc(i) |
|
else key: =false; |
|
|
|
if key then WriteLn('Строка |
\st,' - |
идентификатор. *) |
|
else WriteLnf'Строка \st,' содерэюит недопустимые символы.'); |
|||
end |
|
|
|
else |
|
|
|
JVriteLnCCmpoKa \st,' |
начинается с недопустимого символа.'); |
||
End. |
|
|
|
Пример 4.21. Разработать программу для определения количества раз личных цифр в десятичной записи натурального числа.
Для получения требуемого результата модуль введенного числа преоб разуем в строку символов, а затем сформируем множество из этих символов. Теперь проверим, входят ли во множество цифры от О до 9, и те, которые входят, выведем на экран.
Program ex; Var n:longint;
st:string;
mnoj:setof'0\.'9'; i:integer; j:char;
Begin
WriteLn('Введите число: '); ReadLn(n);
Str(abs(n),st); |
|
|
mnoj:-[]; |
{в исходном состоянии множество пусто} |
|
for i:=l to length(st) do |
||
mnoj:=mnoj-^[st[i]]; {формируем множество} |
||
WriteLn('Запись числа \n,' содерэюит следующие цифры: *); |
||
forj:= 'О'to |
'9'do |
{выводим цифры, вошедшие во множество} |
if j in |
mnoj |
then Write(/+' '); |
End
132
4. Структурные типы данных
Пример 4.22. Разработать программу, которая для строки символов, вве денной с клавиатуры и состоящей из нескольких слов, разделенных пробела ми, определяет множество гласных, которые:
•встречаются в каждом слове строки;
•встречаются только в одном слове строки;
•встречаются хотя бы в одном слове строки;
•встречаются более чем в одном слове строки.
Для решения задачи определим тип «множество символов ASCII». Мно жество гласных букв русского языка зададим с помощью типизированной константы множественного типа. Определим переменные множественного типа для хранения результатов и промежуточных значений:
resl - множество гласных, входящих в каждое слово,
res2 - множество гласных, входящих не более чем в одно слово, res3 - множество гласных предложения,
res4 - множество гласных, входящих более чем в одно слово, mnsl - множество гласных, встретившихся в текущем слове.
В программе введем строку и. будем последовательно выделять из нее слова. Для каждого слова построим множество встретившихся гласных букв mnsl.
Если в строке содержится одно слово, то
resl = res2 = res3 = mnsl,
a множество res4 пусто.
Если в строке более одного слова, то каждое новое слово изменяет ре зультирующие множества следующим образом:
1) множество гласных, входящих в каждое слово, будет равно пересече нию уже найденного множества гласных, входящих в каждое слово, и мно жества гласных слова:
resl п mnsl;
2) множество гласных, входящих более чем в одно слово, res4 увеличит ся (объединение) на повторяющиеся буквы нового слова:
res4 U (res3 n mnsl);
3) множество гласных в предложении res3 увеличится (объединение) на множество гласных слова:
res3 U mnsl .
Множество гласных, входящих только в одно слово, res2 будем опреде лять после обработки всех слов как разность множества гласных букв пред ложения и множества гласных, входящих более чем в одно слово предложе ния:
res3 \ res4.
133
Часть I. Основы алгоритмизации и процедурное программирование
Program ex; |
|
|
|
|
|
|
|
Type setchar=set of char; |
|
|
|||||
Const G: setchar - ['а\'я\у\'ю\'э\'е'у'о\'ё\^и\'ы^]; |
{типизирован |
||||||
Var resl, |
|
|
ная константа «множество гласных букв»} |
||||
{множество гласных, входящих в каждое слово} |
|||||||
res2, |
{множество гласных, входящих только в одно слово} |
||||||
res3, |
{множество гласных в предложении} |
|
|||||
res4, {множество гласных, входящих более чем в одно слово} |
|||||||
mnsUsetchar; |
{множество гласных текущего слова} |
||||||
st,slovo: string; |
|
ch: char; |
|
|
|||
ik:integer; |
first: boolean; |
|
|
||||
Begin |
|
|
|
|
|
|
|
WriteLn('Введите исходную строку:'); |
|
||||||
ReadLn(st); |
{читаем исходную строку} |
|
|||||
st:=st'^ * |
V |
{добавляем в конец пробел для простоты обработки} |
|||||
first:"^true; |
{признак «первое слово»} |
|
|||||
while st<> " do |
{цикл выделения и обработки слов} |
|
|||||
begin |
|
|
|
|
|
|
|
k:=pos(* \st); |
|
|
|
|
|||
slovo:=Copy(stJ,k'l); |
{выделяем слово} |
|
|||||
Delete(stJ,k); |
|
{удаляем слово из строки} |
|
||||
{определяем множество гласных, входящих в данное слово} |
|||||||
mnsl:=fj; |
|
|
|
{исходное состояние «пустое множество»} |
|||
for i:=l to к'1 do |
|
|
|
||||
ifslovofij |
in G then |
{если гласная буква, то} |
|||||
|
|
mnsl:=mnsl+fslavefiJJ; |
{добавляем к множеству} |
||||
{формируем множества результатов} |
|
||||||
iffirst |
then |
{если первое слово, то} |
|
||||
begin |
|
|
|
|
|
|
|
resl:=mnsl; |
{входят в каждое слово} |
|
|||||
res2:=mnsl; |
{входят не более чем в одно слово} |
||||||
res3:-mnsl; |
{встретившиеся гласные} |
|
|||||
res4:-[]; |
|
{входят более чем в одно слово} |
|
||||
first:=false; |
{выключаем признак «первое слово»} |
||||||
end |
|
|
|
|
|
|
|
else |
{если не первое слово предложения, то} |
|
|||||
begin resl:=resl*mnsl;
res4:='res4+res3*mnsl; {входят более чем в одно слово} res3:=res3-^mnsl; {встретившиеся гласные}
end
end;
res2:=res3'res4; {входящие в одно слово}
134
4. Структурные типы данных
{выводим результаты анализа предложения}
WnteLn(*DiacHbie, которые входят в каэюдое слово: *); for ch:=#0 to #255 do ifch in resl then Write(ch:2); WriteLn;
WriteLn('Гласные, входящие только в одно слово:'); for ch:=#0 to #255 do ifch in resl then Write(ch:2): WriteLn;
WriteLn(Tлacныe, входящие хотя бы в одно слово:'); for ch:=#0 to #255 do ifch in res3 then Write(ch:2): WriteLn;
WriteLn('Гласные, входящие более чем в одно слово: '); for ch:=#0 to #255 do ifch in res4 then Write(ch:2); WriteLn;
End
Задания для самопроверки
Задание 1. Дан текст, содержащий несколько слов, разделенных пробелом, в конце точка. Разработайте программу, которая, используя множественный тип, опре деляет количество слов текста, содержащих специальные символы «@, #, $, ^, &, _, *, %, ~». Вывести исходную последовательность, количество искомых слов, а также их номера в тексте.
Задание 2. Дан текст, содержащий несколько слов, разделенных пробелом, в конце точка. Разработайте профамму, которая, используя множественный тип, уда ляет из последовательности все слова, включающие хотя бы одну цифру. Вывести исходный и преобразованный текст. Если слов с цифрами не окажется, вывести со ответствующее сообщение.
Задание 3. Дана строка, состоящая из последовательности целых чисел в сим вольном изображении. Числа разделены пробелами (например: «345 6785 1235 54 657»). Разработайте программу, которая формирует множество цифр, присутству ющих в записи всех чисел последовательности. Вывести исходную последователь ность и сформированное множество. (Для приведенной последовательности множе ство.состоит из одного элемента 5.)
Задание 4. Дана строка, содержащая последовательность слов, разделенных пробелами. В словах содержатся буквы латинского и русского алфавита. Разработай те программу, которая формирует и выводит в алфавитном порядке два множества: множество латинских и множество русских строчных букв (кроме ё), встретивших ся в исходной строке.
Задание 5. Дана строка, содержащая последовательность слов из латинских строчных букв, разделенных пробелами. Разработайте программу, которая, исполь зуя множество, вычеркивает из каждого слова строки буквы i, j , к, I, m, п. Вывести исходную и преобразованную строки.
135
Часть 1. Основы алгоритмизации и процедурное программирование
4.8. Записи
Запись - это структура данных, состоящая из фиксированного числарш- нотипных компонент, называемых полями записи. Записи используются для представления разнородной, но логически связанной информации. Каждое поле записи имеет имя, которое дается ему при объявлении записи.
В Borland Pascal определены записи двух типов: записи с фиксирован ными полями и вариантные записи (рис. 4.33).
Записи с фиксированными полями. Синтаксическая диаграмма запи си с фиксированными полями представлена на рис. 4.34.
Как любой тип данных языка, записи можно определить двумя
способами: |
|
|
|
• |
при объявлении переменных, например: |
||
|
Var ZapLZapl: record {две записи, состоящие из 5 полей} |
||
|
F,S:real; {два поля вещественного типа} |
||
|
А, В.'integer; |
{два поля целого типа} |
|
|
C:char; |
{поле символьного типа} |
|
|
end; |
|
|
|
Zap3: record {запись, состоящая из 3 полей} |
||
|
S: string /80/; {символьная строка длиной 80 байт} |
||
|
А: array [1..20] of real; {одномерный массив на 20 |
||
|
Flag:: boolean; |
вещественных чисел} |
|
|
{поле логического типа} |
||
|
end;... |
|
|
• |
предварительно объявив тип записи, например: |
||
|
А record j I АФиксированная |
to, часть |
|
|
|
end |
|
|
часть |
|
|
Вариантная
Рис. 4.33. Синтаксическая диаграмма <Объявление типа записи>
J Идентификатор |
о- |
Тип |
поля
-о- "0--
Рис. 4.34. Синтаксическая диаграмма <Фиксированная часть записи>
136
4. Структурные типы данных
Туре Ztl = record |
|
{тип «запись, состоящая из 5 полей»} |
F,S:real; |
|
{два поля вещественного типа} |
AyB:integer; |
{два поля целого типа} |
|
C'char; |
|
{поле символьного типа} |
end; |
|
|
Zt2 = record |
|
{тип «запись, состоящая из 3 полей»} |
S: string [80]; |
{символьная строка длиной 80 байт } |
|
А: array [1..20] о/ге^^/;{одномерный массив на |
||
Flag: boolean; |
20 вещественных чисел} |
|
{поле логического типа} |
||
end; |
|
|
Var ZapU Zap2:Ztl; |
{две переменные типа Ztl} |
|
Zap3:Zt2; ... |
{переменная типа Zt2 } |
|
В качестве полей записи можно использовать другие записи, определен ные как ранее, так и внутри записи, например:
Туре Human=record |
{запись о сотруднике} |
|
Fio: record |
{поле типа «запись из 3 полей»} |
|
Fam, |
|
{фамилия} |
Name, |
|
{имя} |
Otch: string; |
{и отчество сотрудника»} |
|
end; {Fio} |
|
|
BirthDay: record |
{поле типа «запись из 3 полей»} |
|
Day:!.,31; |
{день} |
|
Month: 1..12; |
{месяц} |
|
Year: word; |
{год рождения} |
|
end; {Birthday} |
|
|
end; ...{Humein} |
|
|
или
Type Data = record Day:L.31;
Month: L.12; Year: word;
end; Famio = record
Fam, Name, Otch: string;
end;
Human = record {тип «запись о сотруднике»} Fio: Famio; {поле типа Famio } BirthDay: Data {поле типа Data }
end;...
137
Часть 1. Основы алгоритмизации и процедурное программирование
Идентификатор |
Идентификатор |
записи |
поля |
Рис. 4.35. Синтаксическая диаграмма <Доступ к полям записи >
Можно объявить как отдельные переменные программы, так и массивы записей, например:
Var Sotr: Human;
Otdel: array [1..20J of Human;
Инициализация записей. Присвоить начальное значение конкретной записи можно, используя типизированные константы. Начальное значение полей записи при этом указывается в скобках через точку с запятой, причем для каждого поля указывается имя и значение через двоеточие, например:
Const
BirthDay: Data = (Year: 1973; Month:6; Day:30); ...
Операции над записями. Над записями возможно выполнение следую щих операций.
Доступ к полям записи. Синтаксическая диаграмма доступа к полям за писи представлена на рис. 4.35.
Например, к полям переменной Sotr типа Human, объявленного выше, можно обратиться следующим образом:
Sotr.BirthDay Day: =-25;
т: =SotKBirthDay. Year;...
В том случае, если доступ к полям записи осуществляется многократно, целесообразно обращаться к полям записи с использованием оператора при соединения with (рис. 4.36). Например, для переменной Sotr типа Human воз можны следующие варианты доступа к полю Day с применением оператора with:
with |
Идентификатор |
ГтЧ^)ч |
Идентификатор |
КЕНЗначение |
записи / поля |
поля |
Рис. 4.36. Синтаксическая диаграмма <Оператор присоединения>
138
|
|
4. Структурные типы данных |
|
а) |
with |
Sotr do BirthDay.Day:=30; |
|
б) |
with |
SotnEirthDay |
do Day: =24; |
в) |
with |
Sotn BirthDay |
do Daay:=31; |
r) |
with |
Sotr do |
|
with BirthDay do Day:= 7;...
Присваивание записей. Операция возможна при совпадении типов запи сей и выполняется последовательно поле за полем. Например:
OtdelfiJ—Sotr;...
Ввод записей с клавиатуры и вывод их на экран выполняются по полям по правилам ввода переменных соответствующих типов.
Пример 4.23. Разработать программу, которая вводит в массив записей информацию о студентах учебной группы: фамилию и дату рождения. Орга низовать поиск информации о студенте, фамилия которого вводится с клави атуры.
Program ex; |
|
|
|
Type |
|
|
|
data=record |
(тип запись данные о дате} |
||
year: word; |
{год} |
||
month:LJ2; |
{месяц} |
||
day:L.31; |
{день} |
||
end; |
|
|
|
zap-record |
{тип запись о студенте} |
||
fam:stringfl 6J; {фамилия} |
|||
birthday:data; |
{дата рождения} |
||
end; |
|
|
|
Var fb:array[L.25] of zap; { массив данных о группе студентов} fff:string; {строка для ввода фамилии} ij,m,n:byte; key.'boolean; {ключ поиска, если фамилия найдена - true}
Begin
WriteLnCВведите данные о количестве студентов п<=25'); ReadLn(n);
т:=0;
{ввод исходных данных с клавиатуры поле за полем}
repeat |
т:=т-^1; |
|
|
|
Write(*Beedume фамилию :'); |
Readln(fb[m].fam); |
|||
Write(*Введите год роэюдения : |
'); Readln(fb[m]Mrthday.year); |
|||
WriteC |
месяц |
: |
'); |
ReadLn(fb[m].birthday.month); |
WriteC |
день |
: |
*); |
ReadLn(fb[m].birthday.day); |
until n=m; |
|
|
|
|
WriteLn; |
|
|
|
|
139
Часть /. Основы алгоритмизации и процедурное программирование
{вывод исходных данных на экране с помощью оператора with}
WnteLn('Список студентов группы '); WriteLn; for /;=7 to т do
withfbfijdo begin
Write(i:2,fam:17); with birthday do
WriteLn(year:6, month:4y day:4);
end;
WriteLn;
{поиск данных в массиве записей}
WriteLn('Beedume фамилию');
ReadLniffJ):
i:=0;
key:=false; {признак «данные не найдены»} repeat i: =1+1;
if/bfij.fam =fffthen key: =true until key or( i=m);
{вывод результата}
if key then {если такой студент найден, то выводим данные} withfb[i]do
begin
WriteLnCДaнныe о студенте : '); Write(fam:18/ ');
with birthday do
WriteLn(day:2,': \month:2, V \year:5,' года');
end
else WriteLn('Данных о студенте : \fff:18,' нет.');
End.
Записи с вариантами. Иногда бывает удобно и естественно рассматри вать несколько типов данных как варианты одного, т. е. в пределах одной за писи иметь различную информацию в зависимости от конкретного значения некоторых полей. Для обеспечения такой возможности запись кроме фикси рованного списка полей может иметь еще и вариантную часть (4.37).
Из диаграммы видно, что вариантная часть может содержать несколько альтернатив, в каждой из которых задается список полей, присущих данному варианту. Каждой альтернативе предшествует константа, идентифицирую щая соответствующий вариант.
Рассмотрим несколько примеров определения записей с вариантами:
•без предварительного описания типа:
140