數(shù)據(jù)結(jié)構(gòu)與算法

第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. 4 數(shù)據(jù)結(jié)構(gòu)的圖示
1. 5 數(shù)據(jù)結(jié)構(gòu)的分類
1. 5. 1 集合
1. 5. 2 線性結(jié)構(gòu)
1. 5. 3 樹(shù)形結(jié)構(gòu)
1. 5. 4 圖狀結(jié)構(gòu)
1. 6 數(shù)據(jù)結(jié)構(gòu)的存儲(chǔ)
1. 6. 1 存儲(chǔ)器表示
1. 6. 2 存儲(chǔ)映像
1. 6. 3 基本存儲(chǔ)方法
1. 7 數(shù)據(jù)結(jié)構(gòu)的訪問(wèn)接口
1. 7. 1 訪問(wèn)接口與邏輯結(jié)構(gòu)
1. 7. 2 基本操作的種類
1. 7. 3 基本操作的實(shí)現(xiàn)
1. 8 面向?qū)ο蠓椒?br />1. 8. 1 對(duì)象與類
1. 8. 2 面向?qū)ο蠓椒ㄒ?br />1. 8. 3 面向?qū)ο蠓椒ǖ娜舾墒鲈u(píng)*
1. 8. 4 面向?qū)ο蟪绦蛟O(shè)計(jì)語(yǔ)言*
1. 9 面向?qū)ο笈c數(shù)據(jù)結(jié)構(gòu)
1. 9. 1 面向?qū)ο笈c數(shù)據(jù)結(jié)構(gòu)的關(guān)系
1. 9. 2 面向?qū)ο髷?shù)據(jù)結(jié)構(gòu)
1. 9. 3 數(shù)據(jù)結(jié)構(gòu)的對(duì)象模型
本章小結(jié)
習(xí)題
第2章 程序設(shè)計(jì)基本策略與方法
2. 1 算法
2. 1. 1 算法的概念
2. 1. 2 算法的時(shí)間復(fù)雜度與空間復(fù)雜度
2. 1. 3 算法時(shí)間復(fù)雜度的度量
2. 2 窮舉法
2. 3 遞推法與迭代法
2. 3. 1 遞推法
2. 3. 2 迭代法
2. 4 遞歸法
2. 4. 1 遞歸與遞歸程序的概念
2. 4. 2 遞歸程序設(shè)計(jì)要點(diǎn)
2. 4. 3 遞歸程序執(zhí)行機(jī)理
2. 4. 4 Hanoi塔問(wèn)題與運(yùn)行圖
2. 5 逐步求精法
2. 5. 1 基本思想
2. 5. 2 應(yīng)用示例
2. 6 分治法
2. 6. 1 基本思想
2. 6. 2 平面分治法示例--順序統(tǒng)計(jì)
2. 6. 3 迭代分治法示例--循環(huán)賽賽程安排*
本章小結(jié)
習(xí)題
第3章 線性表
3. 1 線性表的邏輯結(jié)構(gòu)
3. 1. 1 基本概念
3. 1. 2 線性表抽象模型
3. 2 線性表的順序存儲(chǔ)結(jié)構(gòu)
3. 2. 1 基本存儲(chǔ)方法
3. 2. 2 面向?qū)ο竺枋?br />3. 3 異常處理與下標(biāo)選擇器*
3. 3. 1 異常處理
3. 3. 2 下標(biāo)選擇器
3. 4 線性表的鏈?zhǔn)酱鎯?chǔ)--線性鏈表
3. 4. 1 鏈?zhǔn)酱鎯?chǔ)方法
3. 4. 2 線性鏈表的面向?qū)ο竺枋?br />3. 4. 3 線性鏈表的面向?qū)ο髮?shí)現(xiàn)
3. 5 幾種特殊線性鏈表
3. 5. 1 帶頭結(jié)點(diǎn)的鏈表
3. 5. 2 循環(huán)鏈表
3. 5. 3 雙向鏈表
3. 6 線性表應(yīng)用示例
3. 6. 1 集合運(yùn)算*
3. 6. 2 一元多項(xiàng)式相加
3. 6. 3 一元多項(xiàng)式的乘法*
本章小結(jié)
習(xí)題
第4章 特殊線性表--棧. 隊(duì)列. 串
4. 1 棧
4. 1. 1 棧的邏輯結(jié)構(gòu)
4. 1. 2 棧的順序存儲(chǔ)結(jié)構(gòu)
4. 1. 3 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
4. 2 隊(duì)列
4. 2. 1 隊(duì)列的邏輯結(jié)構(gòu)
4. 2. 2 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)
4. 2. 3 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
4. 3 串
4. 3. 1 串的邏輯結(jié)構(gòu)
4. 3. 2 串的存儲(chǔ)結(jié)構(gòu)
本章小結(jié)
習(xí)題
第5章 數(shù)組與十字鏈表
5. 1 數(shù)組
5. 1. 1 數(shù)組的定義與運(yùn)算
5. 1. 2 數(shù)組的存儲(chǔ)結(jié)構(gòu)與尋址問(wèn)題
5. 1. 3 一維數(shù)組的存儲(chǔ)與尋址
5. 1. 4 二維數(shù)組的存儲(chǔ)與尋址
5. 1. 5 多維數(shù)組的存儲(chǔ)與尋址
5. 1. 6 尋址公式的計(jì)算
5. 2 特殊數(shù)組*
5. 2. 1 對(duì)稱矩陣
5. 2. 2 下／上三角矩陣
5. 3 稀疏矩陣
5. 3. 1 稀疏矩陣的邏輯表示
5. 3. 2 三元組表存儲(chǔ)法
5. 3. 3 三元組表的操作
5. 3. 4 轉(zhuǎn)置操作
5. 4 十字鏈表
5. 4. 1 存儲(chǔ)方式
5. 4. 2 十字鏈表對(duì)象
5. 4. 3 基本操作的實(shí)現(xiàn)
本章小結(jié)
習(xí)題
第6章 樹(shù)形結(jié)構(gòu)
6. 1 樹(shù)形結(jié)構(gòu)的基本概念
6. 1. 1 樹(shù)形結(jié)構(gòu)的定義
6. 1. 2 基本術(shù)語(yǔ)
6. 2 二叉樹(shù)
6. 2. 1 二叉樹(shù)的基本概念
6. 2. 2 幾種特殊二叉樹(shù)
6. 2. 3
叉樹(shù)的基本性質(zhì)
6. 2. 4
叉樹(shù)的遍歷
6. 3
叉樹(shù)的存儲(chǔ)結(jié)構(gòu)
6. 3. 1 順序存儲(chǔ)結(jié)構(gòu)
6. 3. 2 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)
6. 4 二樹(shù)對(duì)象模型
6. 4. 1
叉樹(shù)結(jié)點(diǎn)對(duì)象
6. 4. 2 二叉樹(shù)對(duì)象
6. 5 二叉樹(shù)的遍歷操作
6. 5. 1 前序遍歷操作
6. 5. 2 中序遍歷操作
6. 5. 3 后序遍歷操作
6. 6
叉樹(shù)的解析表示與存儲(chǔ)結(jié)構(gòu)之間的轉(zhuǎn)化
6. 6. 1 雙遍歷結(jié)果轉(zhuǎn)化為樹(shù)
6. 6. 2 根據(jù)廣義表表示創(chuàng)建樹(shù)
6. 6. 3 根據(jù)存儲(chǔ)結(jié)構(gòu)創(chuàng)建廣義表*
6. 6. 4 根據(jù)前序擴(kuò)展序列創(chuàng)建樹(shù)*
6. 7 二叉樹(shù)的線索化
6. 7. 1 線索化的概念
6. 7. 2 線索化算法
6. 8 樹(shù)與森林
6. 8. 1 樹(shù)與森林的遍歷
6. 8. 2 樹(shù). 森林與二叉樹(shù)之間的轉(zhuǎn)化
6. 8. 3 樹(shù)的存儲(chǔ)結(jié)構(gòu)
6. 9 樹(shù)對(duì)象模型*
6. 9. 1 樹(shù)結(jié)點(diǎn)對(duì)象
6. 9. 2 樹(shù)類
6. 10 樹(shù)的應(yīng)用示例--哈夫曼樹(shù)
6. 10. 1 哈夫曼樹(shù)的基本概念
6. 10. 2 哈夫曼樹(shù)構(gòu)造算法
6. 10. 3 哈夫曼樹(shù)構(gòu)造算法的實(shí)現(xiàn)
6. 10. 4 哈夫曼判定樹(shù)
6. 10. 5 哈夫曼編碼與數(shù)據(jù)壓縮
本章小結(jié)
習(xí)題
第7章 圖結(jié)構(gòu)
7. 1 圖的基本概念
7. 1. 1 圖的概念
7. 1. 2 圖的基本操作
7. 2 圖的對(duì)象抽象模型
7. 2. 1 圖結(jié)點(diǎn)抽象模型
7. 2. 2 圖的邊對(duì)象抽象模型
7. 2. 3 圖抽象對(duì)象模型
7. 3 圖的存儲(chǔ)結(jié)構(gòu)
7. 3. 1 鄰接矩陣法
7. 3. 2 鄰接表
7. 3. 3 十字鏈表*
7. 3. 4 鄰接多重表*
7. 4 圖的遍歷
7. 4. 1 概述
7. 4. 2 深度優(yōu)先遍歷
7. 4. 3 深度優(yōu)先遍歷的性質(zhì)
7. 4. 4 廣度優(yōu)先遍歷
7. 4. 5 廣度優(yōu)先遍歷的性質(zhì)
7. 5 拓?fù)渑判?br />7. 5. 1 拓?fù)湫蛄信cAOV網(wǎng)
7. 5. 2 拓?fù)渑判蛩惴ㄅc實(shí)現(xiàn)
7. 6 AOE網(wǎng)與關(guān)鍵路徑
7. 6. 1 AOE網(wǎng)與關(guān)鍵路徑的概念
7. 6. 2 關(guān)鍵路徑的識(shí)別
本章小結(jié)
習(xí)題
第8章 廣義表
8. 1 廣義表的邏輯結(jié)構(gòu)
8. 1. 1 基本概念
8. 1. 2 廣義表邏輯圖
8. 1. 3 廣義表的遍歷
8. 1. 4 基本特性
8. 1. 5 基本操作
8. 2 廣義表的存儲(chǔ)結(jié)構(gòu)
8. 2. 1 基本存儲(chǔ)方法
8. 2. 2 鏈?zhǔn)浇Y(jié)構(gòu)的高級(jí)語(yǔ)言描述
8. 3 廣義表對(duì)象模型*
8. 3. 1 廣義表元素接口
8. 3. 2 廣義表接口
8. 4 廣義表的分支單鏈表對(duì)象*
8. 4. 1 結(jié)點(diǎn)對(duì)象
8. 4. 2 分支單鏈表對(duì)象
8. 5 廣義表操作的實(shí)現(xiàn)*
8. 5. 1 一般問(wèn)題
8. 5. 2 遍歷操作
8. 5. 3 廣義表統(tǒng)計(jì)計(jì)數(shù)
8. 5. 4 廣義表的串行化與逆串行化
8. 5. 5 廣義表的復(fù)制與求尾
8. 6 廣義表結(jié)構(gòu)的應(yīng)用
8. 6. 1 多元多項(xiàng)式的表示
8. 6. 2 層次結(jié)構(gòu)的表示
本章小結(jié)
習(xí)題
第9章 檢索結(jié)構(gòu)
9. 1 概述
9. 1. 1 檢索的概念
9. 1. 2 檢索結(jié)構(gòu)
9. 1. 3 檢索算法的時(shí)間與空間復(fù)雜度分析
9. 1. 4 檢索算法的判定樹(shù)
9. 2 線性結(jié)構(gòu)的檢索
9. 2. 1 順序檢索
9. 2. 2 折半檢索
9. 2. 3 斐波刀口契檢索*
9. 2. 4 插值檢索*
9. 3 線性索引結(jié)構(gòu)
9. 3. 1 概述
9. 3. 2 稠密索引
9. 3. 3 分塊索引
9. 4 樹(shù)形索引結(jié)構(gòu)與二叉排序樹(shù)
9. 4. 1 樹(shù)形索引結(jié)構(gòu)概述
9. 4. 2 二叉排序樹(shù)的概念
9. 4. 3 二叉排序樹(shù)的檢索
9. 4. 4 二叉排序樹(shù)的插入*
9. 4. 5 二叉排序樹(shù)的刪除*
9. 4. 6 二叉排序樹(shù)的分析與最優(yōu)二叉排序樹(shù)*
9. 5 平衡二叉排序樹(shù)*
9. 5. 1 基本概念
9. 5. 2 若干性質(zhì)
9. 5. 3 局部平衡調(diào)整算法
9. 6 B樹(shù)
9. 6. 1 B樹(shù)的概念
9. 6. 2 B樹(shù)的存儲(chǔ)結(jié)構(gòu)
9. 6. 3 B樹(shù)的基本操作
9. 6. 4 B樹(shù)的檢索方法
9. 6. 5 B樹(shù)的插入
9. 6. 6 B樹(shù)的刪除
9. 6. 7 B 樹(shù)
9. 6. 8 B樹(shù)對(duì)象模型
9. 7 散列結(jié)構(gòu)
9. 7. 1 概念
9. 7. 2 散列技術(shù)中的主要問(wèn)題
9. 7. 3 散列過(guò)程
9. 7. 4 散列函數(shù)的設(shè)計(jì)
9. 7. 5 沖突解決
本章小結(jié)
習(xí)題
第10章 外存與文件組織
10. 1 外存結(jié)構(gòu)
10. 1. 1 外存簡(jiǎn)介
10. 1. 2 磁帶結(jié)構(gòu)
10. 1. 3 磁盤(pán)結(jié)構(gòu)
10. 2 文件
10. 2. 1 文件的概念
10. 2. 2 文件操作與存取方式
10. 2. 3 文件的物理組織
10. 2. 4 緩沖技術(shù)
10. 3 順序文件
10. 4 索引文件
10. 5 ISAM*
10. 5. 1 ISAM的概念
10. 5. 2 ISAM結(jié)構(gòu)的操作
10. 6 VSAM
10. 6. 1 VSAM的概念
10. 6. 2 VSAM結(jié)構(gòu)的操作
10. 7 散列方式
10. 8 多索引文件
10. 8. 1 多重表文件
10. 8. 2 倒排文件
本章小結(jié)
習(xí)題
第11章 排序算法
11. 1 概述
11. 2 插入排序
11. 2. 1 直接插入排序
11. 2. 2 其他插入排序算法
11. 3 交換排序
11. 3. 1 冒泡排序,
11. 3. 2 冒泡算法的改進(jìn)
11. 3. 3 快速排序*
11. 4 選擇排序
11. 4. 1 直接選擇排序
11. 4. 2 堆排序
11. 5 歸并排序
11. 5. 1 二路合并
11. 5. 2 多段二路合并
11. 5. 3 二路歸并排序
11. 6 外排序簡(jiǎn)介
本章小結(jié)
習(xí)題
第12章 算法設(shè)計(jì)基本方法
12. 1 回溯法與限界剪枝法
12. 1. 1 基本思想
12. 1. 2 迷宮問(wèn)題
12. 1. 3 穩(wěn)定婚姻問(wèn)題*
12. 1. 4 n皇后問(wèn)題
12. 1. 5 限界剪枝法簡(jiǎn)介*
12. 2 動(dòng)態(tài)規(guī)劃法
12. 2. 1 動(dòng)態(tài)規(guī)劃法要素與最優(yōu)性原理
12. 2. 2 最長(zhǎng)公共子序列
12. 2. 3 流水線調(diào)度問(wèn)題*
12. 2. 4 多源最短路徑的Floyd算法
12. 2. 5 0-1背包問(wèn)題
12. 3 貪心法
12. 3. 1 基本思想
12. 3. 2 背包問(wèn)題
12. 3. 3 Prim最小生成樹(shù)算法
12. 3. 4 Kruskal最小生成樹(shù)算法
12. 3. 5 單源最短路徑
12. 3. 6 貪心法要素總結(jié)
本章小結(jié)
習(xí)題
詞匯索引
參考文獻(xiàn)