Лекции Булатицкий Дмитрий Иванович (во многом по материалам Прасолова А. Н.)

• Название: Лекции Булатицкий Дмитрий Иванович (во многом по материалам Прасолова А. Н.)
• Дата: 11.01.2022
• Размер: 319.62 Kb.
• Имя файла: Lecture_Programming_2021_09_01.docx
• Тип: Лекции; #328427
• страница: 35 из 36

Динамические СТРУКТУРЫ данных (ДСД)

1. Понятие ДСД

   1. Проблемы статических структур

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

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

Примеры:

1. 
   Допустим, есть массив, упорядоченный по возрастанию. Требуется обеспечить вставку нового значения без нарушения порядка. Потребуется перенос всех более «правых» элементов по сравнению со вставляемым значением.
   
2. 
   При частой и плохо предсказуемой смене числа элементов массива требуется либо всё время иметь большой запас свободного места (что неэффективно в плане использования памяти), либо периодически копировать элементы при перевыделении памяти.
   

При большом количестве элементов описанные эффекты могут становиться недопустимо дорогостоящими.

Для преодоления описанных недостатков программисты разработали для разных случаев различные динамические структуры данных.

2. Связные структуры

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

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

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

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

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

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

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

2. Абстрактные типы данных (АТД)

   1. Понятие АТД

Абстра́ктный тип да́нных (АТД) — это тип данных, который предоставляет для работы с элементами этого типа определённый набор функций, а также возможность создавать элементы этого типа при помощи специальных функций. Вся внутренняя структура такого типа спрятана от разработчика программного обеспечения — в этом и заключается суть абстракции. Абстрактный тип данных определяет набор функций, независимых от конкретной реализации типа, для оперирования его значениями. Конкретные реализации АТД называются структурами данных.

2. Интерфейс и реализация

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

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

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