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

第1章 緒論 1
1.1認(rèn)識(shí)數(shù)據(jù)結(jié)構(gòu) 1
1.1.1舉例認(rèn)識(shí)數(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è)計(jì)中的地位 4
1.3.1算法的描述 4
1.3.2算法與程序設(shè)計(jì) 5
1.3.3算法的特性 6
1.4評(píng)價(jià) 6
1.4.1評(píng)價(jià)標(biāo)準(zhǔn) 6
1.4.2評(píng)價(jià)方法 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)與存儲(chǔ)結(jié)構(gòu) 11
2.3.1數(shù)據(jù)的邏輯結(jié)構(gòu) 1l
2.3.2數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu) 11
2.4本章小結(jié) 11
2.5本章習(xí)題 11
第3章 線性表 12
3.1線性表基本概念和邏輯結(jié)構(gòu) 12
3.1.1線性表實(shí)例 12
3.1.2線性表定義 13
3.1.3線性表邏輯結(jié)構(gòu) 13
3.2線性表存儲(chǔ)方式及操作 13
3.2.1線性表的順序存儲(chǔ) 13
3.2.2線性表順序存儲(chǔ)的操作 14
3.2.3線性表順序存儲(chǔ)操作的評(píng)價(jià) 17
3.2.4線性表的鏈?zhǔn)酱鎯?chǔ) 18
3.2.5單鏈表的操作 20
3.3線性表操作在單鏈表上實(shí)現(xiàn)的程序設(shè)計(jì) 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棧的實(shí)例 41
4.1.2棧的定義 42
4.1.3棧的基本操作 43
4.2棧的實(shí)現(xiàn) 43
4.2.1棧實(shí)現(xiàn)分類 43
4.2.2棧的數(shù)組實(shí)現(xiàn) 43
4.2.3棧的鏈接存儲(chǔ)實(shí)現(xiàn) 46
4.3棧的應(yīng)用實(shí)例 49
4.3.1數(shù)制轉(zhuǎn)換實(shí)例 49
4.3.2堆棧實(shí)例 50
4.4棧與遞歸 51
4.5本章小結(jié) 52
4.6本章習(xí)題 52
第5章 隊(duì)列 53
5.1隊(duì)列的基本概念 53
5.1.1隊(duì)列的實(shí)例 53
5.1.2隊(duì)列的定義 54
5.2隊(duì)列的分類 54
5.2.1隊(duì)列存儲(chǔ)結(jié)構(gòu)分類 54
5.2.2鏈隊(duì)列 55
5.2.3循環(huán)隊(duì)列 55
5.3隊(duì)列的實(shí)現(xiàn) 56
5.3.1隊(duì)列的運(yùn)算 56
5.3.2隊(duì)列的順序存儲(chǔ)操作與實(shí)現(xiàn) 57
5.3.3隊(duì)列的鏈接存儲(chǔ)操作與實(shí)現(xiàn) 61
5.4本章小結(jié) 65
5.5本章習(xí)題 65
第6章 串 66
6.1串的應(yīng)用實(shí)例 66
6.1.1串的應(yīng)用舉例 66
6.1.2串的定義 67
6.2串在非數(shù)值數(shù)據(jù)運(yùn)算中的重要地位 70
6.3 串的運(yùn)算 70
6.3.1串的存儲(chǔ)表示 71
6.3.2串的存儲(chǔ)結(jié)構(gòu)與實(shí)現(xiàn) 73
6.4本章小結(jié) 77
6.5本章習(xí)題 78
第7章 數(shù)組與矩陣 79
7.1數(shù)組概述 79
7.1.1數(shù)組實(shí)例 79
7.1.2數(shù)組定義 79
7.2數(shù)組的存儲(chǔ) 80
7.3矩陣 81
7.3.1矩陣簡(jiǎn)介 8l
7.3.2稀疏矩陣 8l
7.3.3用三元數(shù)組表示的稀疏矩陣 82
7.3.4用十字鏈表示的稀疏矩陣 85
7.4特殊矩陣的壓縮存儲(chǔ) 89
7.4.1對(duì)稱矩陣的壓縮存儲(chǔ) 89
7.4.2三角矩陣的壓縮存儲(chǔ) 90
7.4.3帶狀矩陣的壓縮存儲(chǔ) 91
7.5本章小結(jié) 92
7.6本章習(xí)題 92
第8章 樹(shù) 93
8.1樹(shù)型結(jié)構(gòu) 93
8.1.1樹(shù)型結(jié)構(gòu)實(shí)例 93
8.1.2樹(shù)型結(jié)構(gòu)定義 94
8.1.3樹(shù)型結(jié)構(gòu)相關(guān)術(shù)語(yǔ) 95
8.1.4樹(shù)的表示方法 96
8.2二叉樹(shù) 97
8.2.1二叉樹(shù)實(shí)例 97
8.2.2二又樹(shù)定義 97
8.2.3二叉樹(shù)的基本性質(zhì) 98
8.2.4二叉樹(shù)的存儲(chǔ)結(jié)構(gòu) 100
8.2.5二叉樹(shù)的操作 102
8.2.6二又樹(shù)遍歷 104
8.3二又樹(shù)和森林的關(guān)系 106
8.3.1二叉樹(shù)與樹(shù)的轉(zhuǎn)換 106
8.3.2樹(shù)和森林的遍歷 110
8.4樹(shù)的應(yīng)用 112
8.4.1最佳查找樹(shù) 112
8.4.2平衡樹(shù) 118
8.4.3huffman算法 123
8.5本章小結(jié) 126
8.6本章習(xí)題 126
第9章 圖 128
9.1 圖的定義和基本術(shù)語(yǔ) 128
9.1.1圖的定義 128
9.1.2圖的基本術(shù)語(yǔ) 129
9.2圖的存儲(chǔ)結(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最小生成樹(shù) 136
9.4.1普里姆(prim)算法 137
9.4.2克魯斯卡爾(kruskal)算法 138
9.5最短路徑 140
9.6拓?fù)渑判? 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簡(jiǎn)單選擇排序 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鏈?zhǔn)交鶖?shù)排序算法 182
11.7本章小結(jié) 183
11.8本章習(xí)題 184
部分習(xí)題答案 185