基本データ構造

プログラムで操作するデータを,コンピュータの内部表現として実現するのがデータ構造です.「アルゴリズム+データ構造=プログラム」と言われるほど,データ構造とアルゴリズムには密接な関係があります.

まずは,データ構造の中でよく用いられる基本データ構造を説明します.種類として,基本データ型構造型抽象データ型があります.

基本データ型は構造をもたないデータで,単純型ポインタ型があります.単純型には次の種類があります.

整数型
整数値を表すデータ型です.
実数型
実数値を表すデータ型で,浮動小数点型と固定小数点型に分けられますが,浮動小数点型を実数型とするプログラム言語が多いです.
文字型
文字を表すデータ型す.コンピュータ内部では,文字は文字コードによって表現できます.
論理型
真と偽の2つの値で表されるデータ型です.
列挙型(数え上げ型)
順番に並んでいるデータを表し,データの並んでいる順に「順序数」と言われる,0からの一連の番号をつけます.

一方,ポインタは,データがコンピュータ内部のどこにあるかを指し示す値で,この値の集合がポインタ型です.

例えば,変数aに対してポインタpを宣言し,pの指す値を変数aが格納されている場所とすると,pを使って変数aの内容を操作できます.なお,ポインタが宣言された段階では,どこも指し示していないことを表すNULL(NIL)という値を使います.

構造型には配列型レコード型(構造体)があります.

配列型は,同じ基本データ型が複数個あるものの集合で,配列を構成するデータを配列の要素と言います.配列の要素への操作は添字を使います.プログラミング言語によって,一番始めのデータの添字を0にするか1にするか分かれています.例えば,8番目の要素を表すとき,それぞれa[7]やa[8]と表します(配列に使うかっこは( )の場合もあります).

Column

特定のプログラミング言語の問題ではなく,流れ図に配列を使う問題がでた場合,配列の添字は0から始まるのか1から始まるのか,問題文中に書いてあるはずです.

先ほどの例は1次元配列で,a[8][8]のように2次元以上の配列(多次元配列)も宣言できます.なお,1次元配列を特に線形リストと言います(「リスト」の項目で説明します).

レコード型は,色々なデータの値を1つにまとめたものです.例えば,学生のデータを宣言するなら,氏名(文字型),年齢(整数型)が要素として考えられます.このように,異なるデータ型を1つの集合として管理できます.

抽象型は,データの構造とそれらへの操作をまとめた(抽象化した)データ型で,オブジェクト指向に基づいています.

リスト

コンピュータ内部では,データの並びや列をリストと言います.リストは各データがポインタでつながれており,連結リストとも言われます.ポインタには次のデータのアドレス(番地)が記録されています.各データが順番に並んでいる必要はありません.

まず,リストの種類を示します.

単リスト(片方向リストまたは単方向リスト)
各データが,次のデータのアドレスを記録するポインタを1つだけもったリストです.先頭のデータへのポインタを記録する場所をルートと言います.
双リスト(双方向リスト)
各データが,次のデータと前のデータのアドレスを記録するポインタを1つずつもったリストです.単リストでは先頭からしかたどれませんが,双リストでは逆方向へたどることが可能です.
環状リスト(巡回リストまたは循環リスト)
最後尾のデータのポインタが,先頭のデータのアドレスを記録しています.単リスト・双リストの両方の場合があります.

言葉では分かりづらいので,具体例を挙げながら,データの探索・追加・削除について説明します.

番地 データ ポインタ
10東京30
20札幌NULL
30大阪20

これは単リストの例で,ルートは10を指しています.

札幌のデータを参照するときは,まず,ルートから10番地の東京を参照します.次のデータは30番地の大阪なので,大阪へ移動します.大阪の次のデータは20番地の札幌なので,札幌へ移動します.これで探索が完了します.

次に,データを追加します.例えば,大阪と札幌の間にデータ「福岡」(40番地)を追加します.

まず,大阪のポインタを福岡の場所である40に設定します.そして,福岡のポインタを札幌の場所である20とします.これでデータの追加が完了します.この操作を行った後のリストは次のようになります.

