Классы коллекций общего назначения

Лабораторная работа №4

КОЛЛЕКЦИИ В ЯЗЫКЕ C#

 

1. Цель работы: изучение коллекций языка C#, их методов и практическое освоение их применения.

Домашнее задание и методические указания по его выполнению

 

Основные понятия

В С# под коллекцией понимается группа объектов. Пространство имен System.Collections содержит множество интерфейсов и классов, которые определяют и реализуют коллекции различных типов. Коллекции упрощают программирование, предлагая уже готовые решения для построения структур данных, разработка которых "с нуля" отличается большой трудоемкостью. Речь идет о встроенных коллекциях, которые поддерживают, например, функционирование стеков, очередей и хеш-таблиц. Коллекции пользуются большой популярностью у всех С#-программистов.

Основное достоинство коллекций состоит в том, что они стандартизируют способ обработки групп объектов в прикладных программах. Все коллекции разработаны на основе набора четко определенных интерфейсов. Ряд встроенных реализаций таких интерфейсов, как ArrayList, Hashtable, Stack и Queue, вы можете использовать "как есть". У каждого программиста также есть возможность реализовать собственную коллекцию, но в большинстве случаев достаточно встроенных.

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

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

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

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

Перечислитель обеспечивает стандартизованный способ поэлементного доступа к содержимому коллекции. Поскольку каждая коллекция должна реализовать интерфейс IEnumerable, к элементам любого класса коллекции можно получить доступ с помощью методов, определенных в интерфейсе IEnumerator. Следовательно, после внесения небольших изменений код, который позволяет циклически опрашивать коллекцию одного типа, можно успешно использовать для циклического опроса коллекции другого типа. Интересно отметить, что содержимое коллекции любого типа можно опросить с помощью нумератора, используемого в цикле foreach. И еще. Если вы знакомы со средствами С++-программирования, то вам будет интересно узнать, что С#-классы коллекций по сути аналогичны классам стандартной библиотеки шаблонов (Standard Template Library -— STL), определенной в C++. То, что в C++ называется контейнером, в С# именуется коллекцией. То же справедливо и для Java. Если вы знакомы с Java-средой Collections Framework, то очень легко освоите использование С#-коллекций.

 

Классы коллекций общего назначения

 

Классы общего назначения можно использовать для хранения объектов любого типа. Битовые предназначены для хранения битовой информации. Коллекции специального назначения разрабатываются для обработки данных конкретного типа. Этот раздел посвящен классам коллекций общего назначения. В таблице 2.2.1 представлены классы коллекций общего назначения.

 

Таблица 2.2.1 – Классы коллекций общего назначения

ArrayList	Динамический массив, т.е. массив который при необходимости может увеличивать свой размер
Hashtabie	Хеш-таблица для пар ключ/значение
Queue	Очередь, или список, действующий по принципу: первым прибыл — первым обслужен
SortedList	Отсортированный список пар ключ/значение
Stack	Стек, или список, действующий по принципу: первым прибыл — последним обслужен

 

Класс ArrayList

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

Класс ArrayList реализует интерфейсы ICollection, IList, IEnumerable и ICloneable. В классе ArrayList определены следующие конструкторы:

public ArrayList()

public ArrayList(ICollection с)

public ArrayList(int capacity)

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

Помимо методов, определенных в интерфейсах, которые реализует класс ArrayList, в нем определены и собственные методы. Коллекцию класса ArrayList можно отсортировать с помощью метода Sort(). В отсортированной коллекции можно эффективно выполнять поиск элементов, используя метод BinarySearch(). При необходимости содержимое ArrayList-коллекции можно реверсировать, вызвав метод Reverse(). Класс ArrayList поддерживает ряд методов, которые действуют в некотором диапазоне элементов коллекции. Например, вызвав метод insertRange(), можно вставить в ArrayList-массив другую коллекцию. С помощью метода RemoveRange() можно удалить из коллекции заданный диапазон элементов. А если нужно заменить элементы заданного диапазона одной коллекции элементами другой, используйте метод SetRange(). Сортировать можно не только всю коллекцию, но и заданный диапазон внутри нее. То же справедливо и для поиска.

По умолчанию коллекция класса ArrayList не синхронизирована. Чтобы поместить коллекцию в синхронизированную оболочку, вызовите метод Synchronized().

