Деякі класи неузагальнених колекцій

Матеріали лекцій

з дисципліни «Програмування»

для студентів ІІ курсу спеціальності «Прикладна математика»

Модуль 3

Організація об’єктно-орієнтованих програм у мові С#та організація даних із використанням класів BCL.

Ужгород-2012

Програма модуля

№	Тема	Кількість годин
	Колекції Організація абстрактних структур даних (простір імен System.Collections). Деякі інтерфейси неузагальнених колекцій (ICollection, IList, IDictionary). Деякі класи неузагальнених колекцій (Stack, Queue, ArrayList, Hashtable). Узагальнені колекції.
	Файловий ввід-вивід Організація файлового вводу-виводу (простір імен System.IO, клас Stream). Байтовий ввід-вивід у файл (клас FileStream). Двійковий ввід-вивід у файл (класи BinaryReader та BinaryWriter). Символьний ввід-вивід у файл (класи StreamReader та StreamWriter). Організація роботи із файлами даних стандарту XML (простір імен System.Xml, класи XMLElement та XMLDocument, класи XMLTextReader та XMLTextWriter).
	Делегати та події Клас delegate. Делегати в якості параметрів. Анонімні методи та узагальнені делегати System.Action, System.Func. Організація об’єктно-орієнтованих програм (комбіновані делегати та шаблон «спостерігач», визначення та реалізація подій).

Тема 1

Колекції

Структури даних

Структура даних − програмна одиниця, яка дозволяє зберігати та обробляти множину (сукупність) однотипних або логічно-зв’язаних даних. Структура даних є програмною реалізацією деякої абстрактної структури даних. Найбільш поширені абстрактні структури даних − масив, список, стек, черга, бінарне дерево, хеш-таблиця, множина. Більшість із цих абстрактних структур даних передбачає динамічну зміну свого розміру − при необхідності у структуру даних можна додати новий елемент або видалити існуючий. Відповідні структури даних називають динамічними структурами даних.

Будь-яка програма призначена для обробки даних. Для різних задач необхідні різні способи збереження та обробки даних, а тому вибір структур даних повинен передувати створенню алгоритмів та ґрунтуватися на вимогах до функціональності та швидкодії програми. Вибір тієї чи іншої структури залежить від того, що потрібно робити з даними у програмі. Наприклад при необхідності часто вставляти та видаляти елементи із середини послідовності варто використовувати список, а не масив. Якщо ж включення елементів здійснюється здебільшого на початок послідовності − використовується стек. Тому вивчення та грамотне застосування структур даних є необхідними умовами створення ефективних програм.

Саме тому у бібліотеках більшості сучасних об’єктно-орієнтованих мов програмування присутні стандартні класи, які реалізують основні абстрактні структури даних. У мові C# такі класи називаються колекціями або контейнерами. Використання колекцій дозволяє скоротити строки розробки програм та підвищити їх надійність.

У бібліотеці.NET визначено багато стандартних класів, які реалізують більшість згаданих абстрактних структур даних. Основні простори імен, в яких реалізовані ці класи, − System.Collections, System.Collections.Specialized та System.Collections.Generic.

Неузагальнені колекції

У просторі імен System.Collections визначено неузагальнені колекції, які є структурами даних загального призначення − дозволяють маніпулювати сукупністю різнотипних об’єктів. Також у просторі імен System.Collections визначено ряд інтерфейсів (зокрема, тут визначені у же відомі нам інтерфейси IComparable, IComparer та IEnumerable, а також похідні від них інтерфейси) неузагальнених колекцій. Розгляд неузагальнених колекцій варто розпочати саме з деяких із цих інтерфейсів, оскільки вони визначають функціональні можливості, які є спільними для всіх класів неузагальнених колекцій.

Деякі інтерфейси неузагальнених колекцій

Інтерфейс ICollection. На цьому інтерфейсі побудовані всі неузагальнені колекції. У ньому оголошено основні методи та властивості для всіх неузагальнених колекцій. Він також є похідним від інтерфейсу IEnumerable (Що це нам дає?). Серед чотирьох членів, які визначені у інтерфейсі IСollection, відмітимо наступні:

Елемент інтерфейсу ICollection	Призначення
int Count { get; }	Повертає фактичну кількість елементів, які зберігаються в колекції на даний момент. Якщо значення властивості Count дорівнює нулю, то колекція вважається порожньою.
void CopyTo(Array array, int index);	Копіює вміст колекції в масив array, починаючи із вказаного індекса index. Таким чином метод СоруTо() забезпечує у С# приведення колекції до стандартного масиву.

