CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ

CТРУКТУРЫ ДАННЫХ И АЛГОРИТМЫ

Понятие структур данных и алгоритмов

торых строятся программы. Более того, сам компьютер состоит из структур данных и алгоритмов. Встроенные структуры данных предс- тавлены теми регистрами и словами памяти, где хранятся двоичные

Природа информации

тельной машины включает запись в память, извлечение и манипулиро- вание информацией. Можно ли измерить информацию? В теоретико-информационном смысле информация рассматривается

Хранение информации

ных вида запоминающих устройств: сверхоперативная, оперативная и внешняя память. Сверхоперативная память строится обычно на регистрах. Ре-

Системы счисления

Чтобы обеспечить соответствующую основу для изучения струк-

тур данных следует обсудить существующие типы систем счислений:

позиционные и непозиционные.

Непозиционные системы счисления

чества объектов. Очень простым методом представления количества является использование одинаковых значков. В такой системе между значками и пересчитываемыми объектами устанавливается взаимно од-

Позиционные системы счисления

R уникальных символов. Величину R часто называют основанием сис- темы счисления. В позиционной системе количество представляется как самими символами, так и их позицией в записи числа.

Перевод чисел из одной системы счисления в другую

темы счисления в другую исходное число (или целую часть) надо разделить на основание системы счисления, в которую выполняется перевод. Деление выполнять, пока частное не станет меньше основа-

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ти приведена на рис. 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 структуры данных, име-

ющиеся внутри блока, уничтожаются в процессе выполнения программы

при выходе из этого блока. Операция уничтожения помогает эффек-

тивно использовать память.

Операция выбора используется программистами для доступа к

данным внутри самой структуры. Форма операции доступа зависит от

типа структуры данных, к которой осуществляется обращение. Метод

доступа - один из наиболее важных свойств структур, особенно в

связи с тем, что это свойство имеет непосредственное отношение к

выбору конкретной структуры данных.

Операция обновления позволяет изменить значения данных в

структуре данных. Примером операции обновления является операция

присваивания, или, более сложная форма - передача параметров.

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

и типов данных. Помимо этих общих операций для каждой структуры

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

только с данными данного типа (данной структуры). Специфические

операции рассматриваются при рассмотрении каждой конкретной

структуры данных.

Структурность данных и технология программирования

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