Использование переменных ссылочного типа

Необходимость использования переменных ссылочного типа возникает при различных ситуациях. Рассмотрим наиболее часто встречающиеся ситуации.

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

Задача 9.Дано 10000 вещественных чисел а1, а2, ..., а10000и 8000 целых чисел b1, b2, ..., b8000. Вывести числа а1, а2, ..., а10000в обратном порядке. Вывести то число bk, номер которого k равен минимальному из чисел b1, b2, ..., b8000.

Программа

Program Task9;

Type ra = array [1 .. 10000] of Real;

ia = array [1 .. 8000] of Integer;

pr = ^ra; pi = ^ia; {Определили ссылочный тип}

Var k, i : Integer; f : pr; g : pi; {Описали ссылочные переменные}

Begin

New (f); {Выделили память под массив из 10000 элементов}

For i := 1 to 10000 do Read(f^[i]);

For i := 10000 downto 1 do Writeln(f^[i]);

Dispose (f); {Освободили выделенную память}

New(g); {Выделили память под массив из 8000 элементов}

Read(g^[1]); k := g^[1];

For i := 2 to 8000 do

Begin

Read(g^[i]); If g^[i] < k Then k := g^[i]

End;

Writeln(g^[k]) {В конце программы оператор Dispose можно опустить}

End.

В этой программе сначала отводится место для массива из 10000 элементов. Переменные f^[1], ..., f^[10000] получают значения с помощью оператора Read(f^[i]). После решения первой задачи – вывода этих чисел в обратном порядке, место в памяти, выделенное для объекта типа ra, осво­божда­ется с помощью Dispose(f). После этого отводится место в памяти для массива из 8000 элементов. Переменные g^[1], ..., g^[8000] получают значения с помощью оператора Read(g^[i]), и решается вторая часть задачи. Память для объектов типа ra и ia выделяется поочередно, так что эти объекты могут располагаться в пересекающихся областях памяти вычислительной машины.

Случай 2. Программа во время компиляции использует данные, для которых заранее неизвестен необходимый объем памяти. Некоторые элементы данных, например, строки и массивы, требуют задания максимально возможного их размера во время компиляции. Объем памяти, необходимый для хранения этого максимально возможного количества данных, будет зарезервирован даже в том случае, если в этих массивах или строках не хранится никаких данных. Если расположить переменные в динамически распределяемой области памяти во время выполнения программы, то для хранения данных будет выделено столько байтов памяти, сколько потребуется.

Задача 10.Рассчитать сумму элементов вектора а1, состоящего из n элементов. Сформировать вектор а2 из элементов вектора а1, расположенных в обратном порядке и уменьшенных на единицу.

Объявим тип Vector для массива, состоящего из одного элемента. Перемен­ную типа Vector объявлять не будем, а объявим типизированный указатель, базовым типом данных для которого будет Vector. В процессе работы программы определим количество элементов вектора с помощью оператора Readln(n) и выделим память необходимого размера. Выделять память будем при помощи процедуры Getmem, освобождать – при помощи процедуры Release.

Программа

Program Тask10;

{$R-}

Type Vector = аrray [1..1] of integer;

Var a1, a2: ^Vector; p : pointer; n, i, s : integer;

Begin

Write(‘Введите число элементов вектора: ‘); Readln(n);

mark(p); {Запоминаем состояние памяти}

Getmem(a1, n*sizeof(integer)); {Выделяем память под вектор а1}

for i := 1 to n do Readln(a1^[i]); {Вводим элементы вектора а1}

S := 0;

For i := 1 to n do S := S+a1^[i]; {Суммируем элементы вектора}

Writeln(‘S=’,S);

Getmem(a2, n*sizeof(integer)); {Выделяем память под вектор а2}

For i := 1 to n do a2^[n+1-i] := a1^[i] – 1; {Формируем вектор а2}

For i := 1 to n do Writeln(a2^[i]); {Выводим элементы вектора а2}

Release(p); {Возвращаем память в исходное состояние}

End.

Тип Vector объявлен как массив, индексы которого изменяются в диапазоне от 1 до 1. Чтобы не возникло ошибки при выходе за границу массива, необходимо, чтобы директива компилятора, осуществляющая проверку выхода за граничное значение, была отключена {$R–}.

Задача 11.Cчитать 1000 строк из файла и записать их в динамическую память.

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

Программа

Program Task11

Type PString = ^String;

Var

Buf : String;

L : array[1..1000] of PString;

ff : Text;

i: Integer;

Begin

Assign(ff, ‘Dat.txt’);

Reset(ff);

