На этом шаге мы рассмотрим задачи на использование списков свойств.

Фрагмент теории

    Сейчас мы познакомим Вас с фундаментальным типом данных языка LISP, называемый списком свойств атома (P-списком).

    Атом вместе со списком свойств имеет структуру, изображенную ниже (P-имя атома - "печатное" имя):

Рис.1. Структура атома со списком свойств

    Доступ к списку свойств всегда открывается через информационную ячейку данного атома. На рисунке буква A обозначает специальный адрес, по которому могут быть распознаны информационные ячейки.

    Список свойств состоит из звеньев - по две ячейки в каждом звене. Первая ячейка каждого звена содержит так называемый индикатор i_k - наименование свойства. Более точно, индикатор - это адрес информационной ячейки атома, используемого в качестве наименования свойства. Во второй ячейке звена содержится адрес p_k самого свойства - определяющего выражения функции.

    Список свойств атома можно по необходимости обновлять или удалять, однако программист должен сам предусматривать и обрабатывать интересующие его свойства.

    1. Присваивание нового свойства или изменение значения существующего свойства осуществляется псевдофункцией PUT:

   (PUT VARIABLE PROPNAME PROPVAL)

• VARIABLE - атом;
• PROPNAME - имя свойства;
• PROPVAL - значение свойства.

    Функция PUT возвращает значение ее третьего аргумента PROPVAL.

    Побочный эффект заключается в модификации списка свойств атома VARIABLE:

• если в списке свойств не было свойства с именем PROPNAME, то свойство с таким именем и значением PROPVAL будет добавлено в список;
• если свойство с именем PROPNAME уже присутствовало в списке свойств атома VARIABLE, то значение этого свойства будет заменено на новое значение PROPVAL.

    2. Удаление свойства и его значения осуществляется псевдофункцией REMPROP:

   (REMPROP VARIABLE PROPNAME)

• VARIABLE - атом;
• PROPNAME - имя свойства.

    Функция REMPROP возвращает в качестве значения имя удаляемого свойства. Если удаляемого свойства нет, то возвращается NIL.

    Свойство можно "удалить", присвоив ему значение NIL:

   (PUT VARIABLE PROPNAME NIL)

    В этом случае имя свойства и значение NIL физически остаются в списке свойств.

    3. Выяснить значение свойства, связанного с атомом, можно с помощью функции GET:

    (GET VARIABLE PROPNAME)

• VARIABLE - атом;
• PROPNAME - имя свойства.

   $ (PUT A SVOISTVO 1111)
   1111
   $ (GET A SVOISTVO)
   1111

    Следующий пример является очень важным!

   $ (SETQ A 0)
   0
   $ (PUT A SVOISTVO1 111)
   111
   $ (PUT A SVOISTVO2 222)
   222
   $ (CAR A)
   0
   $ (CDR A)
   ((SVOISTVO1 . 111) (SVOISTVO2 222))

    Таким образом, вычисление функции CDR от P-имени атома позволяет "проникнуть" в структуру списка свойств! Оказывается, что список свойств - это ассоциативный список, где на месте ключей расположены свойства, а на месте данных, ассоциированных с ключами, находятся значения соответствующих свойств.

    4. Для описания свойств, принимающих всего два возможных значения, в языке LISP имеется механизм флагов.

    Флаг - это свойство без значения. Единственно, что можно сказать о флаге - есть он у атома или нет.

    Для того, чтобы снабдить атом флагом, существует функция FLAG. Эта функция имеет два аргумента. Первый - список атомов, второй - имя флага:

   (FLAG ATOM FLAGNAME)

• ATOM - атом,
• FLAGNAME - имя флага, который появится у атома.

    Функция FLAG делает FLAGNAME первым элементом в списке свойств атома ATOM, если он там отсутствовал. Например:

   $ (FLAG JOHN MALE)    $ (FLAG SUE FEMALE)
   MALE                  FEMALE

    Функция

   (REMFLAG ATOM FLAGNAME)

"снимает" с атома ATOM флаг FLAGNAME (удаляет флаг FLAGNAME из списка свойств атома ATOM) и возвращает T. Если флаг не найден, то функция возвращает NIL. Например:

   $ (FLAG JAN MALE)
   MALE
   $ (FLAG JAN TALL)
   TALL
   $ (REMFLAG JAN MALE)
   T
   $ (FLAGP JAN MALE)
   NIL
   $ (FLAGP JAN TALL)
   (TALL)

    Если FLAGNAME является элементом списка свойств атома ATOM, то функция

   (FLAGP ATOM FLAGNAME)

возвращает значение не NIL (а именно: список свойств, начиная с FLAGNAME), иначе возвращает NIL. Например:

   $ (FLAGP JOHN MALE)
   (MALE)
   $ (FLAGP SUE MALE)
   NIL

