На этом шаге мы рассмотрим задачи на обработку A-списков.
Фрагмент теории
Ассоциативный список (A-список, список пар) - это фундаментальный тип данных, представляющий собой список точечных пар вида: ( (A1 . T1) (A2 . T2) ... (AN . TN) )
Первый элемент пары (CAR) называют ключом, а второй (CDR) - связанными с ключом данными. Обычно ключом является атом. Связанные с ним данные могут быть атомами, списками или какими-нибудь другими объектами языка LISP.
Приведем формальное определение A-списка в форме Бэкуса-Наура:
<Ассоциативный список> ::=
NIL | (<Точечная пара> . <Ассоциативный список>)
<Точечная пара> ::=
(<Атом> . <Атом>) | (<Атом> . <Точечная пара>) |
(<Точечная пара> . <Атом>) |
(<Точечная пара> . <Точечная пара>)
Приведем графическое представление A-списка:
Рис.1. Графическое представление A-списка
В работе со списками пар нужно уметь:
- строить ассоциативные списки,
- искать данные по ключу,
- обновлять данные в ассоциативном списке.
Демонстрационные примеры
Пример 1. Библиотека функций для работы с ассоциативными списками
(DEFUN DEMO_1 (LAMBDA NIL
; Инициализация атомов A и B ;
(SETQ A '(JAPAN USSR))
(SETQ B '(TOKIO MOSCOW))
(PRIN1 "Построим A-список из списков A и B: ")
(PRINT (SETQ ALIST (PAIRLIS A B NIL)))
; ----------------------------------------- ;
(PRIN1 "Проверим составные части A-списка: ")
(PRINT (REKEY ALIST))
(PRINT (REDATA ALIST))
; ------------------------------------------------- ;
(PRIN1 "Найдем данные, соответствующие ключу USSR: ")
(PRINT (ASSOC1 USSR ALIST))
(PRIN1 "Найдем данные, соответствующие ключу JAPAN: ")
(PRINT (ASSOC1 JAPAN ALIST))
; -------------------------------------------------- ;
(PRIN1 "Найдем ключ, соответствующий данным MOSCOW: ")
(PRINT (RASSOC MOSCOW ALIST))
; -------------------------------------------------- ;
(PRINT "Добавление в начало A-списка точечной пары: ")
(PRINT (SETQ ALIST (ACONS USA WASHINGTON ALIST)))
; ---------------------------------------------------- ;
(PRINT "Изменение данных, соответствующих ключу USSR: ")
(PUTASSOC USSR SPB ALIST)
))
; ----------------------------------- ;
(DEFUN PAIRLIS (LAMBDA (KEY DATA ALIST)
; Построение A-списка из списка ключей KEY и списка ;
; данных DATA путем добавления новых пар к существу- ;
; ющему списку ALIST ;
( (NULL KEY) ALIST )
( (NULL DATA) ALIST )
( CONS (CONS (CAR KEY) (CAR DATA))
(PAIRLIS (CDR KEY) (CDR DATA) ALIST) )
))
; ----------------------------- ;
(DEFUN ASSOC1 (LAMBDA (KEY ALIST)
; Поиск в списке пар ALIST данных, соответствующих ;
; ключу KEY ;
(COND ( (NULL ALIST) NIL )
( (EQ (CAAR ALIST) KEY) (CAR ALIST) )
; Возвращается первая найденная пара, ;
; содержащая ключ KEY ;
( T (ASSOC1 KEY (CDR ALIST)) )
)
))
; ------------------------------ ;
(DEFUN RASSOC (LAMBDA (DATA ALIST)
; Поиск в списке пар ALIST ключа, соответствующего ;
; данным DATA ;
(COND ( (NULL ALIST) NIL )
( (EQ (CDAR ALIST) DATA) (CAR ALIST) )
; Возвращается пара, содержащая данные DATA ;
( T (RASSOC DATA (CDR ALIST)) )
)
))
; ---------------------------- ;
(DEFUN ACONS (LAMBDA (X Y ALIST)
; Добавление в начало списка ALIST ;
; точечной пары (X . Y) ;
(CONS (CONS X Y) ALIST)
))
; ------------------------------------ ;
(DEFUN PUTASSOC (LAMBDA (KEY DATA ALIST)
; Изменение данных, соответствующих ключу KEY, ;
; на данные DATA ;
( (NULL ALIST) NIL )
( (EQ (CAAR ALIST) KEY) (RPLACD (CAR ALIST) DATA) )
( (NULL (CDR ALIST))
(RPLACD ALIST (LIST (CONS KEY DATA))) )
; Добавление новой пары (KEY . DATA) ;
( PUTASSOC KEY DATA (CDR ALIST) )
))
; ------------------------ ;
(DEFUN REKEY (LAMBDA (ALIST)
; Восстановление списка ключей по известному А-списку ;
(COND ( (NULL ALIST) NIL )
( T (CONS (CAR (CAR ALIST))
(REKEY (CDR ALIST))) )
)
))
; ------------------------- ;
(DEFUN REDATA (LAMBDA (ALIST)
; Восстановление списка данных по известному А-списку ;
(COND ( (NULL ALIST) NIL )
( T (CONS (CDR (CAR ALIST))
(REDATA (CDR ALIST))) )
)
))
Пример 2. Построение ассоциативного списка "с клавиатуры".
(DEFUN DEMO_2 (LAMBDA NIL
(PRINT "Построение ассоциативного списка:")
(SETQ ALIST NIL)
(LOOP
(PRINT "Введите ключ (окончание ввода - !:")
(SETQ KEY (READ))
( (EQ KEY '!) )
(PRINT "Введите данное для этого ключа:")
(SETQ DATA (READ))
(SETQ ALIST (ACONS KEY DATA ALIST))
)
; Взглянем на ассоциативный список
(PRINT "Ассоциативный список:") (PRINT ALIST)
))
; ------------------------------
(DEFUN ACONS (LAMBDA (X Y ALIST)
; Добавление в начало списка ALIST
; точечной пары (X . Y)
(CONS (CONS X Y) ALIST)
))
Задачи для самостоятельного решения
- Напишите функцию, возвращающую N-ю пару данного ассоциативного списка.
- Осуществите циклическую перестановку точечных пар ассоциативного списка: первая пара должна стать второй, вторая - третьей и т.д., последняя - первой.
- Напишите функцию для проверки, совпадают ли вторая и предпоследняя точечные пары ассоциативного списка LST.
- Напишите функцию, возвращающую ассоциативный список, содержащий N последних точечных пар данного ассоциативного списка LST.
- Определить функцию LASTHALF, которая возвращает ассоциативный список из последних N точечных пар заданного ассоциативного списка, содержащего 2N точечных пар.
- Отыскать в ассоциативном списке такую пару, которая встречается непосредственно перед заданной парой.
- Напишите функцию для проверки, совпадают ли первая точечная пара ассоциативного списка Х и последняя точечная пара ассоциативного списка Y.
- Напишите функцию, возвращающую последнюю пару данного ассоциативного списка.
- Написать функцию, возвращающую ассоциативный список, в котором каждая пара из данного ассоциативного списка LST имеет ровно одно вхождение.
- Напишите функцию, зависящую от трех аргументов X, N и LST, добавляющую точечную пару X на N-е место в ассоциативный список LST.
- Напишите функцию, удаляющую повторные вхождения точечных пар в данный ассоциативный список.
- Напишите функцию, удаляющую из ассоциативного списка все точечные пары, стоящие на четных местах.
- Определите функцию, которая по заданному ассоциативному списку возвращает список его точечных пар, встречающихся в нем более одного раза.
- Постройте функцию, которая переставляет элементы ассоциативного списка так, чтобы одинаковые точечные пары стали соседями.
- Напишите функцию, "обрывающую" ассоциативный список, если он состоит более чем из N точечных пар.
- Определить, имеются ли в заданном ассоциативном списке три подряд идущих заданных точечных пары.
- Написать функцию для определения количества точечных пар в заданном ассоциативном списке LST.
- Дан ассоциативный список А. Определить, сколько в нем различных точечных пар.
- Выясните, есть ли в данном ассоциативном списке две одинаковые точечные пары.
- Найдите номер чаще всего встречающейся точечной пары в заданном ассоциативном списке.
- Напишите функцию, осуществляющую "переворачивание" данного ассоциативного списка.
- Дан ассоциативный список А. Определить, сколько в нем одинаковых точечных пар.
На следующем шаге мы приведем задачи на использование списков свойств.
