数据结构教程 Java语言描述PDF电子书下载

第1章　课程概论 1

1.1　课程的初步认识 1

1.2　数据结构的基本概念 3

1.2.1　基本术语 3

1.2.2　数据结构的概念 3

1.2.3　逻辑结构和物理结构 4

1.2.4　数据结构形式的定义 4

1.3　数据类型及面向对象的概念 5

1.3.1　数据类型概述 5

1.3.2　抽象数据类型 6

1.3.3　实现方法 6

1.3.4　面向对象的概念 8

1.4　算法及算法分析 9

1.4.1　算法特性 10

1.4.2　算法描述 10

1.4.3　算法的设计要求 11

1.4.4　算法分析 11

习题1 14

第2章　线性表 15

2.1　线性表的相关概念及抽象数据类型 15

2.1.1　线性表的相关概念 15

2.1.2　线性表抽象数据类型描述 16

2.1.3　线性表的接口定义 17

2.2　顺序表类 18

2.2.1　顺序表的存储结构 18

2.2.2　顺序表的类定义 19

2.2.3　顺序表类的实现 21

2.2.4　顺序表算法设计举例 24

2.3　单链表类 27

2.3.1　单链表的存储结构 27

2.3.2　单链表的类定义 28

2.3.3　单链表类的实现 30

2.3.4　单链表算法设计举例 34

2.4　双向循环链表类 35

2.4.1　双向循环链表的存储结构 35

2.4.2　双向循环链表的类定义 36

2.4.3　双向循环链表类的实现 38

2.5　线性表应用举例 42

2.5.1　线性表功能演示程序 42

2.5.2　进程调度模拟程序 44

习题2 49

第3章　栈 50

3.1　栈的相关概念及抽象数据类型 50

3.1.1　栈的相关概念 50

3.1.2　栈抽象数据类型描述 51

3.1.3　栈的接口定义 52

3.2　顺序栈类 52

3.2.1　顺序栈的存储结构 52

3.2.2　顺序栈的类定义及实现 53

3.2.3　顺序栈算法设计举例 55

3.3　链栈类 56

3.3.1　链栈的存储结构 57

3.3.2　链栈的类定义及实现 57

3.3.3　链栈算法设计举例 60

3.4　栈的应用举例 61

3.4.1　括号配对问题 61

3.4.2　表达式求值 63

3.4.3　栈功能演示程序 68

习题3 71

第4章 队列 73

4.1 队列的相关概念及抽象数据类型 73

4.1.1　队列的相关概念 73

4.1.2　队列抽象数据类型描述 74

4.1.3　队列的接口定义 74

4.2　链队列类 75

4.2.1　链队列的存储结构 75

4.2.2　链队列的类定义及实现 76

4.2.3　链队列算法设计举例 79

4.3　循环队列类 80

4.3.1 队列的顺序存储结构 80

4.3.2　循环队列类的定义及实现 83

4.3.3　循环队列算法设计举例 85

4.4　队列的应用举例 87

4.4.1　显示杨辉三角形 87

4.4.2　表达式（逆波兰表示）求值 90

4.4.3　循环队列功能演示程序 93

习题4 96

第5章 串 97

5.1 串的相关概念及抽象数据类型 97

5.1.1　串的相关概念 97

5.1.2　串抽象数据类型描述 98

5.1.3　串的接口定义 99

5.2　串的存储结构 100

5.2.1　顺序存储结构 100

5.2.2　链式存储结构 101

5.2.3　堆存储结构 101

5.3 串值不变的顺序串类Str1 101

5.3.1　Str1的类定义 102

5.3.2　求子串、定位操作的实现 103

5.3.3　删除、插入及替换操作的实现 106

5.3.4　Str1类算法设计举例 108

5.4　串值可变的顺序串类Str2 110

5.4.1 Str2类的定义 110

5.4.2　Str2类的实现 110

5.4.3　Str2类算法设计举例 112

5.5　串的应用举例 113

5.5.1　字符串类功能演示程序 113

5.5.2　文本文件单词统计程序 115

习题5 117

第6章　数组、矩阵和集合 118

6.1　数组 118

6.1.1　数组的相关概念及抽象数据类型 118

6.1.2　数组类的定义及实现 119

6.2　矩阵概述 121

6.2.1　矩阵的相关概念 121

6.2.2　矩阵的存储方式 122

6.3　矩阵类 123

6.3.1　矩阵类的定义 123

6.3.2　矩阵类的实现 124

6.3.3　矩阵类算法设计举例 127

6.4　矩阵的压缩存储 128

6.4.1　对称矩阵的压缩存储 128

6.4.2　对角矩阵的压缩存储 129

6.4.3　稀疏矩阵的压缩存储 130

6.5　稀疏矩阵类 133

6.5.1　稀疏矩阵类的定义 133

6.5.2　稀疏矩阵类的实现 134

6.5.3　稀疏矩阵类算法设计举例 137

6.6　集合 138

6.6.1　集合的相关概念及抽象数据类型 138

6.6.2　整数集合类 139

6.7　应用举例 142

