Timbunan, tindanan, kamus, pokok merah-hitam dan struktur data lain dalam bahasa Go

Dengan perkembangan sains komputer, struktur data telah menjadi subjek penting. Dalam pembangunan perisian, struktur data adalah sangat penting Mereka boleh meningkatkan kecekapan dan kebolehbacaan program, dan juga boleh membantu menyelesaikan pelbagai masalah. Dalam bahasa Go, struktur data seperti timbunan, tindanan, kamus dan pokok merah-hitam juga sangat penting. Artikel ini akan memperkenalkan struktur data ini dan pelaksanaannya dalam bahasa Go.

1. Heap

Heap ialah struktur data klasik yang digunakan untuk menyelesaikan masalah baris gilir keutamaan. Barisan keutamaan merujuk kepada baris gilir yang mengeluarkan elemen mengikut keutamaannya. Timbunan boleh digunakan untuk mencari dengan cepat elemen keutamaan tertinggi dalam baris gilir, supaya operasi sisipan, pemadaman dan carian boleh dilaksanakan dalam kerumitan masa O(log n).

Dalam bahasa Go, heap boleh dilaksanakan menggunakan pakej bekas/timbunan. Pakej ini menyediakan definisi antara muka, yang perlu melaksanakan tiga kaedah:

// Len mengembalikan bilangan elemen dalam timbunan
func (h *timbunan) Len() int {

// ...

}

// Kurang membandingkan keutamaan dua elemen, mengembalikan benar bermakna elemen pertama mempunyai keutamaan yang lebih tinggi
func (h *timbunan) Kurang(i, j int) bool {

// ...

}

// Tukar menukar kedudukan dua elemen
func (h *timbunan) Tukar(i, j int) {

// ...

}

Antaranya, kaedah Less perlu melaksanakan logik perbandingan keutamaan elemen mengikut keperluan sebenar.

Selepas melaksanakan ketiga-tiga kaedah ini, anda boleh menukar kepingan menjadi timbunan melalui kaedah timbunan.Init. Apabila anda perlu menambah atau mengalih keluar elemen, anda boleh menggunakan kaedah heap.Push dan heap.Pop dalam pakej bekas/timbunan.

2. Timbunan

Timbunan ialah satu lagi struktur data biasa, yang boleh merealisasikan storan data masuk pertama dan keluar terakhir. Tindanan digunakan terutamanya dalam senario seperti panggilan program dan rekursi Ia boleh merekodkan susunan panggilan fungsi dan memudahkan pengembalian fungsi.

Dalam bahasa Go, anda boleh menggunakan struktur senarai dalam pakej bekas/senarai untuk melaksanakan tindanan. Perlu diingatkan bahawa operasi tolak dan pop tindanan perlu dilaksanakan menggunakan list.PushBack dan list.Back().Value.(type) masing-masing.

3. Kamus

Kamus (Peta) ialah struktur data yang biasa digunakan yang boleh menyimpan dan menanyakan pasangan nilai kunci. Kamus juga merupakan struktur data yang sangat penting dalam bahasa Go dan sering digunakan untuk merekodkan konfigurasi, maklumat statistik, dsb.

Dalam bahasa Go, kamus boleh ditakrifkan terus menggunakan kata kunci peta. Seperti berikut:

// Takrifkan kamus
m := make(map[string]int)

// Tambah pasangan nilai kunci
m["apple"] = 2
m["pisang"] = 3

// Pasangan nilai kunci pertanyaan
fmt.Println(m["epal"]) // Output 2

// Delete Key-value pair
delete(m, "banana")

Perlu diambil perhatian bahawa jenis kunci kamus mestilah jenis data yang menyokong operator ==, seperti rentetan , int, dsb. Begitu juga, jenis nilai kamus juga perlu mematuhi peraturan dalam bahasa Go.

4. Pokok Merah-Hitam

Pokok Merah-Hitam ialah pokok carian binari pengimbangan diri yang boleh dijalankan dalam O(log n) Laksanakan sisipan, pemadaman dan operasi carian dalam kerumitan masa. Nod pokok merah-hitam mempunyai dua warna, merah dan hitam Mereka mempunyai ciri-ciri berikut:

• Nod akar berwarna hitam
• Semua nod daun adalah hitam dan kosong nod (iaitu, nod daun tidak menyimpan data);
• Semua nod merah mesti mempunyai dua nod anak hitam (pokok merah-hitam menjamin bahawa semua laluan dari nod akar ke nod daun mempunyai bilangan yang sama nod hitam) ;
• Semua laluan dari mana-mana nod ke nod daunnya mengandungi bilangan nod hitam yang sama.

Dalam bahasa Go, anda boleh menggunakan pakej bekas/rbtree untuk melaksanakan pokok merah-hitam. Pakej ini menyediakan definisi antara muka Kaedah yang perlu dilaksanakan ialah:

// Kurang membandingkan saiz dua elemen dan mengembalikan benar untuk menunjukkan bahawa elemen pertama lebih kecil
func (x *MyStruct. ) Less( than item) bool {

// ...

}

Antaranya, kaedah Less perlu melaksanakan logik perbandingan saiz elemen mengikut keperluan sebenar. Semasa pelaksanaan khusus, struktur MyStruct perlu dibenamkan dalam struktur Item, seperti yang ditunjukkan di bawah:

taip MyStruct struct {

item.Item
// ...

}

Selepas melaksanakan kaedah Kurang MyStruct, anda boleh menggunakan bekas Kaedah Root dalam pakej /rbtree mendapatkan nod akar pokok, dan memasukkan, memadam dan menanyakan pokok merah-hitam melalui kaedah Insert, Delete, dan Get. Perlu diingatkan bahawa kaedah Dapatkan yang disediakan oleh pakej ini mengembalikan nod yang sepadan, bukan nilai nod.

Ringkasan

Artikel ini memperkenalkan struktur data yang biasa digunakan dalam bahasa Go: timbunan, tindanan, kamus, pokok merah-hitam. Struktur data ini sangat biasa dalam pembangunan harian, dan menguasai penggunaannya boleh meningkatkan kecekapan dan kebolehbacaan kod kami.

Dalam pembangunan sebenar, kita perlu memilih struktur data yang sesuai berdasarkan keperluan sebenar. Contohnya, anda boleh menggunakan timbunan apabila anda perlu melaksanakan baris gilir keutamaan, anda boleh menggunakan kamus apabila anda perlu menyimpan pasangan nilai kunci, anda boleh menggunakan pokok merah-hitam apabila anda perlu melaksanakan carian pantas, dsb.

Menggunakan struktur data yang sesuai boleh menjadikan kod kami lebih cekap, ringkas dan mudah diselenggara. Saya harap artikel ini akan membantu anda mempelajari dan menggunakan struktur data.

Atas ialah kandungan terperinci Timbunan, tindanan, kamus, pokok merah-hitam dan struktur data lain dalam bahasa Go. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!