刪除列表中包含列表的元素

這裏是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)))) 
) 
)

來源

2012-11-28 ssBarBee

還好，問題是什麼？ –

@RainerJoswig我想知道如何解決我發佈的問題。 – ssBarBee

當然，但是你的代碼在做什麼或者不在做什麼？ –

你爲什麼在z位置拼寫Pos和CurrPos？

而你的代碼中的問題在於cond的最後一個分支。當你在List的cdr上進行遞歸時，CurrPos需要按照（汽車列表）中的元素數來提前。而一個簡單的（長度列表）將不起作用，因爲它需要對子列表中的元素進行遞歸計數。

編輯：更多的闡述說我們稱之爲

(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))))

因爲（汽車列表）中有2個元素。

所以，你只需要改變

(deleteElementAcc Pos CurrPos (cdr List))

到

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

和程序遞歸長度，這是一個非常簡單的功能。它應該計入子列表中的元素，例如（遞歸長度爲（（1 2）（（3））））返回3.

來源

2012-11-29 04:31:54 imMAW

感謝您的回覆。我已經修復了z和s。你能否寫下一段代碼來幫助我跟蹤真實的CurrPos？ – ssBarBee

我編輯了這篇文章，讓我知道如果這沒有幫助。 – imMAW

非常感謝。我知道問題是什麼，但從來沒有想過調用另一個函數來解決這個問題。 :)乾杯 – ssBarBee

雖然解決這個問題只需要任何方式並不是特別困難，解決這個問題確實不是一件容易的事情。我的意思是既有大的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-29 14:06:57

刪除列表中包含列表的元素

回答

相關問題