精华内容
下载资源
问答
  • 静态查找动态查找

    千次阅读 2016-10-17 10:26:22
    参考:http://blog.csdn.net/pamchen/article/details/8476134首先无论是静态查找还是动态查找,都要有查找的对象,也就是包含很多同类型数据的“表”,这个“表”可以理解为一个由同类型数据元素组成的一个“集合”...

    参考:http://blog.csdn.net/pamchen/article/details/8476134

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

    一、静态查找

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

    静态查找包括:

    1. 顺序查找
    2. 折半查找
    3. Fibonacci
    4. 分块查找
      详细可以参考:http://blog.csdn.net/wangzi11322/article/details/45456871

    二、动态查找

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

    动态查找包括:
    1. 二叉排序树
    2. 平衡二叉树
    详细参考:http://blog.csdn.net/wangzi11322/article/details/45456971

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

    千次阅读 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

    展开全文
  • 动态查找

    千次阅读 2017-12-11 19:07:50
    前面介绍过var,var关键字不是一个类型,所以并没有违反C#的“强类型化”方法论。...这包括与旧技术的交互燥作,例如Component Object Model(COM),以及处理动态语言,例如JavaScript、Python 和Ruby。

    前面介绍过var,var关键字不是一个类型,所以并没有违反C#的“强类型化”方法论。但在C# 4 引入了“动态变量”的概念,顾名思义,动态变量是类型不固定的变量。引入动态变量的主要目的是在许多情况下,都希望使用C#处理另一种语言创建的对象。这包括与旧技术的交互燥作,例如Component Object Model(COM),以及处理动态语言,例如JavaScript、Python 和Ruby。

    例如,假定代码从JavaScript 中获得了一个带Add()方法的对象,该方法把两个数字加在一起。如果没有动态查找功能,调用这个方法的代码就如下所示:

    ScriptObject jsObj = SomeMethodThatGetsTheObject();

    int sum = Convert.ToInt32(jsObj.Invoke("Add", 2, 3));

    ScriptObject 类型提供了一种访问JavaScript 对象的方式,但不能执行如下操作:

    int sum = jsObj.Add(2, 3);

    动态查找功能改变了这一切,它允许编写上述代码。

    另一个可一使用动态查找功能的情形是处理未知类型的C#对象。这听起来似乎很古怪,但这种情形出现的次数比我们想象得多。如果需要编写一些泛型代码,来处理它接收的输入,这也是一个重要的功能。处理这种情形的“旧”方法称为“反射(reflection)”,它涉及使用类型信息来访问类型和成员。实际上,反射的语法非常类似于上述代码中访问JavaScript 对象的语法,也非常麻烦。

    在后台,动态查找功能由Dynamic Language Runtime(动态语言运行库,DLR)支持。与CLR 一样,DLR 是.NET 4 的一部分。

    使用dynamic 关键字,以用于定义变量。例如:

    dynamic myDynamicVar;

    注:

    1)与前面介绍的var 关键字不同,的确存在dynamic 类型,所以在声明myDynamicVar 时,无需初始化它的值。

    2)dynamic 类型不同寻常之处是,它仅在编译期间存在,在运行期间它会被System.Object 类型替代。这是较细微的实现细节,但必须记住这一点。

    无论myDynamicVar 实际包含什么值,这行代码都会编译。但是,如果所请求的成员不存在,

    在执行这行代码时会生成一个RuntimeBinderException 类型的异常。

    我们还是来看一个栗子:

    using System;

    using System.Collections.Generic;

    using System.Linq;

    using System.Text;

    //为包含RuntimeBindingException 异常的名称空间添加一个using 语句

    using Microsoft.CSharp.RuntimeBinder;

    namespace Ch14Ex03

    {

    //接着定义两个类MyClass1 和MyClass2,其中MyClass1 包含Add()方法,而MyClass2 不含成员

    class MyClass1

    {

    public int Add(int var1, int var2)

    {

    return var1 + var2;

    }

    }

    class MyClass2

    {

    }

    class Program

    {

    static int callCount = 0;

    //注意dynamic 关键字可以用作方法的返回类型

    static dynamic GetValue()

    {

    if (callCount++ == 0)

    {

    return new MyClass1();

    }

    return new MyClass2();

    }

    static void Main(string[] args)

    {

    try

    {

    dynamic firstResult = GetValue();

    dynamic secondResult = GetValue();

    Console.WriteLine("firstResult is: {0}",

    firstResult.ToString());

    Console.WriteLine("secondResult is: {0}",

    secondResult.ToString());

    Console.WriteLine("firstResult call: {0}", firstResult.Add(2, 3));

    Console.WriteLine("secondResult call: {0}",

    secondResult.Add(2, 3));

    }

    //这些代码放在try ... catch 块中,以捕获可能发生的RuntimeBinderException 类型的异常。

    catch (RuntimeBinderException ex)

    {

    Console.WriteLine(ex.Message);

    }

    Console.ReadKey();

    }

    }

    }

    我想这个栗子很好理解,dynamic 关键字也可以用于其他需要类型名的地万,例如方法参数。Add()方法可以重写为:

    public int Add(dynamic var1, dynamic var2)

    {

    return var1 + var2;

    }

    传送给var1 和var2 的值在运行期间检查,可以确定加号+是否存在一个兼容的运算符定义。如果传送了两个int 值,就存在这样的运算符。如果使用了不兼容的值,就抛出RuntimeBinderException 异常。

    对于大多数自己编写的C#代码,应避免使用dynamic 关键字。但是,如果需要使用它,就应使用它,并会喜欢上它——而不像过去那些可怜的程序员那样没有这个强大的工具可用。

    展开全文
  • 查找算法总结之二(动态查找表)

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

    刚刚介绍完静态查找树查找算法总结(一),接下来谈谈一些常用的动态查找结构。其中包括最基本的二叉排序树(二叉查找树、二叉收索树)、二叉平衡树(AVL树)、红黑树、以及一些多路查找树(B+,B-树)

    二叉排序树

    特点:
    1、如果它的左子树不空,那么左子树上的所有结点值均小于它的根结点值;
    2、如果它的右子树不空,那么右子树上的所有结点值均大于它的根结点值;
    3、它的左右子树也分别为二叉查找树
    如下如所示二叉查找树:
    二叉查找树

    二叉查找树的插入和删除都非常的方便,很好的解决了折半查找添加删除所带来的问题。

    那么它的效率又如何呢?

    很显然,二叉查找树查找一个数据,不需要遍历全部的节点,查找效率确实提高了。但是,也有一个很严重的问题,我在a图中查找8需要比较5次,而在b图中查找8需要3次,更为严重的是,我的二叉查找树是c图,如果再查找8,那将会如何呢?很显然,整棵树就退化成了一个线性结构,此时再查找8,就和顺序查找没什么区别了。

    时间复杂度分析:最坏的情况下和顺序查找相同,是O(N),最好的情况下和折半查找相同,是O(logN)。进过研究发现,在随机的情况下,二叉排序树的平均查找长度和logn是等数量级的。然而,在某些情况下(有人研究表明,这种概率大约占46.5%)尚需在构成二叉排序树的过程中进行”平衡化”处理,成为二叉平衡树。

    这说明了一个问题,同样的一组数据集合,不同的添加顺序会导致二叉查找树的结构完全不一样,直接影响到了查找的效率。

    二叉排序树的一些基本操作,包括,添加节点,删除节点,获取做大的节点,获取最小的节点,得到任意孩子节点的父节点等。

    /**
         * 向二叉排序树中添加节点
         * @param root
         * @param value
         * @return 二叉排数树根节点
         */
        public static TreeNode insertTreeNode(TreeNode root,int value){
            if(root == null){
                root = new TreeNode(value);
            }else if(root.value>value){
                root.left = insertTreeNode(root.left,value);
            }else if(root.value<value){
                root.right =insertTreeNode(root.right,value);
            }
            return root;
        }
    /**
         * 在二叉排数树中查找,关键字为key的节点
         * @param root
         * @param key
         * @return 二叉排数树中关键字为key的节点
         */
        public static TreeNode serachTreeNode(TreeNode root,int key){
            if(root == null){
                return null;
            }
            if(key>root.value)
                return serachTreeNode(root.right,key);  
            else if(key<root.value)
                return serachTreeNode(root.left,key);  
            else  
                return root;  
        }
    //获取父节点
    public static TreeNode getParentTreeNode (TreeNode root,int key){
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            if(root==null || root.value==key){
                return null;
            }
            queue.add(root);
            while(!queue.isEmpty()){
                TreeNode current = queue.poll();
                if(current.left!=null){
                    if(current.left.value==key)
                        return current;
                    else
                        queue.add(current.left);
                }
                if(current.right!=null){
                    if(current.right.value==key)
                        return current;
                    else
                        queue.add(current.right);
                }
            }
            return null;
    //获得关键字最大的节点
        public static TreeNode getMaxTreeNode(TreeNode root){
            if(root == null || root.right==null)
                return root;
            if(root.right != null){
                root = getMaxTreeNode(root.right);
            }
            return root;
        }
        //获得关键字最小的节点
        public static TreeNode getMinTreeNode(TreeNode root){
            if(root == null || root.left==null)
                return root;
            if(root.left != null){
                root = getMinTreeNode(root.left);
            }
            return root;
        }
        //打印排序二叉树
        public static void printInOrder(TreeNode root){
            if(root!=null){
                printInOrder(root.left);
                System.out.print(root.value+" ");
                printInOrder(root.right);           
            }
        }

    最后关于二叉排序树的删除相对比较复杂,可以分下面三种情况讨论:

    (1)需要删除的节点下并没有其他子节点,其为叶子节点。
    
    (2)需要删除的节点下有一个子节点(左或右)。
    
    (3)需要删除的节点下有两个子节点(既左右节点都存在)。
    

    二叉排序树的删除

    • 针对第一种情况:删除叶子节点,例如删除4,只需判断4是它的父节点的左孩子,还是右孩子。如图中,4则为其父节点3的右孩子,所以直接将3的右孩子置为空。

    • 针对第二种情况:要删除的节点有一个孩子节点,若其为其父节点的右孩子,则让其父节点的右指针指向其孩子节点;若其为其父节点的左孩子,则让其父节点的左指针指向其孩子节点。

    • 针对第三种情况:要删除的节点既有左孩子又有右孩子,例如节点2,则我们先在需要删除的节点的右子树中,找到一个最小的值(因为右子树中的节点的值一定大于根节点)4。然后,用找到的最小的值与需要删除的节点的值替换。然后,再将最小值的原节点进行删除.

    public static void deleteTreeNode(TreeNode root,TreeNode pNode){
            TreeNode parent = getParentTreeNode(root,pNode.value);
            //该节点是叶子节点
            if(pNode.left==null && pNode.right==null){
                //该节点是父节点的左孩子
                if(parent.left==pNode)
                    parent.left=null;
                else
                    parent.right=null;
            //该节点只有右孩子
            }else if(pNode.left==null&&pNode.right!=null){
                //该节点为其父节点的左孩子
                if(pNode == parent.left ){
                    parent.left = pNode.right;
                }else{
                    parent.right = pNode.right;
                }
            //该节点只有右孩子
            }else if(pNode.left!=null&&pNode.right==null){
                if(pNode ==parent.left ){
                    parent.left = pNode.left;
                }else{
                    parent.right = pNode.left;
                }
            //该节点左右孩子都存在
            }else if(pNode.left!=null&&pNode.right!=null){
                /*
                 * 我们先在需要删除的节点的右子树中,找到一个最小的值(因为右子树中的节点的值一定大于根节点)。
                 * 然后,用找到的最小的值与需要删除的节点的值替换。然后,再将最小值的原节点进行删除
                 * */           
                TreeNode minNode=getMinTreeNode(pNode.right);
                deleteTreeNode(root,minNode);
                TreeNode pNpdeparent = getParentTreeNode(root,pNode.value);
                if(pNpdeparent.left==pNode){
                    pNpdeparent.left=minNode;
                    minNode.left = pNode.left;
                    minNode.right = pNode.right;
                }               
                else{
                    pNpdeparent.right=minNode;
                    minNode.left = pNode.left;
                    minNode.right = pNode.right;
                }               
            }
        }   

    最后附上有关二叉排序树的基本操作的代码:(可直接运行)

    输入:两行,第一行为二叉树节点的个数,第二行为各个节点的值(不重复)
    10
    89 67 34 30 40 50 44 55 66 77
    输出:逐步按输入删除节点(除根节点)后二叉排序树的中序遍历(有序)
    30 34 40 44 50 55 66 67 77 89
    30 34 40 44 50 55 66 77 89
    30 40 44 50 55 66 77 89
    40 44 50 55 66 77 89
    44 50 55 66 77 89
    44 55 66 77 89
    55 66 77 89
    66 77 89
    77 89
    89

    import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.io.StreamTokenizer;
    import java.util.LinkedList;
    import java.util.Queue;
    
    class TreeNode {
        public int value;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(int value){
            this.value = value;
            this.left = this.right = null;
        }
    }
    public class BinarySearchTree {
        /**
         * 向二叉排序树中添加节点
         * @param root
         * @param value
         * @return 二叉排数树根节点
         */
        public static TreeNode insertTreeNode(TreeNode root,int value){
            if(root == null){
                root = new TreeNode(value);
            }else if(root.value>value){
                root.left = insertTreeNode(root.left,value);
            }else if(root.value<value){
                root.right =insertTreeNode(root.right,value);
            }
            return root;
        }
        /**
         * 在二叉排数树中查找,关键字为key的节点
         * @param root
         * @param key
         * @return 二叉排数树中关键字为key的节点
         */
        public static TreeNode serachTreeNode(TreeNode root,int key){
            if(root == null){
                return null;
            }
            if(key>root.value)
                return serachTreeNode(root.right,key);  
            else if(key<root.value)
                return serachTreeNode(root.left,key);  
            else  
                return root;  
        }
        public static void deleteTreeNode(TreeNode root,TreeNode pNode){
            TreeNode parent = getParentTreeNode(root,pNode.value);
            //该节点是叶子节点
            if(pNode.left==null && pNode.right==null){
                //该节点是父节点的左孩子
                if(parent.left==pNode)
                    parent.left=null;
                else
                    parent.right=null;
            //该节点只有右孩子
            }else if(pNode.left==null&&pNode.right!=null){
                //该节点为其父节点的左孩子
                if(pNode == parent.left ){
                    parent.left = pNode.right;
                }else{
                    parent.right = pNode.right;
                }
            //该节点只有右孩子
            }else if(pNode.left!=null&&pNode.right==null){
                if(pNode ==parent.left ){
                    parent.left = pNode.left;
                }else{
                    parent.right = pNode.left;
                }
            //该节点左右孩子都存在
            }else if(pNode.left!=null&&pNode.right!=null){
                /*
                 * 我们先在需要删除的节点的右子树中,找到一个最小的值(因为右子树中的节点的值一定大于根节点)。
                 * 然后,用找到的最小的值与需要删除的节点的值替换。然后,再将最小值的原节点进行删除
                 * */           
                TreeNode minNode=getMinTreeNode(pNode.right);
                deleteTreeNode(root,minNode);
                TreeNode pNpdeparent = getParentTreeNode(root,pNode.value);
                if(pNpdeparent.left==pNode){
                    pNpdeparent.left=minNode;
                    minNode.left = pNode.left;
                    minNode.right = pNode.right;
                }               
                else{
                    pNpdeparent.right=minNode;
                    minNode.left = pNode.left;
                    minNode.right = pNode.right;
                }               
            }
        }   
        //获取父节点
        /*
          public static TreeNode getParentTreeNode(TreeNode root,int key){
                if(root!=null){
                    if(root.left!=null && root.right!=null){
                        if(root.left.value == key || root.right.value ==key){
                            return root;
                        }else{
                            TreeNode tempRoot= getParentTreeNode(root.left,key);
                            if(tempRoot!=null)
                                return tempRoot;
                            root = getParentTreeNode(root.right,key);
                        }
                    }else if(root.left==null && root.right!=null){
                        if(root.right.value ==key){
                            return root;
                        }else{
                            root = getParentTreeNode(root.right,key);
                        }
                    }else if(root.left!=null && root.right==null){
                        if(root.left.value ==key){
                            return root;
                        }else{
                            root = getParentTreeNode(root.left,key);
                        }
                    }
                    else {
                        return null;
                    }
                }
                return root;
            }
            */
        public static TreeNode getParentTreeNode (TreeNode root,int key){
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            if(root==null || root.value==key){
                return null;
            }
            queue.add(root);
            while(!queue.isEmpty()){
                TreeNode current = queue.poll();
                if(current.left!=null){
                    if(current.left.value==key)
                        return current;
                    else
                        queue.add(current.left);
                }
                if(current.right!=null){
                    if(current.right.value==key)
                        return current;
                    else
                        queue.add(current.right);
                }
            }
            return null;
        }
        //获得关键字最大的节点
        public static TreeNode getMaxTreeNode(TreeNode root){
            if(root == null || root.right==null)
                return root;
            if(root.right != null){
                root = getMaxTreeNode(root.right);
            }
            return root;
        }
        //获得关键字最小的节点
        public static TreeNode getMinTreeNode(TreeNode root){
            if(root == null || root.left==null)
                return root;
            if(root.left != null){
                root = getMinTreeNode(root.left);
            }
            return root;
        }
        //打印排序二叉树
        public static void printInOrder(TreeNode root){
            if(root!=null){
                printInOrder(root.left);
                System.out.print(root.value+" ");
                printInOrder(root.right);           
            }
        }
        public static void main(String[] args) throws IOException {
            StreamTokenizer cin = new StreamTokenizer (new BufferedReader(new InputStreamReader(System.in)));
            while(cin.nextToken()!=cin.TT_EOF){
                int n =(int)cin.nval;
                int []input = new int[n];
                for(int i=0;i<n;i++){
                    cin.nextToken();
                    input[i] = (int)cin.nval;
                }
                TreeNode root = null;
                for(int i=0;i<n;i++){
                    root = insertTreeNode(root,input[i]);
                }
                printInOrder(root);
                for(int i=1;i<input.length;i++){
                    TreeNode pNpde = serachTreeNode(root,input[i]);
                    deleteTreeNode(root,pNpde);
                    System.out.print("\n");
                    printInOrder(root);
                }
            }
        }
    }
    展开全文
  • 面试-查找(静态查找动态查找

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

    万次阅读 2018-03-14 15:08:01
    为了防止自己记不住,也方便自己查找,特此记录在博客中查找包含指定内容的文件就是用grep这个命令grep 'name' -r / grep '指定内容' -r 目录上述命令就是在根目录下递归查找包含name内容的文件 -r 递归查找文件 -e ...
  • (3)B-树from:http://student.zjzk.cn/course_ware/data_structure/web/chazhao/chazhao9.3.2.1.htm 当查找的文件较大,且存放在磁盘等直接存取设备中时,为了减少查找过程中对磁盘的读写次数,提高查找效率,...
  • <br />我们这个专题介绍的动态查找树主要有: 二叉查找树(BST),平衡二叉查找树(AVL),红黑树(RBT),B~/B+树(B-tree)。这四种树都具备下面几个优势: (1) 都是动态结构。在删除,插入操作的时候,都不...
  • 查找可以分为静态查找动态查找。 静态查找 定义: 在查找过程中,只是对数据元素执行查找操作,而不对其执行其他操作。 顺序查找 折半查找 索引查找 通常用线性表来表示静态查找表,线性表有顺序存储结构和...
  • 查找分为两种:静态查找动态查找。 1) 静态查找:是指在数据元素集合中查找与给定的关键字相等的元素。 2) 动态查找:就是指在查找过程中,如果数据元素集合中不存在与给定的关键字相等的元素,则将该元素插入...
  • 动态规划_最优二分查找

    千次阅读 2013-11-19 19:24:33
    一、什么是最优二叉查找树 最优二叉查找树: 给定n个互异的关键字组成的序列K=,且关键字有序(k1 图一显示了给定上面的概率分布pi、qi,生成的两个二叉查找树的例子。图二就是在这种情况下一棵最优二叉查找树。 ...
  • 动态查找表——基于树表的查找法 哈希表——计算式查找法 基本概念 查找表 由同一类型的数据元素(记录)构成的集合。 查找的定义 给定一个值 key,在含有 n 个记录的表中找出关键字等于 key 的记录。若找到,则...
  • 查找算法包括:顺序查找,二分查找,分块查找,散列查找,二叉排序树查找,B树 B树用于查找磁盘数据,这里不进行分析顺序查找思想:从头到尾一个一个比较,简单,时间复杂度O(n)java实现:public static int ...
  • 静态查找:顺序查找和折半查找

    千次阅读 2017-06-09 15:18:18
     只是起查询或检索的作用,不涉及插入、删除,反之为动态查找。 二、顺序查找  顺序查找过程中往往设置监视哨,在查找过程中不用每一步都检查整个表是否查找完毕。  假设,每个元素的查找概率相同,顺序查找...
  • 二分查找(折半查找

    万次阅读 多人点赞 2018-07-21 00:07:47
    二分查找是一种算法,其输入是一个有序的元素列表(必须是有序的),如果查找的元素包含在列表中,二分查找返回其位置,否则返回NULL 比如说有一个1-100的数字,我随机的选择其中一个数字(假设为60),你需要以...
  • 查找

    千次阅读 2017-08-09 19:43:00
    既然是查找 时间复杂度肯定不可能大于N吧 什么是ASL?平均查找长度。 ASL =∑PiCi (Pi 为查找第i个记录的概率,Ci为找到第i个记录数据需要比较的次数,Ci随查找过程的不同而不同。)动态查找和静态查找: 静态查找...
  • if(p->lchild)//左子树存在(这里包括了左右子树都存在的情形),就用删除结点的直接前驱代替它 { q=p; s=p->lchild; while(s->rchild) { q=s; s=s->rchild; } p->data=s->data; if(q!=p) ...
  • 动态库的查找路径

    千次阅读 2016-07-11 17:26:58
    LD_LIBRARY_PATH: 动态库的查找路径 设置: 方法一: export LD_LIBRARY_PATH=LD_LIBRARY_PATH:/XXX 但是登出后就失效 方法二: 修改~/.bashrc或~/.bash_profile或系统级别的/etc/profile  1. 在其中添加例如...
  • 近期总结了各大排序算法的原理 ,并对其进行了实现,想着一并把查找算法总结了,今天就着手开始总结查找算法。 废话不多说,这篇文章从最简单的查找算法开始讲起,之后会补充复杂的二叉搜索树查找(BST)和B树,B+树...
  • 查找_分块查找(C语言)

    千次阅读 2020-07-19 15:33:18
    目录分块查找1.查找原理2.源代码:2.1 动态数组实现2.2 顺序表实现2.3 单链表实现 分块查找 分块查找(Blocking Search)又称索引顺序查找,这是一种...索引表包括两项内容:最大关键项、最大关键项块区域的指针项;
  •  对查找表经常进行的操作有:1、查找某个"特定的"数据元素是否在查找表中;2、检索某个"特定的"数据元素的各种属性;3、在查找表中插入一个数据元素;4、从查找表中删去某个数据元素。对查找表只作前两种统称为...
  • 在数据库内查找包含指定字段的表

    千次阅读 2019-06-04 10:43:30
    在数据库内查找包含指定字段的表 SELECT DISTINCT TABLE_NAME FROM information_schema.COLUMNS WHERE COLUMN_NAME = ‘字段名称’ AND TABLE_SCHEMA=‘数据库名称’ ;
  • intellij idea全局查找和替换

    万次阅读 多人点赞 2018-05-02 16:33:44
    lt;intellij idea使用教程汇总篇&gt; 全局查找 通过快捷键 Ctrl+Shift+f 快速进入全局查找页面,或者通过 Edit 》...3、查找范围,分别表示 在整个项目中查找、在指定模块中查找、在指定目录下查找、在指定...
  • 查找算法之线性表查找

    千次阅读 2015-08-29 21:26:21
    动态查找表:在进行查找的操作时候,同时插入不存在的元素,或者删除表中已经存在的元素。 平均查找长度(ASL):对关键字需要执行的平均比较次数作为衡量查找算法效率的标准。 二 线性表查找算法
  • 在当前目录下查找查找包含“hello”的命令,列出文件名。 find . -type f -name "*.txt" | xargs grep "hello" -l
  • SQL游标遍历用户表及各字段查找具有指定数据的字段
  • 查找】折半查找

    万次阅读 多人点赞 2019-01-28 02:40:22
    折半查找 如果从文件中读取的数据记录的关键字是有序排列的(递增的或是递减的),则可以用一种更有效率的查找方法来查找文件中的记录,这就是折半查找法,又称为二分搜索。 折半查找的基本思想:减少查找序列的...
  • 相关概念: 关键字:关键字是数据元素中某给数据项的值,用来标识一...查找包含有一下几种操做: 1、查询某个“特定”的数据元素是否在查找表当中; 2、检索某个“特定”的数据元素的相关属性; 3、在查找中插入数据...
  • 1、线性查找算法 ...例: 有一个数列: {1, 9, 11, -1, 34, 89} ,判断数列中是否包含11 要求: 如果找到了,就提示找到,并给出下标值。 public class SeqSearch { public static void main(String[] args)

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,554,980
精华内容 621,992
关键字:

动态查找包括什么查找