UkrReferat.com
найбільша колекція україномовних рефератів

Всього в базі: 75855
останнє поновлення: 2016-12-09
за 7 днів додано 17

Реферати на українській
Реферати на російській
Українські підручники

$ Робота на замовлення
Реклама на сайті
Зворотній зв'язок

 

ПОШУК:   

реферати, курсові, дипломні:

Українські рефератиРусские рефератыКниги
НазваДерева (графи) (реферат)
Авторdimich
РозділМатематика, алгебра, геометрія, статистика
ФорматWord Doc
Тип документуРеферат
Продивилось2752
Скачало536
Опис
ЗАКАЧКА
Замовити оригінальну роботу

Реферат на тему:

 

Дерева (графи)

 

Означення. Деревом називається граф без цикл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

-----> Page:

0 [1] [2] [3] [4]

ЗАМОВИТИ ОРИГІНАЛЬНУ РОБОТУ