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

講師 矢沢 久雄

ソートでも“順番”に配列のインデックスを使う

図6●バブル・ソートのイメージ
先頭に来るべき学生を,現在先頭にいる学生とそれ以降の学生を比べることを繰り返して決定する。次に先頭から2番目,3番目,…,9番目を決定する。末尾の学生は9番目を決定することで自動的に決定する。

 つぎに,ソートの問題を解いてみよう。ソートには,データを小さい順に並び替える「昇順」と,大きい順に並び替える「降順」とがある。ソートされたデータの値が配列の先頭から末尾に向かって昇っていくのが昇順であり,降りていくのが降順である。ここでは,比較的理解しやすい「バブル・ソート」と呼ばれるアルゴリズムを利用してみよう。

【問題4】表1のデータを降順に並び替えよ。

 先の例と同様に,バブル・ソートのアルゴリズムも人間の感覚に近いものである(図6[拡大表示])。10人の学生にテストの得点の書かれたゼッケンを付けてもらい,横一列に並んでもらった様子をイメージしてほしい。学生の並び順を降順ソートするにはどうするか? 多くの皆さんが考え付くであろう手順が,バブル・ソートのアルゴリズムそのものである。

図7●バブル・ソート
 10人の学生の得点を配列に格納し,チェック開始点のインデックスを配列の先頭から末尾の1つ前まで順番に移動しながら,チェック開始点以降のデータの中で最大のデータを見つけることを繰り返す。最大データを見つけた場合,チェック開始点のデータと交換する。チェック終了点は配列の末尾に固定しておく(図7[拡大表示],写真4[拡大表示])。

多次元配列で表現するテーブル

 表2[拡大表示]を見ていただきたい。これは3人の学生に5科目のテストを行った結果を示すものである。この表から以下の問題を解くためのアルゴリズムとデータ構造を考えてみよう。

【問題5】表2に示されたデータの平均点を科目ごとに求めよ。

写真4●図7の実行結果
 この問題を解くためのアルゴリズムは問題1と同様である。それでは,データ構造はどうすればよいだろうか?

 プログラムは現実世界で行われている作業をコンピュータでシミュレートするものである。このような表をシミュレートする場合には,配列のインデックスを複数持つ“多次元配列”を利用するのが正解である*7

表2●5科目のテスト結果
 表2は横方向に5つのデータを持ち,縦方向に3つのデータを持っているので,インデックスを(4,2)または(2,4)とした2次元配列を使うことになる。どちらを使っても構わないが,ここでは(学生,科目)の順となる前者を使うことにする。データを参照するためには,2重にネストした多重ループ*8を使うことになる。科目のループの中で,学生のループを回す(図8[拡大表示],写真5)。

構造体の配列を使うとスゴイことができる

図8●多次元配列でテーブルを処理する
 ここまで,主に単純な配列を利用したデータ構造とアルゴリズムの関係を見てきた。アルゴリズムとデータ構造の関係と,その密接さが,ぼんやりと見えてきたことだろう。

 アルゴリズムと同様に,データ構造にも,既に多くの数学者やプログラマたちによって考案されたものが数多くある。ここからは,それらの中からプログラマのたしなみとして,必ず習得しておかなければならないものを紹介しよう。これらのデータ構造のイメージは,皆さんが独自のアルゴリズムを考える場合において,採用しやすい場合が多いものである。

 ここで紹介するデータ構造は,“構造体の配列”を利用した「リスト構造」と「木構造」である。いくつか新しい言葉が出てきたが,順番に解説しよう。

写真5●図8の実行結果
 構造体は,既存のデータ型を組み合せて作成する新しいデータ型である。VBでは「ユーザー定義型」と呼ぶ。ユーザー定義型は,Type~End Typeの内部に既存のデータ型を列挙することで定義される(図9[拡大表示])。まず,ある構造体の中身を見てみよう。図9上は,住所録のための構造体Jushoを定義したものである。構造体の中には,氏名,住所,電話番号,および年齢を格納するためにName,Address,Phone,およびAgeという変数のようなものがある。これらは,変数とは呼ばずに「メンバー」と呼ぶ。

 図9では構造体を定義しているだけである。実際に構造体の値を参照するためには,Jusho型の変数を定義し,その変数名にドットを付けた後にメンバー名を指定して参照する。例えば,Jusho型の変数jDataのNameメンバーに「山本信雄」という文字列を格納し,それをメッセージ・ボックスに表示する場合は,図9下のようにする。

図9●構造体の定義と,宣言,メンバー参照の方法
 この構造体を複数並べると,構造体の配列になる。リスト構造と木構造は,この構造体の配列を応用したものである。コンピュータでデータを格納する場所はメモリーであり,連続したメモリーをプログラム・コードで表したものが配列にほかならない。メモリーを連続して参照するだけなら単純な配列で構わないが,効率を重視した順序で参照するためには構造体の配列が必要になる。

 構造体の配列を作成する方法は,単純な変数の配列と同様である。Jusho型で要素数が10個の配列なら,Dim jData(9) As Jushoと宣言すればよい。この場合は,10人の住所データを格納できるメモリーが確保されたことになる。

 データベースをご存知の方は構造体はデータベースのレコードに似ていると思うかもしれない。全くその通りで,構造体のことを「レコード型」と呼ぶ場合もある。