數據結構（C語言）

第1章緒論1 
1.1數據結構起源1 
1.2基本概念和術語1 
1.2.1基本概念1 
1.2.2數據結構2 
1.3抽像數據類型4 
1.4算法和算法分析5 
1.4.1算法5 
1.4.2算法的時間複雜度5 
1.4.3最壞、最好和平均情況時間復
雜度6 
1.4.4算法的空間複雜度7 
1.5微課（一） 7 
習題7 
第2章線性表9 
2.1線性表定義9 
2.2線性表的順序存儲結構和實現10 
2.2.1線性表的順序存儲結構10 
2.2.2順序表基本運算的實現10 
2.3線性表的鍊式存儲結構和實現14
2.3.1單鍊錶的定義和表示15 
2.3.2單鍊錶基本運算的實現15 
2.3.3帶錶頭結點的單鍊錶20 
2.3.4單循環鍊錶22 
2.3.5雙向鍊錶22 
2.4順序表與鍊錶的比較23 
2.5線性表的應用24 
2.6微課（二） 27 
習題27 
第3章堆棧和隊列29 
3.1堆棧29 
3.1.1堆棧ADT 29 
3.1.2堆棧的順序表示30 
3.1.3堆棧的鏈接表示31 
3.2隊列32 
3.2.1隊列ADT 32 
3.2.2隊列的順序表示32 
3.2.3隊列的鏈接表示35 
3.3表達式計算35 
3.3.1中綴表達式35 
3.3.2後綴表達式及其求值方法36 
3.3.3中綴表達式轉換為後綴表達式39 
3.4遞歸41 
3.4.1遞歸的概念41 
3.4.2遞歸的實現42 
3.5微課（三） 43 
習題43 
第4章數組和字符串45 
4.1數組45 
4.1.1一維數組45
4.1.2二維數組46 
4.1.3多維數組47 
4.2數組的抽像數據類型47 
4.3特殊矩陣50 
4.3.1對稱矩陣50 
4.3.2三角矩陣51 
4.4稀疏矩陣52 
4.4.1稀疏矩陣的抽像數據類型52 
4.4.2稀疏矩陣的簡單轉置算法54 
4.4.3稀疏矩陣的快速轉置算法55 
4.5字符串57 
4.5.1字符串的抽像數據類型57 
4.5.2簡單字符串匹配算法58 
4.5.3改進的字符串匹配算法61 
4.6微課（四） 65 
習題65 
第5章樹和二叉樹67 
5.1樹67 
5.1.1樹的定義67 
5.1.2基本術語67 
5.1.3樹的抽像數據類型68 
5.1.4樹的存儲表示69 
5.2二叉樹71 
5.2.1二叉樹的定義及主要性質71 
5.2.2二叉樹的抽像數據類型73 
5.2.3二叉樹的順序存儲和鍊式存儲
表示74 
5.2.4二叉樹的遍歷75 
5.2.5線索二叉樹的基本概念和構造77
5.3樹、森林與二叉樹的關係78 
5.3.1樹、森林與二叉樹的轉換79 
5.3.2樹和森林的遍歷82 
5.4堆和優先權隊列83 
5.4.1堆83 
5.4.2優先權隊列85 
5.5哈夫曼樹及其應用88 
5.5.1哈夫曼樹的基本概念88 
5.5.2哈夫曼算法89 
5.5.3哈夫曼編碼90 
5.6微課（五） 92 
習題92 
第6章集合和搜索95 
6.1集合的表示95 
6.1.1基本概念95 
6.1.2動態集ADT 96 
6.1.3集合的表示96 
6.2順序搜索97 
6.2.1無序表的順序搜索97 
6.2.2有序表的順序搜索98 
6.3對半搜索98 
6.3.1對半搜索方法98 
6.3.2二叉判定樹101 
6.4微課（六） 102 
習題102 
第7章搜索樹104 
7.1二叉搜索樹104 
7.1.1二叉搜索樹的定義和表示104 
7.1.2二叉搜索樹基本運算的實現105
7.2二叉平衡樹109 
7.2.1二叉平衡樹的定義和表示109 
7.2.2 AVL搜索樹基本運算的實現111 
7.3 B-樹113 
7.3.1 B-樹的定義和表示114 
7.3.2 B-樹基本運算的實現116 
7.4微課（七） 120 
習題120 
第8章跳錶和散列表122 
8.1跳錶122 
8.1.1跳錶的定義和表示122 
8.1.2跳錶基本操作的實現123 
8.2散列表125 
8.2.1散列表的定義和表示125 
8.2.2散列表基本操作的實現127 
8.3微課（八） 132 
習題132 
第9章圖134 
9.1圖的基本概念134 
9.1.1圖的定義134 
9.1 .2圖的基本術語135 
9.1.3圖的類型定義137 
9.2圖的存儲結構137 
9.2.1鄰接矩陣表示法137 
9.2.2鄰接矩陣的實現138 
9.2.3圖的鄰接表表示法141 
9.2.4鄰接表的實現141 
9.3圖的遍歷144
9.3.1深度優先遍歷144 
9.3.2寬度優先遍歷146 
9.4拓撲排序148 
9.4.1 AOV網148 
9.4.2拓撲排序149 
9.5關鍵路徑150 
9.5.1 AOE網150 
9.5.2關鍵路徑151 
9.6最小代價生成樹154 
9.6.1基本概念154 
9.6.2普裏姆（Prim）算法154 
9.6.3克魯斯卡爾（Kruskal）算法156 
9.7單源最短路徑159 
9.7.1最短路徑159 
9.7.2單源最短路徑159 
9.8所有頂點之間的最短路徑163 
9.9微課（九） 165 
習題165 
第10章排序168 
10.1排序的基本概念168 
10.2簡單排序算法169 
10.2.1簡單選擇排序169 
10.2.2直接插入排序172 
10.2 .3冒泡排序174 
10.3快速排序算法177 
10.4兩路合併排序181 
10.5堆排序184 
10.6外排序187
10.6.1預處理187 
10.6.2多路合併191 
10.6.3最佳合併樹195 
10.6.4完整的外排序過程196 
10.7微課（十） 196 
習題196 
附錄綜合實驗199