for i := 1 to 1000 do

Begin

Readln(ff, Buf);

GetMem(L[i], Length(Buf) + 1);

L[i]^ := Buf;

End;

End.

Вместо выделения для строк 256К (256 символов на строку 1000 раз) программа выделила 4К (4 байта на указатель 1000 раз).

Случай 3. В программе необходимо использовать массив большой размерности.

Задача 12.Найти среднее значение элементов массива d, состоящего из 200 строк и 200 столбцов.

Под элементы двухмерного массива такого размера потребуется 200х200х6 байтов памяти, что составит более 234К. Переменная d : array [1..200, 1..200] of Real, не может быть объявлена. Нужно реорганизовать массив так, чтобы он распался на части, не превышающие по отдельности 64К.

Программа

Program Task12;

Type

d200 = Array [1 .. 200] of Real;{Объявлен тип строки матрицы}

dPtr = ^d200;{Объявлен тип ссылки на строку}

dPtr200 = array [1..200] of dPtr;{Тип для массива указателей}

Var d : dPtr200; {Объявили массив указателей, каждый элемент которого}

{указывает на одномерный массив d200}

S : Real; i, j : Integer;

Begin

S:=0;

For i := 1 to 200 do

Begin

New(d[i]);

{Выделили память под строку из 200 элементов типа Real,}

{на которую указывает ссылка d[i]}

For j := 1 to 200 do

Begin

d[i]^[j] := random(10);

{Формирование элемента с помощью датчика}

{случайных чисел и подсчет суммы элементов}

S := S + d[i]^[j];

End;

Dispose(d[i]);

End;

S := S/40000; Writeln(‘S= ‘, S:2:2);

End.

Матрица 200 на 200 в программе определяется как статический массив из 200 ссылок на динамические массивы по 200 элементов. Одновременно память выделяется только для одной строки. Выделение памяти для каждой следующей строки происходит после освобождения памяти, занятой предыдущей строкой. Для каждого массива понадобится блок длиной 200х6 байтов. Обращение к элементу массива d (разыменование) имеет вид: d[i]^[j], где i – номер строки, а j – номер столбца.

Случай 4. В программе необходимо применять ссылки на данные, имеющие разную структуру.

Задача 13.Компоненты файла f1 являются объектами типа “игрушка”. Ком­поненты файла f2 являются объектами типа “багаж”. “Игрушка” – это запись, состоящая из следующих полей: наименование игрушки, цена игрушки, возрастные границы. “Багаж” – это запись, состоящая из полей: количество предметов, вес предметов. В текстовом файле f расположена последователь­ность a1b1a2b2... anbn, где каждое ai– это символ “i” или “б”, а каждое bi– натуральное число. Написать программу, в результате выполнения которой для каждого i = 1, 2, ..., n выводится: если аiесть символ “i” – название и стоимость игрушки, информация о которой содержится в bi-й компоненте файла f1; если aiесть символ “б” – количество мест и вес багажа, информация о котором содержится в bi-й компоненте файла f2. Программу составить так, чтобы в каждый момент ее выполнения было выделено место в памяти не более, чем для одного объекта типа “игрушка” или “багаж”.

Программа

Program Task13;

Type Igru = Record {Объявили записной тип “игрушка”}

Name : String[15];

Cost : Integer;

Age1, Age2 : Integer;

End;

Bagaz = Record {Объявили записной тип “багаж”}

Count : Integer;

W : Real;

End;

Var

Ig : ^Igru; Ba : ^Bagaz; {Объявили ссылочные переменные, которые}

{будут ссылаться на переменные типа запись}

f1 : File of Igru; f2 : File of Bagaz; f : Text;

i, k : Integer; a, b:Char; code : Word;

Begin

