- •Московский государственный социальный университет
- •Часть I
- •Лекция 1: Введение в программирование.
- •Лекция 2: Язык Паскаль и системы программирования на Паскале.
- •Лекции 3-4: Базисные конструкции языка.
- •Лекции 5-6: Простые операторы и программы с линейной структурой.
- •Лекция 7: Операторы с условиями.
- •Лекция 8: Методика разработки простых программ.
- •Лекция 9: Концепция типа данных.
- •Лекция 10: Структурный тип - Массив.
- •Лекция 11: Структурный тип - Строка.
- •Лекция 15: Структурный тип - Множество.
- •Лекция 16: Структурный тип - Запись.
- •Часть II
- •Лекции 17-19: Модули и их использование.
- •Interface
- •Interface
- •Implementation
- •Interface
- •Implementation
- •Лекция 20: Структурный тип - Файл.
- •Лекции 21-22: Основные задачи обработки файлов.
- •Interface
- •Implementation
- •Лекция 23: Динамическая память и указатели.
- •Лекции 24-25: Использование указателей для представления динамически структур данных.
- •Лекции 26-27: Объекты и объектно-ориентированное программирование.
- •Interface
- •Implementation
- •Оглавление
- •Часть I 3
- •Часть II 53
Лекция 15: Структурный тип - Множество.
1. Понятие о типе Множество в Турбо Паскале.
2. Описание типа Множество и константы-множества .
3. Обработка множеств.
4. Примеры использования множеств .
1. Понятие о типе Множество в Турбо Паскале.
Множество является ещё одним структурным типом Турбо Паскаля, служащим для объединения однородных (однотипных) элементов. Однако форма объединения в Множество существенно отличается от типа Массив. Если в Массиве все элементы линейно упорядочены, то в Множестве - элементы неупорядочены. Понятие Множества в Паскале во многом похоже на конечное множество в дискретной математике и оказывается весьма удобным при решении многих задач управления, оптимизации, поиска и др. Паскаль - один из немногих языков программирования, поддерживающий тип Множество.
Множество в Паскале - набор элементов одного и того же типа (порядкового типа или типа-диапазона), причем порядок элементов безразличен. Отсутствие порядка элементов означает, что нет прямого доступа к элементу множества, однако можно непосредственно проверить входит ли некоторый элемент в данное множество.
Преимуществом типа Множество по сравнению с типом Массив является то, что множество может изменять количество своих элементов при выполнении программы, т.е. оно имеет черты динамической структуры в отличие от статического массива. Однако динамизм множеств лишь относительный: в Паскале количество элементов множества не может быть больше 256. Следовательно, не любой порядковый тип может быть типом элементов множества, а лишь такой, который содержит не более 256 элементов (например, нельзя использовать тип integer, однако можно использовать диапазоны от типа integer).
2. Описание типа Множество и константы-множества.
Формально тип Множество определяется в Паскале как тип, константами (значениями) которого являются все возможные подмножества из элементов базового типа, включая пустое множество. Базовым может быть порядковый тип или его тип-диапазон, содержащий не более 256 элементов, и каждый элемент которого имеет порядковый номер, не более 255. Описание типа Множество имеет форму:
type < имя типа-множества> = set of < базовый тип >;
Как и для других типов, для использования типа Множество необходимо вначале определить переменные этого типа. Например:
type primes = set of 1..200; {множество простых чисел до 200}
var pr1, pr2: primes; { переменные типа primes}
Константы типа Множество должны быть заключены в квадратные скобки (не путайте квадратные скобки для индексации элементов массива - которые всегда записываются только после имени массива, с квадратными скобками, выделяющими константы-множества !).
Одной из констант любого типа-множества является пустое множество, обозначаемое как []. Все другие константы-множества содержат один или более элементов, заключенных в общие квадратные скобки. Для образования констант-множеств используется конструктор множества - список спецификаций элементов множества, отделяемых запятыми и заключенный в квадратные скобки. Каждая спецификация может быть не только константой базового типа, но и произвольным выражением базового типа, а также типом-диапазоном этого же базового типа. Примеры конструкторов множеств:
[2] {множество из одного элемента 2}
[ 0, 2..5] {множество из элементов 0,2,3,4,5}
[1..200] {множество всех чисел базового типа 1..200}
Допускается использование обычных и типизированных констант-множеств, описание которых осуществляется с помощью конструктора множеств. Например:
const initset: set of 0..16 = [0,1,2,4,8,16]; const range=[2..100];
3. Обработка множеств.
Над множествами Паскаля определены теоретико-множественные операции и отношения.
Операции над множествами:
+ операция объединения множеств, результатом её является множество, содержащее элементы множеств-операндов и только их.
Например:[2] + [2..5] даёт множество [2..5];
* операция пересечения множеств, результатом её является множество, содержащее только элементы, общие для множеств-операндов (т.е. входящие во все множества-операнды);
Например: [1..200] *[0,2..5] даёт множество [2..5];
- операция разности множеств, результатом её является множество, содержащее элементы множества-первого операнда и не содержащее элементы множества-второго операнда;
Например: [1..200] - [0,2..5] даёт множество [1, 6..200];
Отношения над множествами - бинарные отношения, имеющие применительно к множествам смысл эквивалентности (неэквивалентности) и включения одного множества в другое.
Два множества считаются эквивалентными, если они имеют одинаковые элементы (порядок перечисления элементов безразличен).
Множество А включено в множество В, если все элементы из А являются также элементами множества В.
= проверка эквивалентности, даёт true , если оба множества эквиваленты и false - в противном случае. Например: [1..3] =[3,1,2] - даёт true.
<> проверка неэквивалентности, является отрицанием эквивалентности.
Например: [1..3] <> [3,2,1] - даёт false.
<= проверка включения левого операнда в правый, даёт true, если такое включение имеет место и false - в противном случае.
Например: [5] <= [1..5] - даёт true, а [0] <=[1..5] - даёт false.
>= проверка включения правого операнда в левый, даёт true, если такое включение имеет место и false - в противном случае.
Кроме отношений эквивалентности и включения имеется ещё отношение принадлежности элемента множеству. Это отношение имеет структуру:
< выражение базового типа> in < множество над этим базовым типом >
Данное отношение дает значение true, если первый операнд является элементом множества - второго-операнда и false - в противном случае.
Например: 3 in [1..5] - даёт true, а 0 in [1..5] - дает false.
Рассмотренные операции и отношения составляют основной набор средств для обработки множеств в программах. Они могут использоваться либо для построения условий, либо - непосредственно в операторах программы. Используя переменные, конструкторы, операции и отношения можно строить выражения типа множества. Для таких выражений допустимы операторы присваивания вида:
< переменная типа-множество> := < выражение типа-множество>;
Например: pr1:= pr2; {копирование множества pr2 в pr1}
pr1:= []; {присваивание pr1 пустого множества}
pr1:= [1..200];{присваивание pr1 множества элементов от 1 до 200}.
Оператор присваивания совместно с операцией объединения или вычитания позволяет включать или исключать элементы из множества:
set1:=set1 + [a]; {включение элемента а в множество set1}
set2:= set2 - [d]; {исключение элемента d из множества set2}
Эти же действия выполняют стандартные процедуры include(set1,a) и exclude(set2,d) соответственно.
4. Примеры использования множеств.
Рассмотрим примеры программ на Турбо Паскале с использованием множеств, иллюстрирующие технику обработки множеств.
program lat_letters;{Определение множества латинских букв в строке}
uses CRT;
var s:string; {исходная строка}
lat:set of 'A'..'Z'; {множество лат.букв}
k:char; j:byte;
begin TextBackground(cyan);TextColor(white);ClrScr;
repeat writeln('Введите строку');readln(s);
if s='' then writeln('Ошибка: пустая строка');
until s<>'';lat:=[];for j:=1 to length(s) do if upcase(s[j]) in ['A'..'Z'] then
lat:=lat+[upcase(s[j])];if lat=[] then writeln('В строке нет латинских букв') else
begin writeln('Латинские буквы:'); for k:='A' to 'Z'do if k in lat then write(k,' ') end;
end { lat_letters}.
program sieve; {Решето Эратосфена - генератор простых чисел <= N}
const N=100;
uses CRT;
var next:integer; {Следующее простое число}
start,prim:set of 1..N; {Исходное множество и множество простых чисел}
k,j:integer;
begin TextBackground(cyan);TextColor(white);ClrScr;
start:=[2..N];prim:=[1];next:=2;
{Формирование в prim множества простых чисел до N}
while start<>[] do begin k:=next;while k<=N do
begin start:=start-[k];k:=k+next end; prim:=prim+[next];
repeat next:=next+1
until (next in start) or (next>N);
end; {Вывод чисел из множества prim}
writeln('Простые числа до ',N,':'); for j:=1 to N do
if j in prim then write(j:3,' ');writeln;
end {sieve}.
Использование множеств в ряде случаев позволяет получать более простые тексты программ, "маскирующие" дополнительные циклы обработки. Например, в программе lat_letters таким "замаскированным циклом" является условие upcase(s[j]) in ['A'..'Z'], которое при отсутствии множеств, потребовало бы для реализации функцию с циклом по типу-диапазону 'A'..'Z'.