第1章 绪论 1
1.1基本术语 1
1.2数据结构的定义及研究的内容 2
1.2.1数据的逻辑结构 2
1.2.2数据的存储结构 5
1.2.3数据的运算 6
1.3算法 7
1.3.1算法的概念及特性 7
1.3.2算法的描述 8
1.3.3算法的评价 12
1.4学习数据结构的意义和目的 16
小结 17
习题 17
第2章 线性表 19
2.1线性表的定义及运算 19
2.1.1线性表的定义及逻辑特征 19
2.1.2线性表上运算的定义 20
2.1.3线性表的存储结构 21
2.2顺序表 21
2.2.1顺序表的定义及表示 21
2.2.2线性表运算在顺序表上的实现 23
2.3链表 27
2.3.1链表的定义及形式 27
2.3.2单链表 28
2.3.3循环链表 42
2.3.4双链表 43
2.3.5静态链表 45
2.4顺序表和链表的比较 47
小结 48
习题 49
第3章 栈和队列 53
3.1栈 53
3.1.1栈的定义及运算 53
3.1.2顺序栈及运算的实现 54
3.1.3链栈及运算的实现 56
3.1.4栈的应用 57
3.1.5栈与递归 60
3.2队列 63
3.2.1队列的定义及运算 63
3.2.2顺序队列及运算的实现 64
3.2.3链队列及运算的实现 67
3.3栈与队列的比较 69
小结 70
习题 71
第4章 多维数组及广义表 73
4.1多维数组 73
4.2矩阵的压缩存储 75
4.2.1特殊矩阵 75
4.2.2稀疏矩阵 78
4.3广义表 83
4.3.1广义表的定义 83
4.3.2广义表的运算 85
小结 85
习题 86
第5章树 88
5.1树的定义 88
5.2二叉树 90
5.2.1二叉树的定义及性质 90
5.2.2二叉树上运算的定义 93
5.2.3二叉树的存储 95
5.2.4二叉链表上实现二叉树的遍历运算 99
5.3线索二叉树 102
5.3.1中序线索二叉链表 104
5.3.2中序线索二叉链表的中序遍历 106
5.3.3利用中序线索实现前序遍历和后序遍历 107
5.4哈夫曼树 108
5.4.1哈夫曼树的定义及建立 108
5.4.2哈夫曼编码及译码 113
5.5树和森林 117
5.5.1树和森林的遍历定义 117
5.5.2森林与二叉树的转换 118
5.5.3树的存储 119
小结 122
习题 123
第6章图 126
6.1图的概念 126
6.2图的存储 131
6.2.1邻接矩阵 131
6.2.2邻接表 134
6.2.3边集数组 137
6.2.4图的三种存储方法的比较 138
6.3图的遍历 139
6.3.1深度优先搜索遍历 139
6.3.2广度优先搜索遍历 143
6.3.3非连通图的遍历 146
6.4最小生成树 147
6.4.1普里姆算法 147
6.4.2克鲁斯卡尔算法 152
6.5最短路径 154
6.5.1单源最短路径 155
6.5.2任意两点间的最短路径 161
6.6拓扑排序 163
6.7关键路径 167
小结 172
习题 173
第7章 排序 176
7.1排序的基本概念 176
7.2插入排序 178
7.2.1直接插入排序 178
7.2.2希尔排序 180
7.3交换排序 182
7.3.1起泡排序 182
7.3.2快速排序 184
7.4选择排序 187
7.4.1直接选择排序 187
7.4.2堆排序 189
7.5归并排序 194
7.6基数排序 196
7.7内排序方法的比较 198
小结 200
习题 200
第8章 查找 203
8.1查找的基本概念 203
8.2顺序表查找 204
8.2.1顺序查找 205
8.2.2二分法查找 205
8.3索引查找 209
8.3.1索引表的组织 209
8.3.2分块查找 211
8.4树表查找 213
8.4.1二叉排序树 213
8.4.2平衡二叉排序树 220
8.4.3 B-树 225
8.5散列表查找 232
8.5.1散列表的概念 233
8.5.2散列函数的设计 234
8.5.3解决冲突的方法 236
8.5.4散列表的特点 239
小结 240
习题 241
附录A经典结构的典型应用程序 243
附录B习题解析及参考答案 270
参考文献 299