前言

之前我已經(jīng)將Python的基本語法與Java進行了比較，相信大家對Python也有了一定的了解。我不會選擇去寫一些無用的業(yè)務(wù)邏輯來加強對Python的理解。相反，我更喜歡通過編寫一些數(shù)據(jù)結(jié)構(gòu)和算法來加深自己對Python編程的理解。學(xué)習(xí)任何語言都一樣。

通過編寫數(shù)據(jù)結(jié)構(gòu)和算法，不僅可以加強我自己的思維能力，還能提高對Python編程語言的熟練程度。在這個過程中，我會不斷地優(yōu)化我的代碼，以提高算法的效率和性能。我相信通過這種方式，我能夠更好地掌握Python編程，并且在解決實際問題時能夠更加靈活地運用Python的特性和語法。

跳表

今天我們來使用Python實現(xiàn)一個簡易版本的跳表。所謂跳表就是一種跳躍式的數(shù)據(jù)結(jié)構(gòu)。

假設(shè)你是一位圖書館管理員，你需要在圖書館的書架上找到一本特定的書。如果圖書館只是一個普通的書架，你需要逐本書進行查找，這樣會花費很多時間和精力。

然而，如果圖書館采用了跳表這種數(shù)據(jù)結(jié)構(gòu)，書架上的書被分成了幾個層次，每一層都有一個索引，上面標(biāo)注了每本書的位置信息。當(dāng)你需要找到一本書時，你可以先查看最高層的索引，快速定位到可能包含該書的區(qū)域，然后再在該區(qū)域內(nèi)根據(jù)索引逐步查找，直到找到目標(biāo)書籍。

這樣，跳表的索引層就相當(dāng)于圖書館的書籍分類系統(tǒng)，它提供了一個快速查找的方法。通過索引層，你可以迅速定位到書籍所在的區(qū)域，減少了查找的次數(shù)和時間。

跳表主要的思想是利用索引的概念。因此，每個節(jié)點除了保存下一個鏈表節(jié)點的地址之外，還需要額外存儲索引地址，用于指示下一步要跳轉(zhuǎn)的地址。它在有序鏈表的基礎(chǔ)上增加了多層索引，以提高查找效率。

而且這適合于讀多寫少的場景。在實現(xiàn)過程中，無論是在插入數(shù)據(jù)完畢后重新建立索引，還是在插入數(shù)據(jù)的同時重新建立索引，都會導(dǎo)致之前建立的索引丟棄，浪費了大量時間。而且，如果考慮多線程的情況，情況會更糟糕。寫這種東西時，通常先實現(xiàn)一個簡單版，然后根據(jù)各個環(huán)節(jié)進行優(yōu)化，逐步改進算法。因此，我們今天先實現(xiàn)一個簡單版的跳表。

具體實現(xiàn)

我們先來實現(xiàn)一個簡單版的跳表，不動態(tài)規(guī)定步長。我們可以先定義一個固定的步長，比如2。

為了實現(xiàn)跳表，我們需要定義一個節(jié)點的數(shù)據(jù)結(jié)構(gòu)。這個節(jié)點包含以下信息：當(dāng)前節(jié)點的值（value），指向前一個節(jié)點的指針（before_node），指向后一個節(jié)點的指針（next_node），以及指向索引節(jié)點的指針（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)

為了方便操作，我先生成了兩個特殊節(jié)點，一個是頭節(jié)點，另一個是尾節(jié)點。頭節(jié)點作為跳表的起始點，尾節(jié)點作為跳表的結(jié)束點。

數(shù)據(jù)插入

在跳表中插入節(jié)點時，我們按照從小到大的升序進行排序。插入節(jié)點時，無需維護索引節(jié)點。一旦完成插入操作，我們需要重新規(guī)劃索引節(jié)點，以確保跳表的性能優(yōu)化。

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
    # 當(dāng)遍歷到尾節(jié)點時，需要直接插入
    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()

重建索引

為了重新規(guī)劃索引，我們可以先將之前已經(jīng)規(guī)劃好的索引全部刪除。然后，我們可以使用步長為2的方式重新規(guī)劃索引。

def re_index():
    step = 2
    # 用來建立索引的節(jié)點
    index_temp = head.next_node
    # 用來遍歷的節(jié)點
    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

查詢節(jié)點

查詢：從頭節(jié)點開始查詢，根據(jù)節(jié)點的值與目標(biāo)值進行比較。如果節(jié)點的值小于目標(biāo)值，則向右移動到下一個節(jié)點或者索引節(jié)點繼續(xù)比較。如果節(jié)點的值等于目標(biāo)值，則找到了目標(biāo)節(jié)點，返回結(jié)果。如果節(jié)點的值大于目標(biāo)值，則則說明目標(biāo)節(jié)點不存在。

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"該值已找到，經(jīng)歷了{step}次查詢")
            return
        elif value < temp.value:
            print(f"該值在列表不存在,經(jīng)歷了{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"該值在列表不存在,經(jīng)歷了{step}次查詢")

遍歷

為了方便查看，我特意編寫了一個用于遍歷和查看當(dāng)前數(shù)據(jù)的功能，以便更清楚地了解數(shù)據(jù)的結(jié)構(gòu)和內(nèi)容。

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}  # 設(shè)置一個默認(rèn)值為None
        my_list.append(my_dict)
        temp = temp.next_node
    for item in my_list:
        print(item)

查看結(jié)果

所有代碼已經(jīng)準(zhǔn)備完畢，現(xiàn)在我們可以在另一個文件中運行并查看跳表的內(nèi)容和數(shù)據(jù)。讓我們快速進行操作一下。

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)

以下是程序的運行結(jié)果。為了方便查看，我特意打印了索引節(jié)點的值，以告訴你要跳到哪一個節(jié)點。

總結(jié)

通過實現(xiàn)一個簡易版本的跳表，可以加深了對Python編程的理解。跳表是一種跳躍式的數(shù)據(jù)結(jié)構(gòu)，通過索引層提供快速查找的能力，提高了查找的效率。在實現(xiàn)跳表的過程中，會更加熟悉了Python的語法和特性，并且可以更加靈活地運用它來解決實際問題。

以上就是Java開發(fā)者快速進修Python指南之簡易跳表的詳細(xì)內(nèi)容，更多關(guān)于Python簡易跳表的資料請關(guān)注腳本之家其它相關(guān)文章！

最新評論