Списки и бинарные деревья. Написание программы для выполнения операций со списками

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

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

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

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

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

Кафедра математического обеспечения и применения ЭВМ

ЛАБОРАТОРНАЯ РАБОТА № 3

По курсу: «Функциональное программирование»

Студент группы 4ВС-1:                                                                                 Шелестов И.А.

Рогозин В.А.

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

2007 г.

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

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

Задание:        написать программу для выполнения следующих операций со списками:

1)  удаления элемента из списка по заданному номеру;

2)  реверс списка;

3)  объединение трех списков в указанном порядке;

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

Списки и бинарные деревья.

В Прологе список — это объект, который содержит конечное число других объектов. Списки можно грубо сравнить с массивами в других языках, но, в отличие от массивов, для списков нет необходимости заранее объявлять их размер.

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

domains

List=integer*

Список является рекурсивным составным объектом. Он состоит из двух частей — головы, которая является первым элементом, и хвоста, который является списком, включающим все последующие элементы. Хвост списка — всегда список, голова списка — всегда элемент.

Главный способ обработки списка — это просмотр и обработка каждого его элемента, пока не будет достигнут конец.

Алгоритму этого типа обычно нужны два предложения. Первое из них говорит, что делать с обычным списком (списком, который можно разделить на голову и хвост), второе — что делать с пустым списком.

Дерево – рекурсивный тип данных. Каждая ветвь дерева сама является деревом.

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

domains

mytree=tree(string, mytree, mytree); empty

Эта декларация говорит о том, что дерево записывается как функтор tree, аргументами которого являются строка и два других дерева.

Бинарное поисковое дерево строится таким образом, что, глядя на любой узел, можно предсказать, в каком из его узлов находится заданное значение. Это делается заданием отношения порядка между значениями, таким как алфавитный или пронумерованный порядок. Значения в левом поддереве предшествуют значению в текущем узле, а в правом — следуют после значения в текущем узле.

Описание алгоритма сортировки методом пузырька. Просматриваем соседние элементы списка слева направо. При этом, если А1 < A2, то меняем их местами. Таким образом, за один проход наименьший элемент списка окажется последним. Если в списке N элементов, то для сортировки будет достаточно N-1 проходов.

Предикаты, используемые в программе.

adding(SLIST,STRING,SLIST) – добавление элемент в список. Первый параметр – список, в который нужно добавить элемент, второй параметр – добавляемый элемент, третий параметр – результирующий список.

print(SLIST,WINDOW) – вывод списка в ListBox. Первый параметр – выводимый список, второй – хендл ListBox’а.

delete(INTEGER,INTEGER,SLIST,SLIST) – удаление элемента из списка по заданному номеру. Первый параметр – номер удаляемого элемента, второй – счётчик пройденных элементов, третий – список из которого происходит удаление элемента,  четвёртый – результирующий список.

revers(SLIST,SLIST,SLIST) – реверс списка. Первый параметр – исходный список, второй – вспомогательный (пустой), третий – результирующий список.

poradok(STRING,STRING) – определение большего из двух элементов. Первый, второй параметры – сравниваемые между собой.

change(SLIST,SLIST) –перестановка местами двух головных элементов списка. Первый параметр – исходный список (элементы списка в исходном порядке), второй –  результирующий список (элементы поменяны местами).

sort(SLIST,SLIST) – сортировка методом пузырька. Первый параметр – неотсортированный список, второй - отсортированный список

list_union(SLIST,SLIST,SLIST) – объединение списков. Первый, второй параметры – объединяемые списки, третий – результирующий список.

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

include "lab3.inc"

include "lab3.con"

include "hlptopic.con"

%BEGIN_WIN Task Window

/***************************************************************************

Event handling for Task Window

***************************************************************************/

predicates

task_win_eh : EHANDLER

adding(SLIST,STRING,SLIST)

print(SLIST,WINDOW)

delete(INTEGER,INTEGER,SLIST,SLIST)

revers(SLIST,SLIST,SLIST)

poradok(STRING,STRING)

change(SLIST,SLIST)

sort(SLIST,SLIST)

list_union(SLIST,SLIST,SLIST)

constants

%BEGIN Task Window, CreateParms, 00:22:46-3.5.2007, Code automatically updated!

task_win_Flags = [wsf_SizeBorder,wsf_TitleBar,wsf_Close,wsf_Maximize,wsf_Minimize,wsf_ClipSiblings]

task_win_Menu  = res_menu(idr_task_menu)

task_win_Title = "Операции над списками"

task_win_Help  = contents

%END Task Window, CreateParms

clauses

%Adding new element in spysok

adding(L,X,[X|L]).

%Printing spysok in listbox

print([],H).

print([X|L],H):-lbox_Add(H,X),print(L,H).

%deleting elemeent     

delete(NM,NM,[X|L],L).

delete(NM,NT,[Y|L],[Y|L1]):-N=NT+1,delete(NM,N,L,L1).

%revers spyska

revers([],L,L).

revers([X|L1],L,L2):-revers(L1,[X|L],L2).

%Sravnenie

poradok(X,Y):-X>Y.

%Make change

change([X,Y|L],[Y,X|L]):-poradok(X,Y).

change([Z|L],[Z|L1]):-change(L,L1).

%Sort by puzirek

sort(L,L1):-change(L,L2),!,sort(L2,L1).

sort(L,L).

%List union

list_union(L1,[],L1).

list_union([],L2,L2).

list_union([X|L1],L2,[X|L3]):-list_union(L1,L2,L3).

%BEGIN Task Window, e_Create

task_win_eh(_Win,e_Create(_),0):-!,

%BEGIN Task Window, InitControls, 00:22:46-3.5.2007, Code automatically updated!

win_CreateControl(wc_Edit,rct(140,50,225,75),"",_Win,[wsf_Group,wsf_TabStop,wsf_AutoHScroll,wsf_AlignLeft],idc_edit),

win_CreateControl(wc_Text,rct(10,25,194,45),"Добавить элемент в список",_Win,[wsf_AlignLeft],idct_static_text),

win_CreateControl(wc_PushButton,rct(230,50,315,75),"Добавить",_Win,[wsf_Group,wsf_TabStop],idc_add),

win_CreateControl(wc_Text,rct(10,80,187,100),"Удалиь элемент из списка",_Win,[wsf_AlignLeft],idct_static_text1),

win_CreateControl(wc_Edit,rct(145,110,185,135),"0",_Win,[wsf_Group,wsf_TabStop,wsf_AutoHScroll,wsf_AlignLeft],idc_edit1),

win_CreateControl(wc_PushButton,rct(230,110,315,135),"Удалить",_Win,[wsf_Group,wsf_TabStop],idc_del),

win_CreateControl(wc_Text,rct(10,50,135,75),"Введите элемент",_Win,[wsf_AlignLeft],idct_static_text2),

win_CreateControl(wc_Text,rct(10,110,111,135),"Укажите номер",_Win,[wsf_AlignLeft],idct_static_text3),

win_CreateControl(wc_LBox,rct(325,25,440,135),"",_Win,[wsf_Group,wsf_TabStop,wsf_VScroll,wsf_NoIntegralHeight],id_lbox),

win_CreateControl(wc_PushButton,rct(450,25,550,55),"Реверс",_Win,[wsf_Group,wsf_TabStop],idc_rev),

win_CreateControl(wc_PushButton,rct(450,105,550,135),"Сортировать",_Win