【中国からのダイレクトメール】I READING Computer Scienceシリーズ・データ構造、アルゴリズム、アプリケーション: C++言語記述 (原書第2版)

編集者の選択

は権威あるデータ構造教科書の第 2 版です。
基本的なデータ構造を完全にカバーしており、CS2 コースに最適な本です。

簡単な紹介

『データ構造、アルゴリズム、およびアプリケーション - C++ 言語記述』は、権威あるデータ構造教科書の第 2 版です。基本的なデータ構造を完全にカバーしており、CS2 コースに最適な本です。著者の Sartaj Sahni は、段階的な説明、直感的で具体的な議論、実践的な応用を通じて、読者が簡単かつ楽しく学ぶことを可能にします。この本の新版は、標準テンプレート ライブラリ (STL) の使用に焦点を当てており、この本で開発されたデータ構造とアルゴリズムを、対応する STL 実装方法と関連付けています。この本には、多くの新しい例や演習も追加されています。
本書に掲載されている応用例がその特徴です。 Sahni 博士は、ソート、圧縮コーディング、画像処理などの側面を含む、データ構造とアルゴリズムごとにいくつかのアプリケーション例を提供します。これらの例は概念と応用を組み合わせ、理論と実践を統合することで概念を理解しやすくし、学習に対する生徒のモチベーションと関心を高めます。
『Computer Science Series・Data Structures, Algorithms and Applications: C++ Language description (Original Book 2nd Edition)』で採用されている実践的な教授法は、理論的概念を豊かにするだけでなく、学生に多数の演習問題を提供します。この本には 800 の演習問題が含まれています) 理解問題や簡単なプログラミングおよびエンジニアリング設計問題を含む複数の演習問題)。さらに、この本の付属 Web サイトには、この本のすべてのプログラム、サンプル データ、実行結果、いくつかの演習の解決策、および結果付きのサンプル テストが含まれています。

著者について

サルタージ・サーニ、フロリダ大学コンピュータおよび情報科学工学の特別教授、欧州科学アカデミー会員、電気電子学会 (IEEE)、コンピューティング機械協会 (ACM)、米国協会の会員科学進歩 (AAAS) およびミネソタ スーパーコンピューティング研究所、カン インド工科大学プルプール校 (LIT) の優秀な卒業生。サーニ博士は、1997 年に IEEE コンピュータ部門の Taylor L Booth Education Award を受賞し、IEEE コンピュータ部門の W.ウォレス・マクダウェル賞と2003年ACMカール・カールストロム特別教育者賞を受賞。彼は現在、ACM ジャーナル「Computing Surveys」の編集長を務めており、17 のジャーナルの編集委員会のメンバーです。彼は、インド工科大学カンプール校で電気工学の学士号を取得し、コーネル大学でコンピュータ サイエンスの修士号および博士号を取得しました。これまでに 250 以上の論文を発表し、15 冊の教科書を執筆しています。彼の研究成果には、効率的なアルゴリズムの分野が含まれます。設計と分析、並列コンピューティング、インターネット、自動設計、医療アルゴリズム。

目次