Демонстрационный пример

    Построение списка свойств атома "с клавиатуры".

   (DEFUN DEMO_2 (LAMBDA NIL
      (PRINT "Построение списка свойств данного атома:")
      (PRINT "Введите имя атома:") (SETQ ATM (READ))
      (LOOP
         (PRINT "Введите имя свойства (окончание ввода - !:")
         (SETQ PROPNAME (READ))
         ( (EQ PROPNAME '!) )
         (PRINT "Введите значение свойства:")
         (SETQ PROPVAL (READ))
         (PUT ATM PROPNAME PROPVAL)
      )
      ;Взглянем на список свойств
      (PRINT "Список свойств атома:") (PRINT (CDR ATM))
   ))

Задачи для самостоятельного решения

    Под элементом мы будем понимать точечную пару, состоящую из имени свойства и его значения.

1. Функция GET возвращает в качестве результата NIL в том случае, если у символа нет данного свойства, либо если значением этого свойства является NIL. Следовательно, функцией GET нельзя проверить, есть ли некоторое свойство в списке свойств. Напишите предикат (HASHPROP ATM PROP), который проверяет, обладает ли данный атом ATM указанным свойством PROP.
2. Определите функцию REMPROPS, которая удаляет все свойства заданного атома.
3. Написать функцию, позволяющую получить список всех свойств данного атома.
4. Написать функцию, позволяющую получить список значений всех свойств данного атома.
5. Определить функцию (LASTHALF ATM), которая возвращает список из последних n точечных пар в списке свойств атома ATM из 2*N точечных пар.
6. Отыскать в списке свойств такое свойство, которое встречается перед заданным свойством.
7. Установите, имеют ли два списка свойств X и Y одинаковую длину.
8. Определить функцию (EQUALPROP ATM), возвращающую T, если в списке свойств атома ATM значения всех свойств равны друг другу и NIL в противном случае.
9. Напишите функцию (INDEXMAX ATM), которая возвращает номер максимального свойства в списке свойств атома ATM (значения всех свойств являются числами).
10. Напишите функцию, возвращающую последний элемент списка свойств заданного атома.
11. Напишите функцию, зависящую от четырех аргументов ATM, PROP, PROPVAL и N, которая добавляет точечную пару (PROP . PROPVAL) на N-е место в список свойств атома ATM.
12. Напишите функцию, удаляющую из списка свойств данного атома ATM свойства с одинаковыми значениями свойств.
13. Напишите функцию, удаляющую из списка свойств данного атома все точечные пары, стоящие на четных местах в нем.
14. Определите функцию, которая по данному атому и значению свойства строит список его свойств с данным значением.
15. Определите функцию, обращает список свойств данного атома.
16. Напишите функцию, "обрывающую" список свойств заданного атома, если он состоит более чем из N точечных пар.
17. Определить, имеются ли в списке свойств заданного атома два подряд идущих в списке свойства, значения которых равны нулю.
18. Из списка свойств данного атома, первое свойство которого обладает неотрицательным значением, удалить все свойства с отрицательными числовыми значениями.
19. Написать программу определения количества свойств данного атома, числовые значения которых удовлетворяют условию:

       0 < Значение_свойства  <= Номер_свойства в списке свойств
    

20. Найти длину самой длинной последовательности нулей значений свойств в списке свойств данного атома.
21. Проверить, является ли последовательность числовых значений свойств данного атома упорядоченной по убыванию.
22. Выясните, является ли список свойств данного атома подсписком списка свойств другого атома.
23. Замените отрицательные значения числовых свойств в списке свойств данного атома на 0.
24. Выясните, есть ли в списке свойств заданного атома два свойства с одинаковыми значениями в смысле EQUAL.
25. Даны два атома. Проверьте, есть ли в их списках свойств одинаковые свойства (одинаковые элементы).
26. Найдите наименьший номер чаще всего встречающегося значения свойств в списке свойств данного атома.
27. Все свойства заданного атома, значения которых не равные нулю, переписать (сохраняя их порядок) в начало списка свойств, а остальные - в конец.
28. Напишите функцию для проверки, совпадают ли первый элемент списка свойств атома ATM1 и последний элемент списка свойств атома ATM2.
29. Значениями всех свойств в списке свойств данного атома являются латинские буквы. Написать функцию для подсчета количества гласных букв в значениях свойств.
30. Напишите функцию для проверки, совпадают ли второй и предпоследнего элементы списка свойств данного атома.
31. Напишите функцию, возвращающую N последних элементов списка свойств данного атома.
32. Определите функцию, возвращающую список свойств атома ATM1, не содержащихся в списке свойств атома ATM2.
33. Даны два атома со списками свойств, имеющих одинаковую длину. Определите функцию, которая по имени свойства атома ATM1 возвращает соответствующее имя свойства атома ATM2.
34. Выбрать из списка свойств данного атома с числовыми значениями все свойства, значения которых делятся на 3, и сформировать из них "обычный" список.
35. Вычислить количество элементов списка свойств данного атома, имеющих положительные, отрицательные и нулевые значения свойств.
36. Опишите функцию, вычисляющую произведение числовых значений свойств списка свойств данного атома.
37. В списке свойств данного атома переставьте местами первый и последний элементы.
38. Напишите функцию, осуществляющую циклическую перестановку элементов списка свойств данного атома, при которой первый элемент списка становится последним.
39. Написать функцию для поиска таких свойств в списке свойств данного атома, значения которых заключены между целыми числами H и L (H <=L).
40. Напишите функцию PROPREVERSE2, которая соединяет списки свойств двух данных атомов, причем оба списка свойств должны быть обращены.
41. Написать функцию DELETEPROP, которая удаляет N-й элемент списка свойств данного атома.
42. Вычислите сумму числовых значений свойств списка свойств данного атома.
43. Определите функцию, которая возвращает последний элемент списка свойств данного атома.

    На следующем шаге мы приведем задачи на использование бинарных деревьев

Предыдущий шаг Содержание Следующий шаг