tree - 检查节点是否属于 tree lisp

Question

我必须检查一个节点是否属于 lisp 中的一棵树，但我不知道为什么它不起作用。

这是我的代码:

(defun number-of-elems (l)
  (cond
    ((null l) 0)
    (t (1+ (number-of-elems (cdr l))))))


(defun ver (tree e)
  (setq message1 "The node belongs to the tree.")
  (setq message2 "The node does not belong to the tree.")
  (cond
    ((null tree) nil)
    ((= (number-of-elems tree) 1)
     (cond
       ((= (car tree) e) (princ message1))
       (t (princ message2))))
    ((> (number-of-elems tree) 1)
     (cond
       ((listp (car tree)) (ver (car tree) e))            
       ((atom (car tree)) 
        (cond
          ((equal (car tree) e) (princ message1))
          (t (ver (cdr tree) e))))
       ((number (car tree)) 
        (cond
          ((= (car tree) e) (princ message1))
          (t (ver (cdr tree) e))))
       (t (mapcar #'ver (cdr tree) e))))))

这是它应该如何工作的一个例子:

树是 (a (b (c)) (d) (e (f))) 节点是 b => true(我想打印消息而不是真或假)

Answer 1

不是数字

= of ((3 (4)) 4) arguments should be of type NUMBER

错误来自(= (car tree) e)，因为你假设如果tree只有一个元素，那么这个元素必然是一个数字。这里，单例的car本身就是一个列表，这使得=失败。

不要把所有东西都放在一个地方

I wanted to print a message instead of true or false

定义另一个 调用第一个函数的函数，它返回 T 或 NIL，否则您将无法重用您的代码。 此外，(setq message1) 不是您想要的，因为它修改了 message1 符号的全局绑定(bind)。一个人会使用 let ，但是此处如果您只是执行 (princ (if (ver ...) "Ok""Not found"))，则不需要它。

停止迭代该列表

您可以使用 number-of-elems 对列表中的元素进行计数(另请参阅 length)。如果您对每个元素执行线性运算，您将具有二次时间复杂度。为了访问一棵树，您只想区分空列表和非空列表。一般情况下已经支持长度等于1的情况。

删除死代码

(number (car tree)) 应该是 (numberp (car tree))(注意 p)。但更重要的是，与这个子句相关的代码是死代码:如果你有一个数字，它就是一个原子，并且与前面的子句匹配。此外，使用 equal 进行测试也适用于数字。

同样，我看不到如何到达默认子句 (T (mapcar ...))。这是一个好消息，因为这里 mapcar 将在每对 (x,y) 元素上应用 #'ver，其中 x 取自 (cdr tree) 和 y 来自 e !结果是一个列表!由于您正在寻找匹配项，因此可以使用 some相反，但您已经可以在 listp 子句中涵盖这种情况。 - (listp (car tree)) 如果您的第一个元素是一个列表，您可以使用该列表递归调用该函数，但是 (cdr tree) 呢？在 (car tree) 中找到该元素，或未找到该元素，您应该尝试使用其余元素。

提示

这是你想要的执行轨迹:

    0: (ver (1 2 (3 (4))) 4)
      1: (ver 1 4)
      1: ver returned nil
      1: (ver 2 4)
      1: ver returned nil
      1: (ver (3 (4)) 4)
        2: (ver 3 4)
        2: ver returned nil
        2: (ver (4) 4)
          3: (ver 4 4)
          3: ver returned t
        2: ver returned t
      1: ver returned t
    0: ver returned t