Структуры данных, коллекции и классы-прототипы

Абстрактные структуры данных

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

Стек — это частный случай однонаправленного списка, добавление элементов в который и выборка из которого выполняются с одного конца, называемого вершиной стека. Другие операции со стеком не определены. При выборке элемент исключается из стека. Говорят, что стек реализует принцип обслуживания LIF O (Last In — First Out, последним пришел — первым ушел). Стек проще всего представить себе как закрытую с одного конца узкую трубу, в которую бросают мячики. Достать первый брошенный мячик можно только после того, как вынуты все остальные. Стеки широко применяются в системном программном обеспечении, компиляторах, в различных рекурсивных алгоритмах.

Очередь — это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец, а выборка — из другого конца. Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIF O (First In — First Out, первым пришел — первым ушел). Очередь проще всего представить себе, постояв в ней час-другой. В программировании очереди применяются, например, в моделировании, диспетчеризации задач операционной системой, буферизованном вводе-выводе.

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

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

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

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

Пространство имен System.Collections

В пространстве имен System.Collections определены наборы стандартных коллекций и интерфейсов, которые реализованы в этих коллекциях. Пространство имен System.Collections.Specialized включает специализироные коллекции, например коллекцию строк StringCollection и хеш-таблицу строковыми ключами StringDictionary.

Классы-прототипы

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

Во вторую версию библиотеки.NET добавлены параметризованные коллекции для представления основных структур данных, применяющихся при создании программ, — стека, очереди, списка, словаря и т. д. Эти коллекции, расположенные в пространстве имен System.Collections.Generic, дублируют аналогичные коллекции пространства имен System.Collections, рассмотренные в разделе «Пространство имен System.CoIlections» (см. с. 295). В табл. 13.5 приводится соответствие между обычными и параметризованными коллекциями библиотеки.NET (параметры, определяющие типы данных, хранимых в коллекции, указаны в угловых скобках).

У коллекций, описанных в библиотеке.NET версий 1.0 и 1.1, есть два основных недостатка, обусловленных тем, что в них хранятся ссылки на тип object:

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

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

Параметром класса-прототипа является тип данных, с которым он работает. Это избавляет от перечисленных недостатков. В качестве примера рассмотрим применение универсального «двойника» класса ArrayLi st — класса List<T> — для хранения коллекции объектов классов Monster и Daemon.

Обобщенные методы

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

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

• описывать способы хранения и алгоритмы обработки данных независимо от типов данных;

• выполнять контроль типов во время компиляции, а не исполнения программы;

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

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

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

Частичные типы

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

Модификаторы доступа для всех частей типа должны быть согласованными. Если хотя бы одна из частей содержит модификатор abstract или sealed, класс считается соответственно абстрактным или бесплодным. Класс-прототип также может объявляться по частям, в этом случае во всех частях должны присутствовать одни и те же параметры типа с одними и теми же ограничениями. Если частичный тип является наследником нескольких интерфейсов, в каждой части не требуется перечислять все интерфейсы: обычно в одной части объявляется один интерфейс и описывается его реализация, в другой части — другой интерфейс и т. д. Набором базовых интерфейсов для типа, объявленного в нескольких частях, является объединение базовых интерфейсов, определенных в каждой части.

Обнуляемые типы

В программировании давно существует проблема, каким образом задать, что переменной не присвоено никакого значения. Эта проблема решается разными способами. Один из способов заключается в том, чтобы присвоить переменной какое-либо значение, не входящее в диапазон допустимых для нее. Например, если величина может принимать только положительные значения, ей присваивается -1. Ясно, что для многих случаев этот подход неприменим. Другой способ — хранение логического признака, по которому можно определить, присвоено ли переменной значение. Этот способ не может использоваться, например, для значений, возвращаемых из метода. В версии С# 2.0 указанная проблема решается введением типов специального вида, называемых обнуляемыми (nullable). Обнуляемый тип представляет собой структуру, хранящую наряду со значением величины (свойство Value) логический признак, по которому можно определить, было ли присвоено значение этой величине (свойство HasValue). Если значение величине было присвоено, свойство HasValue имеет значение true. Если значение величины равно null, свойство HasValue имеет значение false, а попытка получить значение через свойство Value вызывает генерацию исключения. Обнуляемый тип строится на основе базового типа.

Существуют явные и неявные преобразования из обнуляемых типов в обычные и обратно, при этом выполняется контроль возможности получения значения. Для величин обнуляемых типов определены операции отношения. Операции == и!= возвращают значение true, если обе величины имеют значение null. Естественно, что значение nul 1 считается не равным любому ненулевому значению. Операции <, >, <= и >= дают в результате false, если хотя бы один из операндов имеет значение nul 1. Арифметические операции с величинами обнуляемых типов дают в результате nul 1, если хотя бы один из операндов равен nul 1.