數據結構(C++語言版)(第2版)（簡體書）

《清華大學計算機系列教材：數據結構（C++語言版）（第2版）》按照面向對象程序設計的思想，根據作者多年的教學積累，系統地介紹各類數據結構的功能、表示和實現，對比各類數據結構適用的應用環境；結合實際問題展示算法設計的一般性模式與方法．算法實現的主流技巧，以及算法效率的評判依據和分析方法；以高度概括的體例為線索貫穿全書，並通過對比和類比揭示數據結構與算法的內在聯繫，幫助讀者形成整體性認識。
書中穿插驗證型、拓展型和反思型習題總計280餘道，激發讀者的求知欲，培養自學能力和獨立思考習慣；260多組300餘幅插圖結合簡練的敘述，230余段代碼配合詳盡而簡潔的注釋，使深奧抽象的概念和過程得以具體化且便於理解和記憶；推薦20餘冊經典的專著與教材，提供30餘篇重點的學術論文，便於讀者進一步鑽研和拓展。
結合學生基礎、專業方向、教學目標及允許課時總量等因素，《清華大學計算機系列教材：數據結構（C++語言版）（第2版）》提供了若干種典型的教學進度及學時分配方案，供授課教師視具體情況參考和選用。勘誤表、插圖、代碼、部分習題解答以及講義等相關教學資料，均以電子版形式向公眾開放。．

鄧俊輝，清華大學計算機系副教授。1993年，1997年分別于清華大學計算機系獲工學學士和工學博士學位。主要研究方向為科學計算可視化、計算幾何及計算機圖形學。長期承擔清華大學計算機本科生專業基礎課程“數據結構”和研究生基礎理論課“計算幾何”的教學工作，編著的《數據結構與算法（Java描述）》入選“北京市高等教育精品教材”，參與編著的《數據結構（用面向對象方法與C++語言描述）》入選“國家級高等教育精品教材”，曾獲清華大學“青年教師教學優秀獎”、清華大學“教書育人獎”、清華大學“教學成果獎”二等獎、清華大學“教學成果獎”一等獎、中國高校科學技術獎二等獎、寶鋼教育基金“寶鋼教育獎”。

《清華大學計算機系列教材:數據結構(C++語言版)(第2版)》中穿插驗證型、拓展型和反思型習題總計280余道，激發讀者的求知欲，培養自學能力和獨立思考習慣；260多組300余幅插圖結合簡練的敘述，230余段代碼配合詳盡而簡潔的注釋，使深奧抽象的概念和過程得以具體化且便于理解和記憶；推薦20余冊經典的專著與教材，提供30余篇重點的學術論文，便于讀者進一步鉆研和拓展。

