Визначення тесту для алгоритму пошуку в глибину на Visual C # (Sharp)

Тип Node є автономним типом Це означає, що алгоритмом не потрібно створювати екземпляр деревовидної структури Це приклад хорошого Проектуванн, т к в разі необхідності додати нові міста потрібно буде змінити тільки сам тип Node Будь алгоритм пошуку, що використовує тип Node, змінювати не буде потрібно

ПРИМІТКА

Створення коду, який локалізує зміни, не зачіпаючи інші фрагмент и коду, називається розвязуванням (Decoupling) коду, за аналогією з розвязуванням електричних ланцюгів Ізольований таким чином код дозволяє експеріментірать з ним, не зачіпаючи працездатність інших фрагментів коду Як ви побачите, в процесі розробки розвязування коду є щоденне м випробування м вих знань і здібностей як програміста

Тепер розробимо першу версію алгоритму пошуку і подивимося, що у нас з це ю вийде Ми можемо почати з визначення класу пошуку або з визначення тесту для перевірки класу пошуку Спочатку визначимо тест, т к це дозволить нам зясувати, яким повинен бути клас пошуку Почнемо з наступного визначення:

public static void TestSearchO { SearchSolutionSearchAlgorithmDepthFirstFindRoute(&quotMontreal&quot, &quotSeattle&quot)

}

У коді тесту алгоритм пошуку викликається безпосереднім чином за допомогою методу SearchAlgorithmDepthFirstFindRoute () Ідентифікатор SearchAIgorithm є імям класу, а ідентифікатор DepthFirstFindRoute () – Імям мета цього класу Такий спосіб іменування увазі, що даний клас буде містити реалізації всіх компонентів пошукового алгоритму Але це неправильно, т к весь алгоритм пошуку не може міститися в одному методі Швидше за все, для нього буде потрібно кілька методів Але якщо для кожного алгоритму пошуку потрібно кілька методів, то підтримка класу searchAigorithm стане кошмаром для програміста

Кращим рішенням було б реалізувати кожен варіант алгоритму пошуку в оельном класі Тоді для кожного класу ми зможемо визначити загальний ідентікатор методу для знаходження маршруту між двома точками Відповідно модифікований код тесту буде виглядати так:

public static void TestSearchO { SearchSolutionDepthFirstSearchFindRoute(&quotMontreal&quot, &quotSeattle&quot)

}

Тепер тест на увазі, що клас DepthFirstSearch має статичний метод FindRoute () Це прийнятно, і при реалізації класу BreadthFirstsearch посилання на ЦЕЙ метод буде У вигляді SearchSolutionBreadthFirstsearchFindRoute Але тут є інша проблема, повязана з можливістю використання алгоритму декількома користувачами при виконанні програми Як ми зясували при

обговоренні можливості прямого звязку мобільного телефону, метод FindRouteO є статичним, що робить його загальним ресурсом Якщо кілька пользоватей буде використовувати цей алгоритм одночасно, вони стануть розділяти цей ресурс Це може викликати проблеми, якщо тимчасові дані зберігаються в члах даних класу DepthFirstseach Використання статичного методу може вилитися в неправильному знайденому маршруті

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

public static void TestSearch() { SearchSolutionDepthFirstsearch els =

new SearchSolutionDepthFirstsearch()

elsFindRoute(&quotMontreal&quot, &quotSeattle&quot)

}

Щоб виконати метод FindRouteO, нам необхідно спочатку створити екземпляр класу DepthFirstsearch, що дозволить декільком користувачам виконувати пск, не змішуючи стану пошуку різних користувачів На даному етапі ми можемо похвалити себе за кмітливість і вважати, що ми написали хороший тест, для якого потрібно створити клас

Проблема чарівних даних

Наш тест ще не закінчений, тому що у нас ще немає доступу до маршруту, знайденому аорітмом, але ми з цим розберемося трохи пізніше На даний момент будемо вважати, що знайдений маршрут просто впав нам з неба

У реалізації класу DepthFirstsearch необхідно звертатися до структури даих Також алгоритм пошуку повинен знати, яке дерево обходити Одним з споб звернення до дерева буде пряме звернення до статичних даними NodeRootNodes Код для відповідної реалізації класу DepthFirstsearch () такий:

public class DepthFirstsearch { public DepthFirstsearch() {

}

public void FindRoute(string start, string end) {

Node[] startNodes = NodeRootNodes

}

}

У цьому фрагменті коду оголошується змінна startNodes, яка предстаящую початкову точку і корінь дерева (див рис 42) Корінь дерева заснований на чле даних NodeRootNodes, і цей тип присвоювання називається привласненням чарівного типу Чарівний тип створюється, коли викликається метод чарівним

чином знає, яким чином звертатися до даних, незважаючи на те, що ви нікда не давали типу інструкцій про це У випадку методу DepthFirstsearch () воебним є його здатність звертатися до правильного члену даних

RootNodes

Це погане припущення, т к воно повязує член даних RootNodes з методом FindRoute () Уявіть, що буде, якщо в майбутньому розробник класу Node рит додати функціональну можливість завантаження дерева з жорсткого диска Щоб не порушити метод FindRoute про, розробнику доведеться явним чином кіровать завантажуване з диска дерево в член даних RootNodes

Або що станеться, якщо два користувачі захочуть створити різні дерева марутів Член даних Nodes RootNodes є загальним ресурсом і тому може обробляти тільки одне дерево маршрутів Розробник класу Node може іеніть член даних RootNodes, що викличе помилки в роботі методу FindRoute ()

