第1章数据结构概论11.1数据结构的概念11.1.1数据结构举例11.1.2数据与数据结构21.1.3数据结构的分类31.1.4数据结构课程的内容41.2数据结构的抽象形式61.2.1数据类型61.2.2数据抽象与抽象数据类型71.3作为ADT的C++类91.3.1面向对象的概念91.3.2C++中的类101.3.3C++中的对象121.3.4C++的输入输出131.3.5C++中的函数141.3.6动态存储分配171.3.7C++中的继承181.3.8多态性191.3.9C++的模板231.4算法定义241.5算法性能分析与度量261.5.1算法的性能标准261.5.2算法的后期测试261.5.3算法的事前估计271.5.4算法的渐进分析321.5.5最坏、最好和平均情况36习题37第2章线性表432.1线性表432.1.1线性表的概念432.1.2线性表的类定义442.2顺序表452.2.1顺序表的定义和特点452.2.2顺序表的类定义及其操作452.2.3顺序表的性能分析502.2.4顺序表的应用522.3单链表522.3.1单链表的概念532.3.2单链表的类定义542.3.3单链表中的插入与删除562.3.4带附加头结点的单链表592.3.5单链表的模板类602.4线性链表的其他变形662.4.1循环链表662.4.2双向链表692.5单链表的应用：多项式及其运算732.5.1多项式的表示742.5.2多项式的类定义752.5.3多项式的加法772.5.4多项式的乘法792.6静态链表80习题83第3章栈和队列883.1栈883.1.1栈的定义883.1.2顺序栈893.1.3链式栈923.1.4栈的应用之一——括号匹配943.1.5栈的应用之二——表达式的计算953.2栈与递归1013.2.1递归的概念1013.2.2递归过程与递归工作栈1053.2.3用回溯法求解迷宫问题1093.3队列1143.3.1队列的概念1143.3.2循环队列1143.3.3链式队列1183.3.4队列应用举例：打印二项展开式(a+b)i的系数1203.3.5队列应用举例：电路布线1213.4优先级队列1243.4.1优先级队列的概念1243.4.2优先级队列的存储表示和实现1253.5双端队列1263.5.1双端队列的概念1263.5.2双端队列的数组表示1283.5.3双端队列的链表表示129习题131第4章数组、串与广义表1354.1多维数组的概念与存储1354.1.1多维数组的概念1354.1.2多维数组的存储表示1364.2特殊矩阵1384.2.1对称矩阵的压缩存储1384.2.2三对角线/多对角线矩阵的压缩存储1404.3稀疏矩阵1414.3.1稀疏矩阵及其三元组数组表示1414.3.2稀疏矩阵的转置1454.3.3稀疏矩阵的相加和相乘1474.3.4矩阵的正交链表表示1524.4字符串1534.4.1字符串的概念1534.4.2C++有关字符串的库函数1544.4.3字符串的实现1564.4.4字符串的自定义类1584.4.5字符串操作的实现1594.4.6字符串的模式匹配1614.4.7字符串的存储方法1674.5广义表1694.5.1广义表的定义与性质1694.5.2广义表的表示1704.5.3广义表存储结构的实现1704.5.4广义表的递归算法1744.5.5三元多项式的表示181习题183第5章树1865.1树的基本概念1865.1.1树的定义和术语1865.1.2树的抽象数据类型1885.2二叉树1895.2.1二叉树的定义1895.2.2二叉树的性质1905.2.3二叉树的抽象数据类型1915.3二叉树的存储表示1925.3.1二叉树的数组存储表示1925.3.2二叉树的链表存储表示1935.4二叉树遍历及其应用1985.4.1二叉树遍历的递归算法1985.4.2二叉树遍历的应用2005.4.3二叉树遍历的非递归算法2035.4.4二叉树的计数2075.5线索二叉树2105.5.1线索2105.5.2中序线索二叉树的建立和遍历2115.5.3中序线索二叉树的插入与删除2165.5.4前序与后序的线索化二叉树2185.6树与森林2205.6.1树的存储表示2205.6.2森林与二叉树的转换2255.6.3树与二叉树的转换2275.7树与森林的遍历及其应用2275.7.1树与森林的深度优先遍历2275.7.2树和森林的广度优先遍历2305.7.3树遍历算法的应用2315.7.4其他基于遍历序列的几种存储表示2325.8堆2355.8.1最小堆和最大堆2355.8.2堆的建立2365.8.3堆的插入与删除2385.9Huffman树及其应用2405.9.1路径长度2405.9.2Huffman树2415.9.3Huffman树的应用：最优判定树2435.9.4Huffman树的应用：Huffman编码244习题246第6章集合与字典2516.1集合及其表示2516.1.1集合的基本概念2516.1.2用位向量实现集合抽象数据类型2526.1.3用有序链表实现集合的抽象数据类型2576.2并查集与等价类2626.2.1并查集的定义及其实现2626.2.2并查集的应用：等价类划分2676.3字典2686.3.1字典的概念2696.3.2字典的线性表描述2706.4跳表2736.4.1跳表的概念2736.4.2跳表的类定义2746.4.3跳表的搜索、插入和删除2766.5散列2796.5.1散列表与散列方法2796.5.2散列函数2806.5.3处理冲突的闭散列方法2826.5.4处理冲突的开散列方法2916.5.5散列表分析293习题294第7章搜索结构2977.1静态搜索结构2987.1.1静态搜索表2987.1.2顺序搜索3007.1.3基于有序顺序表的顺序搜索和折半搜索3027.1.4基于有序顺序表的其他搜索方法3077.2二叉搜索树3087.2.1二叉搜索树的概念3097.2.2二叉搜索树上的搜索3107.2.3二叉搜索树的插入3117.2.4二叉搜索树的删除3137.2.5二叉搜索树的性能分析3147.2.6最优二叉搜索树3177.3AVL树3207.3.1AVL树的概念3217.3.2平衡化旋转3217.3.3AVL树的插入3267.3.4AVL树的删除3297.3.5AVL树的性能分析3337.4伸展树3347.5红黑树3377.5.1红黑树的概念和性质3377.5.2红黑树的搜索3387.5.3红黑树的插入3387.5.4红黑树的删除339习题342第8章图3468.1图的基本概念3468.1.1与图有关的若干概念3468.1.2图的抽象数据类型3488.2图的存储结构3498.2.1图的邻接矩阵表示3508.2.2图的邻接表表示3558.2.3图的邻接多重表表示3618.3图的遍历3638.3.1深度优先搜索3648.3.2广度优先搜索3658.3.3连通分量3668.3.4重连通分量3688.4最小生成树3708.4.1Kruskal算法3718.4.2Prim算法3738.5最短路径3758.5.1非负权值的单源最短路径3768.5.2任意权值的单源最短路径3798.5.3所有顶点之间的最短路径3818.6用顶点表示活动的网络（AOV网络）3838.7用边表示活动的网络（AOE网络）388习题392第9章排序3979.1排序的概念及其算法性能分析3979.1.1排序的概念3979.1.2排序算法的性能评估3989.1.3排序表的类定义4009.2插入排序4019.2.1直接插入排序4019.2.2折半插入排序4039.2.3希尔排序4049.3快速排序4059.3.1快速排序的过程4069.3.2快速排序的性能分析4079.3.3快速排序的改进算法4099.3.4三路划分的快速排序算法4129.4选择排序4139.4.1直接选择排序4139.4.2锦标赛排序4149.4.3堆排序4199.5归并排序4229.5.1归并4229.5.2归并排序算法4239.6基于链表的排序算法4259.6.1链表插入排序4259.6.2链表归并排序4279.6.3链表排序结果的重排4289.7分配排序4319.7.1桶式排序4319.7.2基数排序4329.7.3MSD基数排序4339.7.4LSD基数排序4359.8内部排序算法的分析4379.8.1排序方法的下界4379.8.2各种内部排序方法的比较439习题440第10章文件、外部排序与搜索44410.1主存储器和外存储器44410.1.1磁带44410.1.2磁盘存储器44610.1.3缓冲区与缓冲池44810.2文件组织44910.2.1文件的概念44910.2.2文件的存储结构45010.3外排序45910.3.1外排序的基本过程45910.3.2k路平衡归并与败者树46110.3.3初始归并段的生成（run generation）46610.3.4并行操作的缓冲区处理47010.3.5最佳归并树47310.4多级索引结构47510.4.1静态的ISAM方法47510.4.2动态的m路搜索树47610.4.3B树47810.4.4B树的插入48010.4.5B树的删除48210.4.6B+树48610.4.7VSAM48910.5可扩充散列49010.5.1二叉Trie树49010.5.2将二叉Trie树转换为目录表49110.5.3目录表扩充与收缩49310.5.4性能分析49410.6Trie树49410.6.1Trie树的定义49410.6.2Trie树的搜索49510.6.3在Trie树上的插入和删除496习题497附录A程序索引500附录B词汇索引504参考文献512