Динамическая структура данных— это структура данных, занимаемый объем памяти которой не фиксированный.
Введение
В электронных вычислительных машинах весь объём памяти делится на отдельные сегменты. При выполнении компиляции программы, подлежащей исполнению, формируются кодовые сегменты, сегменты информационных данных и стековые сегменты, а весь оставшийся доступный программе объём памяти считается динамической памятью. Программные переменные формируются в динамической памяти при исполнении программы. Обратиться к переменным программа может посредством указателей. При помощи таких переменных выполняется обработка информационных данных, объём которых перед началом исполнения программы не определён. Для этих данных выполняется блочное выделение памяти, причём существует связь между этими блоками. Такой метод организации хранения информации определяется как динамическая структура.
Динамические структуры данных
Информационные данные обладают динамической структурой, если объём отведённой под них памяти может меняться при выполнении программы или он теоретически может считаться бесконечным. Данными динамической структуры являются данные, у которых внутреннее построение реализуется по определённому правилу, но число компонентов, их взаимное расположение и взаимные связи способны оперативно меняться при исполнении программы в соответствии с заданными правилами реализации. Общая классификация информационных данных с динамической структурой представлена на рисунке ниже:
Рисунок 1. Общая классификация информационных данных с динамической структурой. Автор24 — интернет-биржа студенческих работ
К типу данных с динамической структурой относятся файлы, которые делятся на несвязанные и связанные динамические данные. Следует отметить, что файлы в приведённой выше классификации причислены к данным с динамической структурой. Это соответствует приведённому выше определению. Хотя нельзя удалить компонент или вставить его в середину файла, но размер файла при исполнении программы способен меняться, то есть возрастать или сокращаться до нуля. Это и есть динамическое свойство файла, который является структурированными данными.
Динамические переменные в Паскале
В языке программирования Паскаль в качестве одной из задач выступает фиксация на время исполнения программы размера значений, а это означает и фиксацию размера выделяемого для них участка памяти. Если переменная описана таким способом, то она является статической переменной. Но иногда в исходных данных нет размера значений переменной, а часто и наличие в принципе значения той или другой переменной не определено. В этом случае для итоговой величины переменной следует выделять память из расчёта на её максимальную величину, что означает нерациональное распределение резервов памяти. При работе с большими массивами данных это может вылиться в большую проблему. Решить эту проблему может применение памяти с динамической структурой.
Динамической памятью является оперативная память персонального компьютера, которая предоставляется программе при её исполнении, без учёта сегмента информационных данных, стековой памяти и непосредственно самой программы. Объём динамической памяти может изменяться, но по умолчанию динамической памятью считается весь доступный объём памяти персонального компьютера. Динамическая память является, по сути, единственной возможностью, позволяющей обрабатывать массивы данных большого объёма. Большинство практических задач нереально решить без применения динамической памяти.
Обращение к динамическим переменным, то есть их адресация, выполняется посредством указателей, значения которых задают адрес объекта. Для использования динамических переменных, программа должна включать в свой состав следующие операции:
- Выделить память для динамической переменной.
- Выполнить инициализацию указателя.
- Очистить выделенный участок памяти после завершения работы динамической переменной.
То есть специалист, проектирующий программу, обязан самостоятельно выполнить в программе эти процедуры.
Указателем является переменная, содержащая в качестве своей величины адрес памяти. Указатели, которые связаны с заданным типом данных, считаются типизированными указателями.
Указатель, который не связан с определённым типом данных, считается не типизированным указателем. Чтобы описать такой указатель в Паскале есть стандартный тип pointer. Не типизированный указатель описывается следующим образом:
Имя-переменной: pointer;
При помощи не типизированных указателей можно выполнять динамическое размещение данных, у которых тип и структура могут изменяться при выполнении программы. Значения указателей являются адресами переменных в памяти. Под адрес отводится четыре байта, и он хранится в формате пары слов, первое из которых задаёт сегмент, а второе определяет смещение в нём.
С указателями можно выполнять лишь операции присваивания и операции проверок на равно или не равно. В языке программирования Паскаль запрещены все арифметические действия с указателями.
Списковые структуры данных
Список — это структура данных, где все элементы связаны через указатели со следующими элементами.
Все компоненты связанного списка сохраняют определенные данные и указывают на очередной компонент. Поскольку компоненты списка могут хранить части разных типов, а именно это собственно информация и указатель, то его можно отобразить записью, где одно поле содержит объект, а другое поле содержит указатель на очередную запись того же самого типа. Этот тип записи является звеном, а структурная организация, состоящая из данных записей, определяется как список или цепочка. Только на начальный компонент списка (его головную часть) задаётся отдельный указатель. А конечный компонент списка вообще не имеет указателя, то есть он не указывает никуда.
В языке Паскаль есть главное правило, перед применением любого объекта, его необходимо сначала описать. То есть, чтобы со списком можно было работать, необходимо выполнить определение указателя на его начальный элемент.
