Загрузка...


  • 9.1. Множества
  • 9.1.1. Простые операции над множествами
  • 9.1.2. Более сложные операции над множествами
  • 9.2. Стеки и очереди
  • 9.2.1. Более строгая реализация стека
  • 9.2.2. Обнаружение несбалансированных скобок
  • 9.2.3. Стек и рекурсия
  • 9.2.4. Более строгая реализация очереди
  • 9.3. Деревья
  • 9.3.1. Реализация двоичного дерева
  • 9.3.2. Сортировка с помощью двоичного дерева
  • 9.3.3. Использование двоичного дерева как справочной таблицы
  • 9.3.4. Преобразование дерева в строку или массив
  • 9.4. Графы
  • 9.4.1. Реализация графа в виде матрицы смежности
  • 9.4.2. Является ли граф связным?
  • 9.4.3. Есть ли в графе эйлеров цикл?
  • 9.4.4. Есть ли в графе эйлеров путь?
  • 9.4.5. Инструменты для работы с графами в Ruby
  • 9.5. Заключение
  • Глава 9. Более сложные структуры данных

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

    (Вильям Гибсон)

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

    Математические множества можно, как мы видели, моделировать с помощью массивов. Но в последних версиях Ruby есть также класс

    Set
    , который хорошо поддерживает эту структуру.

    Стеки и очереди — две весьма распространенные в информатике структуры данных. В первом издании этой книги им было уделено чрезмерно много внимания. Для тех, кого интересуют общие вопросы, я оставил кое-какой материал; для остальных есть немало великолепных книг по структурам данных и алгоритмам.

    Деревья полезны для сортировки, поиска и просто представления иерархических данных. Мы рассмотрим двоичные деревья и сделаем несколько замечаний о деревьях более высокой степени.

    Граф — это обобщение понятия дерева. Граф представляет собой множество вершин, соединенных ребрами, причем с каждым ребром может быть связан вес или направление. Они полезны для решения многих задач, в том числе при анализе сетей и организации знаний.

    Но самыми простыми структурами являются множества. С них мы и начнем.

    9.1. Множества

    Мы уже видели, что некоторые методы класса

    Array
    позволяют использовать массивы для представления математических множеств. Однако для написания более строгого и компактного кода в Ruby есть также класс
    Set
    , который скрывает от программиста большую часть деталей реализации.

    Чтобы получить в свое распоряжение класс

    Set
    , достаточно написать:

    require 'set'

    При этом также добавляется метод

    to_set
    в модуль
    Enumerable
    , так что любой перечисляемый объект становится возможно преобразовать в множество.

    Создать новое множество нетрудно. Метод

    []
    работает почти так же, как для хэшей. Метод
    new
    принимает в качестве необязательных параметров перечисляемый объект и блок. Если блок задан, то он выступает в роли «препроцессора» для списка (подобно операции
    map
    ).

    s1 = Set[3,4,5]                 # В математике обозначается {3,4,5}.

    arr = [3,4,5]

    s2 = Set.new(arr)               # То же самое.

    s3 = Set.new(arr) {|x| x.to_s } # Множество строк, а не чисел.

    9.1.1. Простые операции над множествами

    Для объединения множеств служит метод

    union
    (синонимы
    |
    и
    +
    ):

    x = Set[1,2,3]

    y = Set[3,4,5]


    а = x.union(y) # Set[1,2,3,4,5]

    b = x | y      # То же самое.

    с = x + y      # То же самое.

    Пересечение множеств вычисляется методом

    intersection
    (синоним
    &
    ):

    x = Set[1,2,3]

    y = Set[3,4,5]


    а = x.intersection(y) # Set[3]

    b = x & y # То же самое.

    Унарный минус обозначает разность множеств; мы обсуждали эту операцию в разделе 8.1.9.

    diff = Set[1,2,3] - Set[3,4,5] # Set[1,2]

    Принадлежность элемента множеству проверяют методы

    member?
    или
    include?
    , как для массивов. Напомним, что порядок операндов противоположен принятому в математике.

    Set[1,2,3].include?(2) # true

    Set[1,2,3].include?(4) # false

    Set[1,2,3].member?(4)  # false

    Чтобы проверить, является ли множество пустым, мы вызываем метод

    empty?
    , как и в случае с массивами. Метод
    clear
    очищать множество, то есть удаляет из него все элементы.

    s = Set[1,2,3,4,5,6]

    s.empty? # false

    s.clear

    s.empty? # true

    Можно проверить, является ли одно множество подмножеством, собственным подмножеством или надмножеством другого.

    x = Set[3,4,5]

    y = Set[3,4]


    x.subset?(y)        # false

    y.subset?(x)        # true

    y.proper_subset?(x) # true

    x.subset?(x)        # true

    x.proper_subset?(x) # false

    x.superset?(y)      # true

    Метод

    add
    (синоним
    <<
    ) добавляет в множество один элемент и обычно возвращает его в качестве значения. Метод
    add?
    возвращает
    nil
    , если такой элемент уже присутствовал в множестве. Метод merge полезен, если надо добавить сразу несколько элементов. Все они, конечно, могут изменить состояние вызывающего объекта. Метод
    replace
    работает так же, как в случае со строкой или массивом.

    Наконец, два множества можно сравнить на равенство интуитивно очевидным способом:

    Set[3,4,5] == Set[5,4,3] # true

    9.1.2. Более сложные операции над множествами

    Разумеется, можно обойти множество, но (как и для хэшей) не ожидайте какого-то определенного порядка появления элементов, потому что множества по сути своей неупорядочены, и Ruby не гарантирует никакой последовательности. (Временами можно получить повторяющиеся, ожидаемые результаты, но полагаться на это неразумно.)

    s = Set[1,2,3,4,5]

    s.each {|x| puts x; break } # Выводится: 5

    Метод

    classify
    подобен методу
    partition
    , но с разбиением на несколько частей; он послужил источником идеи для реализации нашей версии метода
    classify
    в разделе 8.3.3.

    files = Set.new(Dir ["*"])

    hash = files.classify do |f|

     if File.size(f) <= 10_000

      :small

     elsif File.size(f) <= 10_000_000

      :medium

     else

      :large

     end

    end


    big_files = hash[:large] # big_files - это Set.

    Метод

    divide
    аналогичен, но вызывает блок, чтобы выяснить «степень общности» элементов, и возвращает множество, состоящее из множеств.

    Если «арность» (число аргументов) блока равна 1, то метод выполняет вызовы вида

    block.call(а) == block.call(b)
    , чтобы определить, принадлежат ли
    а
    и
    b
    одному подмножеству. Если «арность» равна 2, для той же цели выполняются вызовы вида
    block.call(a,b)
    .

    Например, следующий блок (с «арностью» 1) разбивает множество на два подмножества, одно из которых содержит четные числа, а другое — нечетные:

    require 'set'

    numbers = Set[1,2,3,4,5,6,7,8,9,0]

    set = numbers.divide{|i| i % 2}

    p set # #<Set: {#<Set: {5, 1, 7, 3, 9}>, #<Set: {0, 6, 2, 8, 4}>}>

    Вот еще один, несколько искусственный пример. Простыми числами-близнецами называются простые числа, отличающиеся на 2 (например, 11 и 13); все прочие называются одиночными (например, 23). Следующий код разбивает множество на группы, помещая числа-близнецы в одно и то же подмножество. В данном случае применяется блок с «арностью» 2:

    primes = Set[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]

    set = primes.divide{|i,j| (i-j).abs == 2}

    # set is: #<Set: {#<Set: {23}>, #<Set: {11, 13}>,

    #         #<Set: {17, 19}>,     #<Set: {5, 7, 3}>,

    #         #<Set: {2}>,          #<Set: {29, 31}>}>

    # Более компактно: {{23},{11,13},{17,19},{5,7,3}, {2},{29,31}}

    На мой взгляд, этот метод труден для понимания; я рекомендую пользоваться методом

    classify
    , более простым и интуитивно очевидным.

    Важно понимать, что класс

    Set
    не всегда требует, чтобы параметр или операнд также был множеством (если вам это кажется странным, вспомните обсуждение «утипизации» в главе 1). На самом деле большая часть методов данного класса принимает в качестве параметра любой перечисляемый объект. Считайте, что так и задумано.

    Есть и другие методы, которые применяются в частности к множествам (в том числе все методы из модуля

    Enumerable
    ). Я не стану рассматривать здесь такие методы, как
    flatten
    . Дополнительную информацию можно найти на сайте http://ruby-doc.org/ или в любом другом справочном руководстве.

    9.2. Стеки и очереди

    Стеки и очереди — это первые из встретившихся нам структур, которые, строго говоря, не встроены в Ruby. Иными словами, в Ruby нет классов

    Stack
    и
    Queue
    , в отличие от
    Array
    и
    Hash
    (впрочем, класс
    Queue
    есть в библиотеке
    thread.rb
    , которую мы еще будем рассматривать).

    И все же в некотором смысле они встроены в Ruby. Ведь класс

    Array
    реализует всё, что нужно для того, чтобы рассматривать его как стек или очередь. Стек организован по принципу «последним пришел, первым обслужен» (LIFO — last-in first-out). Традиционный пример — стопка подносов на подпружиненной подставке в кафетерии: подносы кладутся сверху и сверху же снимаются.

    Над стеком можно выполнять ограниченный набор операций. Как минимум операции заталкивания (push) и выталкивания (pop), то есть помещения в стек и извлечения из него. Обычно также предоставляется способ проверить, пуст ли стек, и исследовать верхний элемент, не извлекая его из стека. Но никогда реализация не позволяет получить доступ к элементу в середине стека.

    Как же реализовать стек на базе массива, если к элементам массива можно обращаться в произвольном порядке, а стек таким свойством не обладает? Ответ прост. Стек — более абстрактная структура, чем массив. Он является стеком лишь до тех пор, пока мы обращаемся с ним как с таковым. В тот момент, когда вы пытаетесь обратиться к элементу недопустимым образом, стек перестает быть стеком.

    Но можно без труда определить класс

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

    Стоит отметить, что во многих алгоритмах стек применяется как основа элегантного рекурсивного решения. Причина станет ясна, если чуточку подумать. При вызове функции или метода параметры заталкиваются в системный стек и выталкиваются из него при возврате. Таким образом, рекурсивный алгоритм просто подменяет явно определенный пользователем стек системным. Что лучше? Зависит от того, какое значение вы придаете понятности программы, ее эффективности и другим аспектам.

    Очередь организована по принципу «первым пришел, первым обслужен» (FIFO — first-in first-out). Аналогом может служить очередь за билетами в театр: вновь подходящие становятся в конец очереди, а те, кто пришел раньше, обслуживаются первыми. В программировании очереди используются реже, чем стеки.

    Очереди полезны в системах реального времени, когда события нужно обрабатывать в порядке возникновения. Находят они применение и в ситуации «производитель-потребитель» (особенно в многопоточных программах и многозадачных средах). Неплохой пример — очередь к принтеру: задания на печать помещаются в один конец и ожидают, пока не будут извлечены с другого конца.

    Две основные операции над очередью называются «поместить» (enqueue) и «извлечь» (dequeue). Им соответствуют методы

    unpush
    и
    shift
    в классе
    Array
    .

    Отметим, что метод

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

    На этом мы закончим введение в стеки и очереди. Самое время рассмотреть некоторые примеры.

    9.2.1. Более строгая реализация стека

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

    class Stack


     def initialize

      @store = []

     end


     def push(x)

      @store.push x

     end


     def pop

      @store.pop

     end


     def peek

      @store.last

     end


     def empty?

      @store.empty?

     end


    end

    Мы добавили одну операцию, которая для массивов не определена; метод

    peek
    возвращает элемент, находящийся на вершине стека, не выталкивая его.

    Нижеследующие примеры подтверждают адекватность такого определения класса.

    9.2.2. Обнаружение несбалансированных скобок

    В силу самой природы употребления различного вида скобок в выражениях проверить корректность написания можно с помощью стека. При открытии каждого следующего уровня вложенности скобок стек растет. Как только встречается закрывающая скобка, соответствующий элемент выталкивается из стека. Если при обнаружении закрывающей скобки в стеке ничего не оказалось или, наоборот, выражение уже закончилось, а в стеке что-то осталось, значит, выражение записано неверно.

    def paren_match(str)

     stack = Stack.new

     lsym = "{I(<"

     rsym = "}])>"

     str.each_byte do |byte|

      sym = byte.chr

      if lsym.include? sym

       stack.push(sym)

      elsif rsym.include? sym

       top = stack.peek

       if lsym.index(top) != rsym.index(sym)

        return false

       else

        stack.pop

       end

       # Игнорируем символы, отличные от скобок...

      end

     end

     # Убедимся, что стек пуст...

     return stack.empty?

    end


    str1 = "(((a+b))*((c-d)-(e*f))"

    str2 = "[[(a-(b-c))], [[x,y]]]"


    paren_match str1 # false

    paren_match str2 # true

    Наличие вложенности естественным образом наводит на мысль о применении стека. Чуть сложнее распознать несбалансированные теги в HTML- или XML-документе. Лексемы состоят из нескольких символов, но логическая структура задачи остается той же самой. Вот еще типичные примеры задач, требующих стека: преобразование выражений из инфиксной формы в постфиксную (и наоборот), вычисление постфиксного выражения (как делается в виртуальной машине Java и многих других интерпретаторах) и вообще любая задача, имеющая рекурсивное решение. В следующем разделе мы немного поговорим о связи между стеком и рекурсией.

    9.2.3. Стек и рекурсия

    В качестве примера изоморфизма, существующего между стеком и рекурсией, рассмотрим классическую задачу о Ханойской башне.

    По легенде где-то далеко на востоке существует старинный храм. Обитающие в нем монахи заняты решением единственной задачи: перемещением дисков с одного шеста на другой с соблюдением определенных правил. Первоначально на первом шесте было 64 диска. Когда все диски будут перемещены, настанет конец света.

    Попутно разоблачим миф. Похоже, что на самом деле эту задачу впервые сформулировал французский математик Эдуард Люка в 1883 году, и никаких истоков в восточной культуре она не имеет. Сам Люка называл ее «Ханойской башней».

    Так что если вас пугает конец света, можете успокоиться. Да и в любом случае для перемещения 64 дисков потребуется 264-1 ходов. Небольшой расчет на калькуляторе покажет, что монахи будут заняты своим делом несколько миллионов лет.

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

    В следующем примере приведено решение этой задачи с использованием стека. Мы ограничились тремя дисками, потому что для перемещения 64 компьютеру потребовались бы века.

    def towers(list)

     while !list.empty?

      n, src, dst, aux = list.pop

      if n == 1

       puts "Перемещаем диск с #{src} на #{dst}"

      else

       list.push [n-1, aux, dst, src]

       list.push [1, src, dst, aux]

       list.push [n-1, src, aux, dst]

      end

     end

    end


    list = []

    list.push([3, "a", "c", "b"])


    towers(list)

    Вот что напечатает эта программа:

    Перемещаем диск с а на с

    Перемещаем диск с а на b

    Перемещаем диск с с на b

    Перемещаем диск с а на с

    Перемещаем диск с b на а

    Перемещаем диск с b на с

    Перемещаем диск с а на с

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

    def towers(n, src, dst, aux)

     if n==1

      puts "Перемещаем диск с #{src} на #{dst}"

     else

      towers(n-1, src, aux, dst)

      towers(1, src, dst, aux)

      towers(n-1, aux, dst, src)

     end

    end


    towers(3, "а", "с", "b")

    Печатается точно такой же результат. Возможно, вам будет интересно знать, что «закомментарили» предложения, осуществляющие вывод, и сравнили время работы. Никому не говорите, но рекурсивное решение оказалось в два раза быстрее!

    9.2.4. Более строгая реализация очереди

    Мы определим очередь примерно так же, как стек. Если вы хотите защититься от некорректного доступа к структуре данных, рекомендуем поступать аналогично.

    class Queue


     def initialize

      @store = []

     end


     def enqueue(x)

      @store << x

     end


     def dequeue

      @store,shift

     end


     def peek

      @store.first

     end


     def length

      @store.length

     end


     def empty?

      @store.empty?

     end


    end

    Отметим, что класс

    Queue
    имеется в библиотеке
    thread
    для поддержки многопоточных программ. Имеется даже вариант
    SizedQueue
    для организации очереди ограниченного размера.

    В упомянутых классах методы имеют короткие имена:

    enq
    и
    deq
    . У них есть также синонимы
    push
    и
    pop
    , что лично мне кажется неоправданным. Это структура данных FIFO, а не LIFO, то есть именно очередь, а не стек.

    Разумеется, класс

    Queue
    в библиотеке
    thread.rb
    безопасен относительно потоков. Если вы хотите реализовать такой же класс
    Stack
    , рекомендую взять
    Queue
    в качестве отправной точки. Потребуется внести не так много изменений.

    В первом издании книги был длинный пример, демонстрирующий работу с очередями. Но, как и некоторые примеры, касающиеся стеков, он был исключен ради экономии места.

    9.3. Деревья

    Я не увижу никогда, наверное,
    Поэму столь прекрасную как дерево.
    (Джойс Килмер, «Деревья»[11])

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

    Терминология, описывающая деревья, богата, но понять ее легко. Элементы дерева называются узлами; верхний или самый первый узел называется корневым или корнем. У узла могут быть потомки, расположенные ниже него, а непосредственные потомки называются детьми или дочерними узлами. Узел, не имеющий потомков, называется листовым или просто листом. Поддерево состоит из некоторого узла и всех его потомков. Посещение всех узлов дерева (например, с целью распечатки) называется обходом дерева.

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

    Отметим, что во многих языках, например в С или Pascal, деревья реализуются с помощью адресных указателей. Но в Ruby (как и в Java) указателей нет, вместо них используются ссылки на объекты, что ничуть не хуже, а иногда даже лучше.

    9.3.1. Реализация двоичного дерева

    Ruby позволяет реализовать двоичное дерево разными способами. Например, хранить значения узлов можно в массиве. Но мы применим более традиционный подход, характерный для кодирования на С, только указатели заменим ссылками на объекты.

    Что нужно для описания двоичного дерева? Понятно, что в каждом узле должен быть атрибут для хранения данных. Кроме того, в каждом узле должны быть атрибуты для ссылки на левое и правое поддерево. Еще необходим способ вставить новый узел в дерево и получить хранящуюся в дереве информацию. Для этого нам потребуется два метода.

    В первом дереве, которое мы рассмотрим, эти методы будут реализованы неортодоксальным способом. Позже мы расширим класс

    Tree
    .

    В некотором смысле дерево определяется алгоритмом вставки и способом обхода. В нашем первом примере (листинг 9.1) метод

    insert
    будет осуществлять поиск в дереве «в ширину», то есть сверху вниз и слева направо. При этом глубина дерева растет относительно медленно, и оно всегда оказывается сбалансированием. Методу вставки соответствует итератор
    traverse
    , который обходит дерево в том же порядке.

    Листинг 9.1. Вставка и обход дерева в ширину

    class Tree


     attr_accessor :left

     attr_accessor :right

     attr_accessor :data


     def initialize(x=nil)

      @left = nil

      @right = nil

      @data = x

     end


     def insert(x)

      list = []

      if @data == nil

       @data = x

      elsif @left == nil

       @left = Tree.new(x)

      elsif @right == nil

       @right = Tree.new(x)

      else

       list << @left

       list << @right

       loop do

        node = list.shift

        if node.left == nil

         node.insert(x)

         break

        else

         list << node.left

        end

        if node.right == nil

         node.insert(x)

         break

        else

         list << node.right

        end

       end

      end

     end


     def traverse()

      list = []

      yield @data

      list << @left if @left != nil

      list << @right if @right != nil

      loop do

       break if list.empty?

       node = list.shift

       yield node.data

       list << node.left if node.left != nil

       list << node.right if node.right != nil

      end

     end


    end


    items = [1, 2, 3, 4, 5, 6, 7]

    tree = Tree.new

    items.each {|x| tree.insert(x)}


    tree.traverse {|x| print "#{x} "}

    print "\n"

    # Печатается "1 2 3 4 5 6 7 "

    Такое дерево не слишком интересно. Но оно годится в качестве введения и фундамента, на котором можно возводить здание.

    9.3.2. Сортировка с помощью двоичного дерева

    Двоичное дерево позволяет эффективно реализовать сортировку произвольных данных. (Правда, если данные уже отсортированы, оно вырождается в обычный связанный список.) Причина ясна: при каждом сравнении мы исключаем половину мест, в которые можно поместить новый узел.

    Хотя в настоящее время такой способ сортировки применяется редко, знать о нем не повредит. Код в листинге 9.2 основан на предыдущем примере.

    Листинг 9.2. Сортировка с помощью двоичного дерева

    class Tree


     # Предполагается, что определения взяты из предыдущего примера...


     def insert(x)

      if @data == nil

       @data = x

      elsif x <= @data

       if @left == nil

        @left = Tree.new x

       else

        @left.insert x

       end

      else

       if @right == nil

        @right = Tree.new x

       else

        @right.insert x

       end

      end

     end


     def inorder()

      @left.inorder {|y| yield y} if @left != nil

      yield @data

      @right.inorder {|y| yield y} if bright != nil

     end


     def preorder()

      yield @data

      @left.preorder {|y| yield y} if @left != nil

      @right.preorder {|y| yield y} if @right != nil

     end


     def postorder()

      @left.postorder {|y| yield y} if @left != nil

      @right.postorder {|y| yield y} if @right != nil

      yield @data

     end

    end


    items = [50, 20, 80, 10, 30, 70, 90, 5, 14,

             28, 41, 66, 75, 88, 96]


    tree = Tree.new


    items.each {|x| tree.insert(x)}


    tree.inorder {|x| print x, " "}

    print "\n"

    tree.preorder {|x| print x, " "}

    print "\n"

    tree.postorder {|x| print x, " "}

    print "\n"


    # Печатается:

    # 5 10 14 20 28 30 41 50 66 70 75 80 88 90 96

    # 50 20 10 5 14 30 28 41 80 70 66 75 90 88 96

    # 5 14 10 28 41 30 20 66 75 70 88 96 90 80 50

    9.3.3. Использование двоичного дерева как справочной таблицы

    Пусть дерево уже отсортировано. Тогда оно может служить прекрасной справочной таблицей; например, для поиска в сбалансированном дереве, содержащем миллион узлов, понадобится не более 20 сравнений (глубина дерева равна логарифму числа узлов по основанию 2). Чтобы поиск был осмысленным, предположим, что в каждом узле хранится не какое-то одно значение, а ключ и ассоциированные с ним данные.

    Почти всегда лучше использовать в качестве справочной таблицы хэш или даже таблицу во внешней базе данных. Но все равно приведем код:

    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

     end


    end


    keys = [50, 20, 80, 10, 30, 70, 90, 5, 14,

            28, 41, 66, 75, 88, 96]


    tree = Tree.new


    keys.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

     end


    end


    items = %w[bongo grimace monoid jewel plover nexus synergy]

    tree = Tree.new

    items.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"]]]]]

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

    flatten
    .

    9.4. Графы

    Графом называется множество вершин, произвольным образом соединенных друг с другом. (Дерево — частный случай графа.) Не будем слишком углубляться в эту тему, поскольку теория и терминология весьма сложны. Очень скоро мы перешли бы от информатики в область чистой математики.

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

    Под графом мы обычно понимаем неориентированный граф. Попросту говоря, в нем не проставлены стрелки на соединительных линиях; две вершины либо соединены, либо нет. Между тем в ориентированном графе (орграфе) могут быть «улицы с односторонним движением»; из того, что вершина x соединена с вершиной у, не следует, что верно и обратное. Наконец, во взвешенном графе ребрам можно назначать веса. Например, вес может выражать «расстояние» между вершинами. Мы ограничимся только этими основными видами графов; интересующегося читателя отсылаем к многочисленным учебникам информатики и математики.

    В Ruby, как и во многих других языках, граф можно представить разными способами, например в виде настоящей сети взаимосвязанных объектов или в виде матрицы, в которой хранятся ребра графа. Мы рассмотрим оба способа и на примерах покажем, как можно манипулировать графами.

    9.4.1. Реализация графа в виде матрицы смежности

    Нижеприведенный пример основан на двух предыдущих. В листинге 9.3 неориентированный граф реализован в виде матрицы смежности с помощью класса

    ZArray
    (см. раздел 8.1.26). Это нужно для того, чтобы новые элементы по умолчанию получали значение 0. Также мы унаследовали классу
    TriMatrix
    (см. раздел 8.1.7), чтобы получить нижнетреугольную матрицу.

    Листинг 9.3. Матрица смежности

    class LowerMatrix < TriMatrix


     def initialize

      @store = Zarray.new

     end


    end


    class 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)

      if x > y

       @store[x,y]

      elsif x < y

       @store[y,x]

      else

       0

      end

     end


     def []=(x,y,v)

      if x > y

       @store[x,y]=v

      elsif x < y

       @store[y,x]=v

      else

       0

      end

     end


     def edge? x,y

      x,y = y,x if x < y

      @store[x,y]==1

     end


     def add x,y

      @store[x,y] = 1

     end


     def remove x,y

      x,y = y,x if x < y

      @store[x,y] = 0

      if (degree @max) == 0

       @max -= 1

      end

     end


     def vmax

      @max

     end


     def degree x

      sum = 0

      0.upto @max do |i|

       sum += self[x,i]

      end

      sum

     end


     def each_vertex

      (0..@max).each {|v| yield v}

     end


     def each_edge

      for v0 in 0..@max

       for v1 in 0..v0-1

        yield v0, v1 if self[v0,v1]==1

       end

      end

     end


    end


    mygraph = Graph.new{[1,0],[0,3],[2,1],[3,1],[3,2])


    # Напечатать степени всех вершин: 2 3 2 3.

    mygraph.each_vertex {|v| puts mygraph.degree(v)}


    # Напечатать список ребер.

    mygraph.each_edge do |a,b|

     puts "(#{a},#{b})"

    end


    # Удалить одно ребро.

    mygraph.remove 1,3


    # Напечатать степени всех вершин: 2 2 2 2.

    mygraph.each_vertex {|v| p mygraph.degree v}

    Отметим, что приведенная выше реализация не допускает ребер, ведущих из некоторого узла в него же. Кроме того, два узла могут быть соединены только одним ребром.

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

    vmax
    возвращает вершину с наибольшим номером. Метод
    degree
    вычисляет степень указанной вершины, то есть количество исходящих из нее ребер.

    Наконец, имеются два итератора

    each_vertex
    и
    each_edge
    , которые позволяют перебрать все вершины и все ребра соответственно.

    9.4.2. Является ли граф связным?

    Не все графы связные. Иногда нет способа «добраться из одной точки в другую», то есть между двумя вершинами нет никакого пути, составленного из ребер. Связность — это важное свойство графа, его надо уметь вычислять. В связном графе любая вершина достижима из любой другой.

    Не будем объяснять принцип работы алгоритма, интересующийся читатель может найти описание в любой книге по дискретной математике. Но в листинге 9.4 приведена его реализация на Ruby.

    Листинг 9.4. Выяснение того, является ли граф связным

    class Graph


     def connected?

      x = vmax

      k = [x]

      l = [x]

      for i in 0..@max

       l << i if self[x,i]==l

      end

      while !k.empty?

       y = k.shift

       # Теперь ищем все ребра (y,z).

       self.each_edge do |a,b|

        if a==y || b==y

         z = a==y ? b : a

         if !l.include? z

          l << z

          k << z

         end

        end

       end

      end

      if l.size < @max

       false

      else

       true

      end

     end

    end


    mygraph = Graph.new([0,1], [1,2], [2,3], [3,0], [1,3])


    puts mygraph.connected?  # true


    puts mygraph.euler_path? # true


    mygraph.remove 1,2

    mygraph.remove 0,3

    mygraph.remove 1,3


    puts mygraph.connected?  # false


    puts mygraph.euler_path? # false

    В примере упомянут метод

    euler_path?
    , с которым мы еще не встречались. Он определен в разделе 9.4.4.

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

    9.4.3. Есть ли в графе эйлеров цикл?

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

    (Николай Лобачевский)

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

    В немецком городе Кенигсберг был остров посередине реки. С двумя берегами остров связывало семь мостов. Горожане хотели знать, можно ли обойти город так, чтобы побывать на каждом мосту ровно один раз и вернуться в исходную точку. В 1735 году Эйлер доказал, что это невозможно. Эта классическая задача стала первой проблемой теории графов.

    Как часто бывает в жизни, решение кажется простым, когда оно найдено. Оказалось, что для существования в графе эйлерова цикла необходимо и достаточно, чтобы все вершины имели четную степень. Вот короткий код, проверяющий выполнение этого свойства:

    class Graph


     def euler_circuit?

      return false if !connected?

      for i in 0..@max

       return false if degreed) % 2 != 0

      end

      true

     end


    end


    mygraph = Graph.new([1,0],[0,3],[2,1],[3,1],[3,2])


    flag1 = mygraph.euler_circuit? # false


    mygraph.remove 1,3


    flag2 = mygraph.euler_circuit? # true

    9.4.4. Есть ли в графе эйлеров путь?

    Эйлеров путь и эйлеров цикл — разные вещи. Слово «цикл» подразумевает, что нужно вернуться в исходную точку. А наличие пути предполагает, что нужно лишь посетить каждую вершину ровно один раз. В следующем фрагменте демонстрируется это различие:

    class Graph


     def euler_path?

      return false if !connected?

      odd=0

      each_vertex do |x|

       if degree(x) % 2 == 1

        odd += 1

       end

      end

      odd <= 2

     end

    end


    mygraph = Graph.new([0,1],[1,2],[1,3],[2,3],[3,0])


    flag1 = mygraph.euler_circuit? # false

    flag2 = mygraph.euler_path?    # true

    9.4.5. Инструменты для работы с графами в Ruby

    В сообществе пользователей Ruby известно несколько таких инструментов. Они в большинстве своем имеют ограниченную функциональность и предназначены для работы с ориентированными или неориентированными графами. Поищите эти инструменты в архиве RAA (http://raa.ruby-lang.org) или на сайте Rubyforge (http://rubyforge.org). Называются они как-то вроде RubyGraph, RGraph, GraphR и по большей части еще не достигли зрелости.

    Если вас интересует великолепный пакет GraphViz, который умеет представлять сложные графы в виде изображений или программ на языке Postscript, то к нему есть по меньшей мере два работоспособных интерфейса. Есть даже элемент управления

    GnomeGraphWidget
    , который, если верить документации, «можно использовать в приложениях Ruby Gnome для генерирования, визуализации и манипулирования графами». Мы его, впрочем, не изучали; пока еще не вышла даже официальная альфа-версия.

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

    9.5. Заключение

    Мы познакомились с классом Set в Ruby, а также с несколькими примерами «доморощенных» структур данных. Мы видели, как можно создавать сложные структуры данных путем наследования существующему классу или ограниченного делегирования, когда экземпляр существующего класса инкапсулируется в новой структуре. Также были рассмотрены изобретательные способы хранения данных, применения различных структур данных и создания итераторов для обхода таких структур.

    Мы уделили внимание стекам и очередям и способам их использования для решения задач. Кроме того, окинули беглым взглядом деревья и графы.

    В следующей главе мы снова займемся манипулированием данными. Но если до сих пор нас интересовало хранение объектов в основной памяти, то теперь мы обратимся к вспомогательной памяти, то есть файлам (и вводу/выводу в общем), базам данных и устойчивым объектам.


    Примечания:



    1

    Огромное спасибо (яп.)



    11

    Пер. Я. Фельдмана. — Прим. ред.









    Главная | В избранное | Наш E-MAIL | Добавить материал | Нашёл ошибку | Наверх