番地 データ ポインタ
10東京30
20札幌NULL
30大阪40
40福岡20

最後に,データを削除します.例として,大阪のデータを削除します.

大阪の次のデータは札幌なので,東京から札幌へ直接いけるように,東京のポインタを札幌の場所である20とします.これでデータの削除が完了します.この操作を行った後のリストは次のようになります.

番地 データ ポインタ
10東京20
20札幌NULL
30大阪20

この状態では「大阪」のデータ自体は削除されていません(参照できなくなるだけです).データ自体を削除する場合,リストを再構築します.

スタックとキュー

スタック

リストまたは配列の特殊な場合で,データの出し入れがリスト(配列)の一方でのみ行われます.スタックへのデータの格納をプッシュ,スタックからデータを取りだすことをポップと言います.データは,後に入れたものが先に取りだされるLIFO方式です.

図解すると次のようになります.

スタックのイメージ

スタックを配列と見なしたときのプッシュとポップのアルゴリズムは以下の通りです.ここで,配列の名前をa(添字は1から始まるものとします),スタックが格納できるデータの個数をn,データが格納されている個数をI(初期値は0)とします.

スタック(プッシュ)
スタック(ポップ)

Column

スタックの用途の1つに,プログラムのサブルーチンの,戻り値の番地を記録するものがあります.

大きいプログラムになると,1つのプログラムでは膨大になるので,複数のプログラム(サブルーチン)に分けます.サブルーチンの中でサブルーチンを呼びだすこともあります.

メインプログラムからサブルーチン1に移動する際,スタックにメインプログラムの番地を表すデータを格納します.なぜなら,サブルーチン1が終わったときに,メインプログラムに戻る場所を記録する必要があるからです.

サブルーチン1の中にサブルーチン2があれば,同様にサブルーチン1の番地を表すデータを格納します.サブルーチン2が終了した後,スタックからデータを取りだし,サブルーチン1の場所の情報を得ます.サブルーチン1からメインプログラムに戻る場合も同様です.

キュー(待ち行列)

リストや配列の特殊な場合で,データの出し入れがリスト(配列)の先頭と最後尾の両方で行われます.キューにデータを格納することをエンキュー,キューからデータを取りだすことをデキューと言います.データは後に入れたものが先に取りだされるFIFO方式です.

図解すると次のようになります。

キューのイメージ

キューを配列と見なしたときの格納と取りだしのアルゴリズムは,基本的な考え方はスタックと同じです.キューの状態として次の場合が考えられます.

head tail
head tail
tail head

データを格納するとtailの値が1足されます.ここで,データの格納場所をn個としたとき,n=tailならばキューがいっぱいであるとは限りません(2番目の図).n=tailかつキューがいっぱいではないときにデータを格納するなら,tailを1番目とします(3番目の図).

キューにデータを格納するときと取りだすときのアルゴリズムを示します.配列の名前をa(添字は1から始まるものとします),キューが格納できるデータの個数をn,データの先頭をhead,最後尾をtailとします.

キュー(エンキュー)
キュー(デキュー)

Column

キューの用途として,OSのタスク管理やデータ管理が挙げられます.

なお,先頭と末尾の両方でエンキューとデキューができるデータ構造をデック(両方向待ち行列)と言います.

木とは

リストを分かりやすく使ったデータ構造です.以降の説明では図を使いますが,実態はポインタを使ったリストです.

木の1つの例を示します.

木構造

この木をリストで表現したものを示します.

ポインタ
12
23
36
45,7
5NULL
67
7NULL
8NULL

説明の便宜のため数字を振りましたが,実際には何らかのデータが格納されています.

木にはレベル(深さ)があり,上図の例では,1がレベル0,2,3がレベル1……となります.

次に,木に関する用語を説明します.

