Программирование на языке Ruby
вернуться

Фултон Хэл
Шрифт:

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

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

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

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

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
работает так же, как в случае со строкой или массивом.