精华内容
下载资源
问答
  • 数据结构查找
    万次阅读
    2018-11-12 18:30:57

    前言

    今天学习数据结构看到了一个词-静态查找表,还有与之对应的动态查找表,然后我发现。

    啊,这是个啥,好像知道又好像不知道,不就是查找吗,干嘛弄这些专业的说法,回头翻了一下数据结构的书,才发现......。

    唉,小小的抱怨一下,不过,我从这两个词联想到了一门基础但是要精通又不简单的学问,就是查找,然后还有前天被面试官问到的一个查找题,题目很简单,如何查找单向链表中倒数第K个数?当然你先遍历一遍数组,获取数组的总长度,然后再遍历一遍找倒数第K个数,当然可以,但是既然是面试题,这样的答案基本是凉凉的,我自己都不满意,更别提人家面试官了,当你抛出这个答案之后,面试官会说如果只遍历一遍呢?你就懵逼了,如果你和我一样懵逼的话,那么恭喜你,你现在还来得及,当然正确方法我就不说了,感兴趣的可以去想想,实在想不出来,我相信你会有办法的,xixixi,也不难。

    好了,说了这么多,今天既然发现了自己的一个薄弱区-查找,指不准以后哪天还会在查找这里栽倒,于是,何不在这之前好好梳理一下查找这块呢?

    目录

    1.静态查找表

    2.动态查找表

    3.哈希表

    正文

    首先我们需要明白下静态查找表和动态查找表的定义,所谓的静态查找表是指在查找过程中只进行查找操作,动态查找表就是在查找过程中还会进行插入和删除操作,例如,查找某个元素,若查找到了,则删除。

    1.静态查找表

    静态查找表可以有不同的表示方法,在不同的表示方法中,实现的查找操作方法也不同。

    这里列举平时遇到的最为常见的两种情况

    a.以顺序表或线性链表表示静态查找表,则查找可用顺序查找来实现

    b.以有序表(排好顺序的顺序表) 表示静态查找表,则查找可用折半查找(二分查找)来实现

    第一种,就是一个for循环的事,就不赘述了,这里看一下第二种情况,也就是二分查找的代码,思想就是从中间位置起开始查找,如果正好位于正中间,那么就找到了,如果比正中间数据大,那么在后半部分查找,假设整个数据是升序,如果比正中间数据小,那么在前半部分查找,依次类推,递归结束的标志就是左边界大于右边界,也就是已经不能再分了,如果此时还没查找到,那么就返回未查找到即可

    public class BinarySearch {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		int[] a=new int[]{2,3,5,8,9};
    		int index=search(a,50);
    		System.out.println(index);
    	}
    	public static int search(int[] a,int data){
    		return binarlSearch(a, 0, a.length-1,data);
    	}
    	public static int binarlSearch(int[] a,int left,int right,int data){
    		if(left>right)
    			return -1;
    		int mid=(left+right)/2;
    		if(a[mid]==data){
    			return mid;
    		}else if(a[mid]<data){
    			return binarlSearch(a, mid+1, right, data);
    		}else{
    			return binarlSearch(a, left, mid-1, data);
    		}
    	}
    }

    上面的只是查找里的入门知识,学任何东西都像打怪升级一样,先从小怪开始,由简变难,下面我们升级来打一个大点的怪!

    2.动态查找表

    动态查找表的特点是:表结构本身是在查找过程中动态生成的,即对于给定的key值,若表中存在其关键字等于key的记录,则查找成功返回,否则插入关键字等于key的记录。

    动态查找表也可有不同的表示方法,这里主要讨论以各种树结构表示时的实现方法。

    a.二叉排序树(又叫  二叉搜索树  二叉查找树)

    二叉排序树的特点是:

    1.若它的左子树不为空,则左子树上所有节点的值均小于它的根节点的值

    2.若它的右子树不为空,则右子树上所有节点的值均大于它的根节点的值

    3.它的左右子树也分别为二叉排序树

    在了解了这个树的性质之后,我们不难联想到二分查找的思想,只不过大同小异,首先和根节点比较,如果比根节点大,则在右子树中查找,如果比根节点小,则在左子树中查找,如果相等,那么正好查找到了,如果左子树也没有,右子树也没有,则查找失败。

    好了,我们掌握了上面的思想,不难写出下面的代码

    	public boolean contains(Node root, Node node) {
    		if (root == null) {
    			return false;
    		}
    		if (node.data == root.data) {
    			return true;
    		} else if (node.data > root.data) {
    			return contains(root.rChild, node);
    		} else {
    			return contains(root.lChild, node);
    		}
    	}

    代码不难理解,然后我们再考虑这样一种情况,就是一个有序的链表,是不是也符合二叉排序树的性质,也就是说我们查找的这棵二叉排序树是有可能退化为一个链表的,那么我们再对照着上面这个查找的代码去看,会发现查找的效率已经退化成了O(n),这显然不是我们想要看到的结果,我们想要的效果是尽可能的将一组数据分为等长的两部分,以达到类似“二分”的效果,只有这样最终的效率才可以达到O log(n)的最优效果,于是我们就引出了这样一个问题,如何保证二叉排序树查找的效率维持在O log(n)呢?接着往下看

    b.平衡二叉树

    在上面,我们发现如果不对二叉排序树做任何处理,发现查找的效率会有可能退化为链表的查找效率,所以我们期望有一种解决方案能避免效率的降低,现在再来想想,为什么我们的查找效率会降低,究其原因就是二叉树退化成了链表,那么我们必须以某种手段来防止退化,比如强制要求左右子树的高度差小于某个值等措施,于是我们自然而然想到了平衡二叉树。

     

    所以解决方案就是让二叉排序树转换为平衡二叉树,这个就好说了,主要涉及到四个操作,左左旋(LL)、右右旋(RR)、左右旋(LR)、右左旋(RL)。通过在插入一个元素的时候,判断是否符合平衡二叉树的性质,也就是左右子树的高度差是否小于1,如果不符合,那么根据情况做相应的旋转处理即可。

    由于几个旋转基本类似,只要掌握了一个,剩下的依葫芦画瓢即可,我们现在来看下左左旋的代码

    	// 左左翻转 LL
    	// 返回值为翻转后的根结点
    	private Node leftLeftRotation(Node node) {
    		// 首先获取待翻转节点的左子节点
    		Node lNode = node.lChild;
    
    		node.lChild = lNode.rChild;
    		lNode.rChild = node;
    
    		node.height = max(getHeight(node.lChild), getHeight(node.rChild)) + 1;
    		lNode.height = max(getHeight(lNode.lChild), node.height) + 1;
    
    		if (node == root) {
    			root = lNode;// 更新根结点
    		}
    		return lNode;
    	}

    剩下三个操作就不细说了,接下来我们再在插入和删除的时候,进行适当的判断,插入代码如下

    	public void insert(int data) {
    		if (root == null) {
    			root = new Node(data);
    
    		} else {
    			insert(root, new Node(data));
    		}
    	}
    
    	// node 为插入的树的根结点
    	// insertNode 为插入的节点
    	private Node insert(Node node, Node insertNode) {
    		if (node == null) {
    			node = insertNode;
    		} else {
    			if (insertNode.data < node.data) {// 将data插入到node的左子树
    				node.lChild = insert(node.lChild, insertNode);
    				// 如果插入后失衡
    				if (getHeight(node.lChild) - getHeight(node.rChild) == 2) {
    					if (insertNode.data < node.lChild.data) {// 如果插入的是在左子树的左子树上,即要进行LL翻转
    						node = leftLeftRotation(node);
    					} else {// 否则执行LR翻转
    						node = leftRightRotation(node);
    					}
    				}
    			} else if (insertNode.data > node.data) {
    				// 将data插入到node的右子树
    				node.rChild = insert(node.rChild, insertNode);
    				// 如果插入后失衡
    				if (getHeight(node.rChild) - getHeight(node.lChild) == 2) {
    					if (insertNode.data > node.rChild.data) {
    						node = rightRightRotation(node);
    					} else {
    						node = rightLeftRotation(node);
    					}
    				}
    			} else {
    				System.out.println("节点重复啦");
    			}
    			node.height = max(getHeight(node.lChild), getHeight(node.rChild)) + 1;
    		}
    		return node;
    	}

    删除代码如下

    	public void remove(int data) {
    		Node removeNode = new Node(data);
    		if (contains(root, removeNode)) {
    			remove(root, removeNode);
    		} else {
    			System.out.println("节点不存在,无法删除"+data);
    		}
    	}
    
    	// 删除节点
    	private Node remove(Node node, Node removeNode) {
    		if (node == null) {
    			return null;
    		}
    		// 待删除节点在node的左子树中
    		if (removeNode.data < node.data) {
    			node.lChild = remove(node.lChild, removeNode);
    			// 删除节点后,若失去平衡
    			if (getHeight(node.rChild) - getHeight(node.lChild) == 2) {
    				Node rNode = node.rChild;// 获取右节点
    				// 如果是左高右低
    				if (getHeight(rNode.lChild) > getHeight(rNode.rChild)) {
    					node = rightLeftRotation(node);
    				} else {
    					node = rightRightRotation(node);
    				}
    			}
    		} else if (removeNode.data > node.data) {// 待删除节点在node的右子树中
    			node.rChild = remove(node.rChild, removeNode);
    			// 删除节点后,若失去平衡
    			if (getHeight(node.lChild) - getHeight(node.rChild) == 2) {
    				Node lNode = node.lChild;// 获取左节点
    				// 如果是右高左低
    				if (getHeight(lNode.rChild) > getHeight(lNode.lChild)) {
    					node = leftRightRotation(node);
    				} else {
    					node = leftLeftRotation(node);
    				}
    			}
    		} else {// 待删除节点就是node
    				// 如果Node的左右子节点都非空
    			if (node.lChild != null && node.rChild != null) {
    				// 如果左高右低
    				if (getHeight(node.lChild) > getHeight(node.rChild)) {
    					// 用左子树中的最大值的节点代替node
    					Node maxNode = maxNode(node.lChild);
    					node.data = maxNode.data;
    					// 在左子树中删除最大的节点
    					node.lChild = remove(node.lChild, maxNode);
    				} else {// 二者等高或者右高左低
    					// 用右子树中的最小值的节点代替node
    					Node minNode = minNode(node.rChild);
    					node.data = minNode.data;
    					// 在右子树中删除最小的节点
    					node.rChild = remove(node.rChild, minNode);
    				}
    				
    			} else {
    				// 只要左或者右有一个为空或者两个都为空,直接将不为空的指向node
    				// 两个都为空的话,想当于最后node也指向了空,逻辑仍然正确
    				node = node.lChild == null ? node.rChild : node.lChild;// 赋予新的值
    			}
    		}
    		if(node!=null) {
    			node.height = max(getHeight(node.lChild), getHeight(node.rChild)) + 1;
    		}
    		return node;
    	}
    

     每次在插入和删除时进行这样的操作之后,我们的二叉排序树终于变成一颗平衡二叉树啦,这样我们再执行上面一模一样的查找代码时,查找的效率就可以稳定在O log(n),完美!

     

    其实仔细想想,这个问题,也是一个取舍的问题,虽然我们最后让二叉排序树的查找效率稳定为O log(n),但是我们却付出了不小的代价,就是每次插入以及删除的时候,都要进行大量的判断以及节点转换,这肯定会大大降低插入和删除的效率,与之带来的收益就是查找效率高,这样再一想,发现有点类似数组和链表的优缺点了,hhhh,事物总是有两面性,所以我们在实际使用时,也要根据场景来适当的做出取舍。

    3.哈希表

    在说哈希表之前,先回忆一下两个最简单的容器,一个是数组,一个是链表,这二者的优缺点我就不啰嗦了,之前的博客我也说过这样一个问题,既然数组查询快,链表插入删除快,就不能发明一种容器能兼具这二者的优点吗?这样岂不时省事多了,答案是能,没错,这个神奇的容器就是HashMap,而其核心就是哈希表,这时候,你兴冲冲的去查询哈希表,可能会遇到很多晦涩难懂的概念,什么关键字冲突,线性探测再散列,链地址法,再哈希等等,一下子头就大了,放心,我不会去给你灌输这些概念,我喜欢以实际使用的东西,或者叫“成品”来学习某个新的东西,然后再反过来看这些概念,这样就自然而然懂了,所以我们先简单了解HashMap的实现原理,再来看哈希表,就自然而然懂了。

    既然是了解HashMap的实现原理,最最正确的方式就是直接打开jdk的源码去看,重点看核心方法put和remove即可,限于篇幅,我就说下大致思想。

    我们首先需要知道的是HashMap存储的数据是键值对的形式,也就是key-value形式,然后就是HashMap里的一些重要成员变量及类,其中最重要的就是Node对象,每个Node对象含有key和value字段,用于保存插入的key和value值,Node数组的默认长度是16,当插入一个元素的时候,首先计算key的hash值,然后直接和数组长度-1做与运算,这样就定位到一个具体的下标,然后判断下标处是否有元素值存在,如果有,则以尾插法在该处形成一个链表,否则,就直接放入这个插入元素即可,所以最终效果就是这样的

    看了这个结构图后,我们再回到我们的主题--查找,我们再来看看HashMap是如何查找的,首先拿到key值,计算key的hash值,然后同样的方法,和长度减1做与运算,得到下标,如果该下标处为空,则返回找不到,如果不为空,则从链表头开始,逐个遍历该链表,直到找到对应的value值与给定value值相等,若链表遍历完了仍然没有找到,则返回找不到。

    我们现在再来看看这个设计有什么巧妙的地方,当我们在查询一个元素时,发现,对于哈希表来说,首先会根据key值来定位一个下标,这个巧妙利用了数组的优势,这样就不用去逐个遍历所有元素,然后如果发现该下标处已经存在了元素,则形成一个链表,而在形成一个链表之后,对同一个下标处的元素来说,插入删除的效率也变高了。或者换种通俗的话就是,使用数组将一个链表分割成了多个小段。总的来说这种设计就是结合了数组和链表,利用了二者的优势所在,完美结合!

    好了,到这里,其实就已经学习了哈希表的一种,如上图,就是链地址法解决冲突的哈希表,相信到这里你也明白了,所谓的链地址法的具体含义,就是形成一个链表来解决冲突问题。

    链地址法也是最常见的一种设计哈希表的方法,我们现在再来看看另外的两种。

    线性探测再散列法,这种设计方式设计的哈希表的原理就是,当插入一个元素的时候,同样的先定位到一个下标,然后如果该下标处已经存在了元素,则判断下标+1的地方是否有元素存在,同样的如果仍然有元素存在,则下标继续+1,直到对应下标处没有元素存在时,则将元素插在这个地方。

    再哈希法,这个设计方式就比较简单粗暴了,直接在计算key的hash值的方法时,也就是在定位具体的下标时,用两次hash函数来计算,这样原本一次hash计算到相同地方的元素,因为有第二次hash计算,所以会在二次hash函数处理之后,再次判断是否定位到了同一下标,若还是定位在统一下标,则继续hash函数处理,直到冲突不再发生。

    我们仍然回到我们的主旨--查找上来,对这两种方法设计的哈希表,我们在查找时就是先定位,然后如果不存在元素,则“查找返回空”,否则比对对应的value值,如果不相等,则根据设计方法(线性探测再散列或再哈希)得到“下一个地址”,然后判断“下一个地址”是否为要查找的元素。

    好了,到这里,基本说完了三种设计哈希表的方式以及对应的查找方法,个人觉得每一种方式都有自己的特点和适用场景,没有孰好孰坏,只有当我们都掌握了之后,我们才可以去选择用哪种方式来实现哈希表,完成业务要求。

    结语

    这次说的主要是查找,内容相对简单,但是查找这个东西,一但结合实际场景之后,还是有很多需要注意和深究的地方,比如海量数据排序和查找,所以只有会了基础,才能有选择的余地,以后实际场景中若是遇到了相关的问题,再总结归纳一篇“实际场景版”的,今天就到这里了。

     

    更多相关内容
  • 数据结构动态查找

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

    千次阅读 2020-12-10 14:48:50
    2.查找表的数据结构表示 (1)动态查找表和静态查找表 若在查找的同时对表做修改操作(如插入和删除),则相应的表称之为动态查找表。否则称之为静态查找表。 (2)内查找和外查找 若整个查找过程都在内存进行,则称...

    第一节 基本概念

    1.查找

    查找的定义是:给定一个值K,在含有n个结点的表中找出关键字等于给定值K的结点。若找到,则查找成功,返回该结点的信息或该结点在表中的位置; 否则查找失败,返回相关的指示信息。

    2.查找表的数据结构表示

    (1)动态查找表和静态查找表
    若在查找的同时对表做修改操作(如插入和删除),则相应的表称之为动态查找表。否则称之为静态查找表。

    (2)内查找和外查找
    若整个查找过程都在内存进行,则称之为内查找;反之,若查找过程中需要访问外存,则称之为外查找。

    3、平均查找长度ASL

    查找运算的主要操作时关键字的比较,所以通常把查找过程中对关键字需要执行的平均比较次数(也称为平均查找长度)作为衡量一个查找算法效率优劣的标准。

    平均查找长度ASL(Average Search Length )定义为:

    在这里插入图片描述
    其中:

    a.n是结点的个数;
    b.Ci是找到第i个结点所需进行的比较次数
    c.Pi是查找第i个结点的概率。若不特别声明,认为每个结点的查找概率相等,即:
    在这里插入图片描述

    第二节 顺序表的查找

    顺序表是指线性表的顺序存储结构,具体数据类型定义:

    在这里插入图片描述

    一,顺序查找

    1.一般顺序表的查找算法

    (1)算法描述

    在这里插入图片描述

    (2)算法分析

    a.查找成功的情况:最好的情况比较1次,最坏的情况比较n次
    查找成功时的平均查找长度=(1+2+…+n)/n=(n+1)/2

    b.查找失败时的查找长度=(n+1)

    c.如果查找成功和不成功机会相等,顺序查找的平均查找长度为
    ((n+1)/2+(n+1))/2 =3/4(n+1)

    2.在递增有序的顺序表的查找算法

    (1)算法描述

    在这里插入图片描述

    (2)算法分析

    a.查找成功的平均查找长度=(n+1)/2

    b.查找失败的平均查找长度=(n+1)/2

    c.如果查找成功和不成功机会相等,该算法的平均查找长度为((n+1)/2+(n+1)/2)*1/2 = (n+1)/2

    二、二分查找法(重点)

    对有序表可以用查找效率较高的二分查找方法来实现查找运算。

    1、二分查找法的思想

    二分查找的思想:首先将待查的k值和有序表R[1…n]的中间位置mid上的记录的关键字进行比较,若相等,则查找成功,返回该记录的下标mid;否则,若R[mid].key>k,则k在左字表R[1…mid-1]中,接着再在左子表中进行二分查找即可;否则,若[min].key<k,则说明待查记录在右子表R[mid+1…n]中,接着只要在右子表中进行二分查找即可。这样,经过一次关键字的比较,就可以缩小一半的查找空间,如此进行下去,直到找到关键字为k的记录或者当前查找区间为空时(即查找失败)为止。二分查找的过程是递归的。

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    3.算法描述

    (1)二分查找递归算法

    在这里插入图片描述

    (2)二分查找非递归算法

    在这里插入图片描述
    4.算法分析

    二分查找方法可以用一颗判定树描述,查找任一元素的过程对应该树中从根节点到相应结点的一条路径。最短的查找长度为1,最长的查找长度为对应判定树的深度log2n+1向下取整,平均查找长度(n+1)/n*log2(n+1)-1 =log(n+1)-1.二分查找方法效率高是有代价的,因为有序表是通过排序而得到的,而排序操作又是比较费时的,二分查找只适用于顺序结构上的有序表,对链式结构无法进行二分查找。

    在这里插入图片描述

    5.应用实例

    在这里插入图片描述
    三,索引顺序查找

    索引顺序查找又称分块查找,它是一种性能介于顺序查找和二分查找之间的查找方法。

    1.索引查找表的存储结构

    (1)分块有序的线性表

    表R[1…n]均分为b块,前b-1块中结点个数为S=[n/b] ,第b块的结点数小于等于s;每一块中的关键字不一定有序,但前一块中的最大关键字必须小于后一块中的最小关键字,即表是‘分块有序’的。

    (2)索引表

    抽取各块中的最大关键字及其起始位置构成一个索引表ID [ 1 …b ] , 即 :ID [ i ] (1<=i<=b)中存放第i块最大关键字及该块在表R中的起始位置。由于表R是分块有序的,所以索引表是一个递增有序表。

    【例】下图就是满足上述要求的存储结构,其中R只有18个结点,被分成3块,每块中有6个结点,第一块中最大关键字21小于第二块中最小关键字23,第二块中最大关键字45小于第三块中最小关键字48.

    在这里插入图片描述
    2、索引查找的基本思想

    (1)首先查找索引表
    索引表是有序表,可采用二分查找或顺序查找,以确定待查的结点在那一块。

    (2)然后在已确定的块中进行顺序查找
    由于块内无序,只能用顺序查找。

    3.索引查找的平均查找长度

    (1)查找索引表采用二分查找时的平均查找长度。

    ASLblk = log2(b+1) -1+(s+1)/2 = log2(n/s +1)+s/2

    (2)查找索引表采用顺序查找时的平均查找长度
    ASLblk = (b+1)/2 +(s+1)/2 =(b+s)/2 +1= (n/s+s)/2+1 =(块数+块长)/2+1

    当s取根号n(即s=b)时,ASLblk达到最小值根号n+1,即当采用顺序查找确定块时,应将各块中的结点数选定为根号n。

    四,三种查找方法比较

    1、顺序查找

    优点:算法简单,对表的存储结构无任何要求。
    缺点:查找效率低,查找成功的平均查找长度为(n+1)/2。查找失败的查找长度为(n+1).

    2.二分查找

    优点:二分查找的速度,效率高,查找成功的平均查找长度约为log(n+1)-1。

    缺点:要求表以顺序存储表示并且是按关键字有序,使用高效率的排序方法也要花费O(nlog2n)的时间。另外,当对表结点进行插入或删除时,需要移动大量的元素,所以二分查找使用于表不易变动且又经常查找的情况。

    3.分块查找
    优点:在表中插入或删除一个记录时,只要找到该记录所属的块,就可以在该块内进行插入或删除运算。因为块内记录是无序的,所以插入或删除比较容易,无需移动大量记录。

    缺点:是需要增加一个辅助数组的存储空间和将初始表块排序的运算,它也不适宜用链式存储结构。

    此外,顺序查找,二分查找和分块查找三种查找算法的时间复杂度分别为:O(n),O(log2n)和O()。分块查找算法的效率介于顺序查找和二分查找之间。

    【例】若表中有10000个结点,则应把它分成100个块,每块中含100个结点,用顺序查找确定块,分块查找平均需要做根号n+1=根号10000+1=101次比较;顺序查找平均需要做(n+1)/2=5000次比较;二分查找最多需log2 10000 +1=14次比较,平均查 找 长度 log2 10001-1。

    第三节 树表的查找(一)

    一、二叉排序树

    1.二叉排序树的概念

    (1)二叉排序树的定义
    二叉排序树(Binary Sort Tree,BST)又称二叉查找,是一种特殊的二叉树,二叉排序树或者是空树,或者是满足如下性质的二叉树;

    a.若它的左子树非空,则左子树上所有结点的值均小于根结点的值;

    b.若它的右子树非空,则右子树上所有结点的值均大于根结点的值;

    c.左/右子树本身又是一颗二叉排序树。

    在这里插入图片描述

    (2)二叉排序树的重要性质

    中跟遍历一颗二叉排序树所得的结点访问序列是按简直的递增序列。

    (3)二叉排序树的数据类型定义

    在这里插入图片描述
    2、二叉排序树的插入

    (1)算法思想

    在二叉排序树中插入新结点,要保证插入后仍满足BST性质。其插入过程是:

    a.若二叉排序树T为空,则为待插入的关键字key申请一个新结点,并令其为根;

    b.若二叉排序树T不为空,则将key和根的关键字比较;

    c. 若二者相等,则说明是树中已有此关键字key,无须插入。

    若key<t–key,则 将key插入根的左子树中。
    若key>t–key,则将它插入根的右子树中。

    子树中的插入过程与上述的树中插入过程相同。如此进行下去,直到将key作为一个新的叶结点的关键字插入到二叉排序树中,或者直到发现树中已有此关键字为止。

    (2)实例分析
    【例】写出把无序序列(20,10,30,15,25,5,35,12,27)建成二叉排序树的过程。
    【解答】采用逐点插入结点的方法即可建立相应的二叉排序树。建成二叉排序树的过程如图所示
    在这里插入图片描述
    在这里插入图片描述

    3.二叉排序树的生成

    (1)算法思想

    从空的二叉树开始,每输入一个结点数据,生成一个新结点,就调用一次插入算法将它插入到当前生成的二叉排序树中

    (2)算法描述

    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
    4.二叉排序树的查找

    (1)算法思想

    若二叉排序树为空,则表明查找失败,应返回空指针。否则,若给定值key等于根结点的关键字,则表明查找成功,返回当前根结点指针;若给定值key小于根结点的关键字,则继续在根结点的左子树中查找,若给定值key大于根结点的关键字,则继续在根结点的右子树中查找。显然,这是一个递归的查找过程。

    (2)算法描述
    在这里插入图片描述
    (3)算法分析

    二叉排序树上的查找长度与二叉排序树的形态有关,若二叉排序树是一棵理想的平衡树(是指树中任一结点的左右子树的高度差不能大于1),则进行查找的时间复杂度为O(log2n);若退化为一棵单支树,则其查找的时间复杂度为O(n).对于一般情况,其时间复杂度应为O(log2n).

    【例】给定表(20,15,18,12,25,27,30,22,17,20,28),按数据元素在表中的次序构造一棵二叉排序树,求出其平均查找长度。

    在这里插入图片描述

    5.二叉排序树上的删除

    从BST树上删除一个结点,仍然要保证删除后满足BST的性质。设被删除结点为p,其父结点为f,如图(a)所示的BST树。具体删除情况分析如下:

    在这里插入图片描述
    (1)若p是叶子结点:直接删除p,如图(b)所示。

    (2)若p只有一颗子树(左子树或右子树),直接用p的左子树(或右子树)取代p的位置而成为f的一棵子树。即原来p是f的左子树,则p的子树成为f的左子树;原来p是f的右子树,则p的子树成为f的右子树,如图(c)所示。

    (3)若p既有左子树又有右子树,处理方法有以下两种,可以任选其中一种。

    a.用p的直接前驱结点(中序遍历)代替p,即从p的左子树中选择值最大的结点s放在p的位置(用结点s的内容替换结点p内容),然后删除结点s.s是p的左子树中最右边的结点且没有右子树,如图(d)所示。

    b.用p的直接后继结点(中序遍历)代替p,即从p的右子树中选择值最小的结点s放在p的位置(用结点s的内容替换结点p的内容),然后删除结点s。s是p的右子树中的最左边的结点且没有左子树。例如,对图(a)所示的二叉排序树,删除结点8后所得的结果如图(e)所示。

    在这里插入图片描述

    第三节 树表的查找(二)

    二,B树

    1.B树的概念

    (1)B树的定义
    一棵m(m>=3)阶的B树,或为空树,或为满足下列性质的m叉树:

    a.每个结点至少包含下列信息域:
    (n,p0,k1,p1,k2…,kn,pn)

    其中,n为关键字的个数:

    ki(1<=i<=n)为关键字,且ki<ki+1(1<=i<=n-1);
    pi(1<=i<=n)为指向子树跟结点的指针,且pi所指向子树中所有结点的关键字均小于ki+1,pn所指子树中所有结点关键字均大于kn.

    b.树中每个结点至多有m棵子树。
    c.若树为非空,则根结点至少有1个关键字,至多有m-1个关键字。因此,若跟结点不是叶子,则它至少有两棵子树。
    d.所有的叶结点都在同一层上,并且不带信息(可以看做是外部结点或查找失败的结点,实际上这些结点不存在,指向他们的指针均为空),叶子的层数为树的高度h。
    f.每个非根结点中包含的关键字个数满足:[m/2]-1<=n<=m-1. 因为每个内部结点的度数正好是关键字总数加1,所以,除根结点之外的所有非终端结点(非叶子结点的最下层的结点称为终端结点)至少有[m/2]棵子树,至多有m棵子树。

    (2)实例
    在这里插入图片描述
    (3)B树的结点类型定义

    在这里插入图片描述
    2.B树上的插入

    在B树中插入一个结点的过程:先在最低层的某个非终端结点中添加一个关键字。若该结点中关键字的个数不超过m-1,则插入完成,否则要产生结点“分裂”。“分裂”结点时把结点分成两个,将中间的一个关键字拿出来插入到该结点的双亲结点上,如果双亲结点中已有m-1个关键字,则插入后将引起双亲结点的分裂,这一过程可能波及B树的根结点,引起根结点的分裂,从而使B树长高一层。

    在这里插入图片描述
    在这里插入图片描述
    3.B树上的删除

    (1)若需要删除关键字所在结点中的关键字数目不小于m/2向上取整,则只需要该结点中关键字和相对于的指针删除。

    在这里插入图片描述

    (2)若需删除关键字所咋结点中的关键字数目等于m/2-1向上取整,即关键字数目已是最小值,直接删除该关键字会破坏B树的性质。删除这样关键字分两种情况处理:

    a.若删除结点的左(或右)邻兄弟结点中的关键字数目不小于m/2向上取整,则将其兄弟结点中的最大(或最小)的关键字上移至双亲结点中,而将双亲结点中相应的关键字移至删除关键字所在结点中。

    在这里插入图片描述
    b.若需删除关键字所在结点及其相邻的左,右兄弟(或只有一个兄弟)结点中关键字数目均等于m/2-1向上取整,则按上述情况a的移动操作就不能实现。此时,就需要将被删除结点与其左兄弟或右兄弟结点进行“合并”。

    在这里插入图片描述
    上述情况b如果因“合并”操作引起对父结点中关键字的删除,又可能要合并结点,这一过程可能波及根,引起对根结点中关键字的删除,从而可能使B树的高度降低一层。

    在这里插入图片描述
    4.B树上的查找

    (1)查找算法思想

    在B树中查找一个关键字等于给定值K的具体过程:若B树为非空,则首先取出根结点,将给定值K依次与关键字向量中从高下标端(key[keynum])开始的每个关键字进行比较,直到K>=Ki(0<=i<=n=keynum,用key[0]作为中止标志,存放给定的查找值K)为止,此时,若K=Ki且i>0,则表明查找成功。返回具有该关键字的结点的存储位置及K在key[1…keynum]中的位置;否则,其值为K的关键字只可能落在当前结点的pi所指向的子树上,接着只要在该子树商继续进行查找即可。这样,每取出一个结点比较后就下移一层,直到查找成功,或被查找的子树为空(即查找失败)为止。

    在这里插入图片描述
    在这里插入图片描述

    先和根结点a比较:把K=18赋给k0.k=18小于k1的值48,再同a结点中k0比较,k0=k,因为i=0,所以接着取出a结点的p0指向的结点b,用K与b结点中的k2=32进行比较,k=18<k2=32
    而K=18>k1=16,所以再取出b结点的p1所指向的结点e;因为k=k1,因此查找成功,返回e结点的存储地址以及k1d的位置pos=1.

    三、B+树

    B+树是一种常用语文件组织的B树的变形树。一棵m阶的B+树和m阶的B树的差异在于:

    (1)有k个孩子的结点必含有k个关键字。
    (2)所有的叶结点中包含了关键字的信息及指向相应结点的指针,且叶子结点本身依照关键字的大小从小到大顺序链接。
    (3)所有非终端结点可看成是索引部分,结点中仅含有其子树(根结点)中的最大关键字(或最小)关键字。

    下图所示是一棵3阶的B+树。通常在B+树上上有两个头指针root和sqt,前者指向跟结点,后者指向关键字最小的叶子结点。因此,可以对B+树进行两种查找运算:一种是从最小关键字起进行顺序查找,另一种是从根结点开始进行随机查找。

    在这里插入图片描述

    第四节 散列表查找

    一、散列表的概念
    1.散列的概念

    “散列”即时一种存储方式,又是一种查找方法。这种查找方法称为散列查找。散列的基本思想是通过由散列函数决定的键值与散列地址之间的对应关系来实现存储组织和查找运算。

    2.实例分析
    【例】有个线性表A=(31,62,74,36,49,77),散列函数为H(key)=key%m即用元素的关键字key整除m,取其余数作为存储该元素的散列地址,m一般取小于或等于散列表长的最大素数,在这里取m=11,表长业为11,因此可以得到每个元素的散列地址:

    在这里插入图片描述

    二,散列函数的构造方法

    1、直接地址法
    直接地址法是以关键字key本身或关键字加上某个常量C作为散列地址的方法。对应的散列函数H(key)为:H(key)=key +C
    特点:方法计算简单,并且没有冲突。它适合于关键字的分布基本连续的情况,若关键字分布不连续,空号较多,将会造成较大的空间浪费。

    2,数字分析法
    数字分析法是假设有一组关键字,每个关键字由n位数组成,数字分析法是从中提取数字分布比较均匀的若干位作为散列地址。

    3.除余数法

    除余数法是一种最简单也最常用的一种散列函数构造方法。散列函数:H(k)=k%p.
    其中,p最好选取小于或等于表长m的最大素数。

    4.平方取中法
    平方取中法是取关键字平方的中间几位作为散列地址的方法

    5.折叠法
    折叠法是首先把关键字分割成位数相同的几段(最后一段的位数可少一些),段的位数取决于散列地址的位数,由实际情况而定,然后将他们的叠加和(舍去最高进位)作为散列地址的方法。

    【例】关键字k=98 123 658 ,散列地址为3位,则将关键字从左到右每三位一段进行划分,得到的三个段为981、236和58,叠加后值为1275,取低3位275作为关键字98 123 658的元素的散列地址

    三,处理冲突的方法

    1、开放定址法
    开放定址法的思想:使用某种方法在散列表中形成一个探查序列,沿着此序列逐个单元进行查找,直到找到一个空闲的单元时将新的结点存入其中。

    开放定址法又分为线性探查法、二次探查法和双重散列法。

    (1)线性探查法
    探查序列可以由下述公式得到:di=(d+i)%m
    其中:di表示第i次探查的地址,m表示散列表的长度。

    【例】设散列函数为h(key)=key%11;散列地址表空间为0-10,对关键字序列{27,13,55,32,18,49,24,38,43},利用线性探测法解决冲突,构造散列表。并计算查找成功时的平均查找长度。
    在这里插入图片描述
    (2)二次探查法

    在这里插入图片描述

    (3)双重散列法

    在这里插入图片描述
    2.拉链法(链地址法)

    用拉链法处理冲突的办法是:把具有相同散列地址的关键字(同义词)值放在同一个单链表中,称为同义词链表。

    在这里插入图片描述
    四.散列表的查找

    1.线性探查法解决冲突的查找和插入算法

    在这里插入图片描述
    (1)采用线性探查法的散列表查找算法

    在这里插入图片描述
    (2)在散列表上插入一个结点的算法

    在这里插入图片描述
    2.拉链法建立散列表上的查找和插入运算

    采用拉链法的散列表类定义:

    在这里插入图片描述

    (2)插入算法

    在这里插入图片描述

    3.几种处理冲突方法的散列表的平均查找长度比较
    【例】设散列函数h(k)=k%13,散列表地质空间0-12,对给定的关键字序列(19,14,01,68,20,84,27,26,50,36)分别以拉链法和线性探查法解决冲突构造散列表,画出所构造的散列表,指出在这两个散列表中查找每一个关键字时进行比较的次数,并分析在等概率情况下查找成功和查找不成功的平均查找长度以及当结点数为n=10时的顺序查找和二分查找成功与不成功的情况.

    在这里插入图片描述

    在这里插入图片描述
    在这里插入图片描述

    **注意:**结点个数n,散列表长度为m,散列表的平均查找长度不是n的函数,而是装填因子α=n/m的函数,采用四种不同方法处理冲突时得出的散列表的平均查找长度:

    在这里插入图片描述
    开放定址法要求散列表的装填因子α<=1,实用中一般取0.65-0.9之间的某个值为宜。在拉链法中,其装填因子α可以大于1,但一般均取α<=1.

    小结:

    讨论了顺序表的查找,树表的查找以及散列查找。重点讨论了二分查找,二叉,排序树及散列表查找,这也是本章需要学习掌握的重点。不仅要理解这些查找算法的基本思想,还要能够写出各种算法记录的查找和插入顺序过程,以及分析比较计算这些算法在等概率情况下查找成功时的平均查找长度等。

    展开全文
  • 数据结构–七大查找算法总结

    万次阅读 多人点赞 2018-08-06 17:13:43
    数据结构–七大查找算法总结 2017年08月15日 21:06:17 阅读数:10610 ...

      查找定义:根据给定的某个值,在查找表中确定一个其关键字等于给定值的数据元素(或记录)。

       查找算法分类:
      1)静态查找和动态查找;
        注:静态或者动态都是针对查找表而言的。动态表指查找表中有删除和插入操作的表。
      2)无序查找和有序查找。
        无序查找:被查找数列有序无序均可;
        有序查找:被查找数列必须为有序数列。
       平均查找长度(Average Search Length,ASL):需和指定key进行比较的关键字的个数的期望值,称为查找算法在查找成功时的平均查找长度。
      对于含有n个数据元素的查找表,查找成功的平均查找长度为:ASL = P i*C i的和。
      P i:查找表中第i个数据元素的概率。
      C i:找到第i个数据元素时已经比较过的次数。

    1. 顺序查找

       说明:顺序查找适合于存储结构为顺序存储或链接存储的线性表。
       基本思想:顺序查找也称为线形查找,属于无序查找算法。从数据结构线形表的一端开始,顺序扫描,依次将扫描到的结点关键字与给定值k相比较,若相等则表示查找成功;若扫描结束仍没有找到关键字等于k的结点,表示查找失败。
       复杂度分析: 
      查找成功时的平均查找长度为:(假设每个数据元素的概率相等) ASL = 1/n(1+2+3+…+n) = (n+1)/2 ;
      当查找不成功时,需要n+1次比较,时间复杂度为O(n);
      所以, 顺序查找的时间复杂度为O(n)。
      C++实现源码:
    
       
    //顺序查找
    int SequenceSearch(int a[], int value, int n)
    {
        int i;
        for(i=0; i<n; i++)
            if(a[i]==value)
                return i;
        return -1;
    }
    

    2. 二分查找

      说明:元素必须是有序的,如果是无序的则要先进行排序操作。

      基本思想:也称为是折半查找,属于有序查找算法。用给定值k先与中间结点的关键字比较,中间结点把线形表分成两个子表,若相等则查找成功;若不相等,再根据k与该中间结点关键字的比较结果确定下一步查找哪个子表,这样递归进行,直到查找到或查找结束发现表中没有这样的结点。

      复杂度分析:最坏情况下,关键词比较次数为log2(n+1),且期望时间复杂度为O(log2n)

      注:折半查找的前提条件是需要有序表顺序存储,对于静态查找表,一次排序后不再变化,折半查找能得到不错的效率。但对于需要频繁执行插入或删除操作的数据集来说,维护有序的排序会带来不小的工作量,那就不建议使用。——《大话数据结构

      C++实现源码:

    
    
    //二分查找(折半查找),版本1
    int BinarySearch1(int a[], int value, int n)
    {
        int low, high, mid;
        low = 0;
        high = n-1;
        while(low<=high)
        {
            mid = (low+high)/2;
            if(a[mid]==value)
                return mid;
            if(a[mid]>value)
                high = mid-1;
            if(a[mid]<value)
                low = mid+1;
        }
        return -1;
    }
    
    //二分查找,递归版本
    int BinarySearch2(int a[], int value, int low, int high)
    {
        int mid = low+(high-low)/2;
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            return BinarySearch2(a, value, low, mid-1);
        if(a[mid]<value)
            return BinarySearch2(a, value, mid+1, high);
    }
    

    3. 插值查找

      在介绍插值查找之前,首先考虑一个新问题,为什么上述算法一定要是折半,而不是折四分之一或者折更多呢?
      打个比方,在英文字典里面查“apple”,你下意识翻开字典是翻前面的书页还是后面的书页呢?如果再让你查“zoo”,你又怎么查?很显然,这里你绝对不会是从中间开始查起,而是有一定目的的往前或往后翻。
      同样的,比如要在取值范围1 ~ 10000 之间 100 个元素从小到大均匀分布的数组中查找5, 我们自然会考虑从数组下标较小的开始查找。
      经过以上分析,折半查找这种查找方式,不是自适应的(也就是说是傻瓜式的)。二分查找中查找点计算如下:
      mid=(low+high)/2, 即mid=low+1/2*(high-low);
      通过类比,我们可以将查找的点改进为如下:
      mid=low+(key-a[low])/(a[high]-a[low])*(high-low),
      也就是将上述的比例参数1/2改进为自适应的,根据关键字在整个有序表中所处的位置,让mid值的变化更靠近关键字key,这样也就间接地减少了比较次数。
       基本思想:基于二分查找算法,将查找点的选择改进为自适应选择,可以提高查找效率。当然,差值查找也属于有序查找。
      注: 对于表长较大,而关键字分布又比较均匀的查找表来说,插值查找算法的平均性能比折半查找要好的多。反之,数组中如果分布非常不均匀,那么插值查找未必是很合适的选择。
      复杂度分析:查找成功或者失败的时间复杂度均为O(log2(log2n))。
       C++实现源码:
    
     
    //插值查找
    int InsertionSearch(int a[], int value, int low, int high)
    {
        int mid = low+(value-a[low])/(a[high]-a[low])*(high-low);
        if(a[mid]==value)
            return mid;
        if(a[mid]>value)
            return InsertionSearch(a, value, low, mid-1);
        if(a[mid]<value)
            return InsertionSearch(a, value, mid+1, high);
    }
    

    4. 斐波那契查找

      在介绍斐波那契查找算法之前,我们先介绍一下很它紧密相连并且大家都熟知的一个概念——黄金分割。

      黄金比例又称黄金分割,是指事物各部分间一定的数学比例关系,即将整体一分为二,较大部分与较小部分之比等于整体与较大部分之比,其比值约为1:0.618或1.618:1。

      0.618被公认为最具有审美意义的比例数字,这个数值的作用不仅仅体现在诸如绘画、雕塑、音乐、建筑等艺术领域,而且在管理、工程设计等方面也有着不可忽视的作用。因此被称为黄金分割。

      大家记不记得斐波那契数列:1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89…….(从第三个数开始,后边每一个数都是前两个数的和)。然后我们会发现,随着斐波那契数列的递增,前后两个数的比值会越来越接近0.618,利用这个特性,我们就可以将黄金比例运用到查找技术中。

       基本思想:也是二分查找的一种提升算法,通过运用黄金比例的概念在数列中选择查找点进行查找,提高查找效率。同样地,斐波那契查找也属于一种有序查找算法。
      相对于折半查找,一般将待比较的key值与第mid=(low+high)/2位置的元素比较,比较结果分三种情况:

      1)相等,mid位置的元素即为所求

      2)>,low=mid+1;

         3)<,high=mid-1。

      斐波那契查找与折半查找很相似,他是根据斐波那契序列的特点对有序表进行分割的。他要求开始表中记录的个数为某个斐波那契数小1,及n=F(k)-1;

     开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1),比较结果也分为三种

      1)相等,mid位置的元素即为所求

      2)>,low=mid+1,k-=2;

      说明:low=mid+1说明待查找的元素在[mid+1,high]范围内,k-=2 说明范围[mid+1,high]内的元素个数为n-(F(k-1))= Fk-1-F(k-1)=Fk-F(k-1)-1=F(k-2)-1个,所以可以递归的应用斐波那契查找。

      3)<,high=mid-1,k-=1。

      说明:low=mid+1说明待查找的元素在[low,mid-1]范围内,k-=1 说明范围[low,mid-1]内的元素个数为F(k-1)-1个,所以可以递归 的应用斐波那契查找。

       复杂度分析:最坏情况下,时间复杂度为O(log2n),且其期望复杂度也为O(log2n)。

      C++实现源码:

    
    
    // 斐波那契查找.cpp 
    #include "stdafx.h"
    #include <memory>;
    #include  <iostream>;
    using namespace std;
    
    const int max_size=20;//斐波那契数组的长度
    
    /*构造一个斐波那契数组*/ 
    void Fibonacci(int * F)
    {
        F[0]=0;
        F[1]=1;
        for(int i=2;i<max_size;++i)
            F[i]=F[i-1]+F[i-2];
    }
    
    /*定义斐波那契查找法*/  
    int FibonacciSearch(int *a, int n, int key)  //a为要查找的数组,n为要查找的数组长度,key为要查找的关键字
    {
      int low=0;
      int high=n-1;
      
      int F[max_size];
      Fibonacci(F);//构造一个斐波那契数组F 
    
      int k=0;
      while(n>F[k]-1)//计算n位于斐波那契数列的位置
          ++k;
    
      int  * temp;//将数组a扩展到F[k]-1的长度
      temp=new int [F[k]-1];
      memcpy(temp,a,n*sizeof(int));
    
      for(int i=n;i<F[k]-1;++i)
         temp[i]=a[n-1];
      
      while(low<=high)
      {
        int mid=low+F[k-1]-1;
        if(key<temp[mid])
        {
          high=mid-1;
          k-=1;
        }
        else if(key>temp[mid])
        {
         low=mid+1;
         k-=2;
        }
        else
        {
           if(mid<n)
               return mid; //若相等则说明mid即为查找到的位置
           else
               return n-1; //若mid&gt;=n则说明是扩展的数值,返回n-1
        }
      }  
      delete [] temp;
      return -1;
    }
    
    int main()
    {
        int a[] = {0,16,24,35,47,59,62,73,88,99};
        int key=100;
        int index=FibonacciSearch(a,sizeof(a)/sizeof(int),key);
        cout<<key<<" is located at:"<<index;
        return 0;
    }
    

    5. 树表查找

      5.1 最简单的树表查找算法——二叉树查找算法。

      基本思想:二叉查找树是先对待查找的数据进行生成树,确保树的左分支的值小于右分支的值,然后在就行和每个节点的父节点比较大小,查找最适合的范围。 这个算法的查找效率很高,但是如果使用这种查找方法要首先创建树。 

      二叉查找树(BinarySearch Tree,也叫二叉搜索树,或称二叉排序树Binary Sort Tree)或者是一棵空树,或者是具有下列性质的二叉树:

      1)若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

      2)若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

      3)任意节点的左、右子树也分别为二叉查找树。

      二叉查找树性质对二叉查找树进行中序遍历,即可得到有序的数列。

      不同形态的二叉查找树如下图所示:

       有关二叉查找树的查找、插入、删除等操作的详细讲解,请移步浅谈算法和数据结构: 七 二叉查找树

      复杂度分析:它和二分查找一样,插入和查找的时间复杂度均为O(logn),但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候,树没有保持平衡(比如,我们查找上图(b)中的“93”,我们需要进行n次查找操作)。我们追求的是在最坏的情况下仍然有较好的时间复杂度,这就是平衡查找树设计的初衷。

      下图为二叉树查找和顺序查找以及二分查找性能的对比图:

     

      基于二叉查找树进行优化,进而可以得到其他的树表查找算法,如平衡树、红黑树等高效算法。

      5.2 平衡查找树之2-3查找树(2-3 Tree)

      2-3查找树定义:和二叉树不一样,2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node),他保存1个key和左右两个自己点。对应3节点(3-node),保存两个Key,2-3查找树的定义如下:

      1)要么为空,要么:

      2)对于2节点,该节点保存一个key及对应value,以及两个指向左右节点的节点,左节点也是一个2-3节点,所有的值都比key要小,右节点也是一个2-3节点,所有的值比key要大。

      3)对于3节点,该节点保存两个key及对应value,以及三个指向左中右的节点。左节点也是一个2-3节点,所有的值均比两个key中的最小的key还要小;中间节点也是一个2-3节点,中间节点的key值在两个跟节点key值之间;右节点也是一个2-3节点,节点的所有key值比两个key中的最大的key还要大。

    Definition of 2-3 tree

      2-3查找树的性质:

      1)如果中序遍历2-3查找树,就可以得到排好序的序列;

      2)在一个完全平衡的2-3查找树中,根节点到每一个为空节点的距离都相同。(这也是平衡树中“平衡”一词的概念,根节点到叶节点的最长距离对应于查找算法的最坏情况,而平衡树中根节点到叶节点的距离都一样,最坏情况也具有对数复杂度。)

      性质2)如下图所示:

     

      复杂度分析:

      2-3树的查找效率与树的高度是息息相关的。

    • 在最坏的情况下,也就是所有的节点都是2-node节点,查找效率为lgN
    • 在最好的情况下,所有的节点都是3-node节点,查找效率为log3N约等于0.631lgN

      距离来说,对于1百万个节点的2-3树,树的高度为12-20之间,对于10亿个节点的2-3树,树的高度为18-30之间。

      对于插入来说,只需要常数次操作即可完成,因为他只需要修改与该节点关联的节点即可,不需要检查其他节点,所以效率和查找类似。下面是2-3查找树的效率:

    analysis of 2-3 tree

     

      5.3 平衡查找树之红黑树(Red-Black Tree)

      2-3查找树能保证在插入元素之后能保持树的平衡状态,最坏情况下即所有的子节点都是2-node,树的高度为lgn,从而保证了最坏情况下的时间复杂度。但是2-3树实现起来比较复杂,于是就有了一种简单实现2-3树的数据结构,即红黑树(Red-Black Tree)。

      基本思想:红黑树的思想就是对2-3查找树进行编码,尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型,红色链接,他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的,使用红色链接的两个2-nodes来表示一个3-nodes节点,并且向左倾斜,即一个2-node是另一个2-node的左子节点。这种做法的好处是查找的时候不用做任何修改,和普通的二叉查找树相同。

    Red black tree

      红黑树的定义:

      红黑树是一种具有红色和黑色链接的平衡查找树,同时满足:

    • 红色节点向左倾斜
    • 一个节点不可能有两个红色链接
    • 整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同。

      下图可以看到红黑树其实是2-3树的另外一种表现形式:如果我们将红色的连线水平绘制,那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。

    1-1 correspondence between 2-3 and LLRB

      红黑树的性质整个树完全黑色平衡,即从根节点到所以叶子结点的路径上,黑色链接的个数都相同(2-3树的第2)性质,从根节点到叶子节点的距离都相等)。

      复杂度分析:最坏的情况就是,红黑树中除了最左侧路径全部是由3-node节点组成,即红黑相间的路径长度是全黑路径长度的2倍。

      下图是一个典型的红黑树,从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍:

    a typic red black tree

      红黑树的平均高度大约为logn。

      下图是红黑树在各种情况下的时间复杂度,可以看出红黑树是2-3查找树的一种实现,它能保证最坏情况下仍然具有对数的时间复杂度。

      红黑树这种数据结构应用十分广泛,在多种编程语言中被用作符号表的实现,如:

    • Java中的java.util.TreeMap,java.util.TreeSet;
    • C++ STL中的:map,multimap,multiset;
    • .NET中的:SortedDictionary,SortedSet 等。

      5.4 B树和B+树(B Tree/B+ Tree)

      平衡查找树中的2-3树以及其实现红黑树。2-3树种,一个节点最多有2个key,而红黑树则使用染色的方式来标识这两个key。

      维基百科对B树的定义为“在计算机科学中,B树(B-tree)是一种树状数据结构,它能够存储数据、对其进行排序并允许以O(log n)的时间复杂度运行进行查找、顺序读取、插入和删除的数据结构。B树,概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同,B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程,从而加快存取速度。普遍运用在数据库文件系统

      B树定义:

      B树可以看作是对2-3查找树的一种扩展,即他允许每个节点有M-1个子节点。

    • 根节点至少有两个子节点

    • 每个节点有M-1个key,并且以升序排列

    • 位于M-1和M key的子节点的值位于M-1 和M key对应的Value之间

    • 其它节点至少有M/2个子节点

      下图是一个M=4 阶的B树:

      可以看到B树是2-3树的一种扩展,他允许一个节点有多于2个的元素。B树的插入及平衡化操作和2-3树很相似,这里就不介绍了。下面是往B树中依次插入

    6 10 4 14 5 11 15 3 2 12 1 7 8 8 6 3 6 21 5 15 15 6 32 23 45 65 7 8 6 5 4

    的演示动画:

      B+树定义:

      B+树是对B树的一种变形树,它与B树的差异在于:

    • 有k个子结点的结点必然有k个关键码;
    • 非叶结点仅具有索引作用,跟记录有关的信息均存放在叶结点中。
    • 树的所有叶结点构成一个有序链表,可以按照关键码排序的次序遍历全部记录。

      如下图,是一个B+树:

    B Plus tree

     

      下图是B+树的插入动画:

     

      B和B+树的区别在于,B+树的非叶子结点只包含导航信息,不包含实际的值,所有的叶子结点和相连的节点使用链表相连,便于区间查找和遍历。

      B+ 树的优点在于:

    • 由于B+树在内部节点上不好含数据信息,因此在内存页中能够存放更多的key。 数据存放的更加紧密,具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
    • B+树的叶子结点都是相链的,因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连,所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻,所以缓存命中性没有B+树好。

      但是B树也有优点,其优点在于,由于B树的每一个节点都包含key和value,因此经常访问的元素可能离根节点更近,因此访问也更迅速。

      下面是B 树和B+树的区别图:

    Different between B tree and B plus tree

      B/B+树常用于文件系统和数据库系统中,它通过对每个节点存储个数的扩展,使得对连续的数据能够进行较快的定位和访问,能够有效减少查找时间,提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中,如:

    • Windows:HPFS文件系统;
    • Mac:HFS,HFS+文件系统;
    • Linux:ResiserFS,XFS,Ext3FS,JFS文件系统;
    • 数据库:ORACLE,MYSQL,SQLSERVER等中。

      有关B/B+树在数据库索引中的应用,请看张洋的MySQL索引背后的数据结构及算法原理这篇文章,这篇文章对MySQL中的如何使用B+树进行索引有比较详细的介绍,推荐阅读。

      树表查找总结:

      二叉查找树平均查找性能不错,为O(logn),但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化,我们可以使用平衡查找树。平衡查找树中的2-3查找树,这种数据结构在插入之后能够进行自平衡操作,从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难,红黑树是2-3树的一种简单高效的实现,他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树,应用非常广泛,很多编程语言的内部实现都或多或少的采用了红黑树。

      除此之外,2-3查找树的另一个扩展——B/B+平衡树,在文件系统和数据库系统中有着广泛的应用。


    6. 分块查找

      分块查找又称索引顺序查找,它是顺序查找的一种改进方法。
      算法思想:将n个数据元素"按块有序"划分为m块(m ≤ n)。每一块中的结点不必有序,但块与块之间必须"按块有序";即第1块中任一元素的关键字都必须小于第2块中任一元素的关键字;而第2块中任一元素又都必须小于第3块中的任一元素,……
      算法流程:
      step1 先选取各块中的最大关键字构成一个索引表;
      step2 查找分两个部分:先对索引表进行二分查找或顺序查找,以确定待查记录在哪一块中;然后,在已确定的块中用顺序法进行查找。


    7. 哈希查找

      什么是哈希表(Hash)?

      我们使用一个下标范围比较大的数组来存储元素。可以设计一个函数(哈希函数, 也叫做散列函数),使得每个元素的关键字都与一个函数值(即数组下标)相对应,于是用这个数组单元来存储这个元素;也可以简单的理解为,按照关键字为每一个元素"分类",然后将这个元素存储在相应"类"所对应的地方。但是,不能够保证每个元素的关键字与函数值是一一对应的,因此极有可能出现对于不同的元素,却计算出了相同的函数值,这样就产生了"冲突",换句话说,就是把不同的元素分在了相同的"类"之中。后面我们将看到一种解决"冲突"的简便做法。
       总的来说,"直接定址"与"解决冲突"是哈希表的两大特点。

      什么是哈希函数?

      哈希函数的规则是:通过某种转换关系,使关键字适度的分散到指定大小的的顺序结构中,越分散,则以后查找的时间复杂度越小,空间复杂度越高。

      算法思想:哈希的思路很简单,如果所有的键都是整数,那么就可以使用一个简单的无序数组来实现:将键作为索引,值即为其对应的值,这样就可以快速访问任意键的值。这是对于简单的键的情况,我们将其扩展到可以处理更加复杂的类型的键。

      算法流程:

      1)用给定的哈希函数构造哈希表;
      2)根据选择的冲突处理方法解决地址冲突;
        常见的解决冲突的方法:拉链法和线性探测法。详细的介绍可以参见: 浅谈算法和数据结构: 十一 哈希表
      3)在哈希表的基础上执行哈希查找。
       哈希表是一个在时间和空间上做出权衡的经典例子。如果没有内存限制,那么可以直接将键作为数组的索引。那么所有的查找时间复杂度为O(1);如果没有时间限制,那么我们可以使用无序数组并进行顺序查找,这样只需要很少的内存。哈希表使用了适度的时间和空间来在这两个极端之间找到了平衡。只需要调整哈希函数算法即可在时间和空间上做出取舍。

      复杂度分析

      单纯论查找复杂度:对于无冲突的Hash表而言,查找复杂度为O(1)(注意,在查找之前我们需要构建相应的Hash表)。

      使用Hash,我们付出了什么?
      我们在实际编程中存储一个大规模的数据,最先想到的存储结构可能就是map,也就是我们常说的KV pair,经常使用Python的博友可能更有这种体会。使用map的好处就是,我们在后续处理数据处理时,可以根据数据的key快速的查找到对应的value值。map的本质就是Hash表,那我们在获取了超高查找效率的基础上,我们付出了什么?

      Hash是一种典型以空间换时间的算法,比如原来一个长度为100的数组,对其查找,只需要遍历且匹配相应记录即可,从空间复杂度上来看,假如数组存储的是byte类型数据,那么该数组占用100byte空间。现在我们采用Hash算法,我们前面说的Hash必须有一个规则,约束键与存储位置的关系,那么就需要一个固定长度的hash表,此时,仍然是100byte的数组,假设我们需要的100byte用来记录键与位置的关系,那么总的空间为200byte,而且用于记录规则的表大小会根据规则,大小可能是不定的。

      Hash算法和其他查找算法的性能对比:

    search method efficient conclusion

    展开全文
  • 数据结构实验报告五 查找

    千次阅读 2020-12-31 13:45:44
    数据结构实验报告:实验五 查找

    一、实验目的

    1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。
    2、掌握线性表中顺序查找和折半查找的方法。
    3、学会哈希函数的构造方法,处理冲突的机制以及哈希表的查找。

    二、实验内容和要求

    1.静态查找表技术

    依据顺序查找算法和折半查找算法的特点,对下面的两个查找表选择一个合适的算法,设计出完整的C源程序。并完成问题:
    查找表1 : { 8 ,15 ,19 ,26 ,33 ,41 ,47 ,52 ,64 ,90 } ,查找key = 41
    查找表2 : {12 ,76 ,29 ,15 ,62 ,35 ,33 ,89 ,48 ,20 } ,查找key =35
    查找key=41的算法:折半查找算法 比较次数:3
    查找key=35的算法:顺序查找算法 比较次数:5

    顺序查找算法算法实现代码
    #include<bits/stdc++.h>
    #define MAX_NUM 100
    using namespace std;
    typedef int KeyType;
    
    typedef struct
    {
        KeyType key;
    }ElemType;
    typedef struct
    {
        ElemType elem[MAX_NUM];
        int length;
    }SSTable;
    int seq_search(SSTable ST,KeyType key)
    {
        int i;
        ST.elem[0].key=key;
        for(i=ST.length;ST.elem[i].key!=key;i--);
        return i;
    }
    int main()
    {
        SSTable ST;
        KeyType tkey;
        int n,i;
        ST.length=0;
        printf("请输入查找表元素个数:");
        scanf("%d",&n);
        printf("\n查找表输入:\n");
        while(n--)
            scanf("%d",&ST.elem[ST.length++].key);
        printf("\n输入查找元素:");
        scanf("%d",&tkey);
        i=seq_search(ST,tkey);
        if(i==0)
            printf("\n未找到此元素\n");
        else
            printf("\n在查找表中下标为%d",ST.length+1-i);
        return 0;
    }
    
    折半查找算法算法实现代码
    #include<bits/stdc++.h>
    #define MAX_NUM 100
    using namespace std;
    typedef int KeyType;
    
    typedef struct
    {
        KeyType key;
    }ElemType;
    typedef struct
    {
        ElemType elem[MAX_NUM];
        int length;
    }SSTable;
    int bin_search(SSTable ST,int key)
    {
        int low,high,mid;
        low=0;
        high=ST.length;
        while(low<=high)
        {
            mid=(low+high)/2;
            if(key==ST.elem[mid].key)
                return mid;
            else
            if(key<ST.elem[mid].key)
                high=mid-1;
            else
                low=mid+1;
        }
        return -1;
    }
    
    int main()
    {
        SSTable ST;
        KeyType tkey;
        int n,i;
        ST.length=0;
        printf("请输入查找表元素个数:");
        scanf("%d",&n);
        printf("\n查找表输入:\n");
        while(n--)
            scanf("%d",&ST.elem[ST.length++].key);
        printf("\n输入查找元素:");
        scanf("%d",&tkey);
        i=bin_search(ST,tkey);
        if(i==-1)
            printf("\n未找到此元素\n");
        else
            printf("\n在查找表中下标为%d",i+1);
        return 0;
    
    }
    

    2、哈希表的构造与查找

    /* 采用开放地址法构造哈希表*/
    #include<stdio.h>
    #include<malloc.h>
    #define MAXSIZE 25
    #define P 13
    #define OK 1
    #define ERROR 0
    #define DUPLICATE -1
    #define TRUE 1
    #define FALSE 0
    typedef struct{  /*哈希表元素结构*/
        int key;  /*关键字值*/
        int flag; /*是否存放元素*/
    }ElemType;
    
    typedef struct {
        ElemType data[MAXSIZE];
        int count;      /*元素个数*/
        int sizeindex;  /*当前哈希表容量*/
    }HashTable;
    
    int d1[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14}; /*线性探测序列*/
    int d2[15]={0,1,-1,2*2,-2*2,3*3,-3*3,4*4,-4*4,5*5,-5*5,6*6,-6*6,7*7,-7*7}; /*二次探测序列*/
    void dataset(int ds[],int *len);
    int InsertHash(HashTable *H,int e,int d[]);
    int CreateHash(HashTable *H,int ds[],int len,int d[]);
    int SearchHash(HashTable *H, int e,int d[]);
    void menu();
    /*输入查找表*/
    void dataset(int ds[],int *len){
        int n,m;
        n=0;
        printf("\n查找表输入:");
        while(scanf("%d",&m)==1){  /*以输入一个非整数作为结束*/
            ds[n]=m;
            n++;
        }
        *len=n;
    }
    /*计算哈希地址,插入哈希表*/
    int InsertHash(HashTable *H,int e,int d[]){
        int k,i=1;
        k=e%P;
        while(H->data[k].flag==TRUE||k<0){
            k=(e%P+d[i])%MAXSIZE;i++;
            if(i>=15)
                return ERROR;
        }
        H->data[k].key=e;
        H->data[k].flag=TRUE;
        H->count++;
        return OK;
    }
    /*构造哈希表*/
    int CreateHash(HashTable *H,int ds[],int len,int d[]){
        int i;
        for(i=0;i<len;i++){
            if(SearchHash(H,ds[i],d)!=-1)
                return DUPLICATE;
            InsertHash(H,ds[i],d);
            if(H->count>=MAXSIZE)
                return ERROR;
        }
        return OK;
    }
    /*初始化哈希表*/
    void InitHash(HashTable *H){
        int i;
        for(i=0;i<MAXSIZE;i++){
            H->data[i].key=0;
            H->data[i].flag=FALSE;
        }
    }
    /*在哈希表中查找*/
    int SearchHash(HashTable *H, int e,int d[]){
        int k,i=1;
        k=e%P;
        while(H->data[k].key!=e){
            k=(e%P+d[i])%MAXSIZE;i++;
            if(i>=15)
                return -1;
        }
        return k;
    }
    /*演示菜单*/
    void menu(){
        int choice;int *p;
        HashTable h;
        h.count=0;h.sizeindex=MAXSIZE;
        int a[MAXSIZE]={0};
        int i,n,e;
        dataset(a,&n);  /*建立查找表*/
        getchar();
        printf("\n");
        do{
            printf("\n----哈希查找演示----\n");
            printf("\n1.线性探测构造哈希表\n");
            printf("\n2.二分探测构造哈希表\n");
            printf("\n3.退出\n");
            printf("\n输入选择:");
            scanf("%d",&choice);
            if(choice==1)
                p=d1;
            else if(choice==2)
                p=d2;
            else
                return;
            InitHash(&h);   /*初始化哈希表*/
            if(!(i=CreateHash(&h,a,n,p))) /*构造哈希表*/
                printf("\n哈希表构造失败!\n");
            else if(i==DUPLICATE)
                printf("\n哈希表具有重复关键字!\n");
            else{
                printf("\n哈希表:\n");
                for(i=0;i<h.sizeindex;i++)
                    printf("%3d",h.data[i].key);
                printf("\n\n哈希查找\n输入要查找的key值:");
                getchar();
                scanf("%d",&e);
                if((i=SearchHash(&h,e,p))==-1)
                    printf("\n%d未找到\n",e);
                else
                    printf("\n%d在哈希表中下标为%d\n",e,i);
            }
            getchar();
        }while(1);
    }
    
    int main(){
        menu();
        return 0;
    }
    

    输入查找表为:19 14 23 1 68 20 84 27 55 11 10 79(注意以输入一个非整数结束)。
    运行结果:
    1)线性探测散列:
    int d1[15]={0,1,2,3,4,5,6,7,8,9,10,11,12,13,14};
    哈希表形态:
    实验五(1)

    84在哈希表中的位置:8
    2)二次探测散列:
    int d2[15]={0,1,-1,22,-22,33,-33,44,-44,55,-55,66,-66,77,-77};
    哈希表形态:
    实验五(2)
    84在哈希表中的位置:5

    展开全文
  • 一、线性结构查找 1、顺序查找 (1)无序的线性查找 基本思想:从线性表的一端开始,逐个检查关键字是否满足给定的条件。特点:当N比较大时,查找效率低。 (2)有序的线性查找:查效率比无序查找略高。 2、折半...
  • 查找,就是根据给定的某个值在一组记录集合确定某个“特定的”数据元素(记录)或者找到属性值符合特定条件的某些记录。 查找表是由同一类型的数据元素(或记录)构成的集合。 关键字:是数据元素(或记录)某个...
  • 各种数据结构的简单特点 1、列表 包括 (1)数组 【1】会在内存开辟一个连续的内存空间 【2】随机访问的效率比链表高。数组只要给定下标,则可以直接定位到该下标所对应的元素,而链表每次都是从头节点开始...
  • C++ 数据结构实战:快速查找

    千次阅读 2019-03-27 17:36:03
    当时我采取的是stl嵌套的数据结构,由于时间复杂度较高,且vector的值是随着map的rehash阶段不断进行内存拷贝的, 在全量计算特征的时候会给性能造成很大的压力,当时与base的性能对比如下: 性能不...
  • 数据结构 - 静态查找

    千次阅读 2015-05-03 09:31:47
    查找主要讨论顺序表、有序表、索引表和... 关键字(Key,码):数据元素某个(或几个)数据项的值,它可以标识一个数据元素。若关键字能唯一标识一个数据元素,则关键字称为主关键字(Primary Key) ;将能标识若干个数
  • 我将主要讲解介绍 查找的相关知识,如查找算法等,希望你们会喜欢。
  • 数据结构与算法】——二分查找

    千次阅读 2022-02-28 09:34:30
    如果数组是排序的(通常按照递增的顺序排序),那么可以采用二分查找进行优化。可以取出位于数组中间的数字并和目标数字比较 如果中间数字正好等于目标数字,那么就找到了目标数字。如果中间数字大于目标数字,那么...
  • 数据结构:七大查找算法

    千次阅读 2018-05-17 21:50:34
    哈希查找 查找是在大量的信息寻找一个特定的信息元素,在计算机应用查找是常用的基本运算,例如编译程序符号表的查找。本文简单概括性的介绍了常见的七种查找算法,说是七种,其实二分查找、插值...
  • 数据结构】分块查找

    千次阅读 2019-04-24 20:39:40
    2.分块查找特点: 索引表为有序表 块内节点可以无序 前一块的的最大值要小于后一块的最小值 3.C++实现: #include<iostream> using namespace std; typedef struct node{ int key; ...
  • 查找表(查找结构)——用于查找数据集合称为查找表,它由同一类型的数据元素(或记录)组成 关键字——数据元素唯一标识该元素的某个数据项的值,使用基于关键字的查找查找结果应该是唯一的。 查找算法的评价...
  • 数据结构——树表的查找(动态查找表)】

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

    万次阅读 多人点赞 2017-08-15 21:06:17
    查找是在大量的信息寻找一个特定的信息元素,在计算机应用查找是常用的基本运算,例如编译程序符号表的查找。本文简单概括性的介绍了常见的七种查找算法,说是七种,其实二分查找、插值查找以及斐波那契查找...
  • 数据结构-查找算法总结

    千次阅读 2017-09-07 18:45:18
    本文将对数据结构中各种查找算法进行总结。
  • 数据结构:八大数据结构分类

    万次阅读 多人点赞 2018-09-05 18:23:28
    数据结构是指相互之间存在着一种或多种关系的数据元素的集合和该集合数据元素之间的关系组成 。 常用的数据结构有:数组,栈,链表,队列,树,图,堆,散列表等,如图所示: 每一种数据结构都有着独特的数据...
  • 数据结构知识整理

    万次阅读 多人点赞 2018-07-30 18:50:47
    1.数据结构:是一门研究非数值计算的程序设计问题计算机的操作对象以及他们之间的关系和操作等的学科。 2.数据结构涵盖的内容: 3.基本概念和术语: 数据:对客观事物的符号表示,在计算机科学是指所有能...
  • 查找过程,往往是依据数据元素的某个数据项进行查找,这个数据项通常是数据的关键字。 关键字:是数据元素某个数据项的值,用以标识一个数据元素。 若关键字能标识唯一的一个数据元素,则称谓主关键字。 若关键字能...
  • 《算法和数据结构》学习路线指引

    万次阅读 多人点赞 2021-07-01 11:16:15
    本文已收录于专栏 《画解数据结构》 饭不食,水不饮,题必须刷 C语言免费动漫教程,和我一起打卡! 《光天化日学C语言》 LeetCode 太难?先看简单题! 《C语言入门100例》 数据结构难?不存在的! 《画解数据结构》 ...
  • 数据结构:八种数据结构大全

    万次阅读 多人点赞 2021-07-29 12:36:10
    数据结构 1.1 数据结构概述 数据结构是计算机存储、组织数据的方式;通常情况下,精心选择的数据结构可以带来更高...集合:数据结构中的元素之间除了“同属一个集合” 的相互关系外,别无其他关系; 2)线性结构 线性
  • 数据结构与算法学习笔记

    万次阅读 多人点赞 2018-09-25 13:55:49
    本文是王争老师的《算法与数据结构之美》的学习笔记,详细内容请看王争的专栏。有不懂的地方指出来,我做修改。 数据结构与算法思维导图 数据结构指的是“一组数据的存储结构”,算法指的是“操作数据的一组...
  • 数据结构是计算机存储、组织数据的方式。一种好的数据结构可以带来更高的运行或者存储效率。数据在内存是呈线性排列的,但是我们可以使用指针等道具,构造出类似“树形”的复杂结构。下面介绍八个常见的数据结构
  • 原 Java常用数据结构特点

    千次阅读 2018-11-19 10:20:40
    Java有几种常用的数据结构,主要分为Collection和map两个主要接口,我们从源码探索一下各个接口,以及接口的实现。 Collection接口 Map接口 梳理清楚逻辑关系我们主要将从、数据结构、存储结构、线程是否...
  • 数据结构特点---队列

    千次阅读 2020-07-23 17:51:29
    队列 一种特殊的线性表,特殊之处在于它只允许在表的前端(front)进行删除操作,在表的后端(rear)进行插入操作,... 对于队列的查找操作,它也需要遍历整个队列来完成基于某些条件的数值查找,时间复杂度也是 O(n)。
  • 数据结构树(Tree)详解

    千次阅读 2021-03-30 13:29:23
    树(tree)树(Tree)的基本...树是由结点或顶点和边组成的(可能是非线性的)且不存在着任何环的一种数据结构。没有结点的树称为空(null或empty)树。一棵非空的树包括一个根结点,还(很可能)有多个附加结点,所有结点构成
  • 数据结构】折半查找及其二叉判定树画法

    万次阅读 多人点赞 2019-09-25 23:55:40
    折半查找又叫二分查找,是数据结构中一种很重要的查找方式。 其特点有以下几个: 只能对有序的顺序表进行查找。 是一种静态查找查找的平均时间复杂度为o(log2n)。 成功平均查找长度ASL约log2(n+1)-1。 ...
  • 文章目录一、实验目的二、算法说明三、算法实现...5、熟练掌握线性链表(单链表)的基本运算:查找、插入、删除等,能在实际应用灵活选择适当的链表结构。 二、算法说明 在本次实验,首先程序自己建立一个空的头结点

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 240,628
精华内容 96,251
关键字:

数据结构中查找的特点

数据结构 订阅