Анализ структур данных. Часть 1. Введение в структуры данных

Добро пожаловать! Вы читаете первую из шести статей в серии, посвященной структурам данных в .NET. В этой серии статей мы будем рассматривать различные структуры данных. Некоторые из них включены в базовую библиотеку классов .NET Framework Base Class Library, другие мы создадим сами. Структуры данных – это абстрактные структуры или классы, которые используются для организации данных и предоставляют различные операции над этими данными. Наиболее распространенной и общеизвестной структурой данных является массив (array), который содержит непрерывную совокупность элементов данных, к которым можно получить доступ посредством порядкового индекса.

Перед тем как углубиться в материал этой статьи, давайте взглянем на то, что ждет нас впереди. Если вы считаете, что какие-то важные темы отсутствуют в этом списке, автор будет рад, если вы сообщите ему о своих соображениях по адресу Этот e-mail защищен от спам-ботов. Для его просмотра в вашем браузере должна быть включена поддержка Java-script  Автор с удовольствием добавит ваши дополнения в соответствующий раздел или, если это будет необходимо, напишет седьмую статью к данной серии.

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

Во второй части мы более подробно исследуем класс ArrayList вместе с его близнецами: классами Queue (очередь) и Stack (стек). Как и ArrayList, классы Queue и Stack хранят непрерывную коллекцию данных и присутствуют в базовой библиотеке классов .NET Framework. Однако, в отличие от ArrayList, из которого мы можем получить произвольный элемент данных, очереди и стеки позволяют получать доступ к данным лишь в определенном последовательном порядке. Мы рассмотрим некоторые применения очередей и стеков, и увидим, как реализовать оба эти класса, расширяя класс ArrayList. После "возни" с очередями и стеками мы рассмотрим хэш-таблицы, которые, как и ArrayList, предоставляют прямой доступ к своим элементам, однако хранят данные индексированными по строковому ключу.

В то время, как ArrayList идеально подходит для хранения содержимого и предоставления прямого доступа к нему, он не является лучшим выбором, когда нам необходимо осуществлять поиск среди данных. В Части 3 мы изучим двоичное дерево поиска (binary search tree data structure), в котором поиск можно осуществлять гораздо эффективнеe, чем в ArrayList. В состав .NET Framework не входят встроенные классы, реализующие двоичные деревья, так что нам придется написать свои собственные.

Эффективность поиска по двоичному дереву зависит от порядка, в котором данные были вставлены в дерево. Если данные вставляются в отсортированном или почти отсортированном порядке, то выигрыш от использования двоичного дерева вместо ArrayList значительно падает. Для обхождения этого недостатка в Части 4 мы рассмотрим интересную рандомизированную структуру данных — слоеный список или skip-список (SkipList). Скип-списки обладают эффективностью поиска двоичного дерева, однако нечувствительны к упорядоченности вводимых данных.

В Части 5 мы обратим наше внимание на структуры данных, используемые для представления графов. Граф – это совокупность узлов (nodes) и ребер (edges), соединяющих различные узлы. Например, мы можем представить себе карту автодорог, как граф с городами в качестве узлов и шоссе между городами в качестве ребер. Очень много реальных практических задач можно абстрактно описать в терминах графов, что делает их часто используемой структурой данных.

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