Типы рекурсивных данных. Динамические структуры.

Основные структуры данных – это массивы, записи и множества. Из них можно составлять более сложные структуры.

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

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

Работа со ссылками (или иначе указателями) позволяет строить потенциально бесконечные или циклические структуры.

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

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

Если все элементы списка являются простыми, то список называется линейным.

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

Для представления списка в памяти ЭВМ используются 2 способа: последовательное представление и связанное – (ссылочное) представление.

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

При ссылочном представлении каждый элемент списка помимо содержательной информации имеет ссылки на следующий элемент.