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

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

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

第1章 概论1

1.1 什么是数据结构1

1.2 数据抽象和抽象数据类型4

1.3 数据结构的描述6

1.4 算法和算法分析8

1.4.1 算法及其性能标准8

1.4.2 算法的时间复杂度9

1.4.3 渐近时间复杂度11

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

1.4.5 算法的空间复杂度12

小结13

习题113

第2章 两种基本数据结构15

2.1 结构与联合15

2.1.1 结构15

2.1.2 联合16

2.2 数组17

2.2.1 一维数组17

2.2.2 二维数组17

2.2.3 多维数组19

2.3 链表19

2.3.1 指针19

2.3.2 单链表23

2.3.3 带表头结点的单链表29

2.3.4 循环链表30

2.3.5 双向链表31

小结32

习题233

第3章 堆栈和队列34

3.1 堆栈34

3.1.1 堆栈 ADT34

3.1.2 堆栈的顺序表示35

3.1.3 堆栈的链接表示37

3.2 队列38

3.2.1 队列 ADT38

3.2.2 队列的顺序表示39

3.2.3 队列的链接表示42

3.3＊ 表达式的计算42

3.3.1 表达式42

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

3.3.3 计算后缀表达式的值46

3.4＊ 递归和递归过程49

3.4.1 递归的概念49

3.4.2 递归的实现50

3.5＊ 演示和测试52

小结54

习题354

第4章 线性表和数组56

4.1 线性表56

4.1.1 线性表 ADT56

4.1.2 线性表的顺序表示57

4.1.3 线性表的链接表示61

4.1.4 两种存储表示的比较64

4.2＊ 多项式的算术运算65

4.2.1 多项式 ADT65

4.2.2 多项式的链接表示65

4.2.3 多项式的输入和输出66

4.2.4 多项式相加68

4.3 数组作为抽象数据类型70

4.4 特殊矩阵71

4.4.1 对称矩阵71

4.4.2＊ 带状矩阵72

4.5 稀疏矩阵73

4.5.1 稀疏矩阵 ADT73

4.5.2 稀疏矩阵的顺序表示74

4.5.3 稀疏矩阵转置75

4.5.4＊ 稀疏矩阵相乘77

4.5.5 稀疏矩阵的正交链表表示80

4.5.6＊ 建立正交链表83

4.5.7＊ 打印正交链表84

小结85

习题485

第5章 字符串和广义表87

5.1 字符串87

5.1.1 字符串 ADT87

5.1.2 字符串的存储表示88

5.1.3 简单模式匹配算法89

5.1.4＊ 模式匹配的 KMP 算法92

5.2＊ 广义表96

5.2.1 广义表的概念96

5.2.2 广义表 ADT97

5.2.3 广义表的存储表示98

5.2.4 广义表的算法99

小结99

习题5100

第6章 树101

6.1 树的基本概念101

6.1.1 树的定义101

6.1.2 基本术语102

6.2 二叉树103

6.2.1 二叉树的定义和性质103

6.2.2 二叉树 ADT105

6.2.3 二叉树的存储表示106

6.2.4 二叉树的遍历110

6.2.5＊ 二叉树遍历的非递归算法114

6.2.6＊ 二叉树遍历的应用实例116

6.2.7＊ 线索二叉树118

6.3 树和森林122

6.3.1 森林与二叉树的转换122

6.3.2 树和森林的存储表示123

6.3.3 树和森林的遍历125

6.4＊ 堆和优先权队列126

6.4.1 堆126

6.4.2 优先权队列129

6.5 哈夫曼树和哈夫曼编码132

6.5.1 树的路径长度132

6.5.2 哈夫曼树和哈夫曼算法133

6.5.3 哈夫曼编码135

6.6＊ 并查集和等价关系137

6.6.1 并查集137

6.6.2 并查集的实现138

6.6.3 集合按等价关系分组140

小结141

习题6141

第7章 集合和搜索144

7.1 集合及其表示144

7.1.1 集合和搜索144

7.1.2 集合 ADT145

