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

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

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

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

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

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

struct Node{

Data d; // тип данных Data должен быть определен ранее

Node *р:

}:

2. Динамические структуры данных. Линейные списки: Очередь, стек.

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

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

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

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

Очередь проще всего представить себе, постояв в ней час-другой. В программировании очереди применяются, например, при моделировании, диспетчеризации задач операционной системой, буферизованном вводе/выводе.