Assign(f, ’Dat3'); Assign(f1, ’Dat1'); Assign(f2, ’Dat2');

{Связали файловые переменные с физическими файлами на диске}

Reset(f); Reset(f1); Reset(f2); {Открыли файлы на чтение}

While Eof(f) = false do {Организуем цикл}

Begin

Read(f, a, b); {Считали из текстового файла два символа}

Val(b, k, code); {Превратили второй символ в число}

If a = ‘i’ Then

Begin {Блок для работы с объектом типа “игрушка”}

New(Ig);

Seek(f1, k); {Установили указатель файла на компонент k}

Read(f1, Ig^); Writeln;

With Ig^ Do

Begin

Writeln(‘Наименование ‘,Name);

Writeln(‘Цена ‘,Cost);

Writeln(‘Нижняя возрастная граница ‘, Age1);

Writeln(‘Верхняя возрастная граница ‘, Age2);

End;

Dispose(Ig);

End

Else

Begin {Блок для работы с объектом типа “багаж”}

New(Ba);

Seek(f2, k); Read(f2, Ba^);

With Ba^ Do

Begin

Writeln(‘Количество ‘, Count);

Writeln(‘Вес ‘, W:8:2);

End;

Dispose(Ba);

End;

End;

Close(f); Close(f1); Close(f2);

End.

До тех пор, пока не будет достигнут конец файла f, считываются два символа а и b. Символ а указывает на то, с какой структурой придется работать. Символ b содержит номер компоненты типизированного файла. Перемещение на k-ую компоненту файла осуществляется с помощью функции Seek.

Списки

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

Список – это набор записей, каждая из которых имеет поле данных и указатель (ссылку) на следующую запись в списке. Та, в свою очередь, тоже содержит поле данных и ссылку на продолжение списка. Последний элемент списка содержит значение Nil, т.е. уже ни на что не ссылается. Начало списка формирует переменная типа “указатель”, содержащая адрес первого элемента списка (рис. 6). Поле данных еще называют информационной частью списка.

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

Рассмотрим методы работы со списками, информационная часть которых состоит из одного поля типа Integer. Такие списки естественно называть списками целых чисел. Обозначим тип элемента списка идентификатором Elem, а ссылочный тип на элемент списка – идентификатором Uk.

Type

Uk = ^Elem; {Описание типизированного указателя}

Elem = Record{Описание базового типа}

x : Integer;

next : Uk;

End;

Var p, q : Uk;

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

Построим список из трех элементов, содержащих числа 5, 12 и –8. Список обычно задается указателем на свой первый элемент. Назовем этот указатель p. Значением переменной р в процессе построения всегда будет ссылка на первый элемент уже построенной части списка. Переменная q будет использоваться для выделения памяти под размещение новых элементов списка. Выполнение оператора р := Nil приводит к созданию пустого списка. После выполнения операторов

New(q); q^.x := –8; q^.next := p; p := q;

имеем список, состоящий из одного элемента, содержащего число –8 в информационной части. Ссылка на этот элемент является значением переменных р и q.

Выполнение операторов New(q); q^.x := 12; q^. next := p; p := q; приводит к тому, что в начало этого списка добавляется новый элемент, содержащий число 12; значением переменных р и q является ссылка на первый элемент списка.

После выполнения операторов New(q); q^.x := 5; q^.next := p; p := q, добавляющих в начало списка элемент, содержащий число 5, построение списка завершается.

Значением переменных р и q является ссылка на первый элемент списка. Значение Nil поля next элемента, содержащего число –8, является признаком того, что этот элемент – последний в списке.

Если значения –8, 12, 5 вводить с клавиатуры, то программа построения списка будет состоять из следующей последовательности операторов:

Type

Uk = ^Elem;

Elem = Record

x : Integer;

next : Uk;

End;

Var p, q : Uk; i : Integer;

Begin

p := Nil;

For i := 3 downto 1 do

Begin

New(q); {Выделение памяти для элемента списка}

Readln(q^.x); {Ввод численного значения информационной части}

q^.next := p; {Запомнили адрес предыдущего элемента списка}

p:=q; {Запомнили адрес текущего элемента списка}

End;

End.

Заполнение списка начинается с конца списка.

Основными операциями над списками являются:

переход от элемента к следующему элементу;

включение нового элемента в список;

исключение элемента из списка.

Пусть значением переменной q типа ссылка является ссылка на элемент списка целых чисел, описанного выше. Тогда после присваивания q := q^. next ее значением будет или ссылка на следующий элемент этого списка (если такой элемент имеется) или Nil. Пользуясь таким способом перехода от одного элемента к другому, можно просматривать весь список или его часть. Для того, чтобы вывести числа, содержащиеся в элементах списка, нужно выполнить последовательность операторов

q := p;

While q <> Nil do

Begin

Write(q^.x); q := q^.next;

End;

По ходу выполнения цикла While q <> Nil do . . . значением переменной q является поочередно ссылка на первый, второй, третий и т.д. элементы списка и, наконец, Nil.

Пусть имеются переменные p, q, r типа ссылка и значением переменной q является ссылка на некоторый элемент списка целых чисел, а значением p – ccылка на первый элемент этого списка. Требуется включить в данный список после элемента, ссылка на который является значением переменной q, новый элемент, содержащий число 17. Для этого нужно выполнить последователь­ность операторов:

New(r); r^.x := 17; r^.next := q^.next; q^.next := r;

Пусть значением q является ссылка на некоторый (не последний) элемент списка целых чисел и требуется исключить из списка элемент, следующий за тем, ссылка на который является значением переменной q. Для этого нужно выполнить последовательность операторов:

r := q^.next; q^.next := q^.next^.next; r^.next := Nil;

Второе из этих присваиваний – исключение элемента из списка. Первое присваивание выполняется для того, чтобы сохранить ссылку на исключенный элемент. В этом случае элемент останется доступным и с ним можно выполнять нужные операции, например, освободить занимаемую им память с помощью Dispose. Третье присваивание выполняется для того, чтобы сделать исключение окончательным, т.е. чтобы из исключенного элемента по ссылке нельзя было попасть в список, из которого этот элемент исключен.

Процедура, исключающая из списка элемент, ссылка на который r:

Procedure exclude(Var p : Uk; r : Uk);

{р – указатель на первый элемент; r – указатель на исключаемый элемент}

Var q : Uk; {текущий указатель}

Begin

If p = r then p := r^.next

else

Begin

q := p; While q^.next <> r Do q := q^.next;

q^.next := r^.next;

End;

r := Nil;

End;

Для того чтобы включить в начало списка новый элемент, содержащий число 17, нужно выполнить действия:

New(r); r^.x := 17; r^.next := p; p := r;

Для исключения первого элемента из списка нужно выполнить:

r := p; p := p^.next; r^.next := Nil;

То, что включение (или исключение) в зависимости от местоположения элемента в списке выполняется по–разному, доставляет неудобства при программировании. В программах приходится предусматривать дополнитель­ные проверки для того, чтобы выполнить включение или исключение одним из двух способов. Чтобы сделать действия единообразными, применяется следующий прием. В начало каждого списка добавляется заглавный элемент. Он никогда не исключается из списка, и перед ним в список не включаются новые элементы. Информационная часть заглавного элемента или не используется вообще, или используется для специальных целей. Например, в случае целых чисел она может содержать число, равное количеству элементов списка. Добавление заглавного элемента в список приводит к тому, что у всех элементов имеется предшественник, и действия по включению новых элементов в список проводятся одним способом.

Мы рассмотрели линейный однонаправленный список. Двунаправленный список называется очередью (рис. 7). Очередь – линейный список, элементы в который добавляются только в начало, а исключаются только из конца списка (“первым пришел – первым ушел”). Каждый элемент структуры содержит указатель на следующий элемент и еще на предыдущий. Считается, что для этого списка не существует обход элементов. Доступ возможен только к первому и последнему элементам, как в любой очереди в магазине. Очередь определяют два указателя: указатель на первый элемент списка и указатель на последний элемент списка. Начало списка называют хвостом очереди, а конец списка – головой очереди.

Рис. 7. Схематическое изображение очереди

Стек – линейный список, в котором добавления и исключения элемента производятся с одного конца, называемого вершиной стека (рис. 8). Соблюдается принцип “первым пришел – последним ушел”.

Рис. 8. Стек

Считается, что доступ возможен только к верхнему элементу (в списках мы называли его первым). Стек оптимален для случаев, когда требуется просчитать и запомнить большое число структур данных, а потом обработать их в обратном порядке.

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

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

New(q); Readln(q^.x); q^.next := p; p := q;

Считать значение элемента из стека и исключить его из стека:

q := p; p := q^.next; y := q^.x; dispose(q);

Считать элемент, не удаляя его из стека:

y := p^.x;

Списки могут быть не только линейными, но и кольцевыми. В кольцевом списке для последнего элемента следующим является первый, а если список двунаправленный, то для первого предыдущим является последний. Как и линейный, кольцевой список определяется указателем на свой первый элемент. При просмотре линейного списка переход от одного элемента к другому осуществляется до тех пор, пока рабочий указатель не станет равен Nil. При просмотре кольцевого списка надо переходить к следующему элементу до тех пор, пока рабочий указатель не совпадет с указателем на первый элемент. Поэтому первый элемент должен обрабатываться отдельно, а просмотр при помощи цикла следует начинать со второго элемента.

Мультисписки представляют собой структуру, каждый элемент которой входит в более чем один список одновременно и имеет соответствующее числу списков количество полей связи. Часто в виде мультисписков представляют матрицы очень большой размерности, в которых большинство элементов равны 0 (такие матрицы называются разреженными). Мультисписки обеспечивают эффективное хранение таких структур в памяти: хранятся только те элементы, которые отличны от 0. Каждый элемент входит в два списка: в список-строку и список-столбец. Вся матрица представлена m + n списками, где m и n – соответственно число строк и число столбцов матрицы, каждый элемент хранит значение элемента матрицы и две ссылки: на следующий элемент в строке и на следующий элемент в столбце, указатели на начала этих списков хранятся в двух массивах. Описание типа данных одного элемента матрицы-мультисписка аналогично описанию элемента-очереди или узла дерева. Для описания матрицы потребуется два массива – массив указателей на первые элементы списков–строк и на первые элементы списков-столбцов.

Задача 14.Написать программу, обрабатывающую очередь пассажиров, желающих купить авиабилет. Элементы очереди содержат следующую информацию: фамилия пассажира, пункт прибытия, дата вылета. Информация об имеющихся билетах хранится в списке, элементы которого содержат номер рейса, пункт прибытия, дату, число непроданных билетов. Пассажир, обеспеченный билетом, удаляется из очереди. Содержимое списка по мере обеспечения пассажиров билетами корректируется.

Программа

Program Task14;

{Типизированная константа men содержит пункты меню

основной части программы}

Const men:array[1..8] of string[30] =

(‘Сформировать новый список’,’Добавить в список’,

‘Сформировать новую очередь’,’Добавить в очередь’,

‘Купить билет’,’Вывести список’,’Вывести очередь’,’Конец работы’);

Type Uk = ^Elem; Elem = Record {Описание элемента очереди}

Pred : Uk;

Fam : String[10];

Punkt : String[10];

Date : String[5];

next : Uk;

End;

Sp = ^Elem1; Elem1 = Record{Описание элемента списка}

N : integer;

Punkt : String[10];

Date : String[5];

Count : Integer;

next : Sp;

End;

Var o1, o2, o3 : Uk; s1, s2 : Sp;

{o1 – указатель на начало очереди}

{o2 – текущий указатель}

{о3 – указатель на конец очереди}

{s1 – указатель на начало cписка; s2 – текущий указатель}

a, i : integer;

Procedure Spisok;

Var Ch : Char;

Begin

While Ch<>’N’ Do

Begin {Формируется элемент списка}

New(s2); s2^.next := s1; s1 := s2;

Writeln(‘Номер рейса ‘); Readln(s2^.n);

Writeln(‘Пункт прибытия ‘); Readln(s2^.Punkt);

Writeln(‘Дата вылета ‘); Readln(s2^.date);

Writeln(‘Количество билетов ‘); Readln(s2^.count);

Writeln(‘Продолжить?(Y/N)’); Readln(Ch); Ch := Upcase(Ch);

{Переход к новому элементу}

End;

End;

Procedure Ochered;

Var Ch : Char;

Begin

While Ch<>’N’ Do

Begin {Формируется элемент очереди. Запись в начало (в хвост)}

New(o2); o2^.next := o1; {Ссылка на следующий элемент}

o1^.Pred := o2; {Ссылка на предыдущий элемент в следующем элементе}

o1 := o2; {o1 – ссылка на первый элемент}

Writeln(‘Фамилия ‘); Readln(o2^.Fam);

Writeln(‘Пункт прибытия ‘); Readln(o2^.Punkt);

Writeln(‘Дата вылета ‘); Readln(o2^.date);

Writeln(‘Продолжить?(Y/N)’); Readln(Ch); Ch := Upcase(Ch);

{Переход к новому элементу}

End; o2^.pred := Nil;

{В первом элементе (в хвосте очереди) предыдущий отсутствует}

End;

Procedure Pokupka;

Label Met1;

Begin

o2 := o3; {Выбираем последний элемент очереди}

Writeln(‘Фамилия ‘,o2^.Fam);

Writeln(‘Пункт прибытия ‘,o2^.Punkt);

Writeln(‘Дата вылета ‘,o2^.date);

s2 := s1; {Перебираем все элементы списка}

While s2 <> Nil Do

Begin

if (o2^.date = s2^.date) and {Если дата и пункт прибытия совпадают}

(o2^.Punkt = s2^.Punkt) and

(s2^.count <> 0) Then {и билеты имеются в наличии,}

Begin {то соответствующее сообщение и}

Writeln(‘Билет продан. Удаляетесь из очереди!’);

{количество билетов уменьшается на 1}

s2^.count := s2^.count – 1; Goto Met1;

End;

s2 := s2^.next; {Переход к следующему элементу списка}

End;

{Для этого пассажира билета нет}

о3^.next := о1; о1 := о3; o1^.pred := Nil; {Переставляем в хвост очереди}

Met1:o3 := o2^.pred; {Пассажир удаляется из очереди}

o3^.next := Nil; Dispose(o2);

End;

Procedure Vspisok;

{Вывод списка начинается с первого элемента списка}

Begin

s2 := s1;

While s2 <> Nil do

Begin

Writeln(‘Номер рейса ‘,s2^.n);

Writeln(‘Пункт прибытия ‘,s2^.Punkt);

Writeln(‘Дата вылета ‘,s2^.date);

Writeln(‘Количество билетов ‘,s2^.count);

s2 := s2^.next;

End;

End;

Procedure Vochered;

{Вывод очереди с последнего элемента очереди (c головы)}

Begin

o2 := o3;

While o2<>Nil Do

Begin

Writeln(‘Фамилия ‘,o2^.Fam);

Writeln(‘Пункт прибытия ‘,o2^.Punkt);

Writeln(‘Дата вылета ‘,o2^.date);

o2 := o2^.pred;

End;

End;

Begin{Исполняемая часть программы}

Repeat {Цикл выбора пункта меню}

For i := 1 to 8 do Writeln(i:7,’ ‘:5,men[i]); {Вывод меню}

Write(‘Ваше желание ?’); Readln(a); {Ввод номера пункта меню}

Case a of

1 : Begin New(s1); s1 := Nil; Spisok; End; {Формируем новый список}

2 : Spisok; {Добавляем элемент в список}

3 : Begin {Формируем новую очередь}

New(o3); New(o1); o1:=Nil;

New(o2); o3 :=o2; o2^.next := o1; o1 := o2;

{о3 – указатель на последний элемент}

Writeln(‘Фамилия ‘); Readln(o2^.Fam);

Writeln(‘Пункт прибытия ‘); Readln(o2^.Punkt);

Writeln(‘Дата вылета ‘); Readln(o2^.date);

Ochered;

End;

4 : Ochered; {Добавляем элемент в очередь}

5 : Pokupka; {Обеспечим билетом последнего в очереди}

6 : Vspisok; {Выводим содержимое списка}

7 : Vochered; {Выводим содержимое очереди}

End;

Until a = 8; {8 – конец работы}

End.

Деревья

При решении многих задач математики используется понятие графа. Граф – это набор точек на плоскости (эти точки называются вершинами графа), некоторые из которых соединены отрезками (эти отрезки называются ребрами графа). Примером графа служит схема линий метрополитена. Граф называется связным, если любые две его вершины соединены некоторым путем. Состоящий из различных ребер замкнутый путь называется циклом. В графе, изображенном на рис. 9, циклами являются, например, ABCA и BCDB.

Рис. 9. Пример графа

Связанный граф, в котором нет циклов, называется деревом(рис. 10, 11). Рекурсивное определение дерева выглядит следующим образом: дерево либо пусто, либо состоит из элемента, содержащего указатели на непересекаю­щиеся деревья, называемые поддеревьями. Элементы, в которые не входит никаких ветвей, называются корневыми. Элементы, из которых не выходят ветви, называются листьями. То, что для списка принято называть элементом, для дерева часто называют узлом.

Одним из отличительных свойств дерева является то, что в нем любые две вершины соединены единственным путем. Дерево называется ориенти­ро­ванным, если на каждом его ребре указано направление. Двоичное дерево (бинарное)– это такое ориентированное дерево, в котором:

1) имеется только одна вершина, в которую не входит ни одного ребра (эта вершина называется корнем двоичного дерева);

