Бинарные деревья
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
(см рис. 3). Поэтому можно сказать, что программа работает корректно.
Проверка на правильность
При выполнении операций над списком результат должен совпадать с результатами, полученными вручную, на основе эмпирических закономерностей. В процессе тестирования программа отреагировала правильно, результат ввода списка, его сортировки, удаления из него элемента перед указанным, совпал с ожидаемым (см рис. 2, рис. 3).
При проверке на правильность, результат не отличался от ожидаемого, поэтому можно сказать, что программа работает правильно.
Проверка на надежность
При изменении входных данных не должен изменяться внешний вид пользовательского интерфейса. При выводе списка 1,9,2,8,3, 7,4, 6,5,0,а,б внешний вид пользовательского интерфейса не отличался от интерфейса, полученного при вводе списка 3, 5, x, y, Z (см рис. 2 и рис. 9).
Программа выдает сбой лишь в случае, если в списке есть элемент, состоящий более чем из одного символа. Но такой элемент нельзя ввести пользователю в поле, так как на добавление элементов стоит ограничение по длине.
Поскольку процент отказа программы не превышает процента отказа, установленного нормами, то можно сделать вывод, что программа работает надежно.
Эскизы экранных форм
Рис. 1. Результат работы программы при корректных данных.
Рис. 2. Результат сортировки списка.
Рис. 3. Результат удаления элемента из списка перед указанным.
Рис. 4. Вывод сообщения об ошибке при отсутствии элемента для добавления.
Рис. 5. Вывод сообщения об ошибке при добавлении элемента с длиной более 1 символа.
Рис. 6. Вывод сообщения об ошибке при нажатии на кнопку удалить, если список пуст.
Рис. 7. Вывод сообщения об ошибке при отсутствии элемента для удаления.
Рис. 8. Вывод сообщения об ошибке при попытке удаления элемента перед первым элементом.
Рис. 9. Результат работы программы при разных входных данных.
Задание 2
ТЕМА: Бинарные деревья.
ЦЕЛЬ: Научиться работать с бинарными деревьями.
ЗАДАНИЕ 2: Написать программу для обхода бинарного дерева по схеме: Правое поддерево - Корень - Левое поддерево. Все необходимые исходные данные задаются пользователем. Вывод результата осуществляется в отдельное окно.
Теоретические сведения
Бинарное дерево - частный случай составной структуры. Бинарные деревья задаются с помощью тренарного функтора:
программа сортировка предикат бинарный
tree( Element, Left, Right ); void - пустое дерево.
Например:
( a, b, c ); tree ( a, tree( b, void, void), tree( c, void, void) ).
Проверка принадлежности дереву:
_mem ( X, tree( X, L, R ))._mem ( X, tree( Y, L, R )) :- tree_mem ( X, L )._mem ( X, tree( Y, L, R )) :- tree_mem ( X, R ).
Две ветви бинарного дерева могут быть различны, но иногда это различие не существенно. Доступ к отдельным элементам. Для осуществления этого используется идея обхода дерева в предписанном порядке. Существует три варианта:
а) сверху вниз: ( V, L, R )
pre ( tree ( X, L, R ), XS ) :- pre ( L, LS ), pre ( R, RS ), append ( [ X | LS ], RS, XS ).( void, [ ] ).
б) слева направо: ( L, V, R )
in ( tree ( X, L, R ), XS ) :- in ( L, LS ), in ( R, RS ), append ( LS, [ X | RS ], XS ).
in ( void, [ ] ).
в) снизу вверх: ( L, R, V )
post (tree( X, L, R ), XS ):- pre( L, LS ), pre( R, RS ), append( RS, [ X ], RS1),append( LS, RS1, XS ).
post ( void, [ ] ).
Логика программы
= tree(tr, string, tr); void=string*append(slist, slist, slist)in(tr, slist)([], Ys, Ys).([X|Xs], Ys, [X|Zs]) :- append(Xs, Ys, Zs).(tree(L, X, R), XS) :-in(R,RS),in(L,LS),append(LS,[X|RS],XS).(void,[]).(tree (tree (void, "b", void), "a", tree (void, "c", void)), R), write (R).
Список использованных источников
. Дж. Доорс, А. Р. Рейблен, С. Вадера. ПРОЛОГ - язык программирования будущего. - М.: Финансы и статистика, 1990.
. Л. Стерлинг, Э. Шапиро. Искусство программирования на языке ПРОЛОГ. - М.: Мир, 1990.
. И. Братко. Программирование на языке Пролог для искусственного интеллекта. - М.: Мир, 1990.