《數據結構與面向對象程式設計（C++版）（第4版）》是2012年清華大學出版社出版的圖書，作者是Michael Main、Walter Savitch。
基本介紹
- 書名：數據結構與面向對象程式設計（C++版）（第4版）
- 作者：Michael Main、Walter Savitch
- 譯者：金名 等
- ISBN：9787302278818
- 定價：89元
- 出版社：清華大學出版社
- 出版時間：2012-4-17
- 裝幀：平裝
圖書簡介,前言,目錄,
圖書簡介
本書是為計算機科學專業的第二門課程編寫的，在美國很多大學中稱之為CS2。本書的重點是規範說明、設計和實現，以及基本數據類型的使用，這些內容都將在第二學期的課程中介紹。而且，本書還介紹了很多重要的編程技術，提供了有關抽象技術、面向對象程式設計、算法的大O時間分析以及排序等內容。
本書假設學生已經完成了“計算機科學導論”和“程式設計”課程的學習，但本書也包括了在第一門課中沒有完全涵蓋的內容（如遞歸和指針）。本書使用的是C++語言，但對C++類的介紹是從零開始的，因此，對於那些以C而不是以C++作為程式設計入門語言的學生來說，本書也是適用的。根據筆者的經驗，這類學生需要對C++輸入和輸出技術（參見附錄F），以及C++參數類型（參見第2章）有所了解。當C程式設計師克服了有關輸入/輸出和參數的障礙後，就能領略C++的類和面向對象特性。需要指出的是，根據學生不同的知識背景，本書有多種不同的學習方案。對於那些有較強套用背景的學生來說，可以有選擇地學習本書的內容。
本書假設學生已經完成了“計算機科學導論”和“程式設計”課程的學習，但本書也包括了在第一門課中沒有完全涵蓋的內容（如遞歸和指針）。本書使用的是C++語言，但對C++類的介紹是從零開始的，因此，對於那些以C而不是以C++作為程式設計入門語言的學生來說，本書也是適用的。根據筆者的經驗，這類學生需要對C++輸入和輸出技術（參見附錄F），以及C++參數類型（參見第2章）有所了解。當C程式設計師克服了有關輸入/輸出和參數的障礙後，就能領略C++的類和面向對象特性。需要指出的是，根據學生不同的知識背景，本書有多種不同的學習方案。對於那些有較強套用背景的學生來說，可以有選擇地學習本書的內容。
前言
本書是為計算機科學專業的第二門課程編寫的，在美國很多大學中稱之為CS2。本書的重點是規範說明、設計和實現，以及基本數據類型的使用，這些內容都將在第二學期的課程中介紹。而且，本書還介紹了很多重要的編程技術，提供了有關抽象技術、面向對象程式設計、算法的大O時間分析以及排序等內容。
本書假設學生已經完成了“計算機科學導論”和“程式設計”課程的學習，但本書也包括了在第一門課中沒有完全涵蓋的內容（如遞歸和指針）。本書使用的是C++語言，但對C++類的介紹是從零開始的，因此，對於那些以C而不是以C++作為程式設計入門語言的學生來說，本書也是適用的。根據筆者的經驗，這類學生需要對C++輸入和輸出技術（參見附錄F），以及C++參數類型（參見第2章）有所了解。當C程式設計師克服了有關輸入/輸出和參數的障礙後，就能領略C++的類和面向對象特性。需要指出的是，根據學生不同的知識背景，本書有多種不同的學習方案。對於那些有較強套用背景的學生來說，可以有選擇地學習本書的內容。
本版新增內容
C++標準模板庫（Standard Template Library，STL）在我們的課程中起著更大的作用了，在本書中增加了精心挑選的素材給予介紹。對我們來說，重要的是讓我們的學生既能理解如何在應用程式中使用STL類，也能掌握實現這些類（或類似類）的途徑。基於這種思考，本版進行了以下修改：
* 新增了2.6節，利用pair類對標準模板庫進行早期介紹。我們在學生還沒有完全理解模板之前，就向他們介紹STL。
* 在3.4節提前介紹multiset類和STL疊代器。這是介紹這些內容的好地方，因為學生剛剛明白了如何實現他們自己的第一個集合類（即bag類），該類是基於multiset類的。
* 在4.5節繼續介紹STL的string類，在這裡很適合學生用動態數組來實現自己的string類。
* 新增5.6節，對3個類似的STL類：vector、list和deque進行比較。此時，學生有足夠的知識來理解典型的vector和list類實現。
* 在6.3節首次介紹STL算法，在11.2節和13.4節進行了擴展介紹。
* 新增8.4節，介紹了聯合使用動態數組和指針，實現STL的deque類的細節。
* 在12.6節討論了TR1庫中的散列表。
每種數據類型的5個介紹步驟
總體來說，第4版繼續介紹如下的經典數據結構：集合、包（或多集）、序列表、有序列表（利用“小於”操作符排序）、棧、佇列、表和圖。此外，還補充介紹了一些數據結構，比如優先佇列。上述每種數據結構都將按照如下固定的模式來進行介紹。
第1步：抽象地理解數據結構。在這一層上，學生從概念和圖形的層面上，得到對數據結構及其操作的理解。例如，學生可以可視化一個棧及其壓入和彈出元素的操作。簡單的應用程式更容易理解，而且可以手工完成，比如使用棧來顛倒一個單詞的字母順序。
第2步：把數據結構的規範說明編寫成一個C++類。在這一步中，學生明白和理解如何為實現數據類型的C++類編寫規範說明。該規範說明包括構造函式、公用成員函式的原型，以及其他公用屬性（比如一個用於確定棧的最大尺寸的基本常量）。每個成員函式的原型都給出了前置條件和後置條件，完整地描述了該函式的行為。在這一層很重要的是，讓學生明白規範說明與任何實現技術無關。事實上，相同的規範說明可以用於描述相同數據類型的多種不同實現。
第3步：使用數據類型。有了規範說明，學生就可以編寫小型的應用程式或演示程式，來展示所使用的數據結構。這些應用程式只是基於數據類型的規範說明，還沒有涉及實現。
第4步：選擇適當的數據結構，並繼續設計和實現數據類型。在對數據類型有了一個好的抽象理解之後，就可以選擇一個恰當的數據結構，比如固定大小的數組、動態數組、節點鍊表或節點二叉樹。對於很多數據類型來說，最初的設計和實現會選擇簡單的方式，比如固定大小的數組。隨後，我們將用更複雜的基本結構來重新設計和重新實現相同的數據結構。
由於本書使用的是C++類，對於某個數據類型的實現，將有多種可供選擇的數據結構（比如數組、指針等）來作為類的私有成員變數。對於每個實現的類，我們強調應清楚理解私有成員變數與數據類型抽象表示之間的關聯規則。我們要求每個學生套用簡潔的語言寫出這些規則（我們稱之為抽象數據類型的不變式）。一旦不變式編寫完畢後，就可以繼續實現各種成員函式了。不變式有助於編寫正確的函式，原因有兩條：（1）當函式開始運行時，每個函式（構造函式除外）都知道不變式已為真；（2）當函式結束運行時，每個函式（析構函式除外）都要確保不變式為真。
第5步：分析實現。每個實現的分析包括正確性、靈活性（例如固定大小還是動態大小）以及各種操作的時間分析（使用大O表示法）。當同一種數據類型以多種不同的方式來實現時，學生就可以有很好的機會對它們進行分析。
本課程結束時，學生將學到什麼
在本課程結束時，學生將可以徹底理解數據類型了。他們知道如何使用數據類型，如何以多種不同的方式來實現數據類型，知道不同實現方法的實際效果，可以使用大O表示法來分析出各種實現的效率，通過類的不變式來論證各種實現的正確性。
本課程對今後學習有持久重要影響的是，在本課程中學生親身體驗了各種規範說明、設計和實現的過程。本課程對提高學生效率分析和正確性論證的能力也有很重要的幫助。但最重要的一點是，本課程向學生揭示了類可以在很多情況下很容易地使用。學生不再需要從零開始編寫代碼。我們告訴學生，將來某一天，當他們考慮某個問題時，會突然發現大量工作可以用bag類、stack類、queue類或其他類來完成。這些工作根本不需要他們自己去做什麼，他們只需把在本課程中編寫的bag類、stack類、queue類或其他類拿出來用就可以，無需任何修改。更多的情況是，他們可以使用標準數據類型庫（比如C++標準模板庫）中各種熟悉的數據類型。事實上，本書中所介紹的數據類型是標準模板庫中的精簡版本，因此，當學生進一步學習真正的標準模板庫時，他們就有了一個較為熟悉的基礎知識。在這個基礎上進行設計實現時，就知道哪種數據類型是他們最需要的了，他們也就成為了真正的程式設計師。
其他基礎知識
在本課程中，除了介紹基本的數據結構知識外，還為進行“真正的程式設計”所需的其他知識打下基礎，具體如下。
1. 面向對象程式設計
通過讓學生深入理解C++類，為面向對象程式設計（Object-Oriented Programming，OOP）打下基礎。在課程早期會介紹有關類的重要內容：成員函式的表示法，私有成員與公用成員的分離，構造函式的作用，以及操作符重載等。這些內容足以讓學生順利而興奮地開始類的學習。
當首次使用動態記憶體（第4章）時，將進一步介紹類的更多重要特性。此時，需要介紹另外3個方面的內容：複製構造函式、重載後的賦值操作符和析構函式。通過第一次使用動態記憶體時來介紹OOP的這些內容，可以給學生一個有關動態記憶體的具體藍圖。動態記憶體是一種可以拿來使用但隨後必須收回的資源。
從概念上來說，OOP最大的創新在於通過繼承實現軟體重用。當然，也可以在數據結構課程開始時就介紹繼承（例如，把set類實現為bag類的一個子類）。但是，過早介紹會使得過多地關注太多新概念，影響對基本數據結構的理解。因此，在我們的課程中，將繼承放在最後介紹。但對繼承的概述（14.1節和14.2節）可以在理解了複製構造函式之後就進行。基於這種想法，一些教師可能希望在棧與佇列之前講解第14章。
另一種方式是，對於那些已經了解類的基本知識的學生，讓他們早些開始進行繼承項目（比如14.2節的生態系統或14.3節的遊戲引擎），而其他學生則先學習類。
2. 模板
模板函式和模板類是標準模板庫的一個重要部分，使得程式設計師可以很容易地修改容器類中的基本數據項的類型。模板類還可以在一個程式中使用某個類的多個不同實例。同樣，在棧（第7章）之前學習和使用模板（第6章）很重要，因為對使用了兩種棧的表達式求值是一個很重要的套用。
3. 疊代器
疊代器是標準模板庫的另一個重要部分，使得程式設計師可以很容易地遍歷容器對象中的數據項（比如set類或bag類中的元素）。這種疊代器可以是內部的（實現為容器類的成員函式），也可以是外部的（由一個單獨的類來實現，該類是容器類的友元）。我們在講述第一個容器類（3.2節的sequence類）時引入了內部疊代器。在第6章需要時，給bag類添加了一個內部疊代器。此時，還討論了更複雜的外部疊代器，學生應該明白外部疊代器的優點。在本書中，疊代器為許多編程項目提供了一個很好的選擇，例如，實現一個外部bag疊代器（第6章），或使用棧來實現二叉搜尋樹的內部疊代器（第10章）。
4. 遞歸
第一學期有時候會向學生介紹遞歸。但第一學期的很多示例是尾遞歸，其中，函式的最後一步是遞歸調用。這可能會給學生一個錯誤的印象，認為遞歸只不過是一個循環。鑒於此，在第二學期的課程中，儘量避免過早地使用尾遞歸。例如，鍊表中的遍歷和其他操作都可以用尾遞歸來實現，但如果這樣做，其結果是增強對遞歸的錯誤認識（當學生在操作含有成千上萬個數據項的鍊表時，應忘記尾遞歸的鍊表操作，以免出現潛在的運行時棧溢出）。
因此，在第二學期的課程中，我們重點介紹的是使用除尾遞歸之外的其他遞歸解決方案。第9章就是遵循這種理念來介紹3個示例的。其中的兩個示例（產生隨機分形和穿越迷宮）對學生會有較大的觸動。在我講授的課堂上，先講授遞歸（第9章），緊接著講授樹（第10章），因為在遞歸樹算法中，遞歸是非常重用的。但是，對於那些希望更加強調遞歸的教師來說，可能會提前講授遞歸，有的甚至提到第2章之前。
在學時比較充裕的課程中，可以學習高級樹項目（第11章），分析遞歸樹算法，解釋一下保持樹平衡的重要性。這兩者都提高了最壞情況下的性能，避免出現潛在的運行時棧溢出。
5. 搜尋和排序
第12章和第13章介紹了搜尋和排序算法的基礎知識。第12章回顧了有序數組的二叉搜尋，許多學生之前已經見過這些內容了。第13章回顧了簡單的二次排序方法，但該章的重點是快速算法：遞歸合併排序（最壞情況下的運行時間為O(n log n)）和Tony Hoare遞歸快速排序（平均運行時間為O(n log n)）以及基於樹的堆排序（最壞情況下的運行時間為O(n log n)）。此外還對C++標準模板庫的排序函式做了新的介紹。
高級項目
本書提供了很多項目，可以用更高級的類來實現，或者讓那些在設計大型類方面有紮實基礎的學生來完成。部分高級項目如下：
* 使用動態記憶體的polynomial類（4.6節）。
* 標準庫疊代器，這是用於bag類的疊代器的最高級實現（6.3節～6.5節）。
* 用於二叉搜尋樹的疊代器（第10章的編程項目）。
* 用鍊表（第8章的項目）或堆（11.1節）實現的優先佇列。
* 用B-樹（11.3節）實現的set類。我們對這個項目進行了全面介紹，提供了足夠的信息，以便學生無需參考其他教材，就可以實現該類。在我們的課程中，我們已經成功指導一些優先的學生獨立完成該項目。
* 使用繼承的項目，如14.2節的生態系統項目。
* 使用抽象類實現繼承項目，比如14.3節的game基類（利用該類可以很容易地實現兩玩家的遊戲，比如Othello或connect 4）。
* 第15章的graph類以及相關的圖算法。這是優先學生可能獨立完成的另一個案例。
C++語言特性
C++是一種具有很多高級特性的複雜語言，在第二學期的課程中不會觸及到這些內容。但本書將力求介紹所遇到的那些特性。在本書的第1版中，介紹了當年C++的兩個特性：新的布爾數據類型（參見圖2.1）和靜態成員常量（參見3.1節）。關於靜態成員變數的使用要求在1998年發布的標準中進行了修改，本書已經體現了這種修改（現在，常量的聲明必須在類定義內部和外部同時進行）。1998標準的另一個主要新特性是名稱空間的使用，在這本書第2版中也已經體現了。一些老式的編譯器可能不支持這兩種新特性。為此，我們給出了一些解決這些問題的輔助辦法（參見附錄E），以及一些有關下載和安裝GNU g++編譯器的幫助（參見附錄K）。
章節安排的靈活性
本書在編寫方式上給予了教師很大的選擇空間，他們可以根據特定背景的學生調整教學內容，或者有選擇地先講授某些章節。本前言的最後給出了本書章節之間的相互關係。兩個方框之間的連線表明上一個方框中的內容必須在下一個方框中的內容之前講授。
這裡給出了關於本書內容講授次序的一些參考建議：
* 典型課程。從第1～10章開始，如果學生已經具備C++類的基礎知識，可以跳過第2章的部分內容。這其中的大多數章節可以在一周內講授完，但第5章、第6章、第9章和第10章則可能需要多一些的時間。通常，我們是用13周的時間來講授這些內容，包括考試時間以及講授鍊表和樹的時間。剩餘時間可以用來講授第11章或12.1節和第13章。
* 側重面向對象程式設計的課程。如果學生在其他課程中已經學習了排序與搜尋，那么就有時間來重點學習面向對象程式設計了。第1～4章可以詳細講授，然後介紹派生類（14.1節）。此時，可以讓學生做一些有趣的OOP項目，比如14.2節的生態系統或14.3節的遊戲。然後講授基本的數據結構（第5～8章），把佇列實現為一個派生類（14.3節），最後以第9章和第10章結束本課程，重點強調遞歸成員 函式。
* 快速課程。把第1～3章作為第一周的自學內容，從第4章開始講授，這樣在學期末會留出兩三周的時間，於是學生可以在搜尋、排序以及其他高級主題上投入更多的時間。
我們也曾經以更快的速度來講授本課程，不講授棧和佇列（但把這些章節作為自學內容）。
* 提前講授遞歸或提前講授排序。前一到三周的時間用於講授遞歸思想，然後閱讀第1章和第9章的內容，可能還要補充遞歸項目的學習。
如果提前講授遞歸，那么也就可以在介紹C++類之前，講授二叉搜尋（12.1節）和大部分的排序算法（第13章）。
目錄
第1章 軟體開發的階段 1
1.1 規範說明、設計與實現 2
1.1.1 概念設計：問題分解 3
1.1.2 前置條件與後置條件 4
1.1.3 使用由其他程式設計師提供的
函式 6
1.1.4 有關ANSI/ISO C++
標準的實現問題 8
1.1.5 本節自測練習 11
1.2 運行時間分析 12
1.2.1 台階計數問題 12
1.2.2 大O表示法 16
1.2.3 C++函式的時間分析 17
1.2.4 最壞情況、平均情況以及
最好情況下的時間分析 19
1.2.5 本節自測練習 19
1.3 測試與調試 20
1.3.1 選擇測試數據 20
1.3.2 邊界值 20
1.3.3 完全代碼測試 21
1.3.4 調試 21
1.3.5 本節自測練習 22
1.4 本章小結 22
本章自測練習參考答案 23
第2章 抽象數據類型與C++類 25
2.1 類與成員 25
2.1.1 編程示例：節流閥類
throttle 25
2.1.2 使用類 29
2.1.3 throttle類的演示小程式 30
2.1.4 實現成員函式 31
2.1.5 可以調用其他成員的
成員函式 34
2.1.6 本節自測練習 34
2.2 構造函式 35
2.2.1 throttle類的構造函式 35
2.2.2 修訂throttle類的成員
函式 37
2.2.3 內聯成員函式 38
2.2.4 本節自測練習 39
2.3 使用名稱空間、頭檔案與
實現檔案 39
2.3.1 創建名稱空間 40
2.3.2 頭檔案 40
2.3.3 實現檔案 44
2.3.4 使用名稱空間裡的數據項 46
2.3.5 本節自測練習 48
2.4 類與參數 49
2.4.1 編程示例：point類 49
2.4.2 參數默認值 52
2.4.3 參數 53
2.4.4 當函式的返回值的數據
類型為類時 58
2.4.5 本節自測練習 59
2.5 操作符重載 60
2.5.1 二元比較操作符重載 60
2.5.2 二元算術操作符重載 61
2.5.3 輸入輸出操作符重載 62
2.5.4 友元函式 64
2.5.5 point類匯總 66
2.5.6 操作符重載小結 68
2.5.7 本節自測練習 69
2.6 標準模板庫與pair類 69
2.7 本章小結 70
本章自測練習參考答案 71
編程項目 73
第3章 容器類 81
3.1 bag類 81
3.1.1 bag類的規範說明 81
3.1.2 bag類的文檔說明 88
3.1.3 bag類的演示程式 91
3.1.4 bag類的設計 93
3.1.5 類的不變式 94
3.1.6 bag類的實現 95
3.1.7 bag類的集成 101
3.1.8 bag類的測試 104
3.1.9 bag類的分析 105
3.1.10 本節自測練習 106
3.2 編程項目：sequence類 107
3.2.1 sequence類的規範說明 107
3.2.2 sequence類的文檔說明 111
3.2.3 sequence類的設計 113
3.2.4 sequence類的偽代碼實現 114
3.2.5 本節自測練習 116
3.3 互動式測試程式 116
本節自測練習 121
3.4 STL中的multiset類及其疊代器 122
3.4.1 multiset模板類 122
3.4.2 multiset類的一些成員 123
3.4.3 疊代器與[...)模式 123
3.4.4 測試疊代器的相等性 126
3.4.5 multiset類的其他操作符 126
3.4.6 不合法的疊代器 126
3.4.7 本節自測練習 128
3.5 本章小結 128
本章自測練習參考答案 128
編程項目 131
第4章 指針與動態數組 138
4.1 指針與動態記憶體 138
4.1.1 指針變數 139
4.1.2 指針與賦值操作符一起
使用 140
4.1.3 動態變數與new操作符 142
4.1.4 使用new操作符為
動態數組分配記憶體 143
4.1.5 記憶體堆與bad_alloc
異常 144
4.1.6 delete操作符 145
4.1.7 本節自測練習 147
4.2 把指針與數組作為參數 147
4.2.1 以指針作為值參數 147
4.2.2 數組參數 149
4.2.3 以指針或數組作為常量
參數 150
4.2.4 以指針作為引用參數 152
4.2.5 本節自測練習 153
4.3 具有動態數組的bag類 156
4.3.1 指針成員變數 156
4.3.2 成員函式按需分配記憶體 157
4.3.3 值語義 161
4.3.4 析構函式 163
4.3.5 修訂後的bag類定義 164
4.3.6 修訂後的bag類實現 165
4.3.7 修訂後的bag類集成 170
4.3.8 本節自測練習 172
4.4 有關動態類的說明 172
4.4.1 4條規則 173
4.4.2 複製構造函式的特殊
重要性 173
4.4.3 本節自測練習 174
4.5 STL的string類與編程項目 174
4.5.1 以null結尾的字元串 174
4.5.2 初始化字元串變數 175
4.5.3 空字元串 175
4.5.4 讀寫字元串變數 175
4.5.5 strcpy函式 176
4.5.6 strcat函式 177
4.5.7 strlen函式 177
4.5.8 strcmp函式 178
4.5.9 string類的規範說明 178
4.5.10 string類的構造函式 180
4.5.11 重載operator[ ] 181
4.5.12 其他重載成員 181
4.5.13 string類的其他操作 182
4.5.14 string類的設計 182
4.5.15 string類的實現 183
4.5.16 string類的演示程式 185
4.5.17 串聯輸出操作符 186
4.5.18 聲明常量對象 187
4.5.19 由構造函式產生的類型
轉換 187
4.5.20 在表達式中使用
已重載的操作符 187
4.5.21 本章設計的string類與C++
庫的string類 188
4.5.22 本節自測練習 188
4.6 編程項目：polynomial類 188
4.7 本章小結 191
本章自測練習參考答案 192
編程項目 194
第5章 鍊表 196
5.1 鍊表的基本節點類 196
5.1.1 為節點聲明類 196
5.1.2 在鍊表節點中使用
typedef語句 197
5.1.3 頭指針和尾指針 197
5.1.4 空指針NULL 198
5.1.5 頭指針或尾指針為NULL
的含義 199
5.1.6 節點類構造函式 199
5.1.7 節點類成員函式 200
5.1.8 成員選擇操作符 201
5.1.9 本節自測練習 204
5.2 鍊表工具包 205
5.2.1 鍊表工具包的頭檔案 205
5.2.2 計算鍊表的長度 206
5.2.3 鍊表的參數 209
5.2.4 在鍊表頭插入新節點 210
5.2.5 在非鍊表頭的其他位置
插入新節點 212
5.2.6 在鍊表中查找節點 215
5.2.7 根據節點的位置在鍊表中
尋找節點 217
5.2.8 鍊表複製 218
5.2.9 在鍊表頭刪除節點 221
5.2.10 在非鍊表頭刪除節點 222
5.2.11 清空鍊表 223
5.2.12 鍊表工具包的集成 224
5.2.13 使用鍊表工具包 228
5.2.14 本節自測練習 228
5.3 用鍊表實現bag類 229
5.3.1 第3個bag類的規範
說明 229
5.3.2 第3個bag類的類定義 230
5.3.3 如何使bag類的value_
type與節點類的value_
type相匹配 233
5.3.4 在類中使用動態記憶體
應遵循的規則 234
5.3.5 第3個bag類的實現 234
5.3.6 第3個bag類的集成 241
5.3.7 本節自測練習 244
5.4 編程項目：用鍊表實現
sequence類 244
5.4.1 關於修訂後的sequence
類的設計建議 245
5.4.2 關於修訂後的sequence
類的值語義 246
5.4.3 本節自測練習 246
5.5 動態數組、鍊表與雙向鍊表 246
5.5.1 做出抉擇 248
5.5.2 本節自測練習 249
5.6 標準模板庫的vector、list和
deque類 249
本節測試練習 252
5.7 本章小結 252
本章自測練習參考答案 252
編程項目 257
第6章 用模板、疊代器和STL
進行軟體開發 261
6.1 模板函式 261
6.1.1 模板函式的語法 263
6.1.2 使用模板函式 263
6.1.3 交換兩個值的模板函式 265
6.1.4 模板函式的參數匹配 266
6.1.5 在數組中查找最大項
的模板函式 267
6.1.6 在已排序數組中插入一個
數據項的模板函式 268
6.1.7 本節自測練習 270
6.2 模板類 270
6.2.1 模板類的語法 270
6.2.2 進一步了解模板類實現
檔案 277
6.2.3 模板類成員函式的參數
匹配 278
6.2.4 使用模板類 278
6.2.5 詳細討論上一個演示
程式 281
6.2.6 本節自測練習 282
6.3 STL算法與疊代器的使用 282
6.3.1 STL算法 282
6.3.2 標準疊代器的類型 283
6.3.3 數組的疊代器 285
6.3.4 本節自測習題 285
6.4 節點模板類 286
6.4.1 返回引用類型的函式 287
6.4.2 將引用返回值複製到
別處時會發生什麼 288
6.4.3 這裡成員函式data
需要兩個版本 288
6.4.4 新節點類的頭檔案和實現
檔案 289
6.4.5 本節自測練習 297
6.5 鍊表的疊代器 297
6.5.1 節點疊代器 297
6.5.2 從std::iterator派生
而來的節點疊代器 299
6.5.3 節點疊代器的私有
成員變數 300
6.5.4 節點疊代器的構造函式 300
6.5.5 節點疊代器的*操作符 300
6.5.6 節點疊代器兩個版本
的 ++ 操作符 300
6.5.7 節點疊代器的相等和不相
等比較 302
6.5.8 常量集合的疊代器 302
6.5.9 本節自測練習 304
6.6 含疊代器的鍊表版bag模板類 305
6.6.1 如何為容器類提供
疊代器 305
6.6.2 bag類疊代器 306
6.6.3 將疊代器定義在bag
類中的原因 307
6.6.4 本節自測練習 314
6.7 本章小結與5個bag類的小結 314
本章自測練習答案 315
編程項目 318
第7章 棧 320
7.1 STL的stack類 320
7.1.1 標準庫的stack類 321
7.1.2 編程示例：翻轉單詞 322
7.1.3 本節自測練習 323
7.2 棧的套用 323
7.2.1 編程示例：括弧的匹配 323
7.2.2 編程示例：算術表達
式求值 325
7.2.3 算術表達式求值的
規範說明 326
7.2.4 算術表達式求值的設計 326
7.2.5 算術表達式求值的實現 331
7.2.6 計算器程式使用的函式 332
7.2.7 算術表達式求值的
測試與分析 332
7.2.8 算術表達式求值的改進 333
7.2.9 本節自測練習 333
7.3 stack類的實現 334
7.3.1 棧的數組實現 334
7.3.2 棧的鍊表實現 337
7.3.3 Koenig查找 341
7.3.4 本節自測練習 341
7.4 更複雜的棧套用 342
7.4.1 後綴表達式求值 342
7.4.2 將中綴表示法轉換成後
綴表示法 344
7.4.3 在中綴表達式中使用
優先權規則 346
7.4.4 中綴轉換為後綴的
正確性 348
7.4.5 本節自測練習 349
7.5 本章小結 349
本章自測練習答案 350
編程項目 351
第8章 佇列 356
8.1 STL佇列 356
8.1.1 標準庫的佇列類 357
8.1.2 佇列的使用 358
8.1.3 本節自測練習 359
8.2 佇列的套用 359
8.2.1 編程示例：識別回文 359
8.2.2 本節自測練習 361
8.2.3 編程示例：洗車模擬
程式 362
8.2.4 洗車模擬程式的
規範說明 362
8.2.5 洗車模擬程式的設計 362
8.2.6 實現洗車類 365
8.2.7 實現模擬函式 371
8.2.8 本節自測練習 372
8.3 佇列類的實現 373
8.3.1 佇列的數組實現 373
8.3.2 有關佇列中環形數組實現
的討論 377
8.3.3 佇列的鍊表實現 379
8.3.4 實現細節 380
8.3.5 本節自測練習 384
8.4 實現STL的雙端佇列 384
8.4.1 為雙端佇列的value_type
項調用析構函式和構造
函式 387
8.4.2 棧和佇列的其他變體 388
8.4.3 本節自測練習 388
8.5 棧、佇列和優先佇列類的引用
返回值 388
8.6 本章小結 389
本章自測練習答案 389
編程項目 390
第9章 遞歸思想 394
9.1 遞歸函式 394
9.1.1 遞歸思想的第一個例子 394
9.1.2 跟蹤遞歸調用 396
9.1.3 編程示例：write_vertical
的一個擴展 397
9.1.4 深入分析遞歸 398
9.1.5 成功遞歸函式的一般
形式 401
9.1.6 本節自測練習 402
9.2 遞歸的研究：分形和迷宮 402
9.2.1 編程示例：產生隨機
分形 403
9.2.2 產生隨機分形的函式及其
規範說明 404
9.2.3 分形函式的設計和實現 405
9.2.4 如何顯示隨機分形 407
9.2.5 編程示例：穿越迷宮 407
9.2.6 穿越迷宮函式的規範
說明 408
9.2.7 穿越迷宮函式的設計 409
9.2.8 穿越迷宮函式的實現 410
9.2.9 運用回溯窮舉搜尋的
遞歸模式 412
9.2.10 編程示例：玩具熊遊戲 413
9.2.11 本節自測練習 414
9.3 推導遞歸 415
9.3.1 如何確保沒有無限遞歸 417
9.3.2 歸納推導遞歸函式的
正確性 419
9.3.3 本節自測練習 419
9.4 本章小結 420
本章自測練習答案 420
編程項目 422
第10章 樹 427
10.1 樹的簡介 427
10.1.1 二叉樹 427
10.1.2 二叉分類樹 430
10.1.3 一般樹 430
10.1.4 本節自測練習 431
10.2 樹的表示法 431
10.2.1 完全二叉樹的數組
表示法 432
10.2.2 使用節點類表示
二叉樹 433
10.2.3 本節自測練習 434
10.3 二叉樹節點類 435
10.3.1 編程示例：猜測動物
程式 439
10.3.2 猜測動物程式的
設計與實現 440
10.3.3 猜測動物程式的
改進 448
10.3.4 本節自測練習 448
10.4 樹的遍歷 449
10.4.1 二叉樹的遍歷 449
10.4.2 從樹的節點中輸出
數據 453
10.4.3 遍歷中的問題 454
10.4.4 函式作為參數 454
10.4.5 apply函式的一個
模板版本 456
10.4.6 使apply模板函式
更具有通用性 457
10.4.7 樹遍歷的模板函式 458
10.4.8 本節自測練習 465
10.5 二叉查找樹 466
10.5.1 二叉查找樹存儲機制 466
10.5.2 第6個bag類的定義 470
10.5.3 第6個bag類的某些
簡單函式的實現 470
10.5.4 計算某個元素在二叉
查找樹中出現的次數 471
10.5.5 添加一個新元素到二叉
查找樹中 472
10.5.6 從二叉查找樹中刪除
某個元素 473
10.5.7 二叉查找樹的組合
操作符 475
10.5.8 時間分析和疊代器 477
10.5.9 本節自測練習 478
10.6 本章小結 478
本章自測練習答案 479
編程項目 482
第11章 平衡樹 487
11.1 堆 487
11.1.1 堆的存儲規則 487
11.1.2 使用堆結構實現的
優先佇列 488
11.1.3 插入新項 488
11.1.4 刪除項 489
11.2 STL優先佇列與堆算法 491
本節自測練習 492
11.3 B樹 492
11.3.1 非平衡樹的問題 493
11.3.2 B樹的規則 493
11.3.3 B樹的一個示例 495
11.3.4 用B樹實現set類 495
11.3.5 在B樹中查找項 499
11.3.6 在B樹中插入項 501
11.3.7 B樹的鬆散插入操作 501
11.3.8 修正子節點多餘項
的私有成員函式 503
11.3.9 回到成員函式
Insert 504
11.3.10 採用自頂向下方法
設計 505
11.3.11 從B樹中刪除項 505
11.3.12 B樹的鬆散刪除
操作 506
11.3.13 解決子節點項短缺
問題的私有成員
函式 508
11.3.14 從B樹中刪除最大
的項 510
11.3.15 外部B樹 512
11.3.16 本節自測練習 512
11.4 樹、日誌和時間分析 513
11.4.1 二叉查找樹的時間
分析 513
11.4.2 堆的時間分析 514
11.4.3 對數運算 515
11.4.4 對數級算法 516
11.4.5 本節自測練習 516
11.5 STL的map類和
multimap類 517
11.6 本章小結 518
本章自測練習答案 518
編程項目 521
第12章 查找 523
12.1 順序查找和二叉查找 523
12.1.1 順序查找 523
12.1.2 順序查找的分析 523
12.1.3 二叉查找 525
12.1.4 二叉查找的設計 526
12.1.5 二叉查找的分析 528
12.1.6 標準庫的查找函式 531
12.1.7 用於有序區間的函式 531
12.1.8 用於無序區間的函式 532
12.1.9 STL的search函式 533
12.1.10 本節自測練習 534
12.2 開地址散列 534
12.2.1 散列簡介 534
12.2.2 表類的聲明 536
12.2.3 表類的設計 538
12.2.4 表ADT的實現 541
12.2.5 選擇散列函式來
減少衝突 547
12.2.6 再散列減少聚類 547
12.2.7 本節自測練習 548
12.3 鏈式散列 549
本節自測練習 551
12.4 散列的時間分析 551
12.4.1 散列表的裝填因子 551
12.4.2 本節自測練習 553
12.5 程式設計：使用STL向量的
表類 553
12.5.1 新表類 553
12.5.2 在新表類中使用向量 554
12.5.3 常量模板參數 554
12.5.4 函式模板參數 554
12.5.5 實現新表類 555
12.5.6 本節自測練習 556
12.6 TR1庫擴展中的散列表 556
12.7 本章小結 557
本章自測練習答案 557
編程項目 561
第13章 排序 563
13.1 二次排序算法 563
13.1.1 選擇排序的規範說明 563
13.1.2 選擇排序的設計 563
13.1.3 選擇排序的實現 565
13.1.4 選擇排序的效率分析 567
13.1.5 插入排序 569
13.1.6 插入排序的效率分析 571
13.1.7 本節自測練習 573
13.2 遞歸排序算法 574
13.2.1 使用遞歸的分治法 574
13.2.2 歸併排序 576
13.2.3 歸併函式 577
13.2.4 動態記憶體在歸併排序中
的套用 581
13.2.5 歸併排序的效率分析 582
13.2.6 檔案的歸併排序 583
13.2.7 快速排序 584
13.2.8 partition函式 585
13.2.9 快速排序的效率分析 588
13.2.10 為快速排序選擇一個
好的基準元素 589
13.2.11 本節自測練習 589
13.3 使用堆的O(n log n)算法 590
13.3.1 堆排序 590
13.3.2 構建堆 595
13.3.3 向下重排 596
13.3.4 堆排序的效率分析 597
13.3.5 本節自測練習 598
13.4 STL的排序與二叉查找 598
13.4.1 原始C標準庫函式
qsort 598
13.4.2 STL的排序函式 599
13.4.3 STL的堆排序 600
13.4.4 STL的二叉查找函式 600
13.4.5 用於STL排序函式
的比較參數 601
13.4.6 使用疊代器編寫一個
自己的排序函式 601
13.5 本章小結 602
本章自測練習答案 603
編程項目 605
第14章 派生類與繼承 610
14.1 派生類 610
14.1.1 如何聲明派生類 612
14.1.2 派生類的自動構造
函式 613
14.1.3 使用派生類 614
14.1.4 派生類的自動賦值
操作符 615
14.1.5 派生類的自動析構
函式 616
14.1.6 覆蓋繼承的成員函式 616
14.1.7 本節自測練習 617
14.2 仿真生態系統 618
14.2.1 實現部分生物對象層次 618
14.2.2 organism類 618
14.2.3 animal類：具有新私有
成員變數的派生類 621
14.2.4 如何為派生類提供
新構造函式 622
14.2.5 animal類的其他
成員函式 623
14.2.6 本節自測練習 627
14.2.7 herbivore類 628
14.2.8 池塘生態仿真程式 630
14.2.9 池塘生態系統的實現
細節 634
14.2.10 使用池塘模型 634
14.2.11 動態記憶體的使用 635
14.2.12 本節自測練習 636
14.3 虛擬成員函式和game類 636
14.3.1 game類簡介 636
14.3.2 受保護的成員 640
14.3.3 虛擬成員函式 640
14.3.4 虛擬析構函式 641
14.3.5 game類的受保護
虛擬成員函式 641
14.3.6 實現Connect Four
遊戲的派生類 642
14.3.7 connect4類的私有
成員變數 642
14.3.8 connect4類的構造
函式和restart函式 644
14.3.9 處理遊戲狀態的
三個函式 644
14.3.10 處理移動的三個函式 645
14.3.11 clone函式 646
14.3.12 編寫派生自game
類的遊戲 646
14.3.13 game類的play算法 647
14.3.14 本節自測練習 650
14.4 本章小結 650
進階閱讀 650
本章自測練習答案 651
編程項目 655
第15章 圖 657
15.1 圖的定義 657
15.1.1 無向圖 657
15.1.2 有向圖 660
15.1.3 圖的更多術語 661
15.1.4 航線的例子 661
15.1.5 本節自測練習 662
15.2 圖的實現 663
15.2.1 使用鄰接矩陣表示圖 663
15.2.2 使用二維數組
存儲鄰接矩陣 663
15.2.3 使用邊列表表示圖 664
15.2.4 使用邊集表示圖 665
15.2.5 哪種表示方法最好 665
15.2.6 編程示例：標籤圖類 665
15.2.7 用於增加頂點和邊
的成員函式 666
15.2.8 標籤圖類——重載
下標操作符 667
15.2.9 下標操作符的常量
版本 668
15.2.10 標籤圖類——函式
neighbors 668
15.2.11 標籤圖類的實現 669
15.2.12 本節自測練習 674
15.3 圖的遍歷 674
15.3.1 深度優先搜尋 675
15.3.2 寬度優先搜尋 677
15.3.3 深度優先搜尋的實現 679
15.3.4 寬度優先搜尋的實現 680
15.3.5 本節自測練習 682
15.4 路徑算法 683
15.4.1 判斷某條路徑是否
存在 683
15.4.2 具有加權邊的圖 683
15.4.3 最短距離算法 684
15.4.4 最短路徑算法 691
15.4.5 本節自測練習 691
15.5 本章小結 692
本章自測練習答案 692
編程項目 693
附錄 697
附錄A ASCII字元集 697
附錄B 大O表達式 698
附錄C 操作符的優先順序 700
附錄D 命令行編譯和連結 701
附錄E 使用老式編譯器 701
附錄F C++的輸入和輸出 701
附錄G 選擇庫函式 708
附錄H 標準模板類簡介 711
附錄I 一些有用函式的工具包 720
附錄J 基本風格指南 723
附錄K 下載GNU編譯器和軟體 723
附錄L 異常處理 724
第1章 軟體開發的階段 1
1.1 規範說明、設計與實現 2
1.1.1 概念設計：問題分解 3
1.1.2 前置條件與後置條件 4
1.1.3 使用由其他程式設計師提供的
函式 6
1.1.4 有關ANSI/ISO C++
標準的實現問題 8
1.1.5 本節自測練習 11
1.2 運行時間分析 12
1.2.1 台階計數問題 12
1.2.2 大O表示法 16
1.2.3 C++函式的時間分析 17
1.2.4 最壞情況、平均情況以及
最好情況下的時間分析 19
1.2.5 本節自測練習 19
1.3 測試與調試 20
1.3.1 選擇測試數據 20
1.3.2 邊界值 20
1.3.3 完全代碼測試 21
1.3.4 調試 21
1.3.5 本節自測練習 22
1.4 本章小結 22
本章自測練習參考答案 23
第2章 抽象數據類型與C++類 25
2.1 類與成員 25
2.1.1 編程示例：節流閥類
throttle 25
2.1.2 使用類 29
2.1.3 throttle類的演示小程式 30
2.1.4 實現成員函式 31
2.1.5 可以調用其他成員的
成員函式 34
2.1.6 本節自測練習 34
2.2 構造函式 35
2.2.1 throttle類的構造函式 35
2.2.2 修訂throttle類的成員
函式 37
2.2.3 內聯成員函式 38
2.2.4 本節自測練習 39
2.3 使用名稱空間、頭檔案與
實現檔案 39
2.3.1 創建名稱空間 40
2.3.2 頭檔案 40
2.3.3 實現檔案 44
2.3.4 使用名稱空間裡的數據項 46
2.3.5 本節自測練習 48
2.4 類與參數 49
2.4.1 編程示例：point類 49
2.4.2 參數默認值 52
2.4.3 參數 53
2.4.4 當函式的返回值的數據
類型為類時 58
2.4.5 本節自測練習 59
2.5 操作符重載 60
2.5.1 二元比較操作符重載 60
2.5.2 二元算術操作符重載 61
2.5.3 輸入輸出操作符重載 62
2.5.4 友元函式 64
2.5.5 point類匯總 66
2.5.6 操作符重載小結 68
2.5.7 本節自測練習 69
2.6 標準模板庫與pair類 69
2.7 本章小結 70
本章自測練習參考答案 71
編程項目 73
第3章 容器類 81
3.1 bag類 81
3.1.1 bag類的規範說明 81
3.1.2 bag類的文檔說明 88
3.1.3 bag類的演示程式 91
3.1.4 bag類的設計 93
3.1.5 類的不變式 94
3.1.6 bag類的實現 95
3.1.7 bag類的集成 101
3.1.8 bag類的測試 104
3.1.9 bag類的分析 105
3.1.10 本節自測練習 106
3.2 編程項目：sequence類 107
3.2.1 sequence類的規範說明 107
3.2.2 sequence類的文檔說明 111
3.2.3 sequence類的設計 113
3.2.4 sequence類的偽代碼實現 114
3.2.5 本節自測練習 116
3.3 互動式測試程式 116
本節自測練習 121
3.4 STL中的multiset類及其疊代器 122
3.4.1 multiset模板類 122
3.4.2 multiset類的一些成員 123
3.4.3 疊代器與[...)模式 123
3.4.4 測試疊代器的相等性 126
3.4.5 multiset類的其他操作符 126
3.4.6 不合法的疊代器 126
3.4.7 本節自測練習 128
3.5 本章小結 128
本章自測練習參考答案 128
編程項目 131
第4章 指針與動態數組 138
4.1 指針與動態記憶體 138
4.1.1 指針變數 139
4.1.2 指針與賦值操作符一起
使用 140
4.1.3 動態變數與new操作符 142
4.1.4 使用new操作符為
動態數組分配記憶體 143
4.1.5 記憶體堆與bad_alloc
異常 144
4.1.6 delete操作符 145
4.1.7 本節自測練習 147
4.2 把指針與數組作為參數 147
4.2.1 以指針作為值參數 147
4.2.2 數組參數 149
4.2.3 以指針或數組作為常量
參數 150
4.2.4 以指針作為引用參數 152
4.2.5 本節自測練習 153
4.3 具有動態數組的bag類 156
4.3.1 指針成員變數 156
4.3.2 成員函式按需分配記憶體 157
4.3.3 值語義 161
4.3.4 析構函式 163
4.3.5 修訂後的bag類定義 164
4.3.6 修訂後的bag類實現 165
4.3.7 修訂後的bag類集成 170
4.3.8 本節自測練習 172
4.4 有關動態類的說明 172
4.4.1 4條規則 173
4.4.2 複製構造函式的特殊
重要性 173
4.4.3 本節自測練習 174
4.5 STL的string類與編程項目 174
4.5.1 以null結尾的字元串 174
4.5.2 初始化字元串變數 175
4.5.3 空字元串 175
4.5.4 讀寫字元串變數 175
4.5.5 strcpy函式 176
4.5.6 strcat函式 177
4.5.7 strlen函式 177
4.5.8 strcmp函式 178
4.5.9 string類的規範說明 178
4.5.10 string類的構造函式 180
4.5.11 重載operator[ ] 181
4.5.12 其他重載成員 181
4.5.13 string類的其他操作 182
4.5.14 string類的設計 182
4.5.15 string類的實現 183
4.5.16 string類的演示程式 185
4.5.17 串聯輸出操作符 186
4.5.18 聲明常量對象 187
4.5.19 由構造函式產生的類型
轉換 187
4.5.20 在表達式中使用
已重載的操作符 187
4.5.21 本章設計的string類與C++
庫的string類 188
4.5.22 本節自測練習 188
4.6 編程項目：polynomial類 188
4.7 本章小結 191
本章自測練習參考答案 192
編程項目 194
第5章 鍊表 196
5.1 鍊表的基本節點類 196
5.1.1 為節點聲明類 196
5.1.2 在鍊表節點中使用
typedef語句 197
5.1.3 頭指針和尾指針 197
5.1.4 空指針NULL 198
5.1.5 頭指針或尾指針為NULL
的含義 199
5.1.6 節點類構造函式 199
5.1.7 節點類成員函式 200
5.1.8 成員選擇操作符 201
5.1.9 本節自測練習 204
5.2 鍊表工具包 205
5.2.1 鍊表工具包的頭檔案 205
5.2.2 計算鍊表的長度 206
5.2.3 鍊表的參數 209
5.2.4 在鍊表頭插入新節點 210
5.2.5 在非鍊表頭的其他位置
插入新節點 212
5.2.6 在鍊表中查找節點 215
5.2.7 根據節點的位置在鍊表中
尋找節點 217
5.2.8 鍊表複製 218
5.2.9 在鍊表頭刪除節點 221
5.2.10 在非鍊表頭刪除節點 222
5.2.11 清空鍊表 223
5.2.12 鍊表工具包的集成 224
5.2.13 使用鍊表工具包 228
5.2.14 本節自測練習 228
5.3 用鍊表實現bag類 229
5.3.1 第3個bag類的規範
說明 229
5.3.2 第3個bag類的類定義 230
5.3.3 如何使bag類的value_
type與節點類的value_
type相匹配 233
5.3.4 在類中使用動態記憶體
應遵循的規則 234
5.3.5 第3個bag類的實現 234
5.3.6 第3個bag類的集成 241
5.3.7 本節自測練習 244
5.4 編程項目：用鍊表實現
sequence類 244
5.4.1 關於修訂後的sequence
類的設計建議 245
5.4.2 關於修訂後的sequence
類的值語義 246
5.4.3 本節自測練習 246
5.5 動態數組、鍊表與雙向鍊表 246
5.5.1 做出抉擇 248
5.5.2 本節自測練習 249
5.6 標準模板庫的vector、list和
deque類 249
本節測試練習 252
5.7 本章小結 252
本章自測練習參考答案 252
編程項目 257
第6章 用模板、疊代器和STL
進行軟體開發 261
6.1 模板函式 261
6.1.1 模板函式的語法 263
6.1.2 使用模板函式 263
6.1.3 交換兩個值的模板函式 265
6.1.4 模板函式的參數匹配 266
6.1.5 在數組中查找最大項
的模板函式 267
6.1.6 在已排序數組中插入一個
數據項的模板函式 268
6.1.7 本節自測練習 270
6.2 模板類 270
6.2.1 模板類的語法 270
6.2.2 進一步了解模板類實現
檔案 277
6.2.3 模板類成員函式的參數
匹配 278
6.2.4 使用模板類 278
6.2.5 詳細討論上一個演示
程式 281
6.2.6 本節自測練習 282
6.3 STL算法與疊代器的使用 282
6.3.1 STL算法 282
6.3.2 標準疊代器的類型 283
6.3.3 數組的疊代器 285
6.3.4 本節自測習題 285
6.4 節點模板類 286
6.4.1 返回引用類型的函式 287
6.4.2 將引用返回值複製到
別處時會發生什麼 288
6.4.3 這裡成員函式data
需要兩個版本 288
6.4.4 新節點類的頭檔案和實現
檔案 289
6.4.5 本節自測練習 297
6.5 鍊表的疊代器 297
6.5.1 節點疊代器 297
6.5.2 從std::iterator派生
而來的節點疊代器 299
6.5.3 節點疊代器的私有
成員變數 300
6.5.4 節點疊代器的構造函式 300
6.5.5 節點疊代器的*操作符 300
6.5.6 節點疊代器兩個版本
的 ++ 操作符 300
6.5.7 節點疊代器的相等和不相
等比較 302
6.5.8 常量集合的疊代器 302
6.5.9 本節自測練習 304
6.6 含疊代器的鍊表版bag模板類 305
6.6.1 如何為容器類提供
疊代器 305
6.6.2 bag類疊代器 306
6.6.3 將疊代器定義在bag
類中的原因 307
6.6.4 本節自測練習 314
6.7 本章小結與5個bag類的小結 314
本章自測練習答案 315
編程項目 318
第7章 棧 320
7.1 STL的stack類 320
7.1.1 標準庫的stack類 321
7.1.2 編程示例：翻轉單詞 322
7.1.3 本節自測練習 323
7.2 棧的套用 323
7.2.1 編程示例：括弧的匹配 323
7.2.2 編程示例：算術表達
式求值 325
7.2.3 算術表達式求值的
規範說明 326
7.2.4 算術表達式求值的設計 326
7.2.5 算術表達式求值的實現 331
7.2.6 計算器程式使用的函式 332
7.2.7 算術表達式求值的
測試與分析 332
7.2.8 算術表達式求值的改進 333
7.2.9 本節自測練習 333
7.3 stack類的實現 334
7.3.1 棧的數組實現 334
7.3.2 棧的鍊表實現 337
7.3.3 Koenig查找 341
7.3.4 本節自測練習 341
7.4 更複雜的棧套用 342
7.4.1 後綴表達式求值 342
7.4.2 將中綴表示法轉換成後
綴表示法 344
7.4.3 在中綴表達式中使用
優先權規則 346
7.4.4 中綴轉換為後綴的
正確性 348
7.4.5 本節自測練習 349
7.5 本章小結 349
本章自測練習答案 350
編程項目 351
第8章 佇列 356
8.1 STL佇列 356
8.1.1 標準庫的佇列類 357
8.1.2 佇列的使用 358
8.1.3 本節自測練習 359
8.2 佇列的套用 359
8.2.1 編程示例：識別回文 359
8.2.2 本節自測練習 361
8.2.3 編程示例：洗車模擬
程式 362
8.2.4 洗車模擬程式的
規範說明 362
8.2.5 洗車模擬程式的設計 362
8.2.6 實現洗車類 365
8.2.7 實現模擬函式 371
8.2.8 本節自測練習 372
8.3 佇列類的實現 373
8.3.1 佇列的數組實現 373
8.3.2 有關佇列中環形數組實現
的討論 377
8.3.3 佇列的鍊表實現 379
8.3.4 實現細節 380
8.3.5 本節自測練習 384
8.4 實現STL的雙端佇列 384
8.4.1 為雙端佇列的value_type
項調用析構函式和構造
函式 387
8.4.2 棧和佇列的其他變體 388
8.4.3 本節自測練習 388
8.5 棧、佇列和優先佇列類的引用
返回值 388
8.6 本章小結 389
本章自測練習答案 389
編程項目 390
第9章 遞歸思想 394
9.1 遞歸函式 394
9.1.1 遞歸思想的第一個例子 394
9.1.2 跟蹤遞歸調用 396
9.1.3 編程示例：write_vertical
的一個擴展 397
9.1.4 深入分析遞歸 398
9.1.5 成功遞歸函式的一般
形式 401
9.1.6 本節自測練習 402
9.2 遞歸的研究：分形和迷宮 402
9.2.1 編程示例：產生隨機
分形 403
9.2.2 產生隨機分形的函式及其
規範說明 404
9.2.3 分形函式的設計和實現 405
9.2.4 如何顯示隨機分形 407
9.2.5 編程示例：穿越迷宮 407
9.2.6 穿越迷宮函式的規範
說明 408
9.2.7 穿越迷宮函式的設計 409
9.2.8 穿越迷宮函式的實現 410
9.2.9 運用回溯窮舉搜尋的
遞歸模式 412
9.2.10 編程示例：玩具熊遊戲 413
9.2.11 本節自測練習 414
9.3 推導遞歸 415
9.3.1 如何確保沒有無限遞歸 417
9.3.2 歸納推導遞歸函式的
正確性 419
9.3.3 本節自測練習 419
9.4 本章小結 420
本章自測練習答案 420
編程項目 422
第10章 樹 427
10.1 樹的簡介 427
10.1.1 二叉樹 427
10.1.2 二叉分類樹 430
10.1.3 一般樹 430
10.1.4 本節自測練習 431
10.2 樹的表示法 431
10.2.1 完全二叉樹的數組
表示法 432
10.2.2 使用節點類表示
二叉樹 433
10.2.3 本節自測練習 434
10.3 二叉樹節點類 435
10.3.1 編程示例：猜測動物
程式 439
10.3.2 猜測動物程式的
設計與實現 440
10.3.3 猜測動物程式的
改進 448
10.3.4 本節自測練習 448
10.4 樹的遍歷 449
10.4.1 二叉樹的遍歷 449
10.4.2 從樹的節點中輸出
數據 453
10.4.3 遍歷中的問題 454
10.4.4 函式作為參數 454
10.4.5 apply函式的一個
模板版本 456
10.4.6 使apply模板函式
更具有通用性 457
10.4.7 樹遍歷的模板函式 458
10.4.8 本節自測練習 465
10.5 二叉查找樹 466
10.5.1 二叉查找樹存儲機制 466
10.5.2 第6個bag類的定義 470
10.5.3 第6個bag類的某些
簡單函式的實現 470
10.5.4 計算某個元素在二叉
查找樹中出現的次數 471
10.5.5 添加一個新元素到二叉
查找樹中 472
10.5.6 從二叉查找樹中刪除
某個元素 473
10.5.7 二叉查找樹的組合
操作符 475
10.5.8 時間分析和疊代器 477
10.5.9 本節自測練習 478
10.6 本章小結 478
本章自測練習答案 479
編程項目 482
第11章 平衡樹 487
11.1 堆 487
11.1.1 堆的存儲規則 487
11.1.2 使用堆結構實現的
優先佇列 488
11.1.3 插入新項 488
11.1.4 刪除項 489
11.2 STL優先佇列與堆算法 491
本節自測練習 492
11.3 B樹 492
11.3.1 非平衡樹的問題 493
11.3.2 B樹的規則 493
11.3.3 B樹的一個示例 495
11.3.4 用B樹實現set類 495
11.3.5 在B樹中查找項 499
11.3.6 在B樹中插入項 501
11.3.7 B樹的鬆散插入操作 501
11.3.8 修正子節點多餘項
的私有成員函式 503
11.3.9 回到成員函式
Insert 504
11.3.10 採用自頂向下方法
設計 505
11.3.11 從B樹中刪除項 505
11.3.12 B樹的鬆散刪除
操作 506
11.3.13 解決子節點項短缺
問題的私有成員
函式 508
11.3.14 從B樹中刪除最大
的項 510
11.3.15 外部B樹 512
11.3.16 本節自測練習 512
11.4 樹、日誌和時間分析 513
11.4.1 二叉查找樹的時間
分析 513
11.4.2 堆的時間分析 514
11.4.3 對數運算 515
11.4.4 對數級算法 516
11.4.5 本節自測練習 516
11.5 STL的map類和
multimap類 517
11.6 本章小結 518
本章自測練習答案 518
編程項目 521
第12章 查找 523
12.1 順序查找和二叉查找 523
12.1.1 順序查找 523
12.1.2 順序查找的分析 523
12.1.3 二叉查找 525
12.1.4 二叉查找的設計 526
12.1.5 二叉查找的分析 528
12.1.6 標準庫的查找函式 531
12.1.7 用於有序區間的函式 531
12.1.8 用於無序區間的函式 532
12.1.9 STL的search函式 533
12.1.10 本節自測練習 534
12.2 開地址散列 534
12.2.1 散列簡介 534
12.2.2 表類的聲明 536
12.2.3 表類的設計 538
12.2.4 表ADT的實現 541
12.2.5 選擇散列函式來
減少衝突 547
12.2.6 再散列減少聚類 547
12.2.7 本節自測練習 548
12.3 鏈式散列 549
本節自測練習 551
12.4 散列的時間分析 551
12.4.1 散列表的裝填因子 551
12.4.2 本節自測練習 553
12.5 程式設計：使用STL向量的
表類 553
12.5.1 新表類 553
12.5.2 在新表類中使用向量 554
12.5.3 常量模板參數 554
12.5.4 函式模板參數 554
12.5.5 實現新表類 555
12.5.6 本節自測練習 556
12.6 TR1庫擴展中的散列表 556
12.7 本章小結 557
本章自測練習答案 557
編程項目 561
第13章 排序 563
13.1 二次排序算法 563
13.1.1 選擇排序的規範說明 563
13.1.2 選擇排序的設計 563
13.1.3 選擇排序的實現 565
13.1.4 選擇排序的效率分析 567
13.1.5 插入排序 569
13.1.6 插入排序的效率分析 571
13.1.7 本節自測練習 573
13.2 遞歸排序算法 574
13.2.1 使用遞歸的分治法 574
13.2.2 歸併排序 576
13.2.3 歸併函式 577
13.2.4 動態記憶體在歸併排序中
的套用 581
13.2.5 歸併排序的效率分析 582
13.2.6 檔案的歸併排序 583
13.2.7 快速排序 584
13.2.8 partition函式 585
13.2.9 快速排序的效率分析 588
13.2.10 為快速排序選擇一個
好的基準元素 589
13.2.11 本節自測練習 589
13.3 使用堆的O(n log n)算法 590
13.3.1 堆排序 590
13.3.2 構建堆 595
13.3.3 向下重排 596
13.3.4 堆排序的效率分析 597
13.3.5 本節自測練習 598
13.4 STL的排序與二叉查找 598
13.4.1 原始C標準庫函式
qsort 598
13.4.2 STL的排序函式 599
13.4.3 STL的堆排序 600
13.4.4 STL的二叉查找函式 600
13.4.5 用於STL排序函式
的比較參數 601
13.4.6 使用疊代器編寫一個
自己的排序函式 601
13.5 本章小結 602
本章自測練習答案 603
編程項目 605
第14章 派生類與繼承 610
14.1 派生類 610
14.1.1 如何聲明派生類 612
14.1.2 派生類的自動構造
函式 613
14.1.3 使用派生類 614
14.1.4 派生類的自動賦值
操作符 615
14.1.5 派生類的自動析構
函式 616
14.1.6 覆蓋繼承的成員函式 616
14.1.7 本節自測練習 617
14.2 仿真生態系統 618
14.2.1 實現部分生物對象層次 618
14.2.2 organism類 618
14.2.3 animal類：具有新私有
成員變數的派生類 621
14.2.4 如何為派生類提供
新構造函式 622
14.2.5 animal類的其他
成員函式 623
14.2.6 本節自測練習 627
14.2.7 herbivore類 628
14.2.8 池塘生態仿真程式 630
14.2.9 池塘生態系統的實現
細節 634
14.2.10 使用池塘模型 634
14.2.11 動態記憶體的使用 635
14.2.12 本節自測練習 636
14.3 虛擬成員函式和game類 636
14.3.1 game類簡介 636
14.3.2 受保護的成員 640
14.3.3 虛擬成員函式 640
14.3.4 虛擬析構函式 641
14.3.5 game類的受保護
虛擬成員函式 641
14.3.6 實現Connect Four
遊戲的派生類 642
14.3.7 connect4類的私有
成員變數 642
14.3.8 connect4類的構造
函式和restart函式 644
14.3.9 處理遊戲狀態的
三個函式 644
14.3.10 處理移動的三個函式 645
14.3.11 clone函式 646
14.3.12 編寫派生自game
類的遊戲 646
14.3.13 game類的play算法 647
14.3.14 本節自測練習 650
14.4 本章小結 650
進階閱讀 650
本章自測練習答案 651
編程項目 655
第15章 圖 657
15.1 圖的定義 657
15.1.1 無向圖 657
15.1.2 有向圖 660
15.1.3 圖的更多術語 661
15.1.4 航線的例子 661
15.1.5 本節自測練習 662
15.2 圖的實現 663
15.2.1 使用鄰接矩陣表示圖 663
15.2.2 使用二維數組
存儲鄰接矩陣 663
15.2.3 使用邊列表表示圖 664
15.2.4 使用邊集表示圖 665
15.2.5 哪種表示方法最好 665
15.2.6 編程示例：標籤圖類 665
15.2.7 用於增加頂點和邊
的成員函式 666
15.2.8 標籤圖類——重載
下標操作符 667
15.2.9 下標操作符的常量
版本 668
15.2.10 標籤圖類——函式
neighbors 668
15.2.11 標籤圖類的實現 669
15.2.12 本節自測練習 674
15.3 圖的遍歷 674
15.3.1 深度優先搜尋 675
15.3.2 寬度優先搜尋 677
15.3.3 深度優先搜尋的實現 679
15.3.4 寬度優先搜尋的實現 680
15.3.5 本節自測練習 682
15.4 路徑算法 683
15.4.1 判斷某條路徑是否
存在 683
15.4.2 具有加權邊的圖 683
15.4.3 最短距離算法 684
15.4.4 最短路徑算法 691
15.4.5 本節自測練習 691
15.5 本章小結 692
本章自測練習答案 692
編程項目 693
附錄 697
附錄A ASCII字元集 697
附錄B 大O表達式 698
附錄C 操作符的優先順序 700
附錄D 命令行編譯和連結 701
附錄E 使用老式編譯器 701
附錄F C++的輸入和輸出 701
附錄G 選擇庫函式 708
附錄H 標準模板類簡介 711
附錄I 一些有用函式的工具包 720
附錄J 基本風格指南 723
附錄K 下載GNU編譯器和軟體 723
附錄L 異常處理 724