В таблице 2.2.1.1 представлены основные методы класса ArrayList.

 

Таблица 2.2.1.1 - основные методы класса ArrayList

public virtual void AddRange(ICollection с)	Добавляет элементы из коллекции с в конец вызывающей коллекции
public virtual int BinarySearch (object v)	В вызывающей коллекции выполняет поиск значения, заданного параметром v. Возвращает индекс найденного элемента. Если искомое значение не обнаружено, возвращает отрицательное значение. Вызывающий список должен быть отсортирован
public virtual int BinarySearch(object v, IComparer comp)	В вызывающей коллекции выполняет поиск значения, заданного параметром v, на основе метода сравнения объектов, заданного параметром comp. Возвращает индекс найденного элемента. Если искомое значение не обнаружено, возвращает отрицательное значение. Вызывающий список должен быть отсортирован
public virtual int BinarySearch(int startldx, int count, object v, IComparer comp)	В вызывающей коллекции выполняет поиск значения, заданного параметром v, на основе метода сравнения объектов, заданного параметром comp. Поиск начинается с элемента, индекс которого равен значению startldx, и включает count элементов. Метод возвращает индекс найденного элемента. Если искомое значение не обнаружено, возвращает отрицательное значение. Вызывающий список должен быть отсортирован
public virtual void CopyTo(Array ar, int startldx)	Копирует содержимое вызывающей коллекции, начиная с элемента, индекс которого равен значению startldx, в массив, заданный параметром а г. Приемный массив должен быть одномерным и совместимым по типу с элементами коллекции
public virtual void CopyTo(int srcldx, Array ar, int destldx, int count)	Копирует count элементов вызывающей коллекции, начиная с элемента, индекс которого равен значению srcidx, в массив, заданный параметром а г, начиная с элемента, индекс которого равен значению destldx. Приемный массив должен быть одномерным и совместимым по типу с элементами коллекции
public virtual ArrayList GetRange(int idx, int count)	Возвращает часть вызывающей коллекции типа ArrayList. Диапазон возвращаемой коллекции начинается с индекса idx и включает count элементов. Возвращаемый объект ссылается на те же элементы, что и вызывающий объект
public static ArrayList FixedSize(ArrayList ar)	Превращает коллекцию ar в ArrayList-массив с фиксированным размером и возвращает результат
public virtual void InsertRange(int startldx, ICollection c)	Вставляет элементы коллекции, заданной параметром с, в вызывающую коллекцию, начиная с индекса, заданного параметром startldx
public virtual int LastlndexOf(object v)	Возвращает индекс последнего вхождения объекта v в вызывающей коллекции. Если искомый объект не обнаружен, возвращает значение -1
public static ArrayList Readonly(ArrayList ar)	Превращает коллекцию ar в ArrayList-массив, предназначенный только для чтения, и возвращает результат
public virtual void ReraoveRange(int idx, int count)	Удаляет count элементов из вызывающей коллекции, начиная с элемента, индекс которого равен значению idx
public virtual void Reverse()	Располагает элементы вызывающей коллекции в обратном порядке
public virtual void Reverse(int startldx, int count)	Располагает в обратном порядке count элементов вызывающей коллекции, начиная с индекса startldx
public virtual void SetRange(int startldx, ICollection c)	Заменяет элементы вызывающей коллекции, начиная с индекса startldx, элементами коллекции, заданной параметром с
public virtual void Sort()	Сортирует коллекцию по возрастанию
public virtual void Sort(IComparer comp)	Сортирует вызывающую коллекцию на основе метода сравнения объектов, заданного параметром comp. Если параметр comp имеет нулевое значение, для каждого объекта используется стандартный метод сравнения
public virtual void Sort (int startidx, int endidx, icomparer comp)	Сортирует часть вызывающей коллекции на основе метода сравнения объектов, заданного параметром comp. Сортировка начинается с индекса startidx и заканчивается индексом endidx. Если параметр comp имеет нулевое значение, для каждого объекта используется стандартный метод сравнения
public static ArrayList Synchronized(ArrayList list)	Возвращает синхронизированную версию вызывающей коллекции
public virtual object [ ] ToArray ()	Возвращает массив, который содержит копии элементов вызывающего объекта
public virtual Array ToArray (Type type)	Возвращает массив, который содержит копии элементов вызывающего объекта. Тип элементов в этом массиве задается параметром type
public virtual void TrimToSize()	Устанавливает свойство Capacity равным значению свойства Count

 

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

 

