数据结构课程学习与应考指导PDF|Epub|txt|kindle电子书版本网盘下载

数据结构课程学习与应考指导PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

第1章 概论1

1.1 知识点1

1.2 内容精要1

1.2.1 概念和术语1

1.2.2 数据结构的研究目的和研究内容1

1.2.3 数据逻辑结构的四种基本形态2

1.2.4 数据存储结构的基本组织方式2

1.2.5 数据逻辑结构上定义的基本运算3

1.2.6 在数据结构中引入抽象数据类型概念的好处4

1.2.7 什么是算法4

1.2.8 算法的五个重要特性4

1.2.9 评价算法优劣的基本标准4

1.2.10 算法分析的目的5

1.2.11 算法的时间复杂度的含义5

1.2.12 算法的空间复杂度的含义5

1.3 典型例题解析5

第2章 线性表11

2.1 知识点11

2.2 内容精要11

2.2.1 概念和术语11

2.2.2 线性表的特点11

2.2.3 通常在线性表上定义的基本运算11

2.2.4 线性表的顺序存储结构（顺序表）12

2.2.5 C语言中线性表顺序存储空间的两种分配方法12

2.2.6 静态分配空间和动态分配空间时，构造一个顺序表算法之比较13

2.2.7 线性表的顺序存储结构的优缺点14

2.2.8 线性表的链式存储结构（链表）14

2.2.9 几种常用的链式存储结构14

2.2.10 线性表的链式存储结构的优缺点15

2.2.11 单链表设置头结点的好处15

2.2.12 单链表不带头结点和带头结点两种结构下，删除第i个元素的算法之比较15

2.2.13 循环链表设立尾指针而不设头指针的好处17

2.2.14 静态链表的用途和构造方法17

2.2.15 线性表的索引存储结构及其优点17

2.3 典型例题解析17

第3章 栈和队列27

3.1 知识点27

3.2 内容精要27

3.2.1 栈的定义和术语27

3.2.2 栈的特性27

3.2.3 栈的基本运算定义27

3.2.4 顺序栈（栈的顺序存储结构）28

3.2.5 在顺序栈上运算的实现28

3.2.6 链栈（栈的链式存储结构）30

3.2.7 栈空间共享问题30

3.2.8 栈和递归的关系31

3.2.9 哪些类型的问题适合于用递归方法求解31

3.2.10 递归模型及递归执行过程31

3.2.11 递归算法的设计步骤32

3.2.12 递归过程的实现32

3.2.13 递归算法的优缺点33

3.2.14 递归算法转换为非递归算法的方法33

3.2.15 队列的定义和术语35

3.2.16 队列的特性36

3.2.17 队列的基本运算定义36

3.2.18 顺序队列（队列的顺序存储结构）36

3.2.19 循环队列的好处36

3.2.20 在循环队列上运算的实现37

3.2.21 链队列（队列的链式存储结构）38

3.2.22 在链队列上运算的实现38

3.3 典型例题解析39

第4章 串54

4.1 知识点54

4.2 内容精要54

4.2.1 概念和术语54

4.2.2 串与线性表的关系54

4.2.3 两个串相等的充分必要条件54

4.2.4 通常在串上定义的基本运算54

4.2.5 顺序串（串的顺序存储结构）55

4.2.6 链串／块链结构（串的链式存储结构）56

4.2.7 在块链中结点大小（CHUNKSIZE值）的选择56

4.2.8 两种典型的串的模式匹配算法56

4.2.9 求next数组值的方法58

4.2.10 next数组的缺陷和改进58

4.3 典型例题解析58

第5章 多维数组67

5.1 知识点67

5.2 内容精要67

5.2.1 多维数组的定义67

5.2.2 多维数组和线性表的关系67

5.2.3 数组的特点68

5.2.4 数组的基本运算的定义68

5.2.5 数组的顺序存储结构68

5.2.6 特殊矩阵压缩存储的意义69

5.2.7 对称矩阵压缩存储的方法69

5.2.8 三角矩阵压缩存储的方法69

5.2.9 对角矩阵压缩存储的方法70

5.2.10 稀疏矩阵及其压缩存储的特点70

5.2.11 稀疏矩阵压缩存储的顺序存储方式70

5.2.12 稀疏矩阵压缩存储的链式存储方式——十字链表（或称正交链表）72

5.3 典型例题解析73

第6章 树和二叉树81

6.1 知识点81

6.2 内容精要81

6.2.1 树的概念和定义81

6.2.2 树的特点82

6.2.3 树的表示方法82

6.2.4 树的相关术语82

6.2.5 二叉树的定义和它的五种形态83

6.2.6 一棵度为2的有序树与二叉树的区别83

6.2.7 满二叉树和完全二叉树83

6.2.8 二叉树的基本运算84

6.2.9 二叉树的性质85

6.2.10 二叉树的存储结构85

6.2.11 遍历二叉树86

6.2.12 线索二叉树的概念87

6.2.13 线索二叉树的存储结构87

6.2.14 二叉树的线索化87

