WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаМатематика, Геометрія, Статистика → Дерева (графи) - Реферат

Дерева (графи) - Реферат


Реферат на тему:
Дерева (графи)
Означення. Деревом називається граф без циклiв, в якому видiлено окрему вершину, яку називають коренем дерева.
Структурою типу дерева будемо називати або NIL (порожнє дерево), або структуру (Значення . (Лiвий син . Правий син)), де лiвий та правий сини є структурами типа дерево. Наприклад, дерево яке складається з єдиного елемента, буде мати вигляд: (Element . (NIL . NIL)).
Функцiя INSEL вставляє елемент n в дерево tree за наступним правилом: Якщо дерево порожнє, то створити дерево (n . (NIL . NIL)). Iнакше вставити елемент в лiве пiддерево якщо n менше за значення поточної вершини або в праве пiддерево, якщо бiльше. Функцiя INSL створює за списком сортуюче дерево, вершинами якого будуть всi елементи списка. Дерево називається сортуючим, оскiльки при обходi його злiва направо ми отримаємо вiдсортований список елементiв у зростаючому порядку.
(DEFUN insel (n tree)
((NULL tree) (CONS n (CONS NIL NIL)))
((> n (CAR tree)) (cons (car tree) (cons (cadr tree) (insel n (cddr tree)))))
(cons (car tree) (cons (insel n (cadr tree)) (cddr tree))) )
(DEFUN INSL (lst tree)
((NULL lst) tree)
(SETQ tree (insel (car lst) tree))
(INSL (CDR lst) tree) )
Наступнi двi функцiї виконують обхiд дерева: PUD (Print Up-Down) - обхiд згори вниз, PLR (Print Left-Right) - обхiд злiва направо.
(DEFUN PUD (tree) (DEFUN PLR (tree)
((NULL tree)) ((NULL tree))
(PRIN1 (CAR tree)) (SPACES 3) (PLR (CADR tree))
(PUD (CADR tree)) (PRIN1 (CAR tree)) (SPACES 3)
(PUD (CDDR tree)) ) (PLR (CDDR tree)) )
Функцiя REVT (Reverse Tree) обертає дерево: кожне праве пiддерево стає лiвим пiддеревом i навпаки.
(DEFUN REVT (tree)
((NULL tree) NIL)
(CONS (CAR tree) (CONS (REVT (CDDR tree)) (REVT (CADR tree)))) )
Приклади
$ (SETQ a (INSL '(5 1 7 3 9 2 4 8 10) NIL)) $ (SETQ b (REVT a))
$ (PLR a) $ (PLR b)
1 2 3 4 5 7 8 9 10 T 10 9 8 7 5 4 3 2 1
Функцiя HEIGHT обчислює висоту дерева. Вважатимемо, що висота порожнього дерева дорiвнює 0. Висота непорожнього дерева дорiвнює максимумовi мiж висотами лiвого та правого пiддерев плюс одиниця. (HEIGHT a) = 4, де a взято з попереднього прикладу.
(DEFUN HEIGHT (tree)
((NULL tree) 0)
(MAX (ADD1 (HEIGHT (CADR tree))) (ADD1 (HEIGHT (CDDR tree)))) )
Функцiї модифiкатора
Функцiї модифiкатора виконують переадресацiю вказiвникiв в структурах даних мови програмування Лiсп.
1. RPLACA . Вiдбувається замiна CAR-елемента об'єкта1 вказiвником на об'єкт2, повертається модифiкований об'єкт. Якщо об'єкт1 - список, то перший елемент списка замiнюється на об'єкт2. Якщо об'єкт1 - бiнарне дерево, то його лiвий син замiнюється на об'єкт2. Якщо об'єкт1 - символ (aле не NIL), то символ приймає значення об'єкт2.
$ (SETQ a '(a b c d)) $ (SETQ b '((1 . 2) . (3 . 4))) $ (SETQ s 'd)
$ (RPLACA a '(11 12)) $ (RPLACA b 5) $ (RPLACA s 'g)
((11 12) b c d) (5 . (3 . 4)) Val(s)=d,Val(d) = g
2. RPLACD . Вiдбувається замiна CDR-елемента об'єкта1 вказiвником на об'єкт2, повертається модифiкований об'єкт. RPLACA та RPLACD є основними функцiями, якi змiнюють фiзичну структуру спискiв. Їх можна представити через узагальнену функцiю присвоєння SETF:
(RPLACA x y) - це (SETF (CAR x) y)
(RPLACD x y) - це (SETF (CDR x) y)
3. NSUBSTITUTE . Модифiкуються конси найвищого рiвня списку. Старi елементи замiнюються на новi на нульовому рiвнi вкладеностi, для яких перевiрка по тесту не дорiвнює NIL. Якщо тест не вказано, то по замовченню тест = EQL.
$ (NSUBSTITUTE 1 3 '(4 5 6 (3 3 4 5) 3 4 1))
(4 5 6 (3 3 4 5) 1 4 1)
$ (NSUBSTITUTE 10 5 '(4 5 6 3 4 1) >) $ (NSUBSTITUTE 10 5 '(4 5 6 3 4 1)
4. NSUBST . Функцiя працює як i NSUBSTITUTE, але модифiкуються конси всiх рiвнiв списку.
$ (NSUBST 1 3 '(4 5 6 (3 3 4 5) 3 4 1))
(4 5 6 (1 1 4 5) 1 4 1)
5. DELETE . Вилучає зi списку всi елементи, для яких ознака перевiрки за тестом не дорiвнює NIL.
$ (DELETE 3 '(1 2 3 4 3 2 1))
(1 2 4 2 1)
6. NREVERSE . Обертає елементи списку, зчеплених з об'єктом.
$ (NREVERSE '(a b c d)) $ (NREVERSE '(1 2 3 (1 2 3) 4 5 6) '(1 2 3))
(d c b a) (6 5 4 (1 2 3) 3 2 1 1 2 3)
7. NBUTLAST . Якщо n - нуль або додатне цiле, то функцiя NBUTLAST повертає список без n останнiх елементiв (вiдбувається замiна n-го конса, взятого з кiнця списку на NIL). Якщо другий аргумент не вказано, то за замовченням n=1.
$ (NBUTLAST '(a b c d e)) $ (NBUTLAST '(a b c d e) 3)
(a b c d) (a b)
8. NCONC ... . Повертається список, який складається з елементiв спискiв - аргументiв у вказаному порядку. Вiдбувається модифiкацiя останнiх CDR-елементiв спискiв. Якщо виконати команду (NCONC list list), де list - будь-який список, то результатом буде циркулянтний список, процес побудови якого буде нескiнченним.
$ (NCONC '(1 2) '(3 4) '(5 6 7))
(1 2 3 4 5 6 7)
9. SPLIT . Розбиває список на два списки посерединi. Значенням списку стає його перша половина. Функцiя SPLIT повертає другу половину списку.
$ (SETQ a '(1 2 3 4 5 6)) $ a
$ (SPLIT a) (1 2 3)
(4 5 6)
10. SORT . Сортуються елементи списку на основi тесту.
$ (SORT '(2 5 3 4 1 6 8 9 7) >)
(9 8 7 6 5 4 3 2 1)
Завдання 1. Знайти кiлькiсть листiв в заданому деревi.
2. Знайти середнє арифметичне чисел, якi знаходяться у вершинах дерева.
3. Написати функцiю швидкого сортування QSORT.
Робота з файлами
По замовченню за пристрiй потокового вводу (CIS - Current Input Stream) береться консоль.
1. Для читання даних з вхiдного потоку використовують функцiю READ. Пiсля виконання команди (SETQ a (READ)) ви повиннi ввести з консолi вираз, який буде прочитано та присвоєно змiннiй а. При цьому якщо буде
Loading...

 
 

Цікаве