В ПОМОЩЬ СТУДЕНТУ И ШКОЛЬНИКУ

Горбачев Л.И. Основы программирования в среде Turbo Pascal.

[НАЗАД]  [СОДЕРЖАНИЕ]

УКАЗАТЕЛИ И ДИНАМИЧЕСКИЕ СТРУКТУРЫ ДАННЫХ.

5. Динамические структуры данных.

   Указатели являются эффективным средством построения динамических структур данных в виде различных списков.

   Списком называется структура данных, каждый элемент которой содержит ссылку, связывающую его со следующим элементом.

   5.1. Динамические переменные и структуры связанных данных.

   Управление памятью, занятой ссылочной переменной P^, должно осуществляться new(P) и dispose(P) динамически. Назовем управляемую таким образом область памяти динамической памятью или "кучей". В начале программы следует установить указатель динамической области на ее начало, которое при каждом new(P) сдвигается соответственно потребности в памяти для P^. Для dispose(P) соответствующее место в памяти объявляется свободным, так что динамическая область может иметь "пропуски", которые заполняются при следующих вызовах процедуры new(P).

   С помощью следующей программы можно проверить, сколько памяти можно отвести в Вашем компьютере под динамическую память.
[program HeapTest]

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

   Каждый элемент связанного списка является записью, состоящей из двух частей: данные и указатель на следующий элемент списка. Конец списка помечается указателем nil. Начало списка формирует переменная типа "указатель", содержащая первый элемент списка. С точки зрения техники программирования, список характеризуется только переменной типа "указатель", заголовком списка, являющейся указателем на первый элемент списка.

   Следующая программа демонстрирует создание и печать одного такого списка.
[program ListPrint]

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

   5.2. Стек.

   Стек - это список с одной точкой доступа к его элементам. Механизм работы стека таков:

а)	б)	в)	г)	д)	е)
A	A	B A	C B A	B A	A

   Здесь
а) - исходное состояние стека,
б) - состояние после добавления одного элемента A,
в) - состояние после добавления двух элементов: A и B,
г) - состояние после добавления трех элементов: A, B и C и т. д.

   Элемент стека описывается следующим образом:
type Stack = ^S;
S = record
I: integer;
P: Stack;
end;
var T: Stack;

   Здесь Stack - имя типа, которое определяет переменную-указатель. Этот указатель будет содержать значение адресов оперативной памяти, по которым будут размещаться переменные типа record (S). Элемент стека содержит два поля. Первое поле (I) составляет информационную часть записи, второе поле (P) - указатель на другую переменную типа S.

   Формирование стека реализуется следующей процедурой:
T := Nil;
.........
procedure PomVStack(K: integer);
{ Тип Stack должен быть описан в основной программе }
var W: Stack;
begin
New(W); {Резервируется память под новую компоненту стека}
with W do
begin
I := K;{Занесение нового элемента в стек}
P := T;{Формирование ссылки на предыдущий элемент стека}
end;
T := W;
end;

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

   Далее T := W, т.е. при следующем обращении к процедуре PomVStack новая компонента стека будет содержать ссылку на первый элемент стека и т.д.

   Извлечение элементов из стека может быть осуществлено с помощью следующей процедуры:
procedure IzIzStack(var U: integer);
var L: Stack;
begin
{Адрес последнего компонента стека}
L := T;
{Извлечение элемента из стека}
U := L^.I;
{Установление нового адреса последнего элемента стека}
T := L^.P;
{Удаление элемента стека}
Dispose(L);
end;

Пример: Программа, иллюстрирующая работу стека.
[program FormStack]

   5.3. Алгоритм составления связанных списков.

   Алгоритм составления связанных списков разберем на примере программы, иллюстрирующей работу стека.
