Бинарные деревья

clauses %предложения(EL):-EL>="A",EL<="Z",!.(EL):-EL>="a",EL<="z",!.(EL):-EL>="А",EL<="Я",!.(EL):-EL>="а",EL<="я",!.(EL):-EL>="0",EL<="9",!.(EL):-EL="", dlg_error("Ошибка","Элемент не указан"),!, fail.(_):-dlg_error("Ошибка","Некоректный ввод"),!, fail.(EL,[A|LST]):-EL=A.([E|LST],N,O):-=lbox_GetItem(O,N),<>"",=N+1,!,(LST,N1,O).([],_,_).([E|LST],O):-lbox_Add(O,E),tolbox(LST,O).([],_).

Бинарные деревья

Контрольная работа

Компьютеры, программирование

Другие контрольные работы по предмету

Компьютеры, программирование

Сдать работу со 100% гаранией

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение

Высшего профессионального образования

"Комсомольский-на-Амуре государственный технический университет"

Факультет компьютерных технологий

Кафедра МОП ЭВМ

 

 

 

 

 

По дисциплине: "Функциональное и логическое программирование"

 

 

 

Студент группы 0ВТ3к-1

Коновалова. К.А.

Преподаватель Абарникова Е.Б.

 

 

 

 

 

 

 

 

 

 

Задание 1

 

Тема: списки и бинарные деревья.

Цель: изучить основные операции работы со списком.

Задание: написать программу реализующую:

) удаление элемента из списка перед указанным элементом.

) сортировку списка по возрастанию методом быстрой сортировки.

Для всех операций осуществить контроль ввода (элементом списка могут быть как числа, так и символы).

Теоретическое описание

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

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

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

"голову" - первый элемент списка;

"хвост" - элемент или последовательность элементов следующих за "головой" списка.

Описание алгоритма быстрой сортировки.

Выберем случайным образом какой-то элемент х и просмотрим список, двигаясь слева направо, пока не найдем аi больший x, а затем справа налево, пока не найдем аi меньший х. Поменяем их местами и продолжим процесс просмотра с обменом, пока просмотры не встретятся где-то в середине списка.

В результате список разделится на две части: левую - с ключами, меньшими х и правую - с ключами, большими х. Этот шаг называется разделением. Х - центром.

К получившимся частям рекурсивно применяем ту же процедуру. В результате получается очень эффективная сортировка. Среднее быстродействие O(n*log(n)), но возможен случай таких входных данных, на которых алгоритм будет работать за O(n2) операций. Hа случайных входных данных вероятность такого чрезвычайно мала.

Описание программы

Описание предикатов, используемых в программе

Рассмотрим только основные предикаты, реализующие указанные в задании действия.

Список всех предикатов:

 

cmp(STRING,SLIST,SLIST,SLIST) %сортировка (для сравнения элементов)

del (SYMBOL,S,S) %удаление элемента перед указанным(SYMBOL)%проверка ввода пользователя

tolist(S,INTEGER,WINDOW)%запись элементов в список(S,WINDOW)%запись элементов в лист(SYMBOL,S,S)%удаление конкретного элемента(SYMBOL,S) %поиск элемента в списке(S) %проверка на наличие элементов в списке(SLIST,SLIST)%быстрая сортировка(SLIST,SLIST,SLIST)%вспомогательный предикат для сортировки(SYMBOL,S) %проверка на удаление перед первым эл-ом.

 

Основные предикаты:

del(SYMBOL,S,S)%удаление элемента перед указанным

·1-й аргумент - элемент, перед которым требуется удалить другой элемент;

·2-й аргумент - входной список элементов;

·3-й аргумент - результирующий список элементов.

Данное правило использует восходящую рекурсию для удаления элементов из списка (2-й аргумент) и перемещения результата удаления элементов из списка в результирующий список(3-й аргумент).

sort (SLIST,SLIST)%предикат быстрой сортировки

·1-й аргумент - список строк, который требуется отсортировать;

·2-й аргумент - отсортированный список строк (результат).

Данное правило использует восходящую рекурсию для сортировки списка(1-й аргумент) и перемещения отсортированного списка в результирующий список(2-й аргумент).

Для каждого из рассмотренных предикатов текст соответствующих правил представлен в разделе "Текст программы".

Текст программы

=SYMBOL*%предикаты_dialog_eh : EHANDLER %идентификатор окна(STRING,SLIST,SLIST,SLIST)%сортировка(SYMBOL)%проверка ввода пользователя(S,INTEGER,WINDOW)%запсиь элементов в список

tolbox(S,WINDOW)%запсиь элементов в лист(SYMBOL,S,S)%удаление конкретного элемента

nondeterm del(SYMBOL,S,S)%удалить предидущий

scan(SYMBOL,S)%поиск элемента в списке(S)%проверка на наличие элементов в списке(SLIST,SLIST)%быстрая сортировка(SLIST,SLIST,SLIST)%вспомогательный предикат(SYMBOL,S)%проверка на удаление перед первым элементом

