Бинарные деревья
Контрольная работа - Компьютеры, программирование
Другие контрольные работы по предмету Компьютеры, программирование
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение
Высшего профессионального образования
"Комсомольский-на-Амуре государственный технический университет"
Факультет компьютерных технологий
Кафедра МОП ЭВМ
По дисциплине: "Функциональное и логическое программирование"
Студент группы 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"",=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