第1章 绪论 1
1.1从问题到程序 1
1.2有关概念和术语 3
1.3算法及算法分析 6
1.3.1算法特性 6
1.3.2算法描述 7
1.3.3算法分析 8
1.4关于数据结构的学习 9
1.5关于本书内容编写说明 11
本章小结 11
习题1 11
第2章 线性表 14
2.1线性表的逻辑结构 14
2.1.1线性表的定义 14
2.1.2线性表的基本运算 14
2.2线性表的顺序存储及其运算的实现 15
2.2.1顺序表 15
2.2.2顺序表基本运算的实现 17
2.2.3顺序表的其他运算举例 20
2.3线性表的链式存储及其运算的实现 22
2.3.1单链表 23
2.3.2单链表基本运算的实现 24
2.3.3循环链表 30
2.3.4双向链表 30
2.3.5单链表的其他运算举例 32
2.4典型例题 34
本章小结 36
习题2 37
第3章 栈和队列 39
3.1栈 39
3.1.1栈的定义及其基本运算 39
3.1.2栈的存储结构和基本运算的实现 40
3.1.3栈的应用举例 42
3.1.4栈与递归的实现 46
3.2队列 50
3.2.1队列的定义及其基本运算 50
3.2.2队列的存储结构和基本运算的实现 51
3.2.3队列应用举例 56
3.3典型例题 57
本章小结 59
习题3 60
第4章 串和数组 64
4.1串 64
4.1.1串的基本概念 64
4.1.2串的基本运算 65
4.1.3串的存储结构及其基本运算的实现 65
4.1.4串的其他运算举例 68
4.2数组 68
4.2.1数组的逻辑结构和基本运算 68
4.2.2数组的存储结构 70
4.2.3稀疏矩阵 71
4.2.4矩阵的其他运算举例 74
4.3典型例题 75
本章小结 76
习题4 77
第5章 树与二叉树 79
5.1树的概念与基本运算 79
5.1.1树的定义及相关术语 79
5.1.2树的基本运算 81
5.2二叉树 81
5.2.1二叉树的基本概念 81
5.2.2二叉树的主要性质 83
5.2.3二叉树的存储结构与基本运算 85
5.2.4二叉树的遍历 88
5.2.5线索二叉树 92
5.2.6二叉树的其他运算举例 95
5.3树与森林 98
5.3.1树的存储 98
5.3.2树、森林与二叉树的相互转换 100
5.3.3树和森林的遍历 102
5.4最优二叉树——哈夫曼树 103
5.4.1哈夫曼树的基本概念 103
5.4.2哈夫曼树的构造算法 105
5.4.3哈夫曼编码 106
5.4.4哈夫曼编码的算法实现 108
5.5典型例题 109
本章小结 111
习题5 112
第6章 图 116
6.1图的基本概念 116
6.1.1图的定义和术语 116
6.1.2图的基本运算 118
6.2图的存储结构 119
6.2.1邻接矩阵 119
6.2.2邻接表 121
6.3图的遍历 123
6.3.1深度优先搜索 123
6.3.2广度优先搜索 124
6.4图的应用 126
6.4.1最小生成树 126
6.4.2最短路径 129
6.4.3拓扑排序 135
6.5典型例题 137
本章小结 142
习题6 142
第7章 查找 146
7.1基本概念与术语 146
7.2静态查找表 147
7.2.1静态查找表结构 147
7.2.2顺序查找 148
7.2.3有序表的折半查找 149
7.2.4分块查找 152
7.3动态查找表 153
7.3.1二叉排序树 153
7.3.2平衡二叉树及B树 156
7.4哈希表 158
7.4.1哈希表与哈希方法 158
7.4.2常用的哈希函数构造方法 159
7.4.3处理冲突的方法 161
7.4.4哈希表的查找算法 163
7.4.5哈希表的性能分析 163
7.5典型例题 164
本章小结 170
习题7 170
第8章 排序 174
8.1基本概念 174
8.2三种简单的排序方法 175
8.2.1直接插入排序 175
8.2.2冒泡排序 176
8.2.3简单选择排序 179
8.3希尔排序 180
8.4快速排序 181
8.5堆排序 184
8.6归并排序 186
8.7基数排序 188
8.7.1多关键码排序 188
8.7.2链式基数排序 189
8.8各种排序方法的比较与讨论 191
8.9典型例题 192
本章小结 195
习题8 195
第9章 实验 199
实验1顺序表的基本运算 199
实验2链表的基本运算 204
实验3栈的基本运算 210
实验4队列的基本运算 217
实验5串的基本运算 227
实验6二叉树的基本运算 232
实验7二叉树的遍历和哈夫曼树 238
实验8图的基本运算 245
实验9查找 251
实验10排序 257
参考文献 262