Типы структур данных. Что такое структуры данных

Понятие модели данных

Модели данных

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

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

1. Набор типов структур данных.

Здесь можно провести аналогию с языками программирования, в которых тоже есть предопределённые типы структур данных, такие как скалярные данные, вектора, массивы, структуры (например, тип struct в языке Си) и т.д.

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

Такими операциями являются: создание и модификация структур данных, внесение новых данных, удаление и модификация существующих данных, поиск данных по различным условиям.

1. Набор общих правил целостности, которые прямо или косвенно определяют множество непротиворечивых состояний базы данных и/или множество изменений её состояния.

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

Теперь рассмотрим подробнее наборы, составляющие модель данных.

Структуризация данных базируется на использовании концепций "агрегации" и "обобщения". Один из первых вариантов структуризации данных был предложен Ассоциацией по языкам обработки данных (Conference on Data Systems Languages, CODASYL) (рис. 2.1).

Рис.2.1 Композиция структур данных по версии CODASYL

Элемент данных – наименьшая поименованная единица данных, к которой СУБД может обращаться непосредственно и с помощью которой выполняется построение всех остальных структур. Для каждого элемента данных должен быть определён его тип.

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

Рис.2.2 Примеры агрегатов: а) простой и б) составной агрегат

Запись – поименованная совокупность элементов данных или эле-ментов данных и агрегатов. Запись – это агрегат, не входящий в состав никакого другого агрегата; она может иметь сложную иерархическую структуру, поскольку допускается многократное применение агрегации. Различают тип записи (её структуру) и экземпляр записи, т.е. запись с конкретными значениями элементов данных. Одна запись описывает свойства одной сущности ПО (экземпляра). Иногда термин "запись" за-меняют термином "группа".

Пример записи, содержащей сведения о сотруднике, приведён на рис. 2.3.

Рис.2.3 Пример записи типа СОТРУДНИК

Эта запись имеет несколько элементов данных (Номер пропуска, Должность, Пол и т.д.) и три агрегата: простые агрегаты ФИО и Адрес и повторяющийся агрегат Телефоны . (Повторяющийся агрегат может включаться в запись произвольное число раз).

Среди элементов данных (полей записи) выделяются одно или несколько ключевых полей . Значения ключевых полей позволяют классифицировать сущность, к которой относится конкретная запись. Ключи с уникальными значениями называются потенциальными . Каждый ключ может представлять собой агрегат данных. Один из ключей назначается первичным, остальные являются вторичными. Первичный ключ идентифицирует экземпляр записи, его значение должно быть уникальным и обязательным для записей одного типа. Для примера на рис. 2.3 потенциальными ключами являются поля № пропуска и Паспорт , а первичным ключом целесообразнее выбрать поле № пропуска , т.к. оно явно занимает меньше памяти, чем паспортные данные.

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

Групповые отношения удобно изображать с помощью диаграммы Бахмана, которая названа так по имени одного из разработчиков сетевой модели данных. Диаграмма Бахмана – это ориентированный граф, вершины которого соответствуют группам (типам записей), а дуги – групповым отношениям (рис. 2.4).

Рис. 2.4 Пример диаграммы Бахмана для фрагмента БД "Город"

Здесь запись типа ПОЛИКЛИНИКА является владельцем записей типа ЖИТЕЛЬ диспансеризация . Запись типа ОРГАНИЗАЦИЯ также является владельцем записей типа ЖИТЕЛЬ и они связаны групповым отношением работают . Записи типа РЭУ и типа ЖИТЕЛЬ являются владельцами записей типа КВАРТИРА с отношениями соответственно обслуживают и проживают . Таким образом, запись одного и того же типа может быть членом одного отношения и владельцем другого.

База данных – поименованная совокупность экземпляров групп и групповых отношений. Это самый высокий уровень структуризации данных.

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

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

Первым шагом на пути к облегчению задачи программирования был отказ от использования цифр для записи команд и операндов непосредственно в той форме, в которой они используются в машине. С этой целью при разработке программ стали широко применять мнемоническую запись различных команд вместо их шестнадцатеричного представления. Например, вместо цифрового кода команды загрузки регистра программист мог теперь написать LOD, а вместо кода команды копирования содержимого регистра в память мог использовать мнемоническое обозначение STO. Для записи операндов были разработаны правила, в соответствии с которыми программист мог присваивать некоторым областям памяти описательные имена [их часто называют идентификаторами] и использовать их при записи команд программы вместо адресов соответствующих ячеек памяти. Такие идентификаторы обычно называют переменными. Это подчеркивает, что, изменяя значение, размещенное в данном участке памяти, мы изменяем значение, связанное с идентификатором, присвоенным этому участку по ходу выполнения программы.

