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

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

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

Згідно атрибутам, показаним на рис 47, необхідна для проекту searchsoiution

структура даних реалізована, як показано на рис 49

Рис 49 Структура даних для пошуку в глибину

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

Елемент даних connections являє собою масив, що визначає міста, в які є пересадки в поточному місті Міста пересадок можна створити у вигляді масиву елементів Node, як оголошення, показане на рис 49 Як альтернативу можна застосувати масив рядків, що містять назву міста:

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

&gt&nbsp

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

Створення примірника вузла та його ініціалізація

У попередніх прикладах коду ми бачили, як можна створювати екземпляри обсягів по за допомогою ключового слова new Примірники типів завжди створюються з помью ключового слова new Після нього слід імя типу, примірник якого создтся, і відкриває і закриває дужки Для створення екземпляра типу Node застосовується наступний код:

Node city = new Node()

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

ПРИМІТКА

ТерміниКласіСтруктураозначають оголошення типу А термінОбєктозна примірник оголошеного типу

В оголошенні типу Node конструктор не оголосить, тому середовище CLR предтавляет для нього стандартний конструктор Стандартний конструктор нічого не робить і не має параметрів

Після створення обєкта вузла його членам даних можна присвоювати значення:

cityCityName = &quotMontreal" cityX = 00

cityY = 00

