Структуры данных. Неформальный гайд

Тема 26. Структурирование информации в базах данных

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

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

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

Требования к базам данных

Итак, хорошо спроектированная база данных:

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

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

3.Обеспечивает естественное, легкое для восприятия структурирование информации. Качественное построение базы позволяет делать запросы к базе более “прозрачными” и легкими для понимания; следовательно, снижается вероятность внесения некорректных данных и улучшается качество сопровождения базы.

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

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

1.Определить информационные потребности базы данных.

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

3.Поставить в соответствие сущностям и характеристикам – таблицы и столбцы (поля) в нотации выбранной Вами СУБД (Paradox, dBase, FoxPro, Access, Clipper, InterBase, Sybase, Informix, Oracle и т.д.).

4.Определить атрибуты, которые уникальным образом идентифицируют каждый объект.

5.Выработать правила, которые будут устанавливать и поддерживать целостность данных.

6.Установить связи между объектами (таблицами и столбцами), провести нормализацию таблиц.

7.Спланировать вопросы надежности данных и, при необходимости, сохранения секретности информации.

Основные понятия, используемые в реляционных БД

В реляционной теории одним из главных является понятие отношения. Математически отношение определяется следующим образом. Пусть даны n множеств D1,D2,...,Dn. Тогда R есть отношение над этими множествами, если R есть множество упорядоченных наборов вида, где d1 - элемент из D1, d2 - элемент из D2, ..., dn - элемент из Dn. При этом наборы вида называются кортежами, а множества D1,D2,...,Dn - доменами. Каждый кортеж состоит из элементов, выбираемых из своих доменов. Эти элементы называются атрибутами, а их значения - значениями атрибутов. рис. a представляет нам графическое изображение отношения с разных точек зрения.

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

· отношение, таблица, файл (для локальных баз данных);

· кортеж, строка, запись;

· атрибут, столбец, поле.

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

Атрибут (или набор атрибутов), который может быть использован для однозначной идентификации конкретного кортежа (строки, записи), называется первичным ключом. Первичный ключ не должен иметь дополнительных атрибутов. Это значит, что если из первичного ключа исключить произвольный атрибут, оставшихся атрибутов будет недостаточно для однозначной идентификации отдельных кортежей. Для ускорения доступа по первичному ключу во всех системах управления базами данных (СУБД) имеется механизм, называемый индексированием. Грубо говоря, индекс представляет собой инвертированный древовидный список, указывающий на истинное местоположение записи для каждого первичного ключа. Естественно, в разных СУБД индексы реализованы по-разному (в локальных СУБД – как правило, в виде отдельных файлов), однако, принципы их организации одинаковы.

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

Для поддержания ссылочной целостности данных во многих СУБД имеется механизм так называемых внешних ключей. Смысл этого механизма состоит в том, что некоему атрибуту (или группе атрибутов) одного отношения назначается ссылка на первичный ключ другого отношения; тем самым закрепляются связи подчиненности между этими отношениями. При этом отношение, на первичный ключ которого ссылается внешний ключ другого отношения, называется master-отношением, или главным отношением; а отношение, от которого исходит ссылка, называется detail-отношением, или подчиненным отношением. После назначения такой ссылки СУБД имеет возможность автоматически отслеживать вопросы “ненарушения“ связей между отношениями, а именно:

· если Вы попытаетесь вставить в подчиненную таблицу запись, для внешнего ключа которой не существует соответствия в главной таблице (например, там нет еще записи с таким первичным ключом), СУБД сгенерирует ошибку;

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

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

Замечание. Существует два подхода к удалению и изменению записей из главной таблицы:

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

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

· если в главной таблице удалена запись, то в подчиненной таблице должны быть удалены все записи, ссылающиеся на удаляемую;

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

Операции реляционной алгебры

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

2.Объединение R=R1И R2;

3.Пересечение R=R1З R2

4.Вычитание R=R1–R2;

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

7.В результате получается отношение R, содержащее все попарные комбинации строк двух перемножаемых отношений R1 и R2. При этом если отношение R1 обладает арностью k1 и количеством строк s1, а отношение R2 – арностью k2 и количеством строк s2, то результирующее отношение R имеет арность k=k1+k2 и содержит в себе s=s1*s2 строк.

8.Проецирование на атрибуты R = ПРA1,…,An R1.

9.Здесь A1,…,An – атрибуты на которые происходит проецирование. В результате этой операции получается отношение, содержащее только указанные атрибуты исходного отношения. Количество строк в отношении при этом остается прежним.

