データ構造
リスト
リストに添字でアクセスするのは、なんかイヤな気分になるんだけど、まあしょうがない。
(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))