第1章 概论 1
1.1基本概念与术语 1
1.2数据结构的概念 3
1.3数据的逻辑结构 5
1.3.1数据结构的形式化定义 5
1.3.2数据的逻辑结构类型 5
1.4数据的存储结构 6
1.4.1顺序存储方法 6
1.4.2链式存储方法 6
1.4.3索引存储方法 7
1.4.4散列存储方法 7
1.5数据的运算 7
1.6算法与算法特性 8
1.6.1算法及其特性 8
1.6.2算法的描述方法 8
1.6.3算法与程序及数据结构 10
1.7算法性能分析 10
1.8算法度量 11
1.8.1算法时间复杂度 11
1.8.2复杂度函数的增长率 13
小结 15
习题1 15
第2章 线性表 16
2.1线性表定义及其运算 16
2.1.1线性表 16
2.1.2线性表的运算 17
2.2线性表的顺序存储 19
2.2.1顺序存储结构 19
2.2.2顺序结构线性表的运算 20
2.2.3顺序存储结构的特点 22
2.3线性表的链式存储 23
2.3.1线性链表 23
2.3.2线性链表的运算 26
2.3.3循环链表 29
2.3.4循环链表的运算 29
2.3.5双向链表 30
2.3.6双向链表的运算 31
2.3.7链式存储结构的特点 32
2.4链式存储结构的应用 33
小结 36
习题2 36
第3章 栈和队列 38
3.1栈 38
3.1.1栈的定义及其运算 38
3.1.2栈的顺序存储结构及其运算的实现 39
3.1.3栈的链式存储结构 43
3.2栈的应用 44
3.2.1子程序的调用问题 44
3.2.2算术表达式求值 44
3.3队列 47
3.3.1队列的定义 47
3.3.2队列的顺序存储 47
3.3.3队列的链式存储 52
3.4队列的应用 55
小结 56
习题3 56
第4章 串 58
4.1串的基本概念 58
4.2串的存储结构 59
4.2.1串的静态存储结构 59
4.2.2串的动态存储结构 61
4.3串的基本运算 62
4.3.1常见的基本运算 62
4.3.2实现串的基本运算的算法 63
4.4模式匹配 65
4.5串在文本编辑中的应用 67
小结 68
习题4 68
第5章 数组 70
5.1数组及其基本操作 70
5.1.1数组的概念 70
5.1.2数组的基本操作 72
5.2数组的存储结构 72
5.3数组在矩阵运算中的应用 75
5.3.1特殊矩阵的压缩存储 75
5.3.2稀疏矩阵的压缩存储 77
小结 83
习题5 83
第6章 树 85
6.1树 85
6.1.1树的定义 85
6.1.2树的常用术语 86
6.1.3树的基本操作 87
6.2二叉树 87
6.2.1二叉树的定义 87
6.2.2二叉树的存储结构 89
6.2.3二叉树的遍历 91
6.2.4二叉树遍历的应用 93
6.3线索二叉树 94
6.4树、森林和二叉树的关系 97
6.4.1树的存储结构 97
6.4.2森林与二叉树的转换 100
6.4.3树和森林的遍历 102
6.5哈夫曼树 103
6.5.1哈夫曼树的定义 103
6.5.2哈夫曼树的构造 104
小结 105
习题6 105
第7章 图 108
7.1图的概念及其操作 109
7.1.1图的概念 109
7.1.2图的基本操作 113
7.2图的存储结构 113
7.2.1邻接矩阵 113
7.2.2邻接表 115
7.2.3十字链表 118
7.2.4邻接多重表 119
7.3图的遍历 121
7.3.1深度优先搜索 121
7.3.2广度优先搜索 123
7.4图的应用 124
7.4.1生成树 124
7.4.2最短路径 128
7.4.3拓扑排序 131
7.5关键路径法 133
小结 139
习题7 139
第8章 查找 142
8.1基本概念 142
8.2线性表的查找 143
8.2.1顺序查找 143
8.2.2折半查找 145
8.2.3分块查找 147
8.3二叉查找树 148
8.4哈希表的查找 152
8.4.1哈希表 152
8.4.2构造哈希表的基本方法 153
8.4.3解决冲突的方法 154
8.5各种查找方法的比较 156
小结 157
习题8 157
第9章 排序 159
9.1基本概念 159
9.2内部排序 161
9.2.1插入排序 161
9.2.2冒泡排序 164
9.2.3快速排序 166
9.2.4选择排序 168
9.2.5归并排序 173
9.3内部排序方法比较 176
小结 177
习题9 177
第10章 递归 179
10.1递归的定义与类型 179
10.1.1递归的定义 179
10.1.2递归的类型 179
10.2递归应用举例 180
10.2.1汉诺塔问题 180
10.2.2八皇后问题 182
10.3递归的实现 183
10.4递归到非递归的转换过程 187
10.5递归的时间和空间复杂度 190
小结 191
习题10 191
参考文献 192