10.Операция выборки R = ПРУСЛОВИЕ R1.

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

12.Операция соединения отношений по определенному условию.

Почему БД может быть плохой?

Приведем пример плохой БД. Пусть проектируется база “Питание”. Эту базу можно представить в виде одного отношения, представленного на рисунке.

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

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

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

3. Аномалии включения. В БД не может быть записан новый поставщик («Няринга», Вильнюс, Литва), если поставляемый им продукт (Огурцы) не используется ни в одном блюде. Можно, конечно, поместить неопределенные значения в столбцы Блюдо, Вид, Порций и Вес (г) для этого поставщика. Но если появится блюдо, в котором используется этот продукт, не забудем ли мы удалить строку с неопределенными значениями?

По аналогичным причинам нельзя ввести и новый продукт (например, Баклажаны), который предлагает существующий поставщик (например, "Полесье"). А как ввести новое блюдо, если в нем используется новый продукт (Крабы)?

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

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

В полученной БД все еще много повторяющихся данных, находящихся в связующих таблицах (Состав и Поставки). Следовательно, в данном варианте БД сохранилась потенциальная противоречивость: для изменения названия поставщика с «Полесье» на «Днепро» придется изменять не только строку таблицы Поставщики, но и множество строк таблицы Поставки. При этом не исключено, что в БД будут одновременно храниться: "Полесье", "Палесье", «Днепро», «Днипро» и другие варианты названий.

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

Нормализация таблиц

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

Процесс нормализации заключается в приведении таблиц в так называемые нормальные формы. Существует несколько видов нормальных форм: первая нормальная форма (1НФ), вторая нормальная форма (2НФ), третья нормальная форма (3НФ), нормальная форма Бойса-Кодда (НФБК), четвертая нормальная форма (4НФ), пятая нормальная форма (5НФ). С практической точки зрения, достаточно трех первых форм – следует учитывать время, необходимое системе для “соединения” таблиц при отображении их на экране. Поэтому мы ограничимся изучением процесса приведения отношений к первым трем формам.

Этот процесс включает:

· устранение повторяющихся групп (приведение к 1НФ);

· удаление частично зависимых атрибутов (приведение к 2НФ);

· удаление транзитивно зависимых атрибутов (приведение к 3НФ).

Приведение к первой нормальной форме

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

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

Приведение ко второй нормальной форме

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

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

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

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

Приведение к третьей нормальной форме

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

Таблица находится в третьей нормальной форме (3НФ), если она удовлетворяет определению 2НФ и не одно из ее неключевых полей не зависит функционально от любого другого неключевого поля.

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

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

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

• Линейные
  • Массив
  • Список
  • Связанный список
  • Очередь
  • Хэш-таблица

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

Линейные структуры данных

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

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

Линейный массив.
Адрес(элемент(index)) = размер_ячейки * index.

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

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

Связанный список.

Стек – это динамическая линейная структура данных, для которой определены всего две операции изменения набора элементов: добавление элемента в конец и удаление последнего элемента. Еще говорят, что стек реализует принцип LIFO (Last in, First Out) – последним пришел и первым ушел. Например, в ходе выполнения программного кода, вычислительная машина при необходимости вызвать процедуру или функцию сначала заносит указатель на место ее вызова в стек, чтобы при завершении выполнения ее кода корректно вернуться к следующей после точки вызова инструкции. Такая структура данных называется стеком вызовов подпрограмм.

Стек.

Очередь – очень похожая не стек, динамическая структура данных, с той лишь разницей, что она реализует принцип FIFO (First in, First out) – первым пришел и первым ушел. За примерами в реальной жизни, как понятно из названия, далеко ходить не надо. В программировании с помощью очередей, например, обрабатывают события пользовательского интерфейса, обращения клиентов к и прочие информационные запросы.

Очередь.

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

Иерархические структуры данных

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

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

• прямой или префиксный
  {узел, левое поддерево, правое поддерево};


• обратный или постфиксный
  {левое поддерево, правое поддерево, узел};


• симметричный или инфиксный
  {левое поддерево, узел, правое поддерево};

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

Двоичное (бинарное) дерево.

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

Иерархический список.

Сетевые структуры данных

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

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

Граф.

Ориентированный граф.

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

Оценка сложности алгоритмов

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

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

Асимптотическая оценка сложности обозначается греческой буквой Θ (тета).

f(n) = Θ(g(n)), если существуют c1, c2>0 и n0 такие, что c1*g(n)n0.

