Алгоритмизация и программирование

1. АЛГОРИТМИЗАЦИЯ И ПРОГРАММИРОВАНИЕ

2. Коллекции

Класс SortedList
Класс SortedList предназначен для создания коллекции, в которой пары
"ключ-значение" хранятся в порядке, отсортированном по значению
ключей. В классе SortedList реализуются интерфейсы IDictionary,
ICollection, IEnumerable и ICloneable.
В классе SortedList определено несколько конструкторов:
• public SortedList()
• public SortedList(IDictionary d)
• public SortedList(int initialCapacity)
• public SortedList(IComparer comparer)
В первом конструкторе создается пустая коллекция, первоначальная
емкость которой равна нулю.
Во втором конструкторе создается пустая коллекция типа SortedList,
которая инициализируется элементами из коллекции d. Ее
первоначальная емкость равна количеству указанных элементов.
В третьем конструкторе создается пустая коллекция типа SortedList,
первоначальный размер которой определяет емкость, задаваемая
параметром initialCapacity. Эта емкость соответствует размеру
2
базового массива, используемого для хранения элементов
коллекции.

3. Коллекции

В четвертой форме конструктора с помощью параметра comparer
указывается способ, используемый для сравнения объектов по
списку. В этой форме создается пустая коллекция, первоначальная
емкость которой равна нулю.
При добавлении новых элементов в список емкость коллекции типа
SortedList увеличивается автоматически по мере надобности.
Преимущество указания емкости коллекции типа SortedList при ее
создании заключается в снижении издержек на изменение размера
коллекции. Указывать емкость коллекции целесообразно лишь в том
случае, если заранее известно, сколько элементов требуется хранить
в ней.
В классе SortedList определяется ряд собственных методов, помимо тех,
что уже объявлены в интерфейсах, которые в нем реализуются.
Если требуется определить, содержится ли ключ в коллекции типа
SortedList, вызывается метод ContainsКеу().
Если требуется выяснить, хранится ли конкретное значение в коллекции
типа SortedList, вызывается метод ContainsValue().
Для перечисления содержимого коллекции типа SortedList служит метод
GetEnumerator(), возвращающий объект типа IDictionaryEnumerator.3

4. Коллекции

IDictionaryEnumerator - это перечислитель, используемый для
перечисления содержимого коллекции, в которой хранятся пары
"ключ-значение".
Метод
Описание
public virtual bool
ContainsKey(object key)
Возвращает логическое значение true, если в
вызывающей коллекции типа SortedList содержится
ключ key, а иначе — логическое значение false
public virtual bool
ContainsValue(object value)
Возвращает логическое значение true, если в
вызывающей коллекции типа SortedList содержится
значение value, а иначе — логическое значение false
public virtual object
GetBylndex(int index)
Возвращает значение, указываемое по индексу index
public virtual
IDictionaryEnumerator
GetEnumerator()
Возвращает для вызывающей коллекции типа SortedList
перечислитель типа IDictionaryEnumerator
public virtual object GetKey(int
Index)
Возвращает значение ключа, указываемое по индексу
index
public virtual IList GetKeyList()
Возвращает коллекцию типа SortedList с ключами,
хранящимися в вызывающей коллекции типа SortedList
4

5. Коллекции

Метод
Описание
public virtual IList
GetValueList()
Возвращает коллекцию типа SortedList со значениями,
хранящимися в вызывающей коллекции типа SortedList
public virtual int
IndexOfKey(object key)
Возвращает индекс ключа key. Если искомый ключ не
обнаружен, возвращается значение -1
public virtual int
IndexOfValue(object value)
Возвращает индекс первого вхождения значения value в
вызывающей коллекции. Если искомое значение не
обнаружено, возвращается значение -1
public virtual void
SetBylndex(int index, object
value)
Устанавливает значение по индексу Index равным
значению value
public static SortedList
Synchronized(SortedList list)
Возвращает синхронизированный вариант коллекции
типа SortedList, передаваемой в качестве параметра list
public virtual void TrimToSize()
Устанавливает значение свойства Capacity равным
значению свойства Count
5

6. Коллекции

Ключ или значение можно получить разными способами.
Для получения значения по указанному индексу служит метод
GetByIndex(), а для установки значения по указанному индексу метод SetByIndex().
Для извлечения ключа по указанному индексу вызывается метод
GetKey(), а для получения списка ключей по указанному индексу метод GetKeyList().
Для получения списка всех значений из коллекции служит метод
GetValueList(). Для получения индекса ключа вызывается метод
IndexOfKey(), а для получения индекса значения - метод
IndexOfValue().
Также поддерживается индексатор, определяемый в интерфейсе
IDictionary и позволяющий устанавливать и получать значение по
заданному ключу.
В классе SortedList доступны также открытые свойства, определенные
в тех интерфейсах, которые в нем реализуются.
Как и в классе Hashtable, в данном классе имеются свойства Keys и
Values, с их помощью можно получить доступную только для чтения
6
коллекцию ключей или значений из коллекции типа SortedList.

