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

第1章 概论 1

1.1什么是数据结构 1

1.1.1基本概念 1

1.1.2数据的逻辑结构 2

1.1.3数据的存储结构 3

1.1.4数据结构的运算 4

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

1.2.1抽象、数据抽象和过程抽象 5

1.2.2封装与信息隐蔽 5

1.2.3数据类型和抽象数据类型 5

1.2.4数据结构与抽象数据类型 6

1.3描述数据结构 7

1.3.1数据结构的规范 7

1.3.2实现数据结构 8

1.4算法和算法分析 9

1.4.1算法及其性能标准 9

1.4.2算法的时间复杂度 10

1.4.3渐近时间复杂度 12

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

1.4.5算法的空间复杂度 13

小结 14

习题1 14

第2章 数组和链表 16

2.1结构与联合 16

2.1.1结构 16

2.1.2联合 17

2.2数组 18

2.2.1一维数组 18

2.2.2二维数组 18

2.2.3多维数组 20

2.3链表 20

2.3.1指针 20

2.3.2单链表 24

2.3.3带表头结点的单链表 30

2.3.4循环链表 31

2.3.5双向链表 31

小结 33

习题2 33

第3章 堆栈和队列 35

3.1堆栈 35

3.1.1堆栈ADT 35

3.1.2堆栈的顺序表示 36

3.1.3堆栈的链接表示 38

3.2队列 39

3.2.1队列ADT 39

3.2.2队列的顺序表示 40

3.2.3队列的链接表示 43

*3.3表达式的计算 43

3.3.1表达式 43

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

3.3.3计算后缀表达式的值 48

*3.4递归和递归过程 50

3.4.1递归的概念 50

3.4.2递归的实现 51

*3.5演示和测试 53

小结 55

习题3 55

第4章 线性表和数组ADT 57

4.1线性表 57

4.1.1线性表ADT 57

4.1.2线性表的顺序表示 58

4.1.3线性表的链接表示 61

4.1.4两种存储表示的比较 65

*4.2多项式的算术运算 65

4.2.1多项式ADT 65

4.2.2多项式的链接表示 66

4.2.3多项式的输入和输出 67

4.2.4多项式相加 69

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

4.4特殊矩阵 72

4.4.1对称矩阵 72

*4.4.2带状矩阵 72

4.5稀疏矩阵 74

4.5.1稀疏矩阵ADT 74

4.5.2稀疏矩阵的顺序表示 74

4.5.3稀疏矩阵转置 76

*4.5.4稀疏矩阵相乘 78

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

*4.5.6建立正交链表 84

*4.5.7打印正交链表 85

小结 86

习题4 86

第5章 字符串和广义表 88

5.1字符串 88

5.1.1字符串ADT 88

5.1.2字符串的存储表示 89

5.1.3简单模式匹配算法 90

*5.1.4模式匹配的KMP算法 93

*5.2广义表 97

5.2.1广义表的概念 97

5.2.2广义表ADT 98

5.2.3广义表的存储表示 99

5.2.4广义表的算法 100

小结 101

习题5 101

第6章 树 102

6.1树的基本概念 102

6.1.1树的定义 102

6.1.2基本术语 103

6.2二叉树 104

6.2.1二叉树的定义和性质 104

6.2.2二叉树ADT 106

6.2.3二叉树的存储表示 107

6.2.4二叉树的遍历 111

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

*6.2.6二叉树遍历的应用实例 117

*6.2.7线索二叉树 119

6.3树和森林 122

6.3.1森林与二叉树的转换 122

6.3.2树和森林的存储表示 123

6.3.3树和森林的遍历 125

*6.4堆和优先权队列 126

6.4.1堆 127

6.4.2优先权队列 129

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

6.5.1树的路径长度 132

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

6.5.3哈夫曼编码 136

*6.6并查集和等价关系 137

6.6.1并查集 137

6.6.2并查集的实现 138

6.6.3集合按等价关系分组 141

小结 142

习题6 142

第7章 集合和搜索 145

7.1集合及其表示 145

7.1.1集合和搜索 145

7.1.2集合ADT 146

7.1.3集合的表示 147

7.2顺序搜索 147

7.3二分搜索 149

7.3.1对半搜索 150

