江苏盐城网站建设,大型门户网站建设的意义,动画设计与制作教案,网站界面设计要素一、简单查找#xff08;顺序查找#xff09;
最基本的查找#xff0c;相当于遍历#xff0c;从头到尾一个一个找。 二、二分查找 1、简述 二分查找的输入是一个有序的元素列表。 如果要查找的元素包含在列表中#xff0c;二分查找返回其位置#xff1b; 否则返回null。…一、简单查找顺序查找
最基本的查找相当于遍历从头到尾一个一个找。 二、二分查找 1、简述 二分查找的输入是一个有序的元素列表。 如果要查找的元素包含在列表中二分查找返回其位置 否则返回null。
2、特点 对于包含n个元素的列表用二分查找最多需要log2n步而简单查找最多需要n步。 在 N 个键的有序数组中进行二分查找最多需要 lgN1次比较无论是否成功。 向大小为 N 的有序数组中插入一个新的元素在最坏情况下需要访问∼ 2N 次数组因此向一个空符号表中插入 N 个元素在最坏情况下需要访问∼ N2 次数组。
三、符号表字典 1、简述 符号表是一种存储键值对的数据结构支持两种操作 插入put即将一组新的键值 对存入表中 查找get即根据给定的键得到相应的值。
2、操作与结果 一般来说在符号表中查找一个键可能得到两种结果。 如果含有该键的结点存在于表中我们的查找就命中了然后返回相应的值。 否则查找未命中并返回 null
3、目的 符号表最主要的目的就是将一个键和一个值联系起来。 用户能够将一个键值对插入符号表并在之后能够从符号表的所有键值对中按照键直接找到相对应的值
4、规则 每个键只对应着一个值表中不允许存在重复的键 当用例代码向表中存入的键值对和表中已有的键及关联的值冲突时新的值会替代旧的值 键不能为空 不允许有空值 四、二叉树 二叉树的内容非常多先简单记录一些基本概念
1、二叉搜索树 二叉搜索树就是使用每个结点含有两个链接链表中每个结点只含有一个链接的二叉查找树来高效地实现符号表。 在二叉查找树中每个结点还包含了一个键和一个值键之间也有顺序之分以支持高效的查找。 二叉搜索树是一种能够将链表插入的灵活性和有序数组查找的高效性结合起来的符号表实现。
2、平衡搜索树 理想情况下我们希望能够保持二分查找树的平衡性这可以稳定提升查找的效率处于这个目的二叉树概念下衍生出了2-3树并进而衍生出了红黑树。
3、2-3树 我们将一棵标准的二叉查找树中的结点称为 2- 结点含有一个键和两条链接而现在我们引入 3- 结点它含有两个键和三条链接。 2- 结点和 3- 结点中的每条链接都对应着其中保存的键所分割产生的一个区间 一棵 2-3 查找树或为一棵空树或由以下结点组成 1 2- 结点含有一个键及其对应的值和两条链接左链接指向的 2-3 树中的键都小于该结点右链接指向的 2-3 树中的键都大于该结点。 2 3- 结点含有两个键及其对应的值和三条链接左链接指向的 2-3 树中的键都小于该结点中链接指向的 2-3 树中的键都位于该结点的两个键之间右链接指向的 2-3树中的键都大于该结点。
4、红黑树 红黑二叉查找树背后的基本思想是用标准的二叉查找树完全由 2- 结点构成和一些额外的信息替换- 结点来表示 2-3树。我们将树中的链接分为两种类型 红链接将两个 2- 结点连接起来构成一个 3- 结点 黑链接是 2-3 树中的普通链接。 可以理解为将 3- 结点表示为由一条左斜的红色链接两个 2-结点其中之一是另一个的左子结点相连的两个 2- 结点
5、二叉树的基本查找操作 在二叉查找树中查找一个键的递归算法 如果树是空的则查找未命中 如果被查找的键和根结点的键相等查找命中 否则我们就递归地在适当的子树中继续查找。 如果被查找的键较小就选择左子树较大则选择右子树
五、散列表hashtable 哈希表 1、概念 散列表可以认为是普通数组概念的推广 是实现字典操作的一种有效数据结构 也被称为散列映射、映射、字典和关联数组是一种包含额外逻辑的数据结构
2、散列函数 散列函数的计算过程会将键转化为数组的索引。 如果我们有一个能够保存M个键值对的数组那么我们就需要一个能够将任意键转化为该数组范围内的索引 [0,M-1] 范围内的整数 的散列函数。 散列函数和键的类型有关。 严格地说 对于每种类型的键都我们都需要一个与之对应的散列函数。 散列最主要的目的在于均匀地将键散布开来因此在计算散列后键的顺序信息就丢失了。 散列函数是构造散列表的关键一般来说散列函数应该有以下特点 1一致性 同样的输入返回的结果是一致的同样的不同的输入返回的结果一般也不同 2有效性 散列函数只返回有效结果
3、查找操作 使用散列的查找算法分为两步。 第一步是用散列函数将被查找的键转化为数组的一个索引。 理想情况下不同的键都能转化为不同的索引值。 非理想情况需要处理两个或者多个键都会散列到相同的索引值的情况。 散列查找的第二步就是处理这种碰撞冲突的过程。 有两种常用的解决碰撞的方法 拉链法和线性探测法。 4、拉链法 将大小为 M 的数组中的每个元素指向一条链表链表中的每个结点都存储了散列值为该元素的索引的键值对。 因为发生冲突的元素都被存储在链表中这种方法被称为拉链法。
5、线性探测法 实现散列表的另一种方式就是用大小为 M 的数组保存 N 个键值对其中 MN。依靠数组中的空位解决碰撞冲突。 这种统称为开放地址散列表。 开放地址散列表中最简单的方法叫做线性探测法 当碰撞发生时一个键的散列值已经被另一个不同的键占用我们直接检查散列表中的下一个位置将索引值加 1。 这样的线性探测可能会产生三种结果 1 命中该位置的键和被查找的键相同 2 未命中键为空该位置没有键 3 继续查找该位置的键和被查找的键不同。 我们用散列函数找到键在数组中的索引检查其中的键和被查找的键是否相同。 如果不同则继续查找将索引增大到达数组结尾时折回数组的开头直到找到该键或者遇到一个空元素。