6.7.1　在二维数组中存储对称矩阵 142

6.7.2　整数集合类应用程序 143

习题6 144

第7章　递归算法 146

7.1　递归的概念 146

7.2　递归函数的设计方法 148

7.2.1 由递归定义设计递归函数 148

7.2.2　回溯法求解的一般模式 150

7.3　算法设计举例 150

7.4　递归算法的非递归化实现 153

7.4.1 自底向上的递推 153

7.4.2　为递归参数设置循环 153

7.4.3　自顶向下的递推 154

7.4.4　使用无标号递归工作栈 155

7.5　递归算法应用举例 157

7.5.1　方螺旋线求解程序 157

7.5.2　八皇后问题求解程序 160

7.5.3　迷宫问题演示程序 162

习题7 166

第8章　广义表 167

8.1　广义表的相关概念及抽象数据类型 167

8.1.1　广义表的相关概念 167

8.1.2　广义表抽象数据类型描述 168

8.2　广义表的存储方式 169

8.2.1　头尾表示法 169

8.2.2　儿子兄弟表示法 171

8.3　广义表类的定义及实现 172

8.3.1　广义表类的定义 172

8.3.2　建立广义表的存储结构 175

8.3.3　取头、取尾操作的实现 178

8.3.4　插入、删除操作的实现 179

8.4　广义表的递归算法 179

8.4.1　广义表的相等比较 179

8.4.2　广义表的成员判别 180

8.4.3　求广义表的深度 181

8.4.4　广义表递归算法设计举例 182

8.5　广义表应用举例 185

8.5.1　广义表演示程序 185

8.5.2　LISP表达式求值 187

习题8 189

第9章　树与二叉树 190

9.1　树的相关概念及抽象数据类型 190

9.1.1　树的定义 190

9.1.2　树的逻辑表示 191

9.1.3　基本术语 192

9.1.4　树抽象数据类型描述 193

9.2　二叉树 194

9.2.1　二叉树的定义及抽象数据类型 194

9.2.2　二叉树的基本性质 194

9.2.3　二叉树的存储结构 196

9.2.4　二叉树类的定义 198

9.2.5　二叉树类的实现 201

9.2.6　二叉树的遍历 204

9.2.7　二叉树算法设计举例 208

9.3　排序二叉树 209

9.3.1　排序二叉树的定义 209

9.3.2　排序二叉树类的定义 209

9.3.3　排序二叉树类的实现 210

9.4　树与森林 211

9.4.1　树的存储结构 211

9.4.2　森林与二叉树的转换 213

9.4.3　树的遍历 214

9.5 哈夫曼树 214

9.5.1 哈夫曼树的定义 215

9.5.2 哈夫曼树的构造 216

9.5.3 哈夫曼编码 216

9.6　树的应用举例 218

9.6.1 哈夫曼编码生成程序 218

9.6.2　二叉树遍历演示程序 221

习题9 224

第10章　图 226

10.1 图的相关概念及抽象数据类型 226

10.1.1 图的定义 226

10.1.2　基本术语 228

10.1.3　图抽象数据类型描述 230

10.2　图的存储方式 230

10.2.1　邻接矩阵 230

10.2.2　邻接链表 232

10.2.3　邻接多重表 234

10.3 图的遍历 235

10.3.1　邻接链表图类 235

10.3.2　深度优先搜索遍历 237

10.3.3　广度优先搜索遍历 238

10.3.4　算法设计举例 240

10.4　图的应用 242

10.4.1　拓扑排序 242

10.4.2　最短路径 246

10.5　图的应用程序设计举例 249

10.5.1　图的遍历演示程序 249

10.5.2　最短路径应用程序 253

习题10 254

第11章　查找 256

11.1　查找的相关概念 256

11.2　静态查找表 257

11.2.1　顺序表的查找 257

11.2.2　有序表的查找 260

11.2.3　静态树表的查找 263

11.2.4　索引顺序表的查找 266

11.3 动态查找表 267

11.3.1　排序二叉树的查找 267

11.3.2　B－树与B＋树 272

11.4　哈希表 277

11.4.1　哈希表的概念 277

11.4.2　常用哈希函数 279

11.4.3　冲突的处理方法 281

11.4.4　哈希表的查找 283

11.5　查找应用程序举例 284

11.5.1　排序二叉树演示程序 284

11.5.2　图书信息查询程序 285

习题11 289

第12章　排序 291

12.1　排序的相关概念 291

12.2　几种简单的排序算法 293

12.2.1　直接插入排序 293

12.2.2 冒泡排序 295

12.2.3 直接选择排序 297

12.3　几种快速的排序方法 300

12.3.1　快速排序 300

12.3.2　树型选择排序 303

12.3.3　堆排序 304

12.3.4　归并排序 309

12.4　基数排序 311

12.5　排序应用程序举例——排序算法演示程序 314

习题12 317

附录 319

附录A　Java语言概要（与C＋＋语言比较）&3 19

附录B　Java语言中的常用类 323

附录C　JBuilderX开发环境及操作步骤 329

附录D　部分习题参考答案 333

参考文献 343