基礎的なデータ構造
・ スタックとキュー
・ リスト
・ バケツとハッシュ
データを記憶する
・ コンピュータの基礎的な操作の1つは、データ(情報)を記
憶すること
・ しかし、どのように記憶するかで、利用効率が変わる
 記憶させる手間、検索する手間...
-来たデータを本に1ページ目から順に書き込んでいく
-棚を作って整理する
・ 使用用途によって、記憶の仕方(データの構造)を工夫す
る必要がある
データを記憶する記憶の仕方を、データ構造という
コンピュータの記憶の仕方
・ コンピュータの記憶領域は、メモリ。メモリ1単位に値が1
つ入る
-来たデータを本に1ページ目から順に書き込んでいく
 メモリを配列で確保して、来たデータを、添え字の小さ
いところから順に書き込んでいく。スタック、キューなど
-棚を作って整理する
 リスト、ヒープ、2分木、バケツ、ハッシュなど
どのようなデータ構造があるのか、順に見ていこう
配列による記憶
・ 問題です。配列にデータを記憶させたいとします。さて、ここ
に、データ(数字だと思っていいでしょう)が1つずつやってき
ます。さて、どうやって記憶しますか?
 最後に記録したところの次に書き足せばいいんじゃない?
 その通り!
・ ただし、メモリには「書き込まれていない」という状態がないの
で、どこが最後かわからない
・ たとえあっても、メモリ全体を見渡せるわけではないので、
「書き込まれたところの最後」を見つけるのは大変
・ なので、「書き込んだ最後の場所」を記憶する変数を使う
スタック
・ 例を見てみましょう
配列
カウンタ
値 値
1
0
2
・ このように、「配列」と「最後に書いた場所のカウンタ」からな
るデータの構造を スタック という
(カウンタのことを、スタックポインタ といいます)
値の消去
・ 今度は、値を記憶するだけでなく、読み出し、および、読み出
したものを消去する方法も考えましょう
- どれでもいいから1個読み出して消したい
 最後に記録したところを読み出して、カウンタを1減らす
- ●番目の値を消したい
 ●番目に最後の値を移して、カウンタを1減らす
- ▲という値を持つものを消したい
 スキャンして見つけないといけない...
配列
値 値
値 値 値
カウンタ 5
スタックの関数
・ スタックを実現するには、以下のような関数を作ればよい
・ 使うときは、スタックと記憶する値をセットで渡して呼び出す
int STACK_push ( STACK *S, int a){
if ( S->t == S->max ) return (1); // overflow error typedef struct {
S->h[S->t] = a;
int *h; // array for data
S->t ++;
int end; // size of array
return (0);
int t; // counter
}
} STACK
int STACK_pop ( STACK *S, int *a){
if ( S->t == 0 ) return (1); // underflow error
S->t --;
*a = S->h[S->t];
return (0);
}
h[] 値 値 値 値 値
t
end
スタックの利用例
・ 文字列を読み込んで、逆向きにする
ABCDEFGH
・ ワープロの undo 機能
end
h[]
~余談~:あふれないスタック?
・ スタックは、値をたくさん書き込むと、配列からあふれてしまう。
そりゃそうだ。
・ しかし、あらかじめ書き込みの上限がわからないこともある。
(例えば、数字がたくさんあるファイルを読んで、スタックにため
る、といった場合。最初にスキャンすればわかるけど…)
・ あふれたら、新しく大きな配列を取り直して、内容をコピーする、
というようにすれば、あふれても対処できる
・ しかし、サイズを1つずつ大きくしたのでは、毎回あふれてコピ
ーすることになり、無駄が多い
~余談~:あふれないスタック? (2)
・ 配列を取り直す際には、例えば、現在のサイズの2倍の大きさ
の配列を取り直すようにする
 一度あふれたあとは、同時に使われているメモリの大きさ
