數(shù)據(jù)結構

前言
第1章 緒論
本章要點
1.1 數(shù)據(jù)結構的概念及分類
1.1.1 數(shù)據(jù)與數(shù)據(jù)結構
1.1.2 數(shù)據(jù)結構的分類
1.2 抽象數(shù)據(jù)類型及面向對象概念
1.2.1 數(shù)據(jù)類型
1.2.2 數(shù)據(jù)抽象與抽象數(shù)據(jù)類型
1.2.3 面向對象的概念
1.2.4 用于描述數(shù)據(jù)結構的語言
1.3 算法定義
1.4 算法性能分析與度量
1.4.1 算法的性能標準
1.4.2 算法的后期測試
1.4.3 算法的事前估計
1.4.4 漸進的時間復雜度
1.4.5 漸進的空間復雜度
小結
習題
第2章 數(shù)組
本章要點
2.1 作為抽象數(shù)據(jù)類型的數(shù)組
2.1.1 在C＋＋中數(shù)組的定義和初始化
2.1.2 作為抽象數(shù)據(jù)類型的數(shù)組
2.1.3 數(shù)組的順序存儲方式
2.2 順序表
2.2.1 線性表的概念
2.2.2 順序表的定義和特點
2.2.3 順序表的搜索、插入和刪除
2.2.4 作為抽象數(shù)據(jù)類型，使用順序表的事例
2.3 稀疏矩陣
2.3.1 稀疏矩陣的抽象數(shù)據(jù)類型
2.3.2 稀疏矩陣的壓縮表示
2.4 字符串
2.4.1 字符串抽象數(shù)據(jù)類型和類定義
2.4.2 字符串操作的實現(xiàn)
小結
習題
第3章 鏈表
本章要點
3.1 單鏈表
3.1.1 單鏈表的概念
3.1.2 單鏈表的類定義
3.1.3 單鏈表中的插入與刪除
3.1.4 帶表頭結點的單鏈表
3.1.5 單鏈表的模板類
3.1.6 靜態(tài)鏈表
3.2 循環(huán)鏈表
3.3 多項式及其相加
3.3.1 多項式抽象數(shù)據(jù)類型與*this指針
3.3.2 多項式的表示
3.3.3 多項式的加法
3.4 雙向鏈表
3.4.1 雙向鏈表的概念
3.4.2 帶表頭結點的雙向循環(huán)鏈表
3.4.3 雙向循環(huán)鏈表的搜索、插入和刪除算法
3.5 稀疏矩陣
小結
習題
第4章 棧和隊列
本章要點
4.1 棧
4.1.1 棧的定義
4.1.2 順序?！獥５臄?shù)組存儲表示
4.1.3 鏈式?！獥５逆溄哟鎯Ρ硎?br />4.2 表達式的計算
4.2.1 表達式
4.2.2 應用后綴表示計算表達式的值
4.2.3 中綴表示與其他表示之間的轉換
4.3 隊列
4.3.1 隊列的定義
4.3.2 循環(huán)隊列——隊列的順序存儲表示
4.3.3 鏈式隊列——隊列的鏈接存儲表示
4.3.4 隊列的應用舉例——打印二項展開式（a＋b）i的系數(shù)
4.4 優(yōu)先級隊列
4.4.1 優(yōu)先級隊列的定義
4.4.2 優(yōu)先級隊列的存儲表示和實現(xiàn)
小結
習題
第5章 遞歸
本章要點
5.1 遞歸的概念
5.2 遞歸過程與遞歸工作棧
5.2.1 遞歸工作棧
5.2.2 用棧實現(xiàn)遞歸過程的非遞歸算法
5.2.3 用迭代法實現(xiàn)遞歸過程
5.3 用回溯法求解迷宮問題
5.4 廣義表
5.4.1 廣義表的概念
5.4.2 廣義表的表示及操作
5.4.3 廣義表存儲結構的實現(xiàn)
5.4.4 廣義表的遞歸算法
小結
習題
第6章 樹與森林
本章要點
6.1 樹和森林的概念
6.1.1 樹的定義
6.1.2 樹的術語
6.1.3 樹的抽象數(shù)據(jù)類型
6.2 二叉樹
6.2.1 二叉樹的定義
6.2.2 二叉樹的性質(zhì)
6.2.3 二叉樹的抽象數(shù)據(jù)類型
6.2.4 二叉樹的表示
6.3 遍歷二叉樹
6.3.1 遍歷二叉樹的遞歸算法
6.3.2 應用遍歷二叉樹的事例
6.3.3 遍歷二叉樹的非遞歸算法
6.3.4 二叉樹的計數(shù)
6.4 線索化二叉樹
6.4.1 線索
6.4.2 中序線索化二叉樹
6.5 堆
6.5.1 堆的定義
6.5.2 堆的建立
6.5.3 堆的插入與刪除
6.6 樹與森林
6.6.1 樹的存儲表示
6.6.2 森林與二叉樹的轉換
6.6.3 樹的遍歷
6.6.4 森林的遍歷
6.7 霍夫曼樹
6.7.1 路徑長度
6.7.2 霍夫曼樹
6.7.3 霍夫曼編碼
小結
習題
第7章 集合與搜索
本章要點
7.1 集合及其表示
7.1.1 集合基本概念
7.1.2 用位向量實現(xiàn)集合抽象數(shù)據(jù)類型
7.1.3 用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型
7.1.4 并查集
7.2 靜態(tài)搜索表
7.2.1 搜索的概念
7.2.2 靜態(tài)搜索結構
7.2.3 順序搜索
7.2.4 基于有序順序表的折半搜索
7.3 二叉搜索樹
7.3.1 定義
7.3.2 二叉搜索樹上的搜索
7.3.3 二叉搜索樹的插入
7.3.4 二叉搜索樹的刪除
7.3.5 二叉搜索樹的搜索效率
7.4 AVL樹
7.4.1 AVL樹的定義
7.4.2 平衡化旋轉
7.4.3 AVL樹的插入和刪除
7.4.4 AVL樹的高度
小結
習題
第8章 圖
本章要點
8.1 圖的基本概念
8.1.1 圖的基本概念
8.1.2 圖的抽象數(shù)據(jù)類型
8.2 圖的存儲表示
8.2.1 鄰接矩陣
8.2.2 鄰接表
8.2.3 鄰接多重表
8.3 圖的遍歷與連通性
8.3.1 深度優(yōu)先搜索
8.3.2 廣度優(yōu)先搜索
8.3.3 連通分量
8.3.4 重連通分量
8.3.5 圖的遍歷舉例：歐拉回路問題
8.4 最小生成樹
8.4.1 克魯斯卡爾算法
8.4.2 普里姆算法
8.5 單源最短路徑問題
8.6 活動網(wǎng)絡（activity network）
8.6.1 用頂點表示活動的網(wǎng)絡
8.6.2 用邊表示活動的網(wǎng)絡
小結
習題
第9章 排序
本章要點
9.1 概述
9.2 插入排序
9.2.1 直接插入排序
9.2.2 折半插入排序
9.2.3 鏈表插入排序
9.2.4 希爾排序
9.3 交換排序
9.3.1 起泡排序
9.3.2 快速排序
9.4 選擇排序
9.4.1 直接選擇排序
9.4.2 錦標賽排序
9.4.3 堆排序
9.5 歸并排序
9.5.1 歸并
9.5.2 迭代的歸并排序算法
9.5.3 遞歸的鏈表歸并排序
9.6 基數(shù)排序
9.6.1 多排序碼排序
9.6.2 鏈式基數(shù)排序
9.7 外排序
9.7.1 外排序的基本過程
9.7.2 k路平衡歸并與敗者樹
9.7.3 初始歸并段的生成
9.7.4 最佳歸并樹
小結
習題
第10章 索引與散列
本章要點
10.1 靜態(tài)索引結構
10.1.1 線性索引
10.1.2 倒排表
10.1.3 m路靜態(tài)搜索樹
10.2 動態(tài)索引結構
10.2.1 動態(tài)的m路搜索樹
10.2.2 B樹
10.2.3 B樹的插入
10.2.4 B樹的刪除
10.2.5 B＋樹
10.3 散列
10.3.1 詞典的抽象數(shù)據(jù)類型
10.3.2 散列表與散列方法
10.3.3 散列函數(shù)
10.3.4 處理沖突的閑散列方法
10.3.5 處理沖突的開散列方法——鏈地址法
10.3.6 散列表分析
10.4 可擴充散列
10.4.1 二叉Trie樹
10.4.2 將二叉Trie樹轉換為目錄表
10.4.3 目錄表擴充與收縮
10.4.4 性能分析
小結
習題
附錄A 用C＋＋描述面向對象程序
A.1 用模板定義C＋＋中的類
A.2 類中成員函數(shù)的實現(xiàn)
A.3 函數(shù)名重載和操作符重載
A.4 C＋＋中的主函數(shù)
附錄B 教學進度與習題安排參考
附錄C 詞匯索引
參考文獻