データ構造はアルゴリズムと表裏一体
同時に考えてプログラムに仕立てる
講師 矢沢 久雄
ソートでも“順番”に配列のインデックスを使う
|
|
図6●バブル・ソートのイメージ 先頭に来るべき学生を，現在先頭にいる学生とそれ以降の学生を比べることを繰り返して決定する。次に先頭から2番目，3番目，…，9番目を決定する。末尾の学生は9番目を決定することで自動的に決定する。 |
つぎに，ソートの問題を解いてみよう。ソートには，データを小さい順に並び替える「昇順」と，大きい順に並び替える「降順」とがある。ソートされたデータの値が配列の先頭から末尾に向かって昇っていくのが昇順であり，降りていくのが降順である。ここでは，比較的理解しやすい「バブル・ソート」と呼ばれるアルゴリズムを利用してみよう。
【問題4】表1のデータを降順に並び替えよ。
先の例と同様に，バブル・ソートのアルゴリズムも人間の感覚に近いものである（図6[拡大表示]）。10人の学生にテストの得点の書かれたゼッケンを付けてもらい，横一列に並んでもらった様子をイメージしてほしい。学生の並び順を降順ソートするにはどうするか？ 多くの皆さんが考え付くであろう手順が，バブル・ソートのアルゴリズムそのものである。
|
| 図7●バブル・ソート |
多次元配列で表現するテーブル
表2[拡大表示]を見ていただきたい。これは3人の学生に5科目のテストを行った結果を示すものである。この表から以下の問題を解くためのアルゴリズムとデータ構造を考えてみよう。
【問題5】表2に示されたデータの平均点を科目ごとに求めよ。
|
| 写真4●図7の実行結果 |
プログラムは現実世界で行われている作業をコンピュータでシミュレートするものである。このような表をシミュレートする場合には，配列のインデックスを複数持つ“多次元配列”を利用するのが正解である＊7。
|
| 表2●5科目のテスト結果 |
構造体の配列を使うとスゴイことができる
|
| 図8●多次元配列でテーブルを処理する |
アルゴリズムと同様に，データ構造にも，既に多くの数学者やプログラマたちによって考案されたものが数多くある。ここからは，それらの中からプログラマのたしなみとして，必ず習得しておかなければならないものを紹介しよう。これらのデータ構造のイメージは，皆さんが独自のアルゴリズムを考える場合において，採用しやすい場合が多いものである。
ここで紹介するデータ構造は，“構造体の配列”を利用した「リスト構造」と「木構造」である。いくつか新しい言葉が出てきたが，順番に解説しよう。
|
| 写真5●図8の実行結果 |
図9では構造体を定義しているだけである。実際に構造体の値を参照するためには，Jusho型の変数を定義し，その変数名にドットを付けた後にメンバー名を指定して参照する。例えば，Jusho型の変数jDataのNameメンバーに「山本信雄」という文字列を格納し，それをメッセージ・ボックスに表示する場合は，図9下のようにする。
|
| 図9●構造体の定義と，宣言，メンバー参照の方法 |
構造体の配列を作成する方法は，単純な変数の配列と同様である。Jusho型で要素数が10個の配列なら，Dim jData（9） As Jushoと宣言すればよい。この場合は，10人の住所データを格納できるメモリーが確保されたことになる。
データベースをご存知の方は構造体はデータベースのレコードに似ていると思うかもしれない。全くその通りで，構造体のことを「レコード型」と呼ぶ場合もある。
