Cuba Struktur Data dalam Java

Artikel berikut menyediakan garis besar untuk Trie Data Structure dalam Java. Pada asasnya, struktur data memainkan peranan yang sangat penting dalam pengaturcaraan komputer dan juga, kita mesti tahu bila dan mengapa kita menggunakan pelbagai jenis struktur data dalam pengaturcaraan komputer. Biasanya trie ialah struktur data diskret, dan ini tidak biasa, atau kita boleh mengatakan bahawa ini bukan struktur data yang digunakan secara meluas tetapi ini digunakan dalam algoritma biasa, percubaan juga dikenali sebagai pokok digital; ia juga mempunyai nama lain iaitu radix atau awalan.

Mulakan Kursus Pembangunan Perisian Percuma Anda

Pembangunan web, bahasa pengaturcaraan, ujian perisian & lain-lain

Menggunakan struktur data percubaan, kami mencari elemen dengan awalan dalam pepohon yang tersusun dengan baik dengan kunci, dan adalah berfaedah untuk menyimpan rentetan. Selain itu, kami boleh melaksanakan struktur data percubaan operasi yang berbeza seperti sisipan, pemadaman dan carian.

Sintaks Struktur Data Trie dalam Java

Diberikan di bawah ialah sintaks yang disebut:

public void insert_node(specified string of word){
TrieNode present = rootNode;
For (char i: word.toCharArray()){
Present = present.getChildren().computeIfAbsent(I, c->new TrieNode());
}
Present.setEndOfWord(true)
}

Penjelasan:

Dengan menggunakan sintaks di atas, kami cuba memasukkan elemen ke dalam struktur data percubaan; untuk itu, kita perlu mengikuti langkah-langkah berikut seperti berikut:

• Pertama, kita perlu menetapkan nod sekarang sebagai nod akar untuk operasi sisipan.
• Selepas itu, kita perlu menetapkan watak sekarang sebagai watak pertama perkataan.
• Jika nod sekarang wujud dalam pepohon digital, maka rujuk kepada aksara sekarang, dan jika nod sekarang tidak wujud, kita perlu mencipta nod baharu.
• Akhir sekali, kita boleh menggunakan kekunci Trie untuk merentasi digital.

Begitu juga, kita boleh menulis sintaks untuk operasi pemadaman dan carian.

Bagaimanakah Trie Data Structure berfungsi dalam Java?

Diberikan di bawah menunjukkan cara struktur data try berfungsi dalam java:

Biasanya kami boleh melakukan 3 operasi berbeza dalam struktur data percubaan seperti berikut:

1. Operasi Elemen Sisip

Kami telah menerangkan cara operasi sisipan berfungsi dalam java pada titik di atas. Kerumitan operasi sisipan ialah O (n), dengan n mewakili saiz kekunci.

2. Operasi Elemen Mencari

Selepas operasi sisipan, kami boleh melakukan operasi carian atau cari pada struktur data cuba dengan menggunakan algoritma berikut seperti berikut.

Kod:

public void find_node(specified string of word){
TrieNode present = rootNode;
For (char j = 0; j < word.length(); j++){
char c = word.charAt(j);
TrieNode node = present.getChildren().get(c);
If (node = = null){
return false;
}
Present = node;
}
return present.isEndOfWord();
}

Penjelasan:

Sekarang ikut langkah berikut untuk elemen carian dalam struktur data percubaan seperti berikut:

• Pertama, dapatkan nod anak daripada akar.
• Selepas kita perlu mengulangi setiap aksara dalam rentetan.
• Sekarang semak sama ada aksara yang dinyatakan itu ada, atau kita boleh katakan ia adalah sebahagian daripada percubaan kecil; jika aksara yang dinyatakan bukan sebahagian daripada sub cubaan, maka kembalikan yang palsu dan keluar.
• Ulang langkah kedua dan ketiga sehingga tiada aksara hadir dalam rentetan.
• Kerumitan operasi sisipan ialah O (n), dengan n mewakili saiz kekunci.

3. Padamkan Operasi Elemen

Selain operasi sisipan dan cari elemen; jelas, kita juga sepatutnya mempunyai pilihan untuk memadam operasi, jadi kita perlu mengikuti langkah-langkah berikut seperti berikut.

• Semak sama ada elemen yang dinyatakan adalah pada masa ini sebahagian daripada percubaan.
• Sekiranya unsur itu ditemui, hapuskan ia daripada percubaan.
• Kerumitan pengiraan ini ialah O(n), dengan n merujuk kepada panjang kunci.

Contoh Struktur Data Trie dalam Java

Diberikan di bawah adalah contoh Trie Data Structure dalam Java:

Kod:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
// created class to store node into the trie data structure
class trie_data
{
// Define the size of alphabet size
private static final int CHAR_AlPHA_SIZE = 26;
private boolean isLeaf;
private List<trie_data> child = null;
// Created Constructor of class
trie_data()
{
isLeaf = false;
child = new ArrayList<>(Collections.nCopies(CHAR_AlPHA_SIZE, null));
}
// function for insertion operation
public void trie_insert(String id)
{
System.out.println("We inserted new element into the data structure \"" + id + "\"");
// Staritng from the parent node that is root node
trie_data present = this;
for (char ch: id.toCharArray())
{
// if node is not exist then create new node in trie
if (present.child.get(ch - 'a') == null) {
present.child.set(ch - 'a', new trie_data());
}
// visit next node
present = present.child.get(ch - 'a');
}
// mark present as leaf node
present.isLeaf = true;
}
// search function to search element into trie data structure
// if key value is not present then it return the false
public boolean trie_search(String id)
{
System.out.print("We searched element\"" + id + "\" : ");
trie_data present = this;
for (char ch: id.toCharArray())
{
// visit next node
present = present.child.get(ch - 'a');
if (present == null) {
return false;
}
}
return present.isLeaf;
}
}
class Main
{
public static void main (String[] args)
{
// construct a new Trie node
trie_data head = new trie_data();
head.trie_insert("the");
head.trie_insert("they");
head.trie_insert("final");
System.out.println(head.trie_search("the")); // true
System.out.println(head.trie_search("they")); // true
System.out.println(head.trie_search("final")); // true
System.out.println(head.trie_search("Sample")); // false
head.trie_insert("Sample");
System.out.println(head.trie_search("the")); // true
System.out.println(head.trie_search("they")); // true
System.out.println(head.trie_search("final")); // true
System.out.println(head.trie_search("Sample")); // true
}
}

Penjelasan:

• Dalam contoh di atas, kami cuba melaksanakan struktur data cuba dalam java, di sini mula-mula kami mencipta kelas untuk menyimpan nod ke dalam struktur data cuba. Kemudian, kami menentukan saiz abjad dengan menggunakan CHAR_AlPHA_SIZE. Kemudian, kami mencipta pembina untuk kelas.
• Terdapat fungsi untuk operasi sisipan ‘trie_insert’ () serta untuk mencari elemen daripada struktur data cuba seperti yang ditunjukkan dalam atur cara di atas. Pada penghujung program, kami hanya memanggil fungsi sisip dan carian dengan nilai berbeza yang perlu kami masukkan dan cari dalam struktur data cuba.

Output:

Kesimpulan

Daripada artikel di atas, kami melihat sintaks asas struktur data Trie dan kami juga melihat contoh struktur data Trie yang berbeza. Daripada artikel ini, kami melihat cara dan bila kami menggunakan struktur data Trie dalam Java.

Atas ialah kandungan terperinci Cuba Struktur Data dalam Java. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!