第1章 绪论 1
1.1数据结构的基本概念和术语 1
1.2抽象数据类型及面向对象的概念 3
1.2.1抽象数据类型 3
1.2.2面向对象的概念 4
1.3有关的预备知识 4
1.3.1集合 4
1.3.2递归 6
1.4算法和算法分析 9
1.4.1算法的基本概念 9
1.4.2算法的评估和复杂度度量 10
1.4.3算法设计的一个实例 13
本章小结 14
习题 14
第2章 线性表 16
2.1线性表的定义和基本运算 16
2.1.1线性表的定义 16
2.1.2线性表的操作 18
2.2线性表的实现 19
2.2.1顺序存储结构 19
2.2.2链式存储结构 23
2.2.3两种基本存储实现方式的比较 30
2.2.4循环链表 31
2.2.5双向链表 32
2.3线性表的应用 35
本章小结 39
习题 39
第3章栈、队列和数组 43
3.1栈 43
3.1.1栈的定义 43
3.1.2栈的实现 45
3.1.3栈的应用 48
3.2队列 51
3.2.1队列的定义及基本运算 51
3.2.2队列的实现 52
3.2.3队列的应用 57
3.3数组 59
3.3.1数组的抽象数据类型 59
3.3.2数组的存储方式 60
3.3.3特殊数组 61
3.3.4数组的应用 66
本章小结 70
习题 70
第4章 树与二叉树 73
4.1树 73
4.1.1树的基本概念 73
4.1.2树的抽象数据类型 75
4.2二叉树 76
4.2.1二叉树的定义及其主要特性 76
4.2.2二叉树的实现 79
4.2.3二叉树的遍历 82
4.3树与森林 85
4.3.1树的存储结构 85
4.3.2森林与二叉树的转换 88
4.3.3树和森林的遍历 89
4.4哈夫曼树和哈夫曼编码 90
本章小结 102
习题 102
第5章 图结构 106
5.1图 106
5.1.1图的基本概念 106
5.1.2图的抽象数据类型 110
5.2图的存储结构 111
5.2.1邻接矩阵 111
5.2.2邻接表 112
5.2.3图的实现 114
5.3图的遍历及求图的连通分量 118
5.3.1深度优先搜索 120
5.3.2广度优先搜索 123
5.3.3无向图的连通分量 126
5.4有向无环图及拓扑排序 127
5.4.1有向无环图 128
5.4.2拓扑排序 128
5.5生成树和最小代价生成树 132
5.5.1生成树 132
5.5.2最小代价生成树 134
5.6单源最短路径 142
5.6.1问题的提出 142
5.6.2单源最短路径的算法 143
本章小结 146
习题 146
第6章 查找 149
6.1查找的基本概念 149
6.2顺序表的查找 150
6.2.1顺序查找方法 150
6.2.2折半查找方法 154
6.3树形结构的查找 158
6.3.1二叉排序树 158
6.3.2平衡二叉树 166
6.3.3 B树 175
6.4哈希表及其查找 178
6.4.1哈希的概念 178
6.4.2哈希函数的构造方法 180
6.4.3处理冲突的几种方法 182
6.4.4哈希表的查找及其效率分析 184
本章小结 185
习题 185
第7章 内部排序 188
7.1排序的基本概念 188
7.2插入排序 190
7.2.1直接插入排序 191
7.2.2折半插入排序 193
7.2.3希尔排序 194
7.3交换排序 196
7.4基于分治法的排序 199
7.4.1归并排序 199
7.4.2快速排序 204
7.5选择排序 208
7.5.1简单选择排序 208
7.5.2堆排序 210
7.6分配排序和桶式排序 214
7.7有关内部排序算法的比较 218
本章小结 218
习题 219
附录 221
数据结构综合测试题 221
数据结构期末模拟考试试卷一 222
数据结构期末模拟考试试卷二 225
数据结构期末模拟考试试卷三 228
参考文献 230