Інтерфейс IList. В інтерфейсі IList оголошується така поведінка неузагальненої колекції, яка дозволяє здійснювати доступ до її елементів за індексом (індексація елементів починається з нуля). Цей інтерфейс є похідним від інтерфейсів ICollection та IEnumerable. Крім методів, визначених у цих інтерфейсах, в інтерфейсі IList визначається ряд власних методів.

Елемент інтерфейсу IList	Призначення
object this[int index] { get; set; }	Цей індексатор служить для доступу до значення елемента колекції. Але його не можна використовувати для додавання в колекцію нового елемента.
int Add(object value);	Додає об’єкт value у колекцію. Повертає позицію (індекс), у яку цей об’єкт було додано та -1 − у випадку, якщо елемент не було додано у колекцію.
void Clear();	Видаляє всі елементи із колекції.
bool Contains(object value);	Повертає логічне значення true, якщо колекція містить об’єкт value, та логічне значення false − інакше.
int IndexOf(object value);	Повертає індекс об’єкта value, якщо цей об’єкт міститься у колекції та повертає -1 − інакше.
void Insert(int index, object value);	Вставляє у колекцію об’єкт value за індексом index. При цьому всі елементи, з цього індексу index і далі, зміщуються вперед.
void Remove(object value);	Видаляє перше входження об’єкта value у колекції. Елементи, що перебували до цього за вилученим елементом, зміщуються назад на одну позицію.
void RemoveAt(int index);	Видаляє із колекції об’єкт, розташований на позиції, що задається індексом index. Елементи, що перебували до цього за вилученим елементом, зміщуються назад на одну позицію.

Інтерфейс IDictionary. В інтерфейсі IDictionary визначається така поведінка неузагальненої колекції, яка дозволяє здійснювати доступ до її елементів за ключем. У колекції, що реалізує інтерфейс IDictionary, кожен елемент є парою “ключ-значення”. Як тільки подібна пара буде збережена, доступитися до неї можна за допомогою ключа. Інтерфейс IDictionary є похідним від інтерфейсів ICollection та IEnumerable.

Елемент інтерфейсу IDictionary	Призначення
object this[object key] { get; set; }	Цей індексатор служить для доступу до значення елемента колекції за ключем.
void Add(object key, object value)	Додає у колекцію пару “ключ-значення”, що задаються параметрами key і value. Може генерувати помилку часу виконання класу System.ArgumentException.
void Clear();	Видаляє всі пари “ключ-значення” із колекції.
bool Contains(object key);	Повертає логічне значення true, якщо колекція містить об’єкт key у якості ключа, а якщо ні, то − логічне значення false.
void Remove(object key);	Видаляє з колекції елемент, ключ якого рівний значенню параметра key.

Деякі класи неузагальнених колекцій

Клас Stack. Стек відноситься до однієї із найважливіших динамічних структур даних. Ця структура часто застосовується в системному програмному забезпеченні, компіляторах, тощо. Нагадаємо, що стек – це динамічна структура даних, у якій додавання елементів та їх вилучення здійснюється із одного кінця, який називається вершиною стека (головою − head). Інші операції із стеком не визначені. Кажуть, що стек реалізує принцип обслуговування LIFO («last in – first out» – «останнім прийшов – першим вийшов»).

У просторі імен System.Collections колекцією, яка підтримує стек, є клас Stack. Цей клас створює динамічну колекцію, яка розширюється по мірі потреби збереження в ній елементів, які в неї додаються. Кожного разу, коли потрібно розширити таку колекцію, її розмір автоматично збільшується вдвічі. Клас Stack реалізує інтерфейси ICollection, IEnumerable та ICloneable. Окрім методів, оголошених у цих інтерфейсах, у класі Stack визначено ряд власних методів. Наведемо найбільш часто використовувані із них:

Метод класу Stack	Призначення
public Stack(); public Stack(int initialCapacity); public Stack(ICollection col);	У першій формі конструктора створюється порожній стек. У другій − порожній стек, початковий розмір якого задається параметром initialCapacity. У третій − стек, що містить елементи колекції col.
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 у вершину стека.

Стек часто використовується в алгоритмах як допоміжна структура даних у тих випадках, коли потрібно змінити порядок яких-небудь елементів на зворотний. Як приклад розглянемо наступну задачу. Нехай дано ціле додатне число у десятковій системі числення. Потрібно перевести його в задану систему числення. Нагадаємо, що при переводі числа в іншу систему числення проводиться послідовне отримання остач від ділення цього числа на основу нової системи числення, які при записі у зворотному порядку утворюють представлення числа у новій системі числення. Тому остачі від ділення доцільно заносити у стек, а потім вилучати з нього для формування рядкового представлення запису числа. Якщо основа нової системи числення більша за 10, то в рядок заноситься відповідний символ (10 – ‘A’, 11 – ‘B’ і т.д.).

