數(shù)據(jù)結(jié)構(gòu)（C++版）

第0章 預(yù)備知識(shí)
0.1    數(shù)學(xué)預(yù)備知識(shí)
0.1.1    常用數(shù)學(xué)術(shù)語
0.1.2    對(duì)數(shù)
0.1.3    級(jí)數(shù)求和
0.2    常用數(shù)學(xué)證明方法
0.2.1    反證法
0.2.2    數(shù)學(xué)歸納法
0.3    離散數(shù)學(xué)預(yù)備知識(shí)
0.3.1    集合
0.3.2    謂詞
0.3.3    關(guān)系
0.4    C++程序設(shè)計(jì)語言預(yù)備知識(shí)
0.4.1    程序結(jié)構(gòu)
0.4.2    變量、常量與數(shù)據(jù)類型
0.4.3    控制語句
0.4.4    函數(shù)
0.4.5    繼承與派生
0.4.6    多態(tài)與虛函數(shù)
0.4.7    模板
0.4.8    動(dòng)態(tài)存儲(chǔ)分配
0.4.9    輸入與輸出
0.4.10    異常處理
第1章 緒論
1.1    數(shù)據(jù)結(jié)構(gòu)的興起和發(fā)展
1.2    數(shù)據(jù)結(jié)構(gòu)的研究對(duì)象
1.3    數(shù)據(jù)結(jié)構(gòu)的基本概念
1.3.1    數(shù)據(jù)結(jié)構(gòu)
1.3.2    數(shù)據(jù)結(jié)構(gòu)的訪問窗口
1.3.3    抽象數(shù)據(jù)類型
1.4    算法及算法分析
1.4.1    算法
1.4.2    算法分析
1.5    案例綜棕
習(xí)題1
思考題1
第2章 線性表
2.1    線性表的邏輯結(jié)構(gòu)
2.1.1    線性表的定義
2.1.2    線性表的抽象數(shù)據(jù)類型定義
2.2    線性表的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
2.2.1    線性表的順序存儲(chǔ)結(jié)構(gòu)——順序表
2.2.2    順序表的實(shí)現(xiàn)
2.3    線性表的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
2.3.1    線性表的鏈接存儲(chǔ)結(jié)構(gòu)——單鏈表
2.3.2    單鏈表的實(shí)現(xiàn)
2.4    順序表和單鏈表的比較
2.4.1    時(shí)間性能比較
2.4.2    空間性能比較
2.5    線性表的其他存儲(chǔ)方法
2.5.1    循環(huán)鏈表
2.5.2    雙鏈表
2.5.3    靜態(tài)鏈表
2.5.4    間接尋址
2.6    應(yīng)用舉例
2.6.1    順序表的應(yīng)用舉例——符號(hào)表
2.6.2    單鏈表的應(yīng)用舉例——一元多項(xiàng)式求和
2.6.3    高校學(xué)籍管理
習(xí)題2
思考題2
第3章 特殊線性表——棧、隊(duì)列和中
3.1    棧
3.1.1    棧的邏輯結(jié)構(gòu)
3.1.2    棧的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
3.1.3    棧的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
3.1.4    順序棧和鏈棧的比較
3.2    隊(duì)列
3.2.1    隊(duì)列的邏輯結(jié)構(gòu)
3.2.2    隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
3.2.3    隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
3.2.4    循環(huán)隊(duì)列和鏈隊(duì)列的比較
3.3    串
3.3.1    串的邏輯結(jié)構(gòu)
3.3.2    串的存儲(chǔ)結(jié)構(gòu)
3.3.3    模式匹配
3.4    應(yīng)用舉例
3.4.1    棧的應(yīng)用舉例——遞歸
3.4.2    隊(duì)列的應(yīng)用舉例——火車車廂重排
3.4.3    串的應(yīng)用舉例——愷撒密碼
3.4.4    高校實(shí)驗(yàn)任務(wù)安排問題
習(xí)題3
思考題3
第4章 廣義線性表——多維數(shù)組和廣義表
4.1    多維數(shù)組
4.1.1    數(shù)組的定義
4.1.2    數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址
4.2    矩陣的壓縮存儲(chǔ)
4.2.1    特殊矩陣的壓縮存儲(chǔ)
4.2.2    稀疏矩陣的壓縮存儲(chǔ)
4.3    廣義表
4.3.1    廣義表的邏輯結(jié)構(gòu)
4.3.2    廣義表的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
4.4    應(yīng)用舉例
4.4.1    數(shù)組的應(yīng)用舉例——魔方陣
4.4.2    本科生選導(dǎo)師問題
習(xí)題4
思考題4
第5章 樹和二叉樹
5.1    樹的邏輯結(jié)構(gòu)
5.1.1    樹的定義和基本術(shù)語
5.1.2    樹的抽象數(shù)據(jù)類型定義
5.1.3    樹的遍歷操作
5.2    樹的存儲(chǔ)結(jié)構(gòu)
5.2.1    雙親表示法
5.2.2    孩子表示法
5.2.3    雙親孩子表示法
5.2.4    孩子兄弟表示法
5.3    二叉樹的邏輯結(jié)構(gòu)
5.3.1    二叉樹的定義
5.3.2    二叉樹的基本性質(zhì)
5.3.3    二叉樹的抽象數(shù)據(jù)類型定義
5.3.4    二叉樹的遍歷操作
5.4    二叉樹的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
5.4.1    順序存儲(chǔ)結(jié)構(gòu)
5.4.2    二叉樹表
5.4.3    三叉樹表
5.4.4    線索鏈表
5.5    樹、森林與二叉樹的轉(zhuǎn)換
5.6    應(yīng)用舉例
5.6.1    二叉樹的應(yīng)用舉例——哈夫曼樹及哈夫曼編碼
5.6.2    樹的應(yīng)用舉例——8枚硬幣問題
5.6.3    高校學(xué)生會(huì)組織機(jī)構(gòu)的管理
習(xí)題5
思考題5
第6章 圖
6.1    圖的邏輯結(jié)構(gòu)
6.1.1    圖的定義和基本術(shù)語
6.1.2    圖的抽象數(shù)據(jù)類型定義
6.1.3    圖的遍歷操作
6.2    圖的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)
6.2.1    鄰接矩陣
6.2.2    鄰接表
6.2.3    十字鏈表
6.2.4    鄰接多重表
6.2.5    邊集數(shù)組
6.2.6    圖的存儲(chǔ)結(jié)構(gòu)的比較
6.3    圖的連通性
6.3.1    無向圖的連通性
6.3.2    有向圖的連通性
6.3.3    生成樹和生成森林
6.4    應(yīng)用舉例
6.4.1    最小生成樹
6.4.2    最短路徑
6.4.3    AOV網(wǎng)與拓?fù)渑判?br />6.4.4    AOE網(wǎng)與關(guān)鍵路徑
6.4.5    校園最短路徑問題
習(xí)題6
思考題6
第7章 查找技術(shù)
7.1    概述
7.1.1    查找的基本概念
7.1.2    查找算法的性能
7.2    線性表的查找技術(shù)
7.2.1    順序查找
7.2.2    折半查找
7.2.3    斐波那契查找
7.2.4    插值查找
7.3    樹表的查找技術(shù)
7.3.1    二叉排序樹
7.3.2    平衡二叉樹
7.4    散列表的查找技術(shù)
7.4.1    概述
7.4.2    散列函數(shù)的設(shè)計(jì)
7.4.3    處理沖突的方法
7.4.4    散列查找的性能分析
7.4.5    開散列表與閉散列表的比較
習(xí)題7
思考題7
第8章 排序技術(shù)
8.1    概述
8.1.1    排序的基本概念
8.1.2    排序算法的性能
8.2    插入排序
8.2.1    直接插入排序
8.2.2    希爾排序
8.3    交換排序
8.3.1    起泡排序
8.3.2    快速排序
8.4    選擇排序
8.4.1    簡(jiǎn)單選擇排序
8.4.2    堆排序
8.5    歸并排序
8.5.1    二路歸并排序的非遞歸實(shí)現(xiàn)
8.5.2    二路歸并排序的遞歸實(shí)現(xiàn)
8.6    各種排序方法的比較
習(xí)題8
思考題8
第9章 索引技術(shù)
9.1    索引的基本概念
9.2    線性索引技術(shù)
9.2.1    稠密索引
9.2.2    分塊索引
9.2.3    多重表
9.2.4    倒排表
9.3    樹形索引
9.3.1    2-3樹
9.3.2    B_樹
9.3.3    B+樹
習(xí)題9
參考文獻(xiàn)