Главная | Обратная связь

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

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

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

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

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

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

Стек.

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

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

По определению, элементы извлекаются из стека в порядке, обратном их добавлению в эту структуру, то есть действует принцип LIFO (Last In First Out) или "последний пришёл первый ушёл".

Наиболее наглядным примером организации стека служит детская пирамидка, где добавление и снятие колец осуществляется как раз согласно определению стека.

ВАЖНО!!! Для хранения стека в памяти отводится сплошная область, граничные адреса которой являются параметрами физической структуры стека. Если в процессе заполнения стека указатель, перемещаясь "вверх", выходит за границу первоначально отведенной области, то происходит переполнение стека (stack overflow). Переполнение стека рассматривается как исключительная ситуация, требующая выполнения действий по ее ликвидации.