7. Коллекции

Эти свойства определяются в интерфейсе IDictionary следующим
образом.
• public virtual ICollection Keys { get; }
• public virtual ICollection Values { get; }
Порядок следования ключей и значений отражает порядок их
расположения в коллекции типа SortedList.
Аналогично коллекции типа Hashtable, пары "ключ-значение"
сохраняются в коллекции типа SortedList в форме структуры типа
DictionaryEntry, но доступ к ключам и значениям осуществляется по
отдельности с помощью методов и свойств, определенных в классе
SortedList.
В примере программы демонстрируется применение класса SortedList.
Это
переработанный
и
расширенный
вариант
примера,
демонстрировавшего применение класса Hashtable, вместо которого
теперь используется класс SortedList. В результат выполнения
программы, список полученных значений будет отсортированным по
заданному ключу.
7

8. Коллекции

ПРИМЕР.
using System;
using System.Collections;
class SLDemo {
static void Main() {
// Создать отсортированный список.
SortedList sl = new SortedList();
// Добавить элементы в список.
sl.Add("здание", "жилое помещение");
sl.Add("автомашина", "транспортное средство");
sl.Add("книга", "набор печатных слов");
sl.Add("яблоко", "съедобный плод");
// Добавить элементы с помощью индексатора,
sl["трактор"] = "сельскохозяйственная машина";
// Получить коллекцию ключей.
ICollection с = sl.Keys;
8

9. Коллекции

ПРИМЕР.
// Использовать ключи для получения значений.
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.GetByIndex(i));
Console.WriteLine();
// Показать целочисленные индексы элементов списка.
Console.WriteLine("Целочисленные индексы элементов списка.");
foreach(string str in с)
Console.WriteLine(str + ": " + sl.IndexOfKey (str));
}}
9

10. Коллекции

10

11. Коллекции

Класс Stack
Стек представляет собой список, действующий по принципу "первым
пришел - последним обслужен". Стек относится к одним из самых
важных структур данных в вычислительной технике. Он применяется
в системном программном обеспечении, компиляторах, а также в
программах отслеживания в обратном порядке на основе
искусственного интеллекта.
Класс коллекции, поддерживающий стек, носит название Stack. В нем
реализуются интерфейсы ICollection, IEnumerable и ICloneable. Этот
класс создает динамическую коллекцию, которая расширяется по
мере потребности хранить в ней вводимые элементы. Всякий раз,
когда требуется расширить такую коллекцию, ее емкость
увеличивается вдвое.
В классе Stack определяются следующие конструкторы.
• public Stack()
• public Stack(int initialCapacity)
• public Stack(ICollection col)
11

12. Коллекции

В первой форме конструктора создается пустой стек, во второй форме пустой стек, первоначальный размер которого определяет
первоначальная емкость, задаваемая параметром initialCapacity, и в
третьей форме - стек, содержащий элементы указываемой коллекции
col. Его первоначальная емкость равна количеству указанных
элементов.
В классе Stack определяется ряд собственных методов, которые в нем
реализуются.
Для того чтобы поместить объект на вершине стека, вызывается метод
Push(). А для того чтобы извлечь и удалить объект из вершины стека,
вызывается метод Pop().
Если объект требуется только извлечь, но не удалить из вершины стека,
то вызывается метод Рееk().
Если вызвать метод Pop() или Рееk(), когда вызывающий стек пуст, то
сгенерируется исключение InvalidOperationException.
12

13. Коллекции

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

14. Коллекции

ПРИМЕР.
В примере создается стек, в который помещается несколько целых
значений, а затем они извлекаются обратно из стека.
// Продемонстрировать применение класса Stack.
using System;
using System.Collections;
class StackDemo {
static void ShowPush(Stack st, int a) {
st.Push(a);
Console.WriteLine("Поместить в стек: Push(" + a + ")");
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();
14
Console.WriteLine(a);

15. Коллекции

ПРИМЕР.
Console.Write("Содержимое стека: ");
foreach(int i in st)
Console.Write(i + " ");
Console.WriteLine();
}
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);
15

16. Коллекции