C++ のデータ構造、アルゴリズム、およびアプリケーション、第 2 版
出版社のメモ
訳者序文
序文
第 1 部 予備知識
第 1 章 C++ のレビュー
1.1 はじめに
1.2 関数とパラメータ
1.2.1 値パラメータの受け渡し
1.2.2 テンプレート機能
1.2.3 参照パラメータ
1.2.4 定数参照パラメータ
1.2.5 戻り値
1.2.6 オーバーロードされた関数
1.3 例外
1.3.1 例外のスロー
1.3.2 例外の処理
1.4 動的なストレージスペースの割り当て
1.4.1 新しい演算子
1.4.2 1次元配列
1.4.3 例外処理
1.4.4 オペレータの削除
1.4.5 2次元配列
1.5 独自のデータ型
1.5.1 クラス通貨
1.5.2 別の記述方法
1.5.3 演算子のオーバーロード
1.5.4 友人と保護クラスのメンバー
1.5.5 #ifndef、#define、#endif ステートメントを追加する
1.6 例外クラスillegalParameterValue
1.7 再帰関数
1.7.1 再帰的な数学関数
1.7.2 概要
1.7.3 C++ 再帰関数
1.8 標準テンプレートライブラリ
1.9 テストとデバッグ
1.9.1 テストとは
1.9.2 テストデータの設計
1.9.3 デバッグ
1.10 参考文献と推奨書籍
第 2 章 プログラムのパフォーマンス分析
2.1 プログラムのパフォーマンスとは
2.2 空間の複雑さ
2.2.1 空間の複雑さの構成要素
2.2.2 例
2.3 時間計算量
2.3.1 時間計算量の構成要素
2.3.2 操作回数
2.3.3 最高、最悪、平均の操作数
2.3.4 ステップ数
第 3 章 漸近記法
3.1 はじめに
3.2 漸近表記
3.2.1 大きなΟ表記
3.2.2 漸近表記ΩとΘ
3.3 漸近数学 (オプション)
3.3.1 ビッグオー表記法
3.3.2 Ω表記
3.3.3 Θ表記
3.3.4 小さなο表記
3.3.5 特徴
3.4 複雑さの分析の例
3.5 実際の複雑さ
3.6 参考文献と推奨書籍
第4章 性能測定
4.1 はじめに
4.2 インスタンスのサイズを選択する
4.3 設計テストデータ
4.4 実験計画
4.5 キャッシュ
4.5.1 単純なコンピュータモデル
4.5.2 キャッシュミスが実行時間に与える影響
4.5.3 行列の乗算
4.6 参考文献と推奨書籍