2) в каждую вершину, кроме корня, входит одно ребро;

3) из каждой вершины (включая корень) исходит не более двух ребер.

На рис. 10 приведен пример двоичного дерева. Вершина А – корень этого дерева. Для ребер, выходящих из любой вершины, имеется две возможности – быть направленными влево вниз и вправо вниз.

При решении многих прикладных задач бывает удобно представлять наборы объектов в виде двоичных деревьев. Каждый элемент дерева имеет одного левого и одного правого последователя. Подобное дерево можно было бы описать следующим образом:

Type Uk = ^knot;

knot = Record

date : {необходимый тип данных – информационная часть узла}

Left, Right : Uk

End;

Var Tree : Uk;

Объектами типа knot являются записи, в которых каждое из полей Left или Right есть либо Nil, либо ссылка на конкретное место в памяти, отведенное с помощью New для объекта типа knot. Дерево в программе можно представить в виде множества объектов типа knot, связанных ссылками. Сами эти объекты будут вершинами дерева, а ссылки на места в памяти, отведенные для объектов типа knot, – ребрами дерева. Если при этом поле Left (Right) некоторого объекта типа knot есть Nil, то это значит, что в дереве из данной вершины не исходит ребро, направленное влево вниз (вправо вниз).

На рис. 11 представлено дерево, имеющее тип Integer в информационной части узла.

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

