Next: 10.5 探索木表現のデータ変換
Up: 10 探索木
Previous: 10.3 親子関係を表す木表現の生成
ここでちょっと基本的なプログラム作りの復習です．
上のような２つの探索木表現のデータのサイズを比較するために，
コンスセルの数を数えるcell-countを定義してみましょう．
コンスセルはリストを構成する最小ユニットで，アトムでないデータです．
アトムとみなされるデータは以下のようにたくさんあります．
配列，構造体，文字列，文字，数，シンボルなどすべてアトムです．
<cl> (atom "abc")
T
<cl> (atom (make-array '(2 3)))
T
<cl> (atom #\a)
T
<cl> (defstruct test a b)
TEST
<cl> (atom (make-test :a 1 :b 2))
T
<cl> (atom 'abc)
T
<cl> (atom 10)
T
<cl> (atom 1.1)
T
<cl> (atom '(a))
NIL
<cl> (atom nil)
T
<cl> (atom '())
T
注意しなければならないのは，nilもアトムということです．
Lispでは，nilはアトムでもあり長さ０のリストでもあります．
コンスセルを数えるには，リストをたどってゆきアトムでない要素が
きたらば，それはコンスであるからそのコンスのcar部とcdr部の
セルを数えた数に１を加えるということで再帰的に定義可能です．
(defun cell-count (tree)
(cond
((atom tree) 0)
(t (+ 1
(cell-count (car tree))
(cell-count (cdr tree))))))
簡単な構造のリストに適用すると，
<cl> (cell-count '(a b c))
3
<cl> (cell-count nil)
0
<cl> (cell-count '(a))
1
<cl> (cell-count '((a)))
2
となります．グラフと探索木に対して適用してみます．
<cl> (cell-count (graph-tree *graph1* 's))
45
<cl> (cell-count (find-all-paths *graph1* 's))
60
<cl> (cell-count *graph1*)
26
<cl> (cell-count *graph2*)
31
となって，パスのリストで表現する*tree1*の方が*tree2*よりも冗長な分
よけいにセルが必要であることがわかります．
generated through LaTeX2HTML. M.Inaba 平成18年5月6日