Учебное пособие (1077022), страница 19
Текст из файла (страница 19)
Для чтения онодоступно везде, в том числе и снаружи класса (область видимости public), адля записи – только в классе и его наследниках (область видимостиprotected).Метод добавления нового элемента в конец списка Add создает новыйконтейнер элемента на основе переданных данных (объект классаSimpleListItem), увеличивает количество элементов списка на единицу, азатем добавляет контейнер к цепочке контейнеров. В результате этого полеfirst будет содержать ссылку на первый, а last – на последний элементысписка.Метод GetItem используется для получения контейнера по егопорядковому номеру, в частности для контейнера с номером N методперебирает в цикле N-1 контейнеров и возвращает N-ый контейнер. МетодGet возвращает данные, находящиеся в контейнере.156Рассмотренные свойства и методы являются основными для работысписка. Кроме этого, для класса списка реализована дополнительнаяфункциональность.Данные списка можно перебирать в цикле foreach.
Чтобы в .NETэлементы коллекции можно было перебирать в цикле foreach, классколлекциидолженSimpleList<T>реализовыватьреализуетинтерфейсобобщенныйIEnumerable.интерфейсКлассIEnumerable<T>.Реализация данного интерфейса требует реализации у класса методовGetEnumerator.Обобщенныйметод«publicIEnumerator<T>GetEnumerator()»осуществляет перебор всех элементов списка и их возврат с помощьюконструкции«yieldIEnumerator<T>return».требуетРеализацияреализацииобобщенногоинтерфейсанеобобщенногоинтерфейсаIEnumerator. Поэтому класс SimpleList также реализует необобщенныйметод«System.Collections.IEnumeratorGetEnumerator()»,которыйвызываетSystem.Collections.IEnumerable.обобщеннуюреализациюGetEnumerator.Также для простого списка реализована сортировка методом быстройсортировки (Quick Sort).
Метод Sort без параметров выполняет сортировку,метод Sort с параметрами применяется для внутренних рекурсивныхвызовов. Вспомогательный метод Swap используется для перестановкиэлементов.Алгоритм быстрой сортировки разработал Чарльз Хоар во времястажировки в МГУ имени М.В. Ломоносова в 1960 году. Интересно то, чтоалгоритм изначально создавался для сортировки данных на магнитнойленте (устройстве с последовательным доступом), однако, в результате оноказался одним из самых эффективных и для сортировки коллекций спроизвольным доступом к элементам.157Идея алгоритма состоит в том, что выбирается некоторый среднийэлемент коллекции и предполагается, что он находится на своем месте.Далее перебираются все элементы коллекции слева и справа от него.
Еслислева расположен больший элемент, а справа меньший, то они меняютсяместами. В результате такого прохода выбранный элемент действительнооказывается на своем месте, слева от него находятся все меньшие, а справавсе большие элементы, однако элементы справа и слева не упорядочены.Поэтому далее алгоритм вызывается отдельно для левой и для правойчасти, где также выбираются средние элементы и работа алгоритмарекурсивно повторяется до тех пор, пока размер сортируемого подмассиване будет равен одному элементу.Несмотря на кажущуюся простоту алгоритма, доказано, что оноказался одним из самых эффективных алгоритмов сортировки.
Одной изпроблем алгоритма является большое количество рекурсивных вызовов,что может переполнить стек вызовов. Поэтому в некоторых реализацияхданного алгоритма рекурсию заменяют на цикл, а вместо стека вызововиспользуют отдельный стек данных, где хранят индексы начала и концасортируемого подмассива.Рассмотрим пример использования класса SimpleList:SimpleList<Figure> list = new SimpleList<Figure>();list.Add(circle);list.Add(rect);list.Add(square);Console.WriteLine("\nПеред сортировкой:");foreach (var x in list) Console.WriteLine(x);//сортировкаlist.Sort();Console.WriteLine("\nПосле сортировки:");foreach (var x in list) Console.WriteLine(x);В данном примере метод Add обеспечивает добавление данных всписок.
Использование списка в цикле foreach приводит к вызовуобобщенного метода GetEnumerator. Метод Sort осуществляет сортировкуданных списка.158Результаты вывода в консоль:СписокПеред сортировкой:Круг площадью 78,5398163397448Прямоугольник площадью 20Квадрат площадью 25После сортировки:Прямоугольник площадью 20Квадрат площадью 25Круг площадью 78,53981633974486.3.2 Класс стекаКласс стека наследуется от класса списка:using System;namespace FigureCollections{/// <summary>/// Класс стек/// </summary>class SimpleStack<T> : SimpleList<T> where T : IComparable{/// <summary>/// Добавление в стек/// </summary>public void Push(T element){//Добавление в конец списка уже реализованоAdd(element);}/// <summary>/// Удаление и чтение из стека/// </summary>public T Pop(){//default(T) - значение для типа T по умолчаниюT Result = default(T);//Если стек пуст, возвращается значение по умолчанию для типаif (this.Count == 0) return Result;//Если элемент единственныйif (this.Count == 1){//то из него читаются данные159Result = this.first.data;//обнуляются указатели начала и конца спискаthis.first = null;this.last = null;}//В списке более одного элементаelse{//Поиск предпоследнего элементаSimpleListItem<T> newLast = this.GetItem(this.Count - 2);//Чтение значения из последнего элементаResult = newLast.next.data;//предпоследний элемент считается последнимthis.last = newLast;//последний элемент удаляется из спискаnewLast.next = null;}//Уменьшение количества элементов в спискеthis.Count--;//Возврат результатаreturn Result;}}}Класс стека наследует от списка все необходимые методы, заисключением собственно методов стека – Push (запись в стек) и Pop(чтение с удалением из стека).При реализации стека на основе списка необходимо решить, что будетвершиной стека – начало или конец списка.
В данной реализации вкачестве вершины стека выбран конец списка.Метод Push просто вызывает метод Add для добавления данных вконец списка.Метод Pop в готовом виде в списке не реализован. Метод Popвозвращает последний элемент списка, а затем удаляет его из списка.Реализация метода зависит от количества элементов в списке. Если списокне содержит элементов, то возвращается значение по умолчанию дляобобщенного типа default(T). Если список содержит один элемент, то онвозвращается, а список переводится в состояние пустого списка.
Еслисписок содержит более одного элемента, то возвращается и удаляется из160списка последний элемент, а предпоследний элемент устанавливается вкачестве последнего.Рассмотрим пример использования класса SimpleStack:SimpleStack<Figure> stack = new SimpleStack<Figure>();//добавление данных в стекstack.Push(rect);stack.Push(square);stack.Push(circle);//чтение данных из стекаwhile (stack.Count > 0){Figure f = stack.Pop();Console.WriteLine(f);}Результаты вывода в консоль:СтекКруг площадью 78,5398163397448Квадрат площадью 25Прямоугольник площадью 20В соответствии с ожидаемым алгоритмом работы метод Pop извлекаетэлементы из вершины стека в обратном порядке.6.4 Контрольные вопросы к разделу 61.
Вчемсходствоиразличиемеждуобобщеннымиинеобобщенными коллекциями?2. Как выполняется работа с обобщенным списком?3. Как происходит работа с необобщенным списком?4. Как осуществляется работа с обобщенным стеком?5. Как проводится работа с обобщенной очередью?6.
Как осуществляется работа с обобщенным словарем?7. Как выполняется работа с кортежем?8. В чем особенности работы с новым синтаксисом кортежей в C#7.0?9. Как реализуется сортировка коллекций?16110.Как используется интерфейс IComparable при сортировкеколлекций?11.Как можно реализовать класс разреженной матрицы на основекласса словаря?12.Как можно реализовать классы списка и стека без применениястандартных коллекций?7 Работа с файловой системойПлатформа .NET и язык C# предоставляют широкие возможности дляработы с файловой системой. В данном разделе рассматриваютсянекоторые из этих возможностей на основе фрагментов примера 12.7.1 Получение данных о файлах и каталогахНаиболее простой способ получения информации о файловой системе– использование статического класса Directory.
Если класс являетсястатическим, то предполагается, что все его свойства и методы являютсястатическими.Класс Directory, объявленный в пространстве имен System.IO,позволяетосуществлятьработускаталогами:создание(методCreateDirectory), удаление (метод Delete), перемещение (метод Move)каталогов, получение списка файлов и подкаталогов.Пример вывода списка файлов и каталогов в корне диска «С»:string catalogName = @"c:\";Console.WriteLine("\nСписок файлов каталога " + catalogName);string[] files = Directory.GetFiles(catalogName);foreach (string file in files){Console.WriteLine(file);}Console.WriteLine("\nСписок подкаталогов каталога " + catalogName);string[] dirs = Directory.GetDirectories(catalogName);foreach (string dir in dirs){162Console.WriteLine(dir);}МетодDirectory.GetFilesполучаетсписокфайлов,аметодDirectory.GetDirectories – список подкаталогов указанного каталога.Обратите внимание на объявление переменной catalogName.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
