Организация данных в списковые структуры — это структурная организация информационных данных, которая не имеет фиксированного занимаемого объёма памяти.
Введение
В компьютерах, являющихся IBM PC совместимыми, вся доступная область памяти поделена на сегменты. Программа компиляции может сформировать сегменты памяти для программных кодов, информационных данных и стека, а вся оставшаяся неиспользованная память считается динамической.
Формирование динамических переменных в зоне динамической памяти осуществляется при исполнении программы. Обращаться к этим переменным возможно при помощи указателей. Такие переменные позволяют выполнять обработку данных неизвестного до начала исполнения программы объёма. Выделение памяти для таких данных осуществляется блоками, связанными между собой. Такой метод сохранения данных именуется динамической структурой.
Динамические структуры данных
Объекты данных считаются обладающими динамической структурой, когда размеры объектов могут меняться при исполнении программы или, когда они являются в принципе бесконечными. Данные динамических структур – это информационные данные, обладающие заданным определёнными правилами внутренним построением, число компонентов которых, их взаимное расположение и взаимные связи, могут корректироваться в динамическом режиме при исполнении программы, в соответствии с заданными законами. На рисунке ниже представлена обобщённая классификация данных динамической структуры:
Рисунок 1. Данные динамической структуры. Автор24 — интернет-биржа студенческих работ
К данным, имеющим динамическую структуру, следует отнести файлы, а также несвязанные и связанные динамические данные. Следует отметить, что файлы в приведённой классификации причислены к данным с динамической структурой, поскольку это вытекает из приведённого выше определения.
Динамические переменные в Паскале
Часто при работе в Паскале не могут быть определены заранее величины значений, а иногда и в принципе существование значений какой-нибудь переменной. Поэтому для итогового значения переменной отводится объём памяти, исходя из самого большого вероятного её значения, что ведёт к не оптимальному распределению памяти, если использовать её в статическом варианте. Но эту проблему может решить применение динамической памяти.
Динамическая память - это оперативная память персонального компьютера, выделяемая программе при её исполнении, кроме сегмента данных, объёмом 64Кб, стека, размером 16Кб и самого программного кода. Объём динамической памяти может варьироваться, но по умолчанию под динамическую память отводится весь объём доступной памяти персонального компьютера. Динамическая память является практически единственной возможностью работы с массивами данных значительных размеров. Большинство практических задач очень сложно решить без применения динамической памяти. К примеру, при проектировании системы автоматизированного проектирования (САПР) использование статического распределения памяти просто невозможно, поскольку размеры математических моделей в различных проектах могут сильно разниться между собой.
Задание адресов динамических переменных выполняется использованием указателей. Величины указателей задают адреса объектов. Для использования динамических переменных в программе следует выполнить следующие операции:
- Выделить память для динамической переменной.
- Осуществить инициализацию указателя.
- По завершении работы с динамической переменной следует очистить память.
То есть, программисту следует самому резервировать место в памяти для динамического массива, задавать величины указателей, выполнять очистку памяти.
Для использования динамических программных объектов в Паскале предусматривается ссылочный тип или же тип указателей. Переменная, обладающая ссылочным типом, хранит ссылку на обслуживаемый объект, то есть, фактически адрес объекта.
Указателем является переменная, значением которой является адрес байта памяти. Указатель, который связан с заданным типом данных, называется типизированным указателем. Он описывается следующим образом:
Имя_переменной: ^ базовый_тип;
К примеру:
Type A= array [1..100] of integer;
TA= ^ A ; {тип указатель на массив}
Var
P1: ^ integer; {переменная типа указатель на целое число}
P2: ^ real; {переменная типа указатель на вещественное число}
Если указатель не связан с определённым типом информационных данных, то он считается не типизированным указателем. Чтобы описать не типизированный указатель, в Паскале предусмотрен стандартный тип pointer. Описывается такой указатель следующим образом:
Имя_переменной: pointer;
При помощи не типизированных указателей легко можно выполнить динамическое размещение данных, структура и тип которых могут изменяться при исполнении программы.
Значения указателей являются адресами переменных в памяти. Адрес может занимать четыре байта и сохраняться в формате двух слов, первое их которых задаёт сегмент, а второе задаёт величину смещения.
Организация данных в списковые структуры
Списком принято называть структуру данных, где все элементы связаны с идущим за ним элементом при помощи указателя. То есть, любой компонент связанного списка содержит, собственно, информационные данные, а также содержит указатель на идущий за ним компонент.
Поскольку элементы списка сохраняют составляющие разных типов, то есть, это сохраняемая информация и указатель, то их лучше отображать записью, где одно поле отведено объекту, а второе поле отведено указателю на очередную запись этого же типа. Такой вид записи именуется звеном, а структурная организация, составленная из подобных записей, именуется списком или же цепочкой.
Только на начальный компонент в списке, называемый головой, существует отдельный указатель, а конечный компонент в списке не имеет указателя на следующий элемент. И следует помнить о главном правиле в Паскале, прежде чем использовать какоё-нибудь объект, его необходимо сначала описать.
