PHP数据结构(十二) ——静态查找表​

PHP数据结构(十二)——静态查找表

(原创内容,转载请注明来源,谢谢)

一、概念

1、查找表:由同一类型数据元素构成的集合。

2、静态查找表:只进行查找(包括确认元素是否存在、查找元素的值),不进行增加和删除操作。

3、动态查找表:与静态查找表相对应,除了查找,还会进行插入与删除操作。

4、关键字:用于标识一个数据元素,如果对应的数据元素唯一,则为主关键字。如果若干个关键字可以唯一确定一个数据元素,称这些关键字为次关键字。

5、查找:给定某个值,在查找表中确定一个关键字等于给定元素的值,如果存在则返回结果,称为查找成功,否则称为查找不成功。

6、平均查找长度:又称ASL,为确定记录在表中的位置,需要和给定值进行比较的关键字个数的期望值。ASL的值为从0至表长度n中,每一个P*C结果的和。P为第i个数字出现的概率,C为当本数字是找到的结果时,前面已经查找的次数。

二、静态查找表

1、顺序表

1)顺序查找

顺序查找的方法是从最后一个元素开始,逐个与关键字进行比较,成功即返回结果,否则查找失败。

可以设定一个集合里面不存在的元素放置在循环的最后一位,当前面都不匹配时,必然匹配最后一位,则不会死循环。该元素作为哨兵,这样避免每次都要判断是否循环结束。

例:在10000个由1-100000的随机数中找一个数(假设存在数组$arr的0-9999下标内,要查找的数是$num)。

$arr[10000] = $num;
for($i=0;!($num== $arr[$i]);$i++);
return $i;

可以从return的值中进行判断,如果是10000,说明在数组中没有找到元素,否则就是数组中有找到元素。

顺序查找在找得到元素的情况下,当每个元素出现概率相同时,ASL=(n+1)/2。再考虑到找不到的情况下,假设找得到和找不到的概率相同,则ASL=(n+1)*3/4。

2)有序表的查找

有序表是顺序表的特殊情况,即表中的元素按从小到大(或从大到小)的顺序进行排列。对于有序表,要查找一个元素就比较方便,可以用折半查找的方式进行。折半查找又称为二分查找,采用二分法的思想进行查找。

即先判断要查找的结果和有序表长度的一半的大小,假设有序表从小到大排列,则如果结果大于中间值,再去有序表的3/4点进行查找,反之去1/4点查找。

例子如下:加上数组[1,3,6,9,11,15,22,23,34,45,51]共11个元素,要查找数字6是否存在,可以先找数组的第6个元素15,发现6<15,再找第3个元素,发现6=6,找到结果。用代码实现方式如下:

<?php
class Search{
         private $arr;
         private $key;
         public function __construct($arr =array(), $key = ''){
                   $this->arr = $arr;
                   $this->key = $key;
         }
         public function __set($name, $val){
                   $this->$name = $val;
         }
         public function getBisearch(){
                   $key = $this->key;
                   $arr = $this->arr;
                   $arrLength  = count($arr);
                   $high = $arrLength-1;
                   $low = 0;
                   while($low <= $high){
                            //如果key和大的数一样返回大的,和小的一样返回小的
                            if($key ==$arr[$high])  return $high;
                            if($key ==$arr[$low])  return $low;
                            //中间值为high和low的一半
                            $mid = ceil(($high -$low) / 2);
                            //大于中间值,则小的数变为中间值加一,小于中间值,则大的数变为中间值减一,等于就返回中间值
                            if($key >$arr[$mid]){
                                     $low = $mid+ 1;
                            }else if($key <$arr[$mid]){
                                     $high =$mid - 1;
                            }else{
                                     return$mid;
                            }
                   }
                   return -1;//在这里表示查找失败
         }
}
$search = newSearch(array(1,3,6,9,11,15,22,23,34,45,51), 6);
echo$search->getBisearch();
有序表的查找,除了折半查找,还有斐波那契查找和插值查找等方法。下面介绍斐波那契查找。斐波那契序列是1,1,2,3,5,8,13…即F(1) = F(2) = 1,F(n) = F(n-1) + F(n-2) (n>2)。用此生成的一系列值,对数组进行查找。最坏情况下斐波那契序列比折半查找慢,但平均性能此方法比较好。
斐波那契查找的代码如下:
         //斐波那契查找
         //1. 构建斐波那契序列 1 1 2 3 5 813...
         private function getFibonacciArray($n){
                   $arrFi = array(1, 1);
                   if($n <= 2){
                            return $arrFi;
                   }
                   $a = 1;
                   $b = 2;
                   //循环,根据最后两个数获取整个斐波那契数列
                   while($b < $n){
                            array_push($arrFi,$b);
                            $tmp = $b;
                            $b = $b + $a;
                            $a = $tmp;
                   }
                   return $arrFi;
         }
         //2. 进行查找
         public function getFibonacciSearch(){
                   $key = $this->key;
                   $arr = $this->arr;
                   $arrLength = count($arr);
                   //用数组的长度去生成斐波那契数列
                   $arrFi =$this->getFibonacciArray($arrLength);
                   $fiLength = count($arrFi);
                   //遍历斐波那契序列数组,以数组的结果作为arr数组的下标去查找
                   //由于arr从小到大排序,因此key一开始可能的结果是大于或者等于$arr[$arrFi[0]]
                   //如果$key<$arr[$arrFi[0]],因为$arrFi[0]=1,则再判断$key和$arr[0]
                   if($key < $arr[$arrFi[0]]){
                            if($key != $arr[0]){
                                     return -1;
                            }else{
                                     return 0;
                            }
                   }
                   for($i = 1; $i <$fiLength; $i++){
                            if($key ==$arr[$arrFi[$i]]){
                                     return$arrFi[$i];
                            }
                            //当key小于arr[$arrFi[$i]],说明key的取值范围在arr[$arrFi[$i-1]]和arr[$arrFi[$i]]之间
                            if($key <$arr[$arrFi[$i]]){
                                     break;
                            }
                   }
                   //根据上一备注,在区间进行查找
                   for($k = $arrFi[$i-1]; $k<= $arrFi[$i]; $k++){
                            if($key ==$arr[$k]){
                                     return $k;
                            }                          
                   }
                   if($k > $arrFi[$i]){
                            return -1;
                   }
         }