При объявлении в программе переменной обычно одновременно определяют и их тип. Тип данных определяет как интерпретацию конкретных данных, так и операции, которые можно с ними выполнять. К типам данных относятся Integer [целый], Real [действительный], Character [символьный] и Boolean [логический].

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

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

Тип Character используется для данных, состоящих из символов, которые хранятся в памяти в виде кодов ASCII или UNICODE. Данные этого типа можно сравнивать друг с другом [определять, какой из двух символов предшествует другому в алфавитном порядке]; проверять, является ли одна строка символов другой, а также объединять две строки в одну, более длинную строку, дописывая одну из них после другой [операция конкатенации].

Boolean относится к данным, которые могут принимать только два значения True [истина] и False [ложь]. Примером таких данных может служить результат операции сравнения двух чисел. Операции с данными типа Boolean включает проверку, является ли текущее значение переменной True или False.

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

Массивы

Массив - это структура, содержащая в себе несколько однотипных элементов. Для упорядочивания элементов массива используются индексы. Индексы записываются в скобках после имени массива. Массив с одним индексом называется одномерным, с двумя - двумерным и т.д.

Запись

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

record Student (
FirstName,
LastName,
Group
)

Списки

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

Записи в односвязном списке имеют по одному указателю, при этом они связанны в цепочку:

Стрелка на рисунке говорит о содержимом указателя, а слово Data обозначает совокупностей полей, в которых хранятся данные. Список можно организовать с помощью двумерного массива, все элементы которого с первым индексом, равным 0, предназначены для хранения данных, а элементы с первым индексом, равным 1, являются указателями.

В данном списке записи, содержащие буквы английского алфавита, выстроены в алфавитном порядке. Первая запись в списке содержит символ "A", вторая - "B" и т.д.

Для работы со списком нужно уметь выполнять три основных операции:

Pass() - обход или перемещение вдоль списка;
Add() - добавление новой записи в список;
Delete() - удаление записи из списка.

Кроме операций для работы со списком нужны еще две переменные:

переменная Head, в которой хранится информация о первой записи в списке
переменная Current, которая указывает на текущую запись в списке

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

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

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

Дерево - это разветвленный список, каждая запись которого может содержать несколько указателей. Записи, входящие в дерево, называются узлами. Узлы, у которых все указатели пустые, называются листьями. Верхний начальный узел дерева называется корневым узлом. Во многих задачах достаточно использовать двоичные [бинарные] деревья, узлы которых имеют не более двух указателей.

Пример. Требуется вычислить математическое выражение (3+7)*(2/(3-1)). Представим это выражение в виде дерева:

Каждый узел этого дерева представляет собой запись следующего вида:

record Node (
Operation
Number
LeftPointer
RightPointer
)

Листья дерева содержат числа, остальные узлы - символы операций.

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

Для вычисления значения дерева нужно вычислить значения правого и левого поддеревьев, а потом над ними выполнить результирующую операцию. Псевдокод алгоритма решающего поставленную задачу будет иметь вид:

function Calculate (Current) {
if (M=Null) then
Result:= M;
else {
R1:=Calculate(M);
R2:=Calculate(M);
Result:=R1(M)R2;
}
return (Result);
}

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

При работе со стеком возможны две аварийные ситуации: попытка прочитать данные из пустого стека; попытка занести в стек элемент, когда количество элементов в стеке достигло максимально допустимого количества.

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

Хеш-таблица

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

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

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

Необходимым условием построения алгоритма является формализация данных , т.е. приведение информации к некоторой информационной модели (см. “Информационные модели ”), уже описанной и исследованной. Когда такая модель найдена, говорят, что определена абстрактная структура данных .

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

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

· целые числа;

· вещественные числа;

· символы;

· логические значения.

Для компьютерной обработки этих объектов в языках программирования существуют соответствующие типы данных (см. “Типы данных ”). Базовые объекты можно объединять в более сложные структуры, добавляя операции уже над структурой в целом и правила доступа к отдельным элементам этой абстрактной структуры данных.

К таким абстрактным структурам данных относятся:

· векторы (конечные массивы);

· таблицы (матрицы), а в общем случае - многомерные массивы;

· динамические структуры:

Последовательности символов, чисел;

Очереди;

Деревья;

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

