Python跳表实现遇阻：求插入与可视化打印函数指导

问题概述 #

• 插入逻辑瓶颈：只能在最底层（第0层）添加元素，无法实现元素在多层的插入
• 打印格式不符合预期：仅能输出第0层内容和层数，无法按lvl 0: -inf,1,2,3,inf的格式打印所有层级

附上当前实现代码：

import math
import random as rnd


# node class of skiplist, as given by instructor should have pointers to: pred, next, down

class node:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.next = None
        self.pred = None
        self.down = None


class skipList:
    def __init__(self):
        self.head = node(-math.inf)
        self.tail = node(math.inf)
        self.head.next = self.tail
        self.tail.pred = self.head
        self.length = 0
        self.height = 1


def createLevel(self):  # creates new frame lvl with only -inf/inf as nodes
    newHead = node(- math.inf)
    newTail = node(math.inf)
    newHead.next = newTail
    newTail.pred = newHead
    newHead.down = self.head
    newTail.down = self.tail
    self.head = newHead
    self.tail = newTail


def newLevel(self, levels):
    if levels >= self.height:
        self.height += 1
        self.createLevel()


def coinFlip(self):  # see how many lvls item to be inserted in
    x = rnd.randint(0, 1)
    return x


def search(self, key):  # search returns stack of nodes traversed to reach k
    q = []
    current_node = self.head
    while current_node.down != None:
        current_node = current_node.down
        while current_node.next.key <= key:
            current_node = current_node.next
        q.append(current_node.key)
    return q


def put(self, key, value):
    q = self.search(key)
    current_node = q.pop()  # if k exists, insert new value in k
    if current_node.key == key:
        current_node.value = value
        return
    else:  # else create k after current_node
        while self.coinFlip() == 1:  # check for how many levels
            if q == []:  # key is not in the skiplist, or skiplist empty
        # stuck here. idea: createLevel(), create new_node in levels
        # (unsure how to achieve this for all lvls at once/individually?
        # adjust pointers


def printSkip(self):  # or is it best to use the __str__ method, if so how?
    xs = []
    current_node = self.head
    for level in range(self.height):
        print("level", level)
        while current_node.next != None:
            xs.append(current_node.key)
            current_node = current_node.next
    print(xs)

问题修复与讲解 #

1. 插入函数（put）的核心问题与修复 #

关键问题点：

• 原search函数返回的是节点的key值列表，而非节点对象本身，导致无法操作节点的指针（pred/next/down）
• 多层插入的逻辑没有落实：需要从底层向上逐层创建节点，连接上下层，并调整前后节点的指针
• coinFlip的逻辑需要调整为连续抛硬币直到出现0，以此确定元素要插入的层数

修复步骤：

1. 修改search函数：返回遍历过程中经过的节点栈（而非key），后续插入时需要这些节点来定位插入位置
2. 底层插入逻辑：先在最底层找到正确位置，创建新节点并调整前后指针
3. 多层插入逻辑：通过硬币翻转决定是否向上层插入，若栈为空则创建新层级，每层都要创建新节点，连接下层对应节点，并调整当前层的前后指针

2. 打印函数（printSkip）的修复 #

关键问题点：

• 遍历完一层后，没有切换到下一层的head节点，导致只能打印第一层
• 输出格式不符合要求，需要按层级单独输出

修复步骤：

1. 每一层遍历前，先定位到当前层的head节点
2. 遍历当前层的所有节点，按lvl X: -inf, x1, x2, ..., inf的格式输出
3. 遍历完一层后，切换到下一层的head（通过down指针）

修改后的完整代码 #

import math
import random as rnd


class node:
    def __init__(self, key, value=None):
        self.key = key
        self.value = value
        self.next = None
        self.pred = None
        self.down = None


class skipList:
    def __init__(self):
        self.head = node(-math.inf)
        self.tail = node(math.inf)
        self.head.next = self.tail
        self.tail.pred = self.head
        self.length = 0
        self.height = 1

    def createLevel(self):
        # 创建新的顶层，连接到下层的head和tail
        newHead = node(-math.inf)
        newTail = node(math.inf)
        newHead.next = newTail
        newTail.pred = newHead
        newHead.down = self.head
        newTail.down = self.tail
        self.head = newHead
        self.tail = newTail
        self.height += 1

    def coinFlip(self):
        # 连续抛硬币，返回元素要插入的层数（从0开始）
        level = 0
        while rnd.randint(0, 1) == 1:
            level += 1
        return level

    def search(self, key):
        # 返回遍历路径上的节点栈，用于插入时定位
        stack = []
        current = self.head
        while True:
            # 在当前层向右遍历，直到找到大于key的节点
            while current.next.key <= key:
                current = current.next
            stack.append(current)
            # 如果到了最底层，停止遍历
            if current.down is None:
                break
            current = current.down
        return stack

    def put(self, key, value):
        stack = self.search(key)
        current = stack.pop()

        # 如果key已存在，更新值
        if current.key == key:
            current.value = value
            return

        # 先在最底层插入节点
        new_node = node(key, value)
        # 调整前后指针
        new_node.next = current.next
        new_node.pred = current
        current.next.pred = new_node
        current.next = new_node
        self.length += 1

        # 决定要插入的上层数量
        insert_level = self.coinFlip()
        current_level = 0

        # 向上层插入节点
        while current_level < insert_level:
            # 如果当前栈为空，说明需要创建新的顶层
            if not stack:
                self.createLevel()
                stack.append(self.head)
            
            current = stack.pop()
            # 创建当前层的新节点，连接下层的节点
            upper_node = node(key, value)
            upper_node.down = new_node
            # 调整当前层的前后指针
            upper_node.next = current.next
            upper_node.pred = current
            current.next.pred = upper_node
            current.next = upper_node

            new_node = upper_node
            current_level += 1

    def printSkip(self):
        # 从顶层开始遍历每一层
        current_head = self.head
        for level in range(self.height-1, -1, -1):
            current = current_head
            level_str = [f"{current.key}"]
            while current.next is not None:
                current = current.next
                level_str.append(f"{current.key}")
            print(f"lvl {level}: {', '.join(level_str)}")
            # 切换到下一层的head
            current_head = current_head.down


# 测试示例
if __name__ == "__main__":
    sl = skipList()
    for num in [3, 1, 4, 2, 5]:
        sl.put(num, str(num))
    sl.printSkip()

代码讲解 #

• search函数：现在返回的是节点栈，每个节点是当前层中小于等于目标key的最后一个节点，插入时可以直接用这些节点定位插入位置
• put函数：先在最底层完成插入，然后通过硬币翻转决定向上插入的层数，每层都创建新节点并连接下层节点，同时调整前后指针，保证链表的连续性
• printSkip函数：从顶层开始向下遍历每一层，每层单独收集节点key并按指定格式输出，解决了原代码只能打印一层的问题

内容的提问来源于stack exchange，提问作者NX27