2


我正在尝试使用来自http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html的伪代码在 PHP 中实现一个跳过列表。我设法让它在 java 中正常工作，但在 PHP 中却不行。我的 put 方法总是返回 null，因此，我的 get 方法也返回 null。
我不太明白我要去哪里错了，所以我很感激任何帮助！

<?php
interface SkipListEntry {
public function getPrev(); 
public function getNext(); 
public function getAbove(); 
public function getBelow(); 

public function getKey();
public function getValue();    
public function setValue($v);

public function setPrev($v);
public function setNext($v);
public function setAbove($v);
public function setBelow($v);

public function hasPrev();
public function hasNext();
public function hasAbove();
public function hasBelow();
}

class SkipListNode implements SkipListEntry {
  private $prev;
  private $next;
  private $above;
  private $below;

  private $key;
  private $value;

  public static $posInf = "+oo";
  public static $negInf = "-oo"; 

  function __construct($a, $b) {
$this->key = $a;
$this->value = $b;
  }

  public function getPrev(){
return $this->prev;
  }
  public function getNext(){
return $this->next;
  }
  public function getAbove(){
return $this->above;
  }
  public function getBelow(){
return $this->below;
  }

  public function getKey(){
return $this->key;
  }
  public function getValue(){
return $this->value;
  }

  public function setValue($n){
$this->value = $n;
  }

  public function setPrev($n) {
$this->prev = $n;
  }
  public function setNext($n) {
$this->next = $n;
  }
  public function setAbove($n) {
$this->above = $n;
  }
  public function setBelow($n) {
$this->below = $n;
  }

  public function hasPrev(){
return !is_null($this->prev);
  }

  public function hasNext(){
return !is_null($this->next);
  }

  public function hasAbove(){
return !is_null($this->above);
  }

  public function hasBelow(){
return !is_null($this->below);
  }  
}

class SkipList{
  private $topLeft;
  private $topRight;

  private $height = 0;
  private $totalEntries = 0;

  private $head;

  function __construct(){  
  $this->topLeft = new SkipListNode(SkipListNode::$negInf, null);
  $this->topRight = new SkipListNode(SkipListNode::$posInf, null);

  $this->topLeft->setNext($this->topRight);    
  $this->topRight->setPrev($this->topLeft);     

  $this->head = $this->topLeft;   
  }

  public function size() {
return $this->totalEntries;
  }

  public function isEmpty(){
return $this->totalEntries == 0;
  }  

  public function search($key){
$p = $this->head; 
while (true) {
  while (!$p->getNext()->getKey() == SkipListNode::$posInf
    && strcmp($p->getNext()->getKey(), $key) <= 0) {
      $p = $p->getNext();
    }
    if ($p->hasBelow()){
      $p = $p->getBelow();
    }
    else {
      break;
    }      
}
return $p;
  }

  public function put($key, $value){ 
$searchElement = $this->search($key);  
if ($key == $searchElement->getKey()){
  $oldValue = $searchElement->getValue();
  $searchElement->setValue($value);
  return $oldValue;
}
$newEntry = new SkipListNode($key, $value);
$newEntry->setPrev($searchElement);
$newEntry->setNext($searchElement->getNext());


$searchElement->getNext()->setPrev($newEntry);
$searchElement->setNext($newEntry);

$currentHeight = 0;
for ($j = 1; $j <= $this->coinFlip(); $j ++){
  if ($currentHeight >= $this->height){
    $this->createAdditionalLayer();
  }
  while (is_null($searchElement->getAbove())){
    $searchElement = $searchElement->getprev();
  }
  $searchElement = $searchElement->getAbove();

  $aboveElement = new SkipListNode($key, null);
  $aboveElement->setPrev($searchElement);
  $aboveElement->setNext($searchElement->getNext());
  $aboveElement->setBelow($newEntry);

  $searchElement->getNext()->setPrev($aboveElement);
  $searchElement->setNext($aboveElement);
  $newEntry->setAbove($aboveElement);
  $newEntry = $aboveElement;
  $currentHeight ++;
}
$this->totalEntries ++;
return null;
  }

  public function get($key){
$p = $this->search($key); 
if ($p->getKey() == $key){
  return $p->getValue();
}
return null;
  }

  private function createAdditionalLayer(){  
  $newtopLeft = new SkipListNode(SkipListNode::$negInf, null);
  $newtopRight = new SkipListNode(SkipListNode::$posInf, null);

  $newtopLeft->setNext($newtopRight);
  $newtopLeft->setBelow($this->head);
  $newtopRight->setPrev($newtopLeft);
  $this->head->setAbove($newtopLeft);
  $this->head = $newtopLeft;
  $this->height ++;
  }

  private function coinFlip(){
$total = 0;
$current = -1;

while ($current != 1){
  $current = rand(0,1);
  $total ++;
}
return $total;
  }
}

// test

$a = new SkipList();
var_dump($a->put("a", "b")); 
var_dump($a->put("a", "c")); // should return c (returns null) 
var_dump($a->size()); // should return 1 (returns 2)
var_dump($a->get("a")); // should return c, (returns null)

谢谢！

4

1 回答 1

1

我在搜索功能中发现了一些问题：

请更改您的代码并尝试：

public function search($key){
        $p = $this->head;
        while (true) {


            while ($p->getNext()->getKey() != SkipListNode::$posInf
                    && strcmp($p->getNext()->getKey(), $key) == 0) {
                        $p = $p->getNext();
                    }
                    if ($p->hasBelow()){
                        $p = $p->getBelow();
                    }
                    else {
                        break;
                    }
        }
        return $p;
    }

结果是：

var_dump($a->put("a", "b")); 
var_dump($a->put("a", "c")); string 'b',
var_dump($a->size()); int 1,
var_dump($a->get("a")); string 'c'
于 2015-12-26T05:12:22.897 回答