第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.3復雜度分析
1.3.1常數σ（1）
1.3.2對數σ（logn）
1.3.3線性σ（n）
1.3.4多項式σ（polynomial（n））
1.3.5指數σ（2n）
1.3.6復雜度層次
1.3.7輸入規模
1.4遞歸
1.4.1線性遞歸
1.4.2遞歸分析
1.4.3遞歸模式
1.4.4遞歸消除
1.4.5二分遞歸
§1.5抽象數據類型
習題
第2章向量
2.1從數組到向量
2.1.1數組
2.1.2向量
2.2接口
2.2.1 ADT口
2.2.2操作實例
2.2.3 Vector模板類
2.3構造與析構
2.3.1默認構造方法
2.3.2基于復制的構造方法
2.3.3析構方法
2.4動態空間管理
2.4.1靜態空間管理
2.4.2可擴充向量
2.4.3擴容
2.4.4分攤分析
2.4.5縮容
2.5常規向量
2.5.1直接引用元素
2.5.2置亂器
2.5.3判等器與比較器
2.5.4無序查找
2.5.5插入
2.5.6刪除
2.5.7唯-化
2.5.8遍歷
2.6有序向量
2.6.1比較器
2.6.2有序性甄別
2.6.3唯-化
2.6.4查找
2.6.5二分查找（版本A）
2.6.6 Fibonacci查找
2.6.7二分查找（版本B）
2.6.8二分查找（版本C）
2.7排序與下界
2.7.1有序性
2.7.2排序及其分類
2.7.3下界
2.7.4比較樹
2.7.5估計下界
2.8排序器
2.8.1 統一入口
2.8.2起泡排序
2.8.3歸并排序
習題
第3章列表
3.1從向量到列表
3.1.1從靜態存儲到動態存儲
3.1.2由秩到位置
3.1.3列表
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.3.6基于復制的構造
3.3.7刪除
3.3.8析構
3.3.9唯-化
3.3.10遍歷
§3.4有序列表
3.4.1唯-化
3.4.2查找
3.5排序器
3.5.1統一入口
3.5.2插入排序
3.5.3選擇排序
3.5.4歸并排序
習題
第4章 棧與隊列
4.1棧
4.1.1 ADT接口
4.1.2操作實例
4.1.3 Stack模板類
4.2棧與遞歸
4.2.1遞歸的實現
4.2.2避免遞歸
4.3典型應用
4.3.1逆序輸出
4.3.2遞歸嵌套
4.3.3延遲緩沖
4.3.4逆波蘭表達式
4.4試探回溯法
4.4.1試探與回溯
4.4.2八皇后
4.4.3迷宮尋徑
4.5隊列
4.5.1概述
4.5.2 ADT接口
4.5.3操作實例
4.5.4 Queue模板類
4.6隊列應用
4.6.1循環分配器
4.6.2銀行服務模擬
習題
第5章二叉樹
5.1二叉樹及其表示
5.1.1樹
5.1.2二叉樹
5.1.3多叉樹
5.2編碼樹
5.2.1二進制編碼
5.2.2二叉編碼樹
5.3二叉樹的實現
5.3.1二叉樹節點
5.3.2二叉樹節點操作接口
5.3.3二叉樹
5.4 Huffman編碼
5.4.1 PFC編碼及解碼
5.4.2最優編碼樹
5.4.3 Huffman編碼樹
5.4.4 Huffman編碼算法
5.5遍歷
5.5.1遞歸式遍歷
5.5.2迭代版先序遍歷
5.5.3迭代版中序遍歷
5.5.4迭代版后序遍歷
5.5.5層次遍歷
習題
第6章圖
6.1概述
6.2抽象數據類型
6.2.1操作接口
6.2.2 Graph模板類
6.3鄰接矩陣
6.3.1原理
6.3.2實現
6.3.3時間性能
6.3.4空間性能
6.4鄰接表
6.4.1原理
6.4.2復雜度
6.5圖遍歷算去概述
6.6廣度優先搜索
6.6.1策略
6.6.2實現
6.6.3實例
6.6.4復雜度
6.6.5應用
6.7深度優先搜索
6.7.1策略
6.7.2實現
6.7.3實例
6.7.4復雜度
6.7.5應用
6.8拓撲排序
6.8.1應用
6.8.2有向無環圖
6.8.3算法
6.8.4實現
6.8.5實例
6.8.6復雜度
6.9雙連通域分解
6.9.1關節點與雙連通域
6.9.2蠻力算法
6.9.3算法
6.9.4實現
6.9.5實例
6.9.6復雜度
6.10優先級搜索
6.10.1優先級與優先級數
6.10.2基本框架
6.10.3復雜度
6.11最小支撐樹
6.11.1支撐樹
6.11.2最小支撐樹
6.11.3歧義性
6.11.4蠻力算法
6.11.5 Prim算法
6.12最短路徑
6.12.1最短路徑樹
6.12.2歧義性
6.12.3 Dijkstra算法
習題
第7章搜索樹
7.1查找
7.1.1循關鍵碼訪問
7.1.2詞條
7.1.3序與比較器
7.2二叉搜素樹
7.2.1順序性
7.2.2中序遍歷序列
7.2.3 BST模板類
7.2.4查找算法及其實現
7.2.5插入算法及其實現
7.2.6刪除算法及其實現
7.3平衡二叉搜索樹
7.3.1樹高與性能
7.3.2理想平衡與適度平衡
7.3.3等價二叉搜索樹
7.3.4等價變換與局部調整
7.4 AVL樹
7.4.1定義及性質
7.4.2節點插入
7.4.3節點刪除
7.4.4統一重平衡算法
習題
第8章 高級搜索樹
8.1伸展樹
8.1.1局部性
8.1.2逐層伸展
8.1.3雙層伸展
8.1.4分攤分析
8.1.5伸展樹的實現
8.2 B-樹
8.2.1多路平衡查找
8.2.2 ADT接口及其實現
8.2.3關鍵碼查找
8.2.4性能分析
8.2.5關鍵碼插入
8.2.6 上溢與分裂
8.2.7關鍵碼刪除
8.2.8下溢與合并
8.3 紅黑樹
8.3.1概述
8.3.2紅黑樹接口定義
8.3.3節點播入算去
8.3.4節點刪除算法
8.4 kd-樹
8.4.1范圍查詢
8.4.2 kd-樹
8.4.3基于2d-樹的范圍查詢
習題
第9章詞典
9.1詞典ADT
9.1.1操作接口
9.1.2操作實例
9.1.3接口定義
9.1.4實現方去
9.2 跳轉表
9.2.1 Skiplist模板類
9.2.2總體邏輯結構
9.2.3四聯表
9.2.4查找
9.2.5空間復雜度
9.2.6時間復雜度
9.2.7插入
9.2.8刪除
s9.3 散列表
9.3.1完美散列
9.3.2裝填因子與空間利用率
9.3.3散列函數
9.3.4散列表
9.3.5沖突及其排解
9.3.6閉散列策略
9.3.7查找與刪除
9.3.8插入
9.3.9更多閉散列策略
9.3.10散列碼轉換
9.4散列應用
9.4.1桶排序
9.4.2最大間隙
9.4.3基數排序
習題
第10章優先級隊列
10.1優先級隊列ADT
10.1.1優先級與優先級隊列
10.1.2關鍵碼、比較器與偏序關系
10.1.3操作接口
10.1.4操作實例：選擇排序
10.1.5接口定義
10.1.6應用實例：Huffman編碼樹
10.2堆
10.2.1完全二叉堆
10.2.2元素插入
10.2.3元素刪除
10.2.4建堆
10.2.5就地堆排序
10.3左式堆
10.3.1堆合并
10.3.2單側傾斜
10.3.3 PCLLeftHeap模板類
10.3.4空節點路徑長度
10.3.5左傾性與左式堆
10.3.6右側鏈
10.3.7合并算法
10.3.8實例
10.3.9合并操作merge（）的實現
10.3.10復雜度
10.3.11基于合并的插入和刪除
習題
第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 KMP算法
11.3.1構思
11.3.2 next表
11.3.3 KMP算法
11.3.4 next[0】=-1
11.3.5 next[j+1]
11.3.6構造next表
11.3.7性能分析
11.3.8繼續改進
11.4 BM算法
11.4.1思路與框架
11.4.2壞字符策略
11.4.3好后綴策略
11.4.4 GS【】表構造算法
11.4.5算法縱覽
11.5 Karp-Rabin算法
11.5.1構思
11.5.2算法與實現
習題

借助數據結構來表示和組織待處理信息，可以數據集合為單位將其視作一個整體，進而提高信息訪問接口的規范性以及信息處理的效率。如今，借助關鍵碼直接查找和訪問數據元素的形式已經為越來越多的數據結構所采用，這也成為現代數據結構的一個重要特征。
詞典（dictionary）結構即是其中最典型的例子，邏輯上它是一組數據元素的集合，其中數據元素都是由關鍵碼和數據項合成的詞條（entry）。映射（map）結構與詞典結構一樣也是詞條的集合，二者的差別僅僅在于，映射要求不同詞條的關鍵碼互異，而詞典則允許多個詞條擁有相同的關鍵碼①。除了靜態查找，映射和詞典都支持動態更新，二者統稱作符號表（symbol table）。實際上， “是否允許雷同關鍵碼”應從語義層面而非ADT接口的層面予以界定，故本章將不再過分強調二者的差異，而是籠統地稱之為詞典，并以跳轉表和散列表為例，按照“允許雷同”和“禁止雷同”的語義分別實現其統一的接口。
盡管此處詞典和映射中的數據元素仍表示和實現為詞條形式，但這一做法并非必須。與第7章和第8章的搜索樹相比，符號表并不要求詞條之間能夠根據關鍵碼比較大小：與稍后第10章的優先級隊列相比，其查找對象亦不僅限于最大或最小詞條。符號表的內部甚至也不需要按照大小次序來組織數據項，無論各數據項之間是否能夠定義某種大小關系。實際上，以散列表為典型代表的符號表結構，將轉而依據數據項的數值直接做邏輯查找和物理定位。也就是說對于此類結構，在作為基本數據單位的詞條內部，關鍵碼（key）與數值（value）的地位等同，二者不必加以區分。此類結構所支持的這種新的數據訪問方式，即所謂的循值訪問（call-by-value）。相對于此前各種方式，這一方式更為自然，適用范圍也更廣泛。
饒有趣味的是，在程序設計等方面已經具有一定基礎的讀者，對這種“新的”數據訪問方式往往不由自主地會或多或少有些抵觸的傾向；而剛剛涉足這一領域的讀者，卻反過來會有似曾相識的親切之感并更樂于接受。究其原因在于，循值訪問方式與我們頭腦中原本對數據集合組成的理解最為接近；不幸的是，在學習C／C++之類高級程序語言的過程中，我們思考問題的出發點和方向都已逐步被這些語言所同化并強化，而一些與生俱來的直覺與思路則逐漸為我們所淡忘。比如，在小學低年級孩子們的頭腦中，班級的最初概念只不過是同學們的一組笑臉；而隨著學習內容的持續深入和思維方式的反復塑化，這一概念往往會逐漸被一組姓名所取代；甚至可能進而被抽象為一組學號，以便利用程序語言予以描述和處理。
既已拋開大小的概念，采用循值訪問方式的計算過程自然不再屬于CBA式算法，原先關于算法下界的結論亦不再適用，一條通往高效算法的嶄新大道由此在我們面前豁然展開。比如在9.4節我們將看到，散列式排序算法將不再服從2.7節所給出的CBA復雜度下界。
當然，為支持循值訪問的方式，在符號表的內部，仍然必須強制地在數據對象的數值與其物理地址之間建立某種關聯。而所謂散列，正是在兼顧空間與時間效率的前提下，討論和研究賴以設計并實現這種關聯的一般性原則、技巧與方法，這些方面也是本章的核心與重點。