Функция g(n) является асимптотически точной оценкой сложности алгоритма - функции f(n), приведенное неравенство называется асимптотическим равенством, а само обозначение Θ символизирует множество функций, которые растут “так же быстро”, как и функция g(n) – т.е. с точностью до умножения на константу. Как следует из приведенного неравенства, оценка Θ являет собой одновременно и верхнюю и нижнюю оценки сложности. Не всегда есть возможность получить оценку в таком виде, поэтому верхнюю и нижнюю оценки иногда определяют отдельно.

Верхняя оценка сложности обозначается греческой буквой Ο (омикрон), и является множеством функций, которые растут не быстрее, чем g(n).

f(n)= Ο(g(n)), если существует c>0 и n0 такие, что 0n0.

Нижняя оценка сложности обозначается греческой буквой Ω (омега), и является множеством функций, которые растут не медленнее, чем g(n).

f(n)= Ω(g(n)), если существует c>0 и n0 такие, что 0n0.

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

Работа с линейными структурами данных

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

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

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

Личное дело № 16493, Сергеев Петр Михайлович, дата рождения 1 января 1976 г.; ГУд Na 16593, Петрова Анна Владимировна, дата рожд. 15 марта 1975 г.; Na личн.дела 16693, д.р. 14.04.76, Анохин Андрей Борисович.

Рис. 2.1. Неструктурированные данные

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

Рис. 2.2. Структурированные данные

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

Иерархическая структура данных. Иерархический тип структуры предполагает расположение частей или элементов целого в порядке от высшего к низшему. Объекты, связанные иерархическими отношениями, образуют ориентированный граф (перевернутое дерево), вид которого представлен на рис. 2.3. К основным понятиям иерархической структуры относятся: уровень, элемент (узел), связь. Узел - это совокупность атрибутов данных, описывающих некоторый объект. На схеме иерархического дерева узлы представляются вершинами графа. Каждый узел на более низком уровне связан только с одним узлом, находящимся на более высоком уровне. Такой узел называется порожденным. Иерархическое дерево имеет только одну вершину (корень дерева), не подчиненную никакой другой вершине и находящуюся на самом верхнем (первом) уровне. Зависимые (порожденные) узлы находятся на втором, третьем и т. д. уровнях. Количество деревьев в базе данных определяется числом корневых записей. К каждой записи базы данных существует только один (иерархический) путь от корневой записи. Например, как видно из рис. 2.3, для записи С4 путь проходит через записи А и ВЗ. В такой структуре связь имеет характер подчинения и направлена от исходного (родительского) узла к зависимому (порожденному).

Рис. 2.3. Графическое изображение иерархической структуры БД

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

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

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

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

Рис. 2.4. Пример иерархической структуры данных

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

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

Рис. 2.5. Графическое изображение сетевой структуры

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

Рис. 2.6. Пример сетевой структуры базы данных

ческая. Следовательно, в ней труднее организовать поиск нужных данных. Реальным примером использования такой структуры на практике является структура глобальной информационной сети, которая получила название WWW (World Wide Web), или «всемирная паутина». Именно сложность поиска информации в этой структуре вызвали появление специальных средств поиска, таких, как «поисковые машины» и «каталоги».

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

В ячейку таблицы помещается только один элемент данных;

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

Каждый столбец имеет уникальное имя;

Одинаковые строки в таблице отсутствуют;

Порядок следования строк и столбцов может быть произвольным.

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

Таблица 2.8. Пример реляционной таблицы

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

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

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

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

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

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

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

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

· символы;

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

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

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

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

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

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

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

Очереди;

Деревья;

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

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

1.1 Список Может всё то же самое, что и массив, но позволяет добавлять элементы в любое место, удалять элементы из любого места и получать текущее количество элементов.

1.2 Ассоциативный массив

1.3 Хеш-таблица - это обычный массив с необычной адресацией, задаваемой хеш-функцией. Лучший выбор, если не нужна сортировка информации, а только быстрый доступ к ней. Тратится дополнительная память.

преимущества:

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

недостатки:

• Итерация не в порядке возрастания ключей
• Необходимость «перехеширования» при увеличении числа хранимых объектов (?)
• нельзя реализовать быстро работающие дополнительные операции MIN, MAX и алгоритм обхода всех хранимых пар в порядке возрастания или убывания ключей (?)
• не поддерживает упорядоченности, и не сохраняет порядок следования элементов (?)
• возможность коллизий

общий вид описания структур:

Основное предназначение, описание

Поддерживаемые операции

Преимущества

Недостатки

Готовая реализация в языке программирования (название функции или класса)

условные обозначения

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

редактирование продолжается..