Программирование на языке Ruby
Программирование на языке Ruby читать книгу онлайн
Внимание! Книга может содержать контент только для совершеннолетних. Для несовершеннолетних чтение данного контента СТРОГО ЗАПРЕЩЕНО! Если в книге присутствует наличие пропаганды ЛГБТ и другого, запрещенного контента - просьба написать на почту [email protected] для удаления материала
Почти всегда лучше использовать в качестве справочной таблицы хэш или даже таблицу во внешней базе данных. Но все равно приведем код:
class Tree # Предполагается, что определения взяты из предыдущего примера... def search(x) if self.data == x return self elsif x < self.data return left ? left.search(x) : nil else return right ? right.search(x) : nil end endendkeys = [50, 20, 80, 10, 30, 70, 90, 5, 14, 28, 41, 66, 75, 88, 96]tree = Tree.newkeys.each {|x| tree.insert(x)}s1 = tree.search(75) # Возвращает ссылку на узел, содержащий 75...s2 = tree.search(100) # Возвращает nil (не найдено).9.3.4. Преобразование дерева в строку или массив
С помощью тех же приемов, которые применяются для обхода дерева, мы можем преобразовать его в строку или в массив. Ниже мы выполняем обход во внутреннем порядке, хотя подошел бы и любой другой способ:
class Tree # Предполагается, что определения взяты из предыдущего примера... def to_s "[" + if left then left.to_s + "," else "" end + data.inspect + if right then "," + right.to_s else "" end + "]" end def to_a temp = [] temp += left.to_a if left temp << data temp += right.to_a if right temp endenditems = %w[bongo grimace monoid jewel plover nexus synergy]tree = Tree.newitems.each {|x| tree.insert x}str = tree.to_a * ","# str is now "bongo,grimace,jewel,monoid,nexus,plover,synergy"arr = tree.to_a# arr равно:# ["bongo",["grimace",[["jewel"],"monoid",[["nexus"],"plover",# ["synergy"]]]]]Отметим, что глубина вложенности получающегося массива равна глубине дерева с корнем в том узле, с которого мы начали обход. Чтобы получить плоский массив, можете воспользоваться методом
flatten9.4. Графы
Графом называется множество вершин, произвольным образом соединенных друг с другом. (Дерево — частный случай графа.) Не будем слишком углубляться в эту тему, поскольку теория и терминология весьма сложны. Очень скоро мы перешли бы от информатики в область чистой математики.
И все же у графов есть немало практических приложений. Возьмите обычную дорожную карту, на которой города соединены скоростными магистралями, или печатную плату. То и другое удобно представлять в виде графов. Компьютерную сеть тоже можно описать в терминах теории графов, будь то локальная сеть из нескольких десятков машин или весь Интернет, насчитывающий миллионы узлов.
Под графом мы обычно понимаем неориентированный граф. Попросту говоря, в нем не проставлены стрелки на соединительных линиях; две вершины либо соединены, либо нет. Между тем в ориентированном графе (орграфе) могут быть «улицы с односторонним движением»; из того, что вершина x соединена с вершиной у, не следует, что верно и обратное. Наконец, во взвешенном графе ребрам можно назначать веса. Например, вес может выражать «расстояние» между вершинами. Мы ограничимся только этими основными видами графов; интересующегося читателя отсылаем к многочисленным учебникам информатики и математики.
В Ruby, как и во многих других языках, граф можно представить разными способами, например в виде настоящей сети взаимосвязанных объектов или в виде матрицы, в которой хранятся ребра графа. Мы рассмотрим оба способа и на примерах покажем, как можно манипулировать графами.
9.4.1. Реализация графа в виде матрицы смежности
Нижеприведенный пример основан на двух предыдущих. В листинге 9.3 неориентированный граф реализован в виде матрицы смежности с помощью класса
ZArrayTriMatrixclass LowerMatrix < TriMatrix def initialize @store = Zarray.new endendclass Graph def initialize(*edges) @store = LowerMatrix.new @max = 0 for e in edges e[0], e[1] = e[1], e[0] if e[1] > e[0] @store[e[0],e[1]] = 1 @max = [@max, e[0], e[1]].max end end def [](x,y)
