【アルゴリズム入門オプション問題】データ構造〜配列の基本

こんにちは。ECF代表のヒガです。

本記事では初心者向けアルゴリズムの演習問題を紹介しています。日頃のプログラミング学習にご活用ください。

はじめに

アルゴリズムとは、コンピューターに行わせる計算手順のことです。自在にプログラムを作るには、プログラム言語の文法の知識とともにアルゴリズムの考え方を身につけることが必要になります。

アルゴリズム技法習得の肝は「繰り返し」の活用です。この連載では、簡単な題材で繰り返しを使うアルゴリズムの基本パターンを練習していきます。

演習問題の一覧や勉強スタイルについてのアドバイスはこちらからどうぞ。

【プログラミング初心者向け】アルゴリズム入門演習問題集〜繰り返しをマスターしよう！

こんにちは。ECF代表のヒガです。プログラミング初心者向けアルゴリズム演習問題の連載記事まとめです。日頃のプログラミング学習、講義、研修等での演習にご活用ください。「繰り返しアルゴリズム」をマスターしようアルゴリズムとは、コンピュ...

【オプション問題】データ構造〜配列の基本

注意：今回はアルゴリズムの演習問題ではなく、データ構造（配列）についての解説となっています。配列の役割、プログラムでの使用方法に問題がない方であれば、軽く流し読みしてもかまいません。さらっと終えてQ024に進みましょう。

配列を使って、以下の手順が問題なくできるか確認してください。

整数型（Javaではint型）5個分の配列を宣言し、利用できるようにしてください。【配列の宣言】
上記の配列に以下の値を代入してください。【配列の利用〜添字指定で代入】

添字代入する値

0 10

1 25

2 9

3 3

4 15
上記の配列について「0番のデータ」の内容を表示してください。【配列の利用〜添字指定で表示】
上記の配列について「1番のデータ」と「4番のデータ」を足した結果を表示してください。【配列の利用〜添字指定で計算】
続けて、新しく上記とは別の配列変数名で整数型（Javaではint型）3個分の配列を宣言し、利用できるようにしてください。ただし、今度は宣言と同時に以下の値が代入されるようにしてください。【配列宣言と同時に初期化】

添字代入する値

0 4

1 8

2 12
「１つ目の配列の3番のデータ」と「2つ目の配列の2番のデータ」をかけ算した結果を表示してください。【配列変数名で区別しての利用】

添字	代入する値
0	10
1	25
2	9
3	3
4	15

添字	代入する値
0	4
1	8
2	12

実行例は次のとおりです。

ヒント

今回は特にありません。必要があれば、ご自身の使用するプログラム言語の解説書や解説サイトを確認しましょう。

解答例と解説

考え方

データ構造

プログラムでデータを管理（記憶）するには、まずは変数の利用を検討します。変数は「箱」のイメージで、記憶させたいデータ（数値、ビット列）を入れたり出したりできます。

しかし社員管理システムのような実践的なプログラムのアルゴリズムを考えようとすると、変数を使うのは現実的でない場面が出てきます。例えば、1,000人分の社員データから特定の社員を探し出すアルゴリズムを実現するためには、プログラム内で変数を1,000個作成して管理することになってしまいます。

そこで、アルゴリズムとは別に、複数のデータを効率よく管理する形式（複数データ要素の格納方法）がいくつも考え出されました。これをデータ構造と呼びます。

実践的なプログラムを作成するときには、アルゴリズムに適したデータ構造を選ぶことになります。別の言い方をすると、アルゴリズムを本格的に学ぶときには、一緒にデータ構造の種類についても学んでいく必要があります。

なお、初心者向けである本連載では、データ構造の最も基本である配列のみを扱っていきます。

よく使うデータ構造の種類

配列

データを複数まとめて管理することができる大きな箱のような記憶領域です。最も素朴なデータ構造で、一般的なプログラミング言語では文法として用意されています。順番の概念があり、添字（インデックス）と呼ばれる整数値を使ってデータ要素にアクセスします。

線形リスト

複数のデータ要素を順序付けて管理するデータ構造です。順番の概念があり、使い勝手は配列と似ています。配列が1つの大きな箱で先頭から小部屋を区切るイメージであるのに対し、線形リストは1つ1つの箱が自分の次の箱のありか（アドレス）を管理している、という構造を持っています。そのため、要素の順番を入れ替えたり、途中の要素を削除したり、途中に新しく要素を追加することが簡単にできるという特徴があります。

スタック

データ要素の持ち方自体は配列や線形リストと同じですが、データの出し入れ方法に特徴があります。データをスタックに入れる（プッシュする）と、データを積み上げていくイメージで管理されます。スタックからデータを取り出す（ポップする）と、積み上がったデータの一番上のデータが取り出されます。このプッシュ・ポップの動作はLIFO（Last In First Out）と呼ばれ、様々なアルゴリズムで便利に使うことができます。

マップ

添字のような整数値ではなく、文字列で名前（キー値）を付けて個々のデータ要素を管理するデータ構造です。個々のデータ要素が正しく管理できるように、キー値は重複してはいけません。連想配列とも呼ばれ、配列と同じ感覚で使えるような文法をもつプログラム言語もあります。名前が分かれば一発で目的のデータを取得することができるという特徴があります。

木構造

線形リストと同じ様に個々の箱が次の箱のありか（アドレス）を管理情報として持つのですが、1つの「親」箱に複数（0個以上）の「子」箱が結びつく構造となっています。各データ要素は自由に結びつけることができるわけではなく、格納データの大小関係のようなルールを決めます。ルートと呼ばれる最も根本のデータからルールに従ってたどっていくことで、効率的に目的のデータ要素を探し当てるアルゴリズムを組むことができます。

フローチャート例

今回はフローチャートはありません。

なお、一般的なフローチャートの記法では配列の添字は1から始まることが多いです。しかし、多くのプログラム言語では配列の添字は0から始まるので、特にフローチャートとプログラムを同時に学習している初学者の方は混乱しないように気をつけましょう。

本連載でも、フローチャート例では配列の添字は1から始まるものとして紹介していきます。

Javaでの実装例

public class ArrayOption {
    public static void main(String[] args) {
        int[] a = new int[5]; // 1.配列の宣言
        
        // 2.添字指定で代入
        a[0] = 10;
        a[1] = 25;
        a[2] = 9;
        a[3] = 3;
        a[4] = 15;
        
        System.out.println(a[0]); // 3.添字指定で表示
        
        int x = a[1] + a[4]; // 4.添字指定で計算
        System.out.println(x);
        
        int[] b = {4, 8, 12}; // 5.配列宣言と同時に初期化
        
        int y = a[3] * b[2]; // 6.配列変数名で区別しての利用
        System.out.println(y);
    }
}

配列に関する各文法は今後の演習問題で利用していきます。しっかり押さえておきましょう。