Заметим, что перечисленные структуры существуют независимо от их реализации при программировании. С этими структурами данных работали и в XVIII, и в XIX веках, когда еще не придумали вычислительную машину. Мы можем разрабатывать алгоритм в терминах абстрактной структуры данных, но для реализации алгоритма в конкретном языке программирования необходимо найти способ ее представления в терминах типов данных и операторов , поддерживаемых данным языком программирования (см. “Операторы языка программирования ”). Для компьютерного представления абстрактных структур используются структуры данных ,которые представляют собой набор переменных, возможно различных типов данных, объединенных определенным образом. Для конструирования таких структур, как вектор, таблица, строка, последовательность, в большинстве языков программирования присутствуют стандартные типы данных : одномерный массив, двухмерный массив, строка, файл (реже список) соответственно. Организацию остальных структур данных, в первую очередь динамических структур , размер которых меняется во время выполнения программы, программисту приходится осуществлять самостоятельно, используя базовые типы данных. Рассмотрим такие структуры подробнее.

Списки

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

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

Пример 1. Порядок следования записей фамилий читателей в компьютере библиотекаря определяет отношение “предыдущий–следующий”. Как правило, сами записи имеют дополнительное свойство - они упорядочены по алфавиту. Над этим списком реализованы операции добавления нового читателя и, при необходимости, удаления старого. Если к тому же ведутся записи выданных каждому читателю книг, то каждую такую запись удобно представлять опять же с помощью списка выданных книг.

Кольцевые списки - такая же структура, как и линейный список, но имеющая дополнительную связь между последним и первым элементом, то есть следующим за последним элементом является первый элемент.

В кольцевом списке в отличие от линейного все элементы равноправны (поскольку для каждого элемента определены и предыдущий, и следующий элементы). Выделение “первого” и “последнего” элементов в кольцевом списке весьма условно, так как собственно структура списка не имеет явно выделенных элементов !

Пример 2. Во многих играх дети используют считалочки, чтобы выбрать ведущего, разделиться на команды и т.п. Как правило, считалочки длинные, и дети (сами того не зная) организуют кольцевой список. Отношение “предыдущий–следующий” определяется тем, в какую сторону ведущий считает. Типичная операция в такой структуре - удаление элемента из списка с сохранением его кольцевой структуры.

Линейные списки, в которых операции вставки, удаления и доступа к значениями элементов выполняются только с крайними элементами (первым или последним), получили специальные названия.

Стек - частный случай линейного односвязного списка, для которого определены две операции: добавление элемента в вершину стека (перед первым элементом) и удаление элемента из вершины стека (удаление первого элемента).

Пример 3. Рассмотрим задачу определения сбалансированности скобок различных видов в арифметическом выражении. Например, требуется проанализировать, сбалансированы ли скобки в выражении, содержащем круглые и квадратные скобки: ? Для решения этой задачи будем использовать динамическую структуру данных стек . Приведем алгоритм решения этой задачи по шагам. Будем использовать следующие обозначения:

i - номер анализируемого символа;

n - количество символов в выражении.

1. i = 0.

2. i = i + 1.

3. Если i n , то переход на п. (4), иначе если стек пуст, то выдаем сообщение “скобки сбалансированы”, в противном случае выдаем сообщение “скобки не сбалансированы ”. Конец алгоритма.

4. Если i -й символ отличен от символов скобок, то переход на п. (2).

