1629295403-b876e2087bddebea4bc9666fb2377a02 (846199), страница 89
Текст из файла (страница 89)
Обратитесь к справочной системе заинформацией о пространстве имен System. Collections .Generic).Другие пространства имен коллекций, которыми вы можете захотеть воспользоватьс я — System. Collections и System. Collections . Specialized. Поищитеинформацию о них в справочной системе, но в первую очередь следует искать подходящую коллекцию именно в пространстве имен System.
Collections . Generic.Пример связанного спискаПриведенная далее демонстрационная программа иллюстрирует созданиеи использование связанного списка.// LinkedListContainer - демонстрация "самодельного"// связанного списка. Этот контейнер реализует интерфейс// IEnumerable для поддержки таких операторов, как foreach.// Этот пример включает также итератор, который реализует// интерфейс IEnumeratorusing System;using System.Collections;namespace LinkedListContainer{// LLNode - каждый LLNode образует узел списка.
Каждый// узел LLNode содержит ссылку на целевые данные,// встроенные в списокpublic class LLNode{// Это данные, которые хранятся в узле спискаinternal object linkedData = null;// Указатели на следующий и предыдущий узлы в спискеinternal LLNode forward = null; // Следующий узелinternal LLNode backward = null; // Предыдущий узелinternal LLNode(object linkedData){this.linkedData = linkedData;}// Получение данных, хранящихся в узлеpublic object Data{get{return linkedData;}}452Часть VII. Дополнительные главы}II LinkedList - реализация дважды связанного спискаpublic class LinkedList : IEnumerable{// Концы связанного списка. Спецификатор internal// позволяет итераторам обращаться к ним непосредственноinternal LLNode head = null;// Начало спискаinternal LLNode tail = null;// Конец спискаpublic IEnumerator GetEnumerator()return new LinkedListlterator(this);// AddObject - добавление объекта в конец спискаpublic LLNode AddObject(object objectToAdd){return AddObject(tail, objectToAdd);}// AddObject- добавление объекта в списокpublic LLNode AddObject(LLNode previousNode,object objectToAdd){// Создание нового узла с добавляемым объектомLLNode newNode = new LLNode(objectToAdd);// Начнем с простейшего случая — пустого списка.if (head == null && tail == null){// ...теперь в нем один элементhead = newNode;tail = newNode;return newNode;}// Добавляем ли мы новый узел в средину списка?if (previousNode != null &&previousNode.forward != null){// Просто изменяем указателиLLNode nextNode = previousNode.forward;// Указатель на следующий узелnewNode.forward = nextNode;previousNode.forward = newNode;// Указатель на предыдущий узелnextNode.backward = newNode;newNode.backward = previousNode;return newNode;}// Добавление в начало списка?if (previousNode == null)Глава 20.
Работа с коллекциями453{// Делаем его головой спискаLLNode nextNode = head;newNode.forward = nextNode;nextNode.backward = newNode;head = newNode;return newNode;}// Добавление в конец спискаnewNode.backward = previousNode;previousNode.forward = newNode;tail = newNode;return newNode;}// RemoveObject - удаление объекта из спискаpublic void RemoveObject(LLNode currentNode){// Получаем соседей удаляемого узлаLLNode previousNode = currentNode.backward;LLNode nextNode= currentNode.forward;// Обнуляем указатели удаляемого объектаcurrentNode.forward = currentNode.backward = null;// Был ли это последний элемент списка?if (head == currentNode && tail == currentNode)head = tail = null;return;// Это узел в средине списка?if (head != currentNode && tail!= currentNode)previousNode.forward = nextNode;nextNode.backward = previousNode;return;// Это узел в начале списка?if (head •== currentNode && tail!= currentNode)head = nextNode;nextNode.backward = null;return;// Это узел в конце списка...tail = previousNode;previousNode.forward = null;// LinkedListlterator - дает приложению доступ к спискам454Часть VII.
Дополнительные главы// LinkedListpublic class LinkedListlterator : IEnumerator{// Итерируемый связанный списокprivate LinkedList linkedList;// "Текущий" и "следующий" элементы связанного списка.// Объявлены как private для предотвращения// непосредственного обращения извнеprivate LLNode currentNode = null;private LLNode nextNode = null;//LinkedListlterator - конструкторpublic LinkedListlterator(LinkedList linkedList){this.linkedList = linkedList;Reset ( ) ;}// Current- возвращаем объект данных в текущей позицииpublic object.
Current{get{if{(currentNode == null)return null;}return currentNode.1inkedData;// Reset - перемещение итератора назад, в позицию,// непосредственно предшествующую первому узлу спискаpublic void Reset(){currentNode = null;nextNode = linkedList.head;}// MoveNext - переход к следующему элементу списка, пока// не будет достигнут его конецpublic bool MoveNext(){currentNode = nextNode;if (currentNode == null){return false;}nextNode = nextNode.forward;return true;public class ProgramГлава 20.
Работа с коллекциями455public static void Main (string [] args){// Создаем контейнер и добавляем в него три элементаLinkedList 11с = new LinkedList();LLNode first = 11c.AddObject("Первая с т р о к а " ) ;LLNode second = 11c.AddObject("Вторая с т р о к а " ) ;LLNode third = 11c.AddObject("Последняя с т р о к а " ) ;// Добавляем элементы в начале и средине спискаLLNode newfirst= 11с.AddObject(null,"Перед первой с т р о к о й " ) ;LLNode newmiddle= 11с.AddObject(second, "Между второй и " +"третьей с т р о к о й " ) ;// Итератором можно управлять "вручную"Console.WriteLine("Проход по контейнеру в р у ч н у ю " ) ;LinkedListlterator H i= (LinkedListlterator)11с.GetEnumerator();H i .
Reset () ;while ( H i .MoveNext () ){string s = (string) Hi . Current ;Console.WriteLine(s);}// Либо использовать цикл foreachConsole.WriteLine("\пОбход с использованием foreach");foreach(string s in 11c){Console.WriteLine(s);}// Ожидаем подтверждения пользователяConsole.WriteLine("Нажмите <Enter> для " +"завершения п р о г р а м м ы . . . " ) ;Console.Read();}}Классы LinkedList и LLNode образуют фундамент приведенной демонстрационной программы. На рис. 20.1 показан связанный список с тремя узлами, каждый из которых указывает на (или "содержит") отдельную строку, так что LinkedList вполне заслуживает названия "контейнер".
Лично я, впрочем, как и большинство в мире .NET,предпочитаю термин коллекция.Узлы в связанном списке представлены объектами LLNode. Для каждого данного узла член forward указывает на следующий узел в списке, а член backward —на предыдущий. Класс LinkedList представляет сам список.
Член head указывает на первый узел списка, член tail — на последний. По сути, это все, что естьв данном классе.456Часть VII. Дополнительные главыРис. 20.1. КлассыL i n k e d L i s tиLLNodeсовместно создают связанный списокДобавление объекта в связанный списокОсновные сложности содержатся в методах AddObject ОСначала рассмотрим метод AddOb j ect ().и RemoveObject ().Для того чтобы добавить объект в список, вы должны знать, куда именно его нужнопоместить. По существу, имеется четыре ситуации.1.
Вы добавляете новый объект в пустой список. Это простейшая из всех ситуаций;она показана на рис. 20.2. Указатель head равен null, как и указатель tail.Следует просто заставить указывать их на добавляемый элемент, и на этом все —вы получите список с одним узлом.Рис. 20.2. Добавление нового узла в пустойсвязанный список выполняется в два счета2. Наиболее сложная ситуация — это добавление элемента в середину списка.В этом случае предыдущий и следующий узлы не равны null. На рис. 20.3 показана такая ситуация.
Чтобы вставить объект в середину списка, следует настроитьуказатели forward и backward как вставляемого объекта, так и объектов, рас-Глава 20. Работа с коллекциями457положенных по сторонам от места, куда он будет вставлен. На рис. 20.4 представлен результат (показанные шаги очень важно делать в определенном порядке,чтобы не "потерять" часть списка из-за того, что у вас не останется ссылки на нееВы можете следовать порядку, показанному в приведенном исходном тексте демонстрационной программы).Рис. 20.3. Перед вставкой в список объект не связан ни с чемРис.
20.4. После вставки объекта в список он становится частью команды458Часть VII. Дополнительные главыРис. 20.5. Добавление объекта в голову списка делает его первымв списке3. Объект может быть добавлен и в голову списка. Это гибрид первых двух случаев.Указатель на голову списка после вставки должен указывать на новый объект,а старый первый объект списка после вставки должен указывать на вставленныйузел, как на предыдущий в списке. Все это продемонстрировано на рис. 20.5.4.
И наконец, новый объект может быть вставлен в конец списка. Это ситуация, обратная случаю 3.Удаление объекта из связанного спискаМетод R e m o v e O b j e c t () рассматривает те же четыре ситуации, но в обратном направлении.Единственный способ следовать A d d O b j e c t () и R e m o v e Ob j e c t () — нарисовать рисунки наподобие рис.
20.2-20.5 и аккуратно пройти каждый шаг. Нестесняйтесь — не родился еще программист, который в подобной ситуации ниразу не рисовал бы рисунка для того, чтобы разобраться во всем. Сложные вещи остаются сложными независимо от того, кто с ними работает.Реализация перечислителя связанного спискаОбратите внимание, что демонстрационная программа L i n k e d L i s t C o n t a i n e rв действительности содержит три класса: L L N o d e , L i n k e d L i s t и L i n k e d L i s t l t e r a t o r . Класс L i n k e d L i s t l t e r a t o r — сопутствующий связанному списку класс с оспециальными привилегиями. Он в деталях знаком с внутренним устройством связанного списка, которое недоступно никому во внешнем мире.
Внешние клиенты используютего для итерирования связанного списка.Класс L i n k e d L i s t l t e r a t o r работает путем отслеживания текущего и следующего за ним узла. Изначально c u r r e n t N o d e равен n u l l , a n e x t N o d e — первому элементу связанного списка. После каждого вызова M o v e N e x t () c u r r e n t N o d e указываетна то, что перед этим было следующим узлом, a n e x t N o d e перемещается к следующемуза ним узлу. После того как M o v e N e x t () достигает конца списка, c u r r e n t N o d e равноГлава 20. Работа с коллекциями459n u l l , и функция отвергает все дальнейшие вызовы, возвращая для каждого из них значение f a l s e . Лучше не оказываться за концом списка.Функция M a i n () демонстрирует использование связанного списка, сначала добавляяв него три строки s t r i n g .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