上図の線が枝です.
節(節点またはノード)上図の円が節です.
枝がでていない節で,上図では5,7,8が該当します.
根(ルート)枝が入ってこない最初の節で,上図では1が該当します.
節より1つ上位のレベルです.
節より1つ下位のレベルです.
兄弟同じ親をもつレベルの節で,上図では2,3や4,5が兄弟です.2,4等は兄弟ではありません.
部分木ある節より下位のレベルの節全てで,左部分木・右部分木という言葉もあります.上図の2の左部分木は4,5,8です.

木は,根以外の節は必ず1つだけ親をもちます.また,ある節のもつポインタは,その左の子と兄弟を指します.

二分木と二分探索木

全ての節が2個以内の子をもち,子を左と右に区別したものを二分木二進木またはバイナリツリー)と言います.上図の例も二分木の1つです.一方,子の数が3つ以上の木を多分木と言います.

上図でポインタによる木の表現を示したが,これを二分木と考え,左の子へのポインタ・右の子へのポインタをもつものとも考えられます.

一般に二分木の中で,次のような木を完全二分木と言います.完全二分木は,レベルの最大値をkとすると,節の数が2k-1-1です.

完全二分木

二分木の内,全ての節で次の条件を満たしている木を二分探索木と言います.

二分探索木の一例を示します.

二分探索木

3を探す例を考えます.根は4で,3<4ですから,3は4の左部分木にあります.次の節は2で,3>2ですから,3は2の右部分木にあります.そして,3を発見して探索が終了します.

二分探索木は二分木であれば何でも構いませんが,木のバランスが悪すぎると探索の効率が悪くなります.

木のデータは追加・削除されることがあります.上図で8を追加するなら,7の右側に配置します.また,2を削除する場合は,1か3を2の位置に配置します.

常に一定の大小関係(親>子または親<子)が成立している二分木をヒープと言います.配列と密接な関係があり,データのソート(整列)に役立ちます.

また,どの節でも左部分木と右部分木の高さ(節から一番遠い葉までの枝の数)が1つしか違わない二分木をAVL木と言い,木のレベルがほぼ等しい木をバランス木(平衡木)と言います.

B木

今までの木は,各節の要素に実際のデータ値が格納されていました.これに対しB木は,葉以外にはデータは格納されません.上図の例で2の部分は,B木では2のデータをもつ葉へのポインタ(この場合は1)を指します.

B木は多分木に一定の条件をつけて,データの追加・削除に伴う木のアンバランスを避けたデータ構造です.根以外の各点はn個以上の要素をもち,各点には多くとも2n個の要素があります.各点は要素数に1加えた数の子をもち,根から全ての葉までの深さは等しくなります.

木の走査(探索)法

次の3つがあります.

先行順(前順)走査
根→左部分木→右部分木の順に探します.
後行順(後順)走査
左部分木→右部分木→親の順に探します.
中間順(間順)走査
左部分木→親→右部分木の順に探します.

木構造はデータの探索に有利なデータ構造です.

ハッシュ

今までのデータ構造は,基本的にデータの先頭から目的のデータを探す順次探索でしたが,目的のデータが最後の方にあった場合は時間がかかります.そこで,データのキー値から直接データを記憶し,探索時にそれを利用してデータを探すハッシュ法があります.これは直接探索法の1つです.

具体的な手法(ハッシュ関数)を示します.

自乗・中央法
キー値を自乗し,その中央の数字を使います.1234ならば,12342=1522756より,中央の2275がハッシュ値です.0である桁数が多い場合は不向きです.
除算法
キー値に最も近い素数で割った余りをハッシュ値とします.
基数変換法
10進数以外で表したキー値の下位の桁を使います.例えば,1234(10)=2578(13)より,578をハッシュ値として使います.

異なるキー値からハッシュで得られる値が同じになってしまうことがあります.これを衝突と言い,先に格納されていたデータをホーム,後のデータをシノニムと言います.衝突の対策を次に示します.

シーケンシャル法
ホームが格納されていた次の場所にシノニムを格納します.その場所も埋まっていた場合,空いている場所が見つかるまで順次探索します.
チェーン法
シノニムを全く関係ない場所に格納し,その場所のアドレスをポインタでリストにつなぎます.
オープンアドレス法
シノニムを別のハッシュ関数により再ハッシュします.