В результаті присвоюється найменування міста Монреаль (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(&quotMontreal&quot, 00, 00)

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

Проблема із зверненням до звичайних типам

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

Node montreal   = new Node(&quotMontreal&quot, 0, 0) Node newyork    = new Node(&quotNew York&quot, 0, -3)

Node miami      = new Node(&quotMiami&quot,  -1, -11) Node toronto   = new Node(&quotToronto&quot, -4, -1)  Node houston   = new Node(&quotHouston&quot, -10, -9) Node losangeies = new Node(&quotLos Angeles&quot, -17, -6) Node Seattle   = new Node(&quotSeattle&quot, -16, -1)

У даному коді створюються змінні, що представляють усі міста, показані на рис 47 Для кожної з цих змінних створюється і присвоюється екземпляр типу Node, ініціалізований назвою міста та його координатами Окремі пеменние представляють міста без інформації про пересадках, тому наступним кроком ми звяжемо міста між собою Для цього нам необхідно виділити член даних Connections і привласнити йому значення

Відповідний код для ініціалізації члена даних Connections вузла Montreal даними про пересадках в інші міста буде виглядати наступним чином:

montrealConnections = new Node[3J montrealConnections[0i = newyork montrealConnections[1] = toronto montrealConnections[2] = losangeies

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

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

Зверніть увагу на те, що індекси масиву вказуються в квадратних дужках Не забувайте, що в С # рахунок елементів масиву починається з 0 Тому в трехелентном масиві індекс першого елемента буде 0, а останнього – 2

Розглянемо, що ж відбувається в даному коді Ми оголосили масив, тобто виділи память під нього, після чого привласнили змінні, що представляють міста, кожному елементу масиву Але т к масив Connections є масивом обиого типу, ТО значення членів даних Connections В членах даних Connections елементів масиву не встановлюються Ця обставина для елемента New York масиву (члена даних) Connections вузла Montreal показано на рис 410

Звичайно ж, цю обставину можна логічно пояснити тим фактом, що член даних Connections для вузла New York ще не був визначений Подумайте про те, яким чином відбувається звернення до даних, і освіжіть в памяті Інформ, наведену в табл 41

Node є звичайним типом, а при присвоєнні змінної звичайного типу іншої змінної даного типу, значення першої змінної копіюється в другу

Рис 410 Проблема відсутньої інформації про пересадках

Так як елементів масиву (членам даних) Connections для вузла New York ще не були привласнені значення, то член даних Connections вузла New York для вузла Montreal не матиме жодних значень для пересадок І якщо модифікувати первісну змінну вузла New York, присвоївши значення його елементів масиву (членам даних) Connections, то ці модифікації не відібються в члені даних Connections вузла New York ДЛЯ вузла Montreal або для будь-якого іншого вузла

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

newyorkConnections = new Node[3] newyorkConnections[0] = montreal newyorkConnec t i ons[1] = hous ton newyorkConnections[2] = miami

Ми бачимо, що New York імее т пересадці у на Montreal, а МИ знаємо, ЩО Montreal має пересадку на New York Пасажири, що здійснюють регулярні поїздки МЕУ цими двома містами, хотіли б мати можливість постійно літати туди і назад між Нью-Йорком і Монреалем Але використання змінних зазвичай типу не дозволяє цього (рис 411)

Як можна бачити на рис 411, звичайні типи не можна використовувати рекурсивно Видно, що з Нью-Йорка є рейси на Монреаль Але, прилетівши в Монреаль, ми бачимо, що якщо ми полетимо назад в Нью-Йорк, то знову летіти в Монреаль ми не зможемо Це очевидна брехня, т к ми щойно прилетіли з Нью-Йорка в Монреаль

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

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

Рис 411 Зниклі рейси (пересадки) з Нью-Йорка

Заміна 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, створить таку структуру даних (рис 412)

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

Тепер у нас є рейси між Нью-Йорком і Монреалем Нескінченна ланцюжок членів даних Connections ні означає, що ми використовуємо нескінченні ресурси для її подання Насправді, просто одне посилання вказує на Друю, а та назад на першу (рис 413)

Рис 413 Рекурсивне присвоювання створює враження необхідності нескінченних ресурсів

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

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

Статичні члени даних і методи

Раніше ми бачили, як конкретний екземпляр типу можна ініціалізувати за пощью конструктора Тепер нам потрібно визначити конструктор для деревовидної структури на рис 42 Деревоподібна структура увазі початкову точку для її проходження, але схема пересадок не має однієї початкової точки Що у нас є, так це кілька оголошених змінних, чиї ідентифікатори претавляют міста

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

Це завдання можна вирішити, додавши в оголошення класу 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 (), який запускає консольний додаток на виконання)

На рис 414 показано, що можна і що не можна робити зі статичними і нестатічкімі членами даних

Рис 414 Дозволені і заборонені операції зі статичними і нестатичних членами даних

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(&quotMontreal&quot, 0, 0) Node newyork   = new Node(&quotNew York&quot, 0, -3) Node miami      = new Node(&quotMiami&quot, -1, -11) Node toronto   = new Node(&quotToronto&quot, -4, -1) Node houston   = new Node(&quotHouston&quot, -10, -9)

Node losangeles = new Node(&quotLos Angeles&quot, -17, -6)

Node Seattle   = new Node(&quotSeattle&quot, -16, -1)

montrealConnections = new Node[3] montrealConnections[0] = newyork montrealConnections[1] = toronto

montrealConnections[2] = losangeles

newyorkConnections = new Node[3] newyorkConnections[0] = montreal newyorkConnections[1] = houston newyorkConnections[2] = miami

miamiConnections = new Node[3] miamiConnections[0] = toronto miamiConnections[1] = houston miamiConnections[2] = newyork

torontoConnections = new Node[3] torontoConnections[0] = miami torontoConnections[1] = Seattle torontoConnections[2i = montreal

houstonConnections = new Node[3] houstonConnections[0] = miami houstonConnections[1] = Seattle houstonConnections[2] = newyork

SeattleConnections = new Node[3] SeattleConnections[0] = toronto SeattleConnections[1] = houston SeattleConnections[2] = losangeles

losangelesConnections = new Node[3] losangelesConnections[0] = montreal losangelesConnections[li = Seattle losangelesConnections[2] = houston

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

NodeRootNodes[6i = Seattle

}

}

Джерело: Гросс К С # 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>

*

*