C言語による実用アルゴリズム入門

2019年1月24日

ソフトバンク

林晴比古

まえがき

CONTENTS

Chapter 1 アルゴリズム
1.1 アルゴリズムとは
1.2 ユークリッドの互除法
1.3 アルゴリズムの要件
1.4 アルゴリズムとデータ構造
1.5 計算量の表現

Chapter 2 ソート(整列)
2.1 ソートとは
2.2 単純ソートと選択ソート
説明
プログラム
2.3 バブルソート
説明
プログラム
2.4 シェーカーソート
説明
プログラム
2.5 挿入ソート
説明
プログラム
2.6 シェルソート
説明
シェルソートの原理
プログラム
間隔の選び方
2.7 ヒープソート
ヒープとは
木構造への配列の割り当て
親子の配置ルール
初期ヒープを作る
プログラム
2.8 クイックソート
説明
プログラム

Chapter 3 ソートの応用とマージ
3.1 文字列のソート
説明
プログラム
3.2 レコードのソート
説明
プログラム
3.3 マージ
説明
プログラム
ファイルをマージする
プログラム

Chapter 4 サーチ
4.1 リニアサーチ(線形探索)
説明
プログラム
番兵を立てる
4.2 バイナリサーチ(2分探索)
説明
プログラム

Chapter 5 文字列の検索
5.1 文字列の検索単純法
説明
プログラム
5.2 文字列の検索 BM法
説明
プログラム

Chapter 6 数値計算
6.1 多倍長の数値計算
多倍長計算
配列の用意
配列への値格納と表示
拡張整数の加算
拡張整数の減算
拡張整数の乗算
拡張整数の除算
プログラム
6.2 eの計算
説明
プログラム
6.3 階乗の計算
説明
プログラム
6.4 2の累乗値
説明
プログラム
6.5 円周率の計算
説明
プログラム

Chapter 7 式の処理
7.1 トークン解析
字句の取得
プログラム
7.2 逆ポーランド記法を使う式の解析
式の記述法
逆ポーランド記法に変換する方法
プログラム
変換過程
7.3 逆ポーランド記法の式評価
説明
プログラム
7.4 再帰的な方法による式の解析
説明
プログラム
7.5 電卓プログラム
説明
プログラム

Chapter 8 スタックとキュー
8.1 スタック
スタックとは
用意する関数
プログラム1
プログラム2
8.2 キュー
キューとは
用意する関数
プログラム

Chapter 9 リスト
9.1 リストの機能
リストとは
用意する関数
ヘッダを非ポインタによる
9.2 リストへの追加
9.3 リストの検索
9.4 リストからの削除
9.5 指定位置の要素を処理する
9.6 双方向リスト
9.7 その他のリスト構造
循環リスト
自己組織化探索
領域確保の方法

Chapter 10 木構造
10.1 木の知識
リンクと木
木の部品名称
木の利用
2分木と多分木
順序をつける
10.2 2分探索木
2分探索木とは
データの追加
データの探索
データの削除
10.3 2分木の巡回
10.4 2分木のレベル巡回
10.5 ヒープ
ヒープの要素配置
ヒープの順序付け
10.6 平衡木とAVL木
平衡木
AVL木
10.7 多分木とB木
B木の構成
B木へのデータの追加
B木の探索と利用

Chapter 11 ハッシュ処理
11.1 ハッシュ処理とは
11.2 ハッシュ関数
11.3 かち合いの発生
11.4 クローズドハッシュ法(内部ハッシュ法)
11.5 オープンハッシュ法(外部ハッシュ法)
11.6 ハッシュ関数の工夫
ハッシュ表のサイズ
かち合いを減らす
素数で剰余計算する

Chapter 12 再帰処理
12.1 再帰処理とは
再帰処理の条件
階乗計算をする
12.2 ハノイの塔
12.3 再帰的な発想をする
12.4 バックトラックと八王妃問題
八王妃問題
総当り法
八王妃問題の解き方
効き筋のチェック
プログラム
12.5 その他の再帰プログラム

Chapter 13 お楽しみ
13.1 素数を探す
素数とは
素数を判定する
プログラム1
エラトステネスのふるい
プログラム2
エラトステネスのふるいの拡張
プログラム3
配列要素の規則性を利用
13.2 三山くずし
三山くずしとは
三山くずしの必勝パターン
必勝パターンを作る
プログラム
13.3 小町算
小町算とは
小町算の解を求める
プログラム1
4つの演算子を許可する
プログラム2
13.4 ライフゲーム
ライフゲームとは
ライフゲームのルール
領域の管理
画面のコントロール
プログラム
いろいろな初期パターン