6.2.15 遍历线索二叉树88

6.2.16 最优二叉树（也称哈夫曼树）的概念89

6.2.17 哈夫曼树的构造方法89

6.2.18 哈夫曼树的应用89

6.2.19 树的存储结构90

6.2.20 树与二叉树的转换91

6.2.21 森林转换为二叉树92

6.2.22 树和森林的遍历92

6.3 典型例题解析93

第7章 图122

7.1 知识点122

7.2 内容精要122

7.2.1 概念和术语122

7.2.2 图的基本运算的定义123

7.2.3 图的存储结构124

7.2.4 邻接矩阵和邻接表两种图的存储结构的比较125

7.2.5 图的遍历算法126

7.2.6 图的生成树和最小生成树的概念126

7.2.7 如何得到图的生成树126

7.2.8 最小生成树（MST）的性质129

7.2.9 Prim算法构造最小生成树129

7.2.10 Kruskal算法构造最小生成树130

7.2.11 拓扑排序和AOV（Activity on Vertex）网131

7.2.12 无前趋的顶点优先的拓扑排序算法131

7.2.13 无后继的顶点优先的拓扑排序算法133

7.2.14 关键路径问题和AOE（Activity On Edge）网133

7.2.15 确定关键路径的主要步骤134

7.2.16 采用邻接表作为图的存储结构时，求事件的最早发生时间和最晚发生时间为何采用不同的策略134

7.2.17 求关键路径的算法135

7.2.18 单源最短路径——迪杰斯特拉（Dijkstra）算法136

7.2.19 每对顶点间的最短路径——弗洛伊德（Floyd）算法137

7.2.20 Floyd算法使用时的限制138

7.3 典型例题解析138

第8章 查找154

8.1 知识点154

8.2 内容精要154

8.2.1 查找在数据处理中的重要性154

8.2.2 基本概念和术语154

8.2.3 查找表的典型存储结构155

8.2.4 静态查找表的顺序表存储结构155

8.2.5 顺序表上的顺序查找156

8.2.6 有序顺序表上的折半查找（也称二分查找）156

8.2.7 索引顺序表的分块查找158

8.2.8 二叉排序树（也称二叉查找树）的概念和性质159

8.2.9 二叉排序树的存储结构定义159

8.2.10 二叉排序树上的查找160

8.2.11 二叉排序树上结点的插入161

8.2.12 二叉排序树的生成162

8.2.13 二叉排序树上结点的删除162

8.2.14 平衡二叉树（也称AVL树）的概念163

8.2.15 平衡二叉树上插入结点的操作163

8.2.16 平衡二叉树的生成164

8.2.17 平衡二叉树上结点的删除操作165

8.2.18 平衡二叉树的特点165

8.2.19 B—树的概念165

8.2.20 B—树的高度定理166

8.2.21 B—树的用途166

8.2.22 B—树的存储结构定义166

8.2.23 B—树上的查找操作166

8.2.24 B—树上的插入操作167

8.2.25 B—树上的删除操作168

8.2.26 B＋树的概念168

8.2.27 B—树和B＋树的主要差异169

8.2.28 B＋树上的基本运算169

8.2.29 键树（又称数字查找树或字符树）的概念169

8.2.30 键树的存储结构170

8.2.31 键树上的运算和性能要点171

8.2.32 哈希表（也称散列表或杂凑表）的概念和相关术语171

8.2.33 哈希表的设计过程171

8.2.34 哈希函数的基本构造方法172

8.2.35 哈希表中处理冲突的常用方法172

8.2.36 哈希表的平均查找长度ASL与装填因子α的关系173

8.3 典型例题解析173

第9章 排序187

9.1 知识点187

9.2 内容精要187

9.2.1 排序的概念187

9.2.2 排序的分类187

9.2.3 评价排序算法的主要标准188

9.2.4 直接插入排序188

9.2.5 希尔排序（也称缩小增量排序）190

9.2.6 冒泡排序191

9.2.7 快速排序（也称分划交换排序）192

9.2.8 简单选择排序193

9.2.9 堆的定义194

9.2.10 堆与完全二叉树的关系194

9.2.11 调整堆的操作和建堆的操作194

9.2.12 堆排序195

9.2.13 归并排序196

9.2.14 基数排序与前述排序方法不同的实质是什么197

9.2.15 多关键字排序的两种方法197

9.2.16 基数排序198

9.2.17 各种内部排序方法的比较200

9.2.18 选择内部排序方法时所应考虑的主要因素200

9.2.19 外部排序的概念200

9.2.20 外部排序的基本方法201

9.2.21 影响外部排序时间开销的因素201

9.2.22 提高外部排序效率的途径201

9.2.23 利用败者树实现k路平衡归并的方法201

9.2.24 胜者树较之败者树的缺陷202

9.2.25 置换-选择排序生成初始归并段的方法202

9.2.26 引入最佳归并树的必要性203

9.2.27 最佳归并树的构造方法203

9.3 典型例题解析204

附录A 类C语言说明220

参考文献227