数据结构 C语言描述PDF|Epub|txt|kindle电子书版本网盘下载

数据结构 C语言描述PDF格式电子书版下载

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

第1章 绪论1

1.1 数据结构的概念及分类1

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

1.1.2 与数据结构相关的基本术语2

1.1.3 数据结构的分类4

1.1.4 数据结构的存储结构6

1.1.5 定义在数据结构上的操作6

1.2 使用C语言描述数据结构6

1.2.1 数据类型7

1.2.2 算法的控制结构7

1.2.3 算法的函数结构8

1.2.4 动态存储分配10

1.2.5 逻辑和关系运算的约定11

1.2.6 输入与输出11

1.3 算法和算法设计12

1.3.1 算法的定义和特性12

1.3.2 算法的设计步骤12

1.3.3 算法设计的基本方法13

1.4 算法分析与度量16

1.4.1 算法的评价标准16

1.4.2 算法的时间和空间复杂度度量16

1.4.3 算法的渐近分析19

小结21

习题21

第2章 线性表23

2.1 线性表的定义及操作23

2.1.1 线性表的定义和特点23

2.1.2 线性表的主要操作24

2.2 顺序表25

2.2.1 顺序表的定义和特点25

2.2.2 顺序表的结构定义25

2.2.3 顺序表主要操作的实现26

2.2.4 顺序表主要操作的性能分析28

2.2.5 顺序表的应用举例29

2.3 单链表30

2.3.1 单链表的定义和特点30

2.3.2 单链表的结构定义31

2.3.3 单链表中的插入与删除31

2.3.4 带头结点的单链表33

2.3.5 单链表主要操作的性能分析35

2.3.6 单链表的顺序访问与尾递归36

2.3.7 单链表的应用举例38

2.4 顺序表与线性链表的比较40

2.5 线性链表的其他变形41

2.5.1 循环链表41

2.5.2 双向链表44

2.5.3 静态链表46

2.6 线性表的应用：字符串47

2.6.1 字符串的概念47

2.6.2 字符串的初始化和赋值48

2.6.3 C语言中有关字符串的库函数48

2.6.4 自定义字符串的存储表示50

2.7 单链表的应用：一元多项式及其运算53

2.7.1 一元多项式的表示53

2.7.2 多项式的结构定义54

2.7.3 多项式的加法55

2.7.4 多项式的乘法56

小结58

习题58

第3章 栈、队列和数组61

3.1 栈61

3.1.1 栈的概念61

3.1.2 顺序栈62

3.1.3 链式栈66

3.1.4 栈的混洗68

3.2 队列69

3.2.1 队列的概念69

3.2.2 循环队列70

3.2.3 链式队列73

3.3 栈的应用75

3.3.1 数制转换75

3.3.2 括号匹配75

3.3.3 表达式的计算与优先级处理76

3.3.4 栈与递归的实现80

3.4 队列的应用83

3.4.1 打印杨辉三角形与逐行处理83

3.4.2 电路布线与两点间的最短路径84

3.5 数组86

3.5.1 一维数组86

3.5.2 多维数组87

3.5.3 数组的应用举例89

3.6 在算法设计中使用递归89

3.6.1 汉诺塔问题与分治法90

3.6.2 迷宫问题与回溯法92

3.6.3 计算组合数与动态规划95

3.7 特殊矩阵96

3.7.1 对称矩阵的压缩存储96

3.7.2 三对角线矩阵的压缩存储97

3.7.3 稀疏矩阵的压缩存储98

3.8 双端队列100

3.8.1 双端队列的概念100

3.8.2 双端队列的主要操作101

3.8.3 双端队列的顺序存储表示101

3.8.4 双端队列的链接存储表示103

小结103

习题104

第4章 树与二叉树108

4.1 树的基本概念108

4.1.1 树的定义和术语108

4.1.2 树的基本操作110

4.2 二叉树111

4.2.1 二叉树的概念111

4.2.2 二叉树的性质112

4.2.3 二叉树的主要操作113

4.3 二叉树的存储表示114

4.3.1 二叉树的顺序存储表示114

4.3.2 二叉树的链表存储表示115

4.4 二叉树的遍历116

4.4.1 二叉树遍历的递归算法116

4.4.2 递归遍历算法的应用举例117

4.4.3 二叉树遍历的非递归算法120

4.4.4 非递归遍历算法的应用举例123

4.4.5 二叉树的计数125

4.5 线索二叉树127

4.5.1 线索二叉树的概念127

4.5.2 线索二叉树的种类128

4.5.3 中序线索二叉树的建立和遍历129

4.5.4 前序与后序线索二叉树131

4.6 树与森林132

4.6.1 树的存储表示132

4.6.2 森林与二叉树的转换134

4.6.3 树与森林的深度优先遍历135

4.6.4 树与森林的广度优先遍历137

4.6.5 树遍历算法的应用举例138

