Коллекции классов Лекция 12

С помощью коллекций вместо создания структур данных программист использует готовые структуры данных, не заботясь об их реализации. Т. е., коллекция (контейнер) – это стандартный класс, реализующий какую-либо абстрактную структуру данных (стек, очередь, бинарное дерево и т.д.) В качестве примера коллекций можно привести колоду карт, набор любимых песен и т.д..NET Framework предоставляет несколько коллекций: - ArrayList -Stack - HashTable - Queue и др.

Все они принадлежат пространству имен System.Collections. ArrayList Эта коллекция имитирует функциональность традиционных массивов и обеспечивает динамическое изменении размера коллекции посредством методов класса. Класс ArrayList сохраняет ссылки на object, а т.к. все классы являются производными от object, класс ArrayList может содержать объекты любого типа. Класс имеет внутреннее закрытое поле типа Array и два конструктора: без параметров и с параметром, устанавливающим емкость массива.

Свойства: Capacity – емкость массива (количество элементов, которые могут в нем храниться. Если при добавлении нового элемента фактическое количество превышает емкость, она автоматически удваивается. Создание объекта класса ArrayList осуществляется след. образом: ArrayList A= new ArrayList( ); // создание массива нулевой // емкости ArrayList A=new ArrayList(200); // создание массива c // емкостью 200 элементов

Count – фактическое количество элементов массива. Приведенный ниже фрагмент программы выведет на экран 0: ArrayList A= new ArrayList(200); Console.WriteLine(A.Count); Методы: Add(object ob) – добавляет элемент ob в конец массива, возвращает значение типа int, указывающее место, в которое добавлен новый элемент. A.Add("Вася"); int k = A.Add(5); Console.WriteLine(k); // будет выведено значение 1.

AddRange(ICollection с) – добавляет серию элементов в конец массива. ArrayList B = new ArrayList(1); B.Add(3); B.Add(6.5); B.Add(2); A.AddRange(B); foreach(object a in A) Console.WriteLine(a); Результат: Вася 5 3 6,5 2

Sort( ) – сортировка массива (при условии что элементы являются объектами типа IComparable и могут сравниваться между собой). Sort(i, k ) – сортировка части массива из k элементов начиная с i-го. BinarySearch(object ob) – осуществляет бинарный поиск элемента ob в отсортированном массиве и возвращает номер найденного элемента (или отрицательное число, если элемент не найден). Clear( ) – удаление всех элементов массива. CopyTo(int i1, Array a, int i2, int k) – копирует часть массива из k элементов, начиная с i1-го, в одномерный массив a, начиная с i2-го. Тип элементов массива-источника должен быть совместим с типом элементов в полученном массиве.

int[ ] s=new int[2]; A.CopyTo(1, s, 0, 2); CopyTo( Array a) – копирует все элементы в массив a. Insert(int i, object ob) – вставка элемента ob в заданную позицию i. Например, A.Insert(2, "hhh"); Remove(object ob) – удаление первого вхождения заданного элемента в массив. Например, A.Remove("hhh");

RemoveAt(int i) – удаление i-го элемента. A.RemoveAt(2); Reverse( ) – изменение порядка следования элементов на обратный. TrimToSize() – установка емкости массива равной фактическому количеству элементов. IndexOf(object ob) – осуществляет поиск первого вхождения элемента ob в массив (возвращает индекс найденного элемента или -1, если элемент не найден). LastIndexOf(object ob) – осуществляет поиск последнего вхождения элемента ob в массив (возвращает индекс найденного элемента или -1, если элемент не найден).

К элементу массива класса ArrayList можно получить доступ с помощью индексатора, т. е. обращаться по номеру: A[3]. Таким образом можно изменить или получить значение уже добавленных в массив элементов. Добавить новый элемент, используя индексатор нельзя. Contains(object ob) – возвращает true, если ob находится в массиве, и false в противном случае.

Класс Stack. Реализует стековую структуру данных. Создание объекта класса Stack осуществляется след. образом: Stack st = new Stack( );// создание стека с емкостью по умолчанию (10 элементов) Stack st = new Stack(100);// создание массива c // емкостью 100 элементов Свойство: Count – количество элементов в стеке.

Методы: Push(object ob) – добавляет объект ob в верхнюю часть класса (вершину стека). Если количество элементов в стеке равно его емкости на время выполнения метода Push, размер стека увеличивается для размещения большего количества объектов. Stack st = new Stack(100); st.Push(2); st.Push("Муси"); st.Push("Пуси"); foreach(object stt in st) Console.WriteLine(stt); Результат: Пуси Муси 2

Pop( ) – удаляет «верхний» объект из стека. Peek( ) – возвращает объект (тип object) из вершины стека. string sss =(string) st.Peek( ); Попытка получения (Peek) или вытеснения (Pop) элемента из пустого стека (свойство Count=0) вызывает исключение InvalidOperationException. Contains(object ob) – возвращает true, если ob находится в стеке, и false в противном случае.

Класс HashTable. Реализует хэш-таблицу. Создание объекта класса HashTable осуществляется след. образом: Hashtable tb = new Hashtable( ); // 15 раз перегружен конструктор Hashtable tb = new Hashtable(n); // создание хэш-таблицы // емкостью n Например, Hashtable tb = new Hashtable(500); Hashtable tb = new Hashtable(n, f); // создание хэш-таблицы // емкостью n и коэффициентом нагрузки f ( от 0.1 до 1). Hashtable tb = new Hashtable(500,0.5f);

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

Keys – возвращает коллекцию ключей. Values - возвращает коллекцию данных. Методы: Add(object key, object value) – добавляет элемент в таблицу. tb.Add("Петя", 3.5); Ключ должен быть уникальным и не равным null. Clear( ) – удаляет все записи из таблицы.

Remove(object key) – удаляет запись, соответствующую ключу. Contains(object key) – возвращает true, если ключ key находится в таблице, и false в противном случае. Поиск в таблице осуществляется с помощью индексатора: имя таблицы[object key] Например, tb.Add("Петя", 3.5); tb.Add("Вася", 2.5); Console.WriteLine(tb["Петя"]); Результат: 3,5