パート 2 データ構造
第 5 章 線形テーブル - 配列の説明
5.1 データオブジェクトとデータ構造
5.2 線形テーブルのデータ構造
5.2.1 抽象データ型 LinearList
5.2.2 抽象クラス LinearList
5.3 アレイの説明
5.3.1 説明
5.3.2 可変長一次元配列
5.3.3 クラス arrayList
5.3.4 C++ イテレータ
5.3.5 arrayListのイテレータ
5.4 ベクターの説明
5.5 配列に実装された複数のテーブル
5.6 パフォーマンスの測定
5.7 参考文献と推奨書籍
第 6 章 線形テーブル - 連鎖記述
6.1 一方向リンクリスト
6.1.1 説明
6.1.2 チェーンノードの構造体
6.1.3 クラスチェーン
6.1.4 抽象データ型linearListの拡張
6.1.5 クラスextendedChain
6.1.6 パフォーマンスの測定
6.2 循環リンクリストとヘッドノード
6.3 二重リンクリスト
6.4 リンクリストで使用される語彙
6.5 アプリケーション
6.5.1 ボックスの仕分け
6.5.2 基数ソート
6.5.3 凸包
6.5.4 ユニオン検索
第 7 章 配列と行列
7.1 配列
7.1.1 抽象データ型
7.1.2 C++ 配列のインデックス付け
7.1.3 行優先のマッピングと列優先のマッピング
7.1.4 配列の配列を使用した記述
7.1.5 行マスターの説明と列マスターの説明
7.1.6 不規則な 2 次元配列
7.2 マトリックス
7.2.1 定義と運用
7.2.2 クラスマトリックス
7.3 特殊な行列
7.3.1 定義と適用
7.3.2 対角行列
7.3.3 三重対角行列
7.3.4 三角行列
7.3.5 対称行列
7.4 スパース行列
7.4.1 基本概念
7.4.2 単一の線形テーブルで記述する
7.4.3 複数の線形テーブルを使用して説明する
7.4.4 パフォーマンスの測定
第8章 スタック
8.1 定義と適用
8.2 抽象データ型
8.3 アレイの説明
8.3.1 派生クラスとしての実装
8.3.2 クラス arrayStack
8.3.3 パフォーマンス測定
8.4 リンクリストの説明
8.4.1 クラス派生LinkedStack
8.4.2 クラス linkedStack
8.4.3 パフォーマンス測定
8.5 アプリケーション
8.5.1 括弧の一致
8.5.2 ハノイ塔
8.5.3 車両の配置変更
8.5.4 スイッチボックスの配線
8.5.5 オフライン同値クラス問題
8.5.6 迷路ネズミ
8.6 参考文献と推奨書籍
第9章 待ち行列
9.1 定義と適用
9.2 抽象データ型
9.3 アレイの説明
9.3.1 説明
9.3.2 arrayQueueクラス
9.4 リンクリストの説明
9.5 アプリケーション
9.5.1 車両の配置変更
9.5.2 回路配線
9.5.3 グラフ要素の認識
9.5.4 工場シミュレーション
9.6 参考文献と推奨書籍
第 10 章 ジャンプ リストとハッシュ
10.1 辞書
10.2 抽象データ型
10.3 線形テーブルの記述
10.4 ジャンプテーブル表現（オプション）
10.4.1 理想的な状況
10.4.2 挿入と削除
10.4.3 レベルの割り当て
10.4.4 構造体skipNode
10.4.5 クラススキップリスト
10.4.6 SkipList メソッドの複雑さ
10.5 ハッシュテーブルの説明
10.5.1 理想的なハッシュ化
10.5.2 ハッシュ関数とハッシュテーブル
10.5.3 線形探査
10.5.4 チェーンハッシュ
10.6 アプリケーション - テキスト圧縮
10.6.1 LZW圧縮
10.6.2 LZW圧縮の実装
10.6.3 LZW 解凍
10.6.4 LZW解凍の実装
10.6.5 性能評価
10.7 参考文献と推奨書籍
第 11 章 二分木とその他の木
11.1 ツリー
11.2 二分木
11.3 二分木の性質
11.4 二分木の説明
11.4.1 アレイの説明
11.4.2 リンクリストの説明
11.5 バイナリツリーに対する一般的な操作
11.6 バイナリツリートラバーサル
11.7 抽象データ型 BinaryTree
11.8 クラス linkedBinaryTree
11.9 アプリケーション
11.9.1 信号増幅器のセットアップ
11.9.2 ユニオン検索
11.10 参考文献と推奨書籍
第12章 プライオリティキュー
12.1 定義と適用
12.2 抽象データ型
12.3 線形テーブル
12.4 ヒープ
12.4.1 定義
12.4.2 大規模ルートヒープの挿入
12.4.3 大きなルートヒープの削除
12.4.4 大規模ルートヒープの初期化
12.4.5 クラス maxHeap
12.4.6 ヒープと STL
12.5 左高書
12.5.1 高さ優先および幅優先の最大および最小左高さツリー
12.5.2 最大HBLTの挿入
12.5.3 最大HBLTの削除
12.5.4 2 つの最大手 HBLT の合併
12.5.5 初期化
12.5.6 クラス maxHblt
12.6 アプリケーション
12.6.1 ヒープソート
12.6.2 マシンのスケジュール設定
12.6.3 ハフマン符号化
12.7 参考文献と推奨書籍
第 13 章 競争ツリー
13.1 勝者のツリーとアプリケーション
13.2 抽象データ型 WinnerTree
13.3 勝者ツリーの実装
13.3.1 表現
13.3.2 勝者ツリーの初期化
13.3.3 コンテストの再編成
13.3.4 クラスcompleteWinnerTree
13.4 敗者ツリー
13.5 アプリケーション
13.5.1 最初の適合法を使用してボックスの積載問題を解決する
13.5.2 近隣適応法を使用したボックスローディング問題の解決
13.6 参考文献と推奨書籍
第14章 検索ツリー
14.1 定義
14.1.1 二分探索木
14.1.2 二分探索ツリーのインデックス付け
14.2 抽象データ型
14.3 二分探索木の操作と実装
14.3.1 クラス binarySearchTree
14.3.2 検索
14.3.3 挿入
14.3.4 削除
14.3.5 二分探索木の高さ
14.4 同じキーワードを持つ要素を持つ二分探索木
14.5 二分探索ツリーのインデックス付け
14.6 アプリケーション
14.6.1 ヒストグラム
14.6.2 ボックス積載問題に対する最適なマッチング方法
14.6.3 相互分散
第 15 章 検索ツリーのバランスをとる
15.1 AVLツリー
15.1.1 定義
15.1.2 AVLツリーの高さ
15.1.3 AVLツリーの説明
15.1.4 AVL 検索ツリーの検索
15.1.5 AVL検索ツリーの挿入
15.1.6 AVL検索ツリーの削除
15.2 赤黒木
15.2.1 基本概念
15.2.2 赤黒木の説明
15.2.3 赤黒ツリー検索
15.2.4 赤黒ツリーの挿入
15.2.5 赤黒ツリーの削除
15.2.6 実装の詳細と複雑さの分析の検討
15.3 ツリーの分割
15.3.1 はじめに
15.3.2 ツリーの分割操作
15.3.3 変換の複雑さ
15.4 B ツリー
15.4.1 インデクス順次アクセス方式
15.4.2 m 分探索木
15.4.3 次数 m の B ツリー
15.4.4 B ツリーの高さ
15.4.5 B ツリー検索
15.4.6 B ツリーの挿入
15.4.7 B ツリーの削除
15.4.8 ノード構造
15.5 参考文献と推奨書籍
第16章 画像
16.1 基本概念
16.2 アプリケーションとその他の概念
16.3 機能
16.4 抽象データ型グラフ
16.5 重み付けされていないグラフの説明
16.5.1 隣接行列
16.5.2 隣接リンクリスト
16.5.3 隣接配列
16.6 重み付きグラフの説明
16.7 クラスの実装
16.7.1 さまざまなクラス
16.7.2 隣接行列クラス
16.7.3 チェーンクラスの展開
16.7.4 リンクリストクラス
16.8 グラフトラバーサル
16.8.1 幅優先検索
16.8.2 幅優先検索の実装
16.8.3 bfs のメソッド グラフ::複雑さの分析
16.8.4 深さ優先検索
16.8.5 深さ優先検索の実装
16.8.6 メソッドgraph::dfsの複雑さの分析
16.9 アプリケーション
16.9.1 パスの検索
16.9.2 接続されたグラフとその構成
16.9.3 スパニングツリー

