目录 第1章数据结构概论1 1.1数据结构的概念1 1.1.1数据结构举例1 1.1.2数据与数据结构2 1.1.3数据结构的分类3 1.1.4“数据结构”课程的内容4 1.2数据结构的抽象形式6 1.2.1数据类型6 1.2.2数据抽象与抽象数据类型7 1.3作为ADT的C++类9 1.3.1面向对象的概念9 1.3.2C++中的类10 1.3.3C++中的对象12 1.3.4C++的输入输出13 1.3.5C++中的函数14 1.3.6动态存储分配17 1.3.7C++中的继承18 1.3.8多态性19 1.3.9C++的模板23 1.4算法定义24 1.5算法性能分析与度量25 1.5.1算法的性能标准26 1.5.2算法复杂性度量26 1.5.3算法的渐进分析31 1.5.4最坏、最好和平均情况35 习题36 第2章线性表40 2.1线性表的概念40 2.1.1线性表的定义40 2.1.2线性表的类定义41 2.2顺序表42 2.2.1顺序表的定义和特点42 2.2.2顺序表的类定义及其操作42 2.2.3顺序表的性能分析47 2.2.4顺序表的应用49 2.3单链表49 2.3.1单链表的概念50 2.3.2单链表的类定义51 2.3.3单链表中的插入与删除52 2.3.4带附加头结点的单链表54 2.3.5单链表的模板类56 2.4线性链表的其他变形62 2.4.1循环单链表62 2.4.2双向链表65 2.5单链表的应用： 多项式及其运算69 2.5.1多项式的表示69 2.5.2多项式的类定义71 2.5.3多项式的加法73 2.6静态链表74 习题75 第3章栈和队列81 3.1栈81 3.1.1栈的定义81 3.1.2顺序栈82 3.1.3链式栈85 3.1.4栈的应用之一——括号匹配87 3.1.5栈的应用之二——表达式的计算88 3.2栈与递归93 3.2.1递归的概念93 3.2.2递归过程与递归工作栈97 3.2.3用回溯法求解迷宫问题102 3.3队列105 3.3.1队列的概念105 3.3.2循环队列106 3.3.3链式队列109 3.3.4队列应用举例： 打印二项展开式 (a+b)i的系数111 3.4优先级队列113 3.4.1优先级队列的概念113 3.4.2优先级队列的存储表示和实现114 3.5双端队列115 3.5.1双端队列的概念116 3.5.2双端队列的数组表示117 习题119 第4章数组、串与广义表125 4.1多维数组的概念与存储125 4.1.1多维数组的概念125 4.1.2多维数组的存储表示126 4.2特殊矩阵128 4.2.1对称矩阵的压缩存储128 4.2.2三对角/多对角矩阵的压缩存储130 4.3稀疏矩阵131 4.3.1稀疏矩阵及其三元组数组表示131 4.3.2稀疏矩阵的转置134 4.3.3稀疏矩阵的相加137 4.3.4矩阵的十字链表表示139 4.4字符串140 4.4.1字符串的概念140 4.4.2C++有关字符串的库函数141 4.4.3字符串的实现143 4.4.4字符串的自定义类145 4.4.5字符串操作的实现146 4.4.6字符串的模式匹配148 4.4.7字符串的存储方法154 4.5广义表156 4.5.1广义表的定义与性质156 4.5.2广义表的表示157 4.5.3广义表存储结构的实现158 4.5.4广义表的递归算法161 习题168 第5章树174 5.1树的基本概念174 5.1.1树的定义和术语174 5.1.2树的抽象数据类型176 5.2二叉树177 5.2.1二叉树的定义177 5.2.2二叉树的性质178 5.2.3二叉树的抽象数据类型179 5.3二叉树的存储表示180 5.3.1二叉树的数组存储表示180 5.3.2二叉树的链接存储表示181 5.4二叉树遍历及其应用186 5.4.1二叉树遍历的递归算法186 5.4.2二叉树遍历的应用188 5.4.3二叉树遍历的非递归算法190 5.4.4二叉树的计数194 5.5线索二叉树197 5.5.1线索198 5.5.2中序线索二叉树的建立和遍历198 5.5.3前序与后序的线索化二叉树204 5.6树与森林205 5.6.1树的存储表示205 5.6.2树、森林与二叉树的转换211 5.7树与森林的遍历及其应用212 5.7.1树与森林的深度优先遍历213 5.7.2树和森林的广度优先遍历215 5.7.3树遍历算法的应用216 5.8堆217 5.8.1最小堆和最大堆217 5.8.2堆的建立219 5.8.3堆的插入与删除220 5.9Huffman树及其应用222 5.9.1路径长度222 5.9.2Huffman树223 5.9.3Huffman树的应用： 最优判定树226 5.9.4Huffman树的应用： Huffman编码227 习题229 第6章集合与字典237 6.1集合及其表示237 6.1.1集合的基本概念237 6.1.2用位向量实现集合抽象数据类型238 6.1.3用有序链表实现集合的抽象数据类型243 6.2并查集与等价类248 6.2.1并查集的定义及其实现248 6.2.2并查集的应用： 等价类划分252 6.3字典254 6.3.1字典的概念254 6.3.2字典的线性表描述256 6.4跳表258 6.4.1跳表的概念258 6.4.2跳表的搜索、插入和删除259 6.5散列260 6.5.1散列表与散列方法261 6.5.2散列函数261 6.5.3处理冲突的闭散列方法263 6.5.4处理冲突的开散列方法272 6.5.5散列表分析274 习题276 第7章搜索结构282 7.1静态搜索结构283 7.1.1静态搜索表283 7.1.2顺序搜索285 7.1.3基于有序顺序表的顺序搜索和折半搜索286 7.1.4基于有序顺序表的其他搜索方法291 7.2二叉搜索树293 7.2.1二叉搜索树的概念293 7.2.2二叉搜索树上的搜索295 7.2.3二叉搜索树的插入295 7.2.4二叉搜索树的删除297 7.2.5二叉搜索树的性能分析298 7.3AVL树301 7.3.1AVL树的概念301 7.3.2平衡化旋转302 7.3.3AVL树的插入306 7.3.4AVL树的删除309 7.3.5AVL树的性能分析314 7.4伸展树315 7.5红黑树318 7.5.1红黑树的概念和性质318 7.5.2红黑树的搜索319 7.5.3红黑树的插入319 7.5.4红黑树的删除320 习题323 第8章图330 8.1图的基本概念330 8.1.1与图有关的若干概念330 8.1.2图的抽象数据类型332 8.2图的存储结构333 8.2.1图的邻接矩阵表示334 8.2.2图的邻接表表示339 8.2.3图的邻接多重表表示345 8.3图的遍历347 8.3.1深度优先搜索348 8.3.2广度优先搜索349 8.3.3连通分量350 8.3.4重连通分量352 8.4最小生成树354 8.4.1Kruskal算法355 8.4.2Prim算法358 8.5最短路径360 8.5.1非负权值的单源最短路径360 8.5.2任意权值的单源最短路径363 8.5.3所有顶点之间的最短路径366 8.6用顶点表示活动的网络（AOV网络）368 8.7用边表示活动的网络（AOE网络）372 习题377 第9章排序384 9.1排序的概念及其算法性能分析384 9.1.1排序的概念384 9.1.2排序算法的性能评估385 9.1.3排序表的类定义387 9.2插入排序388 9.2.1直接插入排序388 9.2.2折半插入排序389 9.2.3希尔排序391 9.3快速排序392 9.3.1快速排序的过程392 9.3.2快速排序的性能分析394 9.3.3快速排序的改进算法395 9.3.4三路划分的快速排序算法398 9.4选择排序400 9.4.1直接选择排序400 9.4.2锦标赛排序401 9.4.3堆排序406 9.5归并排序409 9.5.1归并409 9.5.2归并排序算法410 9.6基于链表的排序算法411 9.6.1链表插入排序412 9.6.2链表归并排序414 9.6.3链表排序结果的重排415 9.7分配排序418 9.7.1桶式排序418 9.7.2基数排序419 9.7.3MSD基数排序420 9.7.4LSD基数排序422 9.8内部排序算法的分析424 9.8.1排序方法的下界424 9.8.2各种内部排序方法的比较426 习题427 第10章文件、外部排序与搜索435 10.1主存储器和外存储器435 10.1.1磁带435 10.1.2磁盘存储器437 10.1.3缓冲区与缓冲池439 10.2文件组织441 10.2.1文件的概念441 10.2.2文件的存储结构442 10.3外排序451 10.3.1外排序的基本过程451 10.3.2k路平衡归并与败者树453 10.3.3初始归并段的生成458 10.3.4并行操作的缓冲区处理462 10.3.5最佳归并树465 10.4多级索引结构467 10.4.1静态的ISAM方法467 10.4.2动态的m路搜索树468 10.4.3B树470 10.4.4B树的插入472 10.4.5B树的删除474 10.4.6B+树478 10.4.7VSAM481 10.5字典树482 10.5.1字典树的概念482 10.5.2双链树表示483 10.5.3Trie树484 习题486 附录A部分习题答案495 参考文献501