Существует три способа просмотра всех элементов двоичного дерева:

1) прямой просмотр – элемент; левая ветвь; правая ветвь;

2) обратный просмотр – левая ветвь; элемент; правая ветвь;

3) концевой просмотр – левая ветвь; правая ветвь; элемент.

Просмотр следует начинать от корня рекурсивно для каждого узла. При просмотре дерева, изображенного на рис. 10, по первому методу получим последовательность A B D G H E C F I J. По второму методу – G D H E A C I F J.

Задача 15.(Заимствована из [2]). Рассмотрим программу формирования двоичного дерева поиска, представляющего собой частотный словарь. Пусть с клавиатуры вводятся слова (латинскими буквами). Выведем в алфавитном порядке все введенные слова (каждое слово выводится только по одному разу) с числом встречаемости слова во введенной последовательности. Для хранения слов и частоты их встречаемости будем использовать двоичное дерево поиска. Ключом поиска будут сами слова: меньшие по алфавиту будем помещать в левое поддерево, большие – в правое. Для вывода слов в алфавитном порядке понадобится обратный обход дерева.

Формирование нового узла:

New(p); p^.word := w; p^.count := 1; р^.left := nil; p^.right := nil

Программа

Program Task15;

Type Tree_ptr = ^Tree;

Tree = Record {Описание типа дерева}

