Лекция 12-13. Класы коллекций

План:

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

2.Класс Stack

3.Класс Queue

4.Класс ArrayList

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

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

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

Коллекции общего назначения определены в пространстве имен System.Collection и реализуют такие структуры данных, как стеки, очереди, динамические массивы, словари (хеш-таблицы, предназначенные для хранения пар ключ/значение), отсортированный список для хранения пар ключ/значение. Коллекции общего назначения работают с данными типа object, поэтому их можно использовать для хранения данных любого типа.

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

В пространстве имен System.Collection определена единственная коллекция, ориентированная на побитовую организацию данных, которая служит для хранения групп битов и поддерживает такой набор операций, который не характерен для коллекций других типов.

Классы коллекций общего назначения представлены в таблице 3.1.

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

Класс Stack

Стек – это частный случай однонаправленного списка, добавление элементов в который и выборка элементов из которого выполняются с одного конца, называемого вершиной стека (головой – head). При выборке элемент исключается из стека. Другие операции со стеком не определены. Говорят, что стек реализует принцип обслуживания LIFO (last in – fist out, последним пришел – первым вышел). Стек проще всего представить себе в виде пирамиды, на которую надевают кольца (см. рисунок 3.5).

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

В С# реализацию стек представляет класс Stack, который реализует интерфейсы ICollection, IEnumerable и ICloneable. Stack – это динамическая коллекция, размер которой изменяется.

Рисунок 3.5 – Визуальный пример стека

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

public Stack(); //создает пустой стек, начальная вместимость которого равна 10

public Stack(int capacity); //создает пустой стек, начальная вместимость которого равна capacity

public Stack(ICollection c); //создает стек, который содержит элементы коллекции, заданной параметром с, и аналогичной вместимостью

Кроме методов, определенных в интерфейсах, реализуемых классом Stack, в этом классе определены собственные методы, представленные в приложении 11

Пример 1.

Для заданного значения n запишем в стек все числа от 1 до n, а затем извлечем из стека:

using System;

using System.Collections;

namespace ConsoleApplication

{

class Program

{

public static void Main()

{

Console.Write("n= ");

int n=int.Parse(Console.ReadLine());

Stack intStack = new Stack();

for (int i = 1; i <= n; i++) intStack.Push(i);

Console.WriteLine("Размерность стека " + intStack.Count);

Console.WriteLine("Верхний элемент стека = " + intStack.Peek());

Console.WriteLine("Размерность стека " + intStack.Count);

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

while (intStack.Count != 0)

Console.Write("{0} ", intStack.Pop());

Console.WriteLine("\nНовая размерность стека " + intStack.Count);

}

}

}

Пример 2.

В текстовом файле содержится математическое выражение. Проверить баланс круглых скобок в данном выражении.

using System;

using System.Collections;

using System.IO;

namespace MyProgram

{

class Program

{

public static void Main()

{

StreamReader fileIn=new StreamReader("t.txt",);

string line=fileIn.ReadToEnd();

fileIn.Close();

Stack skobki=new Stack();

bool flag=true;

//проверяем баланс скобок

for ( int i=0; i<line.Length;i++)

{

//если текущий символ открывающаяся скобка, то помещаем ее в стек

if (line[i] == '(') skobki.Push(i);

else

if (line[i] == ')')

//если текущий символ закрывающаяся скобка, то

if (skobki.Count == 0)

//если стек пустой, то для закрывающейся скобки не хватает парной открывающейся

{

flag = false;

Console.WriteLine("Возможно в позиции"+i+"лишняя ) скобка");

}

else

skobki.Pop(); //иначе извлекаем парную скобку

}

//если после просмотра строки стек оказался пустым, то скобки сбалансированы

if (skobki.Count == 0)

if (flag)

Console.WriteLine("скобки сбалансированы");

else //иначе баланс скобок нарушен

{

Console.Write("Возможно лишняя ( скобка в позиции:");

while (skobki.Count != 0)

Console.Write("{0} ", (int)skobki.Pop());

Console.WriteLine();

}

}

}

}

Класс Queue

Очередь – это частный случай однонаправленного списка, добавление элементов в который выполняется в один конец (хвост), а выборка производится с другого конца (головы). Другие операции с очередью не определены. При выборке элемент исключается из очереди. Говорят, что очередь реализует принцип обслуживания FIFO (fist in – fist out, первым пришел – первым вышел). Очередь проще всего представить в виде узкой трубы, в один конец которой бросают мячи, а с другого конца которой они вылетают (см. рисунок 3.6). Понятно, что мяч, который был брошен в трубу первым, первым и вылетит с другого конца.

Рисунок 3.6 – Визуальный пример очереди

В С# реализацию очередь представляет класс Queue, который также как и стек реализует интерфейсы ICollection, IEnumerable и ICloneable. Queue – это динамическая коллекция, размер которой изменяется. При необходимости увеличение вместимости очереди происходит с коэффициентом роста по умолчанию равным 2.0.

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

public Queue();//создает пустую очередь, начальная вместимость которой равна 32

public Queue (int capacity);// создает пустую очередь, начальная вместимость которой равна capacity

public Queue (int capacity, float n);//создает пустую очередь, начальная вместимость которой равна capacity, и коэффициент роста устанавливается параметром n