// клас для переводу цілого додатного числа із десяткової системи числення у іншу class Converter { public static string convert(uint number, byte basis) { // стек для збереження остач від ділення Stack Remainders = new Stack(); // обчислення остач від ділення числа на основу нової системи числення // та їх занесення у стек while (number!= 0) { Remainders.Push(number % basis); number /= basis; } // формування рядкового представлення запису числа шляхом вилучення значень зі стеку string res = ""; while(Remainders.Count!= 0) { uint digit = (uint)Remainders.Pop(); if(digit < 10) res = res + digit; else res = res + (char)((uint)'A' + digit - 10); } return res; } }

Клас Queue. Ще однією розповсюдженою структурою даних є черга, що діє за принципом: першим прийшов − першим оброблений. Додавання елементів у чергу виконується в один кінець («хвіст»), а вилучення проводиться з іншого кінця («голови»). Інші операції із чергою не визначені. Черга реалізує принцип обслуговування FIFO («first in – first out», першим прийшов – першим вийшов).

У мові C# клас колекції, що підтримує чергу, має назву Queue. Цей клас створює динамічну колекцію, яка розширюється, по мірі збереження у ній елементів. Так, якщо в черзі для збереження елемента потрібне додаткове місце, її розмір збільшується на коефіцієнт росту, який за замовчуванням дорівнює 2. У цьому класі реалізуються інтерфейси ICollection, IEnumerable та IСloneable. Крім методів визначених у цих інтерфейсах у класі Queue є ряд власних методів:

Метод класу Queue	Призначення
public Queue (); public Queue (int initialCapacity); public Queue(int capacity, float growFactor); public Queue(ICollection col);	У першій формі конструктора створюється порожня черга із коефіцієнтом росту 2. У другій − порожня черга, початковий розмір якої задається параметром initialCapacity, та коефіцієнтом росту 2. У третій є можливість вказати не тільки початковий розмір черги, але й її коефіцієнт росту (в якості параметра growFactor у межах від 1.0 до 10.0). Ну і четвертій формі − створюється черга, що містить елементи колекції col.
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 virtual void TrimToSize();	Задає розмір черги у відвовідності до фактичної кількості її елементів.

Розглянемо приклад роботи із чергою.

Нехай задано дві черги та , які містять дійсні числа. Із кожної черги одночасно вилучається по одному елементу та відповідно. Якщо , то число додається у чергу , інакше число додається у чергу . Потрібно визначити кількість кроків, через яку одна із черг стане порожньою.

class Program { static void Main() { Queue X = new Queue((ICollection)(new double[] { 1, 2, 3, 4, 5 })); Queue Y = new Queue((ICollection)(new double[] { 3, 2, 1 })); uint Step = 0; while (X.Count!= 0 & Y.Count!= 0) { Step++; double x = (double)X.Dequeue(); double y = (double)Y.Dequeue(); if (x < y) X.Enqueue(x + y); else Y.Enqueue(x - y); } Console.WriteLine("step= {0}", Step); Console.ReadKey(); } }

Клас ArrayList. У мові С# стандартні масиви мають фіксовану довжину. Це означає, що кількість елементів у масиві потрібно задавати заздалегідь, що не зовсім ефективно з точки зору використання пам’яті. Клас ArrayList призначений для випадків, коли кількість елементів масиву не можна визначити наперед або ж, коли кількість елементів буде змінюватись під час виконання програми. Цей клас визначає масив змінної довжини, який складається з посилань на об’єкти та може динамічно збільшувати та зменшувати свій розмір. Колекції класу ArrayList широко використовуються в практиці програмування на С#.

У класі ArrayList реалізуються інтерфейси IСollection, IList, IEnumerable та IСloneable. У класі ArrayList визначається ряд власних методів, окрім тих, що вже оголошені в цих інтерфейсах. Деякі з найбільше часто використовуваних методів класу ArrayList:

