プログラムを作成するには、アルゴリズムとデータ構造の2つを一緒に考えなければならない。なぜなら双方に見合ったものが必要だからだ。ここでは、データ構造の基本、覚えておくべき定番データ構造、定番データ構造をプログラムで表現する方法についてまとめ、その要点を捉える。
１ メモリーと変数の関係
メモリーと変数の関係は、変数を使ってメモリーにデータを格納したり、メモリーからデータを読み出したりするというものだ。C言語、Java、BASICなどほとんどのプログラミング言語では、アドレスを指定してプログラミングするのが面倒なためこの関係を用いている。
コンピュータが取り扱うデータは、メモリーと呼ばれるICの中に記憶される。一般的なパソコンでは、メモリーの内部が8ビット（＝1バイト）ごとのデータ格納領域に区切られていて、それぞれの領域を区別するための番号がつけられている。この番号のことをアドレス（番地）と呼んでいる。64Mバイトのメモリーを装備したパソコンなら、0〜64M（M=100万）までのアドレスがある。
プログラマは、変数aが何番地のメモリー領域になるのかを意識する必要はない。プログラムの実行時にOSが、それまで未使用だったメモリー領域の一部を変数aのために割り当ててくれるからだ。このように、たった1個の変数がプログラムにおけるデータの最小単位であり、それが物理的なメモリー領域に対応する。
２ データ構造の基本は配列
配列とは、複数のデータを格納するためのメモリー領域をまとめて確保し、全体に1つの名前を付けたものである。例えば、1000人の従業員の給与を合計するプログラムでは、1000個の変数を宣言して使うのではなく、配列を用いる。配列によって、複数の変数を同時に宣言するのと同じプログラムが効率的に作成できる。
配列は、データ構造の基本だといえる。なぜなら、配列がメモリーの物理構造そのものだからである。メモリーには、データを格納するための領域が連続的に並んでいる。プログラムでは、メモリー全体の中から必要な領域を確保して使う。これをプログラムの構文で表すと配列になるのだ。
３ 定番アルゴリズムのデータ構造として配列を使う
データ構造の基本である配列を使えば、大量のデータを処理する様々なアルゴリズムをプログラムで実現できる。例えば、線形探索という定番アルゴリズムを使って、配列xに格納された1000個のデータの中から777というデータを見つけるプログラムを作成することができる。
C言語では、配列の要素を先頭から末尾まで連続的に処理するためにfor文を使う。for文は、繰り返し処理を行う機能を提供する。配列とは別に変数iを宣言し、for文の後ろのカッコの中に、変数iを0〜999まで1ずつインクリメント（増加）させる処理を記述する。変数iのように繰り返し回数をカウントする変数のことを「ループ・カウンタ（loop counter）」と呼ぶ。配列が便利なのは、ループ・カウンタの値と配列のインデックスを対応させて使えるからである。
また、バブル・ソートというアルゴリズムを使って、配列の中に格納された1000個のデータを降順に並べ替える（ソート）こともできる。バブル・ソートとは、配列の先頭から末尾まで隣り合った2つの要素の値を比較し、大きい値と小さい値を交換することを繰り返すものである。
これらの例から言えることは、配列とfor文を使うことで、線形探索やバブル・ソートのアルゴリズムを実現するプログラムが作成できるということである。
４ 定番データ構造の種類
アルゴリズムに定番と呼べるものがあるように、データ構造にも定番となるものがある。これらのデータ構造は、物理的なメモリー構造をプログラムによって論理的に変化させてしまうものである。順に解説する。
- スタック（stack）：データを山のように積み上げる。LIFO（Last In First Out）形式。最後に格納されたデータが最初に処理される。原義は干し草を積んだ山
- キュー（queue）：データを行列のように並ばせる。FIFO（First In First Out）形式。最初に格納されたデータが最初に処理される。待ち行列
- リスト：データの並びを任意に変更できる
- 2分木：データの並びを二股に分ける。リストの特殊形態
５ スタックとキューの実現方法
スタックとキューは、すぐには処理できないデータをとりあえず格納しておくという点で似ている。違いは、スタックはLIFO形式であり、キューはFIFO形式であることである。
スタックを実現するには、配列、スタック・ポインタおよびプッシュ関数とポップ関数のセットが必要となる。まずスタックのサイズ（スタックに格納できる最大データ数）を要素数とした配列と、スタックの最上部に格納されたデータのインデックスを表す変数を宣言する。この変数を「スタック・ポインタ」と呼ぶ。スタックのサイズは、プログラムの目的に応じて任意に決める。次に、スタックにデータを格納する（プッシュする）関数と、スタックからデータを取り出す（ポップする）関数を作成する。これらの関数の中には、スタックに格納されているデータの数やスタック・ポインタの値を更新する処理を記述する。
キューを実現するには、任意のサイズの配列、キューの先頭のデータのインデックスを表す変数、キューの末尾のデータのインデックスを表す変数およびキューにデータを格納する関数とキューからデータを取り出す関数のペアが必要となる。配列の末尾までデータを格納したら、次の格納位置が配列の先頭に戻るようにする。これによって配列の末尾と先頭がつながるので、物理的には直線の配列が、論理的には輪になる。
６ 構造体の仕組み
構造体とは、複数のデータを１つにまとめて名前を付けたものである。C言語のプログラムでリストと2分木を実現する方法を理解するには、この知識が必要になる。例えば、学生の国語、数学、英語のテスト結果をまとめてTestKekkaという構造体を作ることができる。
７ リストと２分木の実現方法
リストの実現方法は「自己参照構造体」を使うことである。C言語における自己参照構造体とは、他の要素へのポインタを持つ構造体のことである。ポインタとはアドレスのことで、「*」（アスタリスク）と表記される。これを用いることで、ポインタを介して同じ型の別の構造体へ次々にデータをつないでいくデータチェーンを持つことができる。リストを使うことで要素の並べ替えをする値の数が減り、プログラムの処理時間を短縮できる。これは要素の削除や追加をするプログラムでも同じである。
2分木の実現方法は、リストのつながり情報を2つ持った自己参照構造体を使うことである。データを見つける「2分探索」と呼ばれるアルゴリズムなどで用いられる。単純な配列のように一直線ではなく、2分木の二股に分かれた経路を追うことで、目的のデータに早くたどり着くことができる。
最後に
言語における単語、文法、慣用句が、プログラムにおけるプログラミング言語、データ構造、アルゴリズムに対応している。定番アルゴリズムと定番データ構造を知ったならば、それらを応用していかなければならない。「オリジナルを創り出せるのが、本当の技術者」。筆者もまだまだ修行が必要である。
次回は、オブジェクト指向プログラミングについてまとめる。
 |
 |
