數據結構（C++Plus 實現）（第6版）

《數據結構（C++ Plus實現）（第6版）》於2022年10月由中國水利水電出版社出版

基本介紹

• 中文名：數據結構（C++ Plus實現）（第6版） 
• 作者：【美】內爾·戴爾 、【美】奇普·威姆斯、【美】蒂姆·理查茲
• 譯者：陳 影 、張 淼 、胡云朋
• 出版時間：2022年10月
• 出版社：中國水利水電出版社
• 頁數：652 頁
• ISBN：9787522607887
• 類別：計算機
• 原作品：C++ Plus Data Structures （Sixth Edition）
• 定價：158.00 元
• 開本：16 開

內容簡介

此版本中，內爾·戴爾（Nell Dale）不再是《數據結構（C++ Plus 實現）（第 6 版）》的唯 一作者。

本書加入了兩位作者——奇普·威姆斯（Chip Weems）和蒂姆·理查茲（Tim Richards），並繼續保持

以往版本的優良傳統。在其他論著方面，奇普與內爾合著了三十多年，如 Java Plus Data Structures，為

本書及其早期版本奠定了基礎，並對教學方法的改進作出了重大貢獻。在 Programming and Problem

Solving in C++ 的新版本中，蒂姆、奇普和內爾三人密切合作，共同致力於讓世界各地的學生能夠取

得成功，同時他們對教學的熱愛也激勵著學生們每天走進教室學習。

在過去的二十年里，傳統的數據結構課程已經發展到更廣泛的主題，包括抽象數據類型（Abstract Data Type，ADT）軟體工程和算法的基本分析。

數據結構（Data Structures）研究如何在組織關係中表示數據集合，以及如何編寫相應操作的算法。

抽象數據類型是指一個定義屬性的數據類型以及這個數據類型上的一組操作。計算機科學教育的重點

向更加抽象的方向轉變。在程式中除了研究如何表示對象之外，還研究數據對象類型的抽象屬性。

Johannes J．Martin 說得非常簡單：“從觀點來看，數據對象是由數據類型（對於使用者）或數據結構（對於實現者）來描述的。

抽象的設計和實現都與軟體工程密切相關，軟體工程旨在將工程方法套用於開發可靠、健壯和高

質量的軟體。一個糟糕的抽象會導致一組煩瑣的套用案例，迫使程式設計師要么編寫不必要的複雜代碼，

要么忽略重要的有效性檢查。一個糟糕的實現可能導致效率低下或容易出錯。

高效實現的一個方面是能夠分析既定算法。因此，在本書中，我們將抽象和應用程式的實現分開

介紹，並分析所介紹的算法。

圖書目錄

目 錄

第1章 軟體工程原則

1.1 軟體開發過程

1.1.1 軟體生命周期

1.1.2 程式設計師的工具箱

1.1.3 高質量的軟體的目標

1.1.4 規格說明書：理解問題

1.1.5 編寫詳細規格說明

1.2 程式設計

1.2.1 抽象

1.2.2 信息隱藏

1.2.3 逐步求精

1.2.4 可視化工具

1.3 設計方法

1.3.1 自上而下的設計

1.3.2 面向對象設計

1.4 軟體正確性驗證

1.4.1 缺陷的來源

1.4.2 正確性設計

1.4.3 程式測試

1.4.4 測試C ++數據結構

1.4.5 實際問題

數據結構（C++ Plus 實現）VIII （第 6 版） 1.4.6 案例研究：分數類

1.5 小結

1.6 練習

第2章 數據設計與實現

2.1　不同的數據視圖

2.1.1 數據的含義

2.1.2 數據抽象

2.1.3 數據結構

2.1.4 抽象數據類型操作類別

2.2　抽象和內置類型

2.2.1 記錄

2.2.2 一維數組

2.2.3 二維數組

2.3　高級抽象和C++類

2.3.1 類的規格說明

2.3.2 類的實現

2.3.3 帶對象參數的成員函式

2.3.4 類與結構的區別

2.4　面向對象的程式設計

2.4.1 概念

2.4.2 面向對象的C++構造

2.5　程式驗證的構造

異常

2.6　算法比較

2.6.1 Big-O

2.6.2 常見的數量級

2.6.3 例1：連續整數和

2.6.4 例2：在電話簿中查找電話號碼2.6.5 案例研究：用戶定義的日期ADT

2.7 小結

2.8 練習

第3章 無序列表ADT 3.1 列表

3.2 抽象數據類型的無序列表

目 錄 IX