Wordd : String; {Слово}

Count : Byte; {Частота встречаемости}

Left, Right : Tree_ptr; {указатели на поддеревья}

End;

Var t, p, q : Tree_ptr; W : String; Found : Boolean;

{p, q – рабочие переменные; w – вводимое слово;

found = true, если слово уже есть в дереве}

Procedure Out_tree(t: Tree_ptr); {Процедура вывода дерева}

{t – указатель на корень дерева}

Begin

If t <> Nil Then Begin

Out_tree(t^.Left);

Writeln(t^.Wordd,’-’,t^.count);

Out_tree(t^.Right);

End;

End;

BEGIN {Исполняемая часть программы}

Readln(w);

New(t);{Формирование корня дерева}

With t^ Do Begin Wordd := w; Count := 1; Left := nil; Right := nil; End;

Readln(w);

While w <>’’ Do {Признак окончания ввода – ввод пустой строки}

Begin {поиск элемента в дереве}

found := false; p := t;

While (p<>nil) and (found = false) do

Begin

{Сохранить вершину, к которой будет присоединяться новый элемент}

q := p;

if w<p^.wordd then p := p^.left {Если слово меньше, то левая ветвь}

else if w>p^.wordd then p := p^.right

{Если слово больше, то правая ветвь}

else found := true; {Слово уже есть}

End; {Конец поиска в дереве}

If found then inc(p^.count) {Если слово уже есть, то изменить количество}

Else Begin {Если слова еще нет,}

New(p); {создать новый элемент}

With p^ do Begin

wordd := w; count := 1; Left := Nil; right := Nil;

End;

if w<q^.wordd Then q^.Left := p

{Если меньше, то присоединить слева}

Else q^.Right := p; {Иначе справа}

End;

Readln(w); {Ввод нового слова}

End; {Конец ввода слов}

out_tree(t); {Вывод по алфавиту}

End.

Константы ссылочного типа

Описание константы ссылочного типа может содержать только значение Nil, например:

Const

pr : ^Real = Nil;

Пример задания константы–списка:

type

Direction = (Left, Right, Up, Down);

NodePtr = ^Node;

Node = record

Next: NodePtr;

Value: Direction;

end;

const

N1: Node = (Next: nil; Value: Down);

N2: Node = (Next: @N1; Value: Up);

N3: Node = (Next: @N2; Value: Right);

N2: Node = (Next: @N3; Value: Left);

3. Объектно–ориентированное программирование

В основе того или иного языка программирования лежит некоторая руководящая идея, оказывающая существенное влияние на стиль соответствующих программ. Исторически первой была идея процедурного структурирования, в соответствии с которой программист должен был решить, какие именно процедуры он будет использовать в своей программе, а затем выбрать наилучшие алгоритмы для их реализации. Типичным представителем являлся Фортран. По мере прогресса в области вычислительной математики, акцент в программировании стал смещаться с процедур в сторону организации данных. Паскаль, СИ, Ада имеют более или менее развитые структуры типов данных. Логическим следствием развития этого направления стал модульный подход к разработке программ, характеризующийся стремлением “спрятать” данные и процедуры внутрь модуля.

