Динамические структуры и классы коллекций

Лабораторная работа 5

Динамические структуры и классы коллекций

Задание. Составить программу на языке C#, содержащую библиотеку классов согласно индивидуальному варианту (стек, очередь, дерево) и используя встроенные классы коллекций (ArrayList, Stack, Queue). Программа выполняет следующие действия над списком:

1. добавление элемента по ключу;

2. удаление элемента по ключу;

3. выполнение запроса;

4. просмотр списка;

На примере продемонстрировать состояние списка после выполнения операций

Вариант имеет вид xns, где

x – вариант задания;

n - вид структуры и класса коллекций (1-стек и Stack, 2 –очередь и Queue, 3- дерево и ArrayList)).

s – вид запроса;

Во все варианты к полям структуры добавляется ключ – числовое поле.

Индивидуальные варианты:

1. Структура "Студент" (ФИО, шифр группы, пол, семейное положение, номер комнаты в общежитии):

s=1 определение числа студентов определенной группы;

s=2 определение числа студентов с определенным семейным положением;

s=3 определение числа студентов в определенной комнате.

 

2. Структура “Справочное агентство” c информацией о наличии мест на рейсы (название города, N рейса, тип самолета, цена билета, время вылета, время прибытия, наличие мест):

s=1 определение числа свободных мест по дням для определенного типа самолета;

s=2 определение числа рейсов из определенного города;

s=3 определение числа свободных мест для определенного номера рейса.

3. Структура “Склад” (номенклатурный номер изделия, наименование изделия, количество изделий, цена 1 изделия):

s=1 определение цены всех изделий с названием на определенную букву;

s=2 определение количества изделий с определенным названием;

s=3 определение наименования изделия по его номеру.

4. Структура "Учебный план" (шифр специальности, наименование дисциплины, шифр кафедры, количество лекций, количество практик, количество лабораторных работ, признак: 2 – экзамен, 1 – зачет, 0 - нет ничего):

s=1 определение числа часов по определенной специальности;

s=2 определение числа часов по определенной дисциплине;

s=3 определение числа экзаменов по определенной специальности.

5. Структура “Расписание занятий” (шифр группы, день недели, время начала занятия, название предмета, номер аудитории, фамилия преподавателя):

s=1 определение числа групп, изучающих определенный предмет;

s=2 определение числа преподавателей, преподающих определенную дисциплину;

s=3 определение числа групп, занимающихся в определенный день недели и в определенное время.

6. Структура “ГИБДД” (марка автомобиля, номер, цвет, год регистрации в ГИБДД, фамилия владельца):

s=1 определение числа автомобилей определенной марки;

s=2 определение числа автомобилей с определенным годом регистрации;

s=3 определение числа автомобилей определенного цвета.

7. Структура “Обучение” (номер зачетки, фамилия ИО, номер варианта, отметка о выдаче задания 1, отметка о выполнении задания 1 в баллах, отметка о выдаче задания 2, отметка о выполнении задания 2 в баллах, отметка о выдаче задания 3, отметка о выполнении задания 3 в баллах):

s=1 определение числа выданных заданий для студента с определенной зачеткой;

s=2 определение балла студента с определенной ФИО;

s=3 определение числа студентов, получивших задания.

8. Структура “Книги” (номер книги, наименование книги, год издания, цена одного экземпляра, фамилия автора):

s=1 определение числа книг определенного автора;

s=2 определение цены книги с определенным номером;

s=3 определение числа книг с определенным годом издания.

9. Структура “Транспорт” (номер маршрута, начало маршрута, конец маршрута, тип автобуса, количество автобусов на линии, номер автобазы):

s=1 определение числа автобусов определенного типа;

s=2 определение числа автобусов на определенном маршруте;

s=3 определение типа автобуса на определенном номере маршрута.

10. Структура “Товары” (наименование товара, страна, импортирующая товар, объем поставляемой партии в штуках, страна-производитель):

s=1 определение объема товара для определенной страны – производителя;

