Дерева (графи), Детальна інформація

$ (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.