Начиная с языка Симула 67, в программировании наметился новый подход, который получил название объектно-ориентированного программиро­вания (ООП). Его руководящей идеей является стремление связать данные с обрабатывающими эти данные процедурами в единое целое – объект. Фактически ООП можно рассматривать как модульное программирование нового уровня, когда вместо во многом случайного, механистического объединения в модуле процедур и данных акцент делается на смысловую связь полей и методов объекта.

3.1. Что такое объект?

В терминах Паскаля, объект во многом схож с записью, которая является оболочкой для объединения нескольких связанных элементов под одним именем. Предположим, необходимо разработать программу вывода платежной ведомости, печатающую отчет и показывающую, сколько нужно выплатить каждому служащему института. Запись можно организовать следующим образом:

Type TPerson = record

Name : string[25];

Dolgn : string[25];

Stavka : Real;

end;

Var Person : TPerson;

Здесь TPerson является типом записи, т.е. шаблоном, используемым компилятором для создания переменных типа запись. Переменная Person является экземпляром этого типа.

TPerson представляет два уровня абстракции. Можно рассматривать поля Name, Dolgn и Stavka по отдельности, а когда речь идет о полях, работающих одновременно для описания конкретного работника, можно рассматривать их совокупность как TPerson.

Предположим, что программа должна учитывать выплату денег студентам, преподавателям и сотрудникам института. В каждой категории выплата денег производится особым образом. Например, для определения размера стипендии необходимо знать средний балл студента. Можно построить запись TStudent вида:

TStudent = record

Name : string[25];

Dolgn : string[25];

Stavka : Real;

Ball : Real;

end;

Можно сохранить тип TРerson внутри типа TStudent:

TStudent = record

Student : TPerson;

Ball : Real;

end;

Tип TStudent является дочерним типом для типа TPerson. TStudent наследует все, что принадлежит TPerson, и кроме того имеет кое-что новое, что делает TStudent уникальным.

В Турбо Паскале существует еще один тип данных, который обладает таким свойством. Это объектный тип. Типы данных в этой новой категории определяются с помощью нового зарезервированного слова Оbject.

Type

TPerson = Object

Name : string[25];

Dolgn : string[25];

Stavka : Real;

end;

TStudent = Object (TPerson)

Ball : Real;

end;

Здесь использование скобок означает наследование. TPerson является родительским типом, а TStudent – дочерним типом. Можно определить дочерний тип к типу TStudent и т.д. Большая часть конструирования объектно-ориентированных прикладных программ состоит в построении такой иерархии объектов.

Экземпляры объектных типов описываются в точности так же, как в Паскале описывается любая переменная, либо статическая, либо указатель, ссылающийся на размещенную в динамической памяти переменную:

Type

PStudent = ^TStudent;

Var

Student : TStudent;

DynaStudent : PStudent;

Можно обратиться к полю объекта в точности так же, как к полю обычной записи, либо с помощью оператора With, либо путем уточнения имени с помощью точки. Например:

Student.Stavka := 145;

With Student do

Begin

Name := ‘Степанов Сергей Петрович’;

Ball := 4.87;

End;

Наследуемые поля являются столь же доступными, как если бы они были объявлены внутри типа объекта.

Можно написать специальные процедуры, которые будут изменять содержимое полей. Обычно существует проблема инициализации полей. Для объекта TPerson возможна такая инициализирующая процедура:

Procedure Init (Var Person : TPerson; Nm, Dg : String; Sv : Real);

Begin

With Person Do

Begin Name := Nm; Dolgn := Dg; Stavka := Sv; End;

End;

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

Type

TPerson = Object

Name : string[25];

Dolgn : string[25];

Stavka : Real;

Procedure Init (Nm, Dg : String; Sv : Real);

end;

Сами методы описываются вне определения объекта как отдельная процедура или функция.

Procedure TPerson.Init;

Begin

With Person Do

Begin Name := Nm; Dolgn := Dg; Stavka := Sv; End;

End;

Процесс определения методов объектов напоминает модули Турбо Паскаля. Внутри объекта метод определяется заголовком процедуры или функции подобно интерфейсной части модуля. Описание методов внутри объекта только указывает действия, но не определяет, каким образом они будут выполнены. Сами методы описываются вне определения объекта как отдельная процедура или функция. В заголовках методов указывается имя типа-объекта и после точки – имя метода.

Объект – это такая структура, компонентами которой являются взаимо­свя­занные данные различных типов и использующие эти данные процедуры и функции. Компоненты-данные называются полями объекта, а компоненты-процедуры и функции называются методами.