Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

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

Теперь можно дать более конкретное определение данного на

машинном уровне представления информации.

Независимо от содержания и сложности любые данные в памяти

ЭВМ представляются последовательностью двоичных разрядов, или би-

тов, а их значениями являются соответствующие двоичные числа.

Данные, рассматриваемые в виде последовательности битов, имеют

очень простую организацию или, другими словами, слабо структури-

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

сложные данные в терминах последовательностей битов весьма неу-

добно. Более крупные и содержательные, нежели бит, "строительные

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

понятия "структуры данного".

Под СТРУКТУРОЙ ДАННЫХ в общем случае понимают множество эле-

ментов данных и множество связей между ними. Такое определение

охватывает все возможные подходы к структуризации данных, но в

каждой конкретной задаче используются те или иные его аспекты.

Поэтому вводится дополнительная классификация структур данных,

направления которой соответствуют различным аспектам их рассмот-

рения. Прежде чем приступать к изучению конкретных структур дан-

ных, дадим их общую классификацию по нескольким признакам.

Понятие "ФИЗИЧЕСКАЯ структура данных" отражает способ физи-

ческого представления данных в памяти машины и называется еще

структурой хранения, внутренней структурой или структурой памяти.

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

машинной памяти называется абстрактной или ЛОГИЧЕСКОЙ структурой.

В общем случае между логической и соответствующей ей физической

структурами существует различие, степень которого зависит от са-

мой структуры и особенностей той среды, в которой она должна быть

отражена. Вследствие этого различия существуют процедуры, осу-

ществляющие отображение логической структуры в физическую и, нао-

борот, физической структуры в логическую. Эти процедуры обеспечи-

вают, кроме того, доступ к физическим структурам и выполнение над

ними различных операций, причем каждая операция рассматривается

применительно к логической или физической структуре данных.

Различаются ПРОСТЫЕ (базовые, примитивные) структуры (типы)

данных и ИНТЕГРИРОВАННЫЕ (структурированные, композитные, слож-

ные). Простыми называются такие структуры данных, которые не мо-

гут быть расчленены на составные части, большие, чем биты. С точ-

ки зрения физической структуры важным является то обстоятельство,

что в данной машинной архитектуре, в данной системе программиро-

вания мы всегда можем заранее сказать, каков будет размер данного

простого типа и какова структура его размещения в памяти. С логи-

ческой точки зрения простые данные являются неделимыми единицами.

Интегрированными называются такие структуры данных, составными

частями которых являются другие структуры данных - простые или в

свою очередь интегрированные. Интегрированные структуры данных

конструируются программистом с использованием средств интеграции

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

В зависимости от отсутствия или наличия явно заданных связей

между элементами данных следует различать НЕСВЯЗНЫЕ структуры

(векторы, массивы, строки, стеки, очереди) и СВЯЗНЫЕ структуры

(связные списки).

Весьма важный признак структуры данных - ее изменчивость -

изменение числа элементов и (или) связей между элементами струк-

туры. В определении изменчивости структуры не отражен факт изме-

нения значений элементов данных, поскольку в этом случае все

структуры данных имели бы свойство изменчивости. По признаку из-

менчивости различают структуры СТАТИЧЕСКИЕ, ПОЛУСТАТИЧЕСКИЕ, ДИ-

НАМИЧЕСКИЕ. Классификация структур данных по признаку изменчивос-

ти приведена на рис. 1.1. Базовые структуры данных, статические,

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

и часто называются оперативными структурами. Файловые структуры

соответствуют структурам данных для внешней памяти.

┌───────────────────┐

│ СТРУКТУРЫ ДАННЫХ │

└─────────┬─────────┘

┌─────────────┬───────────┼─────────────┬────────────┐

┌────┴─────┐ ┌─────┴────┐ ┌────┴─────┐ ┌─────┴────┐ ┌─────┴────┐

│ ПРОСТЫЕ │ │ СТАТИЧЕС-│ │ПОЛУСТАТИ-│ │ДИНАМИЧЕС-│ │ ФАЙЛОВЫЕ │

│ БАЗОВЫЕ │ │ КИЕ │ │ ЧЕСКИЕ │ │ КИЕ │ │СТРУКТУРЫ │

│СТРУКТУРЫ │ │СТРУКТУРЫ │ │СТРУКТУРЫ │ │СТРУКТУРЫ │ │ (Файлы) │

└┬─────────┘ └┬─────────┘ └┬─────────┘ └┬─────────┘ └┬─────────┘

│ Числовые │ Вектор │ Стеки │Линейные │Последова-

├─────────── ├─────────── ├───────── │связные │тельные

│ Символьные │ Массивы │ Очереди │списки ├──────────

├─────────── ├─────────── ├───────── ├───────── │Прямого

│ Логические │ Множества │ Деки │Разветвлен- │доступа

├─────────── ├─────────── ├───────── │ные связные ├──────────

│Перечисление│ Записи │ Строки │списки │Комбиниро-

├─────────── ├─────────── └───────── ├─────────── │ванного

│Интервал │ Таблицы │ Графы │доступа

├─────────── └─────────── ├─────────── ├──────────

│Указатели │ Деревья │Организо-

└─────────── └─────────── │ванные

│разделами

└──────────

Рис. 1.1. Классификация структур данных

Важный признак структуры данных - характер упорядоченности

ее элементов. По этому признаку структуры можно делить на ЛИНЕЙ-

НЫЕ И НЕЛИНЕЙНЫЕ структуры.

В зависимости от характера взаимного расположения элементов

в памяти линейные структуры можно разделить на структуры с ПОСЛЕ-

ДОВАТЕЛЬНЫМ распределением элементов в памяти (векторы, строки,

массивы, стеки, очереди) и структуры с ПРОИЗВОЛЬНЫМ СВЯЗНЫМ расп-

ределением элементов в памяти (односвязные, двусвязные списки).

Пример нелинейных структур - многосвязные списки, деревья, графы.

В языках программирования понятие "структуры данных" тесно

связано с понятием "типы данных". Любые данные, т.е. константы,

переменные, значения функций или выражения, характеризуются свои-

ми типами.

Информация по каждому типу однозначно определяет:

1) структуру хранения данных указанного типа, т.е. выделение па-

мяти и представление данных в ней, с одной стороны, и интерпрети-

рование двоичного представления, с другой;

2) множество допустимых значений, которые может иметь тот или

иной объект описываемого типа;

3) множество допустимых операций, которые применимы к объекту

описываемого типа.

В последующих главах данного пособия рассматриваются струк-

туры данных и соответствующие им типы данных. При описании базо-

вых (простых) типов и при конструировании сложных типов ориенти-

ровались в основном на язык PASCAL. Этот язык использовался и во

всех иллюстративных примерах. PASCAL был создан Н.Виртом специ-

ально для иллюстрирования структур данных и алгоритмов и традици-

онно используется для этих целей. Читатель знакомый с любым дру-

гим процедурным языком программирования общего назначения (C,

FORTRAN, ALGOL, PL/1 и т.д.) без труда найдет аналогичные средс-

тва в известном ему языке.