3.2.1 邏輯層

3.2.2 抽象數據類型操作

3.2.3 泛型數據類型

3.2.4 套用層

3.2.5 實現層

3.3　指針類型

3.3.1 邏輯層

3.3.2 套用層

3.3.3 實現層

3.4　將UnsortedType類實現為連結結構

3.4.1 連結結構

3.4.2　UnsortedType類

3.4.3 PutItem函式

3.4.4 構造函式

3.4.5 觀察者函式

3.4.6　MakeEmpty函式

3.4.7　GetItem函式

3.4.8　DeleteItem函式

3.4.9　ResetList函式和GetNextItem函式

3.4.10 類的析構函式

3.5　比較無序列表的實現

案例研究：創建一副紙牌

3.6 小結

3.7 練習

第4章 有序列表ADT

4.1 抽象數據類型有序列表

4.1.1 邏輯層

4.1.2 套用層

4.1.3 實現層

4.2 動態分配數組

4.3 將有序列表實現為連結結構

4.3.1 GetItem 函式

4.3.2　PutItem 函式

4.3.3　DeleteItem 函式

4.3.4 編碼

4.3.5 比較有序列表的實現

數據結構（C++ Plus 實現）X （第 6 版） 4.4　無序列表和有序列表ADT算法的比較

4.5　有界ADT和無界ADT

4.6　面向對象的設計方法

4.6.1 集體研討

4.6.2 篩選

4.6.3 情景分析

4.6.4 職責算法設計

4.6.5 結語

4.6.6 案例研究：評估手牌

4.7 小結

4.8 練習

第5章 棧ADT和佇列ADT

5.1　棧

5.1.1 邏輯層

5.1.2 套用層

5.1.3 實現層

5.1.4 替代基於數組的實現

5.2　將棧實現為連結結構

5.2.1 Push 函式

5.2.2 Pop函式

5.2.3 Top函式

5.2.4 其他棧函式

5.2.5 比較棧的實現

5.3　佇列

5.3.1 邏輯層

5.3.2 套用層

5.3.3 實現層

5.3.4 計數佇列

5.4 將佇列實現為連結結構

5.4.1　Enqueue函式

5.4.2　Dequeue函式

5.4.3 循環連結佇列設計

5.4.4 比較佇列的實現

5.4.5 案例研究：模擬紙牌遊戲

5.5 小結

5.6 練習

第6章 鍊表+

6.1　關於泛型的更多信息：C++模板

6.2　循環鍊表

6.2.1 查找鍊表項

6.2.2 將元素插入循環鍊表

6.2.3 從循環鍊表中刪除元素

6.3 雙向鍊表

6.3.1 在雙向鍊表中查找元素

6.3.2 雙向鍊表的操作

6.4 帶有頭部和尾部的鍊表

6.5 複製結構6.5.1 淺拷貝與深拷貝

6.5.2 類複製構造函式

6.5.3 複製函式

6.5.4 重載運算符

6.6 作為記錄數組的鍊表

6.6.1 為什麼使用數組

6.6.2 如何使用數組

6.7 虛函式的多態性

6.8 專用的鍊表ADT

測試計畫

6.9 基於範圍的疊代

案例研究：實現大整數ADT

6.10 小結

6.11 練習

第7章 遞歸編程

7.1　什麼是遞歸

7.2　遞歸的經典示例

7.3　使用遞歸進行編程

編碼階乘函式

7.4　驗證遞歸函式

三問法

7.5　編寫遞歸函式

編寫布爾函式

7.6　使用遞歸簡化解決方案

7.7　鍊表的遞歸處理

7.8　二分查找的遞歸版本

7.9　PutItem和DeleteItem的遞歸版本

7.9.1 PutItem函式

7.9.2 DeleteItem函式

7.10　遞歸如何工作

7.10.1 靜態存儲分配

7.10.2 動態存儲分配

7.11　跟蹤遞歸函式Insert的執行

7.12　遞歸快速排序

7.13　調試遞歸例程

7.14　刪除遞歸

7.14.1 疊代

7.14.2 使用棧

7.15　決定是否使用遞歸解決方案

案例研究：逃離迷宮

7.16 小結

7.17 練習

第8章 二叉查找樹

8.1　查找

8.1.1 線性查找

8.1.2 高機率排序

8.1.3 鍵排序

8.1.4 二分查找

8.2　樹

8.3　邏輯層

8.4　套用層

8.5　實現層

8.6　二叉查找樹的遞歸操作

8.6.1 IsFull函式和 IsEmpty函式

