2

我有一个家庭作业，我需要做以下事情：

以树为参数并返回 nil/non-nil 值的函数，指示树是否仅包含唯一节点（即：树中没有重复节点）。

到目前为止，我已经编写了以下代码。我是一个 lisp 新手，我需要完成我的作业。这是我尝试实施的第一个解决方案。但是当我编译它时，它给了我以下错误：函数位置必须包含一个符号或 lambda 表达式：（第一棵树）。

  (defun in (tree)
    (cond ((null tree)
           t)
          ((eq (first tree) (second tree))
           nil)
          ((listp (first tree))
           (or ((first tree) in  (second tree))
               ((first tree) in  (rest tree))))
          (t
           ((first tree) in (rest tree)))))

这是我的第二次尝试，它也不起作用：

(defun flatten (structure)
  (cond ((null structure) nil)
        ((atom structure) `(,structure))
        (t (mapcan #'flatten structure))))

(defun uniNodes (inList &optional (out t) (test 0))
  (cond ((null inList)
         out)
        ((zerop test)
         (uniNodes (flatten(cons (first inList) (rest inList))) out (+ test 1)))
        ((eq t (first out))
         (uniNodes (rest inList) (compare1 (first inList) (rest inList) (first out)) test))
        ((eq nil (first out))
         out)))

(defun compare1 (a list &optional (out t))
  (cond ((null list)
         out)
        ((equal a (first list))
         nil)
        (t
         (compare1 a (rest list) (first out)))))

你能给我一些见解吗？

4

2 回答 2

1

我建议你递归遍历树，收集表中的节点。

(defun find-dupes (tree)
  (let ((table (make-hash-table)))
    (labels ((check-node (node)
               (when (consp node)
                 (when (gethash node table)
                   (return-from find-dupes node)) ; return the dupe
                 (setf (gethash node table) node) ; memorize the node
                 (check-node (car node))
                 (check-node (cdr node)))))
      (check-node tree))))

您将需要弄清楚如何更改上述代码以适应您的问题。

至于你的错误，

Function position must contain a symbol or lambda expression: (FIRST TREE)

意味着您需要修复函数调用

(A in B)

和

(in A B)

您没有解释您的第二次尝试有什么问题，尽管它似乎是参数大小的二次方。

于 2012-11-28T18:30:02.510 回答
0

如果树不是很大，那么这种递归方法可以：

(defun tree-contains-duplicates-p (tree)
  (labels ((%tree-contains-duplicates-p (node table)
             (cond
               ((null node) t)
               ((consp node)
                ;; lists can't be same unless they have
                ;; same atoms, but having two `nil' lists
                ;; is a trivial case, which you want to ignore
                ;; probably
                (and (%tree-contains-duplicates-p (car node) table)
                     (%tree-contains-duplicates-p (cdr node) table)))
               (t (unless (gethash node table)
                    (setf (gethash node table) t))))))
    (not (%tree-contains-duplicates-p tree (make-hash-table)))))

否则，您希望将其展开到一个循环中，在其中记录遍历树所采取的最后一个动作，并从那里击中叶子恢复。

看起来这应该工作：

(defun tree-contains-duplicates-p (tree)
  (loop with leaf = tree
     with stack = nil
     with table = (make-hash-table)
     while (or leaf stack)
     do (cond
          ((null leaf)
           (setq leaf (car stack) stack (cdr stack)))
          ((consp (car leaf))
           (when (cdr leaf)
             (setq stack (cons (cdr leaf) stack)))
           (setq leaf (car leaf)))
          (t (setq leaf (cdr leaf))))
       (when leaf
         (if (gethash (car leaf) table)
             (return t)
             (setf (gethash (car leaf) table) t)))))
于 2012-11-28T18:23:22.060 回答