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

本書は情報科学関係の大学や専門学校などの学生を対象にアルゴリズム設計の基礎と応用と題して企画した。通年の教科書として 30 週で一通り終了することを念頭におき,データ構造とアルゴリズムを柱に,プログラミング言語,計算複雑度などにまたがる内容を天下り的になることなく,”読めば理解できる形の説明をできるだけ用意しておく”という試みをし,解説をできるだけ詳しく,例題・演習問題を多く取り上げてできるだけ理解しやすいようにまとめた。 ● 1 章では,実例に基づいてプログラムとは何かを分かりやすく説明することにより,アルゴリズム設計,プログラミングなど不案内な学生への導入とした。 ●基礎的事項は例題を用いて平易な説明による導入を試み,そのため図を多く用い懇切丁寧に解説した。 ●具体例からの一般化や理論的に厳密な証明などもできるだけ記述した。 ●ワークステーションなどのコンピュータ上の C 言語によるプログラム作成を前提にし,これに必要な最小限の解説を本文や付録に組み込むと共に実行例もできるだけ記述した。 ●必要な数学的基礎事項は付録にまとめた。 第 1 章 アルゴリズム設計の概要 1.1 プログラミングとアルゴリズム 1.2 実際のプログラミング 1.3 アルゴリズムとデータ構造 1.4 解き難い問題 1.5 アルゴリズムの設計と解析 1.6 アルゴリズムの評価基準と計算複雑度 第 2 章 コンピュータとプログラム 2.1 コンピュータ内部での文字や数値の扱い 2.2 メモリと CPU 2.3 命令コードとインストラクションポインタ 2.4 プログラムの実行 2.5 スタック領域,フレームポインタ,スタックポインタ 2.6 引数の値と戻り値の受け渡し,変数とスコープ 第 3 章 基本データ構造 3.1 配列 3.2 リスト 3.3 スタックとキュウー 3.4 グラフ 3.5 グラフの実現度 第 4 章 ヒープ 4.1 完全 2 分木 4.2 ヒープとその基本操作 4.3 ヒープの構成法 第 5 章 整列 5.1 バケットソートと基数ソーティング 5.2 選択法 5.3 挿入法 5.4 ヒープソート 5.5 マージソート 5.6 クイックソート 第 6 章 探索 6.1 2 分探索木と対称順 6.2 2 分探索木における基本操作:探索,挿入,削除 6.3 回転 6.4 赤黒木 6.5 赤黒木を実現するプログラム 6.6 ハッシュ法 第 7 章 グラフの基本アルゴリズム 7.1 概要 7.2 無向グラフに対する幅優先探索 7.3 無向グラフに対する深さ優先探索