Файл: Динамические структуры данных (списки).pdf

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

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

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

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

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

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

ГЛАВА 1. ПОНЯТИЕ И ОСОБЕННОСТИ ДИНАМИЧЕСКИХ СТРУКТУР ДАННЫХ

1.1 Определение «динамическая структура данных» и ее
характеристики

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

В C ++ есть инструменты для создания динамических структур данных, которые позволяют формировать объекты во время выполнения программы, выделять память для них и освобождать память, когда она больше не нужна.Таким образом, можно сформулировать следующее определение динамических структур данных:

Динамические структуры данных - это структуры данных, для которых выделяется и освобождается память по мере необходимости.

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

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

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

Динамическая данных характеризуется что:

она имеет имени;
выделяется память процессе выполнения ;
количество элементов может не ;
размерность структуры меняться в выполнения программы;
процессе выполнения может меняться взаимосвязи между структуры.

Каждая динамическая структура данных связана со статической переменной типа указателя (ее значение является адресом этого объекта), через которую осуществляется доступ к динамической структуре.

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

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

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

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

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

Достоинства связного представления данных – в возможности обеспечения значительной изменчивости структур:

• размер структуры ограничивается только доступным объемом машинной памяти;

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

• большая гибкость структуры.

Вместе с тем, связное представление не лишено и недостатков, основными из которых являются следующие:

• на поля, содержащие указатели для связывания элементов друг с другом, расходуется дополнительная память;

• доступ к элементам связной структуры может быть менее эффективным по времени.

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

Процедура работы с динамическими структурами данных выглядит следующим образом:

• создать (выделить место в динамической памяти);

• работать с указателем;

• удалить (свободное место, занимаемое структурой).

Классификация динамических структур данных

Многие задачи требуют использования данных, в которых конфигурация, размер и состав могут меняться во время выполнения программы. Для их представления используются динамические информационные структуры. Эти структуры включают в себя:

• однонаправленные (односвязные) списки;

• двунаправленные (двусвязные) списки;

• циклические списки;

• стек;

• очередь;

• бинарные деревья.

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

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

1.2 Объявление динамических структур данных

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

где поле Р – ; поле – данные.

Элемент динамической структуры состоит из двух полей:

1) информационное поле (поля данных), которое содержит данные, для которых создается структура; в общем случае само информационное поле представляет собой интегрированную структуру - вектор, массив, другую динамическую структуру и т. д .;

2) адресное поле (поле связок), содержащее один или несколько указателей, связывающих этот элемент с другими элементами структуры;

Объявление элемента динамической структуры данных выглядит следующим образом:

_типа

{

информационное ;

адресное поле;

};

Например:

{

; //информационное поле

*; //адресное

};

Информационных и адресных может быть одно, так несколько.

Рассмотрим в примера динамическую , схематично указанную рис. 1:

Рисунок – Схематичное представление динамической

Эта структура состоит из 4 элементов. Его первый элемент имеет поле d, равное 73, и связан со своим собственным полем p со вторым элементом, поле d которого равно 28, и так далее до последнего, четвертого элемента, поле d которого равно 85, и поле p равно NULL, то есть нулевому адресу, который является признаком завершения структуры. Здесь Ph - указатель, который указывает на первый элемент структуры.

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

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

Указатель содержит адрес определенного объекта в динамической памяти. Адрес формируется из двух слов: адрес сегмента и смещение. Сам указатель является статическим объектом и находится в сегменте данных (рис. 2).

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

Рисунок - Связь указателя с объектом

Доступ к в динамических осуществляется с операции "стрелка" (->), называют операцией выбора элемента объекта, адресуемого . Она обеспечивает доступ элементу структуры адресующий ее того же типа. Формат применения операции следующий:

УказательНаСтруктуру-> ИмяЭлемента

Операции "" (->) двуместная. Применяется для к элементу, правым операндом, структуры, которую левый операнд. В левого операнда быть указатель структуру, а качестве правого – элемента этой .

Например:

->;

Имея возможность манипулирования с , которые могут как вне , так и "" отдельных ее , можно создавать памяти различные .

Однако необходимо помнить, работа с данными замедляет программы, поскольку к величине в два : сначала ищется , затем по – величина.

1.4 Работа с памятью при использовании динамических структур

В программах, в которых необходимо использовать динамические структуры данных, работа с памятью происходит стандартным способом. Динамическое выделение памяти выполняется с помощью новой операции или с использованием библиотечной функции malloc (calloc). Освобождение динамической памяти осуществляется с помощью операции удаления или функции free.