7.1.3 集合的表示146

7.2 顺序搜索146

7.3 二分搜索149

7.3.1 对半搜索149

7.3.2＊ 二叉判定树150

7.3.3＊ 斐波那契搜索152

7.4＊ 搜索算法的时间下界154

小结155

习题7155

第8章 搜索树156

8.1 二叉搜索树156

8.1.1 二叉搜索树的定义156

8.1.2 二叉搜索树的搜索157

8.1.3 二叉搜索树的插入158

8.1.4 二叉搜索树的删除159

8.1.5＊ 二叉搜索树的高度162

8.2＊ 二叉平衡树162

8.2.1 二叉平衡树的定义163

8.2.2 二叉平衡树的平衡旋转163

8.2.3 二叉平衡树的插入169

8.2.4 二叉平衡树的删除172

8.2.5 二叉平衡数的高度175

8.3 B-树176

8.3.1 m 叉搜索树176

8.3.2 B-树的定义178

8.3.3 B-树的高度178

8.3.4 B-树的搜索179

8.3.5 B-树的插入179

8.3.6 B-树的删除182

8.4＊ 键树184

8.4.1 键树的定义184

8.4.2 双链树185

8.4.3 Trie 树185

8.5＊ 伸展树186

小结189

习题8189

第9章 跳表和散列表191

9.1 字典191

9.2＊ 跳表191

9.2.1 什么是跳表192

9.2.2 跳表的搜索195

9.2.3 跳表的插入196

9.2.4 跳表的删除197

9.3 散列表198

9.3.1 散列技术198

9.3.2 散列函数199

9.3.3 解决冲突的拉链法201

9.3.4 解决冲突的线性探查法202

9.3.5 解决冲突的其他开地址法206

9.3.6 性能分析208

小结208

习题9209

第10章 图210

10.1 图的基本概念210

10.1.1 图的定义与术语210

10.1.2 图 ADT213

10.2 图的存储结构214

10.2.1 矩阵表示法214

10.2.2 邻接表表示法217

10.2.3＊ 多重表表示法220

10.3 图的遍历221

10.3.1 深度优先遍历221

10.3.2 宽度优先遍历223

10.4 拓扑排序和关键路径225

10.4.1 拓扑排序225

10.4.2＊ 关键路径228

10.5 最小代价生成树232

10.5.1 普里姆算法233

10.5.2＊ 克鲁斯卡尔算法234

10.6＊ 最短路径236

10.6.1 单源最短路径237

10.6.2 所有顶点之间的最短路径240

小结243

习题10243

第11章 内排序246

11.1 排序的基本概念246

11.2 插入排序247

11.2.1 直接插入排序247

11.2.2＊ 希尔排序251

11.3 交换排序252

11.3.1 冒泡排序253

11.3.2 快速排序254

11.4 合并排序259

11.4.1 两路合并排序259

11.4.2 合并排序的迭代算法260

11.4.3＊ 链表上的合并排序261

11.5 选择排序265

11.5.1 简单选择排序265

11.5.2＊ 堆排序266

11.6＊ 排序算法的时间下界267

11.7＊ 基数排序269

小结272

习题11272

第12章 文件和外排序274

12.1＊ 辅助存储器简介274

12.1.1 主存储器和辅助存储器274

12.1.2 磁盘存储器274

12.2 文件276

12.2.1 文件的基本概念276

12.2.2 文件的组织方式276

12.2.3 C 语言文件280

12.3 文件的索引结构281

12.3.1 静态索引结构281

12.3.2 动态索引结构282

12.4＊ 外排序283

12.4.1 外排序的基本过程283

12.4.2 初始游程的生成283

12.4.3 多路合并286

12.4.4 最佳合并树288

小结289

习题12289

附录 A 软件工程概述290

一、软件开发方法学290

二、系统测试方法292

附录 B 实习要求和实习题294

一、实习目的294

二、实习要求294

三、实习步骤294

四、实习报告295

五、实习题296

附录 C 专用名词中英文对照表298

参考文献304