CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ
Системы счисления
Чтобы обеспечить соответствующую основу для изучения струк-
тур данных следует обсудить существующие типы систем счислений:
позиционные и непозиционные.
Классификация структур данных
Теперь можно дать более конкретное определение данного на
машинном уровне представления информации.
Независимо от содержания и сложности любые данные в памяти
ЭВМ представляются последовательностью двоичных разрядов, или би-
тов, а их значениями являются соответствующие двоичные числа.
Данные, рассматриваемые в виде последовательности битов, имеют
очень простую организацию или, другими словами, слабо структури-
рованы. Для человека описывать и исследовать сколько - нибудь
сложные данные в терминах последовательностей битов весьма неу-
добно. Более крупные и содержательные, нежели бит, "строительные
блоки" для организации произвольных данных получаются на основе
понятия "структуры данного".
Под СТРУКТУРОЙ ДАННЫХ в общем случае понимают множество эле-
ментов данных и множество связей между ними. Такое определение
охватывает все возможные подходы к структуризации данных, но в
каждой конкретной задаче используются те или иные его аспекты.
Поэтому вводится дополнительная классификация структур данных,
направления которой соответствуют различным аспектам их рассмот-
рения. Прежде чем приступать к изучению конкретных структур дан-
ных, дадим их общую классификацию по нескольким признакам.
Понятие "ФИЗИЧЕСКАЯ структура данных" отражает способ физи-
ческого представления данных в памяти машины и называется еще
структурой хранения, внутренней структурой или структурой памяти.
Рассмотрение структуры данных без учета ее представления в
машинной памяти называется абстрактной или ЛОГИЧЕСКОЙ структурой.
В общем случае между логической и соответствующей ей физической
структурами существует различие, степень которого зависит от са-
мой структуры и особенностей той среды, в которой она должна быть
отражена. Вследствие этого различия существуют процедуры, осу-
ществляющие отображение логической структуры в физическую и, нао-
борот, физической структуры в логическую. Эти процедуры обеспечи-
вают, кроме того, доступ к физическим структурам и выполнение над
ними различных операций, причем каждая операция рассматривается
применительно к логической или физической структуре данных.
Различаются ПРОСТЫЕ (базовые, примитивные) структуры (типы)
данных и ИНТЕГРИРОВАННЫЕ (структурированные, композитные, слож-
ные). Простыми называются такие структуры данных, которые не мо-
гут быть расчленены на составные части, большие, чем биты. С точ-
ки зрения физической структуры важным является то обстоятельство,
что в данной машинной архитектуре, в данной системе программиро-
вания мы всегда можем заранее сказать, каков будет размер данного
простого типа и какова структура его размещения в памяти. С логи-
ческой точки зрения простые данные являются неделимыми единицами.
Интегрированными называются такие структуры данных, составными
частями которых являются другие структуры данных - простые или в
свою очередь интегрированные. Интегрированные структуры данных
конструируются программистом с использованием средств интеграции
данных, предоставляемых языками программирования.
В зависимости от отсутствия или наличия явно заданных связей
между элементами данных следует различать НЕСВЯЗНЫЕ структуры
(векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры
(связные списки).
Весьма важный признак структуры данных - ее изменчивость -
изменение числа элементов и (или) связей между элементами струк-
туры. В определении изменчивости структуры не отражен факт изме-
нения значений элементов данных, поскольку в этом случае все
структуры данных имели бы свойство изменчивости. По признаку из-
менчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИ-
НАМИЧЕСКИЕ. Классификация структур данных по признаку изменчивос-
ти приведена на рис. 1.1. Базовые структуры данных, статические,
полустатические и динамические характерны для оперативной памяти
и часто называются оперативными структурами. Файловые структуры
соответствуют структурам данных для внешней памяти.
┌───────────────────┐
│ СТРУКТУРЫ ДАННЫХ │
└─────────┬─────────┘
┌─────────────┬───────────┼─────────────┬────────────┐
┌────┴─────┐ ┌─────┴────┐ ┌────┴─────┐ ┌─────┴────┐ ┌─────┴────┐
│ ПРОСТЫЕ │ │ СТАТИЧЕС-│ │ПОЛУСТАТИ-│ │ДИНАМИЧЕС-│ │ ФАЙЛОВЫЕ │
│ БАЗОВЫЕ │ │ КИЕ │ │ ЧЕСКИЕ │ │ КИЕ │ │СТРУКТУРЫ │
│СТРУКТУРЫ │ │СТРУКТУРЫ │ │СТРУКТУРЫ │ │СТРУКТУРЫ │ │ (Файлы) │
└┬─────────┘ └┬─────────┘ └┬─────────┘ └┬─────────┘ └┬─────────┘
│ Числовые │ Вектор │ Стеки │Линейные │Последова-
├─────────── ├─────────── ├───────── │связные │тельные
│ Символьные │ Массивы │ Очереди │списки ├──────────
├─────────── ├─────────── ├───────── ├───────── │Прямого
│ Логические │ Множества │ Деки │Разветвлен- │доступа
├─────────── ├─────────── ├───────── │ные связные ├──────────
│Перечисление│ Записи │ Строки │списки │Комбиниро-
├─────────── ├─────────── └───────── ├─────────── │ванного
│Интервал │ Таблицы │ Графы │доступа
├─────────── └─────────── ├─────────── ├──────────
│Указатели │ Деревья │Организо-
└─────────── └─────────── │ванные
│разделами
└──────────
Рис. 1.1. Классификация структур данных
Важный признак структуры данных - характер упорядоченности
ее элементов. По этому признаку структуры можно делить на ЛИНЕЙ-
НЫЕ И НЕЛИНЕЙНЫЕ структуры.
В зависимости от характера взаимного расположения элементов
в памяти линейные структуры можно разделить на структуры с ПОСЛЕ-
ДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки,
массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ расп-
ределением элементов в памяти ( односвязные, двусвязные списки).
Пример нелинейных структур - многосвязные списки, деревья, графы.
В языках программирования понятие "структуры данных" тесно
связано с понятием "типы данных". Любые данные, т.е. константы,
переменные, значения функций или выражения, характеризуются свои-
ми типами.
Информация по каждому типу однозначно определяет :
1) структуру хранения данных указанного типа, т.е. выделение па-
мяти и представление данных в ней, с одной стороны, и интерпрети-
рование двоичного представления, с другой;
2) множество допустимых значений, которые может иметь тот или
иной объект описываемого типа;
3) множество допустимых операций, которые применимы к объекту
описываемого типа.
В последующих главах данного пособия рассматриваются струк-
туры данных и соответствующие им типы данных. При описании базо-
вых (простых) типов и при конструировании сложных типов ориенти-
ровались в основном на язык PASCAL. Этот язык использовался и во
всех иллюстративных примерах. PASCAL был создан Н.Виртом специ-
ально для иллюстрирования структур данных и алгоритмов и традици-
онно используется для этих целей. Читатель знакомый с любым дру-
гим процедурным языком программирования общего назначения (C,
FORTRAN, ALGOL, PL/1 и т.д.) без труда найдет аналогичные средс-
тва в известном ему языке.
Операции над структурами данных
Над всеми структурами данных могут выполняться четыре опера-
ции: создание, уничтожение, выбор (доступ), обновление.
Операция создания заключается в выделении памяти для струк-
туры данных. Память может выделяться в процессе выполнения прог-
раммы при первом появлении имени переменной в исходной программе
или на этапе компиляции. В ряде языков (например, в С) для струк-
турированных данных, конструируемых программистом, операция соз-
дания включает в себя также установку начальных значений парамет-
ров, создаваемой структуры.
Например, в PL/1 оператор DECLARE N FIXED DECIMAL приведет к
выделению адресного пространства для переменной N во время выпол-
нения программы. В FORTRAN (Integer I), в PASCAL (I:integer), в C
(int I) в результате описания типа будет выделена память для со-
ответствующих переменных. Для структур данных, объявленных в
программе память выделяется автоматически средствами системы
программирования либо на этапе компиляции, либо при активизации
процедурного блока, в котором объявляются соответствующие пере-
менные. Программист может и сам выделять память для структур дан-
ных, используя имеющиеся в системе программирования процеду-
ры/функции выделения/освобождения памяти. В объектно-ориентиро-
ванных языках программирования при разработке нового объекта для
него должны быть определены процедуры создания и уничтожения.
Главное заключается в том, что независимо от используемого
языка программирования, имеющиеся в программе структуры данных не
появляются "из ничего", а явно или неявно объявляются операторами
создания структур. В результате этого всем структурам программы
выделяется память для их размещения.
Операция уничтожения структур данных противоположна по свое-
му действию операции создания. Некоторые языки, такие как BASIC,
FORTRAN не дают возможности программисту уничтожать созданные
структуры данных. В языках PL/1, C, PASCAL структуры данных, име-
ющиеся внутри блока, уничтожаются в процессе выполнения программы
при выходе из этого блока. Операция уничтожения помогает эффек-
тивно использовать память.
Операция выбора используется программистами для доступа к
данным внутри самой структуры. Форма операции доступа зависит от
типа структуры данных, к которой осуществляется обращение. Метод
доступа - один из наиболее важных свойств структур, особенно в
связи с тем, что это свойство имеет непосредственное отношение к
выбору конкретной структуры данных.
Операция обновления позволяет изменить значения данных в
структуре данных. Примером операции обновления является операция
присваивания, или, более сложная форма - передача параметров.
Вышеуказанные четыре операции обязательны для всех структур
и типов данных. Помимо этих общих операций для каждой структуры
данных могут быть определены операции специфические, работающие
только с данными данного типа (данной структуры). Специфические
операции рассматриваются при рассмотрении каждой конкретной
структуры данных.