Главная » C# » Код для алгоритма поиска в глубину на Visual C# (Sharp)

0

Алгоритм поиска в глубину будет реализован в три основных  этапа.  На  первом этапе определяется и реализуется структура данных. На втором этапе реализуются алгоритм и тесты. На последнем этапе алгоритм запускается в рабочем  режиме, чтобы проверить, какой маршрут он сгенерирует.

Определение и реализация структуры данных

Как было  упомянуто ранее, программисты чаще используют ссылочные  типы по причине ограничений,  присущих обычным типам. Но для этого примера мы опрелим узел Node с помощью ключевого слова struct, т. е. как обычный тип. Алгитм поиска в глубину реализуется как два отдельных компонента: структура даых и собственно алгоритм. Поэтому определение Node как обычного типа кажется приемлемым. По крайней мере, попробуем и посмотрим, что из этого получится.

Согласно атрибутам, показанным на рис. 4.7, требуемая для проекта searchsoiution

структура данных реализована, как показано на рис. 4.9.

Рис. 4.9. Структура данных для поиска в глубину

Структура данных объявляется  с  помощью  ключевого  слова struct, а пересадки в этой структуре представлены массивом элементов Node. Массив элементов Node создается, когда один узел Node содержит список ссылок на другие элементы Node. Массив можно рассматривать, как набор заметок, содержащих ссылки наточки А, В и С. Когда один узел ссылается на другой узел, создается что-то вроде бесконеого дерева, т. к. имеется возможность бесконечно путешествовать туда и обратно из одного города в другой. Таким образом, алгоритму поиска в глубину необходо будет избегать повторения самого себя.

Элемент данных connections представляет собой  массив,  определяющий  города, в которые имеются пересадки в текущем городе. Города пересадок можно создать в виде массива элементов Node, как объявление, показанное на рис. 4.9. В качестве альтернативы можно применить массив строк, содержащих название города:

public struct Node { public string CityName; public double X;

public double Y;

public String[] Connections;

}

В данном объявлении connections является строкой, содержащей названия горов, которые выводились бы на табло, показывающее все пересадки в другие гора из  данного города. Но использование строк неэффективно в вычислительном аспекте. Со строками, чтобы обойти дерево городов, сначала нужно обойти назвия городов, сопоставить название города с типом Node и только потом можно оодить узел.  Таким образом, подход с использованием массива строк требует волнения дополнительной необязательной операции.  Поэтому более эффективным и прагматичным подходом будет применение массива экземпляров Node.

Использование объявления, в котором Connections является массивом элементов Node, позволяет размещать имя города и города пересадок в одном элементе. Это позволяет избежать разработки алгоритма для поиска города и связанных с ним городов пересадок. Вместо этого можно применить алгоритм для прохода по структуре, не прибегая к операции поиска и сопоставления.

Самоссылающиеся структуры

Интересная информация, которую следует помнить: если объявить структуру Node, в которой член connections ссылается только на один экземпляр Node, компилор С# выдаст ошибку об узле, ссылающемся на самого себя. Пример объявления самоссылающейся структуры приводится в следующем фрагменте кода:

