精华内容
下载资源
问答
  • 数据结构:静态查找动态查找

    千次阅读 多人点赞 2019-03-15 15:32:10
    首先无论是静态查找还是动态查找,都要查找的对象,也就是包含很多同类型数据的“表”,这个“表”可以理解为一个由同类型数据元素组成的一个“集合”,该集合可以用各种容器来存储,例如数组、链表、树等,我们...

    概念

    1、静态查找

    首先无论是静态查找还是动态查找,都要有查找的对象,也就是包含很多同类型数据的“表”,这个“表”可以理解为一个由同类型数据元素组成的一个“集合”,该集合可以用各种容器来存储,例如数组、链表、树等,我们统称这些存储数据的数据结构为——查找表。可见,查找表有时是我们传统意义的表,有时候是很复杂的一种结构。

    静态查找就是我们平时概念中的查找,是“真正的查找”。之所以说静态查找是真正的查找,因为在静态查找过程中仅仅是执行“查找”的操作,即:(1)查看某特定的关键字是否在表中(判断性查找);(2)检索某特定关键字数据元素的各种属性(检索性查找)。这两种操作都只是获取已经存在的一个表中的数据信息,不对表的数据元素和结构进行任何改变,这就是所谓的静态查找。

    2、动态查找

    看到上面静态查找的概念,动态查找就很好理解了,个人总觉得动态查找不像是“查找”,更像是一个对表进行“创建、扩充、修改、删除”的过程。动态查找的过程中对表的操作会多两个动作:(1)首先也有一个“判断性查找”的过程,如果某特定的关键字在表中不存在,则按照一定的规则将其插入表中;(2)如果已经存在,则可以对其执行删除操作。动态查找的过程虽然只是多了“插入”和“删除”的操作,但是在对具体的表执行这两种操作时,往往并不是那么简单。

    哪种查找对应各自查找表,如有序表可以为静态查找表,也可以为动态查找表。依查找方式决定。

    一、静态查找表

    1.顺序查找

    假设每个记录的查找概率相等,顺序查找的平均查找长度:ASL=\sum_{i=1}^{n}P_{i}C^{i} = \frac{1}{n}\sum_{i=1}^{n}(n-i+1)=\frac{n+1}{2}

    假设查找成功与不成功的可能性相同,对每个记录查找概率也相等,则P_{i} = 1/(2n),此时平均查找长度为ASL=\frac{3}{4}(n+1)

    2.有序表查找

    折半查找:这个查找过程类似二叉树,具有n个节点的判定树深度为\left \lfloor log_{2}n \right \rfloor + 1,平均查找长度为ASL=\frac{1}{n}\sum _{j =1}^{h}j*2_{j-1} = \frac{n+1}{n}log_{2}(n+1)-1

    3.索引顺序表的查找(分块查找)

    对子表建立一个索引表,包括两项内容:关键字项(值为该子表内最大关键字)和指针项(指向该子表的第一个记录在表中的位置)。索引表按关键字有序,表或者有序,或者分块有序。

    由于索引项按关键字有序,则确定块的查找可以用顺序表查找,也可以用折半查找,块中记录是任意排列的,在块中只能是顺序查找。

    分块查找由这两种查找算法简单合成。分块查找的平均查找长度为

                                 ASL_{bs} = L_{b} + L_{w}

    其中:L_{b}为查找索引表确定所在块的平均查找长度,L_{w}为在块中查找元素的平均查找长度。

    一般情况下,为进行分块查找,可以将长度为n的表均匀的分成b块,每块含有s个记录;假定表中每个记录的查找概率相等。用顺序查找确定所在块,分块查找的平均查找长度为

                                ASL = \frac{b+1}{2}+\frac{s+1}{2}

    分块查找是折半查找和顺序查找的一种改进方法,折半查找虽然具有很好的性能,但其前提条件时线性表顺序存储而且按照关键码排序,这一前提条件在结点树很大且表元素动态变化时是难以满足的。而顺序查找可以解决表元素动态变化的要求,但查找效率很低。如果既要保持对线性表的查找具有较快的速度,又要能够满足表元素动态变化的要求,则可采用分块查找的方法。

    分块查找的速度虽然不如折半查找算法,但比顺序查找算法快得多,同时又不需要对全部节点进行排序。当节点很多且块数很大时,对索引表可以采用折半查找,这样能够进一步提高查找的速度。

    分块查找由于只要求索引表是有序的,对块内节点没有排序要求,因此特别适合于节点动态变化的情况。当增加或减少节以及节点的关键码改变时,只需将该节点调整到所在的块即可。在空间复杂性上,分块查找的主要代价是增加了一个辅助数组。

    平均查找长度:

    以一个牛客网上的题目为例:设顺序线性表的长度为30,分成5块,每块6个元素,如果采用分块查找并且索引表和块内均采用顺序查找,则其平均查找长度为(     )。

    分块查找会分两部分进行,第一步先进行索引表查找判断其在那个字表中,第二步然后进行在字表中的查找
    索引表有5个元素 所以平均查找长度为:(1+5)/2=3
    字表中有6个元素,所以平均查找长度为:(1+6)/2=3.5
    所以总的平均查找长度为3+3.5=6.5

    二、动态查找表

    2.1二叉排序树与AVL树

    2.1.1二叉排序树

    含有n个节点的二叉排序树的平均查找长度和树的形态有关,最好和log_{2}n成正比,当先后插入的关键字有序,构成的二叉排序树蜕变为单支树,树的深度为n,最坏情况,平均查找长度为\frac{n+1}{2}

    2.1.2平衡二叉树(AVL树)

    它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左右子树的深度之差绝对值不超过1。结点平衡因子定义为左子树深度减右子树深度(-1,0,1)。平均查找时间复杂度O(logn)

    2.2B-树和B+树

    一棵m阶B-树,或为空树,或满足下列特性的m叉树:(是一种平衡的多路查找树)

    1. 树中每个节点至多有m棵子树;
    2. 若根节点不是叶子结点,则至少有两棵子树;
    3. 除根之外的所有非终端结点至少有\left \lceil m/2 \right \rceil
    4. 所有非终端结点中包含下列信息数据(n,A_{0},K_{1},...,K_{n},A_{n}),其中K_{i}(i=1...n)为关键字,A_{i}(i = 0...n)为指向子树根结点的指针,且指针A_{i-1}所指子树中所有结点的关键字均小于K_{i}
    5. 所有的叶子结点都出现在同一层次上,且不带信息。

    m阶B+树和m阶B-树的差异在于:

    1. 有n棵子树的结点中含有n个关键字。
    2. 所有叶子结点中包含了全部关键字信息,及指向这些关键字记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
    3. 所有非终端结点可以看成是索引部分,结点中仅含有其子树(根结点)中最大(或最小) 关键字。

    参考文献:

    数据结构(C语言版),严蔚敏 

    https://blog.csdn.net/pamchen/article/details/8476134

    展开全文
  • 我将主要讲解介绍 查找的相关知识,如查找算法等,希望你们会喜欢。

    前言

    • 查找是 数据结构中的重要操作
    • 今天,我将主要讲解介绍 查找的相关知识,如查找算法等,希望你们会喜欢。

    目录

    示意图


    1. 简介

    • 本节将介绍关于 查找 的相关基础概念
    • 具体请看下图:

    示意图


    2. 查找 需求场景

    • 对于不同的查找需求场景,会采用不同的查找类型,最终采用的查找方式(查找算法)也有所不同

    • 具体如下

    示意图

    • 下面,将根据不同的查找需求类型,讲解对应的查找算法

    3. 静态查找

    • 定义:仅作 查找操作
    • 面向的数据结构:静态查找表
    • 算法:顺序查找、有序查找、线性索引查找
    • 具体介绍如下

    3.1 顺序查找

    • 具体介绍如下

    示意图

    3.2 有序查找

    1. 主要算法有:二分查找、插值 & 斐波那契
    2. 本文 主要介绍 = 二分查找(也称:折半查找)
    • 定义

    示意图

    • 具体实现
    public class BinarySearch {
    
        /**
         * 二分查找方法
         *  @param srcArray:有序数组
         * @param des:需要查找的元素
         */
        public static int binarySearch(int[] srcArray, int des){
    
            int low = 0; // 比较区间第1位
            int high = srcArray.length-1; // 比较区间最后1位
            int middle ; // 区间的中间位置
            
            
            while(low <= high) {
    
                // 1. 通过折半,求出区间的中间位置
                middle = low +  (high - low)>>1;
                 // 此处需特别注意以下:
               // a. mid = (low + high) / 2:当low、high都是比较大的数时,可能造成上溢除
               // b. 采用右移的位运算代替除2,提高效率
    
                // 2. 比较给定值和中间值
                    // 2.1 若给定值 = 中间记录,则查找成功,返回该位置
                if(des == srcArray[middle]) {
                    return middle;
    
                    // 2.2 若给定值 < 中间记录,则 在中间记录的左半区 继续查找
                    // 即 将比较区间的最后1位 设置为 原中间位置的前1位
                }else if(des <srcArray[middle]) {
                    high = middle - 1;
    
                    // 2.3 若给定值 > 中间记录,则 在中间记录的右半区 继续查找
                    // 即 将比较区间的首位 设置为原中间位置的后1位
                }else {
                    low = middle + 1;
                }
            }
            // 若比较区间的第1位 ≥ 最后1位,则表示查找失败,返回-1
            return -1;
        }
    
    
        /**
         * 执行 二分查找方法
         */
        public static void main(String[] args) {
    
            // 定义1个有序表数组
            int[] src = new int[]{1, 4, 5, 7, 8, 13,20,28};
            // 输出结果
            System.out.println("需要查找数据的数组下标 = " + binarySearch(src,8));
    
        }
        
    }
    
    • 测试结果
    需要查找数据的数组下标 = 4
    
    • 二分查找的变式

    对于二分查找存在一定的优 & 缺点,所以衍生出2种二分查找的变式方法:插值查找 & 斐波那契查找。具体如下:

    区别主要在于:比较元素(中间元素)的计算

    对比

    3.3 线性索引查找

    • 面向的数据结构:索引表

    关于 索引 的介绍如下

    示意图

    • 本文主要介绍的线性索引查找算法 = 稠密索引、分块索引、倒排索引。具体介绍如下:

    示意图


    4. 动态查找

    • 定义:作 查找、插入 & 删除操作
    • 面向的数据结构:动态查找表
    • 算法:二叉排序树、平衡二叉排序树(AVL树)&多路查找树
    • 具体介绍如下

    4.1 二叉排序树

    也称:二叉查找树、二叉搜索树

    • 特点
      示意图

    • 作用 & 应用场景

    示意图

    4.2 平衡二叉排序树(AVL树)

    属于 二叉搜索树的一种特殊类型

    • 特点

    示意图

    • 具体介绍

    示意图

    4.3 多路查找树

    • 具体介绍如下
      示意图

    • 多路查找树的类型介绍 & 对比
      http://blog.csdn.net/wtyvhreal/article/details/46442091

    示意图


    5. 散列查找

    • 定义:通过关键字获取记录
    • 面向的数据结构:散列表
    • 算法:散列技术
    • 具体介绍如下

    5.1 散列技术

    • 简介

    示意图

    5.2 散列函数的设计(构造方法)

    • 简介
      即,该如何构造出 散列函数
      示意图

    • 具体构造方法介绍 & 对比

    示意图

    5.3 散列冲突

    • 简介 & 解决方案

    示意图

    • 解决方案介绍

    示意图


    6. 总结

    • 本文主要讲解了数据结构中的查找相关知识
    • 下面我将继续对 数据结构,有兴趣可以继续关注Carson_Ho的安卓开发笔记

    请帮顶 / 评论点赞!因为你的鼓励是我写作的最大动力!

    展开全文
  • 动态查找之哈希(hash)表

    千次阅读 2016-09-08 15:37:31
    一、介绍 与其他建立在“比较”基础上的查找算法不同,哈希表是通过哈希函数将储存位置与值得关键字建立一一对应关系,从而一般一次就能够得到值。但是有时对于不同关键字哈希后得到的地址会是相同的,称这种现象为...

    一、介绍

      与其他建立在“比较”基础上的查找算法不同,哈希表是通过哈希函数将储存位置与值得关键字建立一一对应关系,从而一般一次就能够得到值。但是有时对于不同关键字哈希后得到的地址会是相同的,称这种现象为冲突。具有相同哈希值的关键字称为同义词。

    二、哈希函数

    哈希函数一般都是尽可能是的关键字随机性较大,出现相同概率小。
    直接定址法:根据关键词由哈希函数直接计算得地址
    这里写图片描述
    数字分析法:分析关键字规律,尽可能找关键字中不相同数字作为哈希地址
    平方取中法:关键字平方后取中间几位作为哈希地址
    折叠法:将关键字分割成相同几部分,然后取这几部分的叠加和作为哈希地址
    除留余数法:取关键字不大于哈希表长度的m的数p除后所得余数作为哈希地址
    这里写图片描述
    随机数法:取关键字的随机函数值作为哈希地址

    三、处理冲突

    哈希函数的冲突问题是不能避免的,因此当有冲突时需要一种解决办法。
    开放地址法:
    顾名思义,将其他地址开放给哈希函数存储
    这里写图片描述
    这里写图片描述

    再哈希法:
    这里写图片描述

    链接地址法:
    将所有关键词为同义词的记录存储在同一个线性列表中
    这里写图片描述

    建立公共溢出区:
    同义词的记录,一旦发生冲突,填入溢出表

    四、查找长度

    装填因子:
    这里写图片描述
    查找长度:
    这里写图片描述

    展开全文
  • 数据结构动态查找

    2013-01-03 19:45:52
    数据结构ADT动态查找动态查找表的特点和抽象数据类型ADT DynamicSearchTable 存储结构定义、 算法设计
  • 静态查找表与动态查找

    千次阅读 2020-09-16 10:36:22
    简而言之,动态查找表的结构是可以随时修改或变化的,表结构本身在查找过程中动态生成,一般而言链式结构这个特征,比如二叉查找树、三棵树等。另外,基于顺序存储的Hash查找应该也算动态查找表;而静态查找表的...

    静态查找表:仅做查询和检索操作的查找表

    动态查找表:在查询之后,还需要将查询结果不在查找表中的数据元素插入到查找表中;或者,从查找表中删除其查询结果为在查找表中的数据元素;

    简而言之,动态查找表的结构是可以随时修改或变化的,表结构本身在查找过程中动态生成,一般而言链式结构有这个特征,比如二叉查找树、三棵树等。另外,基于顺序存储的Hash查找应该也算动态查找表;而静态查找表的结构一次性生成后就不再允许改变,就像在有序数组上使用折半查找那样。

    展开全文
  • 静态查找和动态查找

    千次阅读 2016-10-17 10:26:22
    参考:http://blog.csdn.net/pamchen/article/details/8476134首先无论是静态查找还是动态查找,都要查找的对象,也就是包含很多同类型数据的“表”,这个“表”可以理解为一个由同类型数据元素组成的一个“集合”...
  • 二:动态查找表(Dynamic Search Table) 主要操作: 三:顺序查找(Sequential Search)【线性查找】 1.查找过程 2.时间复杂度 四:折半查找(Binary Search)【二分查找】【有序表查找】 1.查找过程 2.时间...
  • 【数据结构——树表的查找(动态查找表)】

    千次阅读 多人点赞 2020-11-28 20:43:36
    【数据结构——树表的查找(动态查找表)】 目录【数据结构——树表的查找(动态查找表)】动态查找表(基于树的查找法)(一)二叉排序树1、定义2、查找算法3、插入算法4、创建算法5、删除算法(二)平衡二叉树1、...
  • 数据结构 - 动态查找

    千次阅读 2015-05-03 09:48:19
    动态查找当查找表以顺序存储结构存储且需要保持有序时,若对查找表进行插入、删除或排序操作,就必须移动大量的记录,当记录数很多时,这种移动的代价很大。 若查找表无序,则插入删除可无需移动大量记录,但于查找...
  • C语言动态查找表之二叉排序树

    千次阅读 2019-05-02 20:04:14
    1.静态查找表与动态查找表的比较 2.二叉排序树(Binary Sort Tree) 2.1二叉排序树的定义 2.2二叉排序树的查找算法 2.3二叉排序树的插入算法 2.4二叉排序树的构造算法 2.5二叉排序树的删除算法 3.源代码示例 ...
  • 查找--静态查找与动态查找

    千次阅读 2016-04-19 17:06:49
    静态查找: ...动态查找: 1.在查找表中插入一个元素; 2.从查找表中删去某个数据元素。 (需要借助于顺序表) //SeqList.h #ifndef _SEQLIST_H_ #define _SEQLIST_H_ typedef void SeqList; typedef void
  • c语言(树的动态查找)

    2010-02-16 10:48:10
    c语言树的动态查找c语言树的动态查找c语言树的动态查找c语言树的动态查找
  • 查找算法总结之二(动态查找表)

    千次阅读 2015-06-25 14:54:42
    查找树查找算法总结(二),动态查找
  • 静态查找与动态查找结构

    千次阅读 2015-07-30 11:34:04
    在计算机许多应用领域中,查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能。比如说: (1) 全文检索技术中对文本建立索引之后,对索引的...在《查找算法》系列文章中,我将主要介绍动态查找
  • 文章目录动态顺序表及折半查找的实现动态顺序表一、动态顺序表定义二、动态顺序表初始化三、动态顺序表相关操作1.增加动态数组长度2.动态顺序表顺序插入元素3.动态顺序表删除4.动态顺序表按位查找5.动态顺序表按值...
  • 动态查找表(二叉排序树)

    千次阅读 2018-01-08 19:21:40
    动态查找表的特点是:表结构在查找过程中动态生成的,即对于给定值key,若表中存在等于key的记录,则查找成功,否则插入关键字key的记录。 1、二叉排序树 (1)、可以是空树 (2)、满足下列条件:若左子树不空,则...
  • 引言:  动态查找表的特点是在表结构
  • 1.动态查找表 特点:表结构在查找过程中动态生成。 要求:对于给定值 key, 若表中存在其关键字等于 key的记录,则查找成功返回,并且对查找成功的关键字可做删除操作;查找失败则可以做插入关键字等于 key的记录的....
  • 数据结构Data Structures张 凯计算机学院 软件工程系2011年3月12日第9...key 的记录则查找成功返回否则插入关键字等于 key 的记录 9.2 动态查找动态查找动态查找表主要二叉树结构和树结构两种类型二叉树结构
  • 最优二叉查找树—动态规划C++

    千次阅读 2020-12-26 00:35:34
    最优二叉查找树欢迎使用Markdown编辑器新的改变功能快捷键合理的创建标题,助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右...
  •  (1)查找算法 查找成功时,其比较次数为该结点所在的的层次数;查找不成功时,比较次数不超过树的高度。  二叉排序树的平均查找长度与树的形态有关, 当先后插入的关键字有序 时,构成的二叉树就蜕变成...
  • 七大查找算法

    万次阅读 多人点赞 2019-03-29 19:15:08
    1. 顺序查找 2. 二分查找 3. 插值查找 4. 斐波那契查找 ...查找是在大量的信息中寻找一个特定的信息元素,在计算机应用中,查找是常用的基本运算,例如编译程序中符号表的查找。本文简单概括性的介...
  • 详细介绍了常见的4种查找算法,比如顺序查找/线性查找、二分查找/折半查找、插值查找、斐波那契查找等,并且提供了相应的Java代码实现。
  • 动态查找

    千次阅读 2017-12-21 21:02:39
    将 1, 2, 3, 6, 5, 4 顺序一个个插入一棵初始为空的AVL树,会经历下列哪些旋转?  (2分) 两个“右-右”旋和一个“右-左”旋 一个“右-右”旋、一个“右-左”旋、一个“左-右”旋 一个“右-右”旋和两个“右-...
  • Linux动态库的查找路径

    千次阅读 2019-03-19 14:31:13
    这里写自定义目录标题动态库的搜索编译时链接ld-linux编译时搜索动态库路径运行时链接运行时动态库搜索顺序合理的创建标题,助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合...
  • 动态查找表与静态查找表

    千次阅读 2013-09-12 14:01:31
    动态查找表哈希表及其查找 以下分别对数据结构中的查找算法进行描述 一静态查找表 1.顺序表查找 顺序查找(Sequential Search)又称为线性查找,是一种最简单的查找方法。 查找过程如下: 从...
  • el-tree 节点动态查找

    千次阅读 2018-12-21 08:12:06
    1.效果图通过在input框里输入值,动态查询树节点。将父节点展开,找到的节点显示在最当前窗口。 2.代码 2.1 html <template> <div style="height: 100%; "> <div style="height: 45px;padding-top...
  • 面试-查找(静态查找,动态查找

    千次阅读 2011-10-11 10:30:39
    查找结构1】静态查找结构概论 http://hxraid.iteye.com/blog/608982 在计算机许多应用领域中,查找操作都是十分重要的研究技术。查找效率的好坏直接影响应用软件的性能。比如说: (1) 全文检索技术中对...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 653,431
精华内容 261,372
关键字:

动态查找有哪些