数据结构概论PDF电子书下载

目录 1

第1章绪论 1

1.1基本概念和术语 1

1.2发展历程 4

1.3算法和算法描述 5

1.3.1概念和特性 5

1.3.2算法设计要求 5

1.3.3算法描述 6

1.4.1时间复杂度 7

1.4算法的性能分析 7

1.4.2空间复杂度 9

小结 9

习题 9

实习 10

第2章线性表 11

2.1概念和定义 11

2.1.1概念 11

2.1.2定义 12

2.2顺序存储结构 12

2.2.2顺序表的基本操作的实现 13

2.2.1顺序表的存储表示 13

2.3链式存储结构 17

2.3.1单链表的存储表示 17

2.3.2单链表基本操作的实现 18

2.3.3循环链表的表示和基本操作的实现 22

2.3.4双向链表的表示和基本操作的实现 22

2.4应用举例 24

2.4.1顺序表 24

2.4.2单链表 26

小结 28

习题 29

实习 31

第3章栈 32

3.1概念和定义 32

3.2顺序存储表示 33

3.2.1顺序栈的存储表示 33

3.2.2顺序栈基本操作的实现 34

3.3链式存储结构 36

3.3.1链栈的存储表示 36

3.3.2链栈基本操作的实现 36

3.4应用举例 38

习题 42

小结 42

实习 44

第4章队列 45

4.1概念和定义 45

4.2顺序存储结构 46

4.2.1顺序队列的存储表示 46

4.2.2顺序队列基本操作的实现 46

4.2.3循环队列 49

4.3链式存储结构 50

4.3.1链队列的存储表示 50

4.3.2链队列基本操作的实现 51

4.4应用举例 53

小结 54

习题 55

实习 56

第5章串 57

5.1概念和定义 57

5.2顺序存储结构 59

5.2.1定长顺序串的存储表示及操作的实现 59

5.2.2堆存储表示及操作的实现 61

5.4应用举例 65

5.3块链存储表示 65

小结 67

习题 67

实习 68

第6章二维数组和广义表 69

6.1二维数组概念和定义 69

6.2二维数组的顺序存储结构 70

6.3矩阵的压缩存储 70

6.3.1概念 71

6.3.2特殊矩阵的压缩存储 71

6.3.3稀疏矩阵的顺序存储表示和基本操作的实现 72

6.3.4稀疏矩阵的链式存储表示和基本操作的实现 79

6.4广义表的概念和定义 82

6.5广义表的操作和链式存储结构 82

小结 85

习题 86

实习 88

第7章树与二叉树 89

7.1树的概念 89

7.1.1定义 89

7.1.2表示方法 90

7.1.3基本概念和常用术语 91

7.2.1概念和定义 92

7.2二叉树 92

7.2.2性质 93

7.2.3存储结构 94

7.2.4遍历 95

7.2.5二叉树的线索化 99

7.3树和森林 104

7.3.1树的存储结构 104

7.3.2树和森林的遍历 106

7.3.3树、森林与二叉树的转换 107

7.4.1概念和定义 108

7.4哈夫曼树 108

7.4.2哈夫曼树的构造 109

7.4.3哈夫曼编码的实现 112

小结 115

习题 115

实习 116

第8章图 118

8.1图的概念 118

8.1.1定义 118

8.1.2基本概念和常用术语 119

8.2存储结构 120

8.2.1邻接矩阵表示及各操作的实现 121

8.2.2邻接表的表示及各操作的实现 125

8.3图的遍历 131

8.3.1深度优先搜索 131

8.3.2广度优先搜索 134

8.4生成树和最小生成树 135

8.4.1生成树的概念和分类 135

8.4.2最小生成树的概念和实现方法 136

8.5.1概念 143

8.5.2拓扑排序 143

8.5 AOV网及其应用 143

8.6 AOE网及其应用 148

8.6.1概念 148

8.6.2关键路径 148

8.7最短路径 155

8.7.1任意源点到其余各点的最短路径 155

8.7.2任意两点间的最短路径 159

小结 160

习题 160

实习 162

9.1概念及分类 163

第9章排序 163

9.2插入排序 164

9.2.1直接插入排序 164

9.2.2折半插入排序 167

9.2.3 2－路插入排序 169

9.2.4希尔排序 170

9.3交换排序 172

9.3.1冒泡排序 173

9.3.2快速排序 175

9.4.1简单选择排序 178

9.4选择排序 178

9.4.2树型选择排序 181

9.4.3堆排序 182

9.5 K－路归并排序 186

9.6基数排序 190

9.7内部排序方法的比较 191

9.7.1时间性能 192

9.7.2空间性能 192

9.7.3稳定性 192

9.7.4排序方法的选择 193

小结 193

习题 194

实习 195

第10章查找 196

10.1概念 196

10.2顺序存储结构查找 198

10.2.1顺序查找 198

10.2.2折半查找 200

10.2.3分块查找 203

10.3树存储结构查找 206

10.3.1二叉排序树 206

10.3.2 B－树 210

10.4哈希表查找 212

10.4.1基本概念 213

10.4.2哈希函数的构造方法 213

10.4.3解决冲突的方法 215

10.4.4查找方法 218

小结 221

习题 221

实习 222

习题答案 223

参考文献 225