数据结构与算法应用实践教程

本书适合学过一门编程语言的各类读者，包括在读的大中专计算机专业学来自生、想转行做开发的非专业人员、欲考计算机研究生的应届或在职人员，以及工作后需要补学或温习数据结构及算法的360百科程序员等。

• 书名 数据结构与算法应用实践教程
• 作者 李文书
• ISBN 9787301200520
• 出版社 北京大学出版社
• 出版时间 2012年

内容简介

　　本书和传统同类书籍的还击新区别是除了介绍基本的数据结构知识，如线性表、栈、队列、链表、树、二叉树、AVL树、红黑树、排序和查找之外，还引进了一些C语言中的内存分配来自、结构数组和结构指针的有关概念及常见问题分析;另外，还介绍了相应知识点的应用实践。总的来说，本书选取的内容创均侧重于在实际中有广泛应用的数据结构及烈算法，有很好的实用价值。本包给材书介绍的所有数据结构及算法都以不同复杂程度给出其编码实现。为了便于读者自学，每章末附有小结及习题与思考。

　　本书系统介绍数据结构基础理论知识及算法设计方法，它在内容选取上符合计算机学科和信息类学科人才培养目标的要求及教学规律和认知规律，在组织编排上体现"先理论、后应用、理论与应用相结合"的原则，并兼顾学科的广度和深度，力求适用面广。该书的编写参考了国内外数据结构的最新教材和研究成果，全书共分为9章。第1章介绍数据结构的讨论范畴、基本概念、数据的逻辑结构、物理结构及算法的描述与分析;第2章介绍一些重要的C语言概念，同时我们还对C语言常见问题进行分析。由于本书代码都使用C语言来实现，因此具有C语言当皮年烈留措操法困队基础知识对本书的学习是必不可少的;第3章介绍线性表各种存储360百科结构及相关应用;第4章介绍差城创妒施降陈栈与队列的基本概念、各种存储免路胜你防态色态般结构及相关应用;第5章介绍字符串、多维数组和特准操一必企析是图转殊矩阵的存储结构及相关应用;第6章介绍树、二叉树和森林的基本概念、各种存储结构及遍历、线索化二叉树、二叉排序树及相关应用;第7章介绍图的概念、各种存储结构及遍历、最小生成树、关键路径、拓扑排序是门鲁居频精花做很掉补、最短路径及相关应用;第8章介绍了5种基本的排序算法，插入排序、交换排序、选择排序、归并排序和基数排序及相关应用;第9章介绍查找的基本概念、静态查找表及动态查找表的实现算法及相关应用。

图书简介

　　数据结构与算法应用实践教程/李文书主编. -北京:北京大学出版社，2012.2

　　(21世纪全国应用型本科计算机案例型规划教材)

　　ISBN 978-7-301-20052-0

　　Ⅰ. ①数… Ⅱ. ①李… Ⅲ心击总. ①数据结构-高等学校-教材②算法分析-高等学校-教材 Ⅳ. ①TP311.12

　　中国版本图书馆CIP数据核字(2012)段际加略岁第005200号

　　书 名:数据结构与算法应用实践教程

　　著作责任者:李文书 主编

　　策划编辑:郑 双

　　责任编辑:郑 双

　　标步血义轻晶准书号:ISBN 978-7-301-20052-0/TP·1211

　　出 版 者:北京大学出版社

　　地 址:北京市海淀服水错沿区成府路205号 1008和汽原操造装早酸明71

　　发 行 者:北京大学出版社

　　经 销 者:新华年模书店

　　787毫米×1092毫米 16开本 19印张 435千字

　　2012年2月第1版 2012年2月第1次印刷

　　定 价:36.00元

目录

　　第来自1章 初识数据结构.... 1

　　1.1 数据结构讨论范畴... 2

　　1360百科.2 基本概念... 3

　　1.3 数据的逻辑结构... 4

　　1.4 数据的物理结构... 6

　　1.5 算法描述与分析... 7

　　1.5.1 算法括限觉刚动的描述... 7

　　1.5.2 算法的分析... 7

　　本章小困笑统师设增快视底结... 10

　　习题与思考... 11

