アルゴリズム

Cプログラマのためのアルゴリズムとデータ構造

近藤嘉雪
ソフトバンククリエイティブ

第1部 アルゴリズムとデータ構造の基本

  • 1 アルゴリズムとは?
    • 1.1 はじめに
    • 1.2 アルゴリズムとデータ構造の関係
    • 1.3 なぜアルゴリズムを勉強するのか?
  • 2 計算量
    • 2.1 アルゴリズムの性能の基準
    • 2.2 計算量
      • 2.2.1 線形探索法による探索の計算量
      • 2.2.2 二分探索法による探索の計算量
      • 2.2.3 データの登録に必要な計算量
      • 2.2.4 線形探索法と二分探索法の比較
      • 2.2.5 ハッシュ法
      • 2.2.6 アルゴリズムを選択する基準
  • 3 データ構造とは?
    • 3.1 抽象データ型
    • 3.2 データ構造の実現
      • 3.2.1 基本データ型
      • 3.2.2 列挙型
      • 3.2.3 配列と構造体
      • 3.2.4 ポインタ

第2部 基本的なデータ構造

  • 4 配列
    • 4.1 リスト
    • 4.2 スタック
    • 4.3 待ち行列
    • 4.4 配列によるデータ構造の表現
      • 4.4.1 リストの表現
      • 4.4.2 スタックの実現
      • 4.4.3 待ち行列の実現
  • 5 連結リスト
    • 5.1 連結リスト
      • 5.1.1 連結リストとは?
      • 5.1.2 連結リストの基本的性質
      • 5.1.3 連結リストとメモリ管理
      • 5.1.4 連結リストの操作
        • 5.1.4.1 要素の挿入
        • 5.1.4.2 要素の削除
        • 5.1.4.3 境界条件の扱い
    • 5.2 循環リスト
      • 5.2.1 循環リストとは?
      • 5.2.2 循環リストの操作
      • 5.2.3 リストの頭を用いた循環リスト
    • 5.3 双方向リスト
      • 5.3.1 双方向リストとは?
      • 5.3.2 双方向リストの操作
    • 5.4 多重リスト構造
  • 6 木構造
    • 6.1 木構造とは?
    • 6.2 順序木と無順序木
    • 6.3 二分木
    • 6.4 木のなぞり
      • 6.4.1 木をなぞる手順
      • 6.4.2 行きがけ順のなぞり
      • 6.4.3 通りがけ順のなぞり
      • 6.4.4 帰りがけ順のなぞり
    • 6.5 数式の木
    • 6.6 木の実現

第3部 探索

  • 7 探索とは?
    • 7.1 探索という操作
    • 7.2 線形探索法と二分探索法
  • 8 ハッシュ法
    • 8.1 ハッシュ法の原理
    • 8.2 衝突
    • 8.3 チェイン法
      • 8.3.1 チェイン法の原理
      • 8.3.2 チェイン法のプログラム
      • 8.3.3 チェイン法の解析
    • 8.4 オープンアドレス法
      • 8.4.1 オープンアドレス法の原理
      • 8.4.2 オープンアドレス法のプログラム
      • 8.4.3 再ハッシュ手順
      • 8.4.4 オープンアドレス法の解析
    • 8.5 ハッシュ関数
    • 8.6 ハッシュ法の応用
    • 8.7 ハッシュ法の性質
  • 9 二分木探索
    • 9.1 二分木探索とは?
    • 9.2 二分木探索の操作
      • 9.2.1 二分探索木の探索
      • 9.2.2 二分探索木の挿入
      • 9.2.3 二分探索木からの削除
    • 9.3 二分探索木の性質
  • 10 平衡木
    • 10.1 平衡木とは?
    • 10.2 AVL木
      • 10.2.1 AVL木の考え方
      • 10.2.2 AVL木の操作
    • 10.3 B木
      • 10.3.1 B木の考え方
      • 10.3.2 B木の操作
        • 10.3.2.1 B木の探索
        • 10.3.2.2 B木への挿入
        • 10.3.2.3 B木からの削除
      • 10.3.3 B木のプログラム
      • 10.3.4 B*木

第4部 整列

  • 11 整列とは?
    • 11.1 整列という操作
      • 11.1.1 内部整列と外部整列
      • 11.1.2 比較による整列と比較によらない整列
    • 11.2 整列アルゴリズムの種類
    • 11.3 整列の計算量
    • 11.4 安定な整列
  • 12 単純な整列アルゴリズム
    • 12.1 単純な整列アルゴリズムとは?
    • 12.2 バブルソート
    • 12.3 選択ソート
    • 12.4 挿入ソート
    • 12.5 単純な整列アルゴリズムの性能
  • 13 シェルソート
    • 13.1 シェルソートの原理
    • 13.2 シェルソートの計算量
    • 13.3 増分の選択
    • 13.4 シェルソートのプログラム
  • 14 クイックソート
    • 14.1 クイックソートの原理
      • 14.1.1 クイックソートの考え方
      • 14.1.2 分割のアルゴリズム
    • 14.2 クイックソートのプログラム
    • 14.3 クイックソートの計算量
    • 14.4 クイックソートの改善
  • 15 マージソート
    • 15.1 マージソートの原理
      • 15.1.1 マージ
      • 15.1.2 マージソートのアルゴリズム
    • 15.2 配列によるマージソート
    • 15.3 マージソートの性質
    • 15.4 連結リストによるマージソート
    • 15.5 外部整列
      • 15.5.1 外部記憶の性質
      • 15.5.2 マージソートを利用した外部整列

索引