第1章基础知识/1

1.1数据结构研究什么/1

1.2基本概念和有关术语/3

1.3数据类型与抽象数据类型/4

1.3.1数据类型/4

1.3.2抽象数据类型/4

1.4算法描述与算法分析/6

1.4.1算法的描述/6

1.4.2算法的时间复杂度分析/7

1.4.3算法的空间复杂度分析/8

1.5小结/8

1.6经典题库/9

1.6.1要点提醒/9

1.6.2经典剖析/9

1.7练习/11第2章线性存储结构/13

2.1线性表的定义及基本操作/13

2.1.1线性表的基本概念/13

2.1.2线性表的抽象数据类型/14

2.2线性表顺序存储结构的定义/15

2.2.1线性表顺序存储结构的定义/15

2.2.2顺序表的基本操作及实现/16

2.2.3顺序表的应用/18

2.3线性表链式存储结构与实现/20

2.3.1线性表链式存储结构/21

2.3.2单链表及其基本操作/21

2.3.3循环链表的基本操作及实现/29

2.3.4双链表的基本操作及实现/33

2.3.5循环双链表/37

2.4实验/38

实验一： 顺序表的操作/38实验二： 单链表连接/40

实验三： 循环链表连接/43

实验四： 循环双链表操作/47

2.5小结/52

2.6经典题库/52

2.6.1要点提醒/52

2.6.2经典剖析/53

2.7练习/61第3章栈/65

3.1栈/65

3.1.1栈的基本概念/65

3.1.2栈的抽象数据类型/65

3.1.3栈的顺序存储结构及实现/66

3.1.4栈的链式存储结构与实现/70

3.2栈的应用/74

3.2.1表达式求值/74

3.2.2数制转换/76

3.2.3括号匹配检验/77

3.2.4栈与递归的实现/78

3.3实验/79

实验： 利用栈寻找迷宫路径/79

3.4小结/82

3.5经典题库/82

3.5.1要点提醒/82

3.5.2经典剖析/83

3.6练习/86第4章队列/90

4.1队列/90

4.1.1什么是队列/90

4.1.2队列的抽象数据类型/90

4.1.3队列的顺序存储结构与实现/91

4.1.4队列的链式存储结构与实现/97

4.2队列的应用/101

4.3实验/105

实验： 利用队列模拟病人看病/105

4.4小结/109

4.5经典题库/109

4.5.1要点提醒/109

4.5.2经典剖析/109

4.6练习/112第5章串/116

5.1串的定义/116

5.1.1串的定义/116

5.1.2串的抽象数据类型/116

5.2串的存储结构与实现/118

5.2.1串的顺序存储结构与实现/118

5.2.2串的堆存储结构与实现/121

5.2.3串的块链存储结构与实现/122

5.3串的模式匹配算法/123

5.3.1简单的模式匹配算法——BF算法/123

5.3.2改进的模式匹配算法——KMP

算法/125

5.4串的应用/127

5.5实验/128

实验一： 显示多位数数字字符/128

实验二： 块链的基本操作/130

实验三： 统计串中最长的重复子串/135

5.6小结/137

5.7经典题库/138

5.7.1要点提醒/138

5.7.2经典剖析/138

5.8练习/140第6章数组与广义表/142

6.1数组的定义/142

6.1.1数组的概念与性质/142

6.1.2抽象数据类型/143

6.2数组相关结构的实现/143

6.2.1数组的顺序存储/143

6.2.2数组的基本操作实现/144

6.3矩阵的压缩存储探究/147

6.3.1特殊矩阵/147

6.3.2稀疏矩阵/149

6.4广义表/153

6.4.1广义表相关概念/153

6.4.2抽象数据类型/154

6.4.3广义表存储结构详解/155

6.4.4广义表的相关应用/156

6.5实验/157

实验一： 矩阵乘法/157

实验二： 三元组实现两个矩阵的乘法/160

实验三： 广义表的基本运算/163

6.6小结/168

6.7经典题库/169

6.7.1要点提醒/169

6.7.2经典剖析/169

6.8练习/172第7章树型结构/175

7.1树的基本概念和术语/175

7.1.1树的基本概念/175

7.1.2基本术语/175

7.2二叉树/176

7.2.1二叉树的基本概念/176

7.2.2二叉树性质的探究/178

7.2.3抽象数据类型/179