　　第2章 重要的C语言概念.映状线提握亲清帮... 12

　　2.1 内存分配.八.. 13

　　2.1.1 静态内存分配... 走观石支后异13

　　2.1.2 动态内存候甚沿内分配... 13

　　2.1.3 C语言程序编译的

　　内存分配... 14

　　2.2 拉结构数组和结构指针... 16

　通首　2.2.1 结构数组... 16

　　2.2.2 结构指针... 17

　　2.2.3 位结构... 18

　　2.3 C语言常见问题分析... 19

　　2.3.1 指针培意确言团席战米和数组... 20

　　2.3.2 分支语句... 20

　　2.3.3 函数编写... 21

　　2.3.4 void及void指针... 21

　　2.3.5 关于C语言的高药图妒始除外服业军效编程... 22

　　2.3.6 其他若干问题... 24

　　本章小结... 24

　　习题与思考... 25

　　第3章 线性表.... 26

　　3.1 线性表的概念... 27

　　3.1.1 线响发讨升组跟爱白往县笑性表的定义... 27

　　3.1.2 线性表的抽象数据类型描述... 27

　　3.2 线性表的顺序存储... 28

　　3.2.方助歌1 顺序表的定义... 28

　　3.2.2 顺序表的基本运算... 29

　　3.3 单向链表... 31

　　3.3.1 单向链表的基本概念... 31

　　3.3.2 单向链表的存储表示... 31

　　3.3.3 单向链表的基本操作... 32

　　3.4 循环链表... 37

　　3.5 双向链表定格... 38

　　3.5.1 双向链表的基本概念... 38

　　3.5.2 双向链表的基本操作... 38

　　3.6 应用实践... 40

　　3.6.1 单向链表排序问题... 40

　　3.6.2 自动预订飞机票问题... 41

　　3.生置木胜源烟6.3 约瑟夫(Joseph)环问题... 43

　　本章小结... 45

　　习题与思考... 46

　　距施第4章 栈与队列.... 47

　　4.1 栈... 48

　　4.1.1 栈的定义... 48

　　4.1.2 栈的顺序存储... 49

　　4.1.3 栈的链式存储... 52

　　4.2 队列... 54

　　4.2.1 队列的定义... 54

　　4.2.2 队列的顺序存储... 55

　　4.2.3 队列的链式存储... 61

　　4.3 应用实践..青团宗念功. 64

　　4.3.1 火车车厢重排问题... 64

　　4.3.2 四则运算级扩也克政父宣按扩殖要表达式求值... 67

　　4.3.3 渡口管理问题升冷草... 72

　　4.3.4 农夫过河问题... 74

　　本章小结... 77

　　习题与思考... 78

　　第5章 串、多维数组与特殊矩阵.... 79

　　5.1 串... 80

　　5.1.1 串的类型定义... 80

　　5.1.2 串的顺序存储... 81

　　5.1.3 串的链式存储... 88

　　5.2 串的模式匹配... 93

　　5.2.1 模式匹配的简单算法... 93

　　5.2.2 KMP算法... 95

　　5.2.3 KMP模式匹配改进算法... 99

　　5.3 多维数组... 100

　　5.3.1 多维数组的类型定义... 100

　　5.3.2 多维数组的顺序存储表示... 101

　　5.4 特殊矩阵的压缩存储... 102

　　5.4.1 对称矩阵... 102

　　5.4.2 三角矩阵... 103

　　5.4.3 对角矩阵... 104

　　5.5 稀疏矩阵... 105

　　5.5.1 稀疏矩阵的三元组表示法... 106

　　5.5.2 稀疏矩阵的十字链表法... 109

　　5.6 应用实践... 112

　　5.6.1 汉诺塔问题... 112

　　5.6.2 最长重复字串... 113

　　5.6.3 稀疏矩阵的相加... 114

　　5.6.4 中文分词... 116

　　本章小结... 117

　　习题与思考... 117

　　第6章 树.... 119

　　6.1 树的基本概念... 120

　　6.2 二叉树... 122

　　6.2.1 二叉树的基本概念... 122

　　6.2.2 二叉树的性质... 123

　　6.2.3 二叉树的存储结构... 125

