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

0

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

ПРИМЕЧАНИЕ

Создание кода,  который  локализирует  изменения,  не  затрагивая  другие  фрагмент ы кода, называется развязыванием (decoupling) кода, по  аналогии  с  развязыванием электрических цепей. Изолированный  таким  образом  код  позволяет  экспериментирать с  ним,  не  затрагивая  работоспособность  других  фрагментов  кода.  Как  вы  увиде, в процессе разработки  развязывание  кода  является  ежедневны м  испытание м  вих  знаний  и  способностей  как  программиста.

Теперь разработаем первую версию  алгоритма  поиска  и  посмотрим,  что  у  нас  из это ю получится. Мы можем начать с определения класса поиска или с  определения теста для проверки класса поиска. Сначала определим тест, т. к. это позволит нам выяснить,  каким  должен  быть  класс  поиска.  Начнем  со  следующего определения:

public static void TestSearchO { SearchSolution.SearchAlgorithm.DepthFirstFindRoute("Montreal", "Seattle");

}

В коде теста алгоритм поиска вызывается непосредственным образом с помощью метода SearchAlgorithm.DepthFirstFindRoute(). Идентификатор SearchAIgorithm является  именем  класса,  а  идентификатор  DepthFirstFindRoute()  —  именем  мета этого класса. Такой способ именования подразумевает, что данный класс будет содержать  реализации  всех  компонентов  поискового  алгоритма.  Но  это  неправильно, т. к. весь алгоритм поиска не может содержаться в одном методе.  Скорее  всего, для него потребуется несколько методов. Но если для каждого алгоритма поиска нужно несколько методов, то поддержка класса searchAigorithm станет  кошмаром для программиста.

Лучшим решением было бы реализовать каждый вариант алгоритма поиска в оельном классе. Тогда для каждого класса мы сможем определить общий идентикатор метода для нахождения маршрута между двумя точками. Соответственно модифицированный  код  теста  будет  выглядеть  так:

public static void TestSearchO { SearchSolution.DepthFirstSearch.FindRoute("Montreal", "Seattle");

}

Теперь тест подразумевает, что класс DepthFirstSearch имеет статический метод FindRoute (). Это приемлемо,  и  при  реализации  класса BreadthFirstsearch ссылка на ЭТОТ метод будет В виде SearchSolution.BreadthFirstsearch.FindRoute. Но здесь имеется другая проблема, связанная с возможностью использования алгоритма несколькими   пользователями   при   выполнении   программы.  Как  мы   выяснили   при

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

Более подходящим решением будет определение метода FindRouteO нестатичким, подразумевая этим, что прежде чем вызывать метод FindRouteO, необходо создать экземпляр класса DepthFirstsearch. Соответственно, модифицироваый код теста будет таким:

public static void TestSearch() { SearchSolution.DepthFirstsearch els =

new SearchSolution.DepthFirstsearch();

els.FindRoute("Montreal", "Seattle");

}

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

Проблема "волшебных" данных

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

В реализации класса DepthFirstsearch необходимо обращаться к структуре даых. Также алгоритм поиска должен знать, какое дерево обходить. Одним из спобов обращения к дереву будет прямое обращение к статическим данным Node.RootNodes. Код для соответствующей реализации класса DepthFirstsearch() таков:

public class DepthFirstsearch { public DepthFirstsearch() {

}

public void FindRoute(string start, string end) {

Node[] startNodes = Node.RootNodes;

}

}

В данном фрагменте кода объявляется переменная startNodes, которая предстаяет начальную точку и корень дерева (см. рис. 4.2). Корень дерева основан на чле данных Node.RootNodes, и этот тип присваивания называется присваиванием волшебного типа. Волшебный тип создается,  когда вызываемый метод волшебным

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

RootNodes.

Это плохое предположение, т. к. оно связывает член данных RootNodes с методом FindRoute (). Представьте, что будет, если в будущем разработчик класса Node рит добавить функциональную возможность загрузки дерева с жесткого диска. Чтобы не нарушить метод FindRoute о, разработчику придется явным образом кировать загружаемое с диска дерево в член данных RootNodes.

Или что произойдет, если два пользователя захотят создать разные деревья марутов? Член данных Nodes .RootNodes является общим ресурсом и поэтому может обрабатывать только одно дерево маршрутов. Разработчик класса Node может иенить член данных RootNodes, что вызовет ошибки в работе метода FindRoute ().

Когда мы работаем с "волшебными" данными, то какие бы данные у нас не были, типу необходимо передать волшебство. Поэтому тест для проверки метода нахоения маршрута полета будет изменен следующим образом:

public static void TestSearchO { SearchSolution.DepthFirstSearch els =

new  SearchSolution.DepthFirstSearch(SearchSolution.Node.RootNodes);

els.FindRoute("Montreal", "Seattle");

}

Так  как  нам  необходим  корневой узел  дерева,  мы  изменяем  конструктор,  чтобы в нем требовалось, чтобы вызывающий компонент передавал вызываемому методу корневой узел дерева. В тестовом коде продолжается использоваться статический член данных RootNodes, но методу DepthFirstSearch ()  не обязательно знать, где найти дерево. Если теперь разработчик класса Node изменит поведение члена даых RootNodes, то будет необходимо изменить лишь код конструктора для метода DepthFirstSearch (), а не сам метод. Таким образом, классы Node И DepthFirstSearch изолированы (развязаны) друг от друга.

Получение найденного маршрута

Вызвав метод FindRoute (), мы вправе ожидать от него ответа. Так как найденный маршрут может содержать несколько городов, то он сохраняется в массиве элемеов Node. Программно массив элементов Nodes можно получить двумя способами. Первый способ состоит в применении значения возвращаемого параметра:

public static void TestSearchO { SearchSolution.DepthFirstSearch els =

new  SearchSolution.DepthFirstSearch(SearchSolution.Node.RootNodes);

Node[] foundRoute = els.FindRoute("Montreal", "Seattle");

}

Код для  присваивания  возвращаемого  значения  переменной  foundRoute выделен жирным шрифтом.

Второй способ заключается в использовании члена данных:

public static void TestSearchO { SearchSolution.DepthFirstsearch els =

new  SearchSolution.DepthFirstsearch(SearchSolution.Node.RootNodes);

els.FindRoute("Montreal", "Seattle");

Node[] foundRoute = els.FoundRoute;

}

В этом подходе найденный маршрут сохраняется в члене данных FoundRoute. Стветствующий код выделен жирным шрифтом.

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

В случае с нахождением одного маршрута каждый подход является приемлемым. Но посмотрим на код, когда необходимо найти несколько маршрутов. Сначала рамотрим код, в котором найденный маршрут возвращается в значении параметра: public static void TestSearchO {

SearchSolution.DepthFirstsearch els =

new  SearchSolution.DepthFirstsearch(SearchSolution.Node.RootNodes);

Node[] fcrundRoutel = els.FindRoute("Montreal", "Seattle"); Node[] £oundRoute2 = els.FindRoute("New York", "Seattle");

}

А теперь  посмотрим  на  код,  в  котором  найденный  путь  возвращается  как член данных:

public static void TestSearchO { SearchSolution.DepthFirstsearch els =

new  SearchSolution.DepthFirstsearch(SearchSolution.Node.RootNodes); els.FindRoute^"Montreal", "Seattle");

Node[] foundRoute1 = els.FoundRoute; els.FindRoute("New York", "Seattle"); Node[] foundRoute2 = els.FoundRoute;

}

И снова оба решения выглядят достаточными. Но в данном случае есть тонкая, но весьма важная разница. В реализации теста, в котором найденный маршрут воращается в значении параметра, переменные foundRoutel и foundRoute2 претавляют маршруты, прямым образом связанные с маршрутом, для которого волняется поиск. Переменные foundRoutel никоим образом не могут представлять маршрут "Нью-Йорк — Сиэтл". А в случае кода с членом данных, может случить-

ся,  что  переменная  f oundRoutel будет указывать на маршрут "Нью-Йорк — Сиэтл", как показано  в следующем  коде,

public static void TestSearchO { SearchSolution.DepthFirstSearch els =

new SearchSolution.DepthFirstSearch(SearchSolution.Node.RootNodes);

els.FindRoute("Montreal", "Seattle"); els.FindRoute("New York", "Seattle"); Node[ ]    foundRoute 1   =   els.FoundRoute ; Node[ ]    £oundRoute 2   =   els.FoundRoute ;

}

Если поменять порядок вызовов метода FindRoute()  и ссылки на член данных FoundRoute, то   переменные   foundRoutel и   foundRoute2 будут  ссылаться   на  один и тот же  найденный  маршрут,  в  частности,  на  маршрут  "Нью-Йорк —  Сиэтл".  Это не  хорошо.  Пример демонстрирует,  как  члены  данных  не  связаны  непосредственно с  методами  и  могут независимо меняться.

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

ПРИМЕЧАНИЕ

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

Далее приводится полный контрольный пример, включая  код  верификации,  котый  ищет маршрут из Монреаля  в Сиэтл.

public static void TestSearchO { SearchSolution.DepthFirstSearch els =

new SearchSolution.DepthFirstSearch(SearchSolution.Node.RootNodes); SearchSolution.Node[] foundRoute = els.FindRoute("Montreal", "Seattle"); if (foundRoute.Length != 2) {

Console.WriteLine("Incorrect route as route has two legs");

}

if (foundRoute[OJ.CityName.CompareTo("Los Angeles") != 0) { Console.WriteLinet"Incorrect as first leg is Los Angeles");

}

}

ПРИМЕЧАНИЕ

Мы  уже  применял и  конструкцию   if  в  предыдущих  главах.  В  ней  проверяется  условие, и в случае положительного результата проверки выполнятся код в фигурных скобках. Комбинация символов ! = означает "не равно". Оператор i f более подробно рассмаивается    в   разд.        "Оператор    if"   далее     в    этой    главе.

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

По теме:

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