データ構造はアルゴリズムと表裏一体
同時に考えてプログラムに仕立てる

講師 矢沢 久雄

木構造による効率的なサーチ

図14●単純な配列と木構造の比較
単純な配列を利用した場合,順番にたどっていかなければならない。図の例の場合,6つの経路をたどることになる。木構造を利用すれば,どの値を検索する場合でも経路は2つで済む
 「木構造」は,双方向のリスト構造を応用して配列に格納されたデータを根(ルート)から2つずつ枝分かれする構造にしたものである。木構造では,左側の枝に小さいデータ,右側の枝に大きいデータを格納する。このデータ構造を採用すると,単純な配列に比べて目的のデータをより短い経路でサーチできる(図14[拡大表示])。

スタックとキュー

 他に,プログラムが次々とデータを受けるような状況でよく利用されるデータ構造として,「スタック」および「キュー」と呼ばれるものがある。スタックもキューもプログラム・コード上では配列として実現されるのだが,配列のインデックスを意識しないで利用できる。データを格納する一種のオブジェクトである。

 スタックはLIFO(Last In First Out)といって,最後に格納されたデータが最初に取り出される仕組みである。スタックとは「干草を積んだ山」という意味である(図15[拡大表示])。スタックは,データを一時的に保存するためと,簡単な手順でデータの交換を行うために利用する場合が多い。

図15●スタックの構造
スタック,キューの両方とも,データを一時的にためるためのデータ構造。スタックは,最後に入れたものを最初に取り出すデータ構造
 キューはFIFO(Fisrt In First Out)といって,最初に格納されたデータが最初に取り出される。キューは「待ち行列」とも呼ばれ,一度に大量に入力されたデータの処理が間に合わない場合のバッファ*10の役割をするものである(図16[拡大表示])。

 例えば,皆さんが利用しているパソコンのキーボード・ドライバ*11に,キューが利用されている。ワープロ・ソフトで文字入力を行っているときに,キー入力から若干遅れて文字が表示されることがあるだろう。これは,あまりに高速なキー入力によるデータを,一時的にバッファに格納し,皆さんが一呼吸置いたタイミングでキューからワープロ・ソフトにデータが取り込まれているからである。

 誌面の都合でスタックとキューのサンプル・プログラムを省略するが興味のある方は参考文献*12を参照してほしい。

図16●キューの構造
キューは,最初に入れたものを最初に取り出すデータ構造

まとめと次回予告

 アルゴリズムと同様に,データ構造を考えることにもパズルを解くような楽しさがある。そもそも,データ構造をイメージしながらでなければアルゴルリズムも考え付かないはずである。データ構造が不明確なアルゴリズムは,不完全なものでありプログラム・コードに置き換えられない。

 さて,次回は「アルゴリズムとデータ構造の応用」と題して,皆さんをアッと驚かせるようなアルゴリズムと,その手順に美しさを感じさせるようなアルゴリズムを楽しく解説する予定である。