Записи как средство упаковки параметров

type
TPoint = record
x,y: integer;
end;
TRect = record
x1,y1,x2,y2: integer;
end;
TTriangle = record
v1,v2,v3: TPoint;
end;
procedure DrawRect(x1,y1,x2,y2: integer);
procedure DrawRect(ln,rd: TPoint);
procedure DrawRect(const r: TRect);
function Square (const t: TTriangle);
type
IArrN = record
data: IArr;
n: integer;
end;
procedure wrikArr(const a: IArrN);
begin
for i:=1 to a.n do
write(a.data[i],'_');
end;

Записи с вариантами

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

record
постоянная часть
case имя: тип of // имя - переключатель; указывает, какой вариант рассматривается
значение1:(...);
значение2:(...);
...
end

Пример. Заготовка для библиотеки графических фигур.

type
FigureKind=(kPoint, kCircle, kRect, kLabel);
Figure= record
x,y:real;
case kind: FigureKind of // запись "kind:" не является обязательной
kPoint: ();
kCircle: (r: real);
kRect: (x1,y1: real);
kLabel: (s: string); // ";" может не ставиться
// у case нет end'а!
end;

Как записи с вариантами хранятся в памяти

var f:Figure;

Размер записи с вариантами рассчитывается по большему полю.

procedure DrawFigure (const f:Figure);
begin
case f.kind of
kPoint: DrawPoint(f.x,f.y);
kCircle: DrawCircle(f.x,f.y,f.r);
kRect: Drawrectangle(f.x,f.y,f.w,f.h);
kLabel: DrawText(f.x,f.y,f.s);
end;

С оператором with:

begin
with f do
case kind of
kPoint: DrawPoint(x,y);
kCircle: DrawCircle((x,y,r);
...

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

Сортировка массивов записей

Для сортировки массива записей по различным критериям в процедуру сортировки передают функцию сравнения, которая является бинарным предикатом. Например, для сортировки массива студентов функция сравнения имеет следующий вид:

cmp(a[j+1],a[j])

Эта функция имеет смысл операции "меньше".

BubbleSortStudent(gr1_11,36,LessName);

Индексная сортировка

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

i (виртуальный индекс) → Index[i] (реальный индекс)
a[Index[i]]

В начальный момент времени виртуальный индекс совпадает с реальным, т.е. Index[i]=i. При сортировке мы сравниваем элементы массивов используются виртуальные индексы, а меняем местами элементы индексного массива.

procedure BubbleIndexStudentSort(var a: StArr; var Index: IArr; n: integer; cmp: cmpFunc);
var i,j: integer;
begin
for i:=1 to n do
Index[i]=i;
for i:=n downto 2 do
for j:=1 to i-1 do
if cmp(a[Index[j+1]],a[Index[j]])
then Swap(Index[j+1],Index[j]);
end;

Множества

Множества - совокупность элементов одного порядкового типа (целого, символьного, перечислимого или диапазонного). Во множество может входить несколько элементов одновременно, а может не входить ни одного, каждый элемент входит во множество не более 1 раза. Элементы во множестве не упорядочены. Тип множества описывается следующим образом:
set of <базовый тип>

Примеры.

type
ByteSet = set of Byte;
CharSet = set of Char;
DigitsSet = set of '0'..'9';
DaysSet = set of (Mon, Tue, Wen, Thr, Fri, Sat, Sun);

Замечания. Базовый тип множества должен иметь элементы с порядковыми номерами в диапазоне от 0 до 255.

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

var s1,s2: set of byte;
s1+s2 - объединение множеств
s1*s2 - пересечение множеств
s1-s2 - разность множеств
s1<=s2 - s1 вложено в s2
s1>=s2 - s1 содержит s2
i in s1 - принадлежность: true, если i принадлежит s1

Множества - константы

[1,3..5,8]
[2..10,12,14..18]
[ ] - пустое множество, совместно с любым типом множества
['a', 'e', 'i', 'o', 'u', 'y'] - множество гласных

Добавить элемент к множеству

s:= s + [i];

или

Include(s,i) // если элемент во множестве есть, то ничего не произойдет

Удалить элемент из множества

s:= s – [i]

или

Exclude(s,i)

Цикл по множеству

for i:=1 to 255 do // перебрать все возможные элементы
if i in s then
write(i,' ');

Пример. Вывод всех символов, встречающихся в массиве символов, в алфавитном порядке.

const sym: array [1..25] of char = 'Информационные технологии';
var s: set of char;
...
s:=[ ];
for i:=1 to 25 do
s:=s + [sym[i]]; // Include(s,sym[i]);

// Вывод

for i:=1 to 255 do
if i in s then
write(i,' ');

Пример. «Решето Эратосфера». Вывести все простые числа <= 255.

Алгоритм.

const n=255;
var primes: set of byte;
i,x,c: integer;

begin
primes:=[2..n];
for i:=1 to round(sqrt(n)) do
begin
if not i in primes then
continue;
x:=2*i;
while x<=n do
begin
primes:=primes-[x];
x:=x+i;
end;
end;
for i:=0 to n do
if i in primes then
write(i,' ');
end.