アルゴリズム

アルゴリズムとデータ構造

湯田幸八
伊原充博

コロナ社

1 アルゴリズムと計算量

  • 1.1 アルゴリズムとは
  • 1.2 アルゴリズムの性能評価と計算量
  • 1.3 計算量の漸近的な評価
  • 1.4 O記法
  • 1.5 いろいろな計算量の定義
  • 演習問題

2 基本的なデータ構造

  • 2.1 データとその構造
  • 2.2 データの表現法
  • 2.3 配列による順配置
    • 2.3.1 配列の参照
    • 2.3.2 配列への挿入
    • 2.3.3 配列からの削除
  • 2.4 ポインタによるリンク配置
    • 2.4.1 ポインタ
    • 2.4.2 リンク配置
    • 2.4.3 構造体
    • 2.4.4 クラス
  • 2.5 リスト
  • 2.6 順配置によるリストの実現
  • 2.7 ポインタによるリンク配置(連結リスト)のCによる実現
    • 2.7.1 連結リストの構成
    • 2.7.2 連結リストの作成
    • 2.7.3 連結リストの操作
  • 2.8 ポインタによるリンク配置(連結リスト)のC++による表現
  • 2.9 双方向連結リスト
  • 2.10 スタック
    • 2.10.1 スタックとは
    • 2.10.2 スタックのデータ構造としての表現
    • 2.10.3 プログラム
  • 2.11 キュー
    • 2.11.1 キューとは
    • 2.11.2 キューのデータ構造としての表現
    • 2.11.3 配列を用いて順配置で実現したキューのアルゴリズム
    • 2.11.4 リングバッファによるキューの実現
    • 2.11.5 プログラム
  • 2.12 木
    • 2.12.1 木とは
    • 2.12.2 木の概念
    • 2.12.3 2分木
    • 2.12.4 2分木の表現
    • 2.12.5 2分木の走査
    • 2.12.6 数式を表す木
    • 2.12.7 木の表現
    • 2.12.8 プログラム
  • 演習問題

3 探索

  • 3.1 探索とは
  • 3.2 線形探索
  • 3.3 2分探索
  • 3.4 ハッシュ法
  • 3.5 文字列の探索
    • 3.5.1 力まかせアルゴリズム
    • 3.5.2 クヌース-モリス-プラット法
    • 3.5.3 ボイヤ-ムーア法
  • 3.6 木の探索
    • 3.6.1 2分木探索木
    • 3.6.2 B木
  • 演習問題

4 整列

  • 4.1 整列とは
  • 4.2 選択によるソート
  • 4.3 交換によるソート
    • 4.3.1 バブルソート
    • 4.3.2 シェーカソート
    • 4.3.3 クイックソート
  • 4.4 挿入によるソート
    • 4.4.1 単純挿入ソート
    • 4.4.2 シェルソート
  • 4.5 併合によるソート
  • 4.6 外部ソート
  • 演習問題

5 グラフ

  • 5.1 グラフとは
  • 5.2 グラフの基礎
    • 5.2.1 グラフの定義
    • 5.2.2 グラフの用語
  • 5.3 グラフの表現法
    • 5.3.1 順配置
    • 5.3.2 リンク配置
  • 5.4 グラフの探索
    • 5.4.1 深さ優先探索
    • 5.4.2 幅優先探索
  • 5.5 グラフの応用
  • 演習問題

6 いろいろな問題

  • 6.1 ハノイの塔
  • 6.2 8クイーン問題
  • 6.3 ナップサック問題
  • 6.4 描画
    • 6.4.1 樹木曲線
    • 6.4.2 ヒルベルト曲線
    • 6.4.3 シェルピンスキー曲線
  • 演習問題

付録
参考文献
演習問題解答
索引