Тема 2.3 ПРОСТЫЕ структуры данных:
Числовые типы, целые типы,
вещественные типы,
десятичные типы,
битовые
типы, логический тип, символьный тип, перечислимый тип, интервальный тип, указатели.
СТАТИЧЕСКИЕ структуры данных:
Векторы, массивы
Множества:
числовые множества,
символьные множества,
множество из
элементов перечислимого типа, множество от
интервального типа, записи
ПОЛУСТАТИЧЕСКИЕ структуры данных:
Стеки, очереди
FIFO, деки, строки
ДИНАМИЧЕСКИЕ структуры
данных: Связные списки, мультисписки, нелинейные разветвленные списки
НЕЛИНЕЙНЫЕ структуры данных: Графы, деревья
Понятие
структур данных
Структуры данных служит тем материалом, из
которого строятся программы.
Более того, сам компьютер состоит из
структур данных. Встроенные структуры данных представлены теми регистрами и
словами памяти, где хранятся двоичные величины.
Задачи, которые решаются с помощью
компьютера, редко выражаются на языке битов. Как правило, данные имеют форму чисел, литер, текстов,
символов и более сложных структур типа последовательностей, списков и деревьев.
Для точного описания абстрактных структур
данных программ используются такие системы формальных обозначений, называемые
языками программирования, в которых смысл всякого предложения определяется
точно и однозначно. Для компьютера все типы данных сводятся в конечном счете к
последовательности битов, поэтому различие
в типах следует делать явным.
Типы данных, принятые в языках
программирования, включают натуральные и целые числа, вещественные
(действительные) числа (в виде приближенных десятичных дробей), литеры, строки
и т.п.
В некоторых языках программирования тип
каждой константы или переменной определяется компилятором по записи
присваиваемого значения; наличие десятичной точки, например, может служить
признаком вещественного числа. В других языках требуется, чтобы программист
явно задал тип каждой переменной, и это дает одно важное преимущество. Хотя при
выполнении программы значение переменной может многократно меняться, тип ее
меняться не должен никогда; это значит, что компилятор может проверить
операции, выполняемые над этой переменной, и убедиться в том, что все они
согласуются с описанием типа переменной. Такая проверка может быть проведена
путем анализа всего текста программы, и в этом случае она охватит все возможные
действия, определяемые данной программой.
В зависимости от назначения языка программирования
защита типов, осуществляемая на этапе компиляции, может быть более или менее
жесткой. Так, например, язык PASCAL, изначально являвшийся прежде всего
инструментом для иллюстрирования структур данных и алгоритмов, сохраняет от
своего первоначального назначения весьма строгую защиту типов.
PASCAL-компилятор в большинстве случаев расценивает смешение в одном выражении
данных разных типов или применение к типу данных несвойственных ему операций
как фатальную ошибку. Напротив, язык C, предназначенный, прежде всего для
системного программирования, является языком с весьма слабой защитой типов.
C-компиляторы в таких случаях лишь выдают предупреждения. Отсутствие жесткой
защиты типов дает системному программисту, разрабатывающему программу на языке
C, дополнительные возможности, но такой программист сам отвечает за
правильность своих действий.
Структура данных относится, по
существу, к "пространственным" понятиям: ее можно свести к схеме
организации информации в памяти компьютера.
Структуры данных, применяемые в алгоритмах,
могут быть чрезвычайно сложными. В результате выбор правильного представления
данных часто служит ключом к удачному программированию и может в большей
степени сказываться на производительности программы, чем детали используемого
алгоритма. Вряд ли когда-нибудь появится общая теория выбора структур данных.
Классификация структур данных
Независимо от содержания и сложности любые
данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или
битов, а их значениями являются соответствующие двоичные числа. Данные,
рассматриваемые в виде последовательности битов, имеют очень простую
организацию или, другими словами, слабо структурированы. Для человека описывать
и исследовать сколько-нибудь сложные данные в терминах последовательностей
битов весьма неудобно. Более крупные и содержательные, нежели бит,
"строительные блоки" для организации произвольных
данных получаются на основе понятия "структуры данного".
Под СТРУКТУРОЙ ДАННЫХ в общем случае понимают множество элементов данных и
множество связей между ними. Такое определение охватывает все возможные
подходы к структуризации данных, но в каждой конкретной задаче используются те
или иные его аспекты. Поэтому вводится дополнительная классификация структур
данных, направления которой соответствуют различным аспектам их рассмотрения.
Прежде чем приступать к изучению конкретных структур данных, дадим их общую
классификацию по нескольким признакам.
Понятие "ФИЗИЧЕСКАЯ структура данных"
отражает способ физического представления данных в памяти машины и называется
еще структурой хранения, внутренней структурой или структурой памяти.
Рассмотрение структуры данных без учета ее
представления в машинной памяти называется абстрактной или ЛОГИЧЕСКОЙ
структурой. В общем случае между логической и
соответствующей ей физической структурами существует различие, степень которого
зависит от самой структуры и особенностей той среды, в которой она должна быть
отражена. Вследствие этого различия существуют процедуры, осуществляющие
отображение логической структуры в физическую и, наоборот, физической структуры
в логическую. Эти процедуры обеспечивают, кроме того, доступ к физическим
структурам и выполнение над ними различных операций, причем каждая операция
рассматривается применительно к логической или физической структуре данных.
Различаются ПРОСТЫЕ (базовые, примитивные) структуры (типы) данных и
ИНТЕГРИРОВАННЫЕ (структурированные, композитные, сложные). Простыми называются
такие структуры данных, которые не могут быть расчленены на составные части, большие,
чем биты. С точки зрения физической структуры важным является то обстоятельство,
что в данной машинной архитектуре, в данной системе программирования мы всегда
можем заранее сказать, каков будет размер данного простого типа и какова
структура его размещения в памяти. С логической точки зрения простые данные
являются неделимыми единицами.
Интегрированными
называются такие структуры данных, составными частями которых являются другие
структуры данных - простые или в свою очередь интегрированные. Интегрированные
структуры данных конструируются программистом с использованием средств
интеграции данных, предоставляемых языками программирования.
В зависимости от отсутствия или наличия явно заданных связей между
элементами данных следует различать НЕСВЯЗНЫЕ структуры (векторы, массивы,
строки, стеки, очереди) и СВЯЗНЫЕ структуры (связные списки).
Весьма важный признак структуры данных - ее изменчивость - изменение
числа элементов и (или) связей между элементами структуры. В
определении изменчивости структуры не отражен факт изменения значений элементов
данных, поскольку в этом случае все структуры данных имели бы свойство
изменчивости. По признаку изменчивости различают структуры
СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИНАМИЧЕСКИЕ. Базовые структуры данных, статические,
полустатические и динамические характерны для оперативной памяти и
часто называются оперативными структурами. Файловые структуры соответствуют
структурам данных для внешней памяти.
Рис. Классификация структур данных
Важный признак структуры данных - характер упорядоченности ее
элементов. По этому признаку структуры можно делить на ЛИНЕЙНЫЕ И НЕЛИНЕЙНЫЕ
структуры.
В зависимости от характера взаимного расположения элементов в памяти
линейные структуры можно разделить на структуры с ПОСЛЕДОВАТЕЛЬНЫМ
распределением элементов в памяти (векторы, строки, массивы, стеки, очереди) и
структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ распределением элементов в памяти ( односвязные,
двусвязные списки). Пример нелинейных структур - многосвязные списки, деревья,
графы.
В языках программирования понятие
"структуры данных" тесно связано с понятием "типы данных".
Любые данные, т.е. константы, переменные, значения функций или выражения,
характеризуются своими типами.
Информация по каждому типу однозначно
определяет :
1) структуру хранения данных указанного типа,
т.е. выделение памяти и представление данных в ней, с одной стороны, и
интерпретирование двоичного представления, с другой;
2) множество допустимых значений, которые
может иметь тот или иной объект описываемого типа;
3) множество допустимых операций, которые
применимы к объекту описываемого типа.
Операции над структурами данных
Над любыми структурами данных могут выполняться четыре общие операции: создание, уничтожение, выбор (доступ), обновление.
Операция создания заключается в выделении памяти для структуры данных.
Память может выделяться в процессе выполнения программы или на этапе
компиляции. Для структур данных, объявленных в программе,
память выделяется автоматически средствами систем программирования либо на
этапе компиляции, либо при активизации процедурного блока, в котором
объявляются соответствующие переменные. Программист может и сам выделять память
для структур данных, используя имеющиеся в системе программирования
процедуры/функции выделения/освобождения памяти. В объектно-ориентированных
языках программирования при разработке нового объекта для него должны быть
определены процедуры создания и уничтожения.
Главное заключается в том, что независимо от
используемого языка программирования, имеющиеся в программе структуры данных не
появляются "из ничего", а явно или неявно объявляются операторами
создания структур. В результате этого всем экземплярам структур в программе
выделяется память для их размещения.
Операция уничтожения структур данных противоположна по своему действию
операции создания.Операция уничтожения помогает эффективно использовать память.
Операция выбора используется программистами для доступа к данным внутри самой структуры. Форма операции доступа зависит от типа структуры данных, к которой осуществляется обращение. Метод доступа - один из наиболее важных свойств структур, особенно в связи с тем, что это свойство имеет непосредственное отношение к выбору конкретной структуры данных.
Операция обновления позволяет изменить значения данных в структуре
данных. Примером операции обновления является операция присваивания, или, более
сложная форма - передача параметров.
Вышеуказанные четыре операции обязательны для всех структур и типов данных. Помимо этих общих операций для каждой структуры данных могут быть определены операции специфические, работающие только с данными данного типа (данной структуры). Специфические операции рассматриваются при рассмотрении каждой конкретной структуры данных.
Структурность данных и
технология программирования
знание структуры данных позволяет организовать их хранение и обработку
максимально эффективным образом - с точки зрения минимизации затрат как памяти,
так и процессорного времени. Другим не менее, а может быть, и более важным
преимуществом, которое обеспечивается структурным подходом к данным, является
возможность структурирования сложного программного изделия. Программисту,
который хочет, чтобы его программа имела реальное применение в некоторой
прикладной области не следует забывать о том, что программирование - это
обработка данных. Таким образом, задачей любого программного изделия является
преобразование входных данных в выходные. Инструментальные средства программирования
предоставляют набор базовых (простых, примитивных) типов данных и операции над
ними. Интегрируя базовые типы, программист создает более сложные типы данных и
определяет новые операции над сложными типами. Ключевым понятием в СУБД
является понятие модели данных, в основном тождественное понятию логической
структуры данных. Отметим, что физическая структура данных в СУБД не
рассматривается вообще. Но сами СУБД являются программными пакетами,
выполняющими отображение физической структуры в логическую (в модель данных).
Для реализации этих пакетов используются те или иные системы программирования,
разработчики СУБД, следовательно, имеют дело со структурами данных в терминах
систем программирования. Для пользователя же внутренняя структура СУБД и физическая
структура данных совершенно прозрачна; он имеет дело только с моделью данных и
с другими понятиями логического уровня.
