0

我正在尝试实现一个在列表中相应位置插入数字元素的函数，但是括号有问题

(不 (= (1 3 5 6 7 9 16) (((1 3) 5) 6 7 9 16)))

我怀疑是因为反向以一种奇怪的方式执行，因为如果我执行

（我的扁平化'（（（1 3）5）6 7 9 16））

我得到了真正的答案：

(1 3 5 6 7 9 16)

这是我的代码：

(defn insert [x lst]
    (loop [prev () lst lst]
        (cond
        (empty? lst) (my-flatten (cons (reverse prev) (list x)))
        (> (first lst) x) (my-flatten (cons (cons (reverse prev) (list x)) lst))
        :else (recur (conj prev (first lst)) (rest lst)))))
4

1 回答 1

3

首先，您没有“括号问题”，而是列表有问题。

而不是先使用cons然后展平，你应该只使用concat. 然后，您也可以组合这两个基本案例。

在效率方面，您不应该在循环中将单个元素附加到单链表的末尾，因为这会导致二次运行时间。相反，完成后追加到前面并反转。

(if (or (empty? lst) (> (first lst) x))
    (concat (reverse prev) (list x) lst)
    (recur (cons (first lst) prev) (rest lst)))

读者练习：什么是前置条件和后置条件，什么是循环不变量？

于 2012-08-31T20:59:56.730 回答