s=2 определение количества товаров для определенной страны – производителя;

s=3 определение количества стран, в которые импортируется определенный товар.

11. Структура “Игрушки” (название игрушки, ее стоимость в руб. и возрастные границы детей, для которых игрушка предназначена):

s=1 определение количества игрушек для определенной возрастной группы;

s=2 определение суммарной стоимости игрушек с определенным названием;

s=3 возрастные границы игрушки с заданным названием.

12. Структура “Сотрудники” (фамилия и инициалы сотрудника, номер телефона, адрес):

s=1 определение количества сотрудников с определенной ФИО;

s=2 определение адреса сотрудника по его ФИО;

s=3 определение количества сотрудников с фамилией, начинающейся на определенную букву.

13. Структура "Абитуриент" (ФИО абитуриента, пол, адрес, шифр специальности, факультет, номер школы, которую закончил, оценки по трем экзаменам, признак коммерческого зачисления, сумма оплаты):

s=1 определение количества абитуриентов, закончивших определенную школу;

s=2 определение среднего балла абитуриента с определенной ФИО;

s=3 определение количества абитуриентов, поступающих по коммерческому набору на определенную специальность.

14. Структура "Абитуриент" (шифр специальности, наименование специальности, план набора, количество поданных заявлений, из них медалистов):

s=1 определение плана набора по определенной специальности;

s=2 определение числа человек на место по определенной специальности;

s=3 определение числа медалистов на определенную специальность.

15. Структура “Бюро обмена” (город куда, город откуда, тип имеющейся квартиры (кооперативная, государственная, частная), тип нужной квартиры (кооперативная, государственная, частная), этаж имеющейся квартиры, нужный этаж, число имеющихся комнат, число нужных комнат, имеющаяся общая площадь, адрес имеющейся квартиры):

s=1 определение числа лиц, проживающих в определенном городе;

s=2 определение числа лиц, желающих переехать в определенный город;

s=3 определение числа лиц, имеющих квартиру определенного типа с определенным числом комнат.

16. Структура "Подписчики" (индекс издания, наименование издания, число месяцев, ФИО подписчика, адрес подписчика, N отделения связи, месячная стоимость):

s=1 определение стоимости подписки определенного подписчика;

s=2 определение числа месяцев подписки на определенное издание определенного подписчика;

s=3 определение числа подписчиков на определенном отделении связи.

Стек, алгоритмы основных операций

Стек представляет собой объект, работа с которым — добавление и удаление — осуществляется по принципу LIFO (last-in first-out — последним пришел — первым ушел). Добавление объектов в стек может осуществляться в любой момент, удаляется же лишь объект, добавленный последним. Поведение стека напоминает работу со стопкой тарелок в столовой самообслуживания: чистые тарелки помещают сверху (добавление в вершину), а берут тарелки для использования тоже сверху (удаление из вершины). Стеки относятся к базовым структурам данных, используемым во многих приложениях.

Стек является абстрактным типом данных, который поддерживает следующие основные функции:

push (о): помещает объект о на вершину стека.

pop (): удаляет объект из стека и возвращает новый верхний объект стека; если стек пуст, выдается сообщение об ошибке.

Кроме того, стек выполняет следующие дополнительные функции:

size (): возвращает число объектов в стеке.

isEmpty (): возвращает логическое значение, подтверждающее, что стек пуст.

top (): возвращает верхний объект в стеке, не удаляя его; если стек пуст, выдается сообщение об ошибке.

Классы коллекций

 

Класс Stack и его методы

 

Этот класс представляет собой коллекцию объектов типа "последним пришел — первым вышел" (LIFO).

Конструктор Stack() инициализирует новый пустой экземпляр класса Stack.

Реальное количество элементов, хранящихся в данный момент в Stack, можно узнать из свойства Count.

Метод Contains(объект) определяет, входит ли элемент в состав коллекции Stack.

Метод Clear() удаляет все объекты из коллекции Stack.

