第1章緒論
1.1什么是數(shù)據(jù)結(jié)構(gòu)
1.1.1數(shù)據(jù)結(jié)構(gòu)的定義
1.1.2數(shù)據(jù)的邏輯結(jié)構(gòu)
1.1.3數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)
1.1.4數(shù)據(jù)的運(yùn)算
1.1.5數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類(lèi)型
1.2算法及其描述
1.2.1什么是算法
1.2.2算法描述
1.3算法分析
1.3.1算法設(shè)計(jì)的要求
1.3.2算法的時(shí)間性能分析
1.3.3算法的存儲(chǔ)空間分析
1.4數(shù)據(jù)結(jié)構(gòu)的目標(biāo)
1.5練習(xí)題
1.5.1問(wèn)答題
1.5.2算法分析題
1.6實(shí)驗(yàn)題
1.6.1上機(jī)實(shí)驗(yàn)題
1.6.2在線(xiàn)編程題
第2章線(xiàn)性表
2.1線(xiàn)性表的定義
2.1.1什么是線(xiàn)性表
2.1.2線(xiàn)性表的抽象數(shù)據(jù)類(lèi)型描述
2.2線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)
2.2.1線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu)——順序表
2.2.2線(xiàn)性表的基本運(yùn)算算法在順序表中的實(shí)現(xiàn)
2.2.3順序表的應(yīng)用算法設(shè)計(jì)示例
2.2.4順序表容器——ArrayList
2.3線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
2.3.1線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈表
2.3.2單鏈表
2.3.3單鏈表的應(yīng)用算法設(shè)計(jì)示例
2.3.4雙鏈表
2.3.5雙鏈表的應(yīng)用算法設(shè)計(jì)示例
2.3.6循環(huán)鏈表
2.3.7鏈表容器——LinkedList
2.4順序表和鏈表的比較
2.5線(xiàn)性表的應(yīng)用
2.5.1求解多項(xiàng)式相加問(wèn)題的描述
2.5.2采用順序存儲(chǔ)結(jié)構(gòu)求解
2.5.3采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)求解
2.6練習(xí)題
2.6.1問(wèn)答題
2.6.2算法設(shè)計(jì)題
2.7實(shí)驗(yàn)題
2.7.1上機(jī)實(shí)驗(yàn)題
2.7.2在線(xiàn)編程題
第3章棧和隊(duì)列
3.1棧
3.1.1棧的定義
3.1.2棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算算法的實(shí)現(xiàn)
3.1.3順序棧的應(yīng)用算法設(shè)計(jì)示例
3.1.4棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算算法的實(shí)現(xiàn)
3.1.5鏈棧的應(yīng)用算法設(shè)計(jì)示例
3.1.6Java中的棧容器——StackE
3.1.7棧的綜合應(yīng)用
3.2隊(duì)列
3.2.1隊(duì)列的定義
3.2.2隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算算法的實(shí)現(xiàn)
3.2.3循環(huán)隊(duì)列的應(yīng)用算法設(shè)計(jì)示例
3.2.4隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及其基本運(yùn)算算法的實(shí)現(xiàn)
3.2.5鏈隊(duì)的應(yīng)用算法設(shè)計(jì)示例
3.2.6Java中的隊(duì)列接口——QueueE
3.2.7隊(duì)列的綜合應(yīng)用
*3.2.8雙端隊(duì)列
3.2.9優(yōu)先隊(duì)列
3.3練習(xí)題
3.3.1問(wèn)答題
3.3.2算法設(shè)計(jì)題
3.4實(shí)驗(yàn)題
3.4.1上機(jī)實(shí)驗(yàn)題
3.4.2在線(xiàn)編程題
第4章串
4.1串的基本概念
4.1.1什么是串
4.1.2串的抽象數(shù)據(jù)類(lèi)型
4.2串的存儲(chǔ)結(jié)構(gòu)
4.2.1串的順序存儲(chǔ)結(jié)構(gòu)——順序串
4.2.2串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)——鏈串
4.3Java中的字符串
4.3.1String
4.3.2StringBuffer
4.4串的模式匹配
4.4.1Brute�睩orce算法
4.4.2KMP算法
4.5練習(xí)題
4.5.1問(wèn)答題
4.5.2算法設(shè)計(jì)題
4.6實(shí)驗(yàn)題
4.6.1上機(jī)實(shí)驗(yàn)題
4.6.2在線(xiàn)編程題
第5章遞歸
5.1什么是遞歸
5.1.1遞歸的定義
5.1.2何時(shí)使用遞歸
5.1.3遞歸模型
5.1.4遞歸與數(shù)學(xué)歸納法
5.1.5遞歸的執(zhí)行過(guò)程
5.1.6遞歸算法的時(shí)空分析
5.2遞歸算法的設(shè)計(jì)
5.2.1遞歸算法設(shè)計(jì)的步驟
5.2.2基于遞歸數(shù)據(jù)結(jié)構(gòu)的遞歸算法設(shè)計(jì)
5.2.3基于歸納方法的遞歸算法設(shè)計(jì)
5.3練習(xí)題
5.3.1問(wèn)答題
5.3.2算法設(shè)計(jì)題
5.4實(shí)驗(yàn)題
5.4.1上機(jī)實(shí)驗(yàn)題
5.4.2在線(xiàn)編程題
第6章數(shù)組和稀疏矩陣
6.1數(shù)組
6.1.1數(shù)組的基本概念
6.1.2數(shù)組的存儲(chǔ)結(jié)構(gòu)
6.1.3Java中的數(shù)組
6.1.4數(shù)組的應(yīng)用
6.2特殊矩陣的壓縮存儲(chǔ)
6.3稀疏矩陣
6.3.1稀疏矩陣的三元組表示
6.3.2稀疏矩陣的十字鏈表表示
6.4練習(xí)題
6.4.1問(wèn)答題
6.4.2算法設(shè)計(jì)題
6.5實(shí)驗(yàn)題
6.5.1上機(jī)實(shí)驗(yàn)題
6.5.2在線(xiàn)編程題
第7章樹(shù)和二樹(shù)
7.1樹(shù)
7.1.1樹(shù)的定義
7.1.2樹(shù)的邏輯結(jié)構(gòu)表示方法
7.1.3樹(shù)的基本術(shù)語(yǔ)
7.1.4樹(shù)的性質(zhì)
7.1.5樹(shù)的基本運(yùn)算
7.1.6樹(shù)的存儲(chǔ)結(jié)構(gòu)
7.2二樹(shù)
7.2.1二樹(shù)的概念
7.2.2二樹(shù)的性質(zhì)
7.2.3二樹(shù)的存儲(chǔ)結(jié)構(gòu)
7.2.4二樹(shù)的遞歸算法設(shè)計(jì)
7.2.5二樹(shù)的基本運(yùn)算及其實(shí)現(xiàn)
7.3二樹(shù)的先序、中序和后序遍歷
7.3.1二樹(shù)遍歷的概念
7.3.2先序、中序和后序遍歷遞歸算法
7.3.3遞歸遍歷算法的應(yīng)用
*7.3.4先序、中序和后序遍歷非遞歸算法
7.4二樹(shù)的層次遍歷
7.4.1層次遍歷過(guò)程
7.4.2層次遍歷算法設(shè)計(jì)
7.4.3層次遍歷算法的應(yīng)用
7.5二樹(shù)的構(gòu)造
7.5.1由先序/中序序列或后序/中序序列構(gòu)造二樹(shù)
*7.5.2序列化和反序列化
7.6線(xiàn)索二樹(shù)
7.6.1線(xiàn)索二樹(shù)的定義
7.6.2線(xiàn)索化二樹(shù)
7.6.3遍歷線(xiàn)索二樹(shù)
7.7哈夫曼樹(shù)
7.7.1哈夫曼樹(shù)的定義
7.7.2哈夫曼樹(shù)的構(gòu)造算法
7.7.3哈夫曼編碼
7.8二樹(shù)與樹(shù)、森林之間的轉(zhuǎn)換
7.8.1樹(shù)到二樹(shù)的轉(zhuǎn)換及還原
7.8.2森林到二樹(shù)的轉(zhuǎn)換及還原
*7.9樹(shù)算法設(shè)計(jì)和并查集
7.9.1樹(shù)算法設(shè)計(jì)
7.9.2并查集
7.10練習(xí)題
7.10.1問(wèn)答題
7.10.2算法設(shè)計(jì)題
7.11實(shí)驗(yàn)題
7.11.1上機(jī)實(shí)驗(yàn)題
7.11.2在線(xiàn)編程題
第8章圖
8.1圖的基本概念
8.1.1圖的定義
8.1.2圖的基本術(shù)語(yǔ)
8.2圖的存儲(chǔ)結(jié)構(gòu)
8.2.1鄰接矩陣
8.2.2鄰接表
8.3圖的遍歷
8.3.1圖遍歷的概念
8.3.2深度優(yōu)先遍歷
8.3.3廣度優(yōu)先遍歷
8.3.4非連通圖的遍歷
8.3.5圖遍歷算法的應(yīng)用
*8.3.6求有向圖中強(qiáng)連通分量的Tarjan算法
8.4生成樹(shù)和小生成樹(shù)
8.4.1生成樹(shù)和小生成樹(shù)的概念
8.4.2普里姆算法
8.4.3Kruskal算法
8.5短路徑
8.5.1短路徑的概念
8.5.2Dijkstra算法
8.5.3Floyd算法
8.6拓?fù)渑判?br /> 8.6.1什么是拓?fù)渑判?br /> 8.6.2拓?fù)渑判蛩惴ㄔO(shè)計(jì)
*8.6.3逆拓?fù)湫蛄泻头沁f歸深度優(yōu)先遍歷
8.7AOE網(wǎng)與關(guān)鍵路徑
8.7.1什么是AOE網(wǎng)和關(guān)鍵路徑
8.7.2求AOE網(wǎng)中關(guān)鍵路徑的算法
8.8練習(xí)題
8.8.1問(wèn)答題
8.8.2算法設(shè)計(jì)題
8.9實(shí)驗(yàn)題
8.9.1上機(jī)實(shí)驗(yàn)題
8.9.2在線(xiàn)編程題
第9章查找
9.1查找的基本概念
9.2線(xiàn)性表的查找
9.2.1順序查找
9.2.2折半查找
9.2.3索引存儲(chǔ)結(jié)構(gòu)和分塊查找
9.3樹(shù)表的查找
9.3.1二排序樹(shù)
9.3.2平衡二樹(shù)
*9.3.3Java中的TreeMap和TreeSet集合
9.3.4B-樹(shù)
9.3.5B+樹(shù)
9.4哈希表的查找
9.4.1哈希表的基本概念
9.4.2哈希函數(shù)的構(gòu)造方法
9.4.3哈希沖突的解決方法
9.4.4哈希表的查找及性能分析
*9.4.5Java中的HashMap和HashSet集合
9.5練習(xí)題
9.5.1問(wèn)答題
9.5.2算法設(shè)計(jì)題
9.6實(shí)驗(yàn)題
9.6.1上機(jī)實(shí)驗(yàn)題
9.6.2在線(xiàn)編程題
0章排序
10.1排序的基本概念
10.2插入排序
10.2.1直接插入排序
10.2.2折半插入排序
10.2.3希爾排序
10.3交換排序
10.3.1冒泡排序
10.3.2快速排序
10.4選擇排序
10.4.1簡(jiǎn)單選擇排序
10.4.2堆排序
10.4.3堆數(shù)據(jù)結(jié)構(gòu)
10.5歸并排序
10.5.1自底向上的二路歸并排序
10.5.2自頂向下的二路歸并排序
10.6基數(shù)排序
10.7各種內(nèi)排序方法的比較和選擇
10.8外排序
10.8.1生成初始?xì)w并段的方法
10.8.2多路歸并方法
10.9練習(xí)題
10.9.1問(wèn)答題
10.9.2算法設(shè)計(jì)題
10.10實(shí)驗(yàn)題
10.10.1上機(jī)實(shí)驗(yàn)題
10.10.2在線(xiàn)編程題
參考文獻(xiàn)