Document

基礎的なデータ構造
・スタックとキュー
・リスト
・バケツとハッシュ
データを記憶する
・コンピュータの基礎的な操作の１つは、データ（情報）を記
憶すること
・しかし、どのように記憶するかで、利用効率が変わる
 記憶させる手間、検索する手間．．．
－来たデータを本に1ページ目から順に書き込んでいく
－棚を作って整理する
・使用用途によって、記憶の仕方（データの構造）を工夫す
る必要がある
データを記憶する記憶の仕方を、データ構造という
コンピュータの記憶の仕方
・コンピュータの記憶領域は、メモリ。メモリ1単位に値が１
つ入る
－来たデータを本に1ページ目から順に書き込んでいく
 メモリを配列で確保して、来たデータを、添え字の小さ
いところから順に書き込んでいく。スタック、キューなど
－棚を作って整理する
 リスト、ヒープ、2分木、バケツ、ハッシュなど
どのようなデータ構造があるのか、順に見ていこう
配列による記憶
・問題です。配列にデータを記憶させたいとします。さて、ここ
に、データ（数字だと思っていいでしょう）が１つずつやってき
ます。さて、どうやって記憶しますか？
 最後に記録したところの次に書き足せばいいんじゃない？
 その通り！
・ただし、メモリには「書き込まれていない」という状態がないの
で、どこが最後かわからない
・たとえあっても、メモリ全体を見渡せるわけではないので、
「書き込まれたところの最後」を見つけるのは大変
・なので、「書き込んだ最後の場所」を記憶する変数を使う
スタック
・例を見てみましょう
配列
カウンタ
値値
１
０
２
・このように、「配列」と「最後に書いた場所のカウンタ」からな
るデータの構造をスタックという
（カウンタのことを、スタックポインタといいます）
値の消去
・今度は、値を記憶するだけでなく、読み出し、および、読み出
したものを消去する方法も考えましょう
－どれでもいいから１個読み出して消したい
 最後に記録したところを読み出して、カウンタを１減らす
－ ●番目の値を消したい
 ●番目に最後の値を移して、カウンタを１減らす
－ ▲という値を持つものを消したい
 スキャンして見つけないといけない．．．
