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

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

1. Очередь организована по принципу FIFO (First Input First Output – первым вошел и первым вышел). Схематически можно представлять это в виде трубочки с одним входом и с одним выходом:

2. Стек организован по принципу LIFO (Last Input First Output - последним вошел, первым вышел). Схематически это можно изобразить в виде трубочки с запаянным концом.

3. Список является обобщением очереди и стека. В списке возможен доступ к любому элементу, он допускает вставку любого элемента в любое место. А также исключение элемента из любого места списка.

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

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

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

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

1. отсутствует описание динамических элементов;

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

Связанные динамические списки

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

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

• информационная часть;

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

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

Type p_stud=^Student;

{^Student – тип указателя, который обеспечивает связь между элементами списка}

Student = record {запись Student описывает тип элемента списка}

Fam: string[20];

Name: string[15]; { информационная часть элемента}

Grup: integer;

Adress: string[60];

Next: p_stud; {указатель на следующий элемент списка }

End;

Var head: p_stud; {указатель на первый элемент списка }

Тип Student необходим для описания типа указателя p_stud. Указатель невозможно описать без раздела type, в то же время тип p_stud нужен для описания поля Next в записи Student. Таким образом, идентификатор Student используется до его описания, этим нарушается одно из требований языка Pascal, Это исключение сделано только для описания указателей, чтобы сделать возможным создание связанных структур.

Добавлять данные можно в начало, в конец, в нужное место списка.

Во всех этих случаях необходимо корректировать указатели.

Изобразим схематически процесс добавления элементов в начало односвязанного списка.

1. Список пустой, указатель head ни на что не указывает (nil).

head

• т

2. После добавления первого элемента head указывает на этот элемент.

head

3.После добавления второго элемента в начало списка head указывает на этот новый элемент (curr – указатель на текущий элемент).

Head

Рассмотрим пример программы, которая формирует список студентов, добавляя фамилии в начало этого списка. Данные для списка вводятся с клавиатуры. Если вместо ввода очередной фамилии нажата сразу Enter (это равносильно вводу пустой строки, длина которой равна 0), тогда программа начнет распечатывать введенный нами список.