数据结构
出版信息
殷人昆 / 清华大学 / 2007-6 / 39.00元
内容简介
《数据结构》(第2版)“数据结构”是计算机专业的核心课程，是从事计算机软件开发和应用人员必备的专业基础。随着计算机的日益普及，“数据结构”课程也在不断地发展。《数据结构》(第2版)按照清华大学计算机系本科“数据结构”大纲的要求，从面向对象的概念、对象类设计的风格和数据结构的层次开始，从线性结构到非线性结构，从简单到复杂，深入地讨论了各种数据结构内在的逻辑关系及其在计算机中的实现方式和使用。此外，对常用的迭代、递归、回溯等算法设计技巧，搜索和排序算法等都做了详尽的描述，并引入了简单的算法分析。
目录
第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
