数据结构知识点.doc

-
. z.
数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号〔数值、字符等〕的集合。
数据元素〔数据成员〕是数据的根本单位。在不称为根(root)的结点，它只有直接后继，但没有直接前驱；根以外的其他结点划分为m (m³ 0) 个互不相交的有限集合T1, T2, …, Tm，每个集合又是一棵树，并且称之为根的子树。每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继
二叉树的定义:一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。
完全二叉树:─假设设二叉树的深度为k，则共有k 层。除第k 层外，其它各层 (1～k-1) 的结点数都到达最大个数，第k层从右向左连续缺假设干结点，这就是完全二叉树
二叉树的遍历就是按*种次序访问树中的结点，要求每个结点访问一次且仅访问一次。设访问根结点记作 V遍历根的左子树记作 L 遍历根的右子树记作 R。则可能的遍历次序有：前序VLR镜像VRL；中序LVR镜像RVL；后序LRV镜像RLV
前序遍历二叉树算法的框架是：假设二叉树为空，则空操作；否则访问根结点 (V)；前序遍历左子树 (L)；前序遍历右子树 (R)。遍历结果- + a * b - c d / e f
树的后根次序遍历:当树非空时依次后根遍历根的各棵子树访问根结点：树后根遍历 EFBCGDA；对应二叉树中序遍历 EFBCGDA；树的后根遍历结果与其对应二叉树。
表示的中序遍历结果一样：树的后根遍历可以借助对应二叉树的中序遍历算法实现
最小堆和最大堆：如果有一个关键码集合K={K0,K1，K2，K3，….,Kn-1}，把它的所有元素按完全二叉树的顺序存储方式存放在一个一维数组中。并满足Ki≤K2i+1且Ki≤K2i+2(或者Ki≥K2i+1且KiK2i+2 )i=0,1,….[〔n-2〕/2]，则称这个集合为最小堆或最大堆。
堆是最高效的一种数据构造，每次出队列的是优先权最高的元素。用堆实现其存储表示，能够高效运作。
堆的建立：有2种方式建立最小的堆，一种方式是通过第一个构造函数建立一个空堆，其大小通过动态存储分配得到，另一中建立最小堆的方式是通过第二个构造函数复制一个记录数组并对其加以调整形成一个堆。
路径：从树中一个结点到达另一个结点之间的分支构成该两结点之间的路径。
路径长度：是指路径上的分支条数，树的路径长度是从树的根结点到每一个结点的路径长度之和。由树的定义，从根结点到达书中每一结点有且仅有一条路径。
Huffman树：带权路径长度最小的二叉树应是权值大的外结点离根结点最近的扩大二叉树。 带路径长度最小的扩大二叉树不一定是完全二叉树。
集合是成员(元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。
字典是一些元素的集合，每个元素有一个称作关键码〔key〕的域，不同元素的关键码互不一样。
散列方法：理想的搜索方法是可以不经过比拟，一次直接从字典中得到要搜索的元素。如果在元素存储位置与其关键码之间建立一个确定的对应函数关系Hash()，使得每个关键码与构造中一个唯一的存储位置相对应：Address ＝ Hash(key