Метод Peek()возвращает верхний объект стека Stack, но не удаляет его.Метод Pop() удаляет и возвращает верхний объект стека Stack.Метод Push(объект) вставляет объект как верхний элемент стека Stack.

Пример применения методов:

using System.Collections;public class SamplesStack { public static void Main() {// Создание и инициализация нового стекаStack myStack = new Stack();myStack.Push("The");myStack.Push("quick");myStack.Push("brown");myStack.Push("fox");// Вывод содержимого стека с конца Console.Write("Содержимое стека:");PrintValues(myStack, '\t');// Удаление элемента из стекаConsole.WriteLine("(Удаленный)\t\t{0}", myStack.Pop());// Вывод содержимого стека Console.Write(" Содержимое стека:");PrintValues(myStack, '\t');// Просмотр элемента в вершине стека.Console.WriteLine("(Верхний элемент)\t\t{0}", myStack.Peek());}public static void PrintValues(Stack myCollection,char mySeparator) { foreach (Object obj in myCollection) Console.Write("{0}{1}", mySeparator, obj); Console.WriteLine();} }

Класс Queue и его методы

 

Этот класс представляет коллекцию объектов, основанную на принципе "первым поступил — первым обслужен".

Конструктор Queue() инициализирует новый пустой экземпляр класса Queue.

Реальное количество элементов, хранящихся в данный момент в Queue, можно узнать из свойства Count.

Метод Contains(объект) определяет, входит ли элемент в состав коллекции Queue.

Метод Clear() удаляет все объекты из коллекции Queue.

Метод Dequeue() удаляет и возвращает объект, находящийся в начале коллекции Queue.

Метод Enqueue(объект) добавляет объект в конец коллекции Queue.

Метод Peek() возвращает объект, находящийся в начале коллекции Queue, но не удаляет его.

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

using System.Collections;public class SamplesQueue {public static void Main() {// Создание и инициализация новой очереди Queue myQ = new Queue(); myQ.Enqueue("The"); myQ.Enqueue("quick"); myQ.Enqueue("brown"); myQ.Enqueue("fox");// Вывод очереди в порядке поступления Console.Write("Очередь:"); PrintValues(myQ); // Удаление первого элемента очередиConsole.WriteLine("(Удален)\t{0}", myQ.Dequeue());// Вывод очереди в порядке поступления Console.Write(" Очередь:"); PrintValues(myQ);// Вывод первого элемента без его удаления Console.WriteLine("(Первый элемент) \t{0}", myQ.Peek()); } public static void PrintValues(Queue myCollection) { foreach (Object obj in myCollection) Console.Write(" {0}", obj);Console.WriteLine(); }}

 

Класс List и его методы

Класс List – это коллекция, элементами которой являются экземпляры класса. Поддерживает методы для поиска по списку, выполнения сортировки и других операций со списками.

Объявление списка имеет вид:

List<тип входящего объекта> имя = new List< тип входящего объекта>(); У класса имеются свойство

Count - Число элементов, которое фактически содержится в коллекции.

Полезные методы класса List перечислены в табл. 12.

Таблица 12

Некоторые методы класса List

Метод	Описание
Add(объект)	Добавляет объект в конец коллекции
Clear()	Удаляет все элементы из коллекции
bool Contains(элемент)	Определяет, входит ли элемент в состав коллекции
bool Exists(метод)	Определяет, содержит ли коллекция элементы, удовлетворяющие условиям указанного метода, который в качестве параметра должен иметь объект того класса, который помещен в коллекцию
Тип объекта Find(метод)	Выполняет поиск элемента, удовлетворяющего условиям метода, и возвращает первое найденное вхождение в пределах всего списка
Insert(индекс с 0,элемент)	Добавляет элемент в список в позиции с указанным индексом
bool Remove(элемент)	Удаляет первое вхождение указанного объекта из коллекции
Sort(метод сравнения)	Сортирует элементы во всем списке с использованием указанного метода

Один из примеров иллюстриует применение метода Exists List<string> dinosaurs = new List<string>();dinosaurs.Add("Compsognathus");dinosaurs.Add("Amargasaurus");dinosaurs.Add("Oviraptor");dinosaurs.Add("Velociraptor");dinosaurs.Add("Deinonychus");dinosaurs.Add("Dilophosaurus");dinosaurs.Add("Gallimimus");dinosaurs.Add("Triceratops"); Console.WriteLine("\nExists(EndsWithSaurus): {0}", dinosaurs.Exists(EndsWithSaurus)); // Метод поиска возвращает true, если строка заканчивается "saurus" private static bool EndsWithSaurus(String s) { if ((s.Length > 5) && (s.Substring(s.Length - 6).ToLower() == "saurus")) { return true; } else {return false; } } Второй пример иллюстрирует применение метода Sort: List<string> dinosaurs = new List<string>();dinosaurs.Add("Pachycephalosaurus");dinosaurs.Add("Amargasaurus");dinosaurs.Add("");dinosaurs.Add(null);dinosaurs.Add("Mamenchisaurus");dinosaurs.Add("Deinonychus");Display(dinosaurs);dinosaurs.Sort(CompareDinosByLength);Display(dinosaurs);private static int CompareDinosByLength(string x, string y){// сранение длин двух строк int retval = x.Length.CompareTo(y.Length); if (retval!= 0) // Если строки неравной длины, то более длинная строка больше return retval; else {// Если строки равной длины, они сортируются обычным образом return x.CompareTo(y); } } private static void Display(List<string> list) { Console.WriteLine(); foreach(string s in list) {if (s == null) Console.WriteLine("(null)"); else Console.WriteLine("\"{0}\"", s); } }

m(n => (long)n)));

Лабораторная работа 5

Динамические структуры и классы коллекций

Задание. Составить программу на языке C#, содержащую библиотеку классов согласно индивидуальному варианту (стек, очередь, дерево) и используя встроенные классы коллекций (ArrayList, Stack, Queue). Программа выполняет следующие действия над списком:

1. добавление элемента по ключу;

2. удаление элемента по ключу;

3. выполнение запроса;

4. просмотр списка;

На примере продемонстрировать состояние списка после выполнения операций

Вариант имеет вид xns, где

x – вариант задания;

n - вид структуры и класса коллекций (1-стек и Stack, 2 –очередь и Queue, 3- дерево и ArrayList)).

s – вид запроса;

Во все варианты к полям структуры добавляется ключ – числовое поле.

Индивидуальные варианты:

1. Структура "Студент" (ФИО, шифр группы, пол, семейное положение, номер комнаты в общежитии):

s=1 определение числа студентов определенной группы;

s=2 определение числа студентов с определенным семейным положением;

s=3 определение числа студентов в определенной комнате.

 

2. Структура “Справочное агентство” c информацией о наличии мест на рейсы (название города, N рейса, тип самолета, цена билета, время вылета, время прибытия, наличие мест):

s=1 определение числа свободных мест по дням для определенного типа самолета;

s=2 определение числа рейсов из определенного города;

s=3 определение числа свободных мест для определенного номера рейса.

3. Структура “Склад” (номенклатурный номер изделия, наименование изделия, количество изделий, цена 1 изделия):

s=1 определение цены всех изделий с названием на определенную букву;

s=2 определение количества изделий с определенным названием;

s=3 определение наименования изделия по его номеру.

4. Структура "Учебный план" (шифр специальности, наименование дисциплины, шифр кафедры, количество лекций, количество практик, количество лабораторных работ, признак: 2 – экзамен, 1 – зачет, 0 - нет ничего):

s=1 определение числа часов по определенной специальности;

s=2 определение числа часов по определенной дисциплине;

s=3 определение числа экзаменов по определенной специальности.

5. Структура “Расписание занятий” (шифр группы, день недели, время начала занятия, название предмета, номер аудитории, фамилия преподавателя):

s=1 определение числа групп, изучающих определенный предмет;

s=2 определение числа преподавателей, преподающих определенную дисциплину;

s=3 определение числа групп, занимающихся в определенный день недели и в определенное время.

6. Структура “ГИБДД” (марка автомобиля, номер, цвет, год регистрации в ГИБДД, фамилия владельца):

s=1 определение числа автомобилей определенной марки;

s=2 определение числа автомобилей с определенным годом регистрации;

s=3 определение числа автомобилей определенного цвета.

7. Структура “Обучение” (номер зачетки, фамилия ИО, номер варианта, отметка о выдаче задания 1, отметка о выполнении задания 1 в баллах, отметка о выдаче задания 2, отметка о выполнении задания 2 в баллах, отметка о выдаче задания 3, отметка о выполнении задания 3 в баллах):

s=1 определение числа выданных заданий для студента с определенной зачеткой;

s=2 определение балла студента с определенной ФИО;

s=3 определение числа студентов, получивших задания.

8. Структура “Книги” (номер книги, наименование книги, год издания, цена одного экземпляра, фамилия автора):

s=1 определение числа книг определенного автора;

s=2 определение цены книги с определенным номером;

s=3 определение числа книг с определенным годом издания.

9. Структура “Транспорт” (номер маршрута, начало маршрута, конец маршрута, тип автобуса, количество автобусов на линии, номер автобазы):

s=1 определение числа автобусов определенного типа;

s=2 определение числа автобусов на определенном маршруте;

s=3 определение типа автобуса на определенном номере маршрута.

10. Структура “Товары” (наименование товара, страна, импортирующая товар, объем поставляемой партии в штуках, страна-производитель):

s=1 определение объема товара для определенной страны – производителя;

s=2 определение количества товаров для определенной страны – производителя;

s=3 определение количества стран, в которые импортируется определенный товар.

11. Структура “Игрушки” (название игрушки, ее стоимость в руб. и возрастные границы детей, для которых игрушка предназначена):

s=1 определение количества игрушек для определенной возрастной группы;

s=2 определение суммарной стоимости игрушек с определенным названием;

s=3 возрастные границы игрушки с заданным названием.

12. Структура “Сотрудники” (фамилия и инициалы сотрудника, номер телефона, адрес):

s=1 определение количества сотрудников с определенной ФИО;

s=2 определение адреса сотрудника по его ФИО;

s=3 определение количества сотрудников с фамилией, начинающейся на определенную букву.

13. Структура "Абитуриент" (ФИО абитуриента, пол, адрес, шифр специальности, факультет, номер школы, которую закончил, оценки по трем экзаменам, признак коммерческого зачисления, сумма оплаты):

s=1 определение количества абитуриентов, закончивших определенную школу;

s=2 определение среднего балла абитуриента с определенной ФИО;

s=3 определение количества абитуриентов, поступающих по коммерческому набору на определенную специальность.

14. Структура "Абитуриент" (шифр специальности, наименование специальности, план набора, количество поданных заявлений, из них медалистов):

s=1 определение плана набора по определенной специальности;

s=2 определение числа человек на место по определенной специальности;

s=3 определение числа медалистов на определенную специальность.

15. Структура “Бюро обмена” (город куда, город откуда, тип имеющейся квартиры (кооперативная, государственная, частная), тип нужной квартиры (кооперативная, государственная, частная), этаж имеющейся квартиры, нужный этаж, число имеющихся комнат, число нужных комнат, имеющаяся общая площадь, адрес имеющейся квартиры):

s=1 определение числа лиц, проживающих в определенном городе;

s=2 определение числа лиц, желающих переехать в определенный город;

s=3 определение числа лиц, имеющих квартиру определенного типа с определенным числом комнат.

16. Структура "Подписчики" (индекс издания, наименование издания, число месяцев, ФИО подписчика, адрес подписчика, N отделения связи, месячная стоимость):

s=1 определение стоимости подписки определенного подписчика;

s=2 определение числа месяцев подписки на определенное издание определенного подписчика;

s=3 определение числа подписчиков на определенном отделении связи.