数据结构：使用C++语言描述 第2版PDF|Epub|txt|kindle电子书版本网盘下载

数据结构：使用C++语言描述 第2版PDF格式电子书版下载

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

第1章　基础知识1

1.1　算法与数据结构1

1.2　什么是数据结构2

1.2.1　基本概念2

1.2.2　数据的逻辑结构3

1.2.3　数据的存储表示3

1.2.4　数据结构的运算4

1.3　数据抽象和抽象数据类型5

1.3.1　抽象、数据抽象和过程抽象5

1.3.2　封装与信息隐蔽6

1.3.3　数据类型和抽象数据类型6

1.3.4　数据结构与抽象数据类型7

1.4　描述数据结构和算法7

1.4.1　数据结构的规范7

1.4.2　实现数据结构8

1.5　算法分析的基本方法9

1.5.1　算法及其性能标准9

1.5.2　算法的时间复杂度10

1.5.3　渐近时间复杂度11

1.5.4　最坏、最好和平均情况时间复杂度12

1.5.5　算法的空间复杂度12

本章小结13

习题13

第2章　线性表15

2.1　线性表ADT15

2.2　线性表的顺序表示16

2.3　线性表的链接表示20

2.3.1　单链表20

2.3.2　带表头结点的单链表25

2.3.3　单循环链表26

2.3.4　双向链表26

2.4　多项式的算术运算27

2.4.1　项结点的C＋＋类28

2.4.2　多项式的C＋＋类30

2.4.3　多项式类的实现30

本章小结32

习题33

第3章　堆栈和队列34

3.1　堆栈34

3.1.1 堆栈ADT34

3.1.2　堆栈的顺序表示35

3.1.3　堆栈的链接表示36

3.2　队列36

3.2.1 队列ADT36

3.2.2　队列的顺序表示37

3.2.3 队列的链接表示39

3.3　表达式计算39

3.3.1　表达式39

3.3.2　计算后缀表达式的值40

3.3.3　中缀表达式转换为后缀表达式43

3.4　递归45

3.4.1　递归的概念45

3.4.2　递归的实现46

本章小结47

习题48

第4章　数组和字符串50

4.1　数组50

4.1.1 数组ADT50

4.1.2　数组的顺序表示50

4.1.3　一维数组的C＋＋类51

4.2　特殊矩阵53

4.2.1　对称矩阵53

4.2.2　带状矩阵54

4.3　稀疏矩阵55

4.3.1　稀疏矩阵ADT55

4.3.2　稀疏矩阵的顺序表示56

4.3.3　稀疏矩阵转置57

4.4　字符串59

4.4.1 字符串ADT59

4.4.2　字符串的存储表示60

4.4.3　简单模式匹配算法61

4.4.4　模式匹配的KMP算法62

本章小结65

习题65

第5章　树67

5.1　树的基本概念67

5.1.1　树的定义67

5.1.2　基本术语68

5.2　二叉树69

5.2.1　二叉树的定义69

5.2.2　二叉树的性质70

5.2.3 二叉树ADT71

5.2.4　二叉树的存储表示72

5.2.5　二叉树类73

5.2.6　实现二叉树基本运算73

5.3　二叉树的遍历75

5.3.1　二叉树遍历算法75

5.3.2　二叉树遍历的递归算法76

5.3.3　二叉树遍历的应用实例77

5.4　二叉树遍历的非递归算法78

5.4.1　遍历器类78

5.4.2　中序遍历器类79

5.5　树和森林81

5.5.1　森林与二叉树的转换81

5.5.2　树和森林的存储表示82

5.5.3　树和森林的遍历83

5.6　堆和优先权队列84

5.6.1 堆85

5.6.2　优先权队列ADT87

5.6.3　优先权队列类87

5.6.4　实现优先权队列88

5.7　哈夫曼树和哈夫曼编码90

5.7.1　树的路径长度90

5.7.2　哈夫曼树和哈夫曼算法91

5.7.3　哈夫曼树类92

5.7.4　构造哈夫曼树92

5.7.5　哈夫曼编码93

5.8　并查集和等价关系94

5.8.1 并查集ADT95

5.8.2　并查集的存储表示95

5.8.3　并查集类96

5.8.4　函数Union和Find96

5.8.5　改进的函数Union和Find97

5.8.6　按等价关系分组98

本章小结98

习题99

第6章　集合和搜索101

6.1　基本概念101

6.1.1　集合与搜索101

6.1.2　动态集ADT102

6.1.3　集合的表示103

6.2　顺序搜索104

6.2.1　无序表的顺序搜索104