// Демонстрация использования ArrayList-массива.

using System;

using System.Collections;

class ArrayListDemo {

public static void Main() {

// Создаем динамический массив.

ArrayList al = new ArrayListO;

Console.WriteLine("Начальная емкость: " +

al.Capacity);

Console.WriteLine("Начальное количество элементов:

al.Count);

Console.WriteLine();

Console.WriteLine("Добавляем 6 элементов.");

// Добавляем элементы в динамический массив.

al.Add(‘C’);

al.Add(‘A’);

al.Add(‘B’);

al.Add(‘D’);

al.Add(‘F’);

Console.WriteLine("Текущая емкость: " + al.Capacity);

Console.WriteLine("Количество элементов: " + al.Count);

// Отображаем массив, используя индексацию.

Console.Write("Текущее содержимое массива: ");

for(int i=0; i < al.Count; i++)

Console.Write (al[i] + " ");

Console.WriteLine("\n");

Console.WriteLine("Удаляем 2 элемента.");

// Удаляем элементы из динамического массива.

al.Remove(‘F’);

al.Remove(‘A’);

Console.WriteLine("Текущая емкость: " + al.Capacity);

Console.WriteLine("Количество элементов: " + al.Count);

// Для отображения массива используем цикл foreach.

Console.Write("Содержимое: ");

foreach(char с in al)

Console.Write(c + " ");

Console.WriteLine("\n");

Console.WriteLine("Добавляем еще 20 элементов.");

// Добавляем такое количество элементов в массив,

// которое заставит его увеличить свой размер.

for(int i=0; i < 20; i++)

al.Add((char)('a' + i));

Console.WriteLine("Текущая емкость: " +

al.Capacity);

Console.WriteLine(

"Количество элементов после добавления 20 новых: " + al.Count);

Console.Write("Содержимое: ");

foreach(char с in al)

Console.Write(с + " ");

Console.WriteLine("\n");

// Изменяем содержимое массива, используя индексацию.

Console.WriteLine("Изменяем первые три элемента.");

al[0] = ‘X’;

al[l] = ‘Y';

al[2] = ‘Z’;

Console.Write("Содержимое: ");

foreach(char с in al)

Console.Write(c + " ");

Console.WriteLine();

}

}

 

Результаты выполнения программы:

 

Начальная емкость: 16

Начальное количество элементов: 0

Добавляем 6 элементов.

Текущая емкость: 16

Количество элементов: 6

Текущее содержимое массива: С А Е В D F

Удаляем 2 элемента.

Текущая емкость: 16

Количество элементов: 4

Содержимое: С Е В D

Добавляем еще 20 элементов.

Текущая емкость: 32

Количество элементов после добавления 20 новых: 24

Содержимое: C E B D a b c d e f g h i j k l m n o p q r s t

Изменяем первые три элемента.

Содержимое: X Y Z D a b c d e f g h i j k l m n o p q r s t

 

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

Класс Hashtable

Класс Hashtable предназначен для создания коллекции, в которой для хранения объектов используется хеш-таблица. Возможно, многим известно, что в хеш-таблице для хранения информации используется механизм, именуемый хешированием (hashing). Суть хеширования состоит в том, что для определения уникального значения, которое называется хэш-кодом, используется информационное содержимое соответствующего ему ключа. Хэш-код затем используется в качестве индекса, по которому в таблице отыскиваются данные, соответствующие этому ключу. Преобразование ключа в хэш-код выполняется автоматически, т.е. сам хэш-код вы даже не увидите. Но преимущество хеширования — в том, что оно позволяет сохранять постоянным время выполнения таких операций, как поиск, считывание и запись данных, даже для больших объемов информации. Класс Hashtable реализует интерфейсы IDictionary, ICollection, IEnumerable, ISerializable, IDeserializationCallback и ICloneable. В классе Hashtable определено множество конструкторов, включая следующие (они используются чаще всего):

public Hashtable()

