本书系统介绍了各种典型的数据结构，主要包括线性表、栈和队列、串、数组、树、图、查找、排序和递归等。为了加强对算法的理解，还介绍了算法分析方面的内容。



        本书选材精练、概念清楚、注重实用、逻辑性强，各章中所涉及的数据结构与算法都给出了C语言描述，并都附有丰富的习题，便于学生理解与掌握。



        本书既可作为高等院校计算机专业及相关专业的教材，也可作为计算机应用技术人员的参考用书。

无

第1章  概论1

1.1  基本概念与术语1

1.2  数据结构的概念3

1.3  数据的逻辑结构5

1.3.1  数据结构的形式化定义5

1.3.2  数据的逻辑结构类型5

1.4  数据的存储结构6

1.4.1  顺序存储方法6

1.4.2  链式存储方法6

1.4.3  索引存储方法7

1.4.4  散列存储方法7

1.5  数据的运算7

1.6  算法与算法特性8

1.6.1  算法及其特性8

1.6.2  算法的描述方法8

1.6.3  算法与程序及数据结构10

1.7  算法性能分析10

1.8  算法度量11

1.8.1  算法时间复杂度11

1.8.2  复杂度函数的增长率13

小结15

习题115

第2章  线性表16

2.1  线性表定义及其运算16

2.1.1  线性表16

2.1.2  线性表的运算17

2.2  线性表的顺序存储19

2.2.1  顺序存储结构19

2.2.2  顺序结构线性表的运算20

2.2.3  顺序存储结构的特点22

2.3  线性表的链式存储23

2.3.1  线性链表23

2.3.2  线性链表的运算26

2.3.3  循环链表29

2.3.4  循环链表的运算29

2.3.5  双向链表30

2.3.6  双向链表的运算31

2.3.7  链式存储结构的特点32

2.4  链式存储结构的应用33

小结36

习题236

第3章  栈和队列38

3.1  栈38

3.1.1  栈的定义及其运算38

3.1.2  栈的顺序存储结构及其运算的实现39

3.1.3  栈的链式存储结构43

3.2  栈的应用44

3.2.1  子程序的调用问题44

3.2.2  算术表达式求值44

3.3  队列47

3.3.1  队列的定义47

3.3.2  队列的顺序存储47

3.3.3  队列的链式存储52

3.4  队列的应用55

小结56

习题356

第4章  串58

4.1  串的基本概念58

4.2  串的存储结构59

4.2.1  串的静态存储结构59

4.2.2  串的动态存储结构61

4.3  串的基本运算62

4.3.1  常见的基本运算62

4.3.2  实现串的基本运算的算法63

4.4  模式匹配65

4.5  串在文本编辑中的应用67

小结68

习题468

第5章  数组70

5.1  数组及其基本操作70

5.1.1  数组的概念70

5.1.2  数组的基本操作72

5.2  数组的存储结构72

5.3  数组在矩阵运算中的应用75

5.3.1  特殊矩阵的压缩存储75

5.3.2  稀疏矩阵的压缩存储77

小结83

习题583

第6章  树85

6.1  树85

6.1.1  树的定义85

6.1.2  树的常用术语86

6.1.3  树的基本操作87

6.2  二叉树87

6.2.1  二叉树的定义87

6.2.2  二叉树的存储结构89

6.2.3  二叉树的遍历91

6.2.4  二叉树遍历的应用93

6.3  线索二叉树94

6.4  树、森林和二叉树的关系97

6.4.1  树的存储结构97

6.4.2  森林与二叉树的转换100

6.4.3  树和森林的遍历102

6.5  哈夫曼树103

6.5.1  哈夫曼树的定义103

6.5.2  哈夫曼树的构造104

小结105

习题6105

第7章  图108

7.1  图的概念及其操作109

7.1.1  图的概念109

7.1.2  图的基本操作113

7.2  图的存储结构113

7.2.1  邻接矩阵113

7.2.2  邻接表115

7.2.3  十字链表118

7.2.4  邻接多重表119

7.3  图的遍历121

7.3.1  深度优先搜索121

7.3.2  广度优先搜索123

7.4  图的应用124

7.4.1  生成树124

7.4.2  最短路径128

7.4.3  拓扑排序131

7.5  关键路径法133

小结139

习题7139
第8章  查找142

8.1  基本概念142

8.2  线性表的查找143

8.2.1  顺序查找143

8.2.2  折半查找145

8.2.3  分块查找147

8.3  二叉查找树148

8.4  哈希表的查找152

8.4.1  哈希表152

8.4.2  构造哈希表的基本方法153

8.4.3  解决冲突的方法154

8.5  各种查找方法的比较156

小结157

习题8157

第9章  排序159

9.1  基本概念159

9.2  内部排序161

9.2.1  插入排序161

9.2.2  冒泡排序164

9.2.3  快速排序166

9.2.4  选择排序168

9.2.5  归并排序173

9.3  内部排序方法比较176

小结177

习题9177

第10章  递归179

10.1  递归的定义与类型179

10.1.1  递归的定义179

10.1.2  递归的类型179

10.2  递归应用举例180

10.2.1  汉诺塔问题180

10.2.2  八皇后问题182

10.3  递归的实现183

10.4  递归到非递归的转换过程187

10.5  递归的时间和空间复杂度190

小结191

习题10191

参考文献192

 

无