1.1. データ構造

1. 概要

　データ構造とは、データを効率的に格納・管理・操作するための方法や仕組みを指します。データ構造は、プログラミングにおいてデータを整理し、様々なアルゴリズムで効率的に処理するための基盤となるものです。

　情報処理において、大量のデータを適切に扱うためには、そのデータの特性や用途に合わせた最適なデータ構造を選択することが重要です。適切なデータ構造を選ぶことで、検索・挿入・削除といった操作を効率的に行うことができ、プログラムの実行速度や使用メモリを最適化することができます。

　また、BNF（バッカス・ナウア記法）は、データ構造やプログラミング言語の構文を形式的に定義するための記法であり、データ構造を明確に定義する上で重要なツールとなっています。

2. 詳細説明

2.1. 基本的なデータ構造

2.1.1. 配列（Array）

　配列は最も基本的なデータ構造の一つで、同じ型のデータを連続したメモリ領域に格納します。各要素はインデックスによってアクセスされます。

// 配列の例
int numbers[5] = {1, 2, 3, 4, 5};

　配列の特徴：

• ランダムアクセスが可能（O(1)の時間複雑度）
• サイズが固定されていることが多い
• 要素の挿入・削除が非効率的（O(n)の時間複雑度）

2.1.2. リスト（List）

　リストは、要素が順序付けられたコレクションです。配列と異なり、サイズを動的に変更できるものが多いです。

連結リスト（Linked List）

　連結リストは、各要素（ノード）がデータと次の要素へのポインタを持つデータ構造です。

// 連結リストのノード定義
struct Node {
    int data;
    Node* next;
};

　連結リストの特徴：

• 要素の挿入・削除が効率的（O(1)の時間複雑度、位置が分かっている場合）
• ランダムアクセスが非効率的（O(n)の時間複雑度）
• メモリを効率的に使用（必要に応じて動的に確保）

図2: 連結リストの図解

2.1.3. スタック（Stack）

　スタックは、データを後入れ先出し（LIFO: Last-In-First-Out）の原則で管理するデータ構造です。

// スタックの基本操作
push(element); // 要素を追加
element = pop(); // 最後に追加された要素を取り出す

2.1.4. キュー（Queue）

　キューは、データを先入れ先出し（FIFO: First-In-First-Out）の原則で管理するデータ構造です。

// キューの基本操作
enqueue(element); // 要素を追加
element = dequeue(); // 最初に追加された要素を取り出す

2.1.5. 木構造（Tree）

　木構造は、階層的な関係を表現するためのデータ構造です。最も代表的なものに二分木があります。

// 二分木のノード定義
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
};

図3: 二分木の図解

2.1.6. グラフ（Graph）

　グラフは、ノード（頂点）と、ノード間の関係を表すエッジ（辺）からなるデータ構造です。

// 隣接リストを用いたグラフの表現
vector<int> adjacencyList[N]; // N個のノードを持つグラフ

2.1.7. ハッシュテーブル（Hash Table）

　ハッシュテーブルは、キーと値のペアを格納するデータ構造で、キーをハッシュ関数で変換してアクセスします。

// ハッシュテーブルの例
HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 5);

データ構造	検索	挿入	削除	備考
配列	O(1)～O(n)	O(n)	O(n)	ランダムアクセス：O(1)、探索：O(n)
連結リスト	O(n)	O(1)	O(1)	位置が分かっている場合の挿入・削除
スタック	O(n)	O(1)	O(1)	最上位要素へのアクセス：O(1)
キュー	O(n)	O(1)	O(1)	先頭と末尾要素へのアクセス：O(1)
二分探索木	O(log n)	O(log n)	O(log n)	平衡状態の場合
ハッシュテーブル	O(1)	O(1)	O(1)	平均ケース（最悪ケース：O(n)）

図1: データ構造の時間複雑度比較表

→ 関連記事: 計算複雑度