7.2.4存储结构/181

7.3遍历二叉树的方法/185

7.3.1遍历的定义/185

7.3.2遍历算法探究/186

7.4线索二叉树/189

7.5树和森林/192

7.5.1树的存储结构/192

7.5.2二叉树与森林/194

7.5.3树和森林的遍历探究/195

7.6哈夫曼树/196

7.6.1哈夫曼树的基本概念/196

7.6.2哈夫曼树的构造算法/197

7.6.3哈夫曼树和哈夫曼编码/199

7.7实验/201

实验一: 运算二叉树/201

实验二: 统计二叉树结点的个数/203

实验三: 统计二叉树的宽度/205

实验四: 按层遍历二叉树/207

7.8小结/210

7.9经典题库/210

7.9.1要点提醒/210

7.9.2经典剖析/210

7.10练习/217第8章图状结构/220

8.1图的相关定义和术语/220

8.1.1图的基本概念/220

8.1.2图的基本术语/220

8.1.3抽象数据类型/222

8.2图的存储结构探究/223

8.2.1邻接矩阵/223

8.2.2邻接表/225

8.2.3十字链表/227

8.2.4多重邻接表/228

8.3图的遍历/229

8.3.1深度优先遍历/229

8.3.2广度优先遍历/230

8.4最小生成树/231

8.4.1生成树的概念/231

8.4.2最小生成树/231

8.4.3Prim算法/235

8.5最短路径探究/238

8.5.1单源点最短路径问题分析/238

8.5.2所有顶点对应最短路径问题分析/240

8.6拓扑排序探究/241

8.7关键路径/244

8.8实验/244

实验一: 遍历算法/244

实验二: Prim算法/248

8.9小结/253

8.10经典题库/253

8.10.1要点提醒/253

8.10.2经典剖析/253

8.11练习/264第9章查找/269

9.1查找的基本概念/269

9.2静态查找表/269

9.2.1顺序表的查找/269

9.2.2有序表的查找/270

9.2.3索引顺序表的查找/271

9.2.4静态树表的查找/273

9.3动态查找表/274

9.3.1二叉排序树/274

9.3.2平衡二叉树/276

9.3.3B-和B+树/280

9.3.4键树/288

9.4哈希表/289

9.4.1哈希表的概念/289

9.4.2哈希表的构造方法/289

9.4.3处理冲突的方法/290

9.4.4哈希表的查找及分析/293

9.5实验/294

实验一: 二叉排序树的查找/294

实验二: 哈希查找/298

9.6小结/300

9.7经典题库/301

9.7.1要点提醒/301

9.7.2经典剖析/301

9.8练习/308第10章内部排序/310

10.1插入排序/310

10.1.1直接插入排序/310

10.1.2希尔排序/311

10.2交换排序/313

10.2.1冒泡排序/313

10.2.2快速排序/315

10.3选择排序/316

10.3.1简单选择排序/316

10.3.2堆排序/317

10.4归并排序/320

10.5基数排序/321

10.6各种内排序方法的比较/324

10.7实验/325

实验一: 双向冒泡排序/325

实验二: 数组归并排序/328

实验三: 计数排序/331

实验四: 字符串排序/332

实验五: 最高位关键字排序MSD/335

10.8小结/338

10.9经典题库/338

10.9.1要点提醒/338

10.9.2经典剖析/339

10.10练习/343第11章经典算法/345

11.1基础算法/345

11.1.1河内之塔/345

11.1.2八皇后/346

11.1.3背包问题/348

11.2数、运算/352

11.2.1筛选求质数/352

11.2.2最大公因数、最小公倍数、因式

分解/353

11.2.3最大访客数/356

11.3关于博弈/358

11.3.1洗扑克牌(乱数排列)/358

11.3.2Craps赌博游戏/360

11.4集合问题/362

11.4.1格雷码(Gray Code)/362

11.4.2m元素集合的n元子集/364

11.5矩阵/365

11.5.1稀疏矩阵存储/365

11.5.2上三角、下三角、对称矩阵存储/367

11.5.3奇数魔方阵/369第12章数据分析与挖掘/371

12.1大数据时代的挖掘/371

12.1.1数据挖掘/371

12.1.2从数据挖掘应用的角度看大

数据/372

12.2挖掘技术发展和历史/373

12.3十大挖掘算法简介/374参考文献/378