[program FormSteck]

   Структурами связанных данных являются упорядоченные двоичные деревья. Дерево состоит из узлов и ветвей, за которыми вновь следуют узлы. Узлы, в которые не входит никаких ветвей, называются корневыми. Узлы, из которых не выходит ветвей, называют листьями. Тем самым можно строить иерархические отношения. Каждый узел вновь состоит из части, содержащей данные, и указателя, показывающего на следующий узел (т.е. на ветви).

   Если каждый узел имеет самое большее по две ветви, говорят о бинарном или двоичном дереве. Тогда каждый узел имеет одного левого и одного правого последователя. Подобное дерево можно было бы описать, например, таким образом:
type zeiger = ^knoten;
datentyp = { какой-то тип данных };
knoten = record
daten : datentyp; links, rechts : zeiger;
end;
var baum : zeiger;

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

   5.4. Упорядоченное двоичное дерево.

   Существует три способа просмотра всех узлов двоичного дерева. Следует начинать от корня рекурсивно для каждого узла.

Прямой просмотр:
preorder: узел, левая ветвь, правая ветвь;

Обратный просмотр:
inorder: левая ветвь, узел, правая ветвь;

Концевой просмотр:
postorder: левая ветвь, правая ветвь, узел;

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

   В следующем примере строится и выводится на печать упорядоченное бинарное дерево. Функция Einfuegen() добавляет такой узел в дерево. Добавление управляется через ключи: если текущее значение меньше значения ключа рассматриваемого в настоящий момент узла дерева, новый узел будет относится к левому поддереву, в противном случае - к правому. В конце выполнения процедуры Einfuegen() новый узел добавляется в дерево в качестве листа.
[program BinBaum]

   5.5. Очередь.

   Здесь
а) - исходное состояние очереди,
б) - состояние после добавления элемента A,
в) - состояние после добавления элемента B,
г) - состояние после добавления элемента C,
д) -состояние после удаления элемента A,
е) - состояние после удаления элемента B.

   Элемент очереди описывается так же, как и элемент стека (здесь однонаправленная очередь):
type Stack = ^S;
S = record
I: integer;
P: Stack;
end;
var T, Ku, Lw, Rw: Stack;
K: integer;

   Формирование очереди осуществляется с помощью следующей процедуры:
procedure ForOtch;
label M;
begin
{ Чтение первого элемента }
Read(K);
{ Пусть значение -32000 будет признаком окончания процесса формирования очереди. Резервируется память под первый элемент очереди }
New(Ku);
{ Первый элемент не имеет ссылки }
Ku^.P := Nil;
{ Занесение в очередь первого элемента }
Ku^.I := K;
Rw := Ku; Lw := Ku;
while True do
begin
Read(K); {Значения очередного элемента}
if K = -32000 then goto M;
New(Ku);
Lw^.P := Ku; Ku^.P := Nil; Ku^.I := K; Lw := Ku;
end;
M: WriteLn('Формирование очереди закончено');
end;

   В данной процедуре Rw - указатель начала очереди, Lw - указатель конца очереди.

   Удаление из очереди производится с помощью следующей процедуры:
procedure UdOtch;
begin
T := Lw;
Lw := Lw^.P;
Dispose(T);
end;

   Применение указателей позволяет достаточно рационально использовать оперативную память ЭВМ.

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

   Пусть требуется разработать программу транспонирования квадратной матрицы размера NxN. Эта программа использует динамический массив и выглядит следующим образом:
(* Программа, иллюстрирующая пример транспонирования матрицы с использованием динамических переменных. *)
[program Matrix]

THE END
(в скором времени будет добавлено объектно-ориентированное программирование)

[НАЗАД]  [СОДЕРЖАНИЕ]

Главная

Новости

TurboPascal

Учебное пособие

Лекции

Исходники

Математика

Книги

Лекции

Шпоры

ЦТ и ЕГЭ

Физика

Книги

Шпоры

ЦТ и ЕГЭ

Литература

Сочинения

Краткие содержания

Другое

Мой родной край

Фотогалерея

Форум

Ссылки

Гостевая

                                        © Copyright(c) 2004 Amro Group. All rights reserved