2.2. BNFを用いたデータ構造の定義

　BNF（バッカス・ナウア記法）は、プログラミング言語の構文やデータ構造を形式的に定義するための記法です。EBNF（拡張BNF）などの変種も広く使われています。応用情報処理技術者試験では、BNFを用いたデータ構造や構文の定義の読み取りと解釈が出題されることがあります。

2.2.1. BNFの基本構文

　BNFでは、以下のような記法を用います：

<記号> ::= <表現>

　この記法は「記号は表現と定義される」ことを表します。

　BNFでは以下の記号が使用されます：

• ::= ：定義を表す
• <> ：非終端記号（さらに展開される記号）
• | ：選択肢を表す「または」
• 終端記号：引用符（””）で囲まれた文字列など、これ以上展開されない記号

2.2.2. BNFによるデータ構造の定義例

　リストの定義例：

<list> ::= <empty> | <element> <list>
<empty> ::= ""
<element> ::= <integer> | <character> | <string>
<integer> ::= <digit> | <digit> <integer>
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"
<character> ::= "a" | "b" | ... | "z" | "A" | "B" | ... | "Z"
<string> ::= <character> | <character> <string>

　二分木の定義例：

<binary-tree> ::= <empty> | <node>
<node> ::= <value> <binary-tree> <binary-tree>
<value> ::= <integer> | <character> | <string>

2.3. 時間複雑度と空間複雑度

　アルゴリズムやデータ構造を評価する際に重要な指標として「時間複雑度」と「空間複雑度」があります。

2.3.1. 時間複雑度

　時間複雑度とは、アルゴリズムの実行時間がデータサイズに対してどのように増加するかを表す指標です。一般的にはビッグO記法（O表記）で表現されます。

　主な時間複雑度の種類：

• O(1)：定数時間（データサイズに関係なく一定）
• O(log n)：対数時間（二分探索など）
• O(n)：線形時間（データサイズに比例）
• O(n log n)：線形対数時間（効率的なソートアルゴリズムなど）
• O(n²)：二次時間（単純なソートアルゴリズムなど）
• O(2ⁿ)：指数時間（総当たり探索など）

　例えば、配列の要素へのアクセスはO(1)ですが、連結リストの特定要素へのアクセスはO(n)となります。

2.3.2. 空間複雑度

　空間複雑度とは、アルゴリズムが実行中に必要とするメモリ量がデータサイズに対してどのように増加するかを表す指標です。

　例えば、単純な配列操作の空間複雑度はO(n)ですが、再帰的なアルゴリズムではコールスタックにより空間複雑度が大きくなる場合があります。

2.4. データ構造の選択基準

　適切なデータ構造を選択する際の基準には以下のようなものがあります：

1. 操作の種類と頻度：検索、挿入、削除などの操作の頻度によって最適なデータ構造が異なります。頻繁に検索を行う場合はハッシュテーブルや二分探索木が適しています。
2. 時間複雑度の要件：リアルタイム性が求められる場合は、最悪ケースの時間複雑度が重要になります。
3. 空間複雑度（メモリ使用量）の制約：メモリに制約がある環境では、空間効率の良いデータ構造を選ぶ必要があります。
4. データの特性：データのサイズ、型、分布などによって適切なデータ構造が異なります。
5. 実装の複雑さ：開発期間や保守性を考慮すると、単純なデータ構造が望ましい場合もあります。

図4: データ構造選択のフローチャート

2.4.1. 具体的な選択例

1. 頻繁な検索、少ない挿入・削除：ハッシュテーブル（検索 O(1)）
   • 例：辞書アプリケーション、キャッシュシステム
2. データの順序が重要で検索も頻繁：二分探索木（検索・挿入・削除 O(log n)）
   • 例：データベースのインデックス、優先度キュー
3. 頻繁な挿入・削除、少ない検索：連結リスト（挿入・削除 O(1)）
   • 例：ブラウザの履歴管理