8.6.2 GetLength函式

8.6.3　GetItem函式

8.6.4 PutItem函式

8.6.5　DeleteItem函式

8.6.6　Print函式

8.6.7 類構造函式和析構函式

8.6.8 樹的複製 .

8.6.9 有關遍歷的更多信息

8.6.10　ResetTree函式和GetNextItem 函式

8.7　插入與刪除函式的疊代方法

8.7.1 查找二叉查找樹

8.7.2　PutItem函式

8.7.3　DeleteItem函式

8.7.4 測試計畫

8.7.5 遞歸還是疊代

8.8　比較二叉查找樹和鍊表

8.8.1　Big-O比較

8.8.2 案例研究：建立索引

8.9　小結

8.10 練習

第9章 堆、優先權佇列和堆排序

9.1　優先權佇列ADT

9.1.1 邏輯層

9.1.2 套用層

9.1.3 實現層

9.2 二叉樹的非連結表示

9.3 堆

9.3.1 邏輯層

9.3.2 套用層

9.3.3 實現層

9.3.4 重現實現層

9.3.5 堆與優先權佇列的其他表示

9.5 小結

第10章 樹+

10.1　AVL 樹

10.1.1 AVL樹的單旋轉

10.1.2 在 AVL 樹上執行單旋轉

數據結構（C++ Plus 實現）XIV （第 6 版） 10.1.3 AVL樹的雙旋轉

10.1.4 在 AVL 樹上執行雙旋轉

10.1.5 套用層

10.1.6 邏輯層

10.1.7 實現層

10.2　紅黑樹

10.2.1 插入紅黑樹

10.2.2 紅黑樹的重新著色的實現

10.2.3 紅黑樹總結

10.3 B樹

10.4 小結

10.5 練習

第11章 集合、映射和散列

11.1 集合

11.1.1 邏輯層

11.1.2 套用層

11.1.3 實現層

11.2 映射

11.2.1 邏輯層

11.2.2 套用層

11.2.3 實現層

11.3 散列

11.3.1 衝突

11.3.2 選擇一個好的散列函式

11.3.3 複雜度

11.4 小結

11.5 練習

第12章 排序

12.1　重新排序

12.2　直接選擇排序

12.3　冒泡排序

12.4　插入排序

12.5　O(N log2 N) 排序 .

12.5.1 歸併排序

12.5.2 快速排序

12.5.3 堆排序

12.5.4 測試

12.6　效率和其他考慮因素

12.6.1 當N很小時

12.6.2 取消對函式的調用

12.6.3 程式設計師時間

12.6.4 空間考慮

12.6.5 鍵和穩定性

12.6.6 用指針排序

12.6.7 快取

12.7　基數排序

分析基數排序

12.8　並行歸併排序

12.9 小結

12.10 練習

第13章 圖

13.1 圖的定義與實現

13.1.1 邏輯層

13.1.2 套用層

13.1.3 實現層

13.2 小結

13.3 練習

附錄

附錄A 保留字

附錄 B 運算符優先權

附錄 C 標準程式庫選編

附錄 D 美國信息交換標準代碼 （ASCII）字元集

附錄 E 標準模板庫（STL）

術語表

作者簡介

內爾·戴爾(Nell Dale)博士―德克薩斯大學奧斯汀分校

內爾·戴爾在休斯頓大學獲得數學和心理學學士學位，在德克薩斯大學奧斯汀分校獲得數學碩士學位，並獲得計算機科學博士學位。內爾·戴爾自1975年以來一直在德克薩斯大學奧斯汀分校任教。她編寫了四十多本計算機科學方面的本科生教材。由於在計算機科學領域的貢獻，她於1996年獲得了ACM SIGCSE計算機科學教育傑出貢獻獎，於2001年獲得了ACM Karl Karlston傑出教師獎。她於2010年被選為ACM會士。

奇普·威姆斯(Chip Weems)博士―麻薩諸塞大學

奇普·威姆斯是麻薩諸塞大學阿默斯特分校的計算機科學副教授。他分別於1977年和1979年在俄勒岡州立大學獲得學士和碩士學位。他1984年在麻薩諸塞大學獲得了博士學位。在過去的23年中，他教授了入門編程、軟jian工程、計算機體系結構和並行處理等課程。自1986年以來，他與人合作了13部教科書，幫助超過一百萬的學生學習計算機編程。他的書已被翻譯成法文、西班牙文和俄文。他從事計算機體系結構、編譯器、並行處理和編譯器-體系結構協同最佳化方面的研究。