資料結構與演算法分析新視角 数据结构与算法分析新视角

第1章緒論1 
1.1從編程說起1 
1.2程序要處理的數據5 
1.3數據結構的引入11 
1.4數據結構的基本概念13 
1.4.1數據結構基本術語13 
1.4.2數據結構的三個要素13 
1.5如何設計算法16 
1.5.1算法的定義及表示方法16 
1.5.2算法設計與函數設計的關係17 
1.5.3軟件設計描述方法18 
1.5.4算法設計的一般步驟19 
1.6如何評價算法的優劣21 
1.6.1算法的設計要求21 
1.6.2算法效率的度量方法22 
1.7算法性能的事前分析方法23 
1.7.1問題的規模與算法的策略23 
1.7.2算法效率的上限與下限25 
1.7.3漸進的上限——算法的時間
複雜度28 
1.7.4算法時間複雜度的綜合討論29 
1.7.5算法的空間效率分析方法33 
1.8算法性能綜合考量37 
1.9本章小結38 
習題38 
第2章結點邏輯關係為線性的結構——線性表41 
2.1從邏輯結構角度看線性表41 
2.1.1實際問題中的線性關係41 
2.1.2線性表的邏輯結構42 
2.2線性表的存儲結構方法之一——順序表43 
2.2.1順序表的存儲結構設計43 
2.2.2順序表的運算46 
2.2.3順序存儲結構的討論53 
2.3線性表的存儲結構方法之二——鍊錶53 
2.3.1單鍊錶的存儲56 
2.3 .2單鍊錶的運算60 
2.3.3單鍊錶的討論78 
2.3.4循環鍊錶78 
2.3.5雙向鍊錶81 
2.3.6鍊錶小結86 
2.4線性表的應用舉例87 
2.4.1逆序輸出單鍊錶結點值87 
2.4.2一元多項式的相加88 
2.5順序表和鍊錶的比較95 
2.6本章小結96 
習題97 
第3章運算受限的線性表——棧和隊列100 
3.1棧——按照先入後出的方式管理的線性表100 
3.1.1棧處理模式的引入100 
3.1.2棧的邏輯結構104 
3.1.3棧的存儲結構設計106 
3.1.4棧的操作107 
3.1.5各種棧結構的比較123 
3.1.6棧的應用舉例123 
3.2隊列——按照先入先出方式管理的線性表132 
3.2.1隊列處理模式的引入133 
3.2.2隊列的邏輯結構136 
3.2.3隊列的順序存儲結構137 
3.2.4順序隊列的基本操作148 
3.2.5隊列的鍊式存儲結構152 
3.2.6鏈隊列的基本操作153 
3.2.7各種隊列結構的比較160 
3.2.8隊列的應用舉例161 
3.3本章小結171 
習題172 
第4章內容特殊的線性表——多維數組與字符串175 
4.1多維數組175 
4.1.1數組的概念175 
4.1.2數組的存儲結構177 
4.2矩陣的壓縮存儲181 
4.2.1對稱矩陣的壓縮存儲182 
4.2.2三角矩陣的壓縮存儲183 
4.2.3對角矩陣的壓縮存儲183 
4.2.4稀疏矩陣的壓縮存儲185 
4.3字符串189 
4.3.1字符串的定義189 
4.3.2字符串的存儲結構190 
4.3.3字符串的查找——模式匹配195 
4.4本章小結211 
習題213 
第5章結點邏輯關係分層次的非線性結構——樹216 
5.1實際問題中的樹216 
5.2樹的邏輯結構219 
5.2.1樹的定義和基本術語219 
5.2.2樹的操作定義222 
5.3樹的存儲結構222 
5.3.1樹的連續存儲方式223 
5.3.2樹的鍊式存儲方式224 
5.4二叉樹的邏輯結構226 
5.4.1二叉樹的概念229 
5.4.2二叉樹的基本性質230 
5.4.3二叉樹的操作定義231 
5.5二叉樹的存儲結構及實現231 
5.5.1二叉樹的順序結構232 
5.5.2二叉樹的鍊式存儲
結構——二叉鍊錶235 
5.5.3建立動態二叉鍊錶236 
5.6二叉樹結點的查找問題——樹的遍歷240 
5.6.1樹的廣度優先遍歷242 
5.6.2樹的深度優先遍歷244 
5.6.3樹的遍歷的應用255 
5.7樹的應用259 
5.7.1表達式樹259 
5.7.2線索二叉樹260 
5.7.3哈夫曼樹及哈夫曼編碼265 
5.8廣義表278 
5.8.1廣義表的定義279 
5.8.2廣義表的存儲281 
5.8.3廣義表的基本運算287 
5.9本章小結293 
習題295 
第6章結點邏輯關係任意的非線性結構——圖299 
6.1實際問題中的圖及抽象299 
6.2圖的邏輯結構304 
6.2.1圖的定義和基本術語304 
6.2.2圖的操作定義307 
6.3圖的存儲結構及實現308 
6.3.1圖的數組表示法1——鄰接矩陣308 
6.3.2圖的數組表示法2——邊集數組310 
6.3. 3圖的鍊錶表示法1——鄰接表311 
6.3.4圖的鍊錶表示法2——十字鍊錶316 
6.3.5圖的鍊錶表示法3——鄰接多重表317 
6.3.6圖各種存儲結構的歸結比較319 
6.4圖的基本操作320 
6.4.1鄰接矩陣的操作320 
6.4.2鄰接表的操作322 
6.5圖的頂點查找問題——圖的遍歷328 
6.5.1圖的廣度優先遍歷BFS 329 
6.5.2圖的深度優先遍歷DFS 334 
6.5.3圖的遍歷小結340 
6.6圖的經典應用——圖中的樹問題340 
6.6.1生成樹342 
6.6.2最小生成樹MST 343 
6.6.3求最小生成樹算法1——Prim算法344 
6.6.4求最小生成樹算法2——Kruskal算法349 
6.6.5生成樹算法小結356 
6.7圖的經典應用——最短路徑問題357 
6.7.1最短路徑問題的引入357 
6.7. 2單源最短路徑算法——Dijkstra算法359 
6.7.3各頂點對間最短路徑算法——Floyd算法364 
6.7.4最短路徑問題小結369 
6.8圖的經典應用——活動頂點與活動邊的問題370 
6.8 .1圖的活動頂點排序問題的引入370 
6.8.2 AOV網與拓撲排序——活動頂點排序問題373 
6.8.3 AOE網與關鍵路徑——活動邊最長問題378 
6.8.4活動頂點與活動邊問題小結390 
6.9本章小結390 
習題391 
第7章數據的處理方法——排序技術397 
7.1概述397 
7.1.1排序的基本概念397 
7.1.2排序算法的分類399 
7.2插入排序399 
7.2.1直接插入排序399 
7.2.2希爾排序402 
7.3交換排序404 
7.3.1冒泡排序404 
7.3.2快速排序406 
7.4選擇排序409 
7.4.1簡單選擇排序410 
7.4.2堆排序411 
7.5歸併排序415 
7.6分配排序418 
7.6.1桶排序418 
7.6.2基數排序421 
7.7各種排序算法的比較424 
7.8本章小結427 
習題428 
第8章數據的處理——索引與查找技術431 
8.1索引的基本概念433 
8.1.1索引的定義433 
8.1.2索引的邏輯特徵434 
8.1.3索引的主要操作435 
8.2線性索引技術435 
8.2.1稠密索引435 
8.2.2分塊索引436 
8.2.3多重表437 
8.2.4倒排表439 
8.3樹形索引441 
8.3.1二叉排序樹441 
8.3.2 B樹448 
8.4查找概述452 
8.4.1查找的基本概念452 
8.4.2查找算法的性能453 
8.5線性表的查找技術453 
8.5.1順序查找453 
8.5.2有序表查找454 
8.5.3索引查找459 
8.6樹表的查找技術461 
8.6.1二叉排序樹461 
8.6.2 B樹462 
8.6.3在非數值有序表上的查找——字典樹462 
8.7散列表的查找技術464 
8.7.1散列概述465 
8.7.2散列函數的設計467 
8.7.3處理衝突的方法469 
8.7.4散列查找的性能分析473 
8.8本章小結474 
習題476 
第9章經典算法479 
9.1遞歸算法479 
9.1.1遞歸的概念及要素479 
9.1.2遞歸的應用場景481 
9.1.3遞歸的計算機實現482 
9.1.4遞歸方法特點分析483 
9.1.5遞歸算法實例485 
9.1.6遞歸小結487 
9.2分治算法487 
9.2.1分治是什麼487 
9.2.2分治法的適用條件488 
9.2.3分治問題的類型488 
9.2.4分治法小結490 
9.3動態規劃491 
9.3.1什麼是動態規劃491 
9.3.2動態規劃的解題方法493 
9.3.3動態規劃解題實例495 
9.3.4動態規劃小結500 
9.4貪心算法501 
9.4.1貪心算法是什麼501 
9.4.2貪心算法經典問題502 
9.4.3貪心算法小結504 
9.5回溯法504 
9.5.1回溯法是什麼504 
9.5.2回溯法經典問題507 
9.5.3回溯法小結509 
9.6分支限界法509 
9.6.1什麼是分支限界法509 
9.6.2分支限界法的求解思想511 
9.6.3分支限界法經典問題512 
9.6.4分支限界法小結514 
9.7本章小結514 
習題516 
​​附錄A數據的聯繫圖517 
附錄B自定義頭文件的加入方法518 
附錄C軟件設計說明書格式519 
參考文獻521