分类:数据结构

简述洗牌算法

扑克牌一共有54张,洗牌是将扑克牌顺序打散。那么问题很简单,设计一个算法,实现洗牌的功能,利用自带的RAND函数 全局洗牌 初始化一个数组,大小为54,初始化值为1~54 按照索引1到54,逐步对每一张索引牌进行洗牌 首先生成一个随机数 value = rand %54,再将索...

yan 2016 年 2 月 6 日 490℃ 2评论 31喜欢

随机函数扩大,如rand5()构造rand7()

引例 利用random(0,1)产生0或1,从而组成二进制数,来完成random(a,b)的实现 解决办法:运行random(0,1)函数k次,使得2k>=(b-a+1),将得到[0,2k)的整数区间,如何将[0,2k)映射到[a,b]的整数区间,保证产生各整数的概率相等,...

yan 2015 年 7 月 20 日 1086℃ 3评论 2喜欢

二叉树实现广度遍历和递归与非递归的深度(前中后序)遍历

二叉树的遍历: (1)深度优先遍历:前序、中序、后序 (2)广度优先遍历 即,前中后序是深度优先遍历的一种而已,广度优先只有非递归方法。 二叉树的深度优先遍历的非递归的通用做法是采用栈,广度优先遍历的非递归的通用做法是采用队列。 一、广度优先遍历 初始化一个队列,并把根结点入列...

yan 2015 年 4 月 20 日 1832℃ 7评论 1喜欢

Java实现KMP算法

package arithmetic; /** * Java实现KMP算法 * * 思想:每当一趟匹配过程中出现字符比较不等,不需要回溯i指针, * 而是利用已经得到的“部分匹配”的结果将模式...

yan 2015 年 4 月 20 日 1655℃ 2评论 0喜欢

简述KMP算法思想(字符串匹配算法)

有一个字符串”BBC ABCDAB ABCDABCDABDE”,我想知道,里面是否包含另一个字符串”ABCDABD”? 许多算法可以完成这个任务,Knuth-Morris-Pratt算法(简称KMP)是最常用的之一。它以三个发明者命...

yan 2015 年 3 月 25 日 954℃ 1评论 2喜欢

二分查找的时间复杂度,最大查找次数

二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好;其缺点是要求待查表为有序表,且插入删除困难。因此,折半查找方法适用于不经常变动而查找频繁的有序列表。首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置...

yan 2015 年 3 月 23 日 1912℃ 1评论 0喜欢

树——多路数,B树、B-树、B+树、B*树

暂且只研究树的基本内容,大致按如下分类: 故本博只讨论:二叉查找树、二叉堆、AVL平衡树、多路数(见本文) 名词解释 B树:二叉查找树,每个结点只存储一个关键字,等于则命中,小于走左结点,大于走右结点; B-树:多路搜索树,每个结点存储M/2到M个关键字,非叶子结点存储指向关...

yan 2015 年 2 月 22 日 874℃ 0评论 0喜欢

二叉树——二叉查找树的增、删、查

定义 在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆(二叉堆是完全二元树(二叉树)或者是近似完全二元树(二叉树)。二叉堆有两种:最大堆和最...

yan 2015 年 2 月 21 日 928℃ 2评论 0喜欢