　　6.2.4 二叉树的遍历... 129

　　6.2.5 二叉树的构造... 130

　　6.3 树和森林... 133

　　6.3.1 树、森林与二叉树的转换... 133

　　6.3.2 树和森林的存储表示... 134

　　6.3.3 树和森林的遍历... 138

　　6.4 线索二叉树... 139

　　6.4.1 线索二叉树的基本概念... 139

　　6.4.2 线索二叉树的基本操作... 142

　　6.5 二叉排序树... 146

　　6.5.1 二叉排序树的基本概念... 146

　　6.5.2 二叉排序树的生成... 147

　　6.5.3 二叉排序树的插入... 147

　　6.5.4 二叉排序树的删除... 148

　　6.6 应用实践... 149

　　6.6.1 等价类问题... 149

　　6.6.2 最优二叉树(哈夫曼树) 154

　　6.6.3 判定树问题... 162

　　本章小结... 163

　　习题与思考... 164

　　第7章 图.... 166

　　7.1 图的基本概念... 167

　　7.2 图的存储方式... 170

　　7.2.1 邻接矩阵... 171

　　7.2.2 邻接表... 172

　　7.2.3 关联矩阵... 175

　　7.3 图的遍历... 176

　　7.3.1 深度优先搜索遍历... 176

　　7.3.2 广度优先搜索遍历... 179

　　7.4 最小生成树... 181

　　7.4.1 生成树的概念... 182

　　7.4.2 最小生成树的概念... 183

　　7.4.3 普里姆(Prim)算法... 184

　　7.4.4 克鲁斯卡尔(Kruskal)算法... 186

　　7.5 最短路径... 189

　　7.5.1 单源最短路径问题... 189

　　7.5.2 每一对顶点之间的

　　最短距离... 192

　　7.6 拓扑排序... 197

　　7.6.1 什么是拓扑排序?... 197

　　7.6.2 拓扑排序的算法... 198

　　7.7 关键路径... 201

　　7.8 应用实践... 203

　　7.8.1 单源点最短路径问题... 203

　　7.8.2 自由树的直径问题... 204

　　7.8.3 医院选址问题... 205

　　本章小结... 206

　　习题与思考... 206

　　第8章 排序.... 209

　　8.1 基本概念... 210

　　8.2 插入排序... 211

　　8.2.1 直接插入排序... 211

　　8.2.2 折半插入排序... 213

　　8.2.3 希尔排序... 214

　　8.3 交换排序... 216

　　8.3.1 冒泡排序... 216

　　8.3.2 快速排序... 220

　　8.4 选择排序... 223

　　8.4.1 直接选择排序... 223

　　8.4.2 堆排序... 224

　　8.5 归并排序... 227

　　8.5.1 2-路归并的迭代算法... 228

　　8.5.2 2-路归并的递归算法... 229

　　8.6 基数排序... 229

　　8.6.1 多关键字排序... 229

　　8.6.2 链式基数排序... 230

　　8.7 排序方法比较... 234

　　8.8 应用实践... 235

　　8.8.1 荷兰国旗问题... 235

　　8.8.2 双向冒泡问题... 236

　　本章小结... 237

　　习题与思考... 237

　　第9章 查找.... 239

　　9.1 基本概念... 240

　　9.2 静态查找... 241

　　9.2.1 顺序查找... 241

　　9.2.2 折半查找... 242

　　9.2.3 分块查找... 244

　　9.3 动态查找... 245

　　9.3.1 二叉排序树查找... 245

　　9.3.2 AVL搜索树... 246

　　9.3.3 红黑树... 257

　　9.3.4 B-树... 270

　　9.3.5 B+树... 273

　　9.4 哈希查找... 273

　　9.4.1 哈希表的概念... 273

　　9.4.2 哈希函数的构造... 274

　　9.4.3 解决冲突的方法... 276

　　9.4.4 查找及分析... 280

　　9.5 应用实践... 281

　　9.5.1 直方图问题... 281

　　9.5.2 箱子装载问题... 282

　　本章小结... 284

　　习题与思考... 284

　　附录 关键词索引.... 286

　　参考文献.... 289