public Hashtable(IDictionary с)

public Hashtable(int capacity)

public Hashtable(int capacity, float fillRatio)

Первая форма позволяет создать стандартный объект класса Hashtable. Вторая для инициализации Hashtable-объекта использует элементы заданной коллекции c. Третья инициализирует емкость создаваемой хэш-таблицы значением capacity, а четвертая — как емкость (значением capacity), так и коэффициент заполнения (значением fillRatio). Значение коэффициента заполнения (также именуемого коэффициентом нагрузки), которое должно попадать в диапазон 0,1-1,0, определяет степень заполнения хеш-таблицы, после чего ее размер увеличивается. В частности, размер таблицы увеличится, когда количество элементов станет больше емкости таблицы, умноженной на ее коэффициент заполнения. Для конструкторов, которые в качестве параметра не принимают коэффициент заполнения, используется значение 1,0. В классе Hashtable помимо методов, определенных в реализованных им интерфейсах, также определены собственные методы. Наиболее употребимые из них перечислены в таблице 2.2.2.1. Чтобы определить, содержит ли Hashtable-коллекция заданный ключ, достаточно вызвать метод ContainsKey (). А чтобы узнать, хранится ли в интересующей вас хеш-таблице заданное значение, вызовите метод ContainsValue (). Для опроса элементов Hashtable-коллекции необходимо получить нумератор типа IDictionaryEnumerator, вызвав метод GetEnumerator (). Вспомните, что для опроса содержимого коллекции, в которой хранятся пары ключ/значение, используется именно класс IDictionaryEnumerator.

 

Таблица 2.2.2.1 – Собственные методы класса Hashtable

public virtual bool ContainsKey (object k)	Возвращает значение true, если в вызывающей Hashtable-коллекции содержится ключ, заданный параметром k. В противном случае возвращает значение false
public virtual bool ContainsValue (object v)	Возвращает значение true, если в вызывающей Hashtable-коллекции содержится значение, заданное параметром v. В противном случае возвращает значение false
public virtual IDictionaryEnumerator GetEnumerator()	Возвращает для вызывающей Hashtable-коллекции нумератоp типа IDictionaryEnumerator.
public static Hashtable Synchronized (Hashtable ht)	Возвращает синхронизированную версию вызывающей Hashtable-коллекции, переданной в параметре ht

 

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

public virtual ICollection Keys { get; }

public virtual ICollection Values { get; }

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

В классе Hashtable пары ключ/значение хранятся в форме структуры типа DictionaryEntry, но по большей части вас это не будет касаться, поскольку свойства и методы обрабатывают ключи и значения отдельно. Например, при добавлении элемента в Hashtable-коллекцию необходимо вызвать метод Add(), который принимает два отдельных аргумента: ключ и значение.

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

Рассмотрим пример, который демонстрирует использование Hashtable-коллекции:

 

// Демонстрация использования Hashtable-коллекции.

using System;

using System.Collections;

class HashtableDemo {

public static void Main() {

// Создаем хэш-таблицу.

Hashtable ht = new Hashtable();

// Добавляем элементы в хэш-таблицу.

ht.Add("здание", "жилое помещение");

ht.Add("автомобиль", "транспортное средство");

ht.Add("книга", "набор печатных слов");

ht.Add("яблоко", "съедобный фрукт");

// Добавлять элементы можно также с помощью индексатора,

ht["трактор"] = "сельскохозяйственная машина";

// Получаем коллекцию ключе*й.

ICollection с = ht.Keys;

// Используем ключи для получения значений,

foreach(string str in с)

Console.WriteLine(str + ": " + ht[str]);

}

}

 

Результаты выполнения этой программы таковы:

 

яблоко: съедобный фрукт

здание: жилое помещение

трактор: сельскохозяйственная машина

автомобиль: транспортное средство

книга: набор печатных слов

 

Как видно по приведенным результатам, пары ключ/значение хранятся отнюдь не в упорядоченном виде. Обратите внимание на то, как было получено и отображено содержимое хеш-таблицы ht. Во-первых, коллекция ключей считывается с помощью свойства Keys. Каждый ключ затем используется в качестве индекса хеш-таблицы ht, который позволяет найти и отобразить значение, соответствующее каждому ключу. Не забывайте, что индексатор, определенный в интерфейсе IDictionary и реализованный в классе Hashtable, использует ключ в роли индекса.

 