配列
値値
値値値
カウンタ５
スタックの関数
・スタックを実現するには、以下のような関数を作ればよい
・使うときは、スタックと記憶する値をセットで渡して呼び出す
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[]
～余談～：あふれないスタック？
・スタックは、値をたくさん書き込むと、配列からあふれてしまう。
そりゃそうだ。
・しかし、あらかじめ書き込みの上限がわからないこともある。
（例えば、数字がたくさんあるファイルを読んで、スタックにため
る、といった場合。最初にスキャンすればわかるけど…）
・あふれたら、新しく大きな配列を取り直して、内容をコピーする、
というようにすれば、あふれても対処できる
・しかし、サイズを１つずつ大きくしたのでは、毎回あふれてコピ
ーすることになり、無駄が多い
～余談～：あふれないスタック？ (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
・どれでもいいから１個読み出して消したい
 例えば、ユーザーが指定した点に★マークを書いて、消し
ゴムボタンを押したときに全部消す、というようなときに使う
（場所を記憶する）
－最後に書き込んだものが、最初に読み出されることになる
－このような、データの読み出され方を FILO（First In Last
Out）という
カウンタ
配列
値値
値値値
５
キュー、FIFO
・読み出し＆消去をするときに、「最初に書き込んだものが最
初に出てくる」ようにしたい
(FIFO、 First In First Out という)
 例えば、ユーザーが指定した点に★マークを書いて、消し
ゴムボタンを押したときに、最初のほうから消していく、とい
うようなときに使う（場所を記憶する）
 窓口サービスなどは、皆このタイプ
・このようなデータ構造をキューという
－最後に書き込んだものが、最後に読み出されることになる
カウンタ５
配列
値値
値値値
キューのカウンタ
・キューを実現するには、「どこが最初に書き込まれたか」を覚
えておく必要がある
 つまり、書き込む場所と、読み込む場所を覚えておくため、
２つカウンタが必要
 読み出す場所を、先頭という意味で head、
書き込む場所を、最後と言う意味で tail とよぶ
head
tail
配列
値値値
値値
２
７
あふれたら
・スタックは、配列の大きさ以上の書き込みをするとあふれる
・キューは、記憶している数が、配列の大きさ以上でなくてもあ
ふれる
 あふれたときは、tail を配列の先頭に戻す
 head も、最後まで来たら先頭に戻す
・本当にあふれるのは、taill が head を追い越すとき
head
tail
配列
値値
値値
値
５
１０
０
追い抜きの調整
・ tail が head を追い抜くときは、実は調整が必要
・配列の数と同じだけ書き込むと、 tail は head においつく
つまり、両者は等しくなる
 これは、何も書き込んでいないときと同じ
 両者を区別できない！
・解決策は
－両者を区別するためのフラグを用意する
－（配列の大きさ－１）までしか書き込まない
head
tail
配列
値
値値
値
値値値
値値
値
５
５
キューの関数
・スタックを実現するには、以下のような関数を作ればよい
・使うときは、スタックと記憶する値をセットで渡して呼び出す
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[]
値値値
キューの利用例
・１つずつ数を入力し、ときどき5個ずつ書き出す
・マウスカーソルの軌跡を描画する
（マウスの座標を連続的にキューに蓄え、1秒間に30コマとか、
ある程度時間が経過したものから消す）
end
h[]
リスト：順番を守って挿入削除
・配列は簡単で便利だが、「順番を維持して挿入／削除」をす
るときに弱みが出る
・他の操作の便利さを犠牲にしてもいいから、この点を何とか
できないだろうか？？？
 ランダムアクセス性（k番目の要素へのアクセスが一手で
できる）を犠牲にしてもよいとする
－窓口サービスで、割り込みを許す、あるいは途中のキャン
セルを許す場合
－文章の編集（段落単位とか）をする場合。途中に絵を挿入
するたびに、全部移動させたくない
アイディア：鎖と同じ構造を
・鎖は挿入削除が簡単。でも、k 番目を見つけるのは面倒
 この構造をまねよう
・鎖の構造は、隣との隣接関係が確保されていて、場所は自
由。場所が自由なのはともかくとして、隣接関係を記録する
ことにしよう
1
5
7
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 構造を１つ用意して、前と次を自分にして、
空のリストを表現
●
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通
り（○○の前に入れる、○○の後に入れる、を用意して、入
れる場所によって使い分けなければいけない
リストをたどるループ
・リストをたどりたいときは、●から始めて、後ろへ１つずつポ
インタをたどり、●まで戻ったら終了する
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度出てこないので、乱数列
とは違う）
・時系列にそって、現れたり消えたりするデータを保持する
（ある値を持つセルがうまく見つけられるように工夫がいる）
リストの利用例２
・値を２つもつデータが n 個ある。 (x1,y1) ,…, (xn,yn) とする
・ y が大きいものから k/n だけデータを集めたときの、
x の値が k‘/m 番目である要素が、各 k,k’ について知りたい
・普通にやると O( n2 log n) 時間
・リストを使ってうまくやると
O( n( m+log n)) 時間
リストの利用例２ (2)
・データを x 個でソートして、リストにする
・ 0/m 番目から m/m 番目を見つける
・次に y でソートした列も作り、 y が小さい順にリストから抜い
ていく
・ 0/m 番目から m/m 番目を更新する。必要に応じて、左右に
１つ動かせばよい
・感覚的には、O( n2 log n)  O( n( m+log n)) 時間
で n 倍速くなる感じ
片方向リスト
・削除がなければ、リストは後ろへのポインタを覚えるだけで
できる
●
1
5
7
・例えば、スライドの作成？
・ k個のソートされた数列の合併
3
配列を利用したリスト
・ポインタを使うとわかりづらい、あるいは、１つずつセルの管
理をするのが面倒な場合、配列を使ったリストが使える
利点添え字がポインタの代わりになるので、
各セルに変数を割当てたい、というよう
なときに面倒がない
欠点配列なので、大きさを変えるのが面倒
・実用では、意外と、
大きさを変えないですむことが多い
・リスト全体の構造体を
作ることになる
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に対して、１つずつリストなり配列なりを持たせ
ればよい
０１２３４５６７８９
バケツの利用例
・例えば、10の位で数値をソートするときに使える
・例えば、疎な行列の転置をするときに使える
A: 1,9,5
B: 1,2
C: 1,6,7
D: 4,5
１２３４５６７８９
応用：Radix(基数) ソート
・バケツの、桁ごとのソートを繰り返すと、数値のソートができ
る
・各数値の下の位から順番にバケツソートをしていく。バケツ
内の順番は変えないこと
・バケツが２ついる。ただし、１つにすることもできる。その際は、
バケツを一回スキャンして全部をつなげる必要がある。
１２３４５６７８９
ハッシュ
・バケツの分類精度を上げようとすると、バケツの数を増やさなく
てはいけない
 大きなメモリが必要。ソートするときのように、全てのバケツ
をスキャンする、という操作にも時間がかかる
・正確に分類できなくてもいいから、分類そこそこ、メモリもそこそ
こ、検索もそこそこ、という間を取れないだろうか？
ハッシュのアイディア
・例えば文字列をしまうデータ構造を考える。
・「この文字列Sはデータの中にありますか？」という質問に高速で
答えるためにはバケツは便利だが、非常に多くのバケツが必要
・しかし、文字列の数自体は少ないだろう
・そこで、例えば、頭2文字だけでバケツを作ったらどうだろう？
 3文字目以降が異なっても、頭2文字が同じなら同じバケツに入
る。バケツを共有してメモリを節約している
 そのため、バケツが空なら、S はない、と簡単に答えられるが、
バケツが空でないときは、バケツの中身を全部調べて、S がある
かないかチェックしなければならない
文字列のバケツ
・「バケツは数値しか入らないんじゃない？」
・その通りなので、文字列は他の場所にしまい、バケツにはそのイ
ンデックスを入れる
１： ABCABC
２： ABBBBB
３： CCCBBB
・「頭2文字」は数値に変換する。例えばABCからなる文字列の場
合は、A=0,B=1,C=2 と思って、3進数2桁の数と解釈
AB  1 、CC  8 となる
０１２３４５６７８
データの偏り
・文字列をしまう場合、文字列の頭2文字がある程度均質であれ
ばいいが、偏っていたらどうしよう？
 あるバケツにデータ集中して、のこりは空ばかり、となる
・ならば、頭2文字でなく、文字列から整数への、均一な写像関数
を持ってきたらどうだろうか？
（これをハッシュ関数、データに対する写像の値をハッシュキー、
ハッシュ値とよぶ）
 実用を考えれば、似たものが異なる値を持つほうがいい
・例えば、x1,x2,x3 ,… に対して、 (x1)1+(x2)2+(x3)3 や、
((x1+1)x2+1)x3… などの、バケツの大きさ（ハッシュの大きさ）の
剰余をとったものを使う
ハッシュの大きさ
・さて、ハッシュ関数のおかげで偏りなくデータをしまえそうだが、
ハッシュの大きさはどうしたらいいのだろうか？
 基本的に、バケツにデータがたくさん入っていると検索に時間
がかかるので、なるべく異なるデータが同じところに入らないよ
うにしたほうがいい
 もともと、データをとっておくところは必要なので、それと同じ
位はメモリを使ってもいいんじゃないか？
・ならば、例えば、データの数の定数倍にする。計算量の意味で
も損失なし
・データが増えてきたら、スタックと同じように、サイズを2倍に変更
して作り直せばよい
まとめ
・スタックとキュー：配列とカウンタをセットにして、逐次的にくる
データに対応
・リスト：隣接構造を記憶することで、順番を保ちながらの挿入
削除を効率化
・バケツ：値による分類で検索を容易に
・ハッシュ：ハッシュキーを使ったバケツで、分類精度とメモリ効
率の良さを両立させる

Download Report