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

ЛЕКЦИЯ  20

Связанные структуры данных

Связанные структуры данных. 1

Стек. 2

Реализация стека, основанная на указателях. 3

Пример, демонстрирующий  работу со стеком.. 4

Реализация стека в виде массива. 7

Примеры использования механизма стека. 9

Проверка баланса скобок. 9

Распознавание строк. 9

Вычисление постфиксных выражений (обратная польская нотация) 10

Очередь. 12

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

Примеры использования механизма очереди. 15

Вычисление значения целого числа, представленного в строке символов. 15

Определение последовательностей-палиндромов. 16

Список. 16

Реализация абстрактного списка в виде массива. 17

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

Нелинейные связанные структуры.. 26

Бинарное дерево. 26

В ходе этой лекции вам необходимо усвоить:

·  Понятие и принципы работы со связанными динамическими данными

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

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

В случае динамической структуры важно:

·  каким образом она может расти и сокращаться;

·  каким образом включить в структуру новый и удалить существующий элемент;

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

Структуры, содержащие указатели, позволяют формировать в ОП линейные и нелинейные связанные структуры. К линейным связанным структурам относятся, например, стеки, очереди, списки. К нелинейным – деревья и графы.

Рассмотрим линейные связанные структуры. Они имеют много общего:

·  все элементы связанных структур представляют собой последовательность элементов, связанных между собой с помощью указателей;

·  количество элементов структур ограничивается объемом ОП;

·  ОП для элементов структур выделяется и освобождается динамически (new,  delete).

·  последовательность элементов имеет начало цепи (его указатель имеет значение NULL) и конец (вершину), которую обычно адресует указатель стека, очереди или списка.

Схематично связь элементов линейных структур представлена на рисунке:

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

·  Стек – линейный список, в котором включение и исключение элементов (и всякий доступ к ним) проводится только с одного его конца – с его вершины.

·  Очередь – линейный список, в котором включение элементов производится только с одного конца списка - в его конце, а исключение элементов проводится с другого конца списка – только из его начала.

·  Дек – линейный список, в котором все включения и исключения (и обычно всякий доступ) делаются на обоих концах.

·  В списке элементы обычно упорядочены по определённому признаку – одному из элементов записи, их которых формируется список; включение и исключение элементов производится в любом месте цепи, т.к. поиск требуемого места в списке производится, как правило, по признаку, по которому список упорядочен.

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

Стек

Стек - это способ организации накопления и извлечения данных, при которой элемент, поступивший в стек последним, извлекается первым. Этот способ используется, например, при отработке последовательности активизированных подпрограмм и вложенных циклов. Другие названия этого способа организации и обслуживания данных: магазинная память (оружейный термин); LIFO – Last In – First Out  (последним вошёл – первым вышел). Стек может быть реализован как массив элементов или в виде