Типы и структуры данных

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

· символы;

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

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

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

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

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

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

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

Очереди;

Деревья;

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

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

• Перевод

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

Очередь

Итак, поздоровайтесь с Лупи!

Лупи обожает играть в хоккей со своей семьей. И под “игрой”, я подразумеваю:

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

Как насчет операций вставки и удаления?

Q = def insert(elem): q.append(elem) #добавляем элемент в конец очереди print q def delete(): q.pop(0) #удаляем нулевой элемент из очереди print q

Стек

После такой веселой игры в хоккей, Лупи делает для всех блинчики. Она кладет их в одну стопку.

Когда все блинчики готовы, Лупи подает их всей семье, один за одним.

Заметьте, что первый сделанный ею блинчик - будет подан последним. Это называется Стек . Последний элемент, добавленный в список - покинет его первым. Также эту структуру данных называют LIFO (Last In First Out).

Добавление и удаление элементов?

S = def push(elem): #Добавление элемента в стек - Пуш s.append(elem) print s def customPop(): #удаление элемента из стека - Поп s.pop(len(s)-1) print s

Куча

Вы когда-нибудь видели башню плотности?

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

Он займет место, в зависимости от своей плотности.

Примерно так работает Куча .

Куча - двоичное дерево. А это значит, что каждый родительский элемент имеет два дочерних. И хотя мы называем эту структуру данных кучей, но выражается она через обычный массив.
Также куча всегда имеет высоту logn, где n - количество элементов

На рисунке представлена куча типа max-heap, основанная на следующем правиле: дочерние элементы меньше родительского. Существуют также кучи min-heap, где дочерние элементы всегда больше родительского.

Несколько простых функций для работы с кучами:

Global heap global currSize def parent(i): #Получить индекс родителя для i-того элемента return i/2 def left(i): #Получить левый дочерний элемент от i-того return 2*i def right(i): #Получить правый дочерний элемент от i-того return (2*i + 1)

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

Алгоритм:

1. Добавляем элемент в самый низ кучи.
2. Сравниваем добавленный элемент с родительским; если порядок верный - останавливаемся.
3. Если нет - меняем элементы местами, и возвращаемся к предыдущему пункту.

Код:

Def swap(a, b): #меняем элемент с индексом a на элемент с индексом b temp = heap[a] heap[a] = heap[b] heap[b] = temp def insert(elem): global currSize index = len(heap) heap.append(elem) currSize += 1 par = parent(index) flag = 0 while flag != 1: if index == 1: #Дошли до корневого элемента flag = 1 elif heap > elem: #Если индекс корневого элемента больше индекса нашего элемента - наш элемент на своем месте flag = 1 else: #Меняем местами родительский элемент с нашим swap(par, index) index = par par = parent(index) print heap
Максимальное количество проходов цикла while равно высоте дерева, или logn, следовательно, трудоемкость алгоритма - O(logn).

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

MaxHeapify().

Алгоритм:

1. Заменить корневой элемент самым нижним.
2. Сравнить новый корневой элемент с дочерними. Если они в правильном порядке - остановиться.
3. Если нет - заменить корневой элемент на одного из дочерних (меньший для min-heap, больший для max-heap), и повторить шаг 2.

Def extractMax(): global currSize if currSize != 0: maxElem = heap heap = heap #Заменяем корневой элемент - последним heap.pop(currSize) #Удаляем последний элемент currSize -= 1 #Уменьшаем размер кучи maxHeapify(1) return maxElem def maxHeapify(index): global currSize lar = index l = left(index) r = right(index) #Вычисляем, какой из дочерних элементов больше; если он больше родительского - меняем местами if l <= currSize and heap[l] > heap: lar = l if r <= currSize and heap[r] > heap: lar = r if lar != index: swap(index, lar) maxHeapify(lar)
И вновь максимальное количество вызовов функции maxHeapify равно высоте дерева, или logn, а значит трудоемкость алгоритма - O(logn).

Делаем кучу из любого рандомного массива
Окей, есть два пути сделать это. Первый - поочередно вставлять каждый элемент в кучу. Это просто, но совершенно неэффективно. Трудоемкость алгоритма в этом случае будет O(nlogn), т.к. функция O(logn) будет выполняться n раз.

Более эффективный способ - применить функцию maxHeapify для ‘под-кучи ’, от (currSize/2) до первого элемента.

Сложность получится O(n), и доказательство этого утверждения, к сожалению, выходит за рамки данной статьи. Просто поймите, что элементы, находящиеся в части кучи от currSize/2 до currSize, не имеют потомков, и большинство образованных таким образом ‘под-куч’ будут высотой меньше, чем logn.

Def buildHeap(): global currSize for i in range(currSize/2, 0, -1): #третий агрумент в range() - шаг перебора, в данном случае определяет направление. print heap maxHeapify(i) currSize = len(heap)-1

Действительно, зачем это все?

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

Реализация до неприличия проста. Просто продолжайте последовательно извлекать из кучи максимальный (корневой) элемент, и записывайте его в массив, пока куча не опустеет.

Def heapSort(): for i in range(1, len(heap)): print heap heap.insert(len(heap)-i, extractMax()) #вставляем максимальный элемент в конец массива currSize = len(heap)-1
Чтобы обобщить все вышесказанное, я написала несколько строчек кода, содержащего функции для работы с кучей, а для фанатов ООП оформила все в виде класса .

Легко, не правда ли? А вот и празднующая Лупи!

Хеш

Лупи хочет научить своих детишек различать фигуры и цвета. Для этого она принесла домой огромное количество разноцветных фигур.

Через некоторое время черепашки окончательно запутались

Поэтому она достала еще одну игрушку, чтобы немного упростить процесс

Стало намного легче, ведь черепашки уже знали, что фигуры рассортированы по форме. А что, если мы пометим каждый столб?

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

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

Фио летовый тре угольник
ф+и+о+т+р+е = 22+10+16+20+18+6 = Столб 92

Кра сный пря моугольник
к+р+а+п+р+я = 12+18+1+17+18+33 = Столб 99

Мы знаем, что 6*33 = 198 возможных комбинаций, значит нам нужно 198 столбов.

Назовем эту формулу для вычисления номера столба - Хеш-функцией .

Код:
def hashFunc(piece): words = piece.split(" ") #разбиваем строку на слова colour = words shape = words poleNum = 0 for i in range(0, 3): poleNum += ord(colour[i]) - 96 poleNum += ord(shape[i]) - 96 return poleNum
(с кириллицей немного сложнее, но я оставил так для простоты . - прим.пер. )

Теперь, если нам нужно будет узнать, где хранится розовый квадрат, мы сможем вычислить:
hashFunc("розовый квадрат")

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

Ладно, но допустим мы ищем “кар амельный пря моугольник” (если, конечно, цвет “карамельный” существует).

HashFunc("карамельный прямоугольник")
вернет нам 99, что совпадает с номером для красного прямоугольника. Это называется “Коллизия ”. Для разрешения коллизии мы используем “Метод цепочек ”, подразумевающий, что каждый столб хранит список, в котором мы ищем нужную нам запись.

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

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

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

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

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

Переведено для Хабра запертым на

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Списки

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

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

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

Деревья

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

Графы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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