《数据结构与C语言程序设计》

第一部分基本概念1

第一章绪论1

1.1 C语言简介1

目 录1

1.2什么是数据结构2

1.3 C语言与数据结构2

1.4基本术语介绍3

1.5问题：数据汇总5

1.6解法Ⅰ5

1.7解法Ⅱ7

1.8性能测量10

1.9讨论12

1.10习题12

2.1算法的概念14

第二章算法的复杂性14

2.2取幂算法15

2.3渐近分析21

2.4实现问题23

2.5讨论24

2.6习题26

第三章指针与动态存储29

3.1变量与指针29

3.2字符串与数组33

3.3类型定义与结构40

3.4动态存储分配43

3.5讨论46

3.6习题47

4.1付帐单的两个方法49

第四章栈和队列49

4.2栈数据类型50

4.3队列数据类型53

4.4应用例子56

4.5讨论61

4.6习题62

第五章链表64

5.1 表64

5.2应用：集合67

5.3用于链接结构的其它工具75

5.4多重链接结构79

5.5讨论80

5.6习题81

6.1关于存储器的进一步讨论83

第六章存储器组织83

6.2变量与运行时栈85

6.3堆管理的一个简单方法87

6.4物理存储器组织90

6.5讨论92

6.6习题93

第二部分高效率算法95

第七章检索（查找）95

7.1关于检索的几个问题95

7.2自组织链表97

7.3二分检索99

7.4二叉树101

7.5二叉检索树104

7.6讨论109

7.7习题110

第八章散列法113

8.1理想散列法113

8.2利用探测法解决冲突113

8.3利用链表解决冲突119

8.4讨论121

8.5习题122

第九章分类表123

9.1 AVL（平衡）树123

9.2 2,4树128

9.3实现：红一黑树131

9.4进一步的课题141

9.5讨论143

9.6习题144

第十章优先队列146

10.1优先队列数据类型146

10.2堆147

10.3堆的实现151

10.4霍夫曼（HUFFMAN）树153

10.5其它运算157

10.6讨论159

10.7习题159

第十一章分类162

11.1分类的基本概念162

11.2两个简单分类算法163

11.3两个高效率分类算法166

11.4两个有用的分类思想172

11.5讨论174

11.6习题175

第十二章应用数据结构177

12.1复式记帐法177

12.2基本解180

12.3解法Ⅰ186

12.4解法Ⅱ188

12.5讨论190

12.6习题191

第三部分高级课题192

第十三章无环图192

13.1有根树192

13.2不相交集合194

13.3拓扑分类198

13.4讨论200

13.5习题201

第十四章图202

14.1基本术语介绍202

14.2数据结构203

14.3最短路径204

14.4最小生成树210

14.5遍历顺序和图的连通性212

14.6讨论218

14.7习题219

附录221

附录A C程序员参考221

附录B库函数228

附录C头文件232

附录D部分习题答案233