clauses %предложения(EL):-EL>="A",EL<="Z",!.(EL):-EL>="a",EL<="z",!.(EL):-EL>="А",EL<="Я",!.(EL):-EL>="а",EL<="я",!.(EL):-EL>="0",EL<="9",!.(EL):-EL="", dlg_error("Ошибка","Элемент не указан"),!, fail.(_):-dlg_error("Ошибка","Некоректный ввод"),!, fail.(EL,[A|LST]):-EL=A.([E|LST],N,O):-=lbox_GetItem(O,N),<>"",=N+1,!,(LST,N1,O).([],_,_).([E|LST],O):-lbox_Add(O,E),tolbox(LST,O).([],_).

%***************************************************************

delelem(_,[],[]).(EL,[E|LST],LST1):-EL=E,!,delelem(EL,LST,LST1).(EL,[E|LST],[E|LST1]):-!,delelem(EL,LST,LST1).

%***************************************************************

del(_,[],[]).(EL,[X,EL|T],[EL|T1]):-del(EL,T,T1),!.(EL,[X|T],[X|T1]):-del(EL,T,T1).

%***************************************************************(_,[]):-!,fail. %проверяем наличие элемента в списке

scan(EL,[EL|_]):-!.(EL,[_|LST]):-!,scan(EL,LST).([],L,L).([X|L1],L2,[X|L3]):-link(L1,L2,L3).([],[]).([X|Z],SORTLIST) :-(X, Z, S, L),(S, SORTS),(L, SORTL),(SORTS,[X|SORTL],SORTLIST).(_,[],[],[]).(X,[Y|TAIL], [Y|S],L):-X>Y,!,cmp(X,TAIL,S,L).(X,[Y|TAIL], S,[Y|L]):-cmp(X,TAIL,S,L).

isempty([]).%список пуст

%создание диалогового окна

dlg_dialog_Create(Parent):-_CreateResDialog(Parent,dlg_dialog_DlgType,dlg_dialog_ResID,dlg_dialog_eh,0).

%BEGIN dialog, idc_sort _CtlInfo_dialog_eh(_Win,e_Control(idc_sort,_CtrlType,_CtrlWin,_CtlInfo),0):-=win_GetCtlHandle(_Win,idc_list),=lbox_CountAll(L),>0,=lbox_GetAll(L),(S,S1),_Clear(L),_Add(L,S1),

!.

%проверка списка на наличие в нем элементов

dlg_dialog_eh(_Win,e_Control(idc_sort,_CtrlType,_CtrlWin,_CtlInfo),0):-=win_GetCtlHandle(_Win,idc_list),=lbox_CountAll(List),=0,

dlg_Note("Ошибка","Список пуст"),

!.

%END dialog, idc_sort _CtlInfo

%BEGIN dialog, idc_addelem _CtlInfo_dialog_eh(_Win,e_Control(idc_add_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-=win_GetCtlHandle(_Win,idc_add),=win_GetCtlHandle(_Win,idc_list), =win_GetText(I),_len(EL,1),

chksmb(EL),_Add(O,EL), %добавление элемента в список_SetText(I,""), %очистка поля ввода

!.

%проверка на корректный ввод

dlg_dialog_eh(_Win,e_Control(idc_add_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-=win_GetCtlHandle(_Win,idc_add),=win_GetText(O),="",

dlg_error("Ошибка","Элемент не задан"),_SetText(O,""),

!.

%проверка длины элемента

dlg_dialog_eh(_Win,e_Control(idc_add_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-=win_GetCtlHandle(_Win,idc_add),=win_GetText(O),<>"",

dlg_error("Ошибка","Элемент должен состоять из 1 символа!"),

win_SetText(O,""),

!.

%END dialog, idc_addelem _CtlInfo

%BEGIN dialog, при нажатии кнопки выхода idc_cancel _CtlInfo_dialog_eh(_Win,e_Control(idc_cancel,_CtrlType,_CtrlWin,_CtrlInfo),0):-!,_Destroy(_Win),

!.

%END dialog, idc_cancel _CtlInfo

%BEGIN dialog, idc_del_elem _CtlInfo

%обработка ввода пользователя - проверка списка на наличие элементов

dlg_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-=win_GetCtlHandle(_Win,idc_list),(LIST,0,O),(LIST),

dlg_error("Ошибка","Список пуст"),

I=win_GetCtlHandle(_Win,idc_del),=win_GetCtlHandle(_Win,idc_befor),_SetText(I,""),_SetText(II,""),

!.

%проверка на заполнение обоих полей для удаления

dlg_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-=win_GetCtlHandle(_Win,idc_del),=win_GetCtlHandle(_Win,idc_befor),=win_GetText(I),=win_GetText(O),

DEL1<>"",<>"",_error("Ошибка","Укажите один элемент для удаления в одном поле"),

win_SetText(I,""),_SetText(O,""),

!.

%удаление конкретного элемента_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-=win_GetCtlHandle(_Win,idc_del),=win_GetCtlHandle(_Win,idc_list),=win_GetText(I),_len(EL,1),(EL),(LIST,0,O),(EL,LIST),(EL,LIST,LIST1),_Clear(O),(LIST1,O),

win_SetText(I,""),

!.

%удаление элементов перед указанным

dlg_dialog_eh(_Win,e_Control(idc_del_elem,_CtrlType,_CtrlWin,_CtlInfo),0):-=win_GetCtlHand

Похожие работы

1 2 >