ПРИМЕР.
try {
ShowPop(st);
}
catch (InvalidOperationException) {
Console.WriteLine("Стек пуст.");
}
}
}
16

17. Коллекции

Класс Queue
Еще одной структурой данных является очередь, действующая по
принципу: первым пришел - первым обслужен. Это означает, что
первым из очереди извлекается элемент, помещенный в нее первым.
В программировании очереди применяются для хранения таких
элементов, как процессы, выполняющиеся в данный момент в
системе, списки приостановленных транзакций в базе данных или
пакеты данных, полученные по Интернету. Кроме того, очереди
нередко применяются в области имитационного моделирования.
Класс коллекции, поддерживающий очередь, носит название Queue. В
нем реализуются интерфейсы ICollection, IEnumerable и ICloneable.
Этот класс создает динамическую коллекцию, которая расширяется,
если в ней необходимо хранить вводимые элементы. Так, если в
очереди требуется свободное место, ее размер увеличивается на
коэффициент роста, который по умолчанию равен 2,0.
В классе Queue определяются приведенные ниже конструкторы.
• public Queue()
• public Queue (int capacity)
17
• public Queue (int capacity, float growFactor)
• public Queue (ICollection col)

18. Коллекции

В
первой форме конструктора создается пустая очередь с
выбираемыми по умолчанию емкостью и коэффициентом роста 2,0.
Во второй форме создается пустая очередь, первоначальный размер
которой определяет емкость, задаваемая параметром сараcity, а
коэффициент роста по умолчанию выбирается для нее равным 2,0.
В третьей форме допускается указывать не только емкость (в качестве
параметра capacity), но и коэффициент роста создаваемой очереди
(в качестве параметра growFactor в пределах от 1,0 до 10,0).
В четвертой форме создается очередь, состоящая из элементов
указываемой коллекции col. Ее первоначальная емкость равна
количеству указанных элементов, а коэффициент роста по
умолчанию выбирается для нее равным 2,0.
В классе Queue определяется ряд собственных методов, которые в нем
реализуются.
Для того чтобы поместить объект в очередь, вызывается метод
Enqueue().
Если требуется извлечь и удалить первый объект из начала очереди, то
вызывается метод Dequeue().
18
Если требуется извлечь, но не удалять следующий объект из очереди,
то вызывается метод Рееk().

19. Коллекции

Если методы Dequeue() и Рееk() вызываются, когда очередь пуста, то
генерируется исключение InvalidOperationException.
Метод
Описание
public virtual void Clear()
Устанавливает свойство Count равным нулю, очищая, по
существу, очередь
public virtual bool Contains(object obj)
Возвращает логическое значение true, если объект obj
содержится в вызывающей очереди, а иначе —
логическое значение false
public virtual object Dequeue()
Возвращает объект из начала вызывающей очереди.
Возвращаемый объект удаляется из очереди
public virtual void Enqueue(object obj)
Добавляет объект obj в конец очереди
public virtual object Peek()
Возвращает объект из начала вызывающей очереди, но
не удаляет его
public static Queue Synchronized(Queue
queue)
Возвращает синхронизированный вариант коллекции
типа Queue, передаваемой в качестве параметра queue
public virtual object[] ToArray()
Возвращает массив, который содержит копии элементов
из вызывающей очереди
public virtual void TrimToSize()
Устанавливает значение свойства Capacity равным
значению свойства Count
19

20. Коллекции

ПРИМЕР.
// Продемонстрировать применение класса Queue.
using System;
using System.Collections;
class QueueDemo {
static void ShowEnq(Queue q, int a) {
q.Enqueue(a);
Console.WriteLine("Поместить в очередь: Enqueue(" + a + ")");
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);
20

21. Коллекции

ПРИМЕР.
Console.Write("Содержимое очереди: ");
foreach(int i in q)
Console.Write(i + " ");
Console.WriteLine();
}
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);
21

22. Коллекции

ПРИМЕР.
try {
ShowDeq (q);
}
catch (InvalidOperationException) {
Console.WriteLine("Очередь пуста.");
}
}
}
22

23. Коллекции

Хранение отдельных битов в классе коллекции BitArray
Класс BitArray служит для хранения отдельных битов в коллекции. Так
как в коллекции этого класса хранятся биты, а не объекты, то своими
возможностями он отличается от классов других коллекций.
В классе BitArray реализуются интерфейсы ICollection и IEnumerable как
основополагающие элементы поддержки всех типов коллекций.
Кроме того, в классе BitArray реализуется интерфейс ICloneable.
В классе BitArray определено несколько конструкторов. Так, с помощью
приведенного ниже конструктора можно сконструировать объект типа
BitArray из массива логических значений.
public BitArray(bool[] values)
В данном случае каждый элемент массива values становится
отдельным битом в коллекции. Это означает, что каждому элементу
массива values соответствует отдельный бит в коллекции. Порядок
расположения элементов в массиве values сохраняется и в
коллекции соответствующих им битов.
Коллекцию типа BitArray можно также составить из массива байтов,
используя следующий конструктор.
23

