(DEFUN move_per (lst)
(PRIN1 lst) (TERPRI 1)
(SETQ cur NIL)
(LOOP
((ATOM (CDR lst)))
((< (CAR lst) (CADR lst)) (SETQ a (POP lst))
(SETQ b (POP lst))
(PUSH a lst)
(PUSH b lst)
(SETQ lst (APPEND (REVERSE cur) lst))
(move_per lst) )
(PUSH (POP lst) cur)
) )
5. Дерева
Деревом називається граф без циклів, в якому виділено окрему вершину, яку називають коренем дерева.
Структурою типу дерева будемо називати або NIL (порожнє дерево), або структуру типу (Значення . (Лівий син . Правий син)), де лівий та правий сини є структурами типа дерево. Наприклад, дерево яке складається з єдиного елемента, буде мати вигляд: (Element . (NIL . NIL)).
Функція INSEL вставляє елемент n в дерево tree за наступним правилом: Якщо дерево порожнє, то створити дерево (n . (NIL . NIL)). Інакше вставити елемент в ліве піддерево якщо n менше за значення поточної вершини або в праве піддерево, якщо більше. Функція INSL створює за списком сортуюче дерево, вершинами якого будуть всі елементи списка. Дерево називається сортуючим, оскільки при обході його зліва направо ми отримаємо відсортований список елементів у зростаючому порядку.
(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) )
Наступні дві функції виконують обхід дерева: PUD (Print Up-Down) — обхід згори вниз, PLR (Print Left-Right) — обхід зліва направо.
(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)) )
Функція REVT (Reverse Tree) обертає дерево: кожне праве піддерево стає лівим піддеревом і навпаки.
(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
Функція HEIGHT обчислює висоту дерева. Вважатимемо, що висота порожнього дерева дорівнює 0. Висота непорожнього дерева дорівнює максимумові між висотами лівого та правого піддерев плюс одиниця. (HEIGHT a) = 4, де a взято з попереднього прикладу.
(DEFUN HEIGHT (tree)
((NULL tree) 0)
(MAX (ADD1 (HEIGHT (CADR tree)))
(ADD1 (HEIGHT (CDDR tree)))) )
6. Робота з файлами
По замовченню за пристрій потокового вводу (CIS - Current Input Stream) береться консоль.
1. Для читання даних з вхідного потоку використовують функцію READ. Після виконання команди (SETQ a (READ)) ви повинні ввести з консолі вираз, який буде прочитано та присвоєно змінній а. При цьому якщо буде введено декілька об’єктів, то змінній а буде присвоєно перший об’єкт. Наприклад, якщо ви введете: as bf gh, то змінна a прийме значення as. Якщо Ви хочете ввести список (складний об’єкт), то його необхідно вводити в круглих дужках: (as df gh).
2. Функція (CLEAR-INPUT) чистить буфер вводу. В будь-якому випадку повертається NIL.
3. Функція (READ-LINE) читає елементи з CIS поки не буде прочитано символ переходу на новий рядок (<return>). Повертається символ, Р-ім’я якого складається з усіх прочитаних символів як ті були розташовані у вхідному рядку, окрім <return>.
4. Функція (READ-CHAR) читає наступний елемент з CIS та повертає його.
5. Функція (UNREAD-CHAR) повертає в CIS останній прочитаний символ.
6. Функція (LISTEN) повертає T якщо CIS не порожній, та NIL якщо ми дійшли до кінця файлу.
7. Функції (OPEN-INPUT-FILE “<name>”) та (CLOSE-INPUT-FILE “<name>”) використовуються для відкриття та закриття файла <name> для вводу.
8. Функції (OPEN-OUTPUT-FILE “<name>”) та (CLOSE-OUTPUT-FILE “<name>”) відповідно відкривають та закривають файл <name> для виводу інформації.