Головна Головна -> Реферати українською -> Інформатика, комп'ютери, програмування -> Дерева (графи)

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

Назва:
Дерева (графи)
Тип:
Реферат
Мова:
Українська
Розмiр:
12,18 KB
Завантажень:
29
Оцінка:
 
поточна оцінка 5.0


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2  3 
Дерева (графи)

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

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2  3 



Реферат на тему: Дерева (графи)

BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок