САОДИС. ИБ-73з Хекк Д.С. саодисс. Кр. М. А. БончБруевича институт непрерывного образования (ино) Структуры и алгоритмы обработки данных в информационных системах и сетях Контрольная работа
 Скачать 0.55 Mb.
|
|
САНКТ-ПЕТЕРБУРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ им. Проф. М.А. Бонч-Бруевича ИНСТИТУТ НЕПРЕРЫВНОГО ОБРАЗОВАНИЯ (ИНО) Структуры и алгоритмы обработки данных в информационных системах и сетях Контрольная работа Вариант 1 ФИО: Хекк Д.С. Группа №: ИБ-73з Студ. билет №: 1710121 Преподаватель: ______________ _____________________________ Санкт-Петербург 2020 г. Цели работы: Освоение технологии реализации ассоциативных нелинейных коллекций на примере АТД "Двоичное дерево поиска". Освоение методики программирования рекурсивных и итеративных алгоритмов задачи. Задание к контрольной работе: Спроектировать, реализовать и провести тестовые испытания АТД "BST - дерево" для коллекции, содержащей данные произвольного типа. Тип коллекции зада ѐтся клиентской программой. Программа может быть реализована на одном из следующих языках программирования Java, C++. Операционная система любая. Среда разработки свободно распространяемая по лицензии GPL. Интерфейс АТД "BST - дерево" включает следующие операции: ● опрос размера дерева ● очистка дерева ● проверка дерева на пустоту ● поиск элемента с заданным ключом ● включение нового элемента с заданным ключом ● удаление элемента с заданным ключом ● итератор для доступа к элементам дерева с операциями: ○ установка на корень дерева ○ проверка конца дерева ○ доступ к данным текущего элемента дерева ○ переход к следующему по значению ключа элементу дерева ○ переход к предыдущему по значению ключа элементу дерева ● обход дерева по схеме, заданной в варианте задания ○ (t -> Lt -> Rt), ● дополнительная операция, заданная в варианте задания (см. алгоритм операции в приложении 3) ○ поиск для заданного ключа предыдущего по значению ключа в дереве (нерекурсивная форма) ● Алгоритмы операций АТД реализуются в рекурсивной форме Для тестирования коллекции интерфейс АТД "BST - дерево" включает дополнительные операции: ● вывод структуры дерева на экран ● опрос числа просмотренных операцией узлов дерева 2. Выполнить отладку и тестирование всех операций АТД "BST - дерево" с помощью меню операций. 3. Выполнить тестирование средней трудо ѐмкости операций поиска, вставки и удаления элементов для среднего и худшего случаев. 4. Провести сравнительный анализ экспериментальных показателей трудо ѐмкости операций. 5. Составить отч ѐт по контрольной работе Выполнение заданий контрольной работы: Для выполнения задания я решил выбрать язык программирования Java, т.к. знаком с ним сильнее всех остальных. В стандартной библиотеке языка уже имеется реализация структуры данных “дерево”, на реализацию которого я частично полагался во время разработки своей версии “дерева”. Структура данных “Двоичное дерево поиска” представляет собой упорядоченный особым способом список элементов, с помощью которого возможно быстро и эффективно находить хранящиеся в нем элементы( O(log n) ). Элементы хранятся в “дереве” в виде ветвей. Ветви выглядят следующим образом: ветвь хранит информацию об одном элементе (ключевой элемент ветви), а также о двух “дочерних” ветвях - правой и левой - также хранящих свои ключевые элементы. Ключевой элемент правой дочерняя ветвь имеет бОльшее значение от текущей, ключевой элемент левой - меньшее. Т.е. дерево, по сути, является рекурсивной структурой данных. Началом дерева является его “корневая ветвь”, которая, в хорошем случае, является средним элементом среди всех элементов дерева. Двоичное дерево поиска может быть сбалансированным и несбалансированным. Сбалансированное дерево - это дерево, в котором количество элементов “справа” от корневого равно количеству элементов “слева”. Несбалансированное, соответственно, такого свойства не имеет. Это свойство влияет на ключевое применение двоичных деревьев - быстрый поиск элементов. В случае сбалансированного дерева, сложность поиска в худшем случае будет равна O(log n), тогда как в несбалансированном может достигать значений в O(n), что абсолютно неоптимально и сильно медленней. Существуют типы “двоичных деревьев” с “автоматической” балансировкой, задаваемой с помощью специальных правил вставки, но для данной контрольной работы это не потребуется и работа будет выполнена при помощи “самого обыкновенного” несбалансированого дерева. Реализация. Для начала следует определить интерфейс для дерева с возможностью добавлять в него только элементы, реализующие интерфейс Comparable, чтобы гарантированно иметь возможность сравнивать элементы: public interface Tree < T extends Comparable < T >> Далее, следуя заданию, необходимо определить методы, которые будут присутствовать в реализации: ● Опрос размера дерева: int size () ● Очистка дерева: Tree < T > clean () ● Проверка дерева на пустоту: boolean isEmpty () ● Поиск элемента с заданным ключом Реализацию функций поиска элемента с заданным ключом и итератора для доступа к элементам дерева было решено вынести в интерфейс вместе с реализацией, т.к. она будет общей для “пустого” и “непустого” дерева. Я несколько расширил функционал дерева с помощью метода filter, для возможности находить элементы по заданному условию, который использовал также и для поиска элемента с заданным ключом. Для наследников, однако, осталась необходимость в реализации метода filterWithAccumulator - вспомогательная функция для рекурсивного поиска по дереву. default Tree < T > findElement ( T element ) { return filter ( element::equals ) ; } default Tree < T > filter ( Predicate < T > predicate ) { return filterWithAccumulator ( predicate, new EmptyTree <>()) ; } Tree < T > filterWithAccumulator ( Predicate < T > predicate, Tree < T > accumulator ) ; ● Включение нового элемента с заданным ключом Tree < T > add ( T element ) ● Удаление элемента с заданным ключом Tree < T > remove ( T element ) ● Итератор для доступа к элементам дерева Для последнего метода из списка я реализовал шаблон “Итератор” с некоторыми дополнениями к стандартной реализации данного шаблона, о которых будет рассказано позже. Iterator < T > iterator () ● Вспомогательная функция объединения двух деревьев Tree < T > union ( Tree < T > that ) ; Далее необходимо определить две реализации интерфейса “дерево”, для гарантии отсутствия значений null и, следовательно, отсутствия ошибки NullPointerException, что, в свою очередь, упрощает реализацию и сохраняет “чистоту” кода: EmptyTree (для пустого дерева) и BinaryTree (для дерева, содержащего элементы). EmptyTree Пустое дерево практически не будет иметь логики и будет оперировать только только константными значениями. ● Опрос размера дерева: Всегда 0 public int size () { return 0 ; } ● Очистка дерева: Когда бы ни был вызван - дерево уже пустое public Tree < T > clean () { return this ; } ● Проверка дерева на пустоту: Всегда true public boolean isEmpty () { return true ; } ● Включение нового элемента с заданным ключом Возвращаем “непустое” дерево с заданным элементом, т.к. это всегда пустое и нам не нужно искать место для вставки public Tree < T > add ( T element ) { return new BinaryTree < T >( element ) ; } ● Удаление элемента с заданным ключом Дерево всегда пустое, т.ч. можем вернуть дерево без изменений public Tree < T > remove ( T element ) { return this ; } ● Вспомогательная функция для поиска Что бы ни хранилось в “аккумуляторе”, здесь мы не найдем ничего и возвращаем “аккумулятор” без изменений public Tree < T > filterWithAccumulator ( Predicate < T > predicate, Tree < T > accumulator ) { return accumulator; } ● Вспомогательная функция объединения двух деревьев Просто возвращаем то, что получили, т.к. объединяя “пустое” дерево с “непустым” получим “непустое”, а при объединении двух “пустых”, можем далее использовать любое из них. public Tree < T > union ( Tree < T > that ) { return that; } BinaryTree Методы в реализации BinaryTree будут несколько сложнее, а также в классе появляются три дополнительных “поля”: elem - для хранения значения элемента, left - левое поддерево, right - правое поддерево. ● Опрос размера дерева: Рекурсивно опрашиваем размеры поддеревьев, складываем их между собой и добавляем к размеру текущей ячейки. public int size () { return left .size () + right .size () + 1 ; } ● Очистка дерева: Возвращаем пустое дерево public Tree < T > clean () { return new EmptyTree <>() ; } ● Проверка дерева на пустоту: Всегда false public boolean isEmpty () { return false ; } ● Включение нового элемента с заданным ключом Рекурсивная функция, в которой мы сравниваем полученный элемент с текущим элементом “ветви” и выбираем куда будет осуществлена вставка public Tree < T > add ( T element ) { Tree < T > result ; switch ( element.compareTo (elem)) { case - 1 : result = new BinaryTree <>(elem , left .add ( element ) , right) ; break ; case 0 : result = this ; break ; case 1 : result = new BinaryTree <>(elem , left , right .add ( element )) ; break ; default : throw new IllegalStateException ( "Cannot reach this" ) ; } return result ; } ● Удаление элемента с заданным ключом Так же, как и при добавлении элемента, рекурсивно ищем public Tree < T > remove ( T element ) { Tree < T > result ; switch ( element.compareTo (elem)) { case - 1 : result = new BinaryTree <>(elem , left .remove ( element ) , right) ; break ; case 0 : result = left .union (right) ; break ; case 1 : result = new BinaryTree <>(elem , left , right .remove ( element )) ; break ; default : throw new IllegalStateException ( "Cannot reach this" ) ; } return result ; } ● Вспомогательная функция для поиска Рекурсивная функция для поиска, в которой мы добавляем в “аккумулятор” элемент только в том случае, если он отвечает требованиям. В противном случае, ”аккумулятор” остается без изменений public Tree < T > filterWithAccumulator ( Predicate < T > predicate, Tree < T > accumulator ) { if ( predicate.test (elem)) { return left .filterWithAccumulator ( predicate, right .filterWithAccumulator ( predicate, accumulator.add (elem))) ; } else { return left .filterWithAccumulator ( predicate, right .filterWithAccumulator ( predicate, accumulator )) ; } } ● Вспомогательная функция объединения двух деревьев Рекурсивно добавляем текущий элемент в новое дерево, получившийся результат объединяем с правым поддеревом, а после с левым. public Tree < T > union ( Tree < T > that ) { return left .union (right .union ( that.add (elem))) ; } Функция получения итератора также была добавлена к базовому интерфейсу для деревьев и имеет вид: default Iterator < T > iterator () { return new Iterator <>( this ) ; } Далее я хотел бы перейти к реализации шаблона “итератор” для данного дерева. Iterator У итератора будут присутствовать ссылки на корневой элемент дерева (она же - ссылка на само дерево) и ссылка на “текущий” элемент дерева (текущее поддерево) для возможности реализаций всех функций итератора. Следуя заданию, итератор должен иметь следующие возможности: ● Установка на корень дерева Имеем ссылку на корень - ее и возвращаем public Iterator < T > root () { return root .iterator () ; } ● Проверка конца дерева Используем вспомогательную функцию calculateNext с условием, чтобы найденный элемент был больше ключевого элемента текущего поддерева public boolean hasNext () { return !calculateNext ( elem -> elem.compareTo (currentPointer .get ()) > 0 ) .isEmpty () ; } ● Доступ к данным текущего элемента дерева Возвращаем значение текущего поддерева public T get () { return currentPointer .get () ; } ● Переход к следующему по значению ключа элементу дерева Через вспомогательную функцию calculateNext находим следующий элемент public String next () { Tree < T > next = calculateNext ( elem -> elem.compareTo (currentPointer .get ()) > 0 ) ; if ( ! next .isEmpty ()) { currentPointer = next ; } return "Done" ; } ● Переход к предыдущему по значению ключа элементу дерева Через вспомогательную функцию calculateNext находим предыдущий элемент public String prev () { Tree < T > next = calculateNext ( elem -> elem.compareTo (currentPointer .get ()) < 0 ) ; if ( ! next .isEmpty ()) { currentPointer = calculateNext ( elem -> elem.compareTo (currentPointer .get ()) < 0 ) ; } return "Done" ; } ● Поиск для заданного ключа предыдущего по значению ключа в дереве Сначала находим элемент в дереве, а после через вспомогательную функцию calculateNext находим предыдущий элемент public Tree < T > prevByElement ( T element ) { Tree < T > pointer = root .findElement ( element ) ; Tree < T > next = calculateNext ( elem -> elem.compareTo (currentPointer .get ()) < 0 ) ; if ( ! next .isEmpty ()) { pointer = calculateNext ( elem -> elem.compareTo (currentPointer .get ()) < 0 ) ; } return pointer; } Тестирование Для выполнения тестирования через “меню операци”, я добавил вспомогательный класс и класс, содержащий метод main. Ознакомиться с их реализацией можно в приложении к данной контрольной работе, а также на сервисе GitHub по ссылке https://github.com/kochunstvo/bst-sut Далее будут приведены скриншоты проведенного мной тестирования реализации структуры хранения данных “Двоичное дерево поиска”. Для тестирования я буду использовать дерево вида [1][2][3][4][5][6][7][8][9] Рис. 1 Доступные опции в “меню” Рис. 2 Получение размера дерева Рис. 3 Проверка дерева на пустоту Рис. 4 Добавление элемента в дерево Рис. 5 Удаление элемента из дерева Рис. 6 Проверка конца дерева с помощью итератора Рис. 7 Получение значения из указателя итератора Рис. 8 Перемещение итератора к следующему элементу и получение этого элемента Рис. 9 Перемещение итератора к предыдущему элементу и получение этого элемента Заключение Мною была проведена разработка, тестирование и отладка структуры хранения данных “Двоичное дерево поиска”. В процессе реализации пришлось поработать с рекурсивными функциями, интерфейсами, классами, ссылками, лямбда-выражениями и пр. Получившаяся структура данных не столь оптимальна, насколько этого хотелось бы, но в определенных условиях и она может быть полезна. |