5. Если i -й символ равен “(” или “[”, то помещаем его в стек, переход на п. (2).

6. Если i -й символ равен “)”, то проверяем вершину стека: если в вершине стека находится “(”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “скобки не сбалансированы ”. Конец алгоритма.

7. Если i -й символ равен “]”, то проверяем вершину стека: если в вершине стека находится “[”, то извлекаем ее из стека; переход на п. (2), иначе выдаем сообщение “скобки не сбалансированы ”. Конец алгоритма.

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

Понятие очереди действительно очень близко к бытовому термину “очередь”. Очередь покупателей в магазине хорошо описывается в терминах этой структуры данных.

Деревья

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

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

Используются деревья и для определения выигрышной стратегии в играх (см. статью “Игры. Выигрышные стратегии ”), и для построения различных информационных моделей (см. “Информационные модели ”).

Особенно важную роль в информатике играют так называемые бинарные деревья .

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

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

Графы

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

В силу того, что с помощью графов можно описывать объекты произвольной структуры, графы являются основным средством для описания структур сложных объектов и функционирования систем. Например, для описания вычислительной сети, транспортной системы, иерархической структуры (дерево является одной из разновидностей графа). Блок-схемы алгоритмов (см. “Способы записи алгоритмов ”) также представляют собой графы.

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

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

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

Абстрактную структуру данных - граф - в программе можно представить несколькими способами, т.е. используя разные типы данных. Например, граф можно описывать с помощью списка ребер, задавая каждое ребро парой вершин и, при необходимости, весом. Наибольшее распространение получило табличное хранение графа (см. “Табличные модели ”), называемое также матрицей смежности , т.е. двухмерного массива, скажем, A , где для невзвешенного графа (или 1), если ребро между вершинами i и j существует, и (или 0) в противном случае. Для взвешенного графа A [i ][j ] равно весу соответствующего ребра, а отсутствие ребра в ряде задач удобно обозначать бесконечностью. Для неориентированных графов матрица смежности всегда симметрична относительно главной диагонали (i = j ). C помощью матрицы смежности легко проверить, существует ли в графе ребро, соединяющее вершину i с вершиной j . Основной же ее недостаток заключается в том, что матрица смежности требует, чтобы объем памяти был достаточен для хранения N 2 значений для графа, содержащего N вершин, даже если ребер в графе существенно меньше, чем N 2 .

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

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

Государственный образовательный стандарт предусматривает изучение различных структур данных как в базовом курсе основной школы, так и в старших классах. В курсе программирования основной школы в Примерной программе упоминаются в качестве обрабатываемых объектов цепочки символов (строки), числа, списки, деревья, графы. Однако в практических работах из данных сложной структуры упоминается только массив (см. статью “Операции с массивами ”). В основной школе остальные структуры, видимо, имеет смысл изучать в первую очередь при построении графических и других моделей (см. раздел IV энциклопедии).

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

Бинарное дерево также легко представить в памяти компьютера с помощью одномерного массива, при этом в первом элементе массива будет храниться корень дерева, а потомки узла дерева, хранящегося в i -м элементе массива, будут располагаться в 2i -м и (2i + 1)-м элементах соответственно. Если потомок у узла отсутствует, то соответствующий элемент будет равен, например, 0. Рекурсивная процедура обхода дерева t и печати его элементов в этом случае будет выглядеть так:

procedure order(i:integer);

if t[i] <> 0 then

О реализации списков и массивов с помощью динамических переменных можно прочитать, например, в классической книге Н.Вирта “Алгоритмы и структуры данных”.

В программу для профильной школы включены и алгоритмы на графах. В частности, упоминается поиск кратчайшего пути в графе. Для невзвешенного графа решать эту задачу можно, например, с использованием алгоритма “поиска в ширину”, когда сначала помечаются вершины графа, соединенные ребром с исходной вершиной, затем все вершины, соединенные с помеченными, и т.д. Для взвешенного графа чаще всего используют алгоритм Дийкстры (см., например, статью Е.В. Андреевой “Олимпиады по информатике. Пути к вершине”, “Информатика” № 8/2002). Знание таких алгоритмов необходимо для успешного решения олимпиадных задач по информатике. Так, на IV федеральном окружном этапе Всероссийской олимпиады по информатике 2007 г. предлагалась задача “Окопы и траншеи”, решение которой как раз и сводилось к поиску кратчайшего пути во взвешенном графе.

Данные, хранящиеся в памяти ЭВМ, представляют собой совокупность нулей и единиц (битов). Биты объединяются в последовательности: байты, слова и т.д. Каждому участку оперативной памяти, который может вместить один байт или слово, присваивается порядковый номер (адрес).

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

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

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

Некоторые структуры:

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

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

Такие структуры данных как массив или запись занимают в памяти ЭВМ постоянный объем, поэтому их называют статическими структурами. К статическим структурам относится также множество .

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

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

Рис. 1.1. Классификация типов данных

1.1.2.Обобщенные структуры или модели данных.

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

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

Любая модель данных должна содержать три компоненты:

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

2. набор допустимых операций , выполняемых на структуре данных. Модель данных предполагает, как минимум, наличие языка определения данных (ЯОД), описывающего структуру их хранения, и языка манипулирования данными (ЯМД), включающего операции извлечения и модификации данных.

3. ограничения целостности - механизм поддержания соответствия данных предметной области на основе формально описанных правил.

В процессе исторического развития в СУБД использовалось следующие модели данных:

· иерархическая,

· сетевая,

· реляционная.

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

1.2.Методы доступа к данным

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

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

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

Существуют два класса методов, реализующих доступ к данным по ключу:

· методы поиска по дереву,

· методы хеширования.

1.2.1.Методы поиска по дереву

Определение: Деревом называется конечное множество, состоящее из одного или более элементов, называемых узлами, таких, что:

1. между узлами имеет место отношение типа "исходный - порожденный";

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

3. все узлы за исключением корня имеют только один исходный; каждый узел может иметь несколько порожденных узлов;

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

Число порожденных отдельного узла (число поддеревьев данного корня) называется его степенью . Узел с нулевой степенью называют листом или концевым узлом. Максимальное значение степени всех узлов данного дерева называется степенью дерева .

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

Упорядоченное дерево, степень которого не больше 2 называется бинарным деревом. Бинарное дерево особенно часто используется при поиске в оперативной памяти. Алгоритм поиска: вначале аргумент поиска сравнивается с ключом, находящимся в корне. Если аргумент совпадает с ключом, поиск закончен, если же не совпадает, то в случае, когда аргумент оказывается меньше ключа, поиск продолжается в левом поддереве, а в случае, когда больше ключа - в правом поддереве. Увеличив уровень на 1, повторяют сравнение, считая текущий узел корнем.

Пример: Пусть дан список студентов, содержащий их фамилии и средний бал успеваемости (см. таблицу 1.1). В качестве ключа используется фамилия студента. Предположим, что все записи имеют фиксированную длину, тогда в качестве указателя можно использовать номер записи. Смещение записи в файле в этом случае будет вычисляться как ([номер_записи ] -1) * [длина_записи ] . Пусть аргумент поиска "Петров". На рисунке 1.2 показано одно из возможных для этого набора данных бинарное дерево поиска и путь поиска.

Рис. 1.2. Поиск по бинарному дереву

Заметим, что здесь используется следующее правило сравнения строковых переменных: считается, что значение символа соответствует его порядковому номеру в алфавите. Поэтому "И" меньше "К", а "К" меньше "С". Если текущие символы в сравниваемых строках совпадают, то сравниваются символы в следующих позициях.

Бинарные деревья особенно эффективны в случае, когда множество ключей заранее неизвестно, либо когда это множество интенсивно изменяется. Очевидно, что при переменном множестве ключей лучше иметь сбалансированное дерево .

Определение: Бинарное дерево называют сбалансированным (balanced ), если высота левого поддерева каждого узла отличается от высоты правого поддерева не более чем на 1.

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

Определение: В-деревом порядка n называется сильно ветвящееся дерево степени 2n+1, обладающее следующими свойствами:

1. Каждый узел, за исключением корня, содержит не менее n и не более 2n ключей.
2. Корень содержит не менее одного и не более 2n ключей.
3. Все листья расположены на одном уровне.
4. Каждый промежуточный узел содержит два списка: упорядоченный по возрастанию значений список ключей и соответствующий ему список указателей (для листовых узлов список указателей отсутствует).

Для такого дерева:

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

· при добавлении и изменении ключей все изменения ограничиваются, как правило, одним узлом.

Рис. 1.3.Сбалансированное дерево

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

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

R -дерево (R -Tree ) это индексная структура для доступа к пространственным данным, предложенная А. Гуттманом (Калифорнийский университет, Беркли). R-дерево допускает произвольное выполнение операций добавления, удаления и поиска данных без периодической переиндексации.

Для представления данных используются записи, каждая из которых имеет уникальный идентификатор (tuple-identifier ). В каждом концевом узле (листе) дерева содержится запись вида (I,tuple-identifier ) , где I - n -мерный параллелепипед, содержащий указатели на пространственные данные (его также называют minimal bounding rectangle , MBR), а каждый элемент в tuple-identifier содержит верхнюю и нижнюю границу параллелепипеда в соответствующем измерении.

Неконцевые узлы содержат записи вида (I, childnode-pointer ) , где I минимальный ограничивающий параллелепипед для MBR всех узлов, производных по отношению к данному. Childnode-pointer - это указатель на производные узлы.

Пусть M и m <= M/2 соответственно максимальное и мимимальное количество элементов, которое может быть размещено в узле. Тогда свойства R-дерева можно описать следующим образом:

· R-Tree является сильно сбалансированным деревом, т.е. все листья находятся на одном уровне.

· Корневой узел имеет, как минимум, двух потомков.

· Для каждого элемента (I, childnode-pointer ) в неконцевом узле I является наименьшим возможным параллелепипедом, т.е. содержит все параллелепипеды производных узлов.

· Каждый концевой узел (лист) содержит от m до M индексных записей.

· Для каждой индексной записи (I, tuple-identifier ) в концевом узле I является параллелепипедом, который содержит n -мерный объект данных, на который указывает tuple-identifier .

1.2.2.Хеширование

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

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