Как я уже упомянул, разработчики используют главным образом ключевое слово class для определения структур данных как ссылочного типа в связи с ограничениями, присущими типам значения. Однако для этого примера мы используем ключевое слово struct, определяя Node как тип значения. Алгоритм поиска в глубь имеет два отдельных элемента реализации — структуру данных и алгоритм. Поскольку каждый элемент не¬зависим, кажется вполне подходящим определить Node как тип значения. Итак, давайте по крайней мере попробуем это и увидим, что получится. Согласно атрибутам, представленным на рис. 4.7, структура данных, добавленная в проект SearchSolution, будет выглядеть, как на рис. 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 с одной ссылкой на элемент Node. Компилятор С# выдаст сообщение об ошибке, указывающее на са¬моссылку узла. Вот пример структуры с самоссылкой, которая не будет откомпилирована. public struct Node { public string CityName; public double X; ^ public double Y; public Node Connections; } Проблема объявления в том, что тип значения имеет фиксированный размер, а поскольку вы :5ъявляете переменную Node внутри переменной Node, компилятор не может определить раз¬мер объявляемой структуры. Объявление типа Node с массивом ([ ]) ссылок компилируется, тоскольку массив явно определен как имеющий неизвестную длину, и объявление массива рас¬сматривается как ссылочный тип. Создание экземпляра и инициализация узла В предыдущем коде вы видели, как объекты создаются с помощью ключевого слова - sw. Для создания экземпляра типа всегда используется ключевое слово new. После клю¬чевого слова new следует идентификатор типа, экземпляр которого вы хотите создать i скобки. Экземпляр объекта типа Node создает следующий код: :~ode city = new Node () ; Если вы рассмотрите только идентификатор Node со скобками, то создастся впечат¬ление, что вы вызываете метод без параметров. Впечатление правильно, но это специ¬альный тип вызова метода, который осуществляется с явным использованием ключе-1 zco слова new. Этот метод известен как конструктор (constructor). Каждый тип имеет -инструктор, применяемый для инициализации состояния объекта перед возвратом его называющей стороне. ->з заметку. Когда я говорю класс или структура, я имею в виду объявление типа. Когда я говорю объект, я имею в виду экземпляр объекта объявленного типа. В объявлении типа Node нет никакого явного конструктора. Поэтому среда CLR сседоставит стандартный конструктор. Но стандартный конструктор не делает ничего не имеет никаких параметров. После создания экземпляра узла мы можем присвоить значения его переменным-членам в следующем коде: city.CityName = "Montreal"; city.X = 0.0; city.Y = 0.0; Здесь переменным-членам присваивается название города Монреаль и его коорди¬наты (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 = x; Y = y; Connections = 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 losangeles = new Node("Los Angeles", -17, -6); Node Seattle = new Node("Seattle", -16, -1); Этот код по отдельности создает экземпляры для всех городов на рис. 4.7. ; индивидуальные переменные городов не имеют связей, поэтому следующий шаг — сое-линить все города между собой. Необходимо создать и присвоить значение переменной-члену Connections. Чтобы создать связи с городами, доступными из Монреаля, исполь-ьуем следующий код: montreal.Connections = new Node[3]; nontreal.Connections [0] = newyork; montreal.Connections [1] = toronto; montreal.Connections[2] = losangeles; Когда вы размещаете в памяти массив, вы резервируете под него пространство, со¬гласно объявленному типу, не сам тип. Считайте это покупкой пустого бумажника и на¬личие места для размещения денег и кредитных карточек. Таким образом, вы не вызы¬ваете конструктор объектов, поскольку экземпляры объектов еще не создаются. После того как место под массив будет зарезервировано, его можно присвоить, как :бычные переменные. В качестве альтернативы вы могли бы создать экземпляр и при-:воить массив. Обратите внимание, что квадратные скобки используются для указания индекса массива. Не забудьте, что массивы начинаются с нулевого элемента. Если вы имеете массив из трех элементов, индексом первого элемента будет 0, а последнего — 2. Давайте рассмотрим, что делает код. Вы резервируете пространство для массива и присваиваете переменные, представляющие города, индивидуальным элементам мас-::пва. Поскольку Connections — это массив типа значения, связи внутри связей не уста¬навливаются, как показано на рис. 4.10. Проблема в том, что массив Connections для Нью-Йорка отсутствует. Конечно, вы югли бы логически догадаться, что массив отсутствует потому, что переменная-член : r.nections для узла Нью-Йорка еще не определена. Но (и это большое НО), подумайте : том, как обращаются к данным и каково поведение, описанное в табл. 4.1. Node — это тип значения, а когда такому типу присваивается значение, внутри : называется его копия. Поскольку связи для узла Нью-Йорка еще не были присвоены, массив Connections для Монреаля не будет содержать никаких связей Нью-Йорка. И -:ли вы изменяете исходную переменную Нью-Йорка и его связи, эти изменения ни- ак не отражаются в массиве связей для Монреаля. Пока это еще не кажется настоящей проблемой, но давайте рассмотрим следующий код для Нью-Йорка: newyork.Connections = new Node[3]; newyork.Connections [0] = montreal; newyork.Connections[1] = houston; newyork.Connections [2] = miami; В этом примере Нью-Йорк имеет связь с Монреалем и Монреаль имеет связь с Нью-Йорком, что завершает крут. Жители, конечно, хотели бы летать туда и обратно между городами. Но поскольку мы используем тип значения, летать назад и вперед не полу¬чится, как проиллюстрировано на рис. 4.11. На рис. 4.11 показано, что рекурсия с типами значений не работает. Здесь проде¬монстрировано, что есть связь между Нью-Йорком и Монреалем. Но проследите связь с Монреалем, теперь оказывается, что Нью-Йорк не имеет никаких связей, что является очевидной ложью, поскольку связь от Нью-Йорка до Монреаля очевидна. При присвоении типов значения вы копируете содержимое, получая таким образом снимок состояния объекта в некоторый момент времени. В сущности, код иллюстри¬рует проблему курицы и яйца с точки зрения определения связей для специфического города и их последующего применения. Как же, используя типы значения, присвоить связь одного города другому, когда она еще не существует? Короткий ответ — никак. Длинный ответ — то, что вы можете, означало бы выполнение бесконечного цикла, ко¬торый абсолютно бесполезен, ведь мы хотим с данными что-нибудь делать, как-то их применить. Переходим к классу при определении узла Для устранения проблемы курицы и яйца необходимо использовать ссылочный тип вместо типа значения. Это означает необходимость замены в объявлении Node ключе¬вого слова struct на class следующим образом: 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) i CityName = city; X = x; Y = y; Connections = null; } Изменение всего в одной строке. После перехода, если выполнить тот же код при¬своения, что и в предыдущем разделе, когда Node был типом значения, то структура данных, представленная на рис. 4.12, будет создана. При просмотре структуры узла на рис. 4.12 можно заметить, что Нью-Йорк ука¬зывает на Монреаль и наоборот. Бесконечная связь не означает, что вы используете бесконечные ресурсы. Это означает лишь то, что один объект имеет ссылку на другой и наоборот, как иллюстрирует рис. 4.13. Обычно бесконечный ресурс (infinite resource) — это перекрестная ссылка, рекур¬сивно присваивающая две области распределяемой памяти. Кроме всего прочего, эта способность — одна из причин, почему программисты предпочитают использовать ссылочные типы, а не типы значения. Зачастую, когда используют типы значений, люди считают, что значения неким переменным присвоены, когда фактически они еще не присвоены Понятие статических переменных-членов и методов Как уже упоминалось, конструктор применяется для инициализации состояния специфического экземпляра типа. Теперь необходимо определить конструктор для дре¬вовидной структуры, представленной на рис. 4.2. Дерево подразумевает отправную точ¬ку, но код для связей перелетов не имеет единой отправной точки. Вместо того, суще¬ствует объявление ряда переменных, где каждый идентификатор — это город. Проблема с таким объявлением в том, что если вы хотите управлять древовидной структурой, необходимо знать индивидуальные имена переменных и управлять древо¬видной структурой каждой из них. Это решение нереально. Желательно создать единую общую точку, из которой будут доступны все другие города. Решение заключается в использовании массива, подобного используемому для переменной-члена Connections. Чтобы продемонстрировать проблему предоставления единой точки доступа, объявим статическую переменную-член следующим образом: 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, означающим, что переменная-член статическая. Что же значит статичность в данном контексте? Многие компании используют конференц-связь в своей телефонной сети. Если че¬тыре человека приглашены на конференцию, любой может говорить в любое время. Однако, если все четверо будут говорить одновременно, то слышать они будут только шум. Конференц-связь — это общий ресурс, никак не связанный с определенным теле¬фоном. Точно так же статическая переменная является общим ресурсом, не связанным ни с одним конкретным экземпляром типа. Когда вы используете для переменной-члена ключевое слово static, как в примере кода, вы говорите, что, независимо от количества экземпляров объекта Node, все они будут использовать единственный экземпляр переменной-члена RootNodes. Вам даже не нужно создавать экземпляр объекта Node, чтобы получить доступ к переменной-члену ";otNodes. Статические методы подобны статическим переменным-членам, это общий ресурс, и они не связаны с конкретным объектом (как иллюстрирует метод Main (), ис¬пользуемый для запуска приложения). На рис. 4.14 показано, что можно и нельзя делать со статическими и нестатическими переменными-членами. Общее эмпирическое правило — к статическим переменным-членам и методам можно обращаться без создания экземпляра типа, которому они принадлежат. Не пытайтесь также ссылаться на нестатические переменные-члены или методы в статическом методе. Возвращаясь к объявлению типа 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, Node newyork = new Node("New York", 0, - Node miami = new Node("Miami", -1, -11), Node toronto = new Node("Toronto", -4, - Node houston = new Node("Houston", -10, Node losangeles = new Node("Los Angeles Node Seattle = new Node("Seattle", -16, montreal.Connections = new Node[3J; 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 [2] = montreal; houston.Connections = new Node[3J; 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 [0j = montreal; losangeles.Connections [1j = 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 [5] = losangeles; Node.RootNodes[6] = Seattle; } }