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

龍馬精神

前言

之前我已经将Python的基本语法与Java进行了比较，相信大家对Python也有了一定的了解。我不会选择去写一些无用的业务逻辑来加强对Python的理解。相反，我更喜欢通过编写一些数据结构和算法来加深自己对Python编程的理解。学习任何语言都一样。
通过编写数据结构和算法，不仅可以加强我自己的思维能力，还能提高对Python编程语言的熟练程度。在这个过程中，我会不断地优化我的代码，以提高算法的效率和性能。我相信通过这种方式，我能够更好地掌握Python编程，并且在解决实际问题时能够更加灵活地运用Python的特性和语法。
跳表

今天我们来使用Python实现一个简易版本的跳表。所谓跳表就是一种跳跃式的数据结构。
假设你是一位图书馆管理员，你需要在图书馆的书架上找到一本特定的书。如果图书馆只是一个普通的书架，你需要逐本书进行查找，这样会花费很多时间和精力。
然而，如果图书馆采用了跳表这种数据结构，书架上的书被分成了几个层次，每一层都有一个索引，上面标注了每本书的位置信息。当你需要找到一本书时，你可以先查看最高层的索引，快速定位到可能包含该书的区域，然后再在该区域内根据索引逐步查找，直到找到目标书籍。
这样，跳表的索引层就相当于图书馆的书籍分类系统，它提供了一个快速查找的方法。通过索引层，你可以迅速定位到书籍所在的区域，减少了查找的次数和时间。
跳表主要的思想是利用索引的概念。因此，每个节点除了保存下一个链表节点的地址之外，还需要额外存储索引地址，用于指示下一步要跳转的地址。它在有序链表的基础上增加了多层索引，以提高查找效率。
而且这适合于读多写少的场景。在实现过程中，无论是在插入数据完毕后重新建立索引，还是在插入数据的同时重新建立索引，都会导致之前建立的索引丢弃，浪费了大量时间。而且，如果考虑多线程的情况，情况会更糟糕。写这种东西时，通常先实现一个简单版，然后根据各个环节进行优化，逐步改进算法。因此，我们今天先实现一个简单版的跳表。
具体实现

我们先来实现一个简单版的跳表，不动态规定步长。我们可以先定义一个固定的步长，比如2。
为了实现跳表，我们需要定义一个节点的数据结构。这个节点包含以下信息：当前节点的值（value），指向前一个节点的指针（before_node），指向后一个节点的指针（next_node），以及指向索引节点的指针（index_node）。

1. class SkipNode:
3.     def __init__(self,value,before_node=None,next_node=None,index_node=None):
4.         self.value = value
5.         self.before_node = before_node
6.         self.next_node = next_node
7.         self.index_node = index_node
8.         
9. head = SkipNode(-1)
10. tail = SkipNode(-1)

复制代码

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

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

1. def insert_node(node):
2.     if head.next_node is None:
3.         head.next_node = node
4.         node.next_node = tail
5.         node.before_node = head
6.         tail.before_node = node
7.         return
8.     temp = head.next_node
9.     # 当遍历到尾节点时，需要直接插入
10.     while temp.next_node is not None or temp == tail:
11.         if temp.value > node.value or temp == tail:
12.             before = temp.before_node
13.             before.next_node = node
14.             temp.before_node = node
15.             node.before_node = before
16.             node.next_node = temp
17.             break
18.         temp = temp.next_node
19.     re_index()

复制代码

重建索引

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

1. def re_index():
2.     step = 2
3.     # 用来建立索引的节点
4.     index_temp = head.next_node
5.     # 用来遍历的节点
6.     temp = head.next_node
7.     while temp.next_node is not None:
8.         temp.index_node = None
9.         if step == 0:
10.             step = 2
11.             index_temp.index_node = temp
12.             index_temp = temp
13.         temp = temp.next_node
14.         step -= 1

复制代码

查询节点

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

1. def search_node(value):
2.     temp = head.next_node
3.     step = 0
4.     while temp.next_node is not None:
5.         step += 1
6.         if value == temp.value:
7.             print(f"该值已找到，经历了{step}次查询")
8.             return
9.         elif value < temp.value:
10.             print(f"该值在列表不存在,经历了{step}次查询")
11.             return
12.         if temp.index_node is not None and value > temp.index_node.value:
13.             temp = temp.index_node
14.         else:
15.             temp = temp.next_node
16.     print(f"该值在列表不存在,经历了{step}次查询")

复制代码

遍历

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

1. def print_node():
2.     my_list = []
3.     temp = head.next_node
4.     while temp.next_node is not None:
5.         if temp.index_node is not None:
6.             my_dict = {"current_value": temp.value, "index_value": temp.index_node.value}
7.         else:
8.             my_dict = {"current_value": temp.value, "index_value": None}  # 设置一个默认值为None
9.         my_list.append(my_dict)
10.         temp = temp.next_node
11.     for item in my_list:
12.         print(item)

复制代码

查看结果

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

1. import skipList
2. import random
5. for i in range(0,10):
6.     random_number = random.randint(1, 100)
7.     temp = skipList.SkipNode(random_number)
8.     skipList.insert_node(temp)
10. skipList.print_node()
12. skipList.search_node(89)

复制代码

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

总结

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

来源:https://www.cnblogs.com/guoxiaoyu/p/17856392.html
免责声明：由于采集信息均来自互联网，如果侵犯了您的权益，请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容，谢谢合作！