前言

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

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

跳表

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

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

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

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

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

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

具體實(shí)現(xiàn)

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

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

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

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

在跳表中插入節(jié)點(diǎn)時(shí)，我們按照從小到大的升序進(jìn)行排序。插入節(jié)點(diǎn)時(shí)，無需維護(hù)索引節(jié)點(diǎn)。一旦完成插入操作，我們需要重新規(guī)劃索引節(jié)點(diǎn)，以確保跳表的性能優(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é)點(diǎn)時(shí)，需要直接插入
    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é)點(diǎn)
    index_temp = head.next_node
    # 用來遍歷的節(jié)點(diǎn)
    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é)點(diǎn)

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

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

遍歷

為了方便查看，我特意編寫了一個(gè)用于遍歷和查看當(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è)置一個(gè)默認(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)在我們可以在另一個(gè)文件中運(yùn)行并查看跳表的內(nèi)容和數(shù)據(jù)。讓我們快速進(jìn)行操作一下。

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)

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

總結(jié)

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

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

最新評(píng)論