Bagaimana untuk melaksanakan struktur data jadual langkau dalam golang

Skip list ialah struktur data berdasarkan senarai terpaut, serupa dengan pepohon seimbang, yang boleh merealisasikan operasi carian, sisipan dan pemadaman pantas. Senarai langkau telah dicadangkan oleh William Pugh pada tahun 1990. Pelaksanaannya adalah berdasarkan senarai terpaut Berdasarkan senarai terpaut, indeks berbilang peringkat ditambah, supaya nod senarai terpaut dapat dikesan dengan cepat melalui indeks. . Senarai terpaut di bahagian bawah senarai lompatan boleh menjadi senarai terpaut sehala, senarai terpaut dua kali, dsb., tetapi senarai terpaut sehala yang paling biasa digunakan ialah senarai terpaut sehala. Artikel ini terutamanya memperkenalkan cara menggunakan bahasa Golang untuk melaksanakan struktur data jadual langkau.

Struktur senarai langkau

Struktur utama senarai langkau terdiri daripada tiga bahagian: nod kepala, tatasusunan dan senarai terpaut. Nod kepala digunakan untuk mencari nod permulaan senarai lompat. Tatasusunan digunakan untuk menyimpan indeks berbilang peringkat Setiap elemen tatasusunan ialah penunjuk kepada nod senarai terpaut. Senarai terpaut ialah teras senarai langkau dan digunakan untuk menyimpan data.

Setiap peringkat senarai lompatan mengandungi beberapa nod dan nod disambungkan antara satu sama lain melalui penunjuk. Bilangan nod pada setiap peringkat secara beransur-ansur berkurangan. Lapisan paling rendah mengandungi semua nod data Lapisan ini biasanya dipanggil "lapisan asas", juga dikenali sebagai "senarai terpaut tahap 0". Setiap nod adalah sama ada nod data atau nod indeks. Nod indeks menghala ke nod peringkat seterusnya, dan boleh terdapat sehingga indeks peringkat logn, di mana n ialah bilangan nod data. Jika terdapat indeks tahap k, maka nod pada indeks tahap ke-i akan menyebabkan setiap nod 2^i nod pada indeks tahap ke-1 menghala ke nod pada indeks tahap ke-i. Setiap nod mengandungi penunjuk ke nod peringkat seterusnya di lokasi yang sama.

Golang melaksanakan jadual langkau

Untuk melaksanakan struktur data jadual langkau dalam bahasa Golang, anda perlu melaksanakan fungsi berikut.

1. fungsi createNode: Bertanggungjawab untuk mencipta nod jadual lompat.

taip skipNode struct {

forward []*skipNode 
key int
val interface{}

}

func createNode(level int, key int, val interface{}) *skipNode {

return &skipNode{
    forward: make([]*skipNode, level),
    key: key,
    val: val,
}

}

2. fungsi sisip: bertanggungjawab untuk memasukkan data ke dalam jadual lompat.

sisip func (senarai *SkipList)(int kekunci, antara muka val{}, int tahap) {

 update := make([]*skipNode, list.level+1)
 currentNode := list.head
 for i := list.level; i >= 0; i-- {
    for currentNode.forward[i] != nil && currentNode.forward[i].key < key {
        currentNode = currentNode.forward[i]
    }
    update[i] = currentNode
 }
 currentNode = currentNode.forward[0]
 if currentNode != nil && currentNode.key == key {
    currentNode.val = val
 } else {
    newNode := createNode(level, key, val)
    for i := 0; i <= level; i++ {
        newNode.forward[i] = update[i].forward[i]
        update[i].forward[i] = newNode
    }
 }

}

3. fungsi padam : Bertanggungjawab untuk memadam data.

func (list *SkipList) delete(key int) {

update := make([]*skipNode, list.level+1)
currentNode := list.head

for i := list.level; i >= 0; i-- {
    for currentNode.forward[i] != nil && currentNode.forward[i].key < key {
        currentNode = currentNode.forward[i]
    }
    update[i] = currentNode
}

currentNode = currentNode.forward[0]
if currentNode != nil && currentNode.key == key {
    for i := 0; i <= list.level; i++ {
        if update[i].forward[i] != currentNode {
            break
        }
        update[i].forward[i] = currentNode.forward[i]
    }
}

}

4. fungsi cari: bertanggungjawab mencari data dalam langkau senarai .

func (senarai SkipList) find(key int) skipNode {

currentNode := list.head
for i := list.level; i >= 0; i-- {
    for currentNode.forward[i] != nil && currentNode.forward[i].key < key {
        currentNode = currentNode.forward[i]
    }
}
currentNode = currentNode.forward[0]
if currentNode != nil && currentNode.key == key {
    return currentNode
} else {
    return nil
}

}

Perkara di atas diperlukan untuk melaksanakan langkau senarai fungsi utama. Selain itu, struktur SkipList perlu dilaksanakan, yang mengandungi beberapa atribut senarai langkau, seperti nod kepala, kedalaman maksimum, dsb.

Kesimpulan

Langkau jadual ialah struktur data yang cekap yang boleh melaksanakan operasi sisipan, pemadaman dan carian dengan purata kerumitan masa O(log n). Bahasa Golang menyediakan sintaks dan perpustakaan standard yang agak mesra, jadi agak mudah untuk melaksanakan jadual lompat menggunakan bahasa Golang. Dengan mengkaji artikel ini, saya percaya bahawa pembaca bukan sahaja akan mempunyai pemahaman yang lebih mendalam tentang jadual langkau, tetapi juga menguasai kaedah pelaksanaan jadual langkau dalam bahasa Golang.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan struktur data jadual langkau dalam golang. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!