数据结构及其应用

第1章概述1

1.1相关概念1

1.1.1数据1

1.1.2数据元素1

1.1.3数据类型1

1.1.4数据结构2

1.2算法6

1.2.1算法概念及算法特性6

1.2.2算法的描述8

1.2.3算法的评价12

1.3数据结构与算法14

习题115

第2章线性结构及其应用17

2.1线性表的概念及基本操作17

2.1.1线性表的概念17

2.1.2线性表的基本操作18

2.2线性表的存储结构18

2.2.1顺序存储结构18

2.2.2链接存储结构19

2.3线性表基本操作的实现22

2.3.1顺序存储线性表基本操作的实现22

2.3.2单链表基本操作的实现24

2.3.3双向链表基本操作的实现28

2.3.4循环链表基本操作的实现30

2.4线性表的应用32

2.5特殊线性结构栈及其应用38

2.5.1栈及其基本操作38

2.5.2栈的存储方式38

2.5.3栈基本操作的实现40

2.5.4栈的应用43

2.6特殊线性结构队列及其应用56

2.6.1队列及其基本操作56

2.6.2队列的存储方式57

2.6.3队列基本操作的实现58

2.6.4循环队列及其基本操作的实现61

2.6.5队列的应用63

习题272

第3章线性结构的深入应用83

3.1高精度运算83

3.1.1基本算法83

3.1.2应用实例85

3.1.3拓展98

3.2排序98

3.2.1简单排序算法99

3.2.2算法的改进101

3.2.3应用实例105

3.3查找109

3.3.1顺序表的查找109

3.3.2二分查找110

3.3.3索引查找112

3.3.4应用实例112

3.4散列查找114

3.4.1散列表的概念114

3.4.2散列函数的构造115

3.4.3处理冲突的方法116

3.4.4应用实例120

3.5分治126

3.5.1分治算法解决问题模式126

3.5.2应用实例126

3.6递推133

3.6.1递推算法133

3.6.2常见递推关系140

3.6.3应用实例141

3.7动态规划初探145

3.7.1动态规划的定义145

3.7.2动态规划的基本概念148

3.7.3应用实例150

习题3154

第4章层次结构(树)及其应用162

4.1从线性结构到层次结构广义表及其操作162

4.1.1广义表概念及存储结构162

4.1.2广义表的建立与输出164

4.1.3广义表的应用165

4.2树的基本概念166

4.2.1树的定义166

4.2.2树的表示方法167

4.2.3树的基本术语168

4.3二叉树的基本知识168

4.3.1二叉树基本概念168

4.3.2二叉树的性质168

4.3.3二叉树的存储结构170

4.3.4二叉树的建立算法171

4.3.5二叉树的基本运算172

4.4二叉树的应用176

4.5特殊二叉树及其应用182

4.5.1二叉排序树182

4.5.2哈夫曼树184

4.5.3哈夫曼编码187

4.6层次结构的综合应用188

习题4194

第5章网状结构(图)及其应用200

5.1网状结构(图)的基本知识200

5.1.1图的基本概念201

5.1.2图的连通性203

5.2图的存储结构204

5.2.1邻接矩阵204

5.2.2邻接表205

5.2.3边集数组208

5.2.4邻接压缩表209

5.2.5几种存储结构比较209

5.3图的遍历210

5.3.1图的深度优先遍历210

5.3.2图的广度优先遍历211

5.3.3应用实例213

5.4图的应用221

5.4.1求图的某个通路221

5.4.2求图的最小生成树236

5.4.3求图的最短路径240

5.4.4图的拓扑排序及关键路径246

习题5251

第6章数据结构深入应用257

6.1概述257

6.2从数据结构与算法的关系优化算法257

6.2.1数学建模与算法优化257

6.2.2时空优化与搜索算法265

6.3数据结构与动态规划277

6.3.1线性结构与动态规划277

6.3.2树型结构与动态规划289

6.4综合应用举例297

6.5总结313

习题6313

参考文献320

　　本教材遵循青少年信息学奥林匹克竞赛大纲的要求，深入浅出地介绍了数据结构的基本知识、数据结构在程序设计中的作用以及数据结构与算法之间的关系。本教材将数据结构知识与算法设计有机结合，使读者了解数据结构在算法设计中的作用。　　本书是面向青少年信息学奥林匹克竞赛活动训练的教材。本书共分为6章，分别是概述(数据结构基础)、线性结构及其应用、线性结构的深入应用、层次结构(树)及其应用、网状结构(图)及其应用、数据结构深入应用。本书以最主要的三种数据组织的逻辑结构(线性、层次、网状)为主线，将数据结构知识恰当地应用到实际问题的解决中，详细分析了每一种逻辑结构的不同的存储方式以及基于不同存储方式建立的对问题求解的算法。每章均配有适量习题。　　本书特色是描述简单、易懂、易学，有机地将实际问题求解、竞赛问题求解与数据结构紧密结合，使读者感悟到数据结构与算法之间的关系，体会数据结构的具体应用之奥妙。　　本书也可以作为大学生学习数据结构的配套辅导教材。