Метод класу ArrayList	Призначення
public ArrayList(); public ArrayList(int capacity); public ArrayList(ICollection c);	У першій формі конструктора створюється порожній екземпляр із початковим нульовим розміром. У другій − порожній екземпляр, початковий розмір якого задається параметром сapacity. У третій − екземпляр, що містить елементи колекції c.
public virtual int Capacity { get; set; }	Дозволяє отримувати та всановлювати розмір динамічного масиву.
public virtual void TrimToSize();	Задає розмір динамічного масиву у відвовідності до кількості фактичних елементів масиву, тобто встановлює значення властивості Capacity рівним значенню властивості Count.
public virtual void AddRange(ICollection c);	Додає у кінець динамічного масиву елементи із колекції с.
public virtual void InsertRange(int index, ICollection c);	Вставляє у динамічний масив елементи колекції c, починаючи з елемента із індексом index.
public virtual void SetRange(int index, ICollection c);	Замінює частину динамічного масиву, починаючи з елемента з індексом index, елементами колекції c.
public virtual void RemoveRange(int index, int count);	Видаляє count елементів динамічного масиву, починаючи з елемента, що задається індексом index.
public virtual ArrayList GetRange(int index, int count);	Повертає частину динамічного масиву, посинаючи із елемента з індексом index та включає кількість елементів, що задається параметром count. Об’єкт, що повертається містить посилання на ті ж самі елементи, що і вихідний об’єкт.
public virtual void Reverse(); public virtual void Reverse(int index, int count);	У першому випадку метод розташовує елементи динамічного масиву в оберненому порядку. У другому − розташовує в оберненому порядку тільки перші count елементів, які розташовані після елементу з індексом index.
public virtual void Sort(); public virtual void Sort(IComparer comparer); public virtual void Sort(int index, int count, IComparer comparer);	Перший метод сортує динамічний масив за зростанням. Другий − сортує за зростанням динамічний масив, використовуючи для порівняння спосіб, який відповідає параметру comparer. Третій − робить те саме, що й другий, тільки сортуються перші count елементів, починаючи із елемента з індексом index.
public virtual int BinarySearch(object value); public virtual int BinarySearch(object value, IComparer comparer); public virtual int BinarySearch(int index, int count, object value, IComparer comparer);	Здійсню пошук значення value у динамічному масиві. Повертає індекс знайденогого елемента. Якщо значення не знайдено, то повертає від’ємне значення. Динамічний масив має бути відсортованим. У другому методі для порівняння використовується сосіб у відповідності до параметру comparer. У третьому методі пошук ведеться серед перших count елементів, починаючи із елемента з індексом index.

Наведемо приклад використання та особливості деяких із наведених можливостей. Нехай задано масив цілих чисел, серед яких немає однакових. Цей масив у загальному випадку ділиться на три частини двома елементами: мінімальним та максимальним. Потрібно виконати над масивом наступну послідовність дій:

1) додати у кінець масиву його першу частину;

2) видалити другу частину;

3) вставити на початок третю частину.

