刪除元素

Question

我有形式的列表：

((1 (3 2 4)) (2 (3 1)) (3 (2 1)) (4 (1))) 

該列表表示的形式（「節點」（「邊緣」））的曲線圖。我該如何編寫一個採用表示節點值的過程，例如「1」，並從圖中刪除該節點。例如：使用輸入5和'（（1（3 2））（2（3 1））（3（2 1））（4（5））（5（4））的（刪除節點ng）應該輸出：

((1 (3 2)) (2 (3 1)) (3 (2 1)) (4())) 

從上面的例子可以看出，節點和添加到該節點的任何邊都必須被刪除。我的代碼迄今如下：

(define graph '((1 (3 2)) (2 (3 1)) (3 (2 1)) (4 (5)) (5 (4)))) 

;...Other procedures not shown... 

(define (delete-node n g) 
    (define (delete ls item) 
     (cond ((null? ls) nil) 
      ((pair? (car ls)) 
      (cons (delete (car ls) item) (delete (cdr ls) item))) 
      ((equal? (car ls) item) (delete (cdr ls) item)) 
      (else (cons (car ls) (delete (cdr ls) item))))) 
     (delete (filter (lambda (x) (not (eq? (car x) n))) g) n)) 

(delete-node 5 graph) 

上面的代碼工作，但有沒有這樣做的更有效的方法？

Answer 1

使用高級別功能的可能的定義是：用一個遞歸函數

(define (delete-node n g) 
    (map (lambda(x) (list (car x) (filter (lambda(x) (not (= x n))) (cadr x)))) 
     (filter (lambda(x) (not (= (car x) n))) g))) 

(delete-node 5 '((1 (3 2)) (2 (3 1)) (3 (2 1)) (4 (5)) (5 (4)))) 
     ; produces ((1 (3 2)) (2 (3 1)) (3 (2 1)) (4())) 

稍微更有效的解決方案是替代以下：

(define (delete-node n g) 
    (cond ((null? g) '()) 
     ((= (caar g) n) (delete-node n (cdr g))) 
     (else (cons (list (caar g) (filter (lambda(x) (not (= x n))) (cadar g))) 
        (delete-node n (cdr g)))))) 

如果圖形是大和你知道它的結構是正確的， 知道一個節點只有一個輸出弧等於n，更有效的版本可能如下：

(define (delete-node n g) 
    (define (delete-edge edges) 
    (cond ((null? edges) '()) 
      ((= (car edges) n) (cdr edges)) ; stop recursion when the edge is found 
      (else (delete-edge (cdr edges))))) 
    (cond ((null? g) '()) 
     ((= (caar g) n) (delete-node n (cdr g))) 
     (else (if (member n (cadar g) =) 
        (cons (list (caar g) (delete-edge (cadar g))) 
         (delete-node n (cdr g))) 
        (cons (car g) (delete-node n (cdr g))))))) 

請注意，測試(member n (cadar g) =)是爲了避免在n不存在時複製邊緣列表。

Answer 2

不確定我是否正確理解您的問題 - 這是否符合您的需求？

(define (delete-node node graph) 
    (define node-1 (car node)) 
    (define node-2 (cdr node)) 
    (let iter ((graph graph) (result '())) 
    (if (null? graph) 
     (reverse result) 
     (let* ((head (car graph)) (head-1 (car head)) (head-2 (cadr head))) 
      (iter (cdr graph) 
       (cons (cond 
         ((eqv? head-1 node-1) (list head-1 (remove node-2 head-2))) 
         ((eqv? head-1 node-2) (list head-1 (remove node-1 head-2))) 
         (else   head)) 
         result)))))) 

測試：

> (delete-node '(2 . 3) '((1 (3 2 4)) (2 (3 1)) (3 (2 1)) (4 (1)))) 
'((1 (3 2 4)) (2 (1)) (3 (1)) (4 (1))) 
> (delete-node '(1 . 2) '((1 (3 2 4)) (2 (3 1)) (3 (2 1)) (4 (1)))) 
'((1 (3 4)) (2 (3)) (3 (2 1)) (4 (1)))