Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Формулировка задачи

К-2012

Лабораторная работа №6. Бинарные деревья с использованием файлов и списков

Цель работы: смоделировать АТД «Бинарное дерево» с использованием списков и файлов. Использовать язык программирования логики Prolog.

Формулировка задачи

Смоделировать бинарное дерево со следующими возможными операциями:

· вставка и удаление элементов;

· вставка и удаление листов дерева;

· вставка и удаление элементов на любом уровне дерева;

· отображение дерева на экран;

· поиск элемента в дереве.

Первоначальное дерево хранить в двух вариантах: как список и как файл.

Лістинг програми:

domains

file = infile; outfile

domains

treetype = tree(integer, treetype, treetype); empty()

ttreelist = integer*

predicates

nondeterm writetree(treetype, integer,integer)

nondeterm tab(integer)

nondeterm intree(integer, treetype)

gt(integer,integer)

nondeterm addelement(integer, treetype, treetype)

nondeterm delelement(integer, treetype,treetype)

nondeterm delmin(treetype, integer, treetype)

nondeterm read_input(treetype)

nondeterm read_input_aux(treetype,treetype)

nondeterm add_list_to_tree(ttreelist, treetype,treetype)

clauses

add_list_to_tree([], Tree, Tree).

add_list_to_tree([X|Tail], Tree, NewTree):-

addelement(X,Tree,Tree1),

add_list_to_tree(Tail, Tree1,NewTree).

tab(0).

tab(X):-

write(" "),

X1 = X-1,

tab(X1).

writetree(empty, _, _).

writetree(tree(X,Left,Right), CurInd, Indent):-

CurInd2 = CurInd + Indent,

writetree(Right,CurInd2,Indent),

tab(CurInd2), write(X), nl,

writetree(Left,CurInd2,Indent).

gt(X,Y):-

X > Y.

intree(X,empty):-

write(X, " not in tree ", '\n'),!.

intree(X,tree(X,_,_)):-

write(X, " in tree ", '\n').

intree(X,tree(Root,Left,_)):-

gt(Root,X),

intree(X,Left).

intree(X,tree(Root,_,Right)):-

gt(X,Root),

intree(X,Right).

addelement(X, empty, tree(X, empty,empty)).

addelement(X, tree(X, Left, Right),tree(X, Left, Right)).

addelement(X, tree(Root, Left, Right),tree(Root, Left1, Right)):-

gt(Root, X),

addelement(X, Left, Left1).

addelement(X, tree(Root, Left, Right),tree(Root, Left, Right1)):-

gt(X, Root),

addelement(X, Right, Right1).

delelement(X, tree(X, empty, Right), Right).

delelement(X, tree(X, Left, empty), Left).

delelement(X, tree(X, Left, Right), tree(Y,Left, Right1)):-

delmin(Right, Y, Right1).

delelement(X, tree(Root, Left, Right), tree(Root,Left1, Right)):-

gt(Root,X),

delelement(X,Left,Left1).

delelement(X, tree(Root, Left, Right), tree(Root,Left, Right1)):-

gt(X, Root),

delelement(X,Right, Right1).

delmin(tree(Y, empty, Right), Y, Right).

delmin(tree(Root,Left, Right), Y, tree(Root, Left1, Right)):-

delmin(Left, Y, Left1).

read_input(InTree):-

read_input_aux(empty, InTree).

read_input_aux(Tree, NewTree):-

readint(S), nl,

addelement(S,Tree, Tree1),

read_input_aux(Tree1, NewTree).

read_input_aux(Tree, Tree).

goal

write("Please, input file name: "),

readln(InFileName), nl,

openread(infile, InFileName),

readdevice(infile),

read_input(TX),

write(TX,'\n'),

writetree(TX,0,8),

intree(6,TX),

intree(12,TX),

write("add 22 to tree", '\n'),

addelement(22, TX, T9),

writetree(T9,0,8),

write("delete 5 from tree", '\n'),

delelement(5, T9, T10),

writetree(T10,0,8),!,fail.

Результат:

Висновок: на лабораторній роботі ми навчились створювати бінарні дерева, освоїли методи реалізації операцій над ними.