24. Коллекции

public BitArray(byte[] bytes)
Битами в коллекции становится уже целый их набор из массива bytes,
при чем элемент bytes[0] обозначает первые 8 битов, элемент
bytes[1] - вторые 8 битов и т.д. Аналогично, коллекцию типа BitArray
можно составить из массива целочисленных значений, используя
приведенный ниже конструктор.
public BitArray(int[ ] values)
В данном случае элемент values[0] обозначает первые 32 бита, элемент
values[1] - вторые 32 бита и т.д.
Можно составить коллекцию типа BitArray, указав ее конкретный размер:
public BitArray(int length)
где length обозначает количество битов в коллекции, которые
инициализируются логическим значением false.
В приведенном ниже конструкторе можно указать не только размер
коллекции, но и первоначальное значение составляющих ее битов.
public BitArray(int length, bool defaultValue)
В данном случае все биты в коллекции инициализируются значением
defaultValue, передаваемым конструктору в качестве параметра.
24

25. Коллекции

Новую коллекцию типа BitArray можно создать из уже существующей,
используя следующий конструктор.
public BitArray(BitArray bits)
Вновь сконструированный объект будет содержать такое же количество
битов, как и в указываемой коллекции bits, а в остальном это будут
две совершенно разные коллекции.
Коллекции типа BitArray подлежат индексированию. По каждому индексу
указывается отдельный бит в коллекции, нулевой индекс обозначает
младший бит. В классе BitArray определяется ряд собственных
методов, которые в нем реализуются.
В классе BitArray не поддерживается метод Synchronized().
25

26. Коллекции

Метод
Описание
public BitArray And(BitArray
value)
Выполняет операцию логического умножения И битов
вызывающего объекта и коллекции value. Возвращает
коллекцию типа BitArray, содержащую результат
public bool Get(int index)
Возвращает значение бита, указываемого по индексу
index
public BitArray Not()
Выполняет операцию поразрядного логического
отрицания НЕ битов вызывающей коллекции и
возвращает коллекцию типа BitArray, содержащую
результат
public BitArray Or(BitArray
value)
Выполняет операцию логического сложения ИЛИ битов
вызывающего объекта и коллекции value. Возвращает
коллекцию типа BitArray, содержащую результат
public void Set(int index, bool
value)
Устанавливает бит, указываемый по индексу Index,
равным значению value
public void SetAll(bool value)
Устанавливает все биты равными значению value
public BitArray Xor(BitArray
value)
Выполняет логическую операцию исключающее ИЛИ над
битами вызывающего объекта и коллекции value.
Возвращает коллекцию типа BitArray, содержащую
26
результат

27. Коллекции

В классе BitArray определяется собственное свойство, помимо тех, что
указаны в интерфейсах, которые в нем реализуются.
public int Length { get; set; }
Свойство Length позволяет установить или получить количество битов в
коллекции. Следовательно, оно возвращает такое же значение, как и
стандартное свойство Count, определяемое для всех коллекций. В
отличие от свойства Count, свойство Length доступно не только для
чтения, но и для записи, а значит, с его помощью можно изменить
размер коллекции типа BitArray. Так, при сокращении коллекции
типа BitArray лишние биты усекаются, начиная со старшего разряда.
А при расширении коллекции типа BitArray дополнительные биты,
имеющие логическое значение false, вводятся в коллекцию, начиная
с того же старшего разряда.
В классе BitArray определяется следующий индексатор.
public bool this[int index] { get; set; }
С помощью этого индексатора можно получать или устанавливать
значение элемента.
27

28. Коллекции

