php代码
/**
* 数据链表节点
* /
class skipListNode
{
public $d = null;
public $mem = null;
public $pre = null;
public $level = 0;
public $levelNode = array();
}
/**
* 层链表节点
* /
class skipListLevelNode
{
public $node = null;
public $next = null;
public $cur_level = 0;
public $next_step = 0;
}
/**
* 跳跃表
*/
class skipList
{
private $max_level = 1;
private $head = null;
private $hash_table = array();
public function __construct($max_level = 10)
{
$this->max_level = (int)$max_level;
$skipListNode = new skipListNode();
$skipListNode->level = $max_level;
for ($i=0; $i < $this->max_level; $i++) {
$skipListLevelNode = new skipListLevelNode();
$skipListLevelNode->cur_level = $i;
$skipListLevelNode->node = $skipListNode;
$skipListNode->levelNode[] = $skipListLevelNode;
}
$this->head = $skipListNode;
}
public function add(string $mem, $d)
{
$mem = strval($mem);
$d = floatval($d);
if (!$this->update($mem, $d)) {
# 新加
$listNode = $this->getNodePos($d);
$nextNode = isset($listNode->levelNode[0]->next) ? $listNode->levelNode[0]->next->node : null;
$skipListNode = new skipListNode();
$skipListNode->pre = $listNode;
$skipListNode->mem = $mem;
$skipListNode->d = $d;
$skipListNode->level = $this->node_level();
if ($nextNode) $nextNode->pre = $skipListNode;
$pre_next_step = $next_step = 1;
for ($i=0; $i < $this->max_level; $i++) {
while ($i >= $listNode->level && $listNode->pre!==null) {
$listNode = $listNode->pre;
$pre_next_step++;
}
if (empty($listNode)) {
break;
}
if (!empty($nextNode) && $i >= $nextNode->level) {
$nextNode = isset($nextNode->levelNode[0]->next) ? $nextNode->levelNode[0]->next->node : null;
if ($nextNode) $next_step++;
}
if ($i < $skipListNode->level) {
$skipListLevelNode = new skipListLevelNode();
$skipListLevelNode->node = $skipListNode;
$skipListLevelNode->cur_level = $i;
$skipListLevelNode->next = null;
$skipListLevelNode->next_step = $next_step;
if ($nextNode && isset($nextNode->levelNode[$i]) && !empty($nextNode->levelNode[$i])) {
$skipListLevelNode->next = $nextNode->levelNode[$i];
}
$skipListNode->levelNode[] = $skipListLevelNode;
$listNode->levelNode[$i]->next = $skipListLevelNode;
$listNode->levelNode[$i]->next_step = $pre_next_step;
}else{
$listNode->levelNode[$i]->next_step++ ;
}
}
$this->hash_table[$mem] = $skipListNode;
}
return true;
}
public function update(string $mem, $d)
{
$mem = strval($mem);
$d = floatval($d);
$node = $this->getNodePosByMem($mem);
if ($node) {
if ($node->d === $d) {
return true;
}
if ($this->del($mem)) {
$this->add($mem, $d);
return true;
}
return false;
}
return false;
}
public function del(string $mem)
{
$mem = strval($mem);
$node = $this->getNodePosByMem($mem);
if ($node) {
$preNode = $node->pre;
if (isset($node->levelNode[0]->next->node)) {
$node->levelNode[0]->next->node->pre = $preNode;
}
for ($i=0; $i < $this->max_level; $i++) {
while($i >= $preNode->level && $preNode->pre!==null) {
$preNode = $preNode->pre;
}
if ($preNode->levelNode[$i]->next === null) {
continue;
}
if ($i < $node->level) {
$preNode->levelNode[$i]->next = $node->levelNode[$i]->next;
$preNode->levelNode[$i]->next_step += $node->levelNode[$i]->next_step;
$node->levelNode[$i] = null;
}
$preNode->levelNode[$i]->next_step--;
}
$node = null;
$this->delNodePosByMem($mem);
return true;
}
return false;
}
public function getByScore($s)
{
$s = intval($s);
$node = $this->head;
for ($i=$this->max_level-1; $i >= 0 && $s>0; $i--) {
if (!isset($node->levelNode[$i]) || empty($node->levelNode[$i]->next) || $node->levelNode[$i]->next_step > $s) {
continue;
}
do {
if ($node->levelNode[$i]->next_step === $s) {
$s=0;
}else{
$s -= $node->levelNode[$i]->next_step;
}
$node = $node->levelNode[$i]->next->node;
if ($s<=0) break;
} while (isset($node->levelNode[$i]->next->node) && $node->levelNode[$i]->next->node && $node->levelNode[$i]->next_step <= $s);
}
return isset($node->mem) && $s<=0 ? $node->mem : null;
}
public function getRank($s, $e)
{
$s = intval($s);
$e = intval($e);
$ret = array();
if ($s > $e || $s <1 ) {
return $ret;
}
$node = $this->head;
$step = 0;
for ($i=$this->max_level; $i >= 0; $i--) {
while(isset($node->levelNode[$i]->next) && $node->levelNode[$i]->next && ($step + $node->levelNode[$i]->next_step) <= $s) {
$step += $node->levelNode[$i]->next_step;
$node = $node->levelNode[$i]->next->node;
}
if ($step === $s) {
break;
}
}
if ($step === $s) {
do {
if ($step > $e || empty($node)) {
break;
}
$ret[] = $node->mem;
$step += $node->levelNode[0]->next_step;
$node = isset($node->levelNode[0]->next->node) ? $node->levelNode[0]->next->node : null;
} while (true);
}
return $ret;
}
public function getScore($mem)
{
$mem = strval($mem);
$node = $this->getNodePosByMem($mem);
if ($node) {
$step = 0;
$preNode = $node;
do {
$preNode = $preNode->pre;
if ($preNode === null) {
break;
}
if ($preNode->level < $node->level) {
continue;
}
$step += $preNode->levelNode[$node->level-1]->next_step;
} while (true);
return $step;
}
return null;
}
private function getNodePosByMem($mem)
{
return isset($this->hash_table[$mem]) ? $this->hash_table[$mem] : null;
}
private function delNodePosByMem($mem)
{
unset($this->hash_table[$mem]);
}
private function getNodePos($d)
{
$listNode = $this->head;
$i = $listNode->level-1;
do{
$node = isset($listNode->levelNode[$i]->next->node) ? $listNode->levelNode[$i]->next->node : null;
if ($i>0) {
if (empty($node)) {
$i--;
continue;
}
}else{
if (empty($node)) {
break;
}
}
if ($node->d > $d) {
if ($i === 0) {
break;
}else{
while ($i>0 && $node->levelNode[$i]->next_step === $node->levelNode[--$i]->next_step) {};
}
}elseif ($node->d === $d) {
break;
}else{
$listNode = $node;
continue;
}
}while ($i>=0);
return $listNode;
}
private function node_level()
{
$level = 1;
do{
if (mt_rand(0,10000) > 1999) break;
}while (++$level && $level < $this->max_level);
if ($level === $this->max_level) {
$skipListLevelNode = new skipListLevelNode();
$skipListLevelNode->cur_level = $level-1;
$skipListLevelNode->node = $this->head;
$this->head->levelNode[] = $skipListLevelNode;
$this->max_level++;
}
return $level;
}
public function print_list()
{
$node = $this->head;
do {
if (!isset($node->levelNode[0]->next) || empty($node->levelNode[0]->next)) {
break;
}
$node = $node->levelNode[0]->next->node;
var_dump($node->mem . " = " . $node->d, $node->level, isset($node->pre) ? $node->pre->mem:'null');
for ($i=0; $i < $node->level; $i++) {
echo "+++ {$i} +++";
var_dump($node->levelNode[$i]->next_step, isset($node->levelNode[$i]->next));
}
echo "-----------------------
";
} while (1);
echo "-----------head------------
";
foreach ($this->head->levelNode as $key => $n) {
if (isset($n->next)) {
$node = $n->next->node;
var_dump($node->level . ":" . $node->mem . " = " . $node->d, $n->next_step);
}
}
}
}
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持 码农网
猜你喜欢:
- 你真的了解跳跃表吗
- Redis 数据结构：跳跃表
- 走近源码：Redis跳跃列表究竟怎么跳
- MySQL8.0之跳跃范围扫描
- 干货 | 用跳跃—扩散模型估算市场隐含价值
- 深入理解跳跃链表在 Redis 中的应用
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
30天自制操作系统
[日] 川合秀实 / 周自恒、李黎明、曾祥江、张文旭 / 人民邮电出版社 / 2012-8 / 99.00元
自己编写一个操作系统，是许多程序员的梦想。也许有人曾经挑战过，但因为太难而放弃了。其实你错了，你的失败并不是因为编写操作系统太难，而是因为没有人告诉你那其实是一件很简单的事。那么，你想不想再挑战一次呢？ 这是一本兼具趣味性、实用性与学习性的书籍。作者从计算机的构造、汇编语言、C语言开始解说，让你在实践中掌握算法。在这本书的指导下，从零编写所有代码，30天后就可以制作出一个具有窗口系统的32位......一起来看看 《30天自制操作系统》 这本书的介绍吧!
