目录

第1章绪论1

1.1数据结构1

1.1.1基本概念1

1.1.2三要素2

1.2算法分析5

1.2.1算法的定义5

1.2.2算法的评价标准6

1.2.3时间复杂度7

1.2.4空间复杂度9

1.3程序设计基础10

1.3.1符号常量11

1.3.2数据类型12

1.3.3动态存储分配15

思考与练习16第2章线性表17

2.1顺序表17

2.1.1顺序表的类型定义17

2.1.2顺序表的基本操作18

2.2链表21

2.2.1单链表21

2.2.2双向链表26

2.2.3循环链表28

2.3线性表的应用29

2.3.1扩容29

2.3.2查找30

2.3.3求并集32

思考与练习34第3章栈和队列35

3.1栈35

3.1.1顺序栈35

3.1.2链栈37

3.2队列38

3.2.1循环队列38

3.2.2链队列42

3.3栈和队列的应用42

3.3.1字符和数值的处理43

3.3.2递归的设计与实现47

思考与练习51第4章树和二叉树52

4.1树52

4.1.1树的基本术语53

4.1.2树的存储结构54

4.2二叉树57

4.2.1二叉树的性质57

4.2.2二叉树的存储结构60

4.2.3树、森林与二叉树的转换61

4.3树和二叉树的操作63

4.3.1遍历二叉树63

4.3.2创建二叉树66

4.3.3树和森林的遍历67

4.4树和二叉树的应用67

4.4.1从遍历序列还原树67

4.4.2二叉树的复制与统计69

4.4.3哈夫曼树70

思考与练习73第5章图74

5.1图的基本概念74

5.2图的存储结构78

5.2.1邻接矩阵78

5.2.2邻接表79

5.2.3邻接多重表和十字链表81

5.3图的遍历82

5.3.1深度优先搜索83

5.3.2广度优先搜索85

5.4图的应用87

5.4.1最小生成树87

5.4.2最短路径90

5.4.3拓扑排序93

5.4.4关键路径95

思考与练习98第6章查找100

6.1查找的基本概念100

6.2线性表的查找101

6.2.1顺序查找101

6.2.2折半查找102

6.2.3分块查找105

6.3二叉排序树的查找106

6.3.1二叉排序树的定义107

6.3.2二叉排序树的插入109

6.3.3二叉排序树的删除111

6.4散列表的查找114

6.4.1散列函数的构造方法115

6.4.2处理冲突的方法117

6.4.3性能分析119

思考与练习120第7章排序122

7.1排序的基本概念122

7.2简单的排序算法124

7.2.1冒泡排序126

7.2.2简单选择排序128

7.2.3直接插入排序130

7.3先进的排序算法135

7.3.1希尔排序135

7.3.2堆排序138

7.3.3归并排序144

7.3.4快速排序147

7.4内部排序的性能比较152

思考与练习154附录A课程内容与考核要求155附录B抽象数据类型的定义164附录C上机实验的设计方法175附录D练习题解答（示例）178参考文献201