1

我需要一个函数来删除起始列表和所有子列表中第 n 个位置的元素。我不需要工作代码，我只需要任何建议。

4

3 回答 3

3

寻求建议而不是最终解决方案是值得称赞的。我会尽力向你解释。

单链表有助于从前端到后端进行递归处理。您可以通过廉价的操作来获取列表的第一个元素，其余元素，并通过将新元素放在前面来构建列表。一个简单的递归方案是：从列表中取出第一个元素，对其进行处理，然后将其放在与列表的其余部分重复整个过程的结果的前面。这种对连续元素和休止符的重复过程是递归部分。如果输入列表为空，则无事可做，返回空列表，结束处理。这是您的基本情况、锚点或任何您想称呼它的名称。记住：递归案例，基本案例，检查 - 你需要两者。

（由于 Lisp 的评估规则，要将已处理的元素实际放在已处理的其余元素之前，必须记住它，直到实际处理其余部分，因为构建列表的操作在返回新列表之前评估其两个参数。这些中间结果将被保留在堆栈上，这对于大列表可能是个问题。有一些方法可以避免这种情况，但我们会在这里保持简单。）

现在，您实际上不仅要求简单列表，还要求树。方便的是，该树表示为一个嵌套列表，因此通常上述方法仍然适用，除了有点复杂：您必须检查您要处理的元素本身是否是一个分支，即一个列表。如果是，那么整个过程也必须在该分支上完成。

基本上就是这样。现在，要从树中删除一个元素，您的操作只是检查您的元素是否匹配，如果是，则删除它。更详细地说：

  • 要从空列表中删除元素，只需返回一个空列表。

  • 如果第一个元素本身是一个列表，则返回一个从第一个元素构建的列表，其中所有匹配项被删除作为其第一个元素，其余所有匹配项被删除作为其剩余部分。

  • 如果它的第一个元素匹配，则返回列表的其余部分，并删除所有匹配的元素。（请注意，这里有些东西被“丢弃”了。）

  • 否则，返回一个从第一个元素构建的列表作为它的第一个元素，然后返回列表的其余部分，并删除所有匹配的元素作为它的其余部分。

看一下这个并尝试找到您的递归案例、基本案例以及遍历嵌套树结构的方法。如果您了解所有这些，则实施将很容易。如果你从来没有真正学会这一切，而且你的头脑现在还没有转动，那么认为你自己是一个天生的 Lisp 程序员。否则，递归只是一个基本概念，第一次可能很难掌握，但一旦点击，就像骑自行车一样。

埃德：不知何故错过了“位置”部分，并且误读了——尽管有问题的标题。这就是疲劳对人的影响。

无论如何，如果您想按位置删除树中的元素，您可以让您的函数采用可选的计数器参数（或者您可以使用提供它的包装函数）。如果您查看以上几点，递归新分支将是您重置计数器的地方。基本的递归方案保持不变，但不是比较元素本身，而是检查您的计数器——如果它与您要删除的位置匹配，则删除该元素。在每种递归情况下，您将递增的计数器传递给您的函数，除非在进入新分支时重置它，即为您的计数器参数传递 0。（您也可以在删除元素后只返回列表的其余部分，从而提高函数的性能，特别是对于要删除靠近开头的元素的长列表，但是让'

于 2013-03-12T02:53:18.313 回答
1

我的方法如下：

  1. 删除顶级列表中的第 n 个元素
  2. 从 #1 的结果中递归删除每个子列表中的第 n 个元素

我会这样实现它：

(defun (del n l)
  (defun (del-top-level n l)
    ...) ; return l but with nth gone
  (mapcar #'(lambda (l) (if (not (listp l)) l (del n l)))
          (del-top-level n l)))

您需要实现该del-top-level功能。

于 2013-03-12T02:48:54.323 回答
-1

好的，我想我知道您需要什么。

你应该需要两个功能

入口函数只会调用一个辅助函数，例如 (DeleteHelper position position myList)

DeleteHelper 将递归调用自身，如果当前位置不为 0，则可选择包含列表的当前元素。例如 (cons (car myList) (DeleteHelper (- position 1) originalPosition (cdr myList))

如果 DeleteHelper 遇到一个列表，则递归遍历该列表，并将位置重置为原始传入位置。如 (cons (DeleteHelper originalPosition originalPosition (car myList)) (DeleteHelper (- position 1) originalPosition (cdr myList)))

还要记住基本情况（我想一旦你遍历整个列表就会返回一个空列表）。

这应该让你朝着正确的方向前进。自从我写任何 Lisp 以来也已经有几年了，所以我的语法可能有点不对劲。

于 2013-03-11T23:36:07.213 回答