Структуры данных и оценка сложности алгоритмов. Общее понятие структуры данных

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

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

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

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

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

· символы;

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

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

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

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

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

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

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

Очереди;

Деревья;

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

Заметим, что перечисленные структуры существуют независимо от их реализации при программировании. С этими структурами данных работали и в 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.1

Васильев

Кузнецов


Тихомиров

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

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

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

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

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

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

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

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

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

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

Рис. 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 " - резать, измельчать). Имея такую функцию можно вычислить адрес записи в файле по заданному ключу поиска. В общем случае, ключевые данные, используемые для определения адреса записи, организуются в виде таблицы, называемой хеш-таблицей.

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

Структуры и типы данных. Массивы, деревья, списки, графы. Операции над данными.

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

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

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

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

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

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

Типичный набор операций над списком будет включать добавление, удале¬ние и поиск его элементов, вычисление длины списка, последовательную об¬работку элементов (итерацию) списка.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Дадим теперь более формально основное определение теории графов. Граф G есть упорядоченная пара (V,E), где V - непустое множество вершин, E - множество пар элементов множества V, пара элементов из V называется ребром. Упорядоченная пара элементов из V называется дугой. Если все пары в Е - упорядочены, то граф называется ориентированным.

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

Важным частным случаем графа является дерево.

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

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

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

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

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

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

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

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

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

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

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

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

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

Что включает в себя понятие структуры данных?

Этот термин может иметь несколько близких, но все же отличительных значений. Это:

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

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

Что формирует структуру?

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

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

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

Стоит отметить, что многие языки программирования обладают установленным типом модульности, что позволяет структурам с данными безопасно использоваться в различных приложениях. Яркими примерами являются языки Java, C# и C++. Сейчас классическая структура используемых данных представлена в стандартных библиотеках языков программирования или непосредственно она встроена уже в сам язык. К примеру, хэш-таблицы встроена в Lua, Python, Perl, Ruby, Tcl и другие. Широко применяется стандартная библиотека шаблонов в C++.

Сравниваем структуру в функциональном и императивном программировании

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

Фактически все структуры часто применяют на практике присваивание, которое в чисто функциональном стиле не используется.
Функциональные структуры - это гибкие системы. В императивном программировании старые версии просто заменяются на новые, а в функциональном все работает, как работало. Иными словами, в императивном программировании структуры являются эфемерными, а в функциональном они постоянные.

Что включает в себя структура?

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

Простейший массив подходит для частого обращения к установленным компонентам по индексам и их изменению, а удаление элементов из средины функционирует за принципом O(N)O(N). Если вам требуется удалить элементы, чтобы разрешить определенные задачи, то придется воспользоваться иной структурой. К примеру, бинарное дерево (std::set) позволяет делать это по O(logN)O(log⁡N), однако оно не поддерживает работу с индексами, выполняется исключительно поочередный обход элементов и их поиск по значению. Таким образом, можно сказать, что структура отличается операциями, что она способна выполнять, а также скоростью их проделывания. Для примера стоит рассмотреть простейшие структуры, что не дают выгоды в эффективности, но имеют точно установленный набор поддерживаемых операций.

Стек

Это один из типов структур данных, представленный в виде ограниченного простейшего массива. Классический стек поддерживает всего лишь три опции:

Внести элемент в стек (Сложность: O(1)O(1)).
Извлечение элемента из стека (Сложность: O(1)O(1)).
Проверка, пустой ли стек или нет (Сложность: O(1)O(1)).

Чтобы пояснить принцип работы стека, можно применить на практике аналогию с банкой печенья. Представьте, что на дне посудины лежит несколько печенюшек. Наверх вы можете положить еще пару кусочков или же вы можете, наоборот, взять одну печеньку сверху. Остальные печеньки будут закрыты верхними, и вы про них ничего не будете знать. Вот так дела обстоят и со стеком. Для описания понятия применяется аббревиатура LIFO (Last In, First Out), которая подчеркивает, что компонент, попавший внутрь стека последним, будет первым же и извлечен из него.

Очередь

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

Дек

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

Внести элемент в начало (Сложность: O(1)O(1)).
Извлечь компонент из начала (Сложность: O(1)O(1)).
Внесение элемента в конец (Сложность: O(1)O(1)).
Извлечение элемента из конца (Сложность: O(1)O(1)).
Проверка, пустой ли дек (Сложность: O(1)O(1)).

Списки

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

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

В этом списке элементы равноправны. Выделение первого и последнего - это условность.

Деревья

Это совокупность компонентов, что именуются узлами, в котором есть главный (один) компонент в виде корня, а все остальные разбиты на множество непересекающихся элементов. Каждое множество является деревом, а корень каждого древа - потомком корня дерева. Другими словами, все компоненты соединены между собой отношениями предок-потомок. Как результат можно наблюдать иерархическую структуру узлов. Если узлы не имеют потомка, то они называются листьями. Над деревом определены такие операции, как: добавление компонента и его удаление, обход, поиск компонента. Особую роль в информатике играют бинарные деревья. Что это такое? Это частный случай дерева, где каждый узел может иметь не больше пары потомков, являющихся корнями левого и правого поддерева. Если дополнительно для узлов дерева выполняется еще условие, что все значения компонентов левого поддерева меньше значений корня, а значения компонентов правого поддерева больше корня, то такое дерево именуется деревом бинарного поиска, и предназначается оно для быстрого нахождения элементов. Как же работает алгоритм поиска в таком случае? Искомое значение сравнивается со значением корня, и в зависимости от результата поиск либо завершается, либо продолжается, но исключительно в левом или правом поддереве. Общее число операций сравнения не станет превосходить высоту дерева (это наибольшее число компонентов на пути от корня до одного из листьев).

Графы

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

Графами можно описывать объекты какой угодно структуры, они являются главным средством для описания сложных структур и функционирования всех систем.

Детальней об абстрактной структуре

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

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

Анализ структур данных производится следующими объектами:

Целые и вещественные числа.
Логические значения.
Символы.

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

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

Векторы.
Динамические структуры.
Таблицы.
Многомерные массивы.
Графы.

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

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

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

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

Кому это необходимо знать?

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

Не забывайте: если говорите о той или иной структуре, то имейте в виду ее логическое представление, ведь физическое представление полностью сокрыто от «внешнего наблюдателя».

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

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