Класс SortedList

Класс SortedList предназначен для создания коллекции, которая хранит пары ключ/значение в упорядоченном виде, а именно отсортированы по ключу. Класс SortedList реализует интерфейсы IDictionary, ICollection, IEnumerable и ICloneable. В классе SortedList определено несколько конструкторов, включая следующие:

public SortedList()

public SortedList(IDictionary c)

public SortedList(int capacity)

public SortedList(IComparer comp)

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

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

В классе SortedList помимо методов, определенных в реализованных им интерфейсах, также определены собственные методы. Наиболее употребимые приведены в таблице 2.2.3.1. Чтобы определить, содержит ли SortedList-коллекция заданный ключ, достаточно вызвать метод ContainsKey(). А чтобы узнать, хранится ли в списке заданное значение, вызовите метод ContainsValue(). Для опроса элементов SortedList-коллекции необходимо получить нумератор типа IDictionaryEnumerator, вызвав метод GetEnumerator (). Вспомните, что для опроса содержимого коллекции, в которой хранятся пары ключ/значение, используется именно класс IDictionaryEnumerator. Синхронизированную версию SortedList-коллекции можно получить с помощью метода Synchronized().

 

Таблица 2.2.3.1 – Собственные методы класса SortedList

public virtual bool ContainsKey(object k)	Возвращает значение true, если в вызывающей SortedList-коллекции содержится ключ, заданный параметром k. В противном случае возвращает значение false
public virtual bool ContainsValue(object v)	Возвращает значение true, если в вызывающей SortedList-коллекции содержится значение, заданное параметром k. В противном случае возвращает значение false
public virtual object GetBylndex(int idx)	Возвращает значение, индекс которого задан параметром idx
public virtual IDictionaryEnumerator GetEnumerator()	Возвращает нумератор типа IDictionaryEnumerator для вызывающей SortedList-коллекции
public virtual object GetKeyUnt idx)	Возвращает ключ, индекс которого задан параметром idx
public virtual iList GetKeyList()	Возвращает iList-коллекцию ключей, хранимых в вызывающей SortedList-коллекции
public virtual IList GetValueList()	Возвращает iList-коллекцию значений, хранимых в вызывающей SortedList-коллекции
public virtual int IndexOfKey(object k)	Возвращает индекс ключа, заданного параметром к. Возвращает значение -1, если в списке нет заданного ключа
public virtual int IndexOfValue(object v)	Возвращает индекс первого вхождения значения, заданного параметром v. Возвращает -1, если в списке нет заданного ключа
public virtual void SetBylndex(int idx, object v)	Устанавливает значение по индексу, заданному параметром idx, равным значению, переданному в параметре v
public static SortedList Synchronized(SortedList sl)	Возвращает синхронизированную версию sortedList-коллекции, переданной в параметре sl
public virtual void TrimToSize()	Устанавливает свойство capacity равным значению свойства Count

 

Существуют различные способы установки и считывания ключа либо значения. Чтобы получить значение, связанное с заданным индексом, вызовите метод GetBylndex (), а чтобы установить значение, заданное индексом, — метод SetBylndex (). Получить ключ, связанный с заданным индексом, можно с помощью метода GetKey (). Для получения списка всех ключей используйте метод GetKeyList (), а для получения списка всех значений— метод GetValueList (). Получить индекс ключа можно с помощью метода IndexOf Key (), а индекс значения— с помощью метода IndexOf Value (). Класс SortedList также поддерживает индексатор, определенный интерфейсом iDictionary, благодаря чему можно устанавливать или считывать значение, заданное соответствующим ключом. В классе SortedList помимо свойств, определенных в реализованных им интерфейсах, определены два собственных свойства. Получить предназначенную только для чтения коллекцию ключей или значений, хранимых в SortedList-коллекции, можно с помощью таких свойств:

public virtual ICollection Keys { get; }

public virtual ICollection Values { get; }

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

 

// Демонстрация SortedList-коллекции.

using System;

using System.Collections;