6.2.2　有序表的顺序搜索105

6.2.3　平均搜索长度105

6.3　二分搜索106

6.3.1　二分搜索算法106

6.3.2　对半搜索106

6.3.3　二叉判定树107

本章小结109

习题109

第7章　搜索树110

7.1　二叉搜索树110

7.1.1　二叉搜索树的定义110

7.1.2　二叉搜索树的搜索111

7.1.3　二叉搜索树的插入112

7.1.4　二叉搜索树的删除113

7.1.5　平均情况时间分析115

7.2　二叉平衡树115

7.2.1　二叉平衡树的定义115

7.2.2　二叉平衡树类116

7.2.3　二叉平衡树的平衡旋转117

7.2.4　二叉平衡树的插入121

7.2.5　二叉平衡树的删除123

7.2.6　二叉平衡树的高度126

7.3　B－树127

7.3.1 m叉搜索树127

7.3.2　B－树的定义128

7.3.3 B－树的高度129

7.3.4　B－树的搜索129

7.3.5　B－树的插入130

7.3.6　B－树的删除132

7.4　伸展树134

本章小结136

习题136

第8章　跳表和散列表138

8.1　字典138

8.2　跳表138

8.2.1　什么是跳表139

8.2.2　跳表类141

8.2.3　跳表的搜索142

8.2.4　跳表的插入143

8.2.5　跳表的删除144

8.3　散列表144

8.3.1 散列技术145

8.3.2　散列函数145

8.3.3　拉链法147

8.3.4　开地址法148

8.3.5　线性探查法148

8.3.6　其他开地址法151

8.3.7　性能分析152

本章小结153

习题153

第9章　图154

9.1 图的基本概念154

9.1.1　图的定义与术语154

9.1.2 图ADT156

9.2　图的存储结构157

9.2.1　图的矩阵表示法157

9.2.2　图的邻接矩阵实现159

9.2.3　图的邻接表表示法161

9.2.4　图的邻接表实现162

9.3　图的遍历164

9.3.1　扩充的图类164

9.3.2　深度优先遍历164

9.3.3　宽度优先遍历166

9.4　拓扑排序167

9.4.1 用顶点代表活动的AOV网167

9.4.2　什么是拓扑排序169

9.4.3　拓扑排序算法169

9.5　关键路径171

9.5.1 用边代表活动的AOE网171

9.5.2　什么是关键路径172

9.5.3　关键路径算法174

9.6　最小代价生成树175

9.6.1　基本概念175

9.6.2　普里姆算法175

9.6.3　克鲁斯卡尔算法177

9.7　单源最短路径179

9.7.1　最短路径问题179

9.7.2　单源最短路径问题179

9.7.3　选择数据结构180

9.7.4　迪杰斯特拉算法180

9.8　所有顶点之间的最短路径182

9.8.1　选择数据结构182

9.8.2　弗洛伊德算法183

本章小结184

习题184

第10章　内排序187

10.1　基本概念187

10.2　简单排序算法188

10.2.1　简单选择排序188

10.2.2　直接插入排序189

10.2.3 冒泡排序190

10.3　快速排序191

10.4　两路合并排序193

10.5　堆排序195

10.6　基数排序196

本章小结200

习题200

第11章　文件和外排序202

11.1　辅助存储器简介202

11.1.1　主存储器和辅助存储器202

11.1.2　磁盘存储器202

11.2　文件203

11.2.1　文件的基本概念203

11.2.2　文件的组织方式204

11.3　文件的索引结构207

11.3.1　静态索引结构207

11.3.2　动态索引结构207

11.4　外排序208

11.4.1　外排序的基本过程208

11.4.2　初始游程的生成209

11.4.3　多路合并211

11.4.4　最佳合并树213

本章小结214

习题214

第12章　实习指导和实习题216

12.1　实习目的和要求216

12.1.1　实习目的216

12.1.2　实习要求216

12.2　实习步骤217

12.3　面向对象方法及其表示法217

12.3.1 面向对象方法217

12.3.2　表示法219

12.4　实习报告和样例220

12.4.1　实习报告220

12.4.2　实习样题221

12.4.3　实习报告样例221

12.5　实习题226

12.5.1　实习一226

12.5.2　实习二227

12.5.3　实习三227

12.5.4　实习四228

12.5.5　实习五229

12.5.6　实习六229

12.5.7　实习七230

12.5.8　实习八231

12.5.9　实习九231

12.5.10　实习十232

12.5.11　实习十一232

附录　程序调试233

附录1　调试步骤233

附录2　VC＋＋调试器234

参考文献238