數據結構與算法

第1章 概論.
1.1 為什么要學習數據結構
1.2 什么是數據結構
1.2.1 數據的邏輯結構
1.2.2 數據的存儲結構
1.3 抽象數據類型
1.4 算法及其特性
1.4.1 算法
1.4.2 計算復雜性和算法的效率
1.5 算法的執(zhí)行效率及其度量
1.5.1 算法的漸進分析
1.5.2 最壞.最好和平均情況
1.5.3 時間和空間資源開銷
1.5.4 大Θ表示法及其分析規(guī)則
1.6 數據結構的選擇和評價
習題 第2章 線性表.棧和隊列
2.1 線性表
2.1.1 線性表的抽象數據類型
2.1.2 線性表的存儲結構
2.1.3 線性表運算分類
2.2 順序表——向量
2.2.1 向量的類定義
2.2.2 向量的運算
2.3 鏈表
2.3.1 單鏈表
2.3.2 雙鏈表
2.3.3 循環(huán)鏈表
2.4 線性表實現方法的比較
2.5 棧
2.5.1 順序棧
2.5.2 鏈式棧
2.5.3 棧的應用——計算表達式的值
2.5.4 棧與遞歸
2.6 隊列
2.6.1 順序隊列
2.6.2 鏈式隊列
2.6.3 順序隊列與鏈式隊列的比較
習題 第3章 字符串
3.1 字符串抽象數據類型
3.1.1 基本概念
3.1.2 String抽象數據類型
3.2 字符串的存儲結構和類定義
3.2.1 字符串的順序存儲
3.2.2 字符串類classString的存儲結構
3.3 字符串運算的算法實現
3.3.1 C++標準串運算的實現
3.3.2 String串運算的實現
3.4 字符串的模式匹配
3.4.1 模式匹配原始算法
3.4.2 字符串的特征向量N
3.4.3 KMP模式匹配算法
習題 上機題
第4章 二叉樹
4.1 二叉樹的概念
4.1.1 二叉樹的定義及相關概念
4.1.2 滿二叉樹.完全二叉樹和擴充二叉樹
4.2 二叉樹的主要性質
4.3 二叉樹的抽象數據類型
4.4 周游二叉樹
4.4.1 深度優(yōu)先周游二叉樹
4.4.2 廣度優(yōu)先周游二叉樹
4.5 二叉樹的實現
4.5.1 用指針實現二叉樹
4.5.2 空間開銷
4.5.3 用數組實現完全二叉樹
4.5.4 穿線二叉樹
4.6 二叉搜索樹
4.7 堆與優(yōu)先隊列
4.8 Huffman編碼樹
4.8.1 建立Huffman編碼樹
4.8.2 Huffman編碼及其用法
習題 上機題
第5章 樹
5.1 樹的概念
5.1.1 樹和森林
5.1.2 森林與二叉樹的等價轉換
5.1.3 樹的抽象數據類型
5.1.4 樹的周游
5.2 樹的鏈式存儲
5.2.1 子結點表表示法
5.2.2 左子結點/右兄弟結點表示法
5.2.3 動態(tài)結點表示法
5.2.4 動態(tài)“左子結點/右兄弟結點”二叉鏈表表示法
5.2.5 父指針表示法及等價類的并查算法
5.3 樹的順序存儲
5.3.1 帶右鏈的先根次序表示法
5.3.2 帶雙標記位的先根次序表示法
5.3.3 帶左鏈的層次次序表示法
5.3.4 帶度數的后根次序表示法
5.4K 叉樹
習題 上機題
第6章圖
6.1 圖的基本概念
6.2 圖的抽象數據類型
6.3 圖的存儲結構
6.3.1 圖的相鄰矩陣表示法
6.3.2 圖的鄰接表表示法
6.4 圖的周游..
6.4.1 深度優(yōu)先搜索
6.4.2 廣度優(yōu)先搜索
6.4.3 拓撲排序
6.5 最短路徑問題
6.5.1 單源最短路徑
6.5.2 每對頂點間的最短路徑
6.6 最小支撐樹
6.6.1 Prim算法
6.6.2 Kruskal算法
習題 上機題
第7章 內排序
7.1 排序問題的基本概念
7.2 三種O(n2)的簡單排序算法
7.2.1 插入排序
7.2.2 冒泡排序
7.2.3 直接選擇排序
7.2.4 簡單排序算法的時間代價對比
7.3 Shell排序
7.4 基于分治法的排序
7.4.1 快速排序
7.4.2 歸并排序
7.5 堆排序
7.6 分配排序和基數排序
7.6.1 桶式排序
7.6.2 基數排序
7.7 各種排序算法的理論和實驗時間代價
7.8 排序問題的下限
習題 上機題
第8章 文件管理和外排序
8.1 主存儲器和外存儲器
8.2 外存儲器
8.2.1 磁盤
8.2.2 磁盤訪問時間估算
8.2.3 磁帶
8.3 外存文件的組織
8.3.1 文件組織
8.3.2 C++的流文件
8.4 緩沖區(qū)和緩沖池
8.5 外排序
8.5.1 置換選擇排序
8.5.2 二路外排序
8.5.3 多路歸并——選擇樹
習題 上機題
第9章 檢索
9.1 基于線性表的檢索
9.1.1 順序檢索
9.1.2 二分檢索
9.1.3 分塊檢索
9.2 集合的檢索
9.2.1 集合的數學特性
9.2.2 計算機中的集合
9.3 散列方法
9.3.1 散列函數
9.3.2 開散列方法(拉鏈法)
9.3.3 閉散列方法(開地址法)
9.3.4 閉散列表的算法
9.3.5 散列方法的效率分析
習題 上機題
第10章 索引技術
10.1 線性索引
10.2 靜態(tài)索引
10.2.1 多分樹
10.2.2 ISAM-索引順序存取方法
10.3 倒排索引
10.3.1 基于屬性的倒排
10.3.2 對正文文件的倒排
10.4 動態(tài)索引
10.4.1 B樹
10.4.2 B+樹
10.4.3 VSAM
10.4.4 B樹的性能分析
10.5 動態(tài)索引和靜態(tài)索引性能的比較
習題 上機題
第11章 高級線性結構
11.1 多維數組
11.1.1 特殊矩陣
11.1.2 稀疏矩陣
11.2 廣義表
11.2.1 廣義表的存儲結構
11.2.2 廣義表的周游算法
11.3 存儲管理技術
11.3.1 可利用空間表
11.3.2 存儲的動態(tài)分配和回收
11.3.3 伙伴系統
11.3.4 失敗處理策略和無用單元回收
習題 上機題
第12章 高級樹結構
12.1 Trie結構和Patricia樹
12.2 改進的二叉搜索樹
12.2.1 最佳二叉搜索樹
12.2.2 平衡的二叉搜索樹
12.2.3 伸展樹
12.3 空間樹結構
12.3.1 k-d樹
12.3.2 PR四分樹
12.3.3 R*樹
12.4 樹形結構的應用
12.4.1 決策樹
12.4.2 博弈樹
習題
上機題
參考文獻