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 条评论
登录 后参与评论

相关文章

来自专栏生信小驿站

pandas基础和应用(1)

pandas提供了三种数据对象,分别是Series,DataFrame和Panel。Series用于保存一维数据,DataFrame用于保存二维的数据,Pane...

572
来自专栏机器学习和数学

[编程经验] Pandas入门(二)

上次介绍了Pandas的部分操作,包括创建Series,DataFrame以及基本索引,文件保存与读取等。今天我们介绍一下Pandas常用的其他功能。 首先我们...

3675
来自专栏mwangblog

python字典(Dictionary)

922
来自专栏余林丰

9.动态规划(2)——子集和问题

注:因为对“子集和问题”的学习不够深入,所以本文在讲解动态规划递推公式中可能存在叙述不清,或者错误的地方,如有发现望能不吝赐教。   子集和问题可描述如下:给定...

2298
来自专栏韦弦的微信小程序

Swift 字符串转整数 (atoi) - LeetCode

1、在找到第一个非空字符之前,需要移除掉字符串中的空格字符。如果第一个非空字符是正号或负号,选取该符号,并将其与后面尽可能多的连续的数字组合起来,这部分字符即为...

803
来自专栏python3

python3--元组(tuple),列表(list),字典dict,其它(for,enumerate,range)

元组被称为只读列表,即数据可以被查询,但不能被修改,所以,字符串的切片操作同样适用于元组

971
来自专栏数据结构与算法

BZOJ4939: [Ynoi2016]掉进兔子洞(莫队 bitset)

那么第$i$个询问的答案为$r1 - l1 + r2 - l2 + r3 - l3 + 3 - min(cnt1[x], cnt2[x], cnt3[x])$

461
来自专栏小樱的经验随笔

C/C++中对链表操作的理解&&实例分析

链表概述    链表是一种常见的重要的数据结构。它是动态地进行存储分配的一种结构。它可以根据需要开辟内存单元。链表有一个“头指针”变量,以head表示,它存放...

3054
来自专栏Python小屋

小议Python列表和元组中的元素地址连续性

众所周知,在Python中字典和集合依赖元素哈希表来存储,并不存在传统意义上的所谓元素“顺序”,当然,如果需要一个有序的字典可以使用collections模块提...

33810
来自专栏前端知识分享

第199天:js---扩充内置对象功能总结

582

扫码关注云+社区