数据结构 C语言版

第1章 绪论 1

1.1从问题到程序 1

1.2有关概念和术语 4

1.3算法及算法分析 6

1.3.1算法特性 6

1.3.2算法描述 7

1.3.3算法分析 7

本章小结 9

习题1 9

第2章 线性表 11

2.1线性表的逻辑结构 11

2.1.1线性表的定义 11

2.1.2线性表的基本操作 11

2.2线性表的顺序存储及操作实现 12

2.2.1顺序表 12

2.2.2顺序表的基本操作实现 14

2.2.3顺序表应用举例 17

2.3线性表的链式存储和运算实现 19

2.3.1单链表 19

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

2.3.3循环链表 26

2.3.4双向链表 27

2.4应用举例 28

本章小结 30

习题2 30

第3章 栈和队列 33

3.1栈 33

3.1.1栈的定义及基本运算 33

3.1.2栈的存储实现和运算实现 34

3.2栈的应用举例 36

3.3队列 40

3.3.1队列的定义及基本运算 40

3.3.2队列的存储实现及运算实现 41

3.4队列应用举例 46

本章小结 47

习题3 48

第4章 串和数组 50

4.1串 50

4.1.1串的基本概念 50

4.1.2串的基本运算 50

4.1.3串的存储及基本运算的实现 51

4.2数组 54

4.2.1数组的逻辑结构 54

4.2.2数组的内存映象 54

4.2.3稀疏矩阵 55

4.3应用举例 58

本章小结 60

习题4 60

第5章 树与二叉树 61

5.1树的概念与基本操作 61

5.1.1树的定义及相关术语 61

5.1.2树的基本操作 63

5.2二叉树 63

5.2.1二叉树的基本概念 63

5.2.2二叉树的主要性质 64

5.2.3二叉树的基本操作与存储实现 65

5.2.4二叉树的遍历 68

5.3树与森林 71

5.3.1树的存储 71

5.3.2树、森林与二叉树的转换 73

5.3.3树和森林的遍历 75

5.4最优二叉树——哈夫曼树 76

5.4.1哈夫曼树的基本概念 76

5.4.2哈夫曼树的构造算法 78

5.4.3哈夫曼树在编码问题中的应用 79

5.5应用举例 80

本章小结 82

习题5 83

第6章 图 85

6.1图的基本概念 85

6.1.1图的定义和术语 85

6.1.2图的基本操作 87

6.2图的存储表示 88

6.2.1邻接矩阵 88

6.2.2邻接表 90

6.3图的遍历 91

6.3.1深度优先查找 91

6.3.2广度优先查找 93

6.4图的应用 94

6.4.1最小生成树 94

6.4.2最短路径 97

6.4.3拓扑排序 100

6.5应用举例 103

本章小结 107

习题6 107

第7章 查找 109

7.1基本概念与术语 109

7.2静态查找表 110

7.2.1静态查找表结构 110

7.2.2顺序查找 111

7.2.3有序表的折半查找 112

7.2.4分块查找（索引顺序查找） 114

7.3动态查找表 115

7.4哈希表（杂凑或散列表） 119

7.4.1哈希表与哈希方法 119

7.4.2常用的哈希函数构造方法 120

7.4.3处理冲突的方法 121

7.4.4哈希表的查找及其分析 123

7.5应用举例 124

本章小结 130

习题7 130

第8章 排序 132

8.1基本概念 132

8.2 3种简单排序方法 133

8.2.1直接插入排序 133

8.2.2冒泡排序（Bubble Sort） 134

8.2.3简单选择排序 135

8.3快速排序 136

8.4堆排序（Heap Sort） 139

8.5归并排序 141

8.6基数排序 143

8.6.1多关键码排序 143

8.6.2链式基数排序 144

8.7 各种排序方法的比较与讨论 146

本章小结 146

习题8 147

第9章 模拟试题 148

模拟试题1 148

模拟试题2 150

模拟试题3 152

模拟试题4 154

模拟试题5 156

模拟试题6 159

模拟试题7 162

模拟试题8 165

模拟试题9 168

模拟试题10 171

附录 部分习题参考答案 175