7.3.2二叉判定树 151

*7.3.3斐波那契搜索 153

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

小结 155

习题7 156

第8章 搜索树 157

8.1二叉搜索树 157

8.1.1二叉搜索树的定义 157

8.1.2二叉搜索树的搜索 157

8.1.3二叉搜索树的插入 158

8.1.4二叉搜索树的删除 160

*8.1.5二叉搜索树的高度 162

8.2二叉平衡树 163

8.2.1二叉平衡树的定义 163

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

8.2.3二叉平衡树的插入 170

8.2.4二叉平衡树的删除 173

8.2.5二叉平衡数的高度 176

8.3 B-树 176

8.3.1 m叉搜索树 176

8.3.2 B-树的定义 178

8.3.3 B-树的高度 179

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树 186

*8.5伸展树 187

小结 190

习题8 190

第9章 跳表和散列表 192

9.1字典 192

*9.2跳表 192

9.2.1什么是跳表 193

9.2.2跳表的搜索 196

9.2.3跳表的插入 197

9.2.4跳表的删除 198

9.3散列表 199

9.3.1散列技术 199

9.3.2散列函数 200

9.3.3解决冲突的拉链法 202

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

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

9.3.6性能分析 209

小结 209

习题9 210

第10章 图 211

10.1图的基本概念 211

10.1.1图的定义与术语 211

10.1.2图ADT 214

10.2图的存储结构 215

10.2.1矩阵表示法 215

10.2.2邻接表表示法 218

*10.2.3多重表表示法 221

10.3图的遍历 222

10.3.1深度优先遍历 222

10.3.2宽度优先遍历 224

10.4拓扑排序和关键路径 226

10.4.1拓扑排序 226

*10.4.2关键路径 230

10.5最小代价生成树 233

10.5.1普里姆算法 234

*10.5.2克鲁斯卡尔算法 235

*10.6最短路径 237

10.6.1单源最短路径 238

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

小结 244

习题10 244

第11章 内排序 247

11.1排序的基本概念 247

11.2插入排序 248

11.2.1直接插入排序 248

11.2.2*希尔排序 252

11.3交换排序 253

11.3.1冒泡排序 253

11.3.2快速排序 255

11.4合并排序 260

11.4.1两路合并排序 260

11.4.2合并排序的迭代算法 260

*11.4.3链表上的合并排序 262

11.5选择排序 265

11.5.1简单选择排序 266

*11.5.2堆排序 267

*11.6排序算法的时间下界 268

*11.7基数排序 269

小结 273

习题11 273

第12章 文件和外排序 275

*12.1辅助存储器简介 275

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

12.1.2磁盘存储器 275

12.2文件 277

12.2.1文件的基本概念 277

12.2.2文件的组织方式 277

12.2.3 C语言文件 281

12.3文件的索引结构 282

12.3.1静态索引结构 282

12.3.2动态索引结构 283

*12.4外排序 283

12.4.1外排序的基本过程 284

12.4.2初始游程的生成 284

12.4.3多路合并 286

12.4.4最佳合并树 288

小结 289

习题12 290

第13章 实习指导和实习题 291

13.1实习目的和要求 291

13.1.1实习目的 291

13.1.2实习要求 291

13.2实习步骤 292

13.3实习报告 292

13.4实习题 293

实习1数组操作 293

实习2链表操作 294

实习3表达式计算 294

实习4队列运算和用户界面设计 295

实习5线性表运算及应用 295

实习6一元多项式的相加和相乘 295

实习7对称矩阵的压缩存储 296

实习8稀疏矩阵的三元组表 296

实习9稀疏矩阵的正交链表 296

实习10字符串运算和文本处理 297

实习11二叉树的基本运算 297

实习12哈夫曼编码和译码系统 298

实习13 B-树检索 298

实习14散列表检索 299

实习15 图运算及其应用 299

实习16内排序算法及其性能比较 300

实习17外排序 300

13.5实习报告范例 301

13.5.1实习题：表达式计算 301

13.5.2实习报告 301

附录A 软件工程概述 307

A.1软件开发方法 307

A.2软件文档写作 309

A.3系统测试方法 310

附录B 专用名词中英文对照表 314

参考文献 320