logo search
УП_САОД_2003

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

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

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

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

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

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

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

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

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

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

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

В языках программирования понятие «структуры данных» тесно связано с понятием «типы данных». Любые данные, то есть константы, переменные, значения функций или выражения, характеризуются своими типами.

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

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

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

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