4. LIFO（後入れ先出し）アクセスパターン：スタック
   • 例：関数呼び出し、式の評価
5. FIFO（先入れ先出し）アクセスパターン：キュー
   • 例：プリンタのジョブ管理、メッセージキュー

3. 応用例

3.1. プログラミング言語とコンパイラ

　プログラミング言語の設計やコンパイラの実装において、BNFは言語の構文を定義するために使用されます。また、コンパイラ内部では様々なデータ構造（シンボルテーブル、抽象構文木など）が使用されています。

3.2. データベース管理システム

　データベースでは、インデックスとしてB木やハッシュテーブルなどのデータ構造が使用され、効率的なデータの検索・更新を可能にしています。B木は、ディスクアクセスの回数を最小限に抑えるために設計されており、多くのDBMSで利用されています。

3.3. ネットワーク経路探索

　ルーターなどのネットワーク機器では、グラフアルゴリズムを用いた経路探索が行われており、グラフデータ構造が活用されています。ダイクストラ法やベルマン-フォード法などのアルゴリズムが、最短経路の計算に使用されています。

3.4. Webブラウザの開発

　Webブラウザでは、HTMLドキュメントを解析して表示するために、DOM（Document Object Model）という木構造を使用しています。また、ブラウザの「戻る」「進む」ボタンの機能には、スタックデータ構造が利用されています。

3.5. 人工知能と機械学習

　決定木、ニューラルネットワークなど、AI分野でも様々なデータ構造が活用されています。例えば、決定木は階層的な木構造を使って分類問題を解決し、グラフ構造はニューラルネットワークの表現に使用されています。

4. 例題

例題1

　次のBNF表記が定義するデータ構造を説明せよ。また、この定義に従う具体例を示せ。

<expr> ::= <term> | <expr> "+" <term> | <expr> "-" <term>
<term> ::= <factor> | <term> "*" <factor> | <term> "/" <factor>
<factor> ::= <number> | "(" <expr> ")"
<number> ::= <digit> | <number> <digit>
<digit> ::= "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9"

解答例

　この BNF 表記は、数学的な式（四則演算式）の構文を定義しています。具体的には：

• <expr> は式全体を表し、項（<term>）の加減算で構成されます。
• <term> は項を表し、因子（<factor>）の乗除算で構成されます。
• <factor> は因子を表し、数値または括弧で囲まれた式です。
• <number> は数字の列です。
• <digit> は単一の数字（0-9）です。

　この定義に従う具体例：

• 3 + 4 * 5
• (7 + 2) * 3
• 10 / 2 - 1

　これらの式は、演算子の優先順位（乗除が加減より先に評価される）を考慮した構文木として表現されます。

図5: BNFで定義された式の構文解析木の例

例題2

　スタックとキューの違いを説明し、それぞれが適している用途を具体例と共に示せ。

解答例

　スタックとキューの主な違いは、データの出し入れの順序にあります：

• スタック：後入れ先出し（LIFO）。最後に追加された要素が最初に取り出されます。
• キュー：先入れ先出し（FIFO）。最初に追加された要素が最初に取り出されます。

　スタックが適している用途：

• 関数呼び出しの管理（コールスタック）
• ブラウザの「戻る」ボタン機能
• 式の評価（括弧の対応チェックなど）

　キューが適している用途：

• プリンタの印刷ジョブ管理
• CPUのタスクスケジューリング
• ネットワークのパケットバッファリング

例題3

　連結リストを用いてスタックを実装するためのPseudocodeを示せ。push操作とpop操作の実装を含めること。

解答例

// ノード構造体 struct Node { データ: 任意の型 次: Nodeへの参照 }

// スタッククラス class Stack { private: 先頭: Nodeへの参照 = null

