数据结构PDF电子书下载

第1章 绪论 1

1.1数据结构的基本概念 1

1.2抽象数据类型和软件构造方法 4

1.3算法和算法的时间复杂度 5

算法 5

算法设计的目标 7

算法时间效率的度量 7

1.4算法设计 11

1.5算法书写规范 14

1.6本课程内容概述 14

习题一 15

第2章 线性表 17

2.1线性表的抽象数据类型 17

2.2线性表的顺序表示和实现 18

顺序表的存储结构 18

顺序表的操作实现 19

顺序表操作的效率分析 22

顺序表的应用举例 22

2.3线性表的链式表示和实现 26

单链表的存储结构 26

单链表的操作实现 29

单链表操作的效率分析 34

单链表应用举例 35

循环单链表 36

双向链表 37

2.4设计举例 40

2.5本章小结 46

习题二 47

第3章 堆栈和队列 49

3.1堆栈 49

堆栈和堆栈的抽象数据类型 49

堆栈的顺序表示和实现 50

堆栈的链式表示和实现 53

3.2堆栈应用——表达式计算 58

3.3队列 61

队列和队列抽象数据类型 61

顺序队列 62

顺序循环队列的表示和实现 63

链式队列 66

队列的应用 69

3.4优先级队列 71

顺序优先级队列的设计和实现 71

优先级队列的应用 74

3.5本章小结 75

习题三 76

第4章串 79

4.1串 79

串及其基本概念 79

串的抽象数据类型 80

C语言的串函数 81

4.2串的存储结构 83

串的顺序存储结构 83

串的链式存储结构 84

4.3串基本操作的实现算法 85

4.4串的模式匹配算法 90

Brute-Force算法 90

KMP算法 92

Brute-Force算法和KMP算法的比较 96

4.5本章小结 98

习题四 99

第5章 数组 101

5.1数组的实现机制 101

5.2动态数组的设计方法 102

5.3特殊矩阵的压缩存储 105

5.4稀疏矩阵的压缩存储 106

稀疏矩阵的三元组顺序表 106

稀疏矩阵的三元组链表 110

5.5本章小结 111

习题五 112

第6章 递归 114

6.1递归的概念 114

6.2递归算法的执行过程 115

6.3递归算法的设计方法 118

6.4递归过程和运行时栈 120

6.5递归算法的效率分析 122

6.6递归算法到非递归算法的转换 123

6.7设计举例 126

一般递归算法设计举例 126

回溯法及设计举例 129

6.8本章小结 133

习题六 134

第7章 树和二叉树 137

7.1树 137

树的定义 137

树的表示方法 138

树的抽象数据类型 139

7.2二叉树 140

二叉树的定义 140

二叉树抽象数据类型 141

二叉树的性质 141

7.3二叉树的设计和实现 143

二叉树的存储结构 143

二叉链存储结构下二叉树的操作实现 145

二叉树的遍历及其实现 147

7.4线索二叉树 151

7.5哈夫曼树 153

哈夫曼树的基本概念 153

哈夫曼编码问题 155

哈夫曼编码问题设计和实现 156

7.6树的存储结构、转换和遍历 160

树的存储结构 160

树与二叉树的转换 162

树的遍历 163

7.7本章小结 164

习题七 165

第8章图 168

8.1图的基本概念 168

图的基本概念 168

图的抽象数据类型 170

8.2图的设计和实现 171

图的邻接矩阵存储结构 171

图的邻接表存储结构 172

邻接矩阵存储结构下图的操作实现 173

8.3图的遍历 177

图的深度和广度优先遍历算法 177

图的深度和广度优先遍历算法设计和实现 178

8.4最小生成树 181

最小生成树的基本概念 181

普里姆算法 182

普里姆函数设计和实现 183

克鲁斯卡尔算法 186

8.5最短路径 187

最短路径的基本概念 187

从一个顶点到其余各顶点的最短路径 188

狄克斯特拉算法设计和实现 189

8.6本章小结 192

习题八 192

第9章 排序 195

9.1排序的基本概念 195

9.2插入排序 197

直接插入排序 197

希尔排序 199

9.3选择排序 201

直接选择排序 201

堆排序 202

9.4交换排序 207

冒泡排序 207

快速排序 209

9.5归并排序 211

9.6综合应用举例 214

9.7本章小结 215

习题九 216

第10章 查找 218

10.1查找的基本概念 218

10.2静态查找表 219

顺序表 219

有序顺序表 220

索引顺序表 222

10.3动态查找表 224

二叉排序树 224

B/树 231

10.4哈希表 235

哈希表的基本概念 235

哈希函数构造方法 237

哈希冲突解决方法 238

哈希表设计举例 239

10.5本章小结 243

习题十 244

附录A上机实习内容规范 245

附录B上机实习范例 246

参考文献 257