数据结构教程

书籍目录

第1章绪论 1.1什么是数据结构 1.1.1数据结构的定义 1.1.2逻辑结构类型 1.1.3存储结构类型 1.1.4数据类型和数据结构 1.2算法及其描述 1.2.1什么是算法 1.2.2算法描述 1.3算法分析 1.3.1算法设计的目标 1.3.2算法效率分析 1.3.3算法存储空间分析 1.4数据结构+算法一程序 1.4.1程序和数据结构 1.4.2算法和程序 1.4.3算法和数据结构 1.4.4数据结构的发展 本章小结 练习题1 上机实验题1 第2章线性表 2.1线性表及其逻辑结构 2.1.1线性表的定义 2.1.2线性表的抽象数据类型描述 2.2线性表的顺序存储结构 2.2.1线性表的顺序存储结构——顺序表 2.2.2顺序表基本运算的实现 2.3线性表的链式存储结构 2.3.1线性表的链式存储结构——链表 2.3.2单链表 2.3.3双链表 2.3.4循环链表 2.4线性表的应用 2.5有序表 2.5.1有序表的抽象数据类型描述 2.5.2有序表的存储结构及其基本运算算法 2.5.3有序表的归并算法 2.5.4有序表的应用 本章小结 练习题2 上机实验题2 …… 第3章栈和队列 第4章串 第5章递归 第6章数组和广义表 第7章树和二叉树 第8章图 第9章查找 第10章内排序 第11章外排序 第12章文件 第13章采用面向对象的方法描述算法 附录A综合实验题 附录B实验报告格式 附录C引用型参数的说明 附录D顺序表、顺序栈和顺序队列使用指针引用型参数的说明 附录E书中部分算法清单 附录F全国计算机专业数据结构2012年联考大纲 参考文献

编辑推荐

《"十二五"普通高等教育本科国家级规划教材•高等学校数据结构课程系列教材:数据结构教程(第4版)》针对数据结构课程概念多、算法灵活和抽象性强等特点，在总结长期教学经验的基础上编写的。《"十二五"普通高等教育本科国家级规划教材•高等学校数据结构课程系列教材:数据结构教程(第4版)》适合高等院校计算机及相关专业本科生和研究生使用。

内容概要

李春葆，武汉大学计算机学院教授，主要研究方向为数据挖掘和算法设计，先后主持和参加多个大型研究项目。主要为本科生讲授数据结构（15年以上）和软件工程等课程，为研究生讲授软件开发新技术、数据仓库与数据挖掘等课程，并出版十多部精品著作。

章节摘录

版权页：   7.2.3二叉树与树、森林之间的转换 树、森林与二叉树之间有一个自然的对应关系，它们之间可以进行相互转换，即任何一个森林或一棵树都可以唯一地对应一棵二叉树，而任一棵二叉树也能唯一地对应一个森林或一棵树。正是由于有这样的一一对应关系，可以把在树中处理的问题对应到二叉树中进行处理，从而可以把问题简单化。下面介绍森林、树与二叉树相互转换的方法。 对于一般的树来说，树中节点的左右次序无关紧要，只要其双亲节点与孩子节点的关系不发生错误就可以了。但在二叉树中，左、右孩子节点的次序不能随意颠倒。因此，下面讨论的二叉树与一般树之间的转换都约定按照树在图形上的节点次序进行，即把一般树作为有序树来处理，这样不致于引起混乱。 上述方法是一种递归构造方法，如果假定T是有序树的序列，那么，由T所构造的二叉树β（T）是唯一的。 用上述递归方法构造的二叉树p（T）的节点与原来树T的节点的关系为：二叉树β（T）中的任意节点k，若有左孩子节点，则该左孩子节点为k原来的最左边（即第一棵）子树的根节点；若有右孩子节点，则该右孩子节点为k原来的右边相邻的第一个兄弟节点或右边第一棵相邻的树的根节点（当k为原森林中树的根节点时）。由此可以把递归构造二叉树β（T）的过程归纳如下： （1）在所有相邻兄弟节点（森林中每棵树的根节点可看成是兄弟节点）之间加一条水平连线。 （2）对每个非叶子节点k，除了其最左边的孩子节点外，删去k与其他孩子节点的连线。 （3）所有水平线段以左边节点为轴心顺时针旋转45°。 通过以上步骤，原来的森林就转换为一棵二叉树。一棵树是森林中的特殊情况，由一棵树转换的二叉树的根节点的右孩子节点始终为空，原因是一棵树的根节点不存在兄弟节点和相邻的树。 【例7.5】将如图7.6（a）所示的森林（由三棵树组成）转换成二叉树。 解：转换为二叉树的过程如图7.6（b）和（c）所示，最终结果如图7.6（d）所示。

---

 数据结构教程下载

---