數據結構與實訓（第4版）（微課版）

全書共8章及1個附錄：第1章介紹了數據結構和算法的基本概念；第2～4章介紹了線性表、堆棧、隊列、串、數組；第5、6章介紹了非線性結構，即樹形結構和圖狀結構，第7、8章介紹了兩個基本技術，即查找和排序；附錄A介紹了實訓的相關知識，包括實訓的步驟、實訓報告規範和實訓的上機環境等內容。本書詳細闡述了數據結構的基本概念、各種不同的存儲結構，以及在不同存儲結構上的主要算法的實現，並給出了豐富的典型例題，以幫助讀者有效理解。本書可作為高等院校、高等職業院校電腦及相關專業數據結構課程的教材。

張新顏 ，女，畢業於華中科技大學，碩士學位。從事計算機軟件教學工作二十多年，主講過C、VB等多種程序設計語言課程以及數據結構、微機原理、軟件測試等課程，多次獲得學院教學質量一、二等獎，“數據結構”課程2008年被評為學院精品課程。參加多項教學研究項目，參與多項省級科研項目的開發工作，所有項目均通過省級鑑定。曾多次被評為學院優秀教師，畢業設計優秀指導教師。

目錄
第1 章 概論 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 1
1．1 引言． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 2
1．1．1 什麼是數據結構 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 2
1．1．2 數據結構研究什麼 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 2
1．2 數據結構的基本概念 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 4
1．3 算法和算法的分析 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 4
1．3．1 算法及算法的描述 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 4
1．3．2 算法設計的要求 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 5
1．3．3 算法的分析 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 6
1．4 算法知識準備 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 8
1．4．1 算法描述規範 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 8
1．4．2 C 語言核心知識 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 9
1．5 總結與提高 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 11
習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 11
第2 章 線性表 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 14
2．1 線性表的定義及基本運算 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 15
2．1．1 線性表的定義 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 15
2．1．2 線性表的基本運算 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 15
2．2 線性表的順序存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 16
2．2．1 順序表 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 16
2．2．2 順序表上基本運算的實現 ． ． ． ． ． 16
2．3 線性表的鍊式存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 20
2．3．1 單鍊錶及其基本運算 ． ． ． ． ． ． ． ． ． ． ． ． ． 20
2．3．2 循環鍊錶 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 24
2．4 順序表與鍊錶的比較 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 25
2．5 典型例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 26
2．6 實訓例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 28
2．6．1 實訓例題1：有序順序表的建立及查找 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 28
2．6．2 實訓例題2：多項式的表示和相加 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 31
2．7 總結與提高 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 35
2．7．1 主要知識點 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 35
2．7．2 提高例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 36
習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 37
實訓習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 39
第3 章 堆棧和隊列 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 41
3．1 堆棧 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 42
3．1．1 堆棧的定義及基本運算 ． ． ． ． ． ． ． ． ． 42
3．1．2 堆棧的順序存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． 42
3．1．3 堆棧的鍊式存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． 45
3．2 堆棧典型例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 48
3．3 隊列 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 49
3．3．1 隊列的定義及運算 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 49
3．3．2 隊列的順序存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． 50
3．3．3 隊列的鍊式存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． 52
3．4 隊列典型例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 54
3．5 實訓例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 56
3．5．1 實訓例題1：循環隊列的操作 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 56
3．5．2 實訓例題2：括號配對 ． ． ． ． ． ． ． ． ． ． 58
3．6 總結與提高 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 62
3．6．1 主要知識點 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 62
3．6．2 提高例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 62
習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 64
實訓習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 67
第4 章 串與數組 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 68
4．1 串及其基本運算 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 69
4．1．1 串的基本概念 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 69
4．1．2 串的基本運算 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 69
4．2 串的存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 70
4．2．1 串的順序存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 71
4．2．2 串的堆式存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 73
4．2．3 串的鍊式存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 74
4．3 數組． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 75
4．3．1 數組的定義 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 75
4．3．2 一維數組、二維數組和多維數組 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 75
4．4 典型例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 77
4．5 實訓例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 78
4．5．1 實訓例題1：字符串操作 ． ． ． ． ． ． 78
4．5．2 實訓例題2：二維數組 ． ． ． ． ． ． ． ． ． ． 81
4．6 總結與提高 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 83
4．6．1 主要知識點 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 83
4．6．2 提高例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 84
習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 86
實訓習題． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 88
第5 章 樹和二叉樹 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 89
5．1 樹 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 90
5．1．1 樹的基本概念 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 90
5．1．2 樹的基本操作 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 92
5．1．3 樹的存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 93
5．2 二叉樹 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 96
5．2．1 二叉樹的定義及基本操作 ． ． ． ． ． 96
5．2．2 二叉樹的性質 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 97
5．2．3 二叉樹的存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 99
5．3 遍歷二叉樹 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 102
5．3．1 二叉樹的遍歷方法 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 102
5．3．2 二叉樹遍曆算法應用典型例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 111
5．4 樹和二叉樹的關係 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 113
5．4．1 將樹轉換為二叉樹 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 113
5．4．2 樹的遍歷 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 114
5．5 哈夫曼樹及其應用 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 115
5．5．1 哈夫曼樹的定義及構造 ． ． ． ． ． ． ． 115
5．5．2 哈夫曼樹的應用 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 119
5．6 典型例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 121
5．7 實訓例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 123
5．7．1 實訓例題1：根據順序存儲結構建立二叉樹二叉鍊錶，並對二叉樹進行先序、中序、後序遍歷 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 123
5．7．2 實訓例題2：設計哈夫曼編碼 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 127
5．8 總結與提高 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 132
5．8．1 主要知識點 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 132
5．8．2 提高例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 133
習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 134
實訓習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 137
第6 章 圖 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 138
6．1 圖的定義、基本術語和基本操作 ． ． ． ． 139
6．1．1 圖的定義 ． ． ． ． ．． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 139
6．1．2 圖的基本術語 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 139
6．1．3 圖的基本操作 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 141
6．2 圖的存儲結構 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 142
6．2．1 鄰接矩陣 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 142
6．2．2 鄰接表 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 144
6．2．3 鄰接矩陣和鄰接表的比較 ． ． ． ． 147
6．3 圖的遍歷 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 147
6．3．1 連通圖的深度優先搜索 ． ． ． ． ． ． ． 148
6．3．2 連通圖的廣度優先搜索 ． ． ． ． ． ． ． 149
6．3．3 非連通圖的遍歷 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 151
6．4 最小生成樹 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 151
6．4．1 相關概念 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 151
6．4．2 普里姆算法 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 152
6．4．3 克魯斯卡爾算法 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 153
6．5 最短路徑 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 154
6．6 拓撲排序 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 158
6．7 典型例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 161
6．8 實訓例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 165
6．8．1 實訓例題1：圖的遍歷 ． ． ． ． ． ． ． ． 165
6．8．2 實訓例題2：設計學習計劃 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 170
6．9 總結與提高 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 174
6．9．1 主要知識點 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 174
6．9．2 提高例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 174
習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 176
實訓習題． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 179
第7 章 查找 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 180
7．1 基本概念 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 181
7．2 線性表的查找 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 181
7．2．1 順序查找 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 181
7．2．2 折半查找 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 183
7．2．3 分塊查找 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 185
7．3 二叉排序樹的查找 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 186
7．3．1 二叉排序樹的定義 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 187
7．3．2 二叉排序樹的查找算法 ． ． ． ． ． ． ． 187
7．3．3 二叉排序樹的建立與插入 ． ． ． 188
7．3．4 二叉排序樹的查找算法分析 191
7．4 哈希表的查找 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 191
7．4．1 哈希表的概念 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 191
7．4．2 哈希函數的構造方法 ． ． ． ． ． ． ． ． ． ． ． 192
7．4．3 處理衝突的方法 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 194
7．4．4 哈希表上的運算 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 198
7．5 典型例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 200
7．6 實訓例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 203
7．6．1 實訓例題1：構造二叉排序樹 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 203
7．6．2 實訓例題2：哈希表的操作 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 206
7．7 總結與提高 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 211
7．7．1 主要知識點 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 211
7．7．2 提高例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 212
習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 213
實訓習題． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 215
第8 章 排序 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 216
8．1 排序的基本概念 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 217
8．2 插入排序 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 217
8．2．1 直接插入排序 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 218
8．2．2 希爾排序 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 219
8．3 交換排序 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 221
8．3．1 冒泡排序 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 221
8．3．2 快速排序 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 222
8．4 選擇排序 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 224
8．4．1 直接選擇排序 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 224
8．4．2 堆排序 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 225
8．5 各種內部排序方法的比較 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 230
8．6 典型例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 230
8．7 實訓例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 232
8．7．1 實訓例題1：不同排序算法的比較 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 232
8．7．2 實訓例題2：學生成績名次表 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 240
8．8 總結與提高 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 246
8．8．1 主要知識點 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 246
8．8．2 提高例題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 246
習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 248
實訓習題 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 251
附錄A 數據結構實訓指南 ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． ． 252