归并排序      摘要: 归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法，该算法是采用分治法。
　　申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
　　设定两个指针，最初位置分别为两个已经排序序列的起始位置
　　比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
　　重复步骤3直到某一指针达到序列尾   阅读全文

B-树及B＋树      摘要: 1、B树的定义
B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：
（1）每个结点至多有m个子结点；
（2）除根结点和叶结点外，其它每个结点至少有个子结点；
（3）若根结点不是叶子结点，则至少有两个子结点；
（4）所有的叶结点在同一层；
（5）有k个子结点的非根结点恰好包含k-1个关键码。
  阅读全文

平衡二叉树 （AVL树）      摘要: 　在构造二叉排序树的过程中，每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结点之间的连接关系，以达到新的平衡。通常将这样得到的平衡二叉排序树简称为 AVL 树。
那么什么是 最小不平衡子树
　　以离插入结点最近、且平衡因子绝对值大于 1 的结点作根结点的子树。为了简化讨论，不妨假设二叉排序树的最小不平衡子树的根结点为 A ，则调整该子树的规律可归纳为下列四种情况：
  阅读全文

各种查找算法的实现

二叉搜索树（二叉排序树）（二叉查找树）      摘要: 1、二叉搜索树是二叉树的一种，树的每个结点含有一个数据项，每个数据项有一个键值。结点的存储位置是由键值的大小决定的，所以二叉搜索树是关联式容器。
(1)、 若它的左子树不空，则左子树上所有结点的键值均小于它的根结点的键值；
(2)、若它的右子树不空，则右子树上所有结点的键值均大于它的根结点的键值；
(3)、它的左、右子树也分别为二叉排序树。
注意：：：二叉排序树是一种动态树表，树的结构通常不是一次生成的。而是在查找的过程中，当树中不存在关键字等于给定值的节点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
  阅读全文

哈夫曼树      摘要: 哈夫曼树定义为：给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。
1、那么什么是权值？什么是路径长度？什么是带权路径长度呢？
权值：哈夫曼树的权值是自己定义的，他的物理意义表示数据出现的次数、频率。可以用树的每个结点数据域data存放一个特定的数表示它的值。

路径长度：在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 树中所有叶子节点的带权路径长度之和，WPL=sigma(w*l)

  阅读全文

优先队列      摘要: 优先队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。每个元素都有一个优先权或值
/////用堆实现优先队列
1、把优先队列中的元素按优先级大小组织成堆，堆顶元素具有最大优先级。
2、优先队列的插入与删除可以用堆的插入与删除实现。
3、优先队列在定义为priority_queue ，在STL中#include 中实现、
priority_queue, greater >qi2;
其中

  阅读全文

posted @ 2011-10-02 11:22 Yu_ 阅读(235) | 评论 (0)  编辑

堆排序      摘要: 估计还要问问：什么是堆，什么是堆排序？堆与计算机分配内存的堆相同吗？
很多资料给出：堆的定义是
（1）、n个关键字序列（Kl，K2，…，Kn）称为(Heap)，当且仅当该序列满足如下性质(简称为堆性质)：
ki≤K2i且ki≤K2i+1 或 Ki≥K2i且ki≥K2i+1 (1≤i≤ n) //ki相当于二叉树的非叶结点，K2i则是左孩子，k2i+1是右孩子

  阅读全文