は、常に記憶している要素の数の3倍で抑えられる
・ コピーにかかる手間の総量も、現在の配列の大きさの2倍で
抑えられる
 計算量の意味で、損失はない
~余談~:あふれないスタック? (3)
・ コードを書くと、このようになる
void STACK_push ( STACK *S, int a){
if ( S->t == S->max ){ // overflow error
int i, *h = malloc (sizeof(int)*max*2 ); // using realloc is easy
for ( i=0 ; i<S->t ; i++ ) h[i] = S->h[i];
free ( S->h );
S->h = h;
}
S->h[S->t] = a;
S->t ++;
}
FILO
・ どれでもいいから1個読み出して消したい
 例えば、ユーザーが指定した点に★マークを書いて、消し
ゴムボタンを押したときに全部消す、というようなときに使う
(場所を記憶する)
- 最後に書き込んだものが、最初に読み出されることになる
- このような、データの読み出され方を FILO(First In Last
Out)という
カウンタ
配列
値 値
値 値 値
5
キュー、FIFO
・ 読み出し&消去をするときに、「最初に書き込んだものが最
初に出てくる」ようにしたい
(FIFO、 First In First Out という)
 例えば、ユーザーが指定した点に★マークを書いて、消し
ゴムボタンを押したときに、最初のほうから消していく、とい
うようなときに使う(場所を記憶する)
 窓口サービスなどは、皆このタイプ
・ このようなデータ構造をキューという
- 最後に書き込んだものが、最後に読み出されることになる
カウンタ 5
配列
値 値
値 値 値
キューのカウンタ
・ キューを実現するには、「どこが最初に書き込まれたか」を覚
えておく必要がある
 つまり、書き込む場所と、読み込む場所を覚えておくため、
2つカウンタが必要
 読み出す場所を、先頭という意味で head、
書き込む場所を、最後と言う意味で tail とよぶ
head
tail
配列
値 値 値
値 値
2
7
あふれたら
・ スタックは、配列の大きさ以上の書き込みをするとあふれる
・ キューは、記憶している数が、配列の大きさ以上でなくてもあ
ふれる
 あふれたときは、tail を配列の先頭に戻す
 head も、最後まで来たら先頭に戻す
・ 本当にあふれるのは、taill が head を追い越すとき
head
tail
配列
値 値
値 値
値
5
10
0
追い抜きの調整
・ tail が head を追い抜くときは、実は調整が必要
・ 配列の数と同じだけ書き込むと、 tail は head においつく
つまり、両者は等しくなる
 これは、何も書き込んでいないときと同じ
 両者を区別できない!
・ 解決策は
- 両者を区別するためのフラグを用意する
- (配列の大きさ-1)までしか書き込まない
head
tail
配列
値
値 値
値
値 値 値
値 値
値
5
5
キューの関数
・ スタックを実現するには、以下のような関数を作ればよい
・ 使うときは、スタックと記憶する値をセットで渡して呼び出す
int QUEUE_ins ( QUEUE *Q, int a){
if (( Q->t +1 ) % Q->end == Q->s ) return (1); // overflow error
Q->h[Q->t] = a;
typedef struct {
Q->t = ( Q->t +1 ) % Q->end;
int *h; // array for data
return (0);
int end; // size of array
}
int s; // counter for head
int t; // counter for tail
int QUEUE_ext ( QUEUE *S, int *a){
} QUEUE
if ( Q->s == Q->t ) return (1); // underflow error
*a = Q->h[Q->s];
Q->s = ( Q->s +1 ) % Q->end;
return (0);
t
s
end
}
h[]
値 値 値
キューの利用例
・ 1つずつ数を入力し、ときどき5個ずつ書き出す
・ マウスカーソルの軌跡を描画する
(マウスの座標を連続的にキューに蓄え、1秒間に30コマとか、
ある程度時間が経過したものから消す)
end
h[]
リスト: 順番を守って挿入削除
・ 配列は簡単で便利だが、「順番を維持して挿入/削除」をす
るときに弱みが出る
・ 他の操作の便利さを犠牲にしてもいいから、この点を何とか
できないだろうか???
 ランダムアクセス性(k番目の要素へのアクセスが一手で
できる)を犠牲にしてもよいとする
- 窓口サービスで、割り込みを許す、あるいは途中のキャン
セルを許す場合
- 文章の編集(段落単位とか)をする場合。途中に絵を挿入
するたびに、全部移動させたくない
アイディア:鎖と同じ構造を
・ 鎖は挿入削除が簡単。でも、k 番目を見つけるのは面倒
 この構造をまねよう
