只进行查找的称为静态查找表;
在查找的过程中同时插入查找表中不存在的数据元素,或者从查找表中删除已经存在的元素,称为动态查找表。
静态查找:
1.顺序查找:
算法思想:从表中最后一个记录开始,逐个进行记录的关键字和给定值的比较,若某个记录的关键字和给定值比较相等,则查
找成功,找到所查记录;反之,若直至第一个记录,其关键字和给定值比较都不等,则表明表中没有所查记录,查找不成功
平均查找长度:(n+1)/2
2、二分查找(有序表):
算法思想:先确定待查记录所在的范围(区间),然后逐步缩小范围直到找到或找不到该记录为止。
平均查找长度:(n+1)/n *log2(n+1) -1
3、分块查找(索引顺序查找):
算法思想:首先将一个线性表(即主表)按照一定的函数关系和条件划分为若干个逻辑字表,为每个字表建立一个索引项,由
所有的字表的索引项构成一个索引表。当进行分块查找时,先根据所给的关键字查找索引表,从中找出给定k值小于或等于索引
值的那个索引块,找到待查块,然后在主表中查找该快,查找待查的记录。
平均查找长度:索引表是有序的,所以在索引表中可以用顺序查找,也可以用折半查找;而块内的记录的随机排序的,所以在
块中用顺序查找。
顺序查找确定块:平均查找长度为1/2 *(n/s +s)+1
二分查找确定块:平均查找长度为log2(n/s +1)+s/2
动态查找:(表结构动态生成)
http://www.doc88.com/p-930477746758.html
1、二叉排序树查找
二叉排序树(二叉搜索树、二叉查找树):二叉排序树中序遍历得到的必定是一个有序序列。
查找过程:
(1)若查找树为空,查找失败;
(2)若查找树非空,将给定值和查找树的根节点比较:
若相等,查找成功,结束查找过程;
若给定值小于根节点,查找将在根节点的左子树上继续进行,转至(1)
若给定值大于根节点,查找将在根节点的右字树上继续进行,转至(1)
时间复杂度:平均O(logn),最坏O(n)
二叉排序树的插入:
新插入的结点一定是一个新添加的叶子节点,并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。
二叉排序树的结点删除:
假设在二叉排序树上被删结点为p,其双亲结点为f,且p为f的左孩子,下面分三种情况讨论:
(1)若p结点为叶子节点,即pl和pr均为空树,由于删去叶子节点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。
(2)若p结点只有左子树pl或者只有右子树pr,此时只要令pl和pr直接成为其双亲结点f的左子树即可。
(3)若p结点的左子树和右子树均不空。
2、二叉平衡树
左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1.若将二叉树上结点的平衡因子定义为该节点
的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只能是-1,1,0.平衡树查找的时间复杂度为O()l
ogn
- 浏览: 5041569 次
- 性别:
- 来自: 南京
文章分类
- 全部博客 (2844)
- java (1094)
- hadoop (37)
- jvm (39)
- hbase (11)
- sql (25)
- 异常 (83)
- div css (6)
- 数据库 (95)
- 有趣的code (15)
- struts2 (6)
- spring (124)
- js (44)
- 算法 (65)
- linux (36)
- hibernate (7)
- 中间件 (78)
- 设计模式 (2)
- 架构 (275)
- 操作系统 (91)
- maven (35)
- tapestry (1)
- mybatis (9)
- MQ (101)
- zookeeper (18)
- 搜索引擎,爬虫 (208)
- 分布式计算 (45)
- c# (7)
- 抓包 (28)
- 开源框架 (45)
- 虚拟化 (12)
- mongodb (15)
- 计算机网络 (2)
- 缓存 (97)
- memcached (6)
- 分布式存储 (13)
- scala (5)
- 分词器 (24)
- spark (104)
- 工具 (23)
- netty (5)
- Mahout (6)
- neo4j (6)
- dubbo (36)
- canal (3)
- Hive (10)
- Vert.x (3)
- docker (115)
- 分布式追踪 (2)
- spring boot (5)
- 微服务 (56)
- 淘客 (5)
- mesos (67)
- php (3)
- etcd (2)
- jenkins (4)
- nginx (7)
- 区块链 (1)
- Kubernetes (92)
- 驾照 (1)
- 深度学习 (15)
- JGroups (1)
- 安全 (5)
- 测试 (16)
- 股票 (1)
- Android (2)
- 房产 (1)
- 运维 (6)
- 网关 (3)
最新评论
-
明兜3号:
部署落地+业务迁移 玩转k8s进阶与企业级实践技能(又名:Ku ...
Kubernetes系统常见运维技巧 -
q328965539:
牛掰啊 资料收集的很全面
HDFS小文件处理解决方案总结+facebook(HayStack) + 淘宝(TFS) -
guichou:
fluent挂载了/var/lib/kubelet/pods目 ...
kubernetes上部署Fluentd+Elasticsearch+kibana日志收集系统 -
xu982604405:
System.setProperty("java.r ...
jmx rmi 穿越防火墙问题及jmxmp的替代方案 -
大漠小帆:
麻烦问下,“获取每个Item相似性最高的前N个Item”,这个 ...
协同过滤推荐算法在MapReduce与Spark上实现对比
发表评论
-
Kryo 使用指南
2017-12-05 20:14 20361、Kryo 的简介 Kryo 是一个快速序列化/ ... -
spring session序列化问题排查
2017-12-01 19:07 6279严重: Servlet.service() for ser ... -
利用junit对springMVC的Controller进行测试
2017-11-30 16:26 1451平时对junit测试service/D ... -
Java内存模型之重排序
2017-11-29 09:44 867在执行程序时,为了提供性能,处理器和编译器常常会对指令进行重 ... -
pmd spotbugs 文档
2017-11-28 10:02 0https://pmd.github.io/pmd/pmd ... -
PMD、FindBug、checkstyle、sonar这些代码检查工具的区别?各自的侧重点是什么?
2017-11-28 10:01 2149可以说都是代码静态分析工具,但侧重点不同。pmd:基于源代码 ... -
阿里巴巴Java代码规约插件p3c-pmd使用指南与实现解析
2017-11-23 17:09 1608阿里巴巴Java代码规约插件安装 阿里Java代码规 ... -
静态分析工具PMD使用说明 (文章来源: Java Eye)
2017-11-23 17:07 1147质量是衡量一个软件是否成功的关键要素。而对于商业软件系统,尤 ... -
MyBatis 使用 MyCat 实现多租户的一种简单思路
2017-11-20 18:27 2850本文的多租户是基于多数据库进行实现的,数据是通过不同数据库进 ... -
Spring+MyBatis实现数据库读写分离方案
2017-11-20 17:15 1094百度关键词:spring mybatis 多数据源 读写分离 ... -
数据库连接池druid wallfilter配置
2017-11-20 11:38 1348使用缺省配置的WallFilter <be ... -
java restful 实体封装
2017-11-16 09:47 1602package com.mogoroom.bs.commo ... -
dak
2017-11-15 11:21 0package zzm; import jodd.ht ... -
Java内存模型之从JMM角度分析DCL
2017-11-15 09:35 645DCL,即Double Check Lock,中卫双重检查锁 ... -
Java 打印堆栈的几种方法
2017-11-14 09:36 4760java 中可以通过 eclipse 等工具直接打印堆栈, ... -
Servlet Session学习
2017-11-10 09:25 557HTTP 是一种"无状 ... -
浅析Cookie中的Path与domain
2017-11-10 09:26 1064Path – 路径。指定与co ... -
入分析volatile的实现原理
2017-11-08 09:47 690通过前面一章我们了解了synchronized是一个重量级的 ... -
Spring MVC-ContextLoaderListener和DispatcherServlet
2017-11-15 09:35 690Tomcat或Jetty作为Servlet ... -
搭建spring框架的时候,web.xml中的spring相关配置,可以不用配置ContextLoaderListener(即只配DispatcherServl
2017-11-07 18:27 1439搭建spring框架的时候,web.xml中的sprin ...
相关推荐
在众多的搜索算法中,折半查找算法因其简单高效而被广泛应用。然而,随着数据量的不断增长,传统折半查找算法的性能在某些场合下已不能完全满足需求。本文将针对这一问题,探讨折半查找算法的改进方法,并给出相应的...
二分查找算法 二分查找算法是一种高效的查找算法,适用于已经排好序的数组或链表中查找特定的元素。该算法的时间复杂度为O(log n),远远优于顺序查找算法的O(n)。 二分查找算法的基本思想是将数组或链表分成两个...
本实验主要探讨了三种基本的查找算法:顺序查找、折半查找(二分查找)和索引查找,这些算法都是在数组或集合中寻找特定元素的重要方法。下面将详细解释这三种查找算法,并结合C语言编程环境进行深入分析。 1. **...
查找算法集 查找算法是计算机科学中的一种基本算法,用于在数组或链表中搜索指定的元素。以下是四种常见的查找算法:顺序查找、二分查找、插值查找和动态查找。 顺序查找 顺序查找是一种最简单的查找算法,它的...
折半查找算法在顺序表中插入一个元素讲解 折半查找算法是一种常用的查找算法,它可以在已经排好序的顺序表中快速地找到某个元素。下面我们来详细讲解折半查找算法在顺序表中插入一个元素的过程。 折半查找算法的...
在IT领域,查找算法是计算机科学中的核心概念,特别是在数据结构和算法设计中。本文将深入探讨《C++查找算法大集锦》中所涵盖的各种查找技术,包括差值查找法、斐波那契查找、哈希查找(拉链法与探测法)以及顺序和...
在计算机科学中,查找算法是数据结构和算法领域中的核心概念,用于在数据集合中寻找特定元素。这里我们将深入探讨两种常见的查找算法:二分查找和顺序查找。 **一、顺序查找** 顺序查找是最基础的查找算法之一。它...
查找算法是计算机科学中的一种基本操作,它涉及在数据集合中定位特定元素的过程,这一过程又称为检索。在不同数据结构上实现查找算法会有不同的方法和性能表现。查找算法通常根据数据的存储方式和查找方法进行分类,...
查找算法和排序算法小结 本文总结了常见的查找算法和排序算法,包括顺序查找、二分查找、选择排序、冒泡排序、二分排序、插入排序、希尔排序、堆排序、归并排序等。 一、查找算法 1. 顺序查找(Sequential Search...
查找算法的比较 在计算机科学中,查找算法是一种基本且常用的算法,它们的应用非常广泛。本文将对几种常用的查找算法进行比较,包括顺序查找、二分查找、二叉树查找和哈希表查找。 顺序查找是一个最简单的查找算法...
这篇实验报告,来源于云南大学数据结构课程的第七次实践,聚焦于查找算法的理论和实现,特别是哈希表这一高效的数据结构。哈希表,也称为散列表,是一种能够实现快速查找的结构,它通过哈希函数将数据映射到一个固定...
在数据结构的学习和应用中,查找算法是基本而重要的组成部分。本文将深入探讨C语言中几种常见的查找算法,帮助理解它们的原理、特点及应用场景。 一、静态查找 在数据结构中,静态查找主要是针对已经排序的数据...
数据结构中的查找算法是计算机科学中的重要组成部分,它涉及到如何高效地在大量数据中寻找特定信息。查找操作,也就是检索,通常在数据元素的集合,即查找表中进行。查找的效率与查找对象的组织方式和所采用的查找...
在IT领域,尤其是在编程中,理解并掌握不同的查找算法是至关重要的。本文将详细解析C#中的基础查找算法,包括静态查找与动态查找、内查找与外查找,以及两种具体的查找算法:顺序查找(线性查找)和二叉查找(折半...
在计算机科学领域,排序和查找算法是核心概念,它们直接影响程序的效率和性能。排序算法是用来组织数据,使其按照特定顺序排列的算法,而查找算法则是在这些有序或无序数据中寻找特定元素的方法。本篇文章将深入探讨...
综合查找算法课程设计报告书旨在通过实践加深对各种查找算法的理解和应用,这些算法在软件和硬件设计领域中起着至关重要的作用。本项目利用Java编程语言,借助Eclipse开发环境,实现了一个用户友好的图形界面,允许...
文件名中的"Sun数据结构第8章查找(第22-25讲).ppt"和"Sun数据结构第9章排序(第25-27讲).ppt"表明,内容可能详细涵盖了查找算法的各个方面,包括二分查找的原理、实现和优化,以及排序算法的介绍、实现步骤和性能...
各类查找算法的比较(数据结构课程设计) 开始的时候提示输入一组数据。并存入一维数组中,接下来调用一系列查找算法对其进行处理。顺序查找只是从头到尾进行遍历。二分查找则是先对数据进行排序,然后利用三个标志...
二分查找算法是一种高效的数据搜索方法,尤其适用于有序数组或集合。它的基本思想是通过将查找区间不断减半,快速定位目标元素的位置。在每一步中,算法都会比较中间元素与目标值,根据比较结果缩小查找范围。若目标...
分块查找算法是一种在大规模数据集合中提高查找效率的策略,它是对传统顺序查找方法的优化。在传统的顺序查找中,我们需要线性遍历整个数据序列来查找目标元素,这在数据量大时效率较低。分块查找通过将数据划分为较...