Структурная организация данных

Основные понятия структур данных

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

Компьютер оперирует с одним видом данных – с отдельными битами и работает с этими данными только в соответствии неизменным набором алго- ритмов, которые определяются системой команд центрального процессора. В настоящее время задачи, которые решаются с помощью компьютера выража- ются не на языке битов, а на языках более высокого уровня. Данные, исполь- зуемые при решении экономических задач, имеют форму чисел, символов, тек- стов, и более сложных структур типа последовательностей, списков и деревьев. Структура данных, рассматриваемая без учета ее представления в ма- шинной памяти, называется абстрактной или логической. Понятие «физиче- ская структура данных» отражает способ физического представления данных в памяти компьютера. Вследствие различия между логической и соответствую- щей ей физической структурами в вычислительной системе существуют проце- дуры, осуществляющие отображение логической структуры в физическую структуру и наоборот. Например, доступ к элементу двумерного массива на ло- гическом уровне реализуется указанием номеров строки и столбца в прямо- угольной таблице, на пересечении которых расположен соответствующий эле- мент. На физическом же уровне к элементу массива доступ осуществляется с помощью функции адресации, которая при известном начальном адресе масси- ва в машинной памяти преобразует номера строки и столбца в адрес соответст- вующего элемента массива. Таким образом, каждую структуру данных можно характеризовать ее логическим (абстрактным) и физическим (конкретным) представлениями, а также совокупностью операций на этих уровнях представ- ления. В рамках данного пособия будут рассматриваться абстрактные структу- ры данных, так как для составления алгоритмов решения прикладных задач ис-

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

Под структурой данных в общем случае понимают множество элемен- тов данных и связей между ними. Связи между элементами представляют собой отношения, заданные на множестве данных.

Пусть Х – множество данных, У – множество значений данных Х

µ

→ У,

при этом µ(х) = { х-_i:  х_i  ∈ Х, х-_i ∈ Х }. Если на множестве µ(х)  задано отноше-

ние S(х) $: µ (х), то будем называть это отношение структурой данных, а µ(х) – областью определения структуры данных. Структура данных называется простой, если между значениями данных связи отсутствуют, т. е. S(х) = 0 и µ (х) :;t0.

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

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

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

ные структуры (векторы, массивы, строки, стеки, очереди) и связанные струк- туры (связанные списки, графы, деревья).