// push操作: スタックに要素を追加
public function push(値) {
    新ノード = new Node()
    新ノード.データ = 値
    新ノード.次 = 先頭
    先頭 = 新ノード
}

// pop操作: スタックから最後に追加された要素を取り出す
public function pop() {
    if (先頭 == null) then
        エラー "スタックが空です"
    end if
    
    値 = 先頭.データ
    先頭 = 先頭.次
    return 値
}

// スタックが空かどうかを確認
public function isEmpty() {
    return 先頭 == null
}

}

// ノード構造体
struct Node {
    データ: 任意の型
    次: Nodeへの参照
}

// スタッククラス
class Stack {
    private:
        先頭: Nodeへの参照 = null

    // push操作: スタックに要素を追加
    public function push(値) {
        新ノード = new Node()
        新ノード.データ = 値
        新ノード.次 = 先頭
        先頭 = 新ノード
    }

    // pop操作: スタックから最後に追加された要素を取り出す
    public function pop() {
        if (先頭 == null) then
            エラー "スタックが空です"
        end if
        
        値 = 先頭.データ
        先頭 = 先頭.次
        return 値
    }

    // スタックが空かどうかを確認
    public function isEmpty() {
        return 先頭 == null
    }
}

例題4

　以下の条件を満たすシステムを開発する際、最適なデータ構造を選択し、その理由を説明せよ。

条件：

• 文字列をキーとして値を格納する
• キーを使った高速な検索が必要
• データの挿入・削除も頻繁に行われる
• 格納するデータ量は数十万件程度
• メモリの使用量には制約がある

解答例

　この条件に最も適したデータ構造は「ハッシュテーブル」です。

　理由：

1. ハッシュテーブルは文字列をキーとして扱うことができます。
2. 検索操作の平均時間複雑度はO(1)であり、高速な検索が可能です。
3. 挿入・削除も平均してO(1)の時間複雑度で行えます。
4. 数十万件程度のデータ量であれば、適切なハッシュ関数と衝突解決方法を選ぶことで効率良く動作します。
5. メモリ使用量には多少のオーバーヘッドがありますが、それを上回る性能向上が見込めます。

　ただし、ハッシュテーブルを実装する際は以下の点に注意が必要です：

• 適切なハッシュ関数の選択
• 衝突解決のための方法（チェイン法やオープンアドレス法など）
• 動的なリサイズによるパフォーマンスの一時的な低下の対策

　二分探索木（特に平衡二分探索木）も検討対象となりますが、検索・挿入・削除の時間複雑度がO(log n)であり、ハッシュテーブルよりも若干劣るため、ここではハッシュテーブルを選択します。

5. まとめ

　データ構造は、プログラミングにおいてデータを効率的に管理・操作するための基盤となるものです。基本的なデータ構造には、配列、リスト、スタック、キュー、木構造、グラフ、ハッシュテーブルなどがあります。

　各データ構造には、それぞれ特徴と得意とする操作があり、問題の性質や要件に応じて適切なデータ構造を選択することが重要です。時間複雑度や空間複雑度を考慮した選択が、効率的なアルゴリズムの実装につながります。

　BNF（バッカス・ナウア記法）は、データ構造やプログラミング言語の構文を形式的に定義するための記法であり、データ構造を明確に表現する手段として重要です。応用情報技術者試験では、BNFを使用したデータ構造の定義を理解し、その構造に従ったデータ処理を設計・実装できる能力が問われます。

　データ構造の選択に当たっては、操作の種類と頻度、時間・空間複雑度の要件、データの特性などを総合的に考慮する必要があります。そのためには、各データ構造の特性を十分に理解し、状況に応じて適切に選択できるようになることが重要です。

　データ構造の理解は、アルゴリズムの設計・実装において不可欠であり、情報処理技術者として様々な問題を効率的に解決するために必要な基礎知識です。応用情報技術者試験では、これらの基本概念を理解し、適切なデータ構造を選択・応用できる能力が求められます。