ПРИМЕР.
using System;
using System.Collections;
class BADemo {
public static void ShowBits(string rem,
BitArray bits) {
Console.WriteLine(rem);
for(int i=0; i < bits.Count; i++)
Console.Write("{0, -6} ", bits[i]);
Console.WriteLine("\n");
}
static void Main() {
BitArray bа = new BitArray(8);
byte[] b = { 67 };
BitArray bа2 = new BitArray(b);
ShowBits("Исходное содержимое коллекции ba:", bа);
bа = bа.Not();
ShowBits("Содержимое коллекции bа после логической операции
28
NOT:", bа);

29. Коллекции

ПРИМЕР.
ShowBits("Содержимое коллекции bа2:", bа2);
}
}
29

30. Коллекции

Специальные коллекции
В среде .NET Framework предусмотрен ряд специальных коллекций.
Классы этих необобщенных коллекций определены в пространстве
имен System. Collections.Specialized и перечислены ниже.
Класс специальной
коллекции
Описание
CollectionsUtil
Содержит фабричные методы для создания коллекций
HybridDictionary
Предназначен для коллекций, в которых для хранения небольшого количества
пар “ключ-значение" используется класс ListDictionary. При превышении
коллекцией определенного размера автоматически используется класс
Hashtable для хранения ее элементов
ListDictionary
Предназначен для коллекций, в которых для хранения пар “ключ-значение”
используется связный список. Такие коллекции рекомендуются только для
хранения небольшого количества элементов
NameValueCollection
Предназначен для отсортированных коллекций, в которых хранятся пары
“ключ-значение”, причем и ключ, и значение относятся к типу string
OrderedDictionary
Предназначен для коллекций, в которых хранятся индексируемые пары “ключзначение”
StringCollection
Предназначен для коллекций, оптимизированных для хранения символьных
строк
StringDictionary
30
Предназначен для хеш-таблиц, в которых хранятся пары “ключ-значение”,
причем и ключ, и значение относятся к типу string

31. Коллекции

Обобщенные коллекции
Обобщенные коллекции объявляются в пространстве имен System.
Collections.Generic. Как правило, классы обобщенных коллекций
являются не более чем обобщенными эквивалентами классов
необобщенных коллекций.
Например, в классе обобщенной коллекции LinkedList реализуется
двунаправленный список, тогда как в необобщенном эквиваленте его
не существует.
В некоторых случаях одни и те же функции существуют параллельно в
классах обобщенных и необобщенных коллекций, хотя и под
разными именами. Так, обобщенный вариант класса ArrayList
называется List, а обобщенный вариант класса HashTable - Dictionary.
Конкретное
содержимое
различных
интерфейсов
и
классов
реорганизуется с минимальными изменениями для переноса
некоторых функций из одного интерфейса в другой.
Как правило, обобщенные коллекции действуют по тому же принципу,
что и не обобщенные, за исключением того, что обобщенные
коллекции типизированы.
31

32. Коллекции

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

33. Коллекции

Класс
Описание
Dictionary<Tkey, TValue>
Сохраняет пары “ключ-значение". Обеспечивает такие же
функциональные возможности, как и необобщенный
класс Hashtable
HashSet<T>
Сохраняет ряд уникальных значений, используя хештаблицу
LinkedList<T>
Сохраняет элементы в двунаправленном списке
List<T>
Создает динамический массив. Обеспечивает такие же
функциональные возможности, как и необобщенный
класс ArrayList
Queue<T>
Создает очередь. Обеспечивает такие же
функциональные возможности, как и необобщенный
класс Queue
SortedDictionary<TKey, TValue>
Создает отсортированный список из пар “ключ-значение”
SortedList<TKey, TValue>
Создает отсортированный список из пар "ключ-значение”.
Обеспечивает такие же функциональные возможности,
как и необобщенный класс SortedList
SortedSet<T>
Создает отсортированное множество
Stack<T>
33
Создает стек. Обеспечивает такие же функциональные
возможности, как и необобщенный класс Stack

34. Коллекции

Класс List
В классе List<T> реализуется обобщенный динамический массив. В
этом классе реализуются интерфейсы ICollection, ICollection<T>, IList,
IList<T>, IEnumerable и IEnumerable<T>. У класса List<T> имеются
следующие конструкторы.
• public List()
• public List(IEnumerable<T> collection)
• public List(int capacity)
Первый конструктор создает пустую коллекцию класса List с
выбираемой по умолчанию первоначальной емкостью.
Второй конструктор создает коллекцию типа List с количеством
инициализируемых элементов, которое определяется параметром
collection и равно первоначальной емкости массива.
Третий конструктор создает коллекцию типа List, имеющую
первоначальную емкость, задаваемую параметром capacity. В
данном случае емкость обозначает размер базового массива,
используемого для хранения элементов коллекции. Емкость
коллекции, создаваемой в виде динамического массива, может
34
увеличиваться автоматически по мере добавления в нее элементов.

35. Коллекции

В классе List<T> определяется ряд собственных методов, которые в нем
реализуются.
Метод
Описание
public virtual void
AddRange(Icollection
collection)
Добавляет элементы из коллекции
вызывающей коллекции типа ArrayList
public virtual int
BinarySearch(T item)
Выполняет поиск в вызывающей коллекции значения,
задаваемого параметром item. Возвращает индекс совпавшего
элемента. Если искомое значение не найдено, возвращается
отрицательное значение. Вызывающий список должен быть
отсортирован
public int BinarySearch(Т
item, IComparer<T>
comparer)
Выполняет поиск в вызывающей коллекции значения,
задаваемого параметром item, используя для сравнения
указанный способ, определяемый параметром comparer.
Возвращает индекс совпавшего элемента. Если искомое
значение не найдено, возвращается отрицательное значение.
Вызывающий список должен быть отсортирован
collection
в
конец
35

36. Коллекции

Метод
Описание
public virtual void
AddRange(Icollection
collection)
Добавляет элементы из коллекции
вызывающей коллекции типа ArrayList
public virtual int
BinarySearch(T item)
Выполняет поиск в вызывающей коллекции значения,
задаваемого параметром item. Возвращает индекс совпавшего
элемента. Если искомое значение не найдено, возвращается
отрицательное значение. Вызывающий список должен быть
отсортирован
public int BinarySearch(Т
item, IComparer<T>
comparer)
Выполняет поиск в вызывающей коллекции значения,
задаваемого параметром item, используя для сравнения
указанный способ, определяемый параметром comparer.
Возвращает индекс совпавшего элемента. Если искомое
значение не найдено, возвращается отрицательное значение.
Вызывающий список должен быть отсортирован
collection
в
конец
Выполняет поиск в вызывающей коллекции значения,
задаваемого параметром item, используя для сравнения
указанный способ, определяемый параметром comparer. Поиск
public int BinarySearch(int
начинается с элемента, указываемого по индексу index, и
index, int count, T item,
включает количество элементов, определяемых параметром
IComparer<T> comparer)
count. Метод возвращает индекс совпавшего элемента. Если
36
искомое значение не найдено, возвращается отрицательное
значение. Вызывающий список должен быть отсортирован

37. Коллекции

Метод
Описание
public List<T>
GetRange(int index, int
count)
Возвращает часть вызывающей коллекции. Часть
возвращаемой коллекции начинается с элемента, указываемого
по индексу index, и включает количество элементов, задаваемое
параметром count. Возвращаемый объект ссылается на те же
элементы, что и вызывающий объект
public int IndexOf(T item)
Возвращает индекс первого вхождения элемента item в
вызывающей коллекции. Если искомый элемент не обнаружен,
возвращается значение -1
public void InsertRange(int
Вставляет элементы коллекции collection в вызывающую
index, IEnumerable<T>
коллекцию, начиная с элемента, указываемого по индексу index
collection)
public int LastlndexOf(T
item)
Возвращает индекс последнего вхождения элемента item в
вызывающей коллекции. Если искомый элемент не обнаружен,
возвращается значение -1
public void
RemoveRange(int index,
int count)
Удаляет часть вызывающей коллекции, начиная с элемента,
указываемого по индексу index, и включая количество
элементов, определяемое параметром count
public void Reverse()
Располагает элементы вызывающей коллекции в обратном
порядке
37

38. Коллекции

Метод
Описание
public void Reverse(int
index, int count)
Располагает в обратном порядке часть вызывающей коллекции,
начиная с элемента, указываемого по индексу index, и включая
количество элементов, определяемое параметром count
public void Sort()
Сортирует вызывающую коллекцию по нарастающей
В классе List<T> определяется также собственное свойство Capacity.
public int Capacity { get; set; }
Свойство Capacity позволяет установить и получить емкость
вызывающей коллекции в качестве динамического массива. Эта
емкость равна количеству элементов, которые может содержать
коллекция до ее вынужденного расширения.
Такая коллекция расширяется автоматически, и поэтому задавать ее
емкость вручную необязательно.
В классе List<T> реализуется также приведенный ниже индексатор,
определенный в интерфейсе IList<T>.
public Т this[int index] { get; set; }
С помощью данного индексатора устанавливается и получается
значение элемента коллекции, указываемое по индексу index.
38

39. Коллекции

ПРИМЕР.
// ПРИМЕР применение класса List<T>.
using System;
using System.Collections.Generic;
class GenListDemo {
static void Main() {
// Создать коллекцию в виде динамического массива.
List<char> lst = new List<char>();
Console.WriteLine("Исходное количество элементов: " +
lst.Count);
Console.WriteLine();
Console.WriteLine("Добавить 6 элементов");
// Добавить элементы в динамический массив.
lst.Add('С');
lst.Add('А');
lst.Add('Е');
lst.Add('В');
lst.Add('D');
lst.Add('F');
39

40. Коллекции

ПРИМЕР.
Console.WriteLine("Количество элементов: " + lst.Count);
// Отобразить содержимое динамического массива,
// используя индексирование массива.
Console.Write("Текущее содержимое: ");
for (int i=0; i < lst.Count; i++)
Console.Write(lst[i] + " ");
Console.WriteLine("\n");
Console.WriteLine("Удалить 2 элемента ");
// Удалить элементы из динамического массива.
lst.Remove('F');
lst.Remove('А');
Console.WriteLine("Количество элементов: " + lst.Count);
// Отобразить содержимое динамического массива, используя
цикл foreach.
Console.Write("Содержимое: ");
foreach(char с in lst)
Console.Write(с + " ");
40
Console.WriteLine("\n");

41. Коллекции

ПРИМЕР.
Console.WriteLine("Добавить еще 20 элементов");
// Добавить количество элементов, достаточное для
// принудительного расширения массива.
for(int i=0; i < 20; i++)
lst.Add((char)('a' + i));
Console.WriteLine("Текущая емкость: " + lst.Capacity);
Console.WriteLine("Количество элементов после добавления 20
новых: " + lst.Count);
Console.Write("Содержимое: ");
foreach(char с in lst)
Console.Write(с + " ");
Console.WriteLine("\n");
// Изменить содержимое динамического массива,
// используя индексирование массива.
Console.WriteLine("Изменить три первых элемента");
lst[0] = 'X';
lst[1] = 'Y';
41
lst[2] = 'Z';

42. Коллекции

ПРИМЕР.
Console.Write("Содержимое: ");
foreach(char с in lst)
Console.Write(с + " ");
Console.WriteLine();
// Следующая строка кода недопустима из-за
// нарушения безопасности обобщенного типа.
// lst.Add(99); // Ошибка, поскольку это не тип char!
}
}
42

43. Коллекции

Класс LinkedList
В классе LinkedList<T> создается коллекция в виде обобщенного
двунаправленного списка. В этом классе реализуются интерфейсы
ICollection, ICollection, IEnumerable, IEnumerable<T>, ISerializable и
IDeserializationCallback. В классе LinkedList<T> определяются два
конструктора.
• public LinkedList()
• public LinkedList(IEnumerable<T> collection)
В первом конструкторе создается пустой связный список, а во втором
конструкторе - список, инициализируемый элементами из коллекции
collection.
В классе LinkedList<T> инкапсулируются значения, хранящиеся в узлах
списка, где находятся также ссылки на предыдущие и последующие
элементы списка. Эти узлы представляют собой объекты класса
LinkedListNode<T>.
В классе LinkedListNode<T> предоставляются четыре свойства.
• public LinkedListNode<T> Next { get; }
• public LinkedListNode<T> Previous { get; }
43
• public LinkedList<T> List { get; }
• public T Value { get; set; }

44. Коллекции

С помощью свойств Next и Previous получаются ссылки на предыдущий
и после дующий узлы списка соответственно, что дает возможность
обходить список в обоих направлениях. Если же предыдущий или
последующий узел отсутствует, то возвращается пустая ссылка. Для
получения ссылки на сам список служит свойство List. А с помощью
свойства Value можно устанавливать и получать значение,
находящееся в узле списка.
В классе LinkedList<T> определяются собственные свойства, помимо
тех, что уже объявлены в интерфейсах, которые в нем реализуются.
Эти свойства приведены ниже.
• public LinkedListNode<T> First { get; }
• public LinkedListNode<T> Last { get; }
С помощью свойства First получается первый узел в списке, а с
помощью свой ства Last - последний узел в списке.
44

45. Коллекции

Метод
Описание
public LinkedListNode<T>
AddAfter(LinkedListNode<T> node,
T value)
Добавляет в список узел со значением value
непосредственно
после
указанного
узла
node.
Указываемый узел node не должен быть пустым (null).
Метод возвращает ссылку на узел, содержащий
значение value
public void
AddAfter(LinkedListNode<T> node,
LinkedListNode<T> newNode)
Добавляет
в
список
новый
узел
newNode
непосредственно
после
указанного
узла
node.
Указываемый узел node не должен быть пустым (null).
Если узел node отсутствует в списке или если новый
узел newNode является частью другого списка, то
генерируется исключение InvalidOperationException
public LinkedListNode<T>
AddBefore(LinkedListNode<T>
node, T value)
Добавляет в список узел со значением value
непосредственно перед указанным узлом node.
Указываемый узел node не должен быть пустым (null).
Метод возвращает ссылку на узел, содержащий
значение value
Добавляет
в
список
новый
узел
newNode
непосредственно перед указанным узлом node.
public void
Указываемый узел node не должен быть пустым (null).
AddBefore(LinkedListNode<T>
Если узел node отсутствует в списке или если новый
node, LinkedListNode<T> newNode)
45 то
узел newNode является частью другого списка,
генерируется исключени InvalidOperationException

46. Коллекции

Метод
public LinkedList<T> AddFirst(T
value)
Описание
Добавляет узел со значением value в начало списка.
Метод возвращает ссылку на узел, содержащий
значение value
Добавляет узел node в начало списка. Если узел node
public void AddFirst(LinkedListNode
является частью другого списка, то генерируется
node)
исключение InvalidOperationException
public LinkedList<T> AddLast(T
value)
Добавляет узел со значением value в конец списка.
Метод возвращает ссылку на узел, содержащий
значение value
public void AddLast(LinkedListNode
node)
Добавляет узел node в конец списка. Если узел node
является частью другого списка, то генерируется
исключение InvalidOperationException
public LinkedList<T> Find(T value)
Возвращает ссылку на первый узел в списке, имеющий
значение value. Если искомое значение value
отсутствует в списке, то возвращается пустое значение
public LinkedList<T> FindLast(T
value)
Возвращает ссылку на последний узел в списке,
имеющий значение value. Если искомое значение value
отсутствует в списке, то возвращается пустое значение
46

47. Коллекции

Метод
Описание
public bool Remove(T value)
Удаляет из списка первый узел, содержащий значение
value. Возвращает логическое значение true, если узел
удален, т.е. если узел со значением value обнаружен в
списке и удален; в противном случае возвращает
логическое значение false
public void Remove(LinkedList<T>
node)
Удаляет из списка узел, соответствующий указанному
узлу node. Если узел node отсутствует в списке, то
генерируется исключение InvalidOperationException
public void RemoveFirst()
Удаляет из списка первый узел
public void RemoveLast()
Удаляет из списка последний узел
47

48. Коллекции

ПРИМЕР.
// Продемонстрировать применение класса LinkedList<T>.
using System;
using System.Collections.Generic;
class GenLinkedListDemo {
static void Main() {
// Создать связный список.
LinkedList<char> ll = new LinkedList<char>();
Console.WriteLine("Исходное количество элементов в списке: " +
ll.Count);
Console.WriteLine();
Console.WriteLine("Добавить в список 5 элементов");
// Добавить элементы в связный список.
ll.AddFirst('А');
ll.AddFirst('В');
ll.AddFirst('С');
ll.AddFirst('D');
ll.AddFirst('Е');
48

49. Коллекции

ПРИМЕР.
Console.WriteLine("Количество элементов в списке: " + ll.Count);
// Отобразить связный список, обойдя его вручную.
LinkedListNode<char> node;
Console.Write("Отобразить содержимое списка по ссылкам: ");
for(node = ll.First; node != null; node = node.Next)
Console.Write(node.Value + " ");
Console.WriteLine("\n");
// Отобразить связный список, обойдя его в цикле foreach.
Console.Write("Отобразить содержимое списка в цикле foreach:");
foreach(char ch in ll)
Console.Write(ch + " ");
Console.WriteLine("\n");
// Отобразить связный список, обойдя его вручную в обратном
направлении.
Console.Write("Следовать по ссылкам в обратном направлении:");
for(node = ll.Last; node != null; node = node.Previous)
Console.Write(node.Value + " ");
49

50. Коллекции

ПРИМЕР.
Console.WriteLine("\n");
// Удалить из списка два элемента.
Console.WriteLine("Удалить 2 элемента из списка");
// Удалить элементы из связного списка.
ll.Remove('С');
ll.Remove('А');
Console.WriteLine("Количество элементов в списке: " + ll.Count);
// Отобразить содержимое видоизмененного списка в цикле
foreach.
Console.Write("Содержимое списка после удаления элементов:");
foreach(char ch in ll)
Console.Write(ch + " ");
Console.WriteLine("\n");
// Добавить три элемента в конец списка.
ll.AddLast('X');
ll.AddLast('Y');
ll.AddLast('Z');
50

51. Коллекции

ПРИМЕР.
Console.Write("Содержимое списка после ввода элементов: ");
foreach(char ch in ll)
Console.Write(ch + " ");
Console.WriteLine("\n");
}
}
51