4.7 二叉树的应用：二叉排序树138

4.7.1 二叉排序树的概念138

4.7.2 二叉排序树的查找139

4.7.3 二叉排序树的插入140

4.7.4 二叉排序树的删除141

4.7.5 二叉排序树的性能分析142

4.8 二叉树的应用：平衡二叉树144

4.8.1 平衡二叉树的概念144

4.8.2 平衡化旋转144

4.8.3 平衡二叉树的插入146

4.8.4 平衡二叉树的删除147

4.8.5 平衡二叉树的性能分析149

4.9 二叉树的应用：Huffman树150

4.9.1 带权路径长度的概念150

4.9.2 Huffman树与Huffman算法151

4.9.3 Huffman树的应用：最优判定树153

4.9.4 Huffman树的应用：Huffman编码154

4.10 二叉树的应用：堆155

4.10.1 小根堆和大根堆155

4.10.2 堆的建立156

4.10.3 堆的插入158

4.10.4 堆的删除158

4.11 树的应用：八皇后问题与树的剪枝159

4.11.1 八皇后问题的提出159

4.11.2 八皇后问题的状态树160

4.11.3 八皇后问题算法161

小结162

习题162

第5章 图168

5.1 图的基本概念168

5.1.1 与图有关的概念168

5.1.2 图的基本操作170

5.2 图的存储结构171

5.2.1 图的邻接矩阵表示171

5.2.2 图的邻接表表示175

5.2.3 邻接矩阵表示与邻接表表示的比较178

5.2.4 图的邻接多重表表示179

5.3 图的遍历180

5.3.1 深度优先搜索181

5.3.2 广度优先搜索182

5.3.3 连通分量183

5.3.4 重连通图184

5.3.5 欧拉回路与一笔画问题186

5.3.6 有向图的强连通分量187

5.4 最小生成树188

5.4.1 最小生成树求解和贪婪法188

5.4.2 Kruskal算法190

5.4.3 Prim算法193

5.5 最短路径194

5.5.1 非负权重的单源最短路径194

5.5.2 所有顶点之间的最短路径197

5.5.3 无权重的最短路径199

5.6 用顶点表示活动的网络（AOV网络）200

5.7 用边表示活动的网络（AOE网络）204

小结207

习题208

第6章 查找212

6.1 查找的基本概念与性能分析212

6.1.1 查找的概念212

6.1.2 查找算法的性能分析213

6.2 顺序查找法213

6.2.1 顺序表上的顺序查找算法213

6.2.2 线性链表上的顺序查找算法216

6.3 折半查找法216

6.3.1 一般的折半查找法216

6.3.2 拟最优查找树：折半查找的改进方法219

6.3.3 斐波那契查找：折半查找的变形222

6.3.4 插值查找：折半查找的变形223

6.4 B树224

6.4.1 索引顺序表与分块查找224

6.4.2 多级索引结构与m叉查找树225

6.4.3 B树的概念226

6.4.4 B树上的查找227

6.4.5 B树上的插入228

6.4.6 B树上的删除229

6.4.7 B＋树231

6.5 散列表及其查找233

6.5.1 散列的概念233

6.5.2 常见的散列函数234

6.5.3 解决冲突的开地址法236

6.5.4 解决冲突的链地址法242

6.5.5 散列法分析244

小结245

习题245

第7章 排序250

7.1 排序的概念与算法性能250

7.1.1 排序的概念250

7.1.2 排序算法的性能251

7.1.3 数据表和静态链表的结构定义251

7.2 几种简单的排序方法253

7.2.1 直接插入排序253

7.2.2 基于链表的直接插入排序254

7.2.3 折半插入排序255

7.2.4 起泡排序256

7.2.5 简单选择排序258

7.3 希尔排序259

7.3.1 希尔排序的设计思路259

7.3.2 希尔排序的算法实现260

7.4 快速排序261

7.4.1 快速排序的设计思路261

7.4.2 快速排序的算法描述262

7.4.3 快速排序的算法分析262

7.4.4 快速排序的改进算法263

7.5 堆排序264

7.5.1 大根堆264

7.5.2 堆排序的算法265

7.5.3 堆排序的算法分析267

7.6 归并排序267

7.6.1 两路归并267

7.6.2 递归的归并排序算法268

7.6.3 迭代的归并排序算法269

7.6.4 基于链表的归并排序算法271

7.7 基数排序272

7.7.1 基数排序的概念272

7.7.2 MSD基数排序273

7.7.3 LSD基数排序274

7.8 内排序算法的分析与比较276

7.8.1 排序方法的下界276

7.8.2 各种内排序方法的比较279

7.8.3 链表排序结果的重排280

小结282

习题283

附录一 2009～2011年全国考研计算机学科联考专业基础综合考试数据结构部分试题解析288

附录二 大作业要求及样例303

参考文献308