文档章节

线性表查找

zhaoWSW
 zhaoWSW
发布于 2017/08/31 17:22
字数 1044
阅读 2
收藏 0

0.前言

    查找也就是通常意义上的检索。指的是在给定某种条件的情况下,寻找满足的元素。被查找的对象我们可以简单的称之为元素,但不局限与数字,字符串,文件,对象等。查找运算的主要运算是关键字的比较,随意通常把查找过程中关键字的比较次数作为衡量一个算法效率优劣的标准,即,平均查找长度ASL:

    

    注:pi:查找第i个元素的概率,通常为1/n(1<=i<=n),ci:查找到第i个元素所需要

1.顺序查找

    顺序查找是一种最简单的查找方式,需要从表的一端开始进行比较,知道找到满足要求条件的元素为止。

    FOR seqList FROM 1 TO n

        IF Judge(seqList.get(i))

            RETUREN i

        ELSE

            CONTINUE

    

2.折半查找

    折半查找,又称二分查找,是一种效率比较高的查找方式,但是折半查找必须要求线性表是一个有序表,表中的元素按照关键的元素标志是有序的。在每一次的查找匹配值中,我们的根据当前区间的中间值与目标元素的比较,排除1/2的区间元素,同时获得1/2的目标元素。

    WHILE (low <= high)

        mid =  (low + high) / 2

        IFJudge(seqList.get(mid))

            RETURN mid

        IF JudgeUp(seqList.get(mid))

            low = mid +1

        ELSE

            high = mid -1

       对于折半查找,我们的我一使用二叉树来进行的图形化的展示。对于二叉树,内部节点的个数:

,树的高度的为 ,第i层的元素个数为 ,查找该层上每个元素需要进行比较的次数为i次。因此,得到如下的ASL:

        

        上述公式使用等差数列*等比数列元素求和的公式求得。

        

3.索引存储

    索引存储结构实在存储数据的同时,建立附加的索引表。一般的形式是:

        (关键字,地址)

    每一次的增删改都只是需要维护一下索引的结构就行,但是关键点在于,每一次对元素进行改变,都需要对索引进行维护,这样就增加的一定的开销。他的平均查找长度ASL主要根据索引本身的结构的来进行评判。

4.分块存储

    分块查找也就是我们经常说的索引顺序查找,是一种介于顺序查找和这般查找之间的查找方式。规定使用索引的方式的来存储线性表,将表R[0..n-1]平均分成b块,前面b-1块的元素个数为s=up[n/b],最后一块的元素个数小于等于s。每一块中的元素不一定必须有序,但是前面一块的最大元素一定要小于后一块元素的最小值(大小等标准),即分块有序。抽取各块的最大关键字(元素)以及起始关键字构成一个索引表idx[0..b-1],也就是说idx[i](0<=x<=b-1)存放着第i块的最大关键字以及在表R中的位置索引。由于是分块有序的,因此idx索引表是一个有序的递增的表。

    由此我们可以得出:

    1)二分查找方法+顺序查找

        

        注:b=up[n/s]

    分析 : 当s越小的时候,ASL的值越小,整体上是一个递增的关于s的函数,当n(100)取一定值得时候:

    

    2)顺序查找+顺序查找

      

        注:b=up[n/s]

        分析:当s=sqrt(n)的时候,ASL_ees取得极小值sqrt(n)+1,所以当采用顺序查找+顺序查找的时候,块中各元素选定为sqrt(n)的时候,是最佳的。

        

5.总结

    线性表的查找对于后面学习的树表的查找是非常重要的,只有对它进行深刻的思考,并且理解其中的不同查找的影响因素,才能够在一定程度上设计出符合实际需求的查找数据结构。

© 著作权归作者所有

zhaoWSW
粉丝 0
博文 2
码字总数 2128
作品 0
绵阳
私信 提问
数据结构------线性表 day 001

一:线性表的定义: 线性表是具有相同属性的数据元素的一个有限数列。 二:顺序线性表的具体操作: (1)定义线性表: 1 struct list{2 ElemTpye list; /存线性表的指针,其中ElemTpye为通用...

青柠萌萌哒
2018/09/18
0
0
C语言 数据结构与算法 线性表

数据结构中逻辑结构分线性和非线性。 线性表即为线性结构中的一种。 线性表的特性 百度百科解释在此。 个人总结为 有始有终,顺序排列,首尾不相连(像火车一样)。 线性表的基本操作如下: ...

起什么name呢
2016/03/23
58
0
顺序查找(Sequential Search)

1、定义 顺序查找又叫线性查找,是最基本的查找技术。 2、基本思想  从表的一端开始(第一个或最后一个记录),顺序扫描线性表,依次将扫描到的结点关键宇和给定值K相比较。若当前扫描到的结...

野渡书生
2016/04/28
49
0
《数据结构》笔记三:线性表之顺序存储结构

前言: 关于源码的几个说明: 编码工具:Xcode 语言:C语言 参考书:《大话数据结构》 为了方便不熟悉的小伙伴们,文中关于代码的部分给出了详细的步骤,只要按照步骤,都可以实现。 另:小编...

小曼blog
06/28
0
0
数据结构笔记1---链表与顺序表

导读 1.单链表(创建,插入,删除,查找(2),判空) 2.数组线性表(创建,插入,删除,查找,判空,判满) 3.循环链表(创建,插入,删除,判空) 4.运用数组线性表的串的替换暴力算法 单链...

qq_37527943
2017/11/27
0
0

没有更多内容

加载失败,请刷新页面

加载更多

EDI 电子数据交换全解指南

EDI(Electronic Data Interchange,电子数据交换)技术使得企业与企业(B2B)实现通信自动化,帮助交易伙伴和组织更快更好地完成更多工作,并消除了人工操作带来的错误。从零售商到制造商、物...

EDI知行软件
57分钟前
2
0
CentOS7的LVM动态扩容

# 问题 CentOS7上面的磁盘空间有点紧张,需要扩容。 解决 查询当前磁盘状态 [root@xxx ~]# lsblkNAME MAJ:MIN RM SIZE RO TYPE MOUNTPOINTfd0 2:0 1 4K ...

亚林瓜子
今天
3
0
Kafka 0.8 Producer (0.9以前版本适用)

Kafka旧版本producer由scala编写,0.9以后已经废除 示例代码如下: import kafka.producer.KeyedMessage;import kafka.javaapi.producer.Producer;import kafka.producer.ProducerConfig;......

实时计算
今天
4
0
Giraph源码分析(八)—— 统计每个SuperStep中参与计算的顶点数目

作者|白松 目的:科研中,需要分析在每次迭代过程中参与计算的顶点数目,来进一步优化系统。比如,在SSSP的compute()方法最后一行,都会把当前顶点voteToHalt,即变为InActive状态。所以每次...

数澜科技
今天
6
0
Navicat 快捷键

操作 结果 ctrl+q 打开查询窗口 ctrl+/ 注释sql语句 ctrl+shift +/ 解除注释 ctrl+r 运行查询窗口的sql语句 ctrl+shift+r 只运行选中的sql语句 F6 打开一个mysql命令行窗口 ctrl+l 删除一行 ...

低至一折起
今天
13
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部