class VarAarray { // динамічний масив ArrayList array; // конструктор з параметрами public VarAarray(params object[] args) { array = new ArrayList((ICollection)args); } // вивід на екран всіх елементів колекції заданого типу public void Display() { Console.WriteLine("[ {0}/{1}", array.Count, array.Capacity); foreach (object o in array) Console.Write(" {0}",((int)o).ToString()); Console.WriteLine("\n]"); } //метод розвязання задачі public void Solve() { // визначення індексів найбільшого та найменшого значення масиву int imin =0; int imax =0; for (int i = 1; i < array.Count; i++) { if ((int)array[i] < (int)array[imin]) imin = i; if ((int)array[i] > (int)array[imax]) imax = i; } // впорядковуємо знайдені індекси int i1 = imin; int i2 = imax; if (i1 > i2) { i1 = imax; i2 = imin; } // визначаємо кількість елементів у третій частині int count3 = array.Count - i2 - 1; // додаємо у кінець масиву першу частину ArrayList p1 = array.GetRange(0, i1); // визначаємо першу частину масиву array.AddRange(p1);// додаємо її у кінець масиву array.TrimToSize();// приводимо розмір масиву до фактичної кількості елементів // видяляємо другу частину array.RemoveRange(i1 + 1, i2 - i1 - 1); array.TrimToSize(); // вставляємо на початок третю частину ArrayList p3 = array.GetRange(i2, count3); array.InsertRange(0, p3); array.TrimToSize(); } }

Клас Hashtable призначений для створення колекції, у якій для зберігання її елементів служить хеш-таблиця. Ця структура даних, яка є програмною реалізацією асоціативного масиву (словник) − абстрактного типу даних, який дозволяє зберігати пари виду «(ключ, значення)» та підтримує операції додавання пари, пошуку за ключем та видалення за ключем. Основою реалізації хеш-таблиці є механізм хешування, який полягає у визначенні унікального значення (хеш-коду), на основі значення відповідного ключа. Отриманий хеш-код служить у якості індекса, за яким у таблиці зберігаються значення (дані), які відповідають заданому ключу. Перетворення ключа в хеш-код у мові C# виконується автоматично.

У класі Hashtable реалізуються інтерфейси IDictionary, ICollection, IEnumerable, ISerializable, IDeserializationCallback і ICloneable. У класі Hashtable визначається ряд власних методів, окрім тих, що вже оголошені в цих інтерфейсах. Деякі з найбільше часто використовуваних методів класу Hashtable:

Метод класу Hashtable	Призначення
public Hashtable(); public Hashtable(IDictionary d); public Hashtable(int capacity);	У першій формі конструктора створюється об’єкт класу Hashtable за замовчуванням. У другій формі створюваний об’єкт типу Hashtable ініціалізується елементами із колекції d. У третій формі створюваний об’єкт типу Hashtable ініціалізується, із початковим розміром, що задається параметром capacity.
public virtual bool ContainsKey(object key);	Повертає true, якщо у словнику міститься пара із заданим ключем key.
public virtual bool ContainsValue(object value);	Повертає true, якщо у словнику міститься пара із заданим значенням value.
public virtual ICollection Keys { get; }	Повертає всі ключі даного екземпляра словника.
public virtual ICollection Values { get; }	Повертає всі значення даного екземпляра словника.

Даний вид колекції зручно застосовувати тоді, коли дані визначаються деяким ключовим полем. Це поле стає індексом елемента у колекції. У якості ключового поля може бути обраний об’єкт будь-якого типу даних, наприклад, рядок, число або об’єкт деякого класу. Цей тип збереження інформації дозволяє скорочувати час виконання таких операцій, як пошук за ключем, зчитування за ключем та запис даних, навіть для дуже великої кількості елементів.

Найпростішим прикладом асоціативного масиву є телефонний довідник. У цьому випадку, наприклад, ключем може бути номер телефону, а значенням (даними) − ПІБ та адреса. Це програмно можна реалізувати у такий спосіб:

// інформація про абонента struct SubscriberInfo { // прізвище, ім'я, по-батькові string FIO; // адреса string Address; // конструктор з параметрами public SubscriberInfo(string fio, string adress) { FIO = fio; Address =adress; } // перевизначення успадкованого методу перетворення структури у рядок public new string ToString() { return FIO + " " +Address; } } // телефонна книга class PhoneBook: Hashtable { }

При такій реалізації є можливість зручного та швидкого доступу до даних абонента за його номером телефону. Наприклад:

PhoneBook MyPhoneBook = new PhoneBook(); MyPhoneBook.Add("0509845231", new SubscriberInfo("Сидоренко", "пр.Перемоги, 10")); MyPhoneBook.Add("0959845231", new SubscriberInfo("Петренко", "вул.Мукачівська, 123")); MyPhoneBook.Add("0509844567", new SubscriberInfo("Андрієнко", "вул.Загорська, 15")); if (MyPhoneBook.ContainsKey("0509844567")) Console.WriteLine(((SubscriberInfo)MyPhoneBook["0509844567"]).ToString()); else Console.WriteLine("Абонента не знайдено!");

Оскільки клас Hashtable реалізовує інтерфейс IEnumerable, то для перебору елементів колекції може використовуватися оператор foreach. Для перебору у якості локальної змінної цього циклу можна використати об’єкт структури DictionaryEntry із простору імен System.Collections, яка визначає пару «(ключ, значення)» словника.

[Serializable] [ComVisible(true)] public struct DictionaryEntry { public DictionaryEntry(object key, object value); public object Key { get; set; } public object Value { get; set; } }

Наступний приклад демонструє застосування об’єкта типу DictionaryEntry для виводу всіх елементів екземпляру MyPhoneBook колекції PhoneBook.

foreach (DictionaryEntry de in MyPhoneBook) Console.WriteLine("{0}: {1}", de.Key, ((SubscriberInfo)de.Value).ToString());

Альтернативним варіантом перебору може бути перебір на основі колекції ключів словника. У цьому випадку вивід всіх елементів екземпляру MyPhoneBook колекції PhoneBook виглядає так:

foreach (string key in MyPhoneBook.Keys) Console.WriteLine("{0}: {1}", key, ((SubscriberInfo)MyPhoneBook[key]).ToString());

На завершення огляду класу Hashtable розглянемо типову задачу, при програмній реалізації якої є доцільним та зручним використання словника. Такою задачею є задача підрахунку кількості входжень заданих об’єктів деякого цілого. Наприклад, нехай задано текст, у якому слова розділені пробілами. Потрібно підрахувати скільки разів зустрічається кожне слово у тексті. Програмна реалізація цієї задачі із використанням об’єкту Hashtable може бути такою:

Дата добавления: 2015-10-26