Динамические структуры и абстракции данных

	Лекция. Динамические структуры и абстракции данных
		Новосибирск 11.02.2014

Оглавление

Изучаемые темы: 3

Изучаемые вопросы: 3

Изучаемые понятия: 3

Тезисы.. 3

Структуры хранения данных. 4

Структуры хранения данных. 4

Структуры данных и алгоритмы.. 4

Разновидности структур хранения данных. 4

Списочные структуры.. 4

Древовидные структуры.. 6

Графовая структура. 7

Абстрактные типы данных (ADT) 8

Список. 8

Пример реализации абстрактного типа данных (ADT) «список». 9

Стек. 23

Очередь. 24

Очередь с приоритетом.. 24

Контрольные вопросы.. 24

Источники дополнительных сведений. 24

Введение

Изучаемые темы:

·  Структуры хранения данных.

·  Абстракции данных.

Изучаемые вопросы:

Абстракции данных. Спецификация. Множество реализаций.

Список, упорядоченный список, стек, очередь, очередь с приоритетом, дерево, граф.

Изучаемые понятия:

Тезисы

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

 
Структуры хранения данных

Структуры данных и алгоритмы

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

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

Разновидности структур хранения данных

Необходимо по возможности более точно с учётом организации памяти реализовать структуру данных, обеспечивающую эффективность их обработки большим числом алгоритмов. С этой точки зрения рассмотрим типичные методы хранения данных в ЭВМ.

Одномерный массив

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

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

Двумерный массив

Этот способ хранения данных широко применяется на практике. Если длина (m) строки или столбца известна, то для выборки элемента необходимо определить место его расположения в памяти по формуле A[i,j] = A₀ + (i - 1)*m + j.

Списочные структуры

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

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

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

Списочная структура.

Двусвязный список.

Кольцевой список.

Список с дескриптором списка.

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