・ 鎖の構造は、隣との隣接関係が確保されていて、場所は自
由。場所が自由なのはともかくとして、隣接関係を記録する
ことにしよう
1
5
7
3
・ 記憶する場所それぞれ(セルとよぶ)に、お隣さん(両隣)の
情報を記録。つまり、各セルは3つの値からなる
- 記憶するもの
- 前のセル(場所か名前、つまりポインタか添え字)
- 後ろのセル(場所か名前、つまりポインタか添え字)
挿入削除の戦略
・ 鎖をつけかえるときは何をするか?
 入れるところ、抜くものの周り、の隣接構造を切る
 要素に対して、「隣は何か」を変える
・ 要素をある場所に挿入するときは、挿入する場所の前後の
要素の隣接関係を切り、それを入れる
・ 要素を削除するときは、その要素の前後の要素を直結する
・ 両方とも順番を保ったまま、定数手でできる
1
5
7
3
ポインタを利用した構造体
・ このような構造体を定義して、新しく記憶するものが来るたび
に、新しくメモリを確保するようにする
 配列の大きさのような、上限の制約がなくなる
注意: Cで書くときは、LISTの定義
にLISTを使うので、下記のように
する必要あり
・ リストの最初のセル(head という)
と最後のセル(tailという)を覚えて
おく必要がある
(LISTで覚えてもいい)
typedef struct {
LIST *prv; // pointer
LIST *nxt; // pointer
int h; // value
} LIST
typedef struct _LIST_ {
struct _LIST_ *prv; // pointer
struct _LIST_ *nxt; // pointer
int h; // value
} LIST
コード(初期化)
・ 初期化では、LIST 構造を1つ用意して、前と次を自分にして、
空のリストを表現
●
int LIST_init ( LIST *L ){
L->prv = L;
L->nxt = L;
}
・ セルを挿入すると、●の次と前がそれぞれリストの head と
tail になる
●
1
5
7
3
挿入
・ 挿入は、入れる前のセル(あるいは後ろのセル)を指定して
行う。前と後ろのポインタを付け替える
int LIST_ins ( LIST *l, LIST *p ){
p->nxt->prv = l;
l->nxt = p->nxt;
p->nxt = l;
l->prv = p;
}
●
1
5
7
3
・ つぎ変えの順番を変えると、正常につぎかえられなくなる
削除
・ 削除は、入れる前のセル(あるいは後ろのセル)を指定して
行う。前と後ろのポインタを付け替える
int LIST_del ( LIST *l ){
l->nxt->prv = l->prv;
l->prv->nxt = l->nxt;
}
●
1
5
7
3
・ l のポインタはいじらなくて良い
(消したときの情報が残っているので、復帰するときに使える)
普通の教科書では
・ 一般に、教科書では、リストの両端は NULL のポインタを指
すことにする
 次/前を指すポインタが NULL なら、そこは端である、と
判定する
リスト
1
5
7
3
・ 理論的にきれいだが、プログラミングのときは厄介
 隣がNULLのとき、例外処理をしなければいけない
 NULLの前に挿入、ということはできないので、挿入を2通
