內容簡介
《高職高專計算機專業系列教材:數據結構》對常用的數據結構做了系統的介紹,注重實踐,力求概念清晰、深入淺出。主要內容包括數據結構的基本概念;算法描述和算法分析初步:線性表、堆疊、佇列、串、數組、樹、圖等結構:排序和查找的各種方法;此外還用一章的篇幅詳細介紹了鏈式存儲結構以加強讀者的理解。
目錄
第1章緒 論1
1.1引言1
1.2基本概念和術語3
1.3算法描述5
1.3.1算法的重要特性5
1.3.2數據結構上的基本操作5
1.3.3算法的描述方法6
1.4算法分析7
1.4.1算法設計的要求7
1.4.2算法時間效率的度量分析7
第2章線性表11
2.1線性表的定義及邏輯結構11
2.2線性表的基本操作12
2.3線性表的順序存儲結構12
2.4基本操作在順序表上的實現13
2.4.1順序表上元素的插入13
2.4.2順序表上元素的刪除15
2.4.3順序表上元素的定位16
2.5套用舉例及分析16
第3章鏈式存儲結構21
3.1線性表的鏈式存儲結構21
3.1.1單鍊表上的基本運算23
3.1.2循環鍊表29
3.1.3雙向鍊表29
3.2線性表的順序和鏈式存儲結構的比較31
3.3套用舉例及分析32
第4章棧和佇列37
4.1棧37
4.1.1棧的定義及基本操作37
4.1.2棧的順序存儲結構38
4.1.3棧的鏈式存儲結構40
4.2佇列41
4.2.1佇列的定義及基本操作41
4.2.2佇列的順序存儲結構42
4.2.3佇列的鏈式存儲結構46
4.3套用舉例及分析48
第5章其他線性數據結構53
5.1串53
5.1.1串的定義及基本操作53
5.1.2串的存儲結構54
5.1.3串的基本操作的實現56
5.2多維數組58
5.2.1二維數組定義及基本操作58
5.2.2二維數組的向量存儲結構59
5.2.3稀疏矩陣的壓縮存儲60
5.2.4稀疏矩陣的轉置算法61
5.3套用舉例及分析63
第6章樹和二叉樹67
6.1樹的定義和基本操作67
6.1.1樹的定義67
6.1.2基本術語68
6.1.3樹的基本操作69
6.2二叉樹69
6.2.1二叉樹的定義和基本操作70
6.2.2二叉樹的性質71
6.2.3二叉樹的存儲結構73
6.2.4遍歷二叉樹75
6.3樹和森林78
6.3.1樹的存儲結構78
6.3.2樹、森林與二叉樹的轉換81
6.3.3樹和森林的遍歷83
6.4哈夫曼樹和判定樹84
6.4.1哈夫曼樹的定義及構造方法84
6.4.2哈夫曼編碼86
6.4.3分類與判定87
6.5套用舉例及分析89
第7章圖99
7.1圖的定義和術語99
7.2圖的存儲結構102
7.2.1鄰接矩陣表示法102
7.2.2鄰接鍊表表示法104
7.3圖的遍歷107
7.3.1深度優先搜尋遍歷107
7.3.2廣度優先搜尋遍歷108
7.4圖的套用110
7.4.1生成樹和最小生成樹110
7.4.2拓撲排序113
7.4.3最短路徑116
7.5套用舉例及分析118
第8章查找125
8.1基本概念125
8.2靜態查找表126
8.2.1順序表上順序查找126
8.2.2有序表查找128
8.2.3索引順序表查找130
8.3動態查找132
8.3.1二叉排序樹的生成和插入132
8.3.2二叉排序樹上的查找134
8.3.3二叉排序樹的刪除135
8.4散列表137
8.4.1散列表與散列函式137
8.4.2散列函式的構造方法138
8.4.3解決衝突的主要方法140
8.4.4散列表的查找及分析142
8.5套用舉例及分析144
第9章內部排序152
9.1基本概念152
9.2三種簡單排序方法153
9.2.1直接插入排序153
9.2.2冒泡排序154
9.2.3簡單選擇排序156
9.3快速排序157
9.4堆排序160
9.5歸併排序164
9.6基數排序166
9.6.1多關鍵字的排序167
9.6.2鏈式基數排序167
9.7各種內部排序方法的比較與討論169
附錄數據存儲類型說明(datastru.h)171