Java开发者的Python快速进修指南：实战之简易跳表

通过实现一个简易版本的跳表，可以加深了对Python编程的理解。跳表是一种跳跃式的数据结构，通过索引层提供快速查找的能力，提高了查找的效率。在实现跳表的过程中，会更加熟悉了Python的语法和特性，并且可以更加灵活地运用它来解决实际问题。

前言

之前我已经将Python的基本语法与Java进行了比较，相信大家对Python也有了一定的了解。我不会选择去写一些无用的业务逻辑来加强对Python的理解。相反，我更喜欢通过编写一些数据结构和算法来加深自己对Python编程的理解。学习任何语言都一样。

通过编写数据结构和算法，不仅可以加强我自己的思维能力，还能提高对Python编程语言的熟练程度。在这个过程中，我会不断地优化我的代码，以提高算法的效率和性能。我相信通过这种方式，我能够更好地掌握Python编程，并且在解决实际问题时能够更加灵活地运用Python的特性和语法。

跳表

今天我们来使用Python实现一个简易版本的跳表。所谓跳表就是一种跳跃式的数据结构。

假设你是一位图书馆管理员，你需要在图书馆的书架上找到一本特定的书。如果图书馆只是一个普通的书架，你需要逐本书进行查找，这样会花费很多时间和精力。

然而，如果图书馆采用了跳表这种数据结构，书架上的书被分成了几个层次，每一层都有一个索引，上面标注了每本书的位置信息。当你需要找到一本书时，你可以先查看最高层的索引，快速定位到可能包含该书的区域，然后再在该区域内根据索引逐步查找，直到找到目标书籍。

这样，跳表的索引层就相当于图书馆的书籍分类系统，它提供了一个快速查找的方法。通过索引层，你可以迅速定位到书籍所在的区域，减少了查找的次数和时间。

跳表主要的思想是利用索引的概念。因此，每个节点除了保存下一个链表节点的地址之外，还需要额外存储索引地址，用于指示下一步要跳转的地址。它在有序链表的基础上增加了多层索引，以提高查找效率。

而且这适合于读多写少的场景。在实现过程中，无论是在插入数据完毕后重新建立索引，还是在插入数据的同时重新建立索引，都会导致之前建立的索引丢弃，浪费了大量时间。而且，如果考虑多线程的情况，情况会更糟糕。写这种东西时，通常先实现一个简单版，然后根据各个环节进行优化，逐步改进算法。因此，我们今天先实现一个简单版的跳表。

具体实现

我们先来实现一个简单版的跳表，不动态规定步长。我们可以先定义一个固定的步长，比如2。

为了实现跳表，我们需要定义一个节点的数据结构。这个节点包含以下信息：当前节点的值（value），指向前一个节点的指针（before_node），指向后一个节点的指针（next_node），以及指向索引节点的指针（index_node）。

class SkipNode:

    def __init__(self,value,before_node=None,next_node=None,index_node=None):
        self.value = value
        self.before_node = before_node
        self.next_node = next_node
        self.index_node = index_node
        
head = SkipNode(-1)
tail = SkipNode(-1)

为了方便操作，我先生成了两个特殊节点，一个是头节点，另一个是尾节点。头节点作为跳表的起始点，尾节点作为跳表的结束点。

数据插入

在跳表中插入节点时，我们按照从小到大的升序进行排序。插入节点时，无需维护索引节点。一旦完成插入操作，我们需要重新规划索引节点，以确保跳表的性能优化。

def insert_node(node):
    if head.next_node is None:
        head.next_node = node
        node.next_node = tail
        node.before_node = head
        tail.before_node = node
        return
    temp = head.next_node
    # 当遍历到尾节点时，需要直接插入
    while temp.next_node is not None or temp == tail:
        if temp.value > node.value or temp == tail:
            before = temp.before_node
            before.next_node = node
            temp.before_node = node
            node.before_node = before
            node.next_node = temp
            break
        temp = temp.next_node
    re_index()

重建索引

为了重新规划索引，我们可以先将之前已经规划好的索引全部删除。然后，我们可以使用步长为2的方式重新规划索引。

def re_index():
    step = 2
    # 用来建立索引的节点
    index_temp = head.next_node
    # 用来遍历的节点
    temp = head.next_node
    while temp.next_node is not None:
        temp.index_node = None
        if step == 0:
            step = 2
            index_temp.index_node = temp
            index_temp = temp
        temp = temp.next_node
        step -= 1

查询节点

查询：从头节点开始查询，根据节点的值与目标值进行比较。如果节点的值小于目标值，则向右移动到下一个节点或者索引节点继续比较。如果节点的值等于目标值，则找到了目标节点，返回结果。如果节点的值大于目标值，则则说明目标节点不存在。

def search_node(value):
    temp = head.next_node
    step = 0
    while temp.next_node is not None:
        step += 1
        if value == temp.value:
            print(f"该值已找到，经历了{step}次查询")
            return
        elif value < temp.value:
            print(f"该值在列表不存在,经历了{step}次查询")
            return
        if temp.index_node is not None and value > temp.index_node.value:
            temp = temp.index_node
        else:
            temp = temp.next_node
    print(f"该值在列表不存在,经历了{step}次查询")

遍历

为了方便查看，我特意编写了一个用于遍历和查看当前数据的功能，以便更清楚地了解数据的结构和内容。

def print_node():
    my_list = []
    temp = head.next_node
    while temp.next_node is not None:
        if temp.index_node is not None:
            my_dict = {"current_value": temp.value, "index_value": temp.index_node.value}
        else:
            my_dict = {"current_value": temp.value, "index_value": None}  # 设置一个默认值为None
        my_list.append(my_dict)
        temp = temp.next_node
    for item in my_list:
        print(item)

查看结果

所有代码已经准备完毕，现在我们可以在另一个文件中运行并查看跳表的内容和数据。让我们快速进行操作一下。

import skipList
import random


for i in range(0,10):
    random_number = random.randint(1, 100)
    temp = skipList.SkipNode(random_number)
    skipList.insert_node(temp)

skipList.print_node()

skipList.search_node(89)

以下是程序的运行结果。为了方便查看，我特意打印了索引节点的值，以告诉你要跳到哪一个节点。

总结

通过实现一个简易版本的跳表，可以加深了对Python编程的理解。跳表是一种跳跃式的数据结构，通过索引层提供快速查找的能力，提高了查找的效率。在实现跳表的过程中，会更加熟悉了Python的语法和特性，并且可以更加灵活地运用它来解决实际问题。