文档章节

J2SE_7_数据结构与算法(5)之查找

朱门中人
 朱门中人
发布于 2016/04/27 15:49
字数 1019
阅读 6
收藏 0

       上篇博文我重点介绍了八大内部排序,这篇博文(数据结构与算法的最后一课)重点介绍查找,我们依旧沿用上篇博文的风格,先简单介绍,再以例子重点讲解。

       下面我们开始今天的旅行,首先祝你旅行愉快,呵呵。

                                            

 

静态查找

 

        若查找目的是为了查询某个特定的数据是否在表中检索某个特定数据的各种属性,则此类查找表为静态查找表。

 

 

1、顺序查找

 

基本原理:从表一端开始逐个和关键字进行比较,若找到一个记录和给定值相等,则查找成功,反之失败。再简单点就是,一个一个的比大小,看看是否相等。

 

例子:

         

 

顺序查找更适合于顺序存储结构和链式存储结构的查找表。顺序查找需要一个个的去比较,效率很低

 

2、折半查找(二分查找)

 

基本原理:1.把序列分成左中右三部分,左部分小于中间值,右部分大于中间值;

                  2.把给定值与中间值比较,确定下次查找是在左部分还是右部分;

                  3.继续上面两步操作,直到成功或失败。

 

注意:折半查找需要注意给定的序列必须是一个有序序列。

 

例子:

                      

3、分块查找

 

基本原理:顺序查找和二分法查找的折中,先分块(可能不止两块),在块中顺序查找

 

注意:分成的各块内部数据可能无序;各块之间有序(第二个块中的元素都比第一个块中元素都大);建立了索引表,索引表按关键字有序。

 

例子:

                   

 

静态查找表方法的性能分析

 

 

                  

     

        对于动态查找的插入和删除不是特别好讲,我们就不在这里讲了,只是简单的介绍一下什么是二叉排序树和平衡二叉树,B_树只做了解。

 

动态查找

       

若再查找的过程中同时插入查找表中不存在的数据,或从查找表中删除已存在的某个数据,则称此类查找表为动态查找表。

 

1、二叉排序树(左节点<根节点<右节点

 

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

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

           3.左右子树本身就是两棵二叉排序树。

例子:

                              

       定义看上去不是特别好理解,其实特别简单,我们再以例子简单的说一下。左子树的所有节点:3,1,6,4,7,都小于父节点8,右子树所有节点:10,14,13,都大于父节点。什么时候都是父节点大于左孩子,小于右孩子例如:8>3,8<10;3>1,3<6。

 

2、平衡二叉树(所有左节点和右节点层数/深度相差不超过1)

 

定义:1.它或者是一棵空树

           2.或者树中任一结点的左右子树深度相差不超过1。

注意:从定义我们可得到:想要一颗树平衡,有三种情况,节点的平衡度要么为了0,要么为1,要么为-1。(平衡度:节点左子树的高度减去其右子树的高度。)

例子:

                      

上面图在每个节点上标出了平衡度,所有的节点的平衡度的绝对值都小于等于0或1,所以它是一棵平衡二叉树。

 

总结

 

          数据结构和算法的内容到今天(5月16日)就算结束了(祝旅行愉快),由于距离考试很近了,我们后面的博文就开始介绍软考的大题部分的内容,近期就会推出,敬请期待。

本文转载自:http://blog.csdn.net/jiuqiyuliang/article/details/24405965

朱门中人
粉丝 3
博文 47
码字总数 310
作品 0
南京
程序员
私信 提问
一文掌握关于Java数据结构所有知识点(欢迎一起完善)

在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系...

snailclimb
2018/05/08
0
0
算法和编程面试题精选TOP50!(附代码+解题思路+答案)

作者 | javinpaul 编译 | 王天宇、Jane 整理 | Jane 出品 | AI科技大本营 【导读】之前我们给同学们推荐了很多关于 Python 的面试资源,大家都表示很有用。这次营长表示要翻 Java 的牌子啦~...

AI科技大本营
2018/09/27
0
0
算法和编程面试题精选 TOP50!(附代码+解题思路+答案)

作者 | javinpaul 出品 | AI科技大本营 数组 数组,将元素存储到内存的连续位置中,是最基本的数据结构。在任何和编程相关的面试中,都会被问到和数组相关的问题,可以说是非常热门的考题之一...

CSDN资讯
2018/10/02
0
0
JAVA数据结构的个人见解之绪论

JAVA数据结构的个人见解之绪论 概念 一般来说用计算机解决问题总是围绕以下三个主要步骤: (1) 抽象出所求解问题中需要处理的数据对象的逻辑模型。(逻辑结构) (2) 根据所求解问题需要完...

狂奔啦蜗牛
2012/08/23
92
0
《数据结构与算法系列》合集整理

《数据结构与算法系列》合集整理 整理来自博客园skywang12345,以下摘自作者介绍: “最近抽空整理了"数据结构和算法"的相关文章。在整理过程中,对于每种数据结构和算法分别给出"C"、"C++"...

kaixin_code
2018/12/01
178
0

没有更多内容

加载失败,请刷新页面

加载更多

CSS3

一.复杂选择器 1.兄弟选择器 具备相同父级元素的平级元素之间称为兄弟元素 注意:兄弟选择器,只能往后,不能往前找 (1).相邻兄弟选择器,获取紧紧挨着某元素后面的兄弟元素 选择器1+选择器2...

wytao1995
19分钟前
3
0
Jmeter录制

1. 加HTTP(s) Test Script Recorder 2. 在 recorder下面加reocrding controller 3. 在HTTP(s) Test Script Recorder中设置下面几项 4. browser设置proxy, 注意端口要和step3中jmeter中的一致......

Rebecca_Hu
24分钟前
3
0
DIV+CSS忽悠前端小白

在大约两年前,DIV+CSS是一对很诱人的组合,会用DIV+CSS制作网页的人,常常会被人赞以大拇指的,记得06年初的时候,我用 div+css布局的一个纯静态网站还拿了学校网页设计比赛的一个奖。 今天...

前端老手
27分钟前
4
0
Win10子系统 linux(Ubuntu18.04) 安装Docker

1)原文件备份 sudo cp /etc/apt/sources.list /etc/apt/sources.list.bak 2)编辑源列表文件 sudo vim /etc/apt/sources.list 3)将原来的列表删除,添加如下内容(中科大镜像源) deb http...

jxldjsn
29分钟前
3
0
Ubuntu16.04安装Qt5.12.2

Ubuntu16.04安装Qt5.12.2 第一步:下载文件 https://download.qt.io/official_releases/qt/5.12/5.12.2/ 第二步:安装依赖库 sudo apt-get install build-essential sudo apt-get install li......

shzwork
35分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部