第0章 Java程序设计基础 1
0．1Java的特点和优势 1
0．2Java语言基础 2
0．2．1语言成分 2
0．2．2流程控制语句 4
0．2．3数组 5
0．2．4字符串 7
0．3面向对象程序设计 8
0．3．1类和对象 8
0．3．2类的封装性 10
0．3．3类的继承性 14
0．34类的多态性 17
0．3．5抽象类和最终类 21
0．3．6接口 22
0．3．7内部类 23
0．3．8包 24
0．4异常处理 25
0．4．1Java的错误和异常 25
0．4．2抛出和处理异常 27
0．5Java的标准输入/输出 28
习题0． 29
实验0 Java程序设计基础 30
第1章 绪论 31
1．1数据结构的基本概念 31
1．1．1为什么要学习数据结构 31
1．1．2什么是数据结构 31
1．1．3数据的逻辑结构 33
1．1．4数据的存储结构 34
1．1．5数据操作 35
1．1．6用Java语言描述数据结构 36
1．2算法 36
1．2．1什么是算法 36
1．2．2算法分析 38
1．2．3算法设计实例 40
1．2．4递归算法 45
习题1． 47
实验1 算法设计 48
第2章 线性表 49
2．1线性表抽象数据类型 49
2．2线性表的顺序表示和实现 50
2．3线性表的链式表示和实现 55
2．3．1线性表的链式存储结构 55
2．3．2单链表 56
2．3．3双链表 67
2．4迭代器 70
2．4．1迭代接口 70
2．4．2基于迭代器的操作 71
2．4．3提供迭代器对象 71
习题2． 73
实验2 线性表的基本操作 73
第3章 栈和队列 75
3．1栈 75
3．1．1栈抽象数据类型 75
3．1．2顺序栈 76
3．1．3链式栈 77
3．1．4栈的应用 78
3．2队列 84
3．2．1队列抽象数据类型 84
3．2．2顺序队列 85
3．23链式队列 87
3．2．4队列的应用 88
习题3． 90
实验3 栈和队列及其应用 90
第4章串 92
4．1串抽象数据类型 92
4．1．1串的基本概念 92
4．1．2串抽象数据类型 93
4．2串的表示和实现 93
4．2．1串的存储结构 93
4．2．2字符串类String 94
4．2．3字符串类StringBuffer 98
4．3串的模式匹配 101
4．3．1朴素的模式匹配（Brute-Force）算法 101
4．3．2无回溯的模式匹配（KMP）算法 106
习题4． 110
实验4 串的基本操作及模式匹配应用 111
第5章 数组和广义表 112
5．1数组 112
5．1．1一维数组 112
5．1．2多维数组 112
5．2特殊矩阵的压缩存储 116
5．2．1对称（三角）矩阵的存储 116
5．2．2稀疏矩阵的压缩存储 117
5．3广义表 123
5．3．1广义表抽象数据类型 124
5．3．2广义表的存储结构 125
习题5． 127
实验5 特殊矩阵和广义表的存储和运算 127
第6章 树和二叉树 129
6．1树及其抽象数据类型 129
6．1．1树定义 129
6．1．2树的术语 130
6．1．3树的表示法 131
6．1．4树抽象数据类型 131
6．2二叉树及其抽象数据类型 132
6．2．1二叉树定义 132
6．2．2二叉树性质 132
6．2．3二叉树抽象数据类型 134
6．3二叉树的表示和实现 134
6．3．1二叉树的存储结构 134
6．3．2二叉树的二叉链表实现 136
6．3．3二叉树的遍历 137
6．3．4构造二叉树 142
6．3．5二叉树的插入和删除操作 147
6．3．6二叉树遍历的非递归算法 148
6．37二叉树的层次遍历 149
6．4线索二叉树 151
6．4．1线索二叉树定义 151
6．4．2中序线索二叉树 152
6．5哈夫曼编码与哈夫曼树 157
6．5．1哈夫曼编码 158
6．5．2哈夫曼树 159
6．6树的表示 165
6．6．1树的存储结构 165
6．6．2树的遍历 166
习题6． 167
实验6 二叉树的基本操作 168
第7章 图 170
7．1图及其抽象数据类型 170
7．1．1图的基本概念 170
7．1．2图抽象数据类型 173
7．2图的表示和实现 174
7．2．1图的邻接矩阵表示 174
7．2．2图的邻接表表示 180
7．3图的遍历 187
7．3．1图的深度优先搜索遍历 187
7．3．2图的广度优先搜索遍历 189
7．4最小生成树 191
7．4．1生成树 191
7．4．2最小生成树的构造算法 193
7．5最短路径 197
习题7． 201
实验7 图的表示和操作 202
第8章 查找 203
8．1查找的基本概念 203
8．2基于线性表的查找 204
8．2．1顺序查找 204
8．2．2基于有序顺序表的折半查找 206
8．2．3基于索引顺序表的分块查找 208
8．3树结构的查找 213
8．3．1二叉排序树及其查找 213
8．3．2平衡二叉树 219
8．4散列 220
8．4．1散列表 220
8．4．2散列函数 221
8．4．3处理冲突 222
8．4．4构造链地址法的散列表 223
习题8． 225
实验8 查找算法及其效率分析 226
第9章 排序 227
9．1排序的基本概念 227
9．2插入排序 228
9．2．1直接插入排序和折半插入排序 228
9．2．2希尔排序 230
9．3交换排序 232
9．3．1冒泡排序 232
9．3．2快速排序 233
9．4选择排序 236
9．4．1直接选择排序 236
9．4．2堆排序 237
9．5归并排序 240
习题9． 242
实验9 排序算法设计及分析 243
第10章 综合应用设计 244
10．1Java集合框架 244
10．1．1数组 244
10．1．2集合 248
10．2使用复杂的Swing组件 251
10．2．1列表框JList 252
10．2．2表格JTable 252
10．2．3树JTree 259
10．3课程设计的实例和选题 266
10．3．1用预见算法解骑士游历问题 266
10．3．2课程设计选题 271
第11章 Java开发运行环境 275
11．1JDK 275
11．1．1JDK的安装与设置 275
11．1．2运行Java Application程序 276
11．1．3查看Java类库与包等级 278
11．1．4创建、声明和导入包 278
11．2使用JCreator 280
11．2．1JCreator集成开发环境 280
11．2．2创建、编译并运行一个项目 282
11．2．3一个工作区包含多个项目 285
11．2．4配置JDK 286
11．2．5程序调试技术 288
附录A ASCII字符与Unicode值 293
附录B Java关键字 294
附录C Java基本数据类型 296
附录D Java运算符及其优先级 297
附录E java．lang语言包部分类库 298
附录F Creator4．5常用菜单命令 301
附录G本书数据结构包说明 304
【例0．1】显示字符串的Application应用程序。 3
【例0．2】声明Person类及使用对象。 9
【例0．3】封装的Person类。 12
【例0．4】Student类继承Person类。 16
【例0．5】类的多态性，Student子类重定义父类成员。 18
【例0．6】标准输入/输出。 28
【例1．1】算法时间复杂度分析。 39
【例1．2】交换两个变量值。 40
【例1．3】数组的顺序查找和对象比较相等方法。 42
【例1．4】已排序数组的顺序查找，以及对象比较大小方法。 44
【例1．5】求n！。 46
【例1．6】求Fibonacci序列。 47
【例2．1】使用顺序表类求解约瑟夫（Josephus）环问题。 54
【例2．2】采用单链表求解约瑟夫环问题。 62
【例2．3】单链表逆转。 63
【例2．4】建立排序的单链表。 66
【例3．1】判断表达式中圆括号是否匹配。 79
【例3．2】使用栈计算表达式的值。 80
【例3．3】求解素数环问题。 89
【例4．1】String类的模拟实现。 94
【例4．2】判断标识符。 97
【例4．3】使用String实现字符串的插入、删除操作。 98
【例4．4】StringBuffer类的模拟实现。 99
【例4．5】串的逆转。 101
【例4．6】Brute-Force模式匹配算法实现。 102
【例4．7】串的替换操作。 104
【例5．1】矩阵类。 114
【例5．2】稀疏矩阵的三元组顺序表实现。 118
【例6．1】构造并遍历二叉树。 139
【例6．2】输出二叉树中指定结点的所有祖先结点。 145
【例6．3】建立二叉链表表示的完全二叉树。 146
【例6．4】构造中序线索二叉树并进行中根次序遍历。 155
【例6．5】构造哈夫曼树并获得哈夫曼编码。 161
【例7．1】带权有向图的构造、插入及删除操作。 186
【例7．2】构造带权无向图的最小生成树。 195
【例7．3】求带权图的单源最短路径。 200
【例8．1】判断一个字符串是否为Java关键字。 210
【例8．2】二叉排序树的插入和查找操作。 214
【例10．1】对象数组排序和查找。 245
【例10．2】电话簿。 253
【例10．3】以树结构显示中国城市。 261
【例10．4】用预见算法解骑士游历问题。 267
【例11．1】使用命令行参数作为输入数据。 277
【例11．2】创建Hello工作区和项目。 283
【例11．3】设置命令行参数。 284
【例11．4】一个工作区包含多个项目。 286
【例11．5】使用自定义的包。 287
【例11．6】使用调试技术发现程序逻辑错误。 291