public struct Node { public string CityName; public double X;  public double Y;

public Node Connections;

Проблема с данным объявлением заключается в том, что обычные типы имеют фиксированный размер, но поскольку член структуры типа Node объявляется в сой структуре Node, то компилятор не может определить размер объявленной структуры. Объявление структуры Node, содержащей массив членов типа Node, не представляет для компилятора проблем, т. к. явно объявляется массив неизвестного размера, в результате чего объявление массива считается ссылочным типом.

Создание экземпляра узла и его инициализация

В предыдущих примерах кода мы видели, как можно создавать экземпляры объеов с помощью ключевого слова new. Экземпляры типов всегда создаются с помью ключевого слова new. После него следует имя типа, экземпляр которого создтся, и открывающая и закрывающая скобки. Для создания экземпляра типа Node применяется следующий код:

Node city = new Node();

Если из этого кода рассматривать только идентификатор Node со скобками, то мет создаться впечатление, что вызывается метод без параметров. Это будет прильное впечатление, но это особый вид вызова метода, что обозначается примением ключевого слова new. Вызываемый метод называется конструктором. Каждый тип имеет свой конструктор, который инициализирует состояние объекта, прежде чем возвратить его вызывающему коду.

ПРИМЕЧАНИЕ

Термины   "класс"  и   "структура"  означают  объявление  типа.  А  термин   "объект"  ознает экземпляр объявленного типа.

В объявлении типа Node конструктор не объявляется, поэтому среда CLR предтавляет для него стандартный конструктор. Стандартный конструктор ничего не делает и не имеет параметров.

После создания объекта узла его членам данных можно присваивать значения:

city.CityName = "Montreal"; city.X = 0.0;

city.Y = 0.0;

В результате присваивается наименование города Монреаль (Montreal), с коордатами (0, 0).

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

Надлежащее верифицируемое начальное состояние экземпляра можно устанавлать принудительно, определив конструктор с параметрами вместо использования стандартного конструктора. Когда конструктор предоставляется кодом пользоватя, то независимо от объявления, стандартный конструктор не генерируется и яяется недоступным. Далее приводится пример определения пользовательского конструктора,

public struct Node {

public static Node[] RootNodes; public string CityName;

public double X; public double Y;

public Node[] Connections;

public Node(string city, double x, double y) {

CityName = city;

X = х;

Y = у;

Connections = null;

}

}

ПРИМЕЧАНИЕ

В предыдущем коде используется тип null. Это предопределенный специальный тип, который означает, что данные  ни  на  что  не  указывают  или  программно  определены как null.

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

То обстоятельство, что пользовательский конструктор имеет параметры, означает, что для создания экземпляра типа Node необходимо предоставить три элемента данных. Таким образом, чтобы узел имел смысл,  для  создания  экземпляра типа Node необходимо предоставить достаточно данных. Первоначальный код для соания экземпляра класса в данном случае не скомпилируется; для этого его неоодимо модифицировать следующим образом:

Node city = new Node("Montreal", 0.0, 0.0);

При объявлении узла данные, к которым выполняется обращение, могут быть нравильными, но это уже не входит в круг ответственности разумной структуры данных. Подобным образом, текстовый редактор не отвечает за то, чтобы обрабываемый в нем текст имел какой-либо смысл. Создание смыслового текста явлтся ответственностью пользователя, а роль текстового редактора ограничивается предоставлением возможности создания такого текста.

Проблема с обращением к обычным типам

Как рассматривалось ранее, значения переменных обычных типов хранятся в стеке, и при присваивании  переменной значения другой переменной первой переменной присваивается копия значения второй переменной, а не ссылка на общее для обеих переменных значение. При создании древовидной структуры с применением обыых типов возникает проблема, состоящая в том, что присвоенные значения не оовляются,  т. к.  значения  копируются.  Этот  эффект  можно  продемонстрировать с помощью более обширного примера создания структуры данных городов, на корые есть пересадка в другом городе. Начнем со следующего объявления всех годов и их координат:

Node montreal   = new Node("Montreal", 0, 0); Node newyork    = new Node("New York", 0, -3);

Node miami      = new Node("Miami",  -1, -11); Node toronto   = new Node("Toronto", -4, -1) ;  Node houston   = new Node("Houston", -10, -9) ; Node losangeies = new Node("Los Angeles", -17, -6); Node Seattle   = new Node("Seattle", -16, -1) ;

В данном коде создаются переменные, представляющие все города, показанные на рис. 4.7. Для каждой из этих переменных создается и присваивается экземпляр типа Node, инициализированный названием города и его координатами. Отдельные пеменные представляют города без информации о пересадках, поэтому следующим шагом мы свяжем города между собой. Для этого нам необходимо выделить член данных Connections и присвоить ему значение.

Соответствующий код для инициализации члена данных Connections узла Montreal данными о пересадках в другие города будет выглядеть следующим образом:

montreal.Connections = new Node[3J; montreal.Connections[0i = newyork; montreal.Connections[1] = toronto; montreal.Connections[2] = losangeies;

При присвоении члену данных Connections массива экземпляров типа Node просто выделяется память под данный массив, экземпляры же типа не создаются.  Это можно сравнить с покупкой пустого бумажника, чтобы было, куда класть наличные и кредитные карточки. Поэтому конструктор объектов не вызывается, т. к. никакие объекты не создаются.

После того как было выделено место под массив, элементам массива можно прваивать экземпляры типа. Альтернативным способом было бы создать экземпляр массива и присвоить экземпляры узлов его элементам.

Обратите внимание на то, что индексы массива указываются в квадратных скобках. Не забывайте, что в С# счет элементов массива начинается с 0. Поэтому в трехэлентном массиве индекс первого элемента будет 0, а последнего — 2.

Рассмотрим, что же происходит в данном коде. Мы объявили массив, т. е. выдели память под него, после чего присвоили переменные, представляющие города, каждому элементу массива. Но т. к. массив Connections является массивом обыого типа, ТО значения членов данных Connections В членах данных Connections элементов массива не устанавливаются. Это обстоятельство для элемента New York массива (члена данных) Connections узла Montreal показано на рис. 4.10.

Конечно же, это обстоятельство можно логически объяснить тем фактом, что член данных Connections для узла New York еще не был определен. Подумайте о том, каким образом происходит обращение к данным, и освежите в памяти  информию, приведенную в табл. 4.1.

Node является обычным типом, а при присваивании переменной обычного типа другой переменной данного типа, значение первой переменной копируется во вторую.

Рис. 4.10. Проблема отсутствующей информации о пересадках

Так как элементам массива (членам данных) Connections для узла New York еще не были присвоены значения, то член данных Connections узла New York для узла Montreal не будет иметь никаких значений для пересадок. И если модифицировать первоначальную переменную узла New York, присвоив значения его элементам массива (членам данных) Connections, то эти модификации не отразятся в члене данных Connections узла New York ДЛЯ узла Montreal или для любого другого узла.

На данной стадии можно подумать, что это не представляет никакой проблемы, но посмотрите на следующий код, назначающий пересадки для узла New York.

newyork.Connections = new Node[3]; newyork.Connections[0] = montreal; newyork.Connec t i ons[1] = hous ton; newyork.Connections[2] = miami;

Мы ВИДИМ, ЧТО New York имее т пересадк у на Montreal, а МЫ знаем , ЧТО Montreal имеет пересадку на New York. Пассажиры, совершающие регулярные поездки меу этими двумя городами, хотели бы  иметь возможность постоянно летать туда и обратно между Нью-Йорком и Монреалем. Но использование переменных обычно типа не позволяет этого (рис. 4.11).

Как можно видеть на рис. 4.11, обычные типы нельзя использовать рекурсивно. Видно, что из Нью-Йорка есть рейсы на Монреаль. Но, прилетев в Монреаль, мы видим, что если мы полетим обратно в Нью-Йорк, то снова лететь в Монреаль мы не сможем. Это очевидная ложь, т. к. мы только что прилетели из Нью-Йорка в Монреаль.

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

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

Рис. 4.11. Пропавшие рейсы (пересадки) из Нью-Йорка

Замена struct на class для определения узла

Чтобы решить  проблему курицы и  яйца, необходимо вместо обычных типов пренять ссылочные. Код для объявления типа Node с помощью ключевого слова class будет выглядеть таким образом (изменения выделены жирным шрифтом):

public class Node { public string CityName; public double X;  public double Y;

public Node[] Connections;

public Node(string city, double x, double y) { CityName = city;

X = x; Y = y;

Connections = null;

}

}

Как видно, модификация затронула всего лишь одну строчку кода. После этой мификации выполнение кода из предыдущего раздела, присваивающего значения массиву Connections, создаст такую структуру данных (рис. 4.12).

Рис. 4.12. Правильное состояние массива Connections для узла New York

Теперь у нас есть рейсы между Нью-Йорком и Монреалем. Бесконечная цепочка членов данных Connections не. означает, что мы используем бесконечные ресурсы для ее представления.  В действительности,  просто одна ссылка указывает на друю, а та обратно на первую (рис. 4.13).

Рис. 4.13. Рекурсивное присваивание создает впечатление необходимости бесконечных ресурсов

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

типов программисты довольно часто заблуждаются, полагая, что определенным переменным или членам данных были присвоены значения, когда в действительнти этого не произошло.

Статические члены данных и методы

Ранее мы  видели, как конкретный экземпляр типа можно  инициализировать с  пощью конструктора. Теперь нам нужно определить конструктор для древовидной структуры на рис. 4.2. Древовидная структура подразумевает начальную точку для ее прохождения, но схема пересадок не имеет одной начальной точки. Что у нас имеется, так это несколько объявленных переменных, чьи идентификаторы претавляют города.

Проблема с таким объявлением состоит в том, что для обхода древовидной струуры необходимо знать имена каждой  переменной  и обходить дерево для  каждой из них. Это решение не является приемлемым. Нам нужно создать одну общую нальную точку, из которой можно обращаться ко всем городам.

Эту задачу можно решить, добавив в объявление класса Node массив, подобный массиву для члена данных Connections. Соответствующая модификация выделена жирным шрифтом в следующем коде:

public class Node {

public static Node[] RootNodes;

public string CityName; public double X;

public double Y;

public Nodefi Connections;

public Node(string city, double x, double y) { CityName = city;

X = x; Y = y;

Connections = null;

}

}

Добавленный член данных имеет модификатор static. Разберемся, что это означт в данном контексте.

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

Купленные  вами  мобильные  телефоны  также  имеют  возможность  прямой  связи. В сущности, эта возможность позволяет использовать мобильный телефон как радиостанцию. Все члены вашей семьи активируют эту возможность. Это означает, что когда кто-то из вас разговаривает, используя эту возможность, слышать  его может не только его непосредственный собеседник, но и все остальные члены сьи. Более того, все члены семьи могут говорить (в смысле не слушать) одновренно.  Таким образом,  прямая связь является общим  ресурсом,  не связанным  ни с каким конкретным мобильным телефоном. В случае с классами, словом static обозначаются общие ресурсы класса, не связанные с каким-либо определенным экземпляром типа.

Обозначая член данных класса ключевым словом static, мы говорим, что, несмотря на то, сколько экземпляров класса Node мы создаем, для них всех в любой момент имеется только один экземпляр члена данных RootNodes. Более того, чтобы обриться к члену данных RootNodes, не обязательно создавать экземпляр класса Node. Статические методы подобны статическим членам данных в том, что они являются общим ресурсом и не ассоциируются с конкретным объектом (как демонстрируется методом Main (), который запускает консольное приложение на исполнение).

На рис. 4.14 показано, что можно и что нельзя делать со статическими и нестатичкими членами данных.

Рис. 4.14. Разрешенные и запрещенные операции со статическими и нестатическими членами данных

5 Зак   555

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

Возвратимся к нашему объявлению класса Node. Для определения единого корня для дерева поиска используется статический член данных RootNodes. Для создания экземпляра типа применяется конструктор для статического типа, который вызывтся при каждом обращении к статическому методу или  члену данных.  Статичкий конструктор такой же, как и ранее определенный конструктор, только вместо ключевого слова public в нем используется ключевое слово static. В случае с девом поиска этот конструктор применяется для инициализации дерева и его состояния.

Теперь мы имеем полное определение класса Node, которое показано в следующем коде. Не премините исследовать его и разобраться, каким образом отдельные фрагменты взаимодействуют друг с другом.

public class Node {

public static Node[] RootNodes; public string CityName;

public double X; public double Y;

public Node[] Connections;

public Node(string city, double x, double y) { CityName = city;

X = x; Y = y;

Connections = null;

}

static Node() {

Node montreal  = new Node("Montreal", 0, 0) ; Node newyork   = new Node("New York", 0, -3) ; Node miami      = new Node("Miami", -1, -11); Node toronto   = new Node("Toronto", -4, -1) ; Node houston   = new Node("Houston", -10, -9);

Node losangeles = new Node("Los Angeles", -17, -6);

Node Seattle   = new Node("Seattle", -16, -1);

montreal.Connections = new Node[3]; montreal.Connections[0] = newyork; montreal.Connections[1] = toronto;

montreal.Connections[2] = losangeles;

newyork.Connections = new Node[3]; newyork.Connections[0] = montreal; newyork.Connections[1] = houston; newyork.Connections[2] = miami;

miami.Connections = new Node[3]; miami.Connections[0] = toronto; miami.Connections[1] = houston; miami.Connections[2] = newyork;

toronto.Connections = new Node[3]; toronto.Connections[0] = miami; toronto.Connections[1] = Seattle; toronto.Connections[2i = montreal;

houston.Connections = new Node[3]; houston.Connections[0] = miami; houston.Connections[1] = Seattle; houston.Connections[2] = newyork;

Seattle.Connections = new Node[3]; Seattle.Connections[0] = toronto; Seattle.Connections[1] = houston; Seattle.Connections[2] = losangeles;

losangeles.Connections = new Node[3]; losangeles.Connections[0] = montreal; losangeles.Connections[li = Seattle; losangeles.Connections[2] = houston;

Node.RootNodes = new Node[7]; Node.RootNodes[0] = montreal; Node.RootNodes[1] = newyork; Node.RootNodes[2] = miami; Node.RootNodes [3.] = toronto; Node.RootNodes[4] = houston; Node.RootNodes[5i = losangeles;

Node.RootNodes[6i = Seattle;

}

}

Источник: Гросс  К. С# 2008:  Пер. с англ. — СПб.:  БХВ-Петербург, 2009. — 576 е.:  ил. — (Самоучитель)

По теме:

  • Комментарии