數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)與應(yīng)用

第1章 緒論 1
1.1認識數(shù)據(jù)結(jié)構(gòu) 1
1.1.1舉例認識數(shù)據(jù)結(jié)構(gòu) 1
1.1.2數(shù)據(jù)結(jié)構(gòu)定義 2
1.1.3數(shù)據(jù)結(jié)構(gòu)的基本結(jié)構(gòu)類型和表示 2
1.2數(shù)據(jù)結(jié)構(gòu)類型 3
1.2.1線性結(jié)構(gòu) 4
1.2.2非線性結(jié)構(gòu) 4
1.3數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計中的地位 4
1.3.1算法的描述 4
1.3.2算法與程序設(shè)計 5
1.3.3算法的特性 6
1.4評價 6
1.4.1評價標(biāo)準 6
1.4.2評價方法 6
1.5本章小結(jié) 7
1.6本章習(xí)題 7
第2章 數(shù)據(jù)結(jié)構(gòu)分類 8
2.1幾種數(shù)據(jù)結(jié)構(gòu)案例 8
2.2數(shù)據(jù)結(jié)構(gòu)分類 10
2.2.1數(shù)據(jù)類型 10
2.2.2抽象數(shù)據(jù)類型 10
2.3數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu) 11
2.3.1數(shù)據(jù)的邏輯結(jié)構(gòu) 1l
2.3.2數(shù)據(jù)的存儲結(jié)構(gòu) 11
2.4本章小結(jié) 11
2.5本章習(xí)題 11
第3章 線性表 12
3.1線性表基本概念和邏輯結(jié)構(gòu) 12
3.1.1線性表實例 12
3.1.2線性表定義 13
3.1.3線性表邏輯結(jié)構(gòu) 13
3.2線性表存儲方式及操作 13
3.2.1線性表的順序存儲 13
3.2.2線性表順序存儲的操作 14
3.2.3線性表順序存儲操作的評價 17
3.2.4線性表的鏈式存儲 18
3.2.5單鏈表的操作 20
3.3線性表操作在單鏈表上實現(xiàn)的程序設(shè)計 26
3.4循環(huán)鏈表介紹 33
3.5靜態(tài)鏈表介紹 35
3.6順序表和鏈表的比較 39
3.7本章小結(jié) 39
3.8本章習(xí)題 39
第4章 棧 41
4.1棧的基本概念 41
4.1.1棧的實例 41
4.1.2棧的定義 42
4.1.3棧的基本操作 43
4.2棧的實現(xiàn) 43
4.2.1棧實現(xiàn)分類 43
4.2.2棧的數(shù)組實現(xiàn) 43
4.2.3棧的鏈接存儲實現(xiàn) 46
4.3棧的應(yīng)用實例 49
4.3.1數(shù)制轉(zhuǎn)換實例 49
4.3.2堆棧實例 50
4.4棧與遞歸 51
4.5本章小結(jié) 52
4.6本章習(xí)題 52
第5章 隊列 53
5.1隊列的基本概念 53
5.1.1隊列的實例 53
5.1.2隊列的定義 54
5.2隊列的分類 54
5.2.1隊列存儲結(jié)構(gòu)分類 54
5.2.2鏈隊列 55
5.2.3循環(huán)隊列 55
5.3隊列的實現(xiàn) 56
5.3.1隊列的運算 56
5.3.2隊列的順序存儲操作與實現(xiàn) 57
5.3.3隊列的鏈接存儲操作與實現(xiàn) 61
5.4本章小結(jié) 65
5.5本章習(xí)題 65
第6章 串 66
6.1串的應(yīng)用實例 66
6.1.1串的應(yīng)用舉例 66
6.1.2串的定義 67
6.2串在非數(shù)值數(shù)據(jù)運算中的重要地位 70
6.3 串的運算 70
6.3.1串的存儲表示 71
6.3.2串的存儲結(jié)構(gòu)與實現(xiàn) 73
6.4本章小結(jié) 77
6.5本章習(xí)題 78
第7章 數(shù)組與矩陣 79
7.1數(shù)組概述 79
7.1.1數(shù)組實例 79
7.1.2數(shù)組定義 79
7.2數(shù)組的存儲 80
7.3矩陣 81
7.3.1矩陣簡介 8l
7.3.2稀疏矩陣 8l
7.3.3用三元數(shù)組表示的稀疏矩陣 82
7.3.4用十字鏈表示的稀疏矩陣 85
7.4特殊矩陣的壓縮存儲 89
7.4.1對稱矩陣的壓縮存儲 89
7.4.2三角矩陣的壓縮存儲 90
7.4.3帶狀矩陣的壓縮存儲 91
7.5本章小結(jié) 92
7.6本章習(xí)題 92
第8章 樹 93
8.1樹型結(jié)構(gòu) 93
8.1.1樹型結(jié)構(gòu)實例 93
8.1.2樹型結(jié)構(gòu)定義 94
8.1.3樹型結(jié)構(gòu)相關(guān)術(shù)語 95
8.1.4樹的表示方法 96
8.2二叉樹 97
8.2.1二叉樹實例 97
8.2.2二又樹定義 97
8.2.3二叉樹的基本性質(zhì) 98
8.2.4二叉樹的存儲結(jié)構(gòu) 100
8.2.5二叉樹的操作 102
8.2.6二又樹遍歷 104
8.3二又樹和森林的關(guān)系 106
8.3.1二叉樹與樹的轉(zhuǎn)換 106
8.3.2樹和森林的遍歷 110
8.4樹的應(yīng)用 112
8.4.1最佳查找樹 112
8.4.2平衡樹 118
8.4.3huffman算法 123
8.5本章小結(jié) 126
8.6本章習(xí)題 126
第9章 圖 128
9.1 圖的定義和基本術(shù)語 128
9.1.1圖的定義 128
9.1.2圖的基本術(shù)語 129
9.2圖的存儲結(jié)構(gòu) 130
9.2.1鄰接矩陣 130
9.2.2鄰接表 131
9.3圖的遍歷 133
9.3.1深度優(yōu)先搜索(dfs)遍歷 133
9.3.2深度優(yōu)先搜索(bfs)遍歷 135
9.4最小生成樹 136
9.4.1普里姆(prim)算法 137
9.4.2克魯斯卡爾(kruskal)算法 138
9.5最短路徑 140
9.6拓撲排序 143
9.7關(guān)鍵路徑法 145
9.8本章小結(jié) 149
9.9本章習(xí)題 149
第10章 查找 151
10.1線性表的查找 151
10.1.1順序查找 151
10.1.2折半查找 153
10.1.3分塊查找 156
10.2哈希法 157
10.2.1哈希表的概念 157
10.2.2哈希函數(shù)的構(gòu)造 158
10.2.3處理沖突的方法 160
10.2.4.哈希表的查找分析 162
10.3本章小結(jié) 163
10.4本章習(xí)題 163
第11章 排序 164
11.1基本概念 164
11.2插入排序 165
11.2.1直接插入排序 165
11.2.2希爾排序 167
ll.3交換排序 169
11.3.1冒泡排序 169
11.3.2快速排序 171
11.4選擇排序 174
11.4.1簡單選擇排序 174
1 1.4.2堆排序 176
11.5歸并排序 178
11.5.1歸并排序的基本思想 178
11.5.2歸并排序算法 178
11.6基數(shù)排序 180
11.6.1基數(shù)排序的基本思想 180
11.6.2鏈式基數(shù)排序算法 182
11.7本章小結(jié) 183
11.8本章習(xí)題 184
部分習(xí)題答案 185