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

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