
数据结构与算法是计算机科学中一门综合性的专业基础课,它不仅是计算机学科的核心课程,而且已成为其他非计算机专业的热门选修课之一。
本书从抽象类型的角度描述了各种逻辑结构,即线性结构、树形结构、集合和图形结构。书中由简单到复杂,循序渐进,对各种数据结构从逻辑结构、存储结构和基本操作方面进行了详细的介绍;本书另外一个特点是对各种算法进行了算法分析,对典型算法还给出了算法正确性的证明。最后一章对一些常用的算法,如“分而治之法”、“动态规划法”、“贪心法”和“回溯法”等技术进行了详细的介绍,为设计高效的程序,即以最小的成本、最快的速度和最好的质量开发出适合各种应用需求的软件奠定了基础。
全书从面向对象的角度出发,利用C++语言对书中的算法进行了描述,并配有注解,有利于读者的理解;本书概念严谨、语言通俗易懂、条理清楚、图文并茂,既便于教学,又便于自学。
本书可作为计算机类专业或信息类专业的本科或专科教材,也可作为有关科研人员的参考书。
数据结构与算法是计算机科学中一门综合性的专业基础课,它不仅是计算机学科的核心课程,而且已成为其他非计算机专业的热门选修课之一。
本书从抽象类型的角度描述了各种逻辑结构,即线性结构、树形结构、集合和图形结构。书中由简单到复杂,循序渐进,对各种数据结构从逻辑结构、存储结构和基本操作方面进行了详细的介绍;本书另外一个特点是对各种算法进行了算法分析,对典型算法还给出了算法正确性的证明。最后一章对一些常用的算法,如“分而治之法”、“动态规划法”、“贪心法”和“回溯法”等技术进行了详细的介绍,为设计高效的程序,即以最小的成本、最快的速度和最好的质量开发出适合各种应用需求的软件奠定了基础。
全书从面向对象的角度出发,利用C++语言对书中的算法进行了描述,并配有注解,有利于读者的理解;本书概念严谨、语言通俗易懂、条理清楚、图文并茂,既便于教学,又便于自学。
本书可作为计算机类专业或信息类专业的本科或专科教材,也可作为有关科研人员的参考书。
第1章 概述1
1.1 数据结构的发展1
1.2 数据结构2
1.2.1 数据结构简介2
1.2.2 基本概念4
1.3 数据的逻辑结构4
1.3.1 预备知识5
1.3.2 数据结构的分类6
1.4 抽象数据类型7
1.5 数据的存储结构9
1.5.1 顺序存储结构9
1.5.2 链式存储结构10
1.6 算法与算法分析10
1.6.1 算法11
1.6.2 算法性能分析和度量11
1.6.3 算法的描述16
1.7 ADT的表示与实现间的关系19
习题119
第2章 基本数据结构21
2.1 线性表21
2.1.1 ADT线性表21
2.1.2 线性表的顺序存储23
2.1.3 线性表的链式存储27
2.2 数组34
2.2.1 数组的定义35
2.2.2 数组的存储35
2.2.3 特殊矩阵37
2.2.4 稀疏矩阵39
2.3 字符串44
2.3.1 串的表示与实现44
2.3.2 串的模式匹配算法49
习题255
◆数据结构与算法目 录第3章 栈、队列与广义表57
3.1 栈57
3.1.1 ADT栈57
3.1.2 栈的实现58
3.1.3 栈与递归61
3.2 队列65
3.2.1 ADT 队列65
3.2.2 队列的实现66
3.3 栈与队列的应用71
3.3.1 栈的应用71
3.3.2 队列的应用78
3.4 广义表79
3.4.1 广义表的定义和基本运算79
3.4.2 广义表的存储结构82
3.4.3 广义表基本操作的实现85
习题387
第4章 树与二叉树90
4.1 树的定义和相关术语90
4.2 二叉树92
4.2.1 ADT二叉树92
4.2.2 二叉树的遍历93
4.2.3 二叉树的性质95
4.2.4 二叉树的实现96
4.2.5 二叉树遍历的非递归实现106
4.2.6 线索二叉树109
4.3 树与森林113
4.3.1 树与森林的遍历114
4.3.2 树的存储结构114
4.4 森林与二叉树的关系116
4.5 Huffman树与编码117
4.5.1 Huffman树118
4.5.2 Huffman编码119
习题4125
第5章 集合与查找127
5.1 集合及其实现127
5.1.1 ADT集合127
5.1.2 用位向量实现集合128
5.2 具有Merge、Find的ADT集合131
5.2.1 ADT MFSet集合131
5.2.2 MFSet的实现131
5.2.3 MFSet实现算法的改进133
5.2.4 MFSet的应用--求等价类135
5.3 静态查找136
5.3.1 查找136
5.3.2 顺序查找138
5.3.3 二分查找140
5.3.4 静态次优查找树143
5.3.5 索引顺序查找146
5.4 哈希表147
5.4.1 哈希函数的构造148
5.4.2 闭哈希法151
5.4.3 开哈希法156
5.5 二叉查找树158
5.5.1 ADT二叉查找树158
5.5.2 二叉查找树的实现159
5.5.3 二叉查找树的应用164
5.6 平衡二叉查找树(或称AVL树)165
5.6.1 AVL树及其性质166
5.6.2 最小局部的不平衡类型及平衡方法167
5.6.3 AVL树的实现172
5.7 B-树与B+树176
5.7.1 B-树177
5.7.2 B+树183
5.8 键树185
5.8.1 双链树186
5.8.2 Trie树187
习题5188
第6章 图191
6.1 图的基本概念191
6.1.1 图的定义191
6.1.2 图的术语192
6.2 图的存储结构195
6.2.1 数组(邻接矩阵、相邻矩阵)表示法196
6.2.2 邻接表表示法197
6.2.3 邻接多重表表示法200
6.2.4 十字链表201
6.3 图的遍历202
6.3.1 深度优先遍历203
6.3.2 广度优先遍历204
6.4 无向图的应用206
6.4.1 最小(代价)生成树206
6.4.2 关节点和双连通图210
6.5 有向图的应用213
6.5.1 拓扑排序213
6.5.2 关键路径216
6.6 最短路径220
6.6.1 从一个顶点(源点)到其他顶点的最短路径221
6.6.2 每一对顶点间的最短路径(all-pairs shortest-paths)223
6.6.3 传递闭包225
习题6227
第7章 排序229
7.1 内部排序方式229
7.2 插入排序231
7.2.1 直接插入排序231
7.2.2 折半插入排序 232
7.2.3 希尔排序233
7.3 选择排序234
7.3.1 直接选择排序235
7.3.2 树形选择排序236
7.3.3 堆排序236
7.4 交换排序239
7.4.1 冒泡排序239
7.4.2 快速排序241
7.5 归并排序244
7.6 基数排序245
7.6.1 多排序码排序246
7.6.2 链式基数排序246
7.7 各种内部排序算法的比较249
7.7.1 各种排序方法的比较249
7.7.2 排序问题的下界250
习题7251
第8章 外部排序253
8.1 外部排序的方法253
8.1.1 外部排序的基本过程253
8.1.2 多路平衡归并255
8.1.3 置换-选择排序257
8.2 最佳归并树261
习题8263
第9章 动态存储管理264
9.1 概述264
9.2 可利用空间表266
9.2.1 可利用空间表结构266
9.2.2 分配267
9.2.3 回收268
9.3 伙伴系统268
9.3.1 指数伙伴系统的可利用空间表结构269
9.3.2 分配271
9.3.3 回收272
9.4 一个小型的动态存储管理系统273
9.4.1 系统内存结构273
9.4.2 内存分配275
9.4.3 内存释放与垃圾回收275
习题9276
第10章 算法分析与设计技术277
10.1 递归算法的分析277
10.2 递归式求解278
10.2.1 展开递归式278
10.2.2 猜解278
10.2.3 大递归式的一般解279
10.3 分而治之与递归281
10.4 动态规划法283
10.4.1 动态规划法的基本思想283
10.4.2 最优二叉查找树286
10.5 贪心法289
10.6 搜索法291
10.6.1 搜索法的基本思想291
10.6.2 启发式搜索293
10.7 NP完全性问题295
10.7.1 问题的描述形式296
10.7.2 P类问题与NP类问题297
10.7.3 NP-Complete类问题299
10.7.4 近似算法300
习题10302
参考文献303