數(shù)據結構：Python語言描述

前言
第1章 緒論1
1.1 引言1
1.1.1 學習目的1
1.1.2 課程內容2
1.2 基本概念2
1.2.1 數(shù)據與數(shù)據結構2
1.2.2 數(shù)據類型與抽象數(shù)據類型6
1.3 算法9
1.3.1 算法的概念9
1.3.2 算法描述9
1.3.3 算法分析11
小結13
習題114
第2章 線性表17
2.1 線性表及其基本操作17
2.1.1 線性表的基本概念17
2.1.2 抽象數(shù)據類型描述18
2.1.3 線性表的存儲和實現(xiàn)19
2.2 線性表的順序存儲19
2.2.1 順序表19
2.2.2 順序表的基本操作實現(xiàn)21
2.3 線性表的鏈式存儲和實現(xiàn)25
2.3.1 單鏈表25
2.3.2 單鏈表的基本操作實現(xiàn)27
2.3.3 其他鏈表30
2.4 順序表與鏈表的比較31
2.5 實驗32
2.5.1 數(shù)組奇偶分割32
2.5.2 反轉單向鏈表33
2.5.3 鏈表實現(xiàn)34
小結38
習題238
第3章 棧和隊列41
3.1 棧41
3.1.1 棧的基本概念41
3.1.2 棧的抽象數(shù)據類型描述41
3.1.3 順序棧43
3.1.4 鏈棧46
3.2 隊列50
3.2.1 隊列的基本概念50
3.2.2 隊列的抽象數(shù)據類型描述50
3.2.3 順序隊列51
3.2.4 鏈隊列55
3.2.5 優(yōu)先級隊列57
3.3 棧和隊列的比較60
3.4 實驗60
3.4.1 漢諾塔60
3.4.2 吃巧克力62
3.4.3 數(shù)頭頂63
3.4.4 整數(shù)變換64
3.4.5 表達式求值66
3.4.6 用隊列表示棧67
3.4.7 用棧表示隊列69
3.4.8 層次遍歷71
小結72
習題373
第4章 串和數(shù)組72
4.1 串76
4.1.1 串的基本概念76
4.1.2 串的抽象數(shù)據類型描述76
4.1.3 順序串78
4.1.4 鏈串82
4.2 串的模式匹配82
4.2.1 Brute Force算法83
4.2.2 KMP算法83
4.3 數(shù)組87
4.3.1 數(shù)組的基本概念87
4.3.2 數(shù)組的特性88
4.3.3 數(shù)組的遍歷88
4.4 特殊矩陣的壓縮存儲89
4.4.1 三角矩陣的壓縮存儲89
4.4.2 對稱矩陣的壓縮存儲90
4.4.3 對角矩陣的壓縮存儲90
4.4.4 稀疏矩陣的壓縮存儲91
4.5 實驗93
4.5.1 AZY的冒險島93
4.5.2 最大連續(xù)子數(shù)組94
4.5.3 合并有序數(shù)組95
4.5.4 最長上升子序列96
小結97
習題497
第5章 樹形結構101
5.1 樹101
5.1.1 樹的基本概念101
5.1.2 樹的術語102
5.2 二叉樹103
5.2.1 二叉樹的基本概念103
5.2.2 二叉樹的性質104
5.2.3 二叉樹的存儲結構105
5.2.4 二叉樹的遍歷106
5.2.5 二叉樹遍歷算法的應用110
5.2.6 二叉樹的建立112
5.3 哈夫曼樹及哈夫曼編碼114
5.3.1 哈夫曼樹的基本概念114
5.3.2 哈夫曼樹的構造115
5.3.3 哈夫曼編碼116
5.3.4 構造哈夫曼樹和哈夫曼編碼的類的描述116
5.4 樹和森林118
5.4.1 樹的存儲結構118
5.4.2 樹的遍歷規(guī)則119
5.5 實驗119
小結121
習題5121
第6章 圖125
6.1 圖概述125
6.1.1 圖的基本概念125
6.1.2 圖的抽象數(shù)據類型描述127
6.2 圖的存儲結構128
6.2.1 鄰接矩陣128
6.2.2 鄰接表132
6.3 圖的遍歷137
6.4 最小生成樹141
6.4.1 最小生成樹的基本概念141
6.4.2 Kruskal算法142
6.4.3 Prim算法142
6.5 最短路徑144
6.5.1 單源最短路徑144
6.5.2 求任意兩個頂點間的最短路徑146
6.6 拓撲排序和關鍵路徑148
6.6.1 拓撲排序148
6.6.2 關鍵路徑149
6.7 實驗151
小結152
習題6153
第7章 排序156
7.1 排序概述156
7.1.1 排序的基本概念156
7.1.2 排序算法的性能評價156
7.1.3 待排序的記錄和順序表的類描述156
7.2 插入排序157
7.2.1 直接插入排序157
7.2.2 希爾排序159
7.3 交換排序160
7.3.1 冒泡排序160
7.3.2 快速排序161
7.4 選擇排序164
7.4.1 直接選擇排序164
7.4.2 堆排序166
7.5 歸并排序168
7.6 實驗172
7.6.1 插入排序172
7.6.2 鏈表排序173
7.6.3 區(qū)間排序174
小結175
習題7176
第8章 查找179
8.1 查找的基本概念179
8.1.1 什么是查找179
8.1.2 查找表179
8.1.3 平均查找長度180
8.2 靜態(tài)查找表180
8.2.1 順序查找180
8.2.2 二分查找181
8.2.3 分塊查找182
8.3 動態(tài)查找表182
8.3.1 二叉排序樹查找183
8.3.2 平衡二叉樹187
8.3.3 B-樹和B+樹189
8.4 哈希表查找190
8.4.1 哈希表的概念190
8.4.2 哈希函數(shù)190
8.4.3 解決沖突的方法191
8.4.4 哈希表查找性能分析192
8.5 實驗195
8.5.1 尋找山形數(shù)組的頂點195
8.5.2 尋找和為指定值的數(shù)組元素195
8.5.3 尋找數(shù)組元素196
小結197
習題8198
附錄200
附錄A 名校數(shù)據結構程序設計考研真題解答（部分）200
附錄B 名詞索引206
參考文獻209