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

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

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

Пример 10 1. Дано 10000 вещественных чисел а,, а₂,..., а₁₀₀₀₀ и 8000 целых чисел b₁, b₂ ,b₈₀₀₀. Вывести числа а₁, а₂,..., а₁₀₀₀₀ в обратном порядке. Вывести то число b_k, номер которого к равен минимальному из чисел b₁, b₂ b₈₀₀₀.

Program Task9;

Type

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

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

pr = ^ra;

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

Var

к 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]);

к:= g ^ [1];

For i:= 2 to 8000 do

Begin

Read(g^ [i]);

If g^ [i] < к Then

к:= g ^ [i]

End;

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

End.

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

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

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

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

Program Taski;

{$R-}

Type

Vector = array [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]); {Вводим элементы вектора a1}

S:= 0;

For i:= 1 to n do

S:= S+aT[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-}.

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

Program Taski1;

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. В программе необходимо использовать массив большой размерности.

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

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

Program Task12;

Type

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

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

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

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 элементов. Одновременно память выделяется только для одной строки. Выделение памяти для каждой следующей строки происходит после освобождения памяти, занятой предыдущей строкой. Для каждого массива понадобится блок длиной 200x6 байтов. Обращение к элементу массива d (разыменование) имеет вид: d[i] ^ [j], где i - номер строки, a j - номер столбца.

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

Пример 10.5 Компоненты файла f1 являются объектами типа "игрушка". Компоненты файла f2 являются объектами типа "багаж". "Игрушка" - это запись, состоящая из следующих полей: наименование игрушки, цена игрушки, возрастные границы. "Багаж" - это запись, состоящая из полей: количество предметов, вес предметов. В текстовом файле f расположена последователь­ность a,b,a₂b₂... a_nb_n, где каждое а, - это символ "i" или "б", а каждое b_i - натуральное число. Написать программу, в результате выполнения которой для каждого i = 1, 2,..., n выводится: если а, есть символ "i" - название и стоимость игрушки, информация о которой содержится в b_i,-й компоненте файла f1; если а_i есть символ "б" - количество мест и вес багажа, информация о котором содержится в b_i:-й компоненте файла f2. Программу составить так, чтобы в каждый момент ее выполнения было выделено место в памяти не более, чем для одного объекта типа "игрушка" или "багаж".

Program Task13;

Type

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

Name: String[15];

Cost: Integer;

Age1, Age2: Integer;

End;

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

Count: Integer;

W: Real;

End;

Var

Ig: ^ lgru;

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(lg);

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

Read(f1, Ig^);

Writeln;

With Ig^ Do

Begin

Writeln('HanMeHOBaHne '.Name);

Writeln('Цена'.Cost);

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

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

End;

Dispose(lg);

End

Else

Begin

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

New(Ba);

Seek(f2, k);

Read(f2, Ва^Л);

With Ва^Л Do

Begin

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

Writeln('Bec ', W:8:2);

End;

Dispose(Ba);

End;

End;

Close(f);

Close(f1);

Close(f2);

End.

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

Списки

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

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

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

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

Рисунок 10.4 Линейный однонаправленный список

Type

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

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

х: Integer;

next: Uk;

End;

Var

p, q: Uk;

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

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

New(q);

q ^. x:= -8;

q ^. next:= р;

р:= q;

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

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

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

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

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

Туре

Uk = ^ Elem;

Elem = Record

х; 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:= р;

While q <> Nil do

Begin

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

End;

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

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

New(r); r ^. х:= 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 = г then p:= г".next

else

Begin

q:= p; While q ^. next О г Do q:= q ^. next;

q ^. next:= r ^. next;

End;

r:= Nil;

End;

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

New(r); r ^. х:= 17; r ^,next:= р; р:= r;

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

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

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

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

Рисунок 10.5 - Схематическое изображение очереди

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

Рисунок 10.6 - Стек

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

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

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

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

q:= р; р:= q ^. next; у:= q ^. x; dispose(q);

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

y:= Р ^. х;

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

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

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

Program Task1;

{Типизированная константа 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 = ^Elemi;

Elemi = Record{Описание элемента списка}

N: integer;

Punkt: String[10];

Date: String[5];

Count: Integer;

next: Sp;

End;

Var

o1, o2, o3; Uk;

s1, s2: Sp;

{o1 - указатель на начало очереди, о2 - текущий указатель, оЗ - указатель на конец очереди, s1 - указатель на начало списка; 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 те1п('Продолжить?(У/М)');

Readln(Ch);

Ch:= Up'case(Ch); {Переход к новому элементу}

End;

End;

Procedure Ochered;

Var Ch: Char;

Begin

While Ch<>'N' Do

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

New(o2);

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

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

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

Writeln('Фaмилия ');

Readln(o2^.Fam);

Writeln('Пункт прибытия ');

Readln(o2^.Punkt);

Writeln('Дата вылета ');

Readln(o2^.date);

Writeln('Пpoдoлжить?(Y/N)');

Readln(Ch);

Ch:= Upcase(Ch); {Переход к новому элементу}

End;

o2^.pred:= Nil; {В первом элементе (в хвосте очереди) предыдущий отсутствует}

End;

Procedure Pokupka;

Label Met1;

Begin

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

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;

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

o3^.next:= о1; о1:= оЗ; 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;

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

Begin

о2:= оЗ;

While 02<>Nil Do

Begin

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

Writeln('Пункт прибытия ',о2^. Punkt);

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

о2:= о2.pred;

End;

End;

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

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

For i:= 1 to 8 do

Writeln(i:7,' ':5,men[i]); {Вывод меню}

Write('Bauje желание?');

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); оЗ:=o2; o2^.next:= o1; o1:= o2;

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

Writeln('Фaмилия ');

Readln(o2^.Fam);

Writeln('Пункт прибытия ');

Readln(o2^.Punkt);

Writeln('flaTa вылета ');

Readln(o2^.date);

Ochered;

End;

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

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

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

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

End;

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

End.

Деревья

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

Рисунок 10.5 Пример графа

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

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

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

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

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

Рисунок 10.6 - пример двоичного дерева.

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

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

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, то это значит, что в дереве из данной вершины не исходит ребро, направленное влево вниз (вправо вниз).

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

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

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

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

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

3)концевой просмотр - левая ветвь; правая ветвь; элемент.
Просмотр следует начинать от корня рекурсивно для каждого узла. При просмотре дерева, изображенного на рис. 10.6, по первому методу получим последовательность ABDGHECFIJ. По второму методу -GDHEACIFJ.

Рисунок 10.7 - Упорядоченное двоичное дерево

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

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

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

Program Task15;

Type

Tree_ptr = ^Tree;

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

Wordd: String; {Слово}

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

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

End;

Var

t, p, q: Treeptr;

W: String;

Found: Boolean;

{p, q - рабочие переменные; w - вводимое слово; found = true, если слово уже есть в дереве}

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

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

Begin

If t <> Nil Then

Begin

Out_tree(t^.Left);

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

Out_tree(t^.Right);

End;

End;

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

Readin(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 (ponil) and (found = false) do

Begin

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

q:= р;

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

else if w>p^.wordd then p:= p^.right {Если слово больше, то правая ветвь}

Else

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

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

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

Else

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

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

With р^ 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);