2、静态树表查找

顺序表考虑的是每个元素是等概率的。当每个元素不等概率时,生成静态最优查找树进行查找的效率更高。

静态最优查找树是一棵二叉树,根节点表示权值最大的下标,两个叶子节点表示权值次大的两个下标,以此类推。这样,权值大的表示概率比较大,会优先被查找到。该方法类似赫夫曼树编码。

由于静态最优查找树较为复杂,可以构造静态次优查找树进行分析。构造方式如下:

1)挑选一个节点i,令0..i的权值和与i..n的全职和最接近。

2)再在0..i和i..n分别查找出相应的i‘同样满足上述要求。

3)修正:当选定一个i时,发现i-1或者i+1的权值远大于i,则相应的改为i-1或i+1。

3、索引顺序表查找

索引顺序表是改进版的顺序表,即将一个大块的数组,转换成若干小数组,令每一块数组的最大值小于下一块树组的最小值,在块的内部没有顺序。另外有一个数组,记录每一块的最大值及其起始位置,且从小到大排序。

——written by linhxx 2017.07.14

相关阅读:

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(2)

PHP数据结构(十一) ——图的连通性问题与最小生成树算法(1)

PHP数据结构(十) ——有向无环图与拓扑算法

PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-14

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏决胜机器学习

从机器学习学python(二) ——iteritems、itemgetter、sorted、sort

从机器学习学python(二)——iteritems、itemgetter、sorted、sort (原创内容,转载请注明来源,谢谢) 一、iteritems...

3527
来自专栏Java编程

Java泛型详解

Java泛型(generics)是JDK 5中引入的一个新特性,允许在定义类和接口的时候使用类型参数(type parameter)。声明的类型参数在使用时用具...

6250
来自专栏有趣的django

5.python函数

函数介绍 定义:  函数是指将一组语句的集合通过一个名字(函数名)封装起来,要想执行这个函数,只需调用其函数名即可。 特性:减少重复代码、使程序变的可扩展、使程...

2546
来自专栏我爱编程

Day5函数式编程1/3

高阶函数 map map()函数接收两个参数,一个是函数,一个是Iterable,map将传入的函数依次作用到序列的每个元素,并把结果作为新的Iterator返...

2748
来自专栏python学习指南

Scala入门学习笔记四--List使用

前言 本篇将介绍一个和Array很相似的集合List,更多内容请参考:Scala教程 本篇知识点概括 List的构造 List与Array的区别 Lis...

1877
来自专栏Deep learning进阶路

Python随记(一)列表和元组

Python随记(一)列表和元组 Python中最基本的数据结构就是序列了。Python一共包含6种内建序列:列表、元组、字符串、Unicode字符串、xra...

1720
来自专栏编程理解

排序算法(七):快速排序

快速排序是通过分治的方式,根据选定元素将待排序集合拆分为两个值域的子集合,并对子集合递归拆分,当拆分后的每个子集合中元素个数为一时,自然就是有序状态。

463
来自专栏我的博客

正则表达式–应用篇

匹配年月日(常见三种格式2012-12-12、2012/12/12、2012年12月12日) <?php //匹配格式如:2012年12月12日 $mode...

2453
来自专栏技术小黑屋

Kotlin中常量的探究

在我们尝试使用Kotlin作为开发语言的时候,应该会想到在Kotlin中如何定义一个常量,就像Java中这样的代码一样

545
来自专栏wym

HDU 6109 数据分割(并查集+set维护)

 题目:http://acm.hdu.edu.cn/showproblem.php?pid=6109

511

扫描关注云+社区