リストについては第 8 章の最初の節で簡単にふれた. リストというのは, 見かけは, 要素としてなにをいれてもいい 配列(ベクトル)のことである. たとえば, [3,2,"cat"] は, 数字 3 を 1 番目の要素, 数字 2 を 2 番目の要素, 文字列 "cat" を 3 番目の要素として持つリストである. リストの要素はまたリストでもよいので,
リスト L の先頭要素を取り出すには L[0] を用いてもよいが, 関数 car(L) を用いることも可能である. また, リスト L から先頭要素を除いたリストは, 関数 cdr(L) で求めることが可能である. たとえば,
[429] L=[3,[3,2,"dog"],"cat"]; [3,[3,2,dog],cat] [430] car(L); 3 [431] cdr(L); [[3,2,dog],cat]
となる. car(カァと読んでいい) と cdr (クッダーと読んでいい) は LISP 由来の関数名である.
リスト L の長さを戻す関数は length(L) である. 関数 append(L,M) は二つのリスト L と M をつないだリストを 戻す. たとえば,
[432] L=[3,[3,2,"dog"],"cat"]; [3,[3,2,dog],cat] [433] append(L,M); [3,[3,2,dog],cat,3,[2,5],6]
となる.
リストの使い道は多岐にわたるが, 結果の大きさがあらかじめ予想できないときに 結果をかたつけておく ``袋'' として利用するのは, 一番初歩的な利用法の一つである.
例を一つあげよう. たとえば次のプログラムは, 第 7 章の 試し割りによる素因数分解法のプログラムで, N の素因子をリストにして戻す. リスト L がすでに求まった素因子を格納しておく ``袋'' になっている. 新しい素因子を得たら, 関数 append を用いて, L にその因子を加える.
プログラム
def prime_factorization(N) { K = 2; L = [ ]; while (N>=2) { if (N % K == 0) { N = idiv(N,K); L = append(L,[K]); }else{ K = K+1; } } return(L); }
|
実行例
[430] prime_factorization(98); [2,7,7] |
リストをベクトルに, ベクトルをリストに変換する関数は
それぞれ,
newvect, vtol である.
リストとベクトルの違いは何であろうか?
リスト L に対しては
L[1] = 3 といった代入ができないのが表面的な
違いであるくらいでほとんど同じものに見える.
しかし,
リストとベクトルではその内部でのデータ表現法が全く
異っている.
ベクトルはメモリのなかでひとつづきの領域が確保され
そのなかにデータはインデックス順に格納されると理解しておいてよい.
リストはもっと複雑な構造である.
データ領域とアドレス領域なる二つの領域を持っている
データ構造をセルと呼ぶことにする.
リストは, セルの集まりである.
たとえば [1,2] というリストは, 次のような二つのセルの集まり
である.
リストの内部構造を きちんと理解するには C 言語の構造体と構造体へのポインタまたは, 機械語の間接アドレッシングの仕組みを理解する必要がある. セルを C 言語の構造体で書くと次のようになる.
struct cell { void *data; struct cell *next_address; };
上のプログラムでは L=append(L,[K]); を用いて, リストにどんどん要素を付け足していった. 実はこの方法は巨大なリストを扱うときにはよくない. メモリの無駄使いが生じる.