边城愚人

如果我不在边城,我一定是在前往边城的路上。

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  31 随笔 :: 0 文章 :: 96 评论 :: 0 Trackbacks

DS&Algorithms

     摘要: 哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+ Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
构造哈夫曼树的算法如下:
1)对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,..., Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。
2)在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
3)从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
4)重  阅读全文
posted @ 2007-06-21 08:23 kafka0102 阅读(12211) | 评论 (7)  编辑

     摘要: 设有主串s和子串t,子串t定位是指在主串s中找到一个与子串t相等的子串。通常把主串s称为目标串,把子串t称为模式串,因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串t。

传统的字符串模式匹配算法(也就是BF算法)就是对于主串和模式串双双自左向右,一个一个字符比较,如果不匹配,主串和模式串的位置指针都要回溯。这样的算法时间复杂度为O(n*m),其中n和m分别为串s和串t的长度。

KMP算法是由Knuth,Morris和Pratt等人共同提出的,所以成为Knuth-Morris-Pratt算法,简称KMP算法。KMP算法是字符串模式匹配中的经典算法。和BF算法相比,KMP算法的不同点是匹配过程中,主串的位置指针不会回溯,这样的结果使得算法时间复杂度只为O(n+m)。下面说说KMP算法的原理。  阅读全文
posted @ 2007-06-17 22:14 kafka0102 阅读(9651) | 评论 (6)  编辑

     摘要: 网上看到一道java算法题,题目如下: 用1,2,2,3,4,5,这六个数字,用java写一个main函数,打印出所有不同的排列,如:512234,412345等,要求:“4”不能排第3位,“1”与“5”不能相连。  阅读全文
posted @ 2007-03-13 09:06 kafka0102 阅读(4496) | 评论 (12)  编辑