public Queue (ICollection c); //создает очередь, которая содержит элементы коллекции, заданной параметром с, и аналогичной вместимостью

Кроме методов, определенных в интерфейсах, реализуемых классом Queue, в этом классе определены собственные методы, представленные в приложении 11

Пример 1.

Для заданного значения n запишем в очередь все числа от 1 до n, а затем извлечем их из очереди:

using System;

using System.Collections;

namespace MyProgram

{

class Program

{

public static void Main()

{

Console.Write("n= ");

int n=int.Parse(Console.ReadLine());

Queue intQ = new Queue();

for (int i = 1; i <= n; i++) intQ.Enqueue(i);

Console.WriteLine("Размерность очереди " + intQ.Count);

Console.WriteLine("Верхний элемент = " + intQ.Peek());

Console.WriteLine("Размерность очереди = " + intQ.Count);

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

while (intQ.Count!=0)

Console.Write("{0} ", intQ.Dequeue());

Console.WriteLine("\nНовая размерность = " + intQ.Count);

}

}

}

Пример 2.

В текстовом файле записана информация о людях (фамилия, имя, отчество, возраст, вес через пробел). Вывести на экран вначале информацию о людях младше 40 лет, а затем информацию о всех остальных.

using System;

using System.Collections;

using System.IO;

using System.Text;

namespace MyProgram

{

class Program

{

//структура для хранения данных об одном человеке

public struct one

{

public string f;

public string i;

public string o;

public int age;

public float massa;

}

public static void Main()

{

StreamReader fileIn = new StreamReader("t.txt",

Encoding.GetEncoding(1251));

string line;

Queue people = new Queue();

one a;

Console.WriteLine("ВОЗРАСТ МЕНЕЕ 40 ЛЕТ");

while ((line = fileIn.ReadLine()) != null)

//читаем до конца файла

{

//разбиваем строку на составные элементы заполняем структуру

string [] temp = line.Split(' ');

a.f = temp[0];

a.i = temp[1];

a.o = temp[2];

a.age = int.Parse(temp[3]);

a.massa = float.Parse(temp[4]);

// если возраст меньше 40 лет, то выводим данные на экран, иначе помещаем их в очередь для временного хранения

if (a.age<40)

Console.WriteLine(a.f + "\t"+ a.i + "\t"+ a.o +

"\t"+a.age + "\t" + a.massa);

else

people.Enqueue(a);

}

fileIn.Close();

Console.WriteLine("ВОЗРАСТ 40 ЛЕТ И СТАРШЕ");

while (people.Count != 0) //извлекаем из очереди данные

{

a = (one)people.Dequeue();

Console.WriteLine(a.f + "\t"+ a.i + "\t"+ a.o +

"\t"+a.age + "\t" + a.massa);

}

}

}

}

Класс ArrayList

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

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

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

public ArrayList() //создает пустой массив с максимальной емкостью равной 16 элементам, при текущей размерности 0

public ArrayList(int capacity) //создает массив с заданной емкостью capacity, при текущей размерности 0

public ArrayList(ICollection с) //строит массив, который инициализируется элементами коллекции с

Помимо методов, определенных в интерфейсах, которые реализует класс ArrayList, в нем определены и собственные методы, представленные в приложении 11

Пример 1.

В текстовом файле записана информация о людях (фамилия, имя, отчество, возраст, вес через пробел). Вывести на экран информацию о людях, отсортированную по возрасту.

using System;

using System.Collections;

using System.IO;

using System.Text;

namespace MyProgram

{

class Program

{

//структура для хранения данных об одном человеке

public struct one

{

public string f;

public string i;

public string o;

public int age;

public float massa;

}

//реализация стандартного интерфейса

public class SortByAge : IComparer

{

//переопределение метода Compare

int IComparer.Compare(object x, object y)

{

one t1 = (one)x;

one t2 = (one)y;

if (t1.age > t2.age) return 1;

if (t1.age < t2.age) return -1;

return 0;

}

}

static void ArrayPrint(string s, ArrayList a)

{

Console.WriteLine(s);

foreach (one x in a)

Console.WriteLine(x.f + "\t"+ x.i + "\t"+ x.o +

"\t"+x.age + "\t" + x.massa);

}

static void Main(string[] args)

{

StreamReader fileIn = new StreamReader("t.txt",

Encoding.GetEncoding(1251));

string line;

one a;

ArrayList people = new ArrayList();

string[] temp = new string[3];

//цикл для организации обработки файла

while ((line=fileIn.ReadLine())!=null)

{

temp = line.Split(' ');

a.f = temp[0];

a.i = temp[1];

a.o = temp[2];

a.age = int.Parse(temp[3]);

a.massa = float.Parse(temp[4]);

people.Add(a);

}

fileIn.Close();

ArrayPrint("Исходные данные: ", people);

people.Sort(new Program.SortByAge()); //вызов сортировки

ArrayPrint("Отсортированные данные: ", people);

}

}

}

Контрольные вопросы:

1.Основные типы классов коллекций в С#

2.Что такое стек? Алгоритм работы стека.

3.Что такое очередь? Алгоритм работы очереди.

4.Что такое динамический массив? Алгоритм работы динамического массива.

Тема 4. Инкапсуляция и скрытие информации