1

LISP 的初学者在这里。我正在为即将到来的 LISP 考试做准备，但遇到了一个我无法解决的问题，所以我希望有经验的人可以帮助我。

无论如何，这是我的问题：给您一个列表，其中可能包含列表作为元素。你的任务是删除给定位置的原子元素。

列表和位置作为输入参数给出。

示例： Position=5 ， List=(1 (2 3) ((4)) (5 (6))) ，应该返回 (1 (2 3) ((4)) ((6)))。

这是我到目前为止所得到的......（PS 下面的代码在 imMaw 的帮助下工作，您可以检查编辑以查看我之前的错误）。

(defun number_of_atoms(List)
 (atoms List 0)
)
(defun atoms(List Number)
 (cond
  ((null List) Number)
  ((atom (car List)) (atoms (cdr List) (+ 1 Number)))
  ((+ (atoms (car List) Number) (atoms (cdr List) 0)))
 )
)
(defun deleteElement(Pos List)
 (deleteElementAcc Pos 1 List)
)
(defun deleteElementAcc(Pos CurrPos List)
(cond 
  ((null List) nil)
  ((and (atom (car List)) (not(eql CurrPos Pos))) (cons (car List) (deleteElementAcc Pos (+ CurrPos 1) (cdr List))))
  ((and (atom (car List)) (eql CurrPos Pos)) (deleteElementAcc Pos (+ CurrPos 1) (cdr List)))
  ((cons (deleteElementAcc Pos CurrPos (car List))
         (deleteElementAcc Pos (+ CurrPos (number_of_atoms(car List))) (cdr List))))
)
)
4

2 回答 2

1

为什么你在一半的地方用 z 拼写 Pos 和 CurrPos？

您的代码中的问题在于 cond 的最后一个分支。对List的cdr进行递归时，需要将CurrPos推进(car List)中的元素个数。一个简单的（长度列表）不起作用，因为它需要递归地计算子列表中的元素。

编辑：更详细说我们打电话 

(deleteElement 3 '((1 2) (3 4)))

你把它变成

(deleteElementPos 3 1 '((1 2) (3 4))),

这属于 cond 的最后一种情况，你得到

(cons (deleteElementAcc 3 1 '(1 2))
      (deleteElementAcc 3 1 '((3 4))))

请注意 currPos 对于列表的 cdr 是错误的 - 它应该是 3，而不是 1。您实际上希望您的代码变成

(cons (deleteElementAcc 3 1 '(1 2))
      (deleteElementAcc 3 (+ 1 2) '((3 4))))

因为 (car List) 中有 2 个元素。

所以，你只需要改变

(deleteElementAcc Pos CurrPos (cdr List))

进入

(deleteElementAcc Pos (+ CurrPos (recursive-length (car List))) (cdr List))

和程序递归长度，这是一个非常简单的函数。它应该计算子列表中的元素，例如 (recursive-length '((1 2) ((3)))) 返回 3。

于 2012-11-29T04:31:54.197 回答
0

虽然以任何方式解决这个问题都不是特别困难，但要很好地解决它确实不是一件容易的事。我的意思是大 O 和代码复杂性，以及极端情况的处理。我不确定这段代码是否能处理不正确的列表，并且它的某些部分肯定可以减少冗长，但从技术上讲，它就在那里。它以 O(n) 精确地遍历树，其中 n 是树中元素的数量，并且它使用 O(n + 2 * (最大深度)) 空间，即它将使用树已经使用的内存此外，内存与树的最大深度成正比。

未尝试识别循环列表或重复项：

(defun remove-from-tree-linear (tree &rest positions)
  (loop with node = tree
     with nilcar = (gensym)
     with positions = (sort (remove-duplicates positions) #'<)
     with counter = 0
     with copy = nil
     with root = nil
     with stack = nil
     with backrefs = nil
     while (or node stack) do
       (cond
         ((null node)
          (setf backrefs (cdr backrefs))
          (when (car stack)
            (setf copy (car backrefs)))
          (setf node (car stack) stack (cdr stack)))
         ((consp (car node))
          (if copy
              (if (eq (car copy) nilcar)
                  (setf (car copy) (list nilcar)
                        copy (car copy)
                        (car backrefs) copy)
                  (setf (cdr copy) (list nilcar)
                        copy (cdr copy)
                        (car backrefs) copy))
              (setf copy (list nilcar)
                    root copy))
          (setf backrefs (cons copy backrefs))
          (setf stack (cons (cdr node) stack)
                node (car node)))
         (t (if (and positions (= counter (car positions)))
                (setf positions (cdr positions))
                (if copy
                    (progn
                      (if (eq (car copy) nilcar)
                          (setf (car copy) (list (car node))
                                copy (car copy))
                          (setf (cdr copy) (list (car node))
                                copy (cdr copy)))
                      (setf (car backrefs) copy))
                    (setf copy (list (car node))
                          root copy
                          backrefs (list copy))))
            (setf node (cdr node))))
       (incf counter)
     finally (return root)))
于 2012-11-29T14:06:57.280 回答