class SLDemo {

public static void Main() {

// Создаем упорядоченную коллекцию типа SortedList.

SortedList si = new SortedList();

// Добавляем в список элементы.

sl.Add("здание", "жилое помещение");

sl.Add("автомобиль", "транспортное средство");

sl.Add("книга", "набор печатных слов");

sl.Add("яблоко", "съедобный фрукт");

// Добавлять элементы можно также с помощью индексатора,

sl["трактор"] = "сельскохозяйственная машина";

// Получаем коллекцию ключей.

ICollection с = sl.Keys;

// Используем ключи для получения значений.

Console.WriteLine(

"Содержимое списка, полученное с помощью " +

"индексатора.");

foreach(string str in с)

Console.WriteLine(str + ": " + sl[str]);

Console.WriteLine();

// Отображаем список, используя целочисленные индексы.

Console.WriteLine(

"Содержимое списка, полученное с помощью " +

"целочисленных индексов.");

for(int i=0; i<sl.Count; i++)

Console.WriteLine(sl.GetBylndex(i));

Console.WriteLine();

// Отображаем целочисленные индексы элементов списка.

Console.WriteLine(

"Целочисленные индексы элементов списка.");

foreach(string str in с)

Console.WriteLine(str + ": " + sl.IndexOfKey(str));

}

}

 

Результаты выполнения этой программы таковы:

 

Содержимое списка, полученное с помощью индексатора.

автомобиль: транспортное средство

здание: жилое помещение

книга: набор печатных слов

трактор: сельскохозяйственная машина

яблоко: съедобный фрукт

Содержимое списка, полученное с помощью целочисленных индексов.

транспортное средство

жилое помещение

набор печатных слов

сельскохозяйственная машина

съедобный фрукт

Целочисленные индексы элементов списка.

автомобиль: 0

здание: 1

книга: 2

трактор: 3

яблоко: 4

Класс Stack

Вероятно, большинству читателей известно, что стек представляет собой список, добавление и удаление элементов к которому осуществляется по принципу "последним пришел — первым обслужен" (last-in, first-out — LIFO). Чтобы понять, как работает стек, представьте себе груду тарелок на столе. Тарелку, поставленную на стол первой, можно будет взять лишь последней, т.е. когда будут сняты все поставленные сверху тарелки. Стек — наиболее востребованная структура данных в программировании. Ее часто используют в системном программном обеспечении, компиляторах и программах из области создания искусственного интеллекта (в частности, в сфере программирования с обратным слежением).

Класс коллекции, предназначенный для поддержки стека, называется Stack. Он реализует интерфейсы ICollection, IEnumerable и ICloneable. Стек — это динамическая коллекция, которая при необходимости увеличивается, чтобы принять для хранения новые элементы, причем каждый раз, когда стек должен расшириться, его емкость удваивается.

В классе stack определены следующие конструкторы:

public Stack()

public Stack(int capacity)

public Stack(ICollection c)

Первый конструктор предназначен для создания пустого стека с начальной емкостью, равной 10 элементам. Второй создает пустой стек с начальной емкостью, заданной параметром capacity. Третий конструктор служит для построения стека, который инициализируется элементами и емкостью коллекции, заданной параметром с. Помимо методов, определенных в интерфейсах, которые реализует класс stack, в нем определены также собственные методы, перечисленные в таблице 2.2.4.1. По описанию этих методов можно судить о том, как используется стек Чтобы поместить объект в вершину стека, вызовите метод Push(). Чтобы извлечь верхний элемент и удалить его из стека, используйте метод Pop(). Если при вызове метода Pop() окажется, что вызывающий стек пуст, генерируется исключение типа InvalidOperationException. Метод Peek() позволяет вернуть верхний элемент, не удаляя его из стека.

 

Таблица 2.2.4.1 – Собственные методы класса Stack

public virtual bool Contains(object v)	Возвращает значение true, если объект v содержится в вызывающем стеке. В противном случае возвращает значение false
public virtual void Clear()	Устанавливает свойство count равным нулю, тем самым эффективно очищая стек
public virtual object Peek()	Возвращает элемент, расположенный в вершине стека, но не удаляет его
public virtual object Pop()	Возвращает элемент, расположенный в вершине стека, и удаляет его
public virtual void Push(object v)	Помещает объект v в стек
public static Stack Synchronized(Stack stk)	Возвращает синхронизированную версию stack-списка, переданного в параметре stk
public virtual object[] ToArray()	Возвращает массив, который содержит копии элементов вызывающе- го стека

 

