第1章 绪论 1
1.1数据结构的研究内容 1
1.2基本概念和术语 3
1.2.1数据、数据元素、数据项和数据对象 3
1.2.2数据结构 4
1.2.3数据类型和抽象数据类型 6
1.3抽象数据类型的表示与实现 7
1.4算法和算法分析 11
1.4.1算法的定义及特性 11
1.4.2评价算法优劣的基本标准 11
1.4.3算法的时间复杂度 12
1.4.4算法的空间复杂度 14
1.5小结 15
习题 16
第2章 线性表 18
2.1线性表的类型定义 18
2.1.1线性表的定义和特点 18
2.1.2线性表的抽象数据类型定义 18
2.2线性表的顺序表示和实现 19
2.2.1线性表的顺序存储表示 19
2.2.2顺序表中基本操作的实现 20
2.3线性表的链式表示和实现 24
2.3.1单链表的定义和表示 24
2.3.2单链表基本操作的实现 26
2.3.3循环链表 31
2.3.4双向链表 32
2.4线性表的应用 34
2.4.1一般线性表的合并 34
2.4.2有序表的合并 35
2.4.3一元多项式的表示及相加 37
2.5小结 40
习题 41
第3章 栈和队列 44
3.1栈 44
3.1.1栈的类型定义 44
3.1.2顺序栈的表示和实现 45
3.1.3链栈的表示和实现 47
3.2栈的应用 48
3.2.1数制转换 49
3.2.2括号匹配的检验 49
3.2.3表达式求值 51
3.3栈与递归 54
3.3.1采用递归算法解决的问题 54
3.3.2递归过程与递归工作栈 57
3.3.3递归算法的效率分析 59
3.3.4将递归转换为非递归的方法 60
3.4队列 61
3.4.1队列的类型定义 61
3.4.2循环队列——队列的顺序表示和实现 62
3.4.3链队——队列的链式表示和实现 65
3.5队列的应用 67
3.6小结 69
习题 69
第4章 串、数组和广义表 73
4.1串 73
4.1.1串的类型定义 73
4.1.2串的存储结构 75
4.1.3串的模式匹配算法 76
4.2数组 83
4.2.1数组的类型定义 83
4.2.2数组的顺序存储 84
4.2.3特殊矩阵的压缩存储 85
4.3广义表 87
4.3.1广义表的定义 87
4.3.2广义表的存储结构 88
4.4小结 90
习题 91
第5章 树和二叉树 94
5.1树的定义和基本术语 94
5.1.1树的定义 94
5.1.2树的基本术语 96
5.2二叉树 97
5.2.1二叉树的定义 97
5.2.2二叉树的性质 100
5.2.3二叉树的存储结构 102
5.3遍历二叉树和线索二叉树 103
5.3.1遍历二叉树 103
5.3.2线索二叉树 109
5.4树和森林 114
5.4.1树的存储结构 114
5.4.2森林与二叉树的转换 116
5.4.3树和森林的遍历 116
5.5赫夫曼树及其应用 117
5.5.1赫夫曼树的基本概念 117
5.5.2赫夫曼树的构造算法 118
5.5.3赫夫曼编码 121
5.6小结 123
习题 123
第6章 图 126
6.1图的定义和基本术语 126
6.1.1图的定义 126
6.1.2图的基本术语 128
6.2图的存储结构 129
6.2.1邻领接矩阵 130
6.2.2邻接表 132
6.3图的遍历 135
6.3.1深度优先搜索 135
6.3.2广度优先搜索 138
6.4图的应用 139
6.4.1最小生成树 139
6.4.2最短路径 144
6.4.3拓扑排序 150
6.4.4关键路径 153
6.5小结 158
习题 160
第7章 查找 164
7.1查找的基本概念 164
7.2线性表的查找 165
7.2.1顺序查找 165
7.2.2折半查找 166
7.3树表的查找 169
7.3.1二叉排序树 170
7.3.2平衡二叉树 176
7.3.3 B-树 182
7.3.4 B+树 190
7.4散列表的查找 192
7.4.1散列表的基本概念 192
7.4.2散列函数的构造方法 193
7.4.3处理冲突的方法 195
7.4.4散列表的查找 198
7.5小结 201
习题 203
第8章 排序 207
8.1基本概念和排序方法概述 207
8.1.1排序的基本概念 207
8.1.2排序方法的分类 208
8.1.3待排序记录的存储方式 208
8.1.4排序算法效率的评价指标 209
8.2插入排序 209
8.2.1直接插入排序 209
8.2.2折半插入排序 211
8.2.3希尔排序 212
8.3交换排序 214
8.3.1冒泡排序 215
8.3.2快速排序 216
8.4选择排序 219
8.4.1简单选择排序 219
8.4.2堆排序 221
8.5归并排序 226
8.6基数排序 228
8.6.1多关键字的排序 228
8.6.2链式基数排序 228
8.7小结 232
习题 233