目 录 1
第1章绪论 1
1.1数据结构的基本概念 1
1.1.1抽象数据类型与数据结构 1
1.1.2数据的逻辑结构 3
1.1.3数据的存储结构 3
1.1.4数据的操作 5
1.2算法与算法设计 6
1.2.1算法 6
1.2.2算法设计 8
1.2.3算法分析 9
1.3 Java语言简介 11
1.3.1 Java的安装、编辑、编译和运行 11
1.3.2数据类型与流程控制 13
1.3.3类与对象 17
1.3.4类的继承性与多态性 19
1.3.5 Java的接口、内部类与包 21
1.3.6异常处理 23
1.3.7 Java的标准数据流 25
习题1 26
实习1 26
第2章线性表 27
2.1线性表的概念 27
2.1.1线性表的抽象数据类型 27
2.1.2线性表的顺序存储结构 28
2.1.3线性表的链式存储结构 36
2.2线性链表 37
2.2.1单向链表 37
2.2.2单向循环链表 46
2.2.3双向链表 49
2.2.4双向循环链表 52
2.3.1 串的定义 53
2.3 串 53
2.3.2串的存储结构 54
2.3.3 串的操作 54
习题2 62
实习2 62
第3章排序 63
3.1排序的基本概念 63
3.2插入排序 64
3.2.1直接插入排序 64
3.2.2希尔排序 70
3.3交换排序 73
3.3.1 冒泡排序 73
3.3.2快速排序 75
3.4选择排序 79
3.5归并排序 82
实习3 88
习题3 88
第4章栈与队列 90
4.1栈 90
4.1.1栈的定义 90
4.1.2栈的抽象数据类型 91
4.1.3栈的存储结构及实现 92
4.1.4栈的应用举例 97
4.2.1队列的定义 104
4.2 队列 104
4.2.2队列的抽象数据类型 105
4.2.3队列的存储结构及实现 105
4.2.4队列的应用举例 111
4.3递归 113
习题4 118
实习4 118
第5章数组和广义表 120
5.1 数组 120
5.1.1 一维数组 120
5.1.2多维数组 121
5.2稀疏矩阵 124
5.2.1三元组的顺序存储结构 124
5.2.2三元组的链式存储结构 128
5.3 广义表 131
5.3.1广义表的概念 131
5.3.2广义表的存储结构 133
习题5 135
实习5 135
第6章树和二叉树 136
6.1 树 136
6.1.1树的定义 137
6.1.2树的术语 137
6.1.3树的广义表形式表示 138
6.2二叉树的定义及性质 139
6.2.1二叉树的定义 139
6.2.2二叉树的性质 140
6.2.3二叉树的存储结构 141
6.2.4声明二叉树类 142
6.3二叉树的遍历 143
6.3.1二叉树遍历的概念 143
6.3.2二叉树遍历的递归算法 144
6.3.3建立二叉树 145
6.3.4二叉树遍历的非递归算法 155
6.3.5层次遍历二叉树 157
6.4.1线索二叉树的定义 159
6.4线索二叉树 159
6.4.2中序线索二叉树 161
6.5堆排序 167
6.6树与二叉树的转换 171
习题6 172
实习6 173
第7章查找 174
7.1查找的基本概念 174
7.2.1顺序查找 176
7.2线性表的查找 176
7.2.2折半查找 178
7.2.3分块查找 182
7.3二叉排序树及其查找算法 189
7.4哈希查找 194
习题7 199
实习7 199
第8章图 200
8.1图的基本知识 200
8.1.1图的定义 200
8.1.2结点的度 202
8.1.3子图 202
8.1.4路径、回路及连通性 203
8.2图的存储结构 204
8.2.1邻接矩阵 204
8.2.2邻接表 205
8.3图的遍历 206
8.3.1深度优先遍历 207
8.3.2广度优先遍历 211
8.4最小代价生成树 214
8.4.1树与图 214
8.4.2生成树 215
8.4.3最小代价生成树 216
8.5最短路径 218
习题8 219
实习8 220
第9章综合应用设计 221
9.1用“预见算法”解骑士游历问题 221
9.2综合应用实习 229
附录A ASCII码表 233
附录B Java关键字表 234
附录C Java部分类库表 236
参考文献 242