Рассмотрим пример создания стека и его использования: поместим в него несколько объектов класса Integer, а затем извлечем их.

 

// Демонстрация использования класса Stack.

using System;

using System.Collections;

class StackDemo {

static void showPush(Stack st, int a) {

st.Push(a);

Console.WriteLine(

"Помещаем в элемент стек: Push(" + а + ")"

Console.Write("Содержимое стека: ");

foreach(int i in st)

Console.Write(i + " ");

Console.WriteLine();

static void showPop(Stack st) {

Console.Write("Извлекаем элемент из стека: Pop -> ")

int a = (int) st.Pop();

Console.WriteLine(a);

Console.Write("Содержимое стека: ");

foreach(int i in st)

Console.Write(i + " ");

Console.WriteLine();

public static void Main() {

Stack st = new Stack();

foreach(int i in st)

Console.Write(i + " ");

Console.WriteLine();

showPush (st, 22);

showPush(st, 65);

showPush(st, 91);

showPop(st);

showPop(st);

showPop(st);

try {

showPop(st);

} catch (InvalidOperationException) {

Console.WriteLine("Стек пуст.");

}

}

}

 

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

 

Помещаем элемент в стек: Push(22)

Содержимое стека: 22

Помещаем элемент в стек: Push(65) ^

Содержимое стека: 65 22

Помещаем элемент в стек: Push(91)

Содержимое стека: 91 65 22

Извлекаем элемент из стека: Pop -> 91

Содержимое стека: 65 22

Извлекаем элемент из стека: Pop -> 65

Содержимое стека: 22

Извлекаем элемент из стека: Pop -> 22

Содержимое стека:

Извлекаем элемент из стека: Pop -> Стек пуст.

 

Класс Queue

Еще одной распространенной структурой данных является очередь. Добавление элементов в очередь и удаление их из нее осуществляется по принципу "первым пришел — первым обслужен" (first-in, first-out — FIFO). Другими словами, первый элемент, помещенный в очередь, первым же из нее и извлекается. Ну кто не сталкивался с очередями в реальной жизни? Например, каждому приходилось, вероятно, стоять в очереди к билетной кассе в кинотеатре или к кассе в супермаркете, чтобы оплатить покупку. В программировании очереди используются для организации таких механизмов, как выполнение нескольких процессов в системе и поддержка списка незаконченных транзакций (в системах ведения баз данных) или пакетов данных, полученных из Internet. Очереди также часто используются в области имитационного моделирования.

Класс коллекции, предназначенный для поддержки очереди, называется Queue. Он реализует интерфейсы iCollection, IEnumerable и ICloneable. Очередь — это динамическая коллекция, которая при необходимости увеличивается, чтобы принять для хранения новые элементы, причем каждый раз, когда такая необходимость возникает, текущий размер очереди умножается на коэффициент роста, который по умолчанию равен значению 2,0.

В классе Queue определены следующие конструкторы:

public Queue()

public Queue (int capacity)

public Queue (int capacity, float growFact)

public Queue (ICollection c)

Первый конструктор предназначен для создания пустой очереди с начальной емкостью, равной 32 элементам, и коэффициентом роста 2,0. Второй создает пустую очередь с начальной емкостью, заданной параметром capacity, и коэффициентом роста 2,0. Третий отличается от второго тем, что позволяет задать коэффициент роста посредством параметра growFact. Четвертый конструктор служит для создания очереди, которая инициализируется элементами и емкостью коллекции, заданной параметром с.

Помимо методов, определенных в интерфейсах, которые реализует класс Queue, в нем определены также собственные методы, перечисленные в таблице 2.2.5.1. О работе очереди можно получить представление по описанию этих методов. Чтобы поместить объект в очередь, вызовите метод Enqueue(). Чтобы извлечь верхний элемент и удалить его из очереди, используйте метод Dequeue(). Если при вызове метода Dequeue() окажется, что вызывающая очередь пуста, генерируется исключение типа InvalidOperationException. Метод Реек() позволяет вернуть следующий объект, не удаляя его из очереди.

 

Таблица 2.2.5.1 - Собственные методы класса Queue

public virtual bool Contains (object v)	Возвращает значение true, если объект v содержится в вызывающей очереди. В противном случае возвращает значение false
public virtual void clear ()	Устанавливает свойство Count равным нулю, тем самым эффективно очищая очередь
public virtual object Dequeue ()	Возвращает объект из начала вызывающей очереди, Возвращаемый объект из очереди удаляется
public virtual void Enqueue(object v)	Добавляет объект v в конец очереди
public virtual object Peek ()	Возвращает объект из начала вызывающей очереди, но не удаляет его
public static Queue Synchronized(Queue q)	Возвращает синхронизированную версию очереди, заданной параметром g
public virtual ob j ect [ ] тоАггау ()	Возвращает массив, который содержит копии элементов из вызывающей очереди
public virtual void TrimToSize()	Устанавливает свойство Capacity равным значению свойства Count

 

Рассмотрим пример, в котором демонстрируется использование класса Queue:

 

// Демонстрация класса Queue.

using System;

using System.Collections;

class QueueDemo {

static void showEnq(Queue q, int a) {

q.Enqueue(a);

Console.WriteLine(

"Помещаем элемент в очередь: Enqueue(" + а + ")");

Console.Write("Содержимое очереди: ");

foreach(int i in q)

Console.Write(i + " ");

Console.WriteLine();

static void showDeq(Queue q) {

Console.Write(

"Извлекаем элемент из очереди: Dequeue -> ");

int a = (int) q.Dequeue();

Console.WriteLine(a);

Console.Write("Содержимое очереди: ");

foreach(int i in q)

Console.Write(i + " ");

Console.WriteLine();

public static void Main() {

Queue q = new Queue();

foreach(int i in q)

Console.Write(i + " ");

Console.WriteLine();

showEnq(q, 22);

showEnq(q, 65);

showEnq(q, 91);

showDeq(q);

showDeq(q);

showDeq(q);

try {

showDeq(q);

} catch (InvalidOperationException) {

Console.WriteLine("Очередь пуста.");

}

}

}

 

Результаты выполнения программы таковы:

 

Помещаем элемент в очередь: Enqueue(22)

Содержимое очереди: 22

Помещаем элемент в очередь: Enqueue(65)

Содержимое очереди: 22 65

Помещаем элемент в очередь: Enqueue(91)

Содержимое очереди: 22 65 91

Извлекаем элемент из очереди: Dequeue -> 22

Содержимое очереди: 65 91

Извлекаем элемент из очереди: Dequeue -> 65

Содержимое очереди: 91

Извлекаем элемент из очереди: Dequeue -> 91

Содержимое очереди:

Извлекаем элемент из очереди: Dequeue -> Очередь пуста.

 

Лабораторное задание и методические указания по его выполнению

Составить программу в соответствии с вариантом. Составить отчёт.

 

Отчет должен содержать:

 

· Наименование и цель работы.

· Краткие теоретические сведения.

· Лиcтинг программы.

Варианты заданий

 

Вариант	Задание	Используемый класс
	Упорядочивание и расположение всех элементов массива в обратном порядке	ArrayList
	Замена элементов одной коллекции элементами другой и поиск объекта в коллекции	ArrayList
	Создание базы данных студентов группы. Осуществить функцию поиска по фамилиям.	Hashtable
	Создание базы данных автомобилей. Осуществить выдачу информации о необходимом автомобиле	Hashtable
	Создание базы данных студентов группы. Осуществить вывод первых n студентов в алфавитном порядке	SortedList
	Создание базы данных автомобилей. Осуществить вывод информации об авто в порядке возрастания количества цилиндров двигателя	SortedList
	Создание и отображение ленты новостей	Stack
	Создание базы товаров и цен. «Новинки» показываются в первую очередь	Stack
	Реализация алгоритма очистки оперативной памяти FIFO	Queue
	Моделирование буфера КЭШ-памяти процессора	Queue

 

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

 

1. Троелсен Э. С# и платформа.NET. Библиотека программиста. – СПб.: Питер, 2007 – 796с.:ил.

2. Агуров П.В. С#. Сборник рецептов. – СПб.: БХВ-Петербург, 2007 – 432с.: ил.