データ構造

リスト

リストに添字でアクセスするのは、なんかイヤな気分になるんだけど、まあしょうがない。

(define (create-list) '(list))

(define (insert! target index val)
  (if (> index 1)
      (insert! (cdr target) (- index 1) val)
      (let ((new (cons val (cdr target))))
	(set-cdr! target new))))

(define (delete! target index)
  (if (> index 1)
      (delete! (cdr target) (- index 1))
      (set-cdr! target (cddr target))))

(define (access target index)
  (if (> index 1)
      (access (cdr target) (- index 1))
      (cadr target)))

(define (member target val)
  (let ((next (cdr target)))
    (cond ((null? next) #f)
	  ((eq? (car next) val) #t)
	  (else (member next val)))))

スタック

教科書は配列で実装してあったけれど、Lispなのでリストで実装してみた。

(define (create-stack)
  '(stack))

(define (push! stack val)
  (let ((new-stack (cons val (cdr stack))))
    (set-cdr! stack new-stack)))

(define (pop! stack)
  (let ((top (top stack)))
    (set-cdr! stack (cddr stack))
    top))

(define (empty? stack)
  (null? (cdr stack)))

(define (top stack)
  (cadr stack))