數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)指南與題解

第1章 概論
1.1 基本概念
1.1.1 數(shù)據(jù)的有關(guān)概念
1.1.2 數(shù)據(jù)結(jié)構(gòu)的有關(guān)概念
1.1.3 算法的有關(guān)概念
1.2 基本理論
1.2.1 數(shù)據(jù)結(jié)構(gòu)的研究目的和研究內(nèi)容
1.2.2 邏輯結(jié)構(gòu)的4種基本形態(tài)及特點(diǎn)
1.2.3 引入抽象數(shù)據(jù)類型概念的好處
1.2.4 邏輯結(jié)構(gòu)的特點(diǎn)及意義
1.2.5 算法的特征及設(shè)計(jì)要求
1.2.6 算法的計(jì)算量的含義及估算的方法
1.2.7 數(shù)據(jù)的存儲方式
1.2.8 算法的分類
1.2.9 數(shù)據(jù)結(jié)構(gòu)的評價(jià)和選擇
1.3 典型例題
1.4 習(xí)題
第2章 線性表
2.1 基本概念
2.1.1 順序線性表的有關(guān)概念
2.1.2 鏈?zhǔn)骄€性表的有關(guān)概念
2.2 基本理論
2.2.1 線性結(jié)構(gòu)的基本特征
2.2.2 線性表的特點(diǎn)
2.2.3 線性表典型的基本運(yùn)算
2.2.4 順序表示法的基本思想和特點(diǎn)
2.2.5 單鏈表設(shè)置頭結(jié)點(diǎn)的作用
2.2.6 線性表的定位運(yùn)算與算法
2.2.7 單鏈表插入運(yùn)算的算法實(shí)現(xiàn)
2.2.8 單鏈表的數(shù)據(jù)域和指針域的作用
2.2.9 循環(huán)鏈表和雙鏈表的組織方法
2.2.10 線性表的插入運(yùn)算與算法
2.2.11 線性表的刪除運(yùn)算與算法
2.2.12 順序表的類C語言描述
2.2.13 單鏈表的類C語言描述
2.2.14 單鏈表定位運(yùn)算的算法實(shí)現(xiàn)
2.2.15 單鏈表刪除運(yùn)算的算法實(shí)現(xiàn)
2.2.16 鏈表的組織方法和特點(diǎn)
2.2.17 順序表的主要優(yōu)缺點(diǎn)
2.2.18 鏈表的豐要優(yōu)點(diǎn)和缺點(diǎn)
2.2.19 頭指針、頭結(jié)點(diǎn)、首結(jié)點(diǎn)的區(qū)別
2.2.20 線性表的索引存儲結(jié)構(gòu)及其優(yōu)點(diǎn)
2.2.21 靜態(tài)鏈表的用途和構(gòu)造方法
2.3 典型例題
2.4 習(xí)題
第3章 棧和隊(duì)列
3.1 基本概念
3.1.1 棧的有關(guān)概念
3.1.2 隊(duì)列的有關(guān)概念
3.2 基本理論
3.2.1 棧的基本運(yùn)算
3.2.2 棧的基本特點(diǎn)
3.2.3 順序棧的組織方法
3.2.4 順序棧上初始化的算法
3.2.5 進(jìn)棧和退棧運(yùn)算在順序棧上的實(shí)現(xiàn)算法
3.2.6 鏈棧上實(shí)現(xiàn)進(jìn)棧和退棧的算法
3.2.7 讀棧項(xiàng)元素的算法
3.2.8 判定棧是否為空的算法
3.2.9 取棧項(xiàng)元素的算法
3.2.10 數(shù)組及其基本運(yùn)算
3.2.11 遞歸及其特點(diǎn)
3.2.12 鏈隊(duì)列的組織方法和語言描述
3.2.13 鏈隊(duì)列上入隊(duì)、出隊(duì)的算法
3.2.14 循環(huán)隊(duì)列上進(jìn)行入隊(duì)、出隊(duì)的算法
3.2.15 循環(huán)隊(duì)列的隊(duì)滿、隊(duì)空條件
3.2.16 順序隊(duì)列上的"假溢出"及原因
3.2.17 循環(huán)隊(duì)列的組織方法
3.2.18 順序隊(duì)列的組織方法
3.2.19 隊(duì)列的特點(diǎn)及其基本運(yùn)算
3.2.20 遞歸方法求解的條件
3.3 典型例題
3.4 習(xí)題
第4章 串
4.1 基本概念
4.2 基本理論
4.2.1 串的存儲方法
4.2.2 串的順序存儲結(jié)構(gòu)
4.2.3 順序存儲串的基本運(yùn)算
4.2.4 串的鏈?zhǔn)酱鎯Φ幕具\(yùn)算
4.3 典型例題
4.4 習(xí)題
第5章 數(shù)組與廣義表
5.1 基本概念
5.1.1 數(shù)組的有關(guān)概念
5.1.2 廣義表的有關(guān)概念
5.2 基本理論
5.2.1 數(shù)組的基本操作
5.2.2 數(shù)組的特點(diǎn)
5.2.3 數(shù)組的順序儲存表示
5.2.4 數(shù)組順序存儲的實(shí)現(xiàn)
5.2.5 二維數(shù)組的基本運(yùn)算
5.2.6 二維數(shù)組的順序存儲方式
5.2.7 對稱矩陣的壓縮存儲
5.2.8 稀疏矩陣的基本操作
5.2.9 稀疏矩陣的壓縮存儲方式
5.2.10 廣義表的表示
5.2.11 廣義表的存儲結(jié)構(gòu)和表示
5.2.12 廣義表存儲結(jié)構(gòu)的特點(diǎn)
5.2.13 廣義表的基本算法
5.3 典型例題
5.4 習(xí)題
第6章 樹和二叉樹
6.1 基本概念
6.1.1 樹的基本術(shù)語
6.1.2 二叉樹的有關(guān)概念
6.2 基本理論
6.2.1 樹的含義
6.2.2 二叉樹的5種基本形態(tài)
6.2.3 二叉樹的基本運(yùn)算
6.2.4 二叉樹的性質(zhì)
6.2.5 二叉樹順序存儲的基本思想
6.2.6 二叉樹遍歷方法
6.2.7 二叉樹的遍歷算法
6.2.8 樹的表示法
6.2.9 二叉樹的邏輯結(jié)構(gòu)及特點(diǎn)
6.2.10 二叉鏈表中結(jié)點(diǎn)及根指針的作用
6.2.11 樹的存儲結(jié)構(gòu)
6.2.12 樹的基本運(yùn)算
6.2.13 二叉樹的線索化
6.2.14 哈夫曼樹的構(gòu)造算法
6.2.15 樹的性質(zhì)
6.2.16 哈夫曼編碼
6.2.17 樹與二叉樹的關(guān)系
6.2.18 二叉樹的存儲結(jié)構(gòu)
6.2.19 使用線索二叉樹的原因
6.2.20 線索二叉樹的方法
6.2.21 二叉樹的基本運(yùn)算
6.2.22 樹、森林與二叉樹的轉(zhuǎn)換
6.3 典型例題
6.4 習(xí)題
第7章 圖
7.1 基本概念
7.2 基本理論
7.2.1 鄰接矩陣的表示方法
7.2.2 鄰接表的表示方法及特點(diǎn)
7.2.3 十字鄰接表存儲方法
7.2.4 非連通圖的遍歷方法
7.2.5 非連通圖中連通分量的求法
7.2.6 連通圖深度和廣度優(yōu)先搜索的基本思想
7.2.7 網(wǎng)的鄰接矩陣的建立方法
7.2.8 無向圖的鄰接表的建立方法
7.2.9 有向圖拓?fù)渑判蚍椒?br /> 7.2.10 拓?fù)渑判虻幕舅枷爰八惴?br /> 7.2.11 建立無向網(wǎng)絡(luò)的算法
7.2.12 prim算法的基本思想
7.2.13 最小生成樹的實(shí)際背景
7.2.14 鄰接表的形式及建鄰接表的算法
7.2.15 最小生成樹的性質(zhì)
7.2.16 求最小生成樹需考慮的問題
7.2.17 構(gòu)造最小生成樹的方法
7.2.18 求從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑
7.2.19 每對頂點(diǎn)之間的最短路徑
7.2.20 求關(guān)鍵路徑的計(jì)算過程
7.3 典型例題
7.4 習(xí)題
第8章 查找表
8.1 基本概念
8.2 基本理論
8.2.1 順序查找的基本思想
8.2.2 順序表查找的算法
8.2.3 折半查找的基本思想及特點(diǎn)
8.2.4 折半查找的算法
8.2.5 分塊查找的基本思想及特點(diǎn)
8.2.6 分塊查找的算法及時(shí)間與空間性能
8.2.7 二叉排序樹的基本思想及算法
8.2.8 在二叉排序樹上插入結(jié)點(diǎn)的算法
8.2.9 生成二叉排序樹的算法
8.2.10 從二叉排序樹上刪除結(jié)點(diǎn)
8.2.11 平衡二叉樹的方法
8.2.12 B-樹的含義
8.2.13 B-樹的查找
8.2.14 B-樹的插入和生成
8.2.15 B-樹的刪除
8.2.16 B-樹和B+樹的區(qū)別
8.2.17 B+樹查找、刪除特點(diǎn)
8.2.18 哈希表的含義及特點(diǎn)
8.2.19 常用的構(gòu)造哈希函數(shù)的方法
8.2.20 解決沖突的方法
8.2.21 哈希表的查找及算法
8.2.22 鏈地址法的優(yōu)缺點(diǎn)
8.3 典型例題
8.4 習(xí)題
第9章 排序
9.1 基本概念
9.1.1 內(nèi)部排序的有關(guān)概念
9.1.2 外部排序的有關(guān)概念
9.2 基本理論
9.2.1 直接插入排序的基本思想及算法
9.2.2 直接插入排序的時(shí)空性能
9.2.3 希爾排序的基本思想及算法
9.2.4 冒泡排序的基本思想及算法
9.2.5 快速排序的基本思想及算法
9.2.6 直接選擇排序的基本思想及算法
9.2.7 堆排序的基本思想
9.2.8 堆排序的過程及算法
9.2.9 二路歸并排序的基本思想
9.2.10 基數(shù)排序的基本思想及算法
9.2.11 各種內(nèi)部排序方法的比較
9.2.12 外部排序的基本思想
9.2.13 歸并排序的基本方法
9.2.14 置換-選擇排序的基本思想
9.2.15 利用"敗者樹"實(shí)現(xiàn)置換選擇排序
9.2.16 最佳歸并樹的構(gòu)造
9.3 典型例題
9.4 習(xí)題
第10章 文件
10.1 基本概念
10.2 基本理論
10.2.1 文件的結(jié)構(gòu)
10.2.2 文件的組織形式
10.2.3 順序文件的組織形式及特點(diǎn)
10.2.4 文件的基本運(yùn)算
10.2.5 散列文件的查找及特點(diǎn)
10.2.6 散列文件的結(jié)構(gòu)和操作特點(diǎn)
10.2.7 多關(guān)鍵字文件的結(jié)構(gòu)特點(diǎn)
10.2.8 順序文件的檢索方法
10.2.9 索引文件的組織特點(diǎn)
10.3 典型例題
10.4 習(xí)題
附錄 習(xí)題答案