Простейшие динамические структуры

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

1) Дисциплина LIFO (Last In, First Out), при которой последний поступивший элемент извлекается первым.

2) Дисциплина FIFO (First In, First Out), при которой первый поступивший элемент извлекается первым.

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

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

Применяются также другие динамические структуры – деревья и сети.

Здесь рассмотрена работа с простейшими структурами. Переменные в таких структурах содержат одно поле-указатель на записи такого же типа. Будем считать, что они строятся из динамических переменных, содержащих одно информационное поле типа Integer с именем I, а имя поля-указателя – R.

Очередь LIFO (другое название – Стек)

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

Добавление в стек.

1) Создаем новую динамическую переменную, связанную со вспомогательным указателем.

New(Q);

Заносим данные в информационное поле.

Q^.I:=30;

2) Привязываем к новой переменной существующую цепочку.

Q^.R:=P;

3) Изменяем значение указателя верхушки стека так, чтобы он указывал на новую верхушку.

P:=Q;

Извлечение из стека.

1) Связываем со вспомогательным указателем. Извлекаем данные из информационного поля, например, в переменную IntVar.

Q:=P;IntVar:=Q^.I;

2) Изменяем значение указателя P так, чтобы он указывал на следующую переменную в цепочке.

P:=Q^.R;

3) Уничтожаем извлеченную из стека переменную.

Dispose(Q);

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

Очередь FIFO (также называется просто очередью. Если не упоминается дисциплина очереди, обычно имеется в виду очередь FIFO).

Для работы с очередью нужно три указателя. Один указывает на начало очереди (место, из которого элементы извлекаются для обработки или обслуживания), другой – на ее конец (хвост), очереди (место, через которое в очередь поступают новые элементы), третий – вспомогательный. Примем имя указателя начала очереди H, конца очереди t и вспомогательного указателя Q. Будем считать, что очередь строится из записей, состоящих из информационного поля с именем I и поля-указателя с именем P. Будем считать, что изначально очередь содержит два элемента. Значение Nil в поле-указателе элемента, связанного с указателем.

Добавление в очередь.

1) Создаем новую динамическую переменную, связанную со вспомогательным указателем.

New(Q);

Заносим данные в информационное поле, а в поле-указатель – значение Nil.

Q^.I:=30;

Q^.P:=Nil;

2) Привязываем новую переменную к существующей очереди.

T^.P:=Q;

3) Переустанавливаем указатель хвоста очереди на новую динамическую переменную.

T:=Q;

Извлечение из очереди.

1) Связываем со вспомогательным указателем извлекаемую динамическую переменную, связанную с указателем начала очереди. Извлекаем данные из информационного поля, например, в переменную IntVar.

Q:=H;

InvVar:=Q^.I;

2) Переустанавливаем указатель начала очереди на следующую динамическую переменную в очереди.

H:=Q^.P;

3) Уничтожаем освободившуюся динамическую переменную.

Dispose(Q);

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

If H=Nil then H:=Q;

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

Дата добавления: 2014-01-11