り(○○の前に入れる、○○の後に入れる、を用意して、入
れる場所によって使い分けなければいけない
リストをたどるループ
・ リストをたどりたいときは、●から始めて、後ろへ1つずつポ
インタをたどり、●まで戻ったら終了する
LIST *p;
int e;
for ( p=●->nxt ; p!=● ; p=p->nxt ){
e = p->h;
…
}
・ 逆向きのときは prv を使用
●
1
5
7
3
復元
・ 直前に除去したセルを復元するには、前と後ろのポインタが
指すセルの間に、自分を挿入すればよい
●
int LIST_recov ( LIST *l ){
LIST_ins ( l, l->prv);
}
1
5
7
・ 消した順番の逆順に復元
するのであれば、いくつものセルを復元することができる
(消したものは、片方向リストにすればよい)
1
5
7
3
3
リストの利用例
・ 1 から n の数字をランダムなセルの次に順番に挿入して、ラ
ンダムな列を作る (同じ数字が2度出てこないので、乱数列
とは違う)
・ 時系列にそって、現れたり消えたりするデータを保持する
(ある値を持つセルがうまく見つけられるように工夫がいる)
リストの利用例2
・ 値を2つもつデータが n 個ある。 (x1,y1) ,…, (xn,yn) とする
・ y が大きいものから k/n だけデータを集めたときの、
x の値が k‘/m 番目である要素が、各 k,k’ について知りたい
・ 普通にやると O( n2 log n) 時間
・ リストを使ってうまくやると
O( n( m+log n)) 時間
リストの利用例2 (2)
・ データを x 個でソートして、リストにする
・ 0/m 番目から m/m 番目を見つける
・ 次に y でソートした列も作り、 y が小さい順にリストから抜い
ていく
・ 0/m 番目から m/m 番目を更新する。必要に応じて、左右に
1つ動かせばよい
・ 感覚的には、O( n2 log n)  O( n( m+log n)) 時間
で n 倍速くなる感じ
片方向リスト
・ 削除がなければ、リストは後ろへのポインタを覚えるだけで
できる
●
1
5
7
・ 例えば、スライドの作成?
・ k個のソートされた数列の合併
3
配列を利用したリスト
・ ポインタを使うとわかりづらい、あるいは、1つずつセルの管
理をするのが面倒な場合、配列を使ったリストが使える
利点 添え字がポインタの代わりになるので、
各セルに変数を割当てたい、というよう
なときに面倒がない
欠点 配列なので、大きさを変えるのが面倒
・ 実用では、意外と、
大きさを変えないですむことが多い
・ リスト全体の構造体を
作ることになる
typedef struct {
int *prv; // index to previous
int *nxt; // index to next
int *h; // value
} ALIST
配列リストの例
・ h, prv, nxt の各配列の i 番目の要素が、セル i のh, nxt, prv
・ 0番目なり、最後なりを特別なセルにして、リストをたどるときは
必ずそこからたどるようにする
(そうでないと、どれが「生きているところ」かわからない)
・最初の空リストは、最後のセルの前後を最後のセルにして表現
0 1 2 3 4 (●)
h 値 値 値 値
prv 4
0
3
1
2
nxt 1
3
4
2
0
typedef struct {
int *prv; // index to previous
int *nxt; // index to next
int *h; // value
} ALIST
バケツ
・ キューにしてもリストにしても、順番どおりに記憶することはでき
るが、参照がしづらい
 記憶した数字の中で、1桁のものを全部出してください
・ 少し構造を持たせて、検索が楽になるようにしたい
・ まず、値による分類から始めよう
バケツのアイディア
・ 数字を記憶する際に、それぞれの値ごとに分類して記憶するこ
とにする
・ 例えば、0から 99 までの値を持つ数字がいくつも入力され、そ
れを10の位の値で分類する
・ 10の位、0 から 9に対して、1つずつリストなり配列なりを持たせ
ればよい
0 1 2 3 4 5 6 7 8 9
バケツの利用例
・ 例えば、10の位で数値をソートするときに使える
・ 例えば、疎な行列の転置をするときに使える
A: 1,9,5
B: 1,2
C: 1,6,7
D: 4,5
1 2 3 4 5 6 7 8 9
応用:Radix(基数) ソート
・ バケツの、桁ごとのソートを繰り返すと、数値のソートができ
る
・ 各数値の下の位から順番にバケツソートをしていく。バケツ
内の順番は変えないこと
・ バケツが2ついる。ただし、1つにすることもできる。その際は、
バケツを一回スキャンして全部をつなげる必要がある。
1 2 3 4 5 6 7 8 9
ハッシュ
・ バケツの分類精度を上げようとすると、バケツの数を増やさなく
てはいけない
 大きなメモリが必要。ソートするときのように、全てのバケツ
をスキャンする、という操作にも時間がかかる
・ 正確に分類できなくてもいいから、分類そこそこ、メモリもそこそ
こ、検索もそこそこ、という間を取れないだろうか?
ハッシュのアイディア
・ 例えば文字列をしまうデータ構造を考える。
・ 「この文字列Sはデータの中にありますか?」という質問に高速で
答えるためにはバケツは便利だが、非常に多くのバケツが必要
・ しかし、文字列の数自体は少ないだろう
・ そこで、例えば、頭2文字だけでバケツを作ったらどうだろう?
 3文字目以降が異なっても、頭2文字が同じなら同じバケツに入
る。バケツを共有してメモリを節約している
 そのため、バケツが空なら、S はない、と簡単に答えられるが、
バケツが空でないときは、バケツの中身を全部調べて、S がある
かないかチェックしなければならない
文字列のバケツ
・ 「バケツは数値しか入らないんじゃない?」
・ その通りなので、文字列は他の場所にしまい、バケツにはそのイ
ンデックスを入れる
1: ABCABC
2: ABBBBB
3: CCCBBB
・ 「頭2文字」は数値に変換する。例えばABCからなる文字列の場
合は、A=0,B=1,C=2 と思って、3進数2桁の数と解釈
AB  1 、CC  8 となる
0 1 2 3 4 5 6 7 8
データの偏り
・ 文字列をしまう場合、文字列の頭2文字がある程度均質であれ
ばいいが、偏っていたらどうしよう?
 あるバケツにデータ集中して、のこりは空ばかり、となる
・ ならば、頭2文字でなく、文字列から整数への、均一な写像関数
を持ってきたらどうだろうか?
(これをハッシュ関数、データに対する写像の値をハッシュキー、
ハッシュ値とよぶ)
 実用を考えれば、似たものが異なる値を持つほうがいい
・ 例えば、x1,x2,x3 ,… に対して、 (x1)1+(x2)2+(x3)3 や、
((x1+1)x2+1)x3… などの、バケツの大きさ(ハッシュの大きさ)の
剰余をとったものを使う
ハッシュの大きさ
・ さて、ハッシュ関数のおかげで偏りなくデータをしまえそうだが、
ハッシュの大きさはどうしたらいいのだろうか?
 基本的に、バケツにデータがたくさん入っていると検索に時間
がかかるので、なるべく異なるデータが同じところに入らないよ
うにしたほうがいい
 もともと、データをとっておくところは必要なので、それと同じ
位はメモリを使ってもいいんじゃないか?
・ ならば、例えば、データの数の定数倍にする。計算量の意味で
も損失なし
・ データが増えてきたら、スタックと同じように、サイズを2倍に変更
して作り直せばよい
まとめ
・ スタックとキュー: 配列とカウンタをセットにして、逐次的にくる
データに対応
・ リスト: 隣接構造を記憶することで、順番を保ちながらの挿入
削除を効率化
・ バケツ: 値による分類で検索を容易に
・ ハッシュ: ハッシュキーを使ったバケツで、分類精度とメモリ効
率の良さを両立させる
ダウンロード

基礎的なデータ構造