数据结构与算法PDF电子书下载

第1章 绪论 1

1.1引言 1

1.1.1为什么要学习数据结构 1

1.1.2“数据结构”课程的内容 4

1.2数据结构的概念 5

1.2.1基本概念和术语 5

1.2.2抽象数据类型 7

1.3算法 8

1.3.1算法及其特征 8

1.3.2算法的描述 9

1.3.3算法的性能分析 9

1.4递归 12

1.4.1递归的概念 12

1.4.2递归调用的实现原理 13

1.4.3递归转换为非递归 15

1.4.4递归应用举例 16

1.5本章知识点小结 17

练习题 18

实验题 20

题目1比较算法复杂性描述函数的增长 20

题目2全排列的递归实现 21

题目3皇后问题 21

第2章 基本线性结构 22

2.1线性表 22

2.1.1问题提出 22

2.1.2线性表的定义 23

2.1.3线性表的基本运算 23

2.2线性表的顺序存储 24

2.2.1顺序表 24

2.2.2顺序表上基本运算的实现 26

2.2.3顺序表应用举例 29

2.3线性表的链式存储 31

2.3.1单链表 31

2.3.2单链表上基本运算的实现 33

2.3.3循环链表 39

2.3.4双向链表 39

2.3.5链表应用举例 41

2.4顺序表和链表的比较 44

2.5堆栈 45

2.5.1堆栈的定义 45

2.5.2堆栈的存储及基本运算的实现 46

2.5.3堆栈应用举例 49

2.6队列 58

2.6.1队列的定义 58

2.6.2队列的存储及基本运算的实现 59

2.6.3队列应用举例 64

2.7本章知识点小结 67

练习题 68

实验题 72

题目1 Josephus环问题 72

题目2模拟停车场管理 73

第3章 线性结构的扩展 75

3.1字符串 75

3.1.1字符串的基本概念 75

3.1.2顺序串 76

3.1.3模式匹配 79

3.2多维数组与特殊矩阵 84

3.2.1多维数组 84

3.2.2特殊矩阵 86

3.2.3稀疏矩阵 90

3.3广义表 99

3.3.1广义表的基本概念 99

3.3.2广义表的存储 101

3.4本章知识点小结 103

练习题 104

实验题 107

题目 格式化文本 107

第4章 树结构 110

4.1引言 110

4.1.1问题提出 110

4.1.2相关概念 111

4.2二叉树 113

4.2.1二叉树的概念 113

4.2.2二叉树的主要性质 114

4.2.3二叉树的存储 116

4.2.4二叉树基本运算的实现 119

4.3二叉树的遍历 121

4.3.1递归方法实现二叉树的遍历 121

4.3.2非递归方法实现二叉树的遍历 123

4.3.3队列方法实现二叉树的层次遍历 126

4.4二叉树遍历的应用 127

4.4.1构造二叉树的二叉链表存储 127

4.4.2在二叉树中查找值为x的数据元素 128

4.4.3统计给定二叉树中叶子结点的数目 128

4.4.4由遍历序列恢复二叉树 129

4.5线索二叉树 130

4.5.1线索二叉树的定义及结构 130

4.5.2线索二叉树的构建 132

4.5.3线索二叉树的遍历 133

4.6最优二叉树 136

4.6.1最优二叉树的概念 136

4.6.2最优二叉树的构造 138

4.6.3最优二叉树的应用——哈夫曼编码 141

4.7树和森林 143

4.7.1树的基本操作与表示 143

4.7.2树的存储 144

4.7.3树和森林与二叉树之间的转换 148

4.7.4树或森林的遍历 150

4.7.5树的应用 151

4.8本章知识点小结 153

练习题 155

实验题 159

题目 哈夫曼编码/译码器 159

第5章 图结构 161

5.1引言 161

5.1.1问题提出 161

5.1.2相关概念 162

5.1.3图的基本操作 165

5.2图的存储方法 165

5.2.1邻接矩阵 165

5.2.2邻接表 167

5.2.3十字链表 169

5.2.4邻接多重表 171

5.3图的遍历 173

5.3.1深度优先搜索 173

5.3.2广度优先搜索 175

5.3.3应用图的遍历判定图的连通性 177

5.4生成树与最小生成树 178

5.4.1生成树和生成森林 178

5.4.2最小生成树 179

5.4.3构造最小生成树的Prim算法 180

5.4.4构造最小生成树的Kruskal算法 183

5.5最短路径 186

5.5.1从一个源点到其他各点的最短路径 186

5.5.2每一对顶点之间的最短路径——弗洛伊德算法 189

5.6拓扑排序 193

5.6.1有向无环图的概念 193

5.6.2 AOV网与拓扑排序 194

5.7关键路径 198

5.7.1 AOE网与关键路径 198

5.7.2关键路径的确定 199

5.8本章知识点小结 203

练习题 206

实验题 208

题目 校园导游程序 208

第6章 查找 210

6.1引言 210

6.1.1问题提出 210

6.1.2相关概念 210

6.2线性表查找 212

6.2.1顺序查找 212

6.2.2在顺序存储的有序表上查找 214

6.3树表查找 218

6.3.1二叉排序树 218

6.3.2平衡二叉树 224

6.3.3 B树和B＋树 230

6.4散列表查找 236

6.4.1散列表 236

6.4.2常用的散列函数 237

6.4.3处理冲突的方法及散列表的构造 238

6.4.4散列表上的查找 242

6.4.5散列表上的插入 244

6.4.6散列表上的删除 245

6.5本章知识点小结 245

练习题 246

实验题 249

题目1职工信息检索系统 249

题目2个人图书管理系统 250

第7章 排序 252

7.1引言 252

7.1.1问题提出 252

7.1.2相关概念 252

7.2插入排序 254

7.2.1直接插入排序 254

7.2.2折半插入排序 256

7.2.3希尔排序 256

7.3交换排序 258

7.3.1冒泡排序 258

7.3.2快速排序 259

7.4选择排序 261

7.4.1简单选择排序 261

7.4.2树型选择排序 262

7.4.3堆排序 263

7.5归并排序 266

7.5.1两个有序表的合并 266

7.5.2二路归并排序的迭代算法 267

7.5.3二路归并排序的递归算法 268

7.6基数排序 268

7.6.1多关键码排序 268

7.6.2链式基数排序 269

7.7排序方法比较 272

7.8本章知识点小结 274

练习题 275

实验题 278

题目 各种内部排序的性能比较 278

第8章 扩展应用举例 279

8.1求最大子段和 279

8.1.1问题描述 279

8.1.2问题分析与解决 279

8.2表达式树的构造 283

8.2.1问题描述 283

8.2.2问题分析与解决 283

8.3由等价关系求划分 287

8.3.1问题描述 287

8.3.2问题分析与解决 287

8.4本章知识点小结 289

练习题 290

实验题 290

题目1模拟银行排队办理业务 290

题目2 0-1背包问题 291

附录 292

附录A实验要求 292

实验题目 294

附录B模拟试卷 295

模拟试卷一 295

模拟试卷二 296

模拟试卷三 299

模拟试卷四 301

参考文献 304