第 3 部 アルゴリズムの設計方法
第17章 貪欲なアルゴリズム
17.1 最適化問題
17.2 貪欲なアルゴリズムの考え方
17.3 アプリケーション
17.3.1 コンテナの積み込み
17.3.2 0/1 ナップサック問題
17.3.3 トポロジカルソート
17.3.4 二部構成の適用範囲
17.3.5 単一ソースの最短パス
17.3.6 最小コストのスパニングツリー
17.4 参考文献と推奨書籍
第18章 分割統治
18.1 アルゴリズム的思考
18.2 アプリケーション
18.2.1 不完全なチェス盤
18.2.2 マージソート
18.2.3 クイックソート
18.2.4 選択
18.2.5 最も近い点のペア
18.3 再帰方程式を解く
18.4 複雑さの下限
18.4.1 minmax 問題の下限
18.4.2 ソートアルゴリズムの下限
第 19 章 動的プログラミング
19.1 アルゴリズム的思考
19.2 アプリケーション
19.2.1 0/1 ナップサック問題
19.2.2 行列乗算チェーン
19.2.3 すべての頂点ペア間の最短経路
19.2.4 負の値を含む単一ソースの最短パス
19.2.5 ネットグループの交差のないサブセット
19.3 参考文献と推奨書籍
第20章 後戻り
20.1 アルゴリズム的思考
20.2 アプリケーション
20.2.1 コンテナの積み込み
20.2.2 0/1 ナップサック問題
20.2.3 最大完全サブグラフ
20.2.4 巡回セールスマン問題
20.2.5 回路基板の配置
第21章 分岐と区切り
21.1 アルゴリズム的思考
21.2 アプリケーション
21.2.1 コンテナの積み込み
21.2.2 0/1 ナップサック問題
21.2.3 最大完全サブグラフ
21.2.4 巡回セールスマン問題
21.2.5 回路基板の配置

