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

    На этом шаге мы рассмотрим общий вид динамических структур данных.

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

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

    Для реализации некоторой динамической структуры на языке программирования Pascal необходимо:

    Заметим, что описание динамических структур с помощью массивов, записей и файлов приводит к неэкономному использованию памяти и увеличивает время решения задачи.

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


Рис.1. Представление компоненты динамической структуры

    Описание этой компоненты дадим следующим образом:

 Type
    PtrRec = ^Rec;
    Rec = Record
        Element : TypeElement;
        pNext : PtrRec;
      End;

    Здесь TypeElement - тип данных, например, Integer, Char и другие.

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

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




Содержание Следующий шаг