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

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

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

С другой стороны, множеству значений, которые может принимать некоторая переменная, константа, функция или выражение соответствует понятие типа данных. Информация по каждому типу однозначно определяет:

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

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

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

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

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

Абстрактный тип данных (АТД) – это математическая модель с совокупностью операторов или операций определенных в рамках данной модели. Операции АТД реализуют функциональное назначения математической модели.

Абстрактному типу данных соответствует понятие класса в объектно-ориентированном программирование (ООП). Как известно, класс состоит свойств и методов класса. Свойства представляют собой совокупность переменных для описания объекта предметной области, а методы – набор допустимых операций над ним, реализованных в рамках данного класса.

К АТД применимы понятия инкапсуляции, абстрагирования (обобщение) и наследования парадигмы ООП:

1. Абстракция или обобщение в том смысле, что АТД можно рассматривать как обобщение понятия типа данных.

2. Наследование применимо в том смысле, что одни абстрактные типы данных могут быть описаны на основе АТД, реализация которых уже осуществлена в базовых АТД.

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

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

Независимо от содержания и сложности любые данные в памяти ЭВМ представляются последовательностью двоичных разрядов, или битов, а их значениями являются соответствующие двоичные числа. Данные, рассматриваемые в виде последовательности битов, имеют очень простую организацию или, другими словами, слабо структурированы. Для человека описывать и исследовать сколько-нибудь сложные данные в терминах последовательностей битов весьма неудобно. Более крупные и содержательные, нежели бит, «строительные блоки» для организации произвольных данных получаются на основе понятия «структуры данного».

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

Понятие «физическая структура данных» отражает способ физического представления данных в памяти машины и называется еще структурой хранения, внутренней структурой или структурой памяти.

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

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

Важный признак составной структуры данных – характер упорядоченности ее составных частей. По этому признаку структуры можно делить на линейные и нелинейные структуры.

Классификация структур данных по вышеназванным признакам приведена ниже (см. Рисунок 1).

Весьма важный признак структуры данных – ее изменчивость, то есть изменение числа элементов и/или связей между составными частями структуры. В определении изменчивости структуры не отражен факт изменения значений элементов данных, поскольку в этом случае все структуры данных имели бы свойство изменчивости. По признаку изменчивости различают структуры статические и динамические.

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

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

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