序文/序文

C++ のデータ構造、アルゴリズム、およびアプリケーション、第 2 版 データ構造とアルゴリズムの研究は、コンピューター サイエンスとエンジニアリングの基礎です。この分野の習熟は、コンピュータ リソースを効率的に利用するプログラムを開発するために不可欠です。したがって、すべてのコンピューター サイエンスとエンジニアリングの専攻には、この側面に特化した 1 つ以上のコースがあります。一般的に、最初のプログラミング コースでは、データ構造とアルゴリズムの基礎 (データ構造のスタックとキュー、アルゴリズムの並べ替え、行列演算) を紹介します。 2 番目のプログラミング コースでは、データ構造とアルゴリズムに関する体系的な知識を紹介します。その後、データ構造とアルゴリズムを徹底的に学習することができます。これには通常 1 つまたは 2 つのコースが必要です。
コンピューターサイエンスとエンジニアリングの学部専攻が多数あるため、多くの大学がコースの統合を余儀なくされています。たとえば、フロリダ大学では、データ構造とアルゴリズムに関する 1 学期制のコースのみが学部生に提供されています。このコースを受講する前に、学生は Java プログラミングと離散数学を 1 学期学習している必要があります。
この本は、データ構造とアルゴリズムに特化した 2 つ以上のコース、または関連する総合コースで使用できます。この本は 3 つの部分に分かれています。第 1 章から第 4 章までの第 1 部は、C++ プログラミングの概念とプログラムのパフォーマンスの分析および測定方法を復習することを目的としています。 C 言語プログラミングに慣れている学生は、第 1 章を学習することで C++ に移行できるはずです。第 1 章は C++ の入門知識ではありませんが、パラメータの受け渡し、テンプレート関数、動的ストレージ割り当て、再帰、クラス、継承、例外スロー、キャプチャなど、学生を混乱させることが多い C++ の基本概念がいくつか含まれています。第 2 章と第 3 章では、プログラムのパフォーマンスを分析および測定する方法 (操作のカウント、実行ステップ、漸近表記法 (大きな O、Ω、Θ、小さな o)) について概説します。第 4 章では、プログラムのパフォーマンスの実験的測定を検討し、実行時の測定に対するキャッシュ メモリの影響について簡単に説明します。第 2 章では、プログラムのパフォーマンス分析手法の応用を通じて、プログラミング入門コースで遭遇する典型的な基本アルゴリズムを詳しく学習します。単純なソート アルゴリズム (バブル ソート、選択ソート、挿入ソート、カウンティング ソート)、逐次検索、ホーナー規則の使用などです。多項式の評価と行列演算 (行列の加算、行列の転置、行列の乗算) を実行します。第 3 章では、二分探索アルゴリズムを学習します。第 2 章から第 4 章の主な目的は、プログラムのパフォーマンスを分析および測定する方法を学ぶことですが、学生が一連の基本的なアルゴリズムに習熟できるようにすることもできます。
本書の第 5 章から第 16 章までの第 2 部では、データ構造について詳しく説明します。第 5 章と第 6 章では、それぞれデータの配列記述法とポインタ（またはチェーン）記述法を検討し、データ構造研究の枠組みを構築します。これら 2 つの章では、これら 2 つのデータ記述方法を使用して C++ クラスを作成し、線形テーブル データ構造を記述します。実験データを使用して、線形テーブルを記述する際のさまざまなデータ記述方法のパフォーマンスを比較しました。第 2 部の第 7 章以降では、第 5 章と第 6 章の記述方法を適用して、配列と行列 (第 7 章)、スタック (第 8 章)、キュー (第 9 章) などの他のデータ構造について説明します。第 10 章、第 14 章、および第 15 章)、バイナリ ツリー (第 11 章)、優先キュー (第 12 章)、レース ツリー (第 15 章)、およびグラフ (第 16 章)。
データ構造を扱う場合、本書は類似性または同一性の点で C++ 標準テンプレート ライブラリ (STL) で使用される構造と互換性を持たせるよう努めます。たとえば、第 5 章の線形テーブル データ構造は、STL のベクトル状のパターンに従って構築されています。 copy、min、max などの STL 関数は、学生がこれらの関数に慣れることができるように、本書全体で使用されています。
本書の第 3 部 (第 17 章から第 21 章まで) では、一般的に使用されるアルゴリズム設計手法について説明します。これらの手法には、貪欲アルゴリズム (第 17 章)、分割統治アルゴリズム (第 18 章)、動的プログラミング (第 19 章)、バックトラッキング アルゴリズム (第 20 章)、および分岐限定アルゴリズム (第 21 章) が含まれます。また、2 つの下限 (minmax 問題と並べ替え問題) (セクション 18.4)、マシン スケジューリングの近似アルゴリズム (セクション 12.6.2)、ボックス ローディング アルゴリズム (セクション 13.5)、および 0/1 ナップザック問題 (セクション 17.3.2) の証明も含まれています。祭り）。セクション 12.6.2 では、NP 複合問題についても簡単に紹介します。
本書の特徴は応用を重視していることだ。この本の各データ構造とアルゴリズム設計は、複数のアプリケーション例を通じて実証されています。通常、各章の最後のセクションでは、この章で紹介するデータ構造または設計方法の具体的な応用例を示します。多くの場合、アプリケーション例は章の最初のセクションにも含まれています。これらのアプリケーション例には、ソート (バブル ソート、選択ソート、挿入ソート、カウンティング ソート、ヒープ ソート、マージ ソート、クイック ソート、ボックス ソート、基数ソート、トポロジカル ソート)、行列演算 (行列の加算、行列の転置、行列) など、多くの側面が含まれます。乗算）; 回路設計の自動化（回路ネットグループの検索、回路配線、コンポーネントの折りたたみ、スイッチボックスの配線、信号増幅器の設定、クロス分配、回路基板の配置）; 圧縮符号化（LZW圧縮、ハフマン符号化）; 計算幾何学（凸包および最近点ペア); シミュレーション (工場シミュレーション); 画像処理 (グラフ要素の注釈); 興味深い数学 (ハノイの塔、不完全なチェス盤、迷路マウス); スケジューリング (LPT スケジューリング); 最適化 (ビン詰め問題) 、コンテナーの積載、0 /1 バックパック、行列乗算チェーン)、統計 (ヒストグラム、最大値と最小値の検索、k 番目の最小値の検索)、グラフ理論 (スパニング ツリー、プリミティブ、最短経路、最大完全部分図、二部カバレッジ、巡回セールスマン) 。これらの応用例を学ぶのに関連分野の予備知識は必要ありません。この知識は本書に含まれているため、学生は学習への関心を高めることができます。
私たちは、実用的なアプリケーションとデータ構造およびアルゴリズム設計方法に関する基礎研究を密接に統合することで、学生の専門的な関心をさらに高めることができることを願っています。この本とこの本の Web サイトにある 800 以上の演習を完了することで、学生の知識はより豊かで確実になります。