Коли ми працюємо з чарівними даними, то які б дані у нас не були, типу необхідно передати чарівництво Тому тест для перевірки методу нахоенія маршруту польоту буде змінено таким чином:

public static void TestSearchO { SearchSolutionDepthFirstSearch els =

new  SearchSolutionDepthFirstSearch(SearchSolutionNodeRootNodes)

elsFindRoute(&quotMontreal&quot, &quotSeattle&quot)

}

Так як нам необхідний кореневий вузол дерева, ми змінюємо конструктор, щоб у ньому було потрібно, щоб викликає компонент передавав викликається методом кореневий вузол дерева У тестовому коді триває використовуватися статичний член даних RootNodes, але методом DepthFirstSearch () не обовязково знати, де знайти дерево Якщо тепер розробник класу Node змінить поведінку члена даих RootNodes, то буде необхідно змінити лише код конструктора для методу DepthFirstSearch (), а не сам метод Таким чином, класи Node І DepthFirstSearch ізольовані (розвязані) один від одного

Отримання знайденого маршруту

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

public static void TestSearchO { SearchSolutionDepthFirstSearch els =

new  SearchSolutionDepthFirstSearch(SearchSolutionNodeRootNodes)

Node[] foundRoute = elsFindRoute(&quotMontreal&quot, &quotSeattle&quot)

}

Код для присвоювання значення, що повертається змінної foundRoute виділений жирним шрифтом

Другий спосіб полягає у використанні члена даних:

public static void TestSearchO { SearchSolutionDepthFirstsearch els =

new  SearchSolutionDepthFirstsearch(SearchSolutionNodeRootNodes)

elsFindRoute(&quotMontreal&quot, &quotSeattle&quot)

Node[] foundRoute = elsFoundRoute

}

У цьому підході знайдений маршрут зберігається в члені даних FoundRoute Стветствующій код виділений жирним шрифтом

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

У випадку з знаходженням одного маршруту кожен підхід є прийнятним Але подивимося на код, коли необхідно знайти кілька маршрутів Спочатку рамотрім код, в якому знайдений маршрут повертається в значенні параметра: public static void TestSearchO {

SearchSolutionDepthFirstsearch els =

new  SearchSolutionDepthFirstsearch(SearchSolutionNodeRootNodes)

Node[] fcrundRoutel = elsFindRoute(&quotMontreal&quot, &quotSeattle&quot) Node[] £oundRoute2 = elsFindRoute(&quotNew York&quot, &quotSeattle&quot)

}

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

public static void TestSearchO { SearchSolutionDepthFirstsearch els =

new  SearchSolutionDepthFirstsearch(SearchSolutionNodeRootNodes) elsFindRoute^&quotMontreal&quot, &quotSeattle&quot)

Node[] foundRoute1 = elsFoundRoute elsFindRoute(&quotNew York&quot, &quotSeattle&quot) Node[] foundRoute2 = elsFoundRoute

}

І знову обидва рішення виглядають достатніми Але в даному випадку є тонка, але вельми важлива різниця У реалізації тесту, в якому знайдений маршрут воращается в значенні параметра, змінні foundRoutel і foundRoute2 претавляют маршрути, прямим чином повязані з маршрутом, для якого волняется пошук Змінні foundRoutel жодним чином не можуть представляти маршрут Нью-Йорк – Сіетл. А в разі коду з членом даних, може злучити-

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

public static void TestSearchO { SearchSolutionDepthFirstSearch els =

new SearchSolutionDepthFirstSearch(SearchSolutionNodeRootNodes)

elsFindRoute(&quotMontreal&quot, &quotSeattle&quot) elsFindRoute(&quotNew York&quot, &quotSeattle&quot) Node[ ]    foundRoute 1   =   elsFoundRoute Node[ ]    £oundRoute 2   =   elsFoundRoute

}

Якщо поміняти порядок викликів методу FindRoute () і посилання на член даних FoundRoute, то змінні foundRoutel і foundRoute2 будуть посилатися на один і той же знайдений маршрут, зокрема, на маршрут Нью-Йорк – Сіетл. Це не добре Приклад демонструє, як члени даних не повязані безпосередньо з методами і можуть незалежно змінюватися

Тому підхід, в якому знайдений маршрут представляється у повернутому методом значенні, є кращим і більш надійним

ПРИМІТКА

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

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

public static void TestSearchO { SearchSolutionDepthFirstSearch els =

new SearchSolutionDepthFirstSearch(SearchSolutionNodeRootNodes) SearchSolutionNode[] foundRoute = elsFindRoute(&quotMontreal&quot, &quotSeattle&quot) if (foundRouteLength = 2) {

ConsoleWriteLine(&quotIncorrect route as route has two legs&quot)

}

if (foundRoute[OJCityNameCompareTo(&quotLos Angeles&quot) = 0) { ConsoleWriteLinet&quotIncorrect as first leg is Los Angeles&quot)

}

}

ПРИМІТКА

Ми вже застосовував і конструкцію if в попередніх розділах У ній перевіряється умова, і в разі позитивного результату перевірки виконаються код у фігурних дужках Комбінація символів = Означає Не дорівнює. Оператор if більш докладно рассмаівается врозд Оператор if далі в цьому розділі

Джерело: Гросс К С # 2008: Пер з англ – СПб: БХВ-Петербург, 2009 – 576 е: ил – (Самовчитель)

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*