我想用Python實現一個跳過列表。你可以幫我嗎？很簡單

Question

這只是一個非常簡單的代碼，我的參考就是從這裏開始：http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/Map/skip-list-impl.html#why-q

我想插入功能是好的，但是當我嘗試使用get()功能，它不返回任何東西，而是循環無休止地在searchEntry()部分內。我不知道什麼是錯的。在insert()功能中，searchEntry()運行良好。它返回對floorEntry(k)條目的引用，其中包含的關鍵字小於需要在跳過列表中插入的關鍵字。請幫我弄清searchEntry()函數中的錯誤來源。對不起，我並不擅長這一點。謝謝！

from QuadLinkedList import QLLNode 
import random 
class Skippy: 


    def __init__(self): 

     self._p1 = QLLNode("MINUS_INF") 
     self._p2 = QLLNode("PLUS_INF") 

     self._head = self._p1 
     self._tail = self._p2 

     self._p1.setNext(self._p2) 
     self._p2.setPrev(self._p1) 

     self._height = 0 
     self._n = 0 

    def insert(self, key, value): 

     p = self.searchEntry(key) 
     print "p = " + str(p.getKey()) 
     q = QLLNode(key, value) 
     q.setPrev(p) 
     q.setNext(p.getNext()) 
     p.getNext().setPrev(q) 
     p.setNext(q) 

     i = 0 

     while random.randint(0,1) != 0: 

      if i >= self._height: 
       self._height += 1 

       newHead = QLLNode("MINUS_INF") 
       newTail = QLLNode("PLUS_INF") 

       newHead.setNext(newTail) 
       newHead.setDown(self._head) 

       newTail.setPrev(newHead) 
       newTail.setDown(self._tail) 

       self._head.setUp(newHead) 
       self._tail.setUp(newTail) 

       self._head = newHead 
       self._tail = newTail 

      while p.getUp() == None: 
       p = p.getPrev() 

      p = p.getUp() 

      e = QLLNode(key,None) 

      e.setPrev(p) 
      e.setNext(p.getNext()) 
      e.setDown(q) 

      p.getNext().setPrev(e) 
      p.setNext(e) 
      q.setUp(e) 

      q = e 

      i += 1 

     self._n += 1 
     return None 

    def get(self, key): 
     p = self.searchEntry(key) 

     if key == p.getKey(): 
      return p.getElement() 
     else: 
      return "There's None!" 

    def searchEntry(self, key): 
     p = self._head 

     while True: 
      while p.getNext().getKey() != "PLUS_INF" and p.getNext().getKey() <= key: 
       p = p.getNext() 
      if p.getDown() != None: 
       p = p.getDown() 
      else: 
       break 
     return p 

Answer 1

問題並不在searchEntry的代碼，這似乎有正確的邏輯。問題是列表結構正在變得混亂。我相信問題出在您爲insert中的列表添加新級別的代碼。特別是該位：

 if i >= self._height: #make an empty level 

      self._height += 1 

      self._minus.setNext(self._plus) 
      self._minus.setDown(self._head) 

      self._plus.setPrev(self._minus) 
      self._plus.setDown(self._tail) 

      self._head.setUp(self._minus) 
      self._tail.setUp(self._plus) 

      self._head = self._minus 
      self._tail = self._plus 

脫穎而出，以我這個代碼的事情是，你沒有創建任何新的節點，只需修改現有的，這是什麼是打破你的表結構。我想，您需要創建新的head和tail節點，並將它們鏈接到結構的頂部。 （minus和plus不如在你的鏈接描述的算法的一部分，所以我不知道你與他們做什麼。）也許你想是這樣的：

 if i >= self._height: #make an empty level 

      self._height += 1 

      newHead = QLLNode("MINUS_INF") 
      newTail = QLLNode("PLUS_INF") 

      newHead.setNext(newTail) 
      newHead.setDown(self._head) 

      newTail.setPrev(newHead) 
      newTail.setDown(self._tail) 

      self._head.setUp(newHead) 
      self._head = newHead 

      self._tail.setUp(newTail) 
      self._tail = newTail