Javaでデータ構造を試す

次の記事では、Java の Try データ構造の概要を説明します。基本的に、データ構造はコンピューター プログラミングにおいて非常に重要な役割を果たします。また、コンピューター プログラミングにおいてさまざまな種類のデータ構造をいつ、そしてなぜ使用するのかを知る必要があります。通常、トライは離散データ構造であり、これは馴染みがありません。または、これは広く使用されているデータ構造ではないと言えますが、典型的なアルゴリズムで使用されます。トライはデジタル ツリーとしても知られています。基数または接頭辞という別の名前もあります。

無料ソフトウェア開発コースを始めましょう

Web 開発、プログラミング言語、ソフトウェア テスト、その他

トライ データ構造を使用して、キーを使用して適切に構造化されたツリー内のプレフィックスによって要素を検索します。文字列を保存すると有利です。さらに、挿入、削除、検索などのデータ構造に対するさまざまな操作を実行できます。

Java の Trie データ構造の構文

前述の構文を以下に示します。

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)
}

説明:

上記の構文を使用して、trie データ構造に要素を挿入しようとします。そのためには、次の手順に従う必要があります:

• まず、現在のノードを挿入操作のルート ノードとして設定する必要があります。
• その後、現在の文字を単語の最初の文字として設定する必要があります。
• デジタルツリーに現在のノードが存在する場合は、現在のキャラクターを参照し、現在のノードが存在しない場合は、新しいノードを作成する必要があります。
• 最後に、Trie キーを使用してデジタル トラバースを行うことができます。

同様に、削除操作と検索操作の構文を作成できます。

Trie データ構造は Java でどのように機能しますか?

以下は、Trie データ構造が Java でどのように機能するかを示しています。

通常、トライ データ構造では次のように 3 つの異なる操作を実行できます。

1.要素の挿入操作

上記の点については、Java で挿入操作がどのように機能するかについてはすでに説明しました。挿入操作の複雑さは O (n) です。ここで、n はキーのサイズを表します。

2.要素の検索操作

挿入操作の後、次のアルゴリズムを使用して、トライ データ構造に対して検索または検索操作を実行できます。

コード:

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();
}

説明:

次に、try データ構造内の検索要素に対して次の手順を実行します。

• まず、ルートから子ノードを取得します。
• その後、文字列内のすべての文字を反復処理する必要があります。
• 次に、指定された文字が存在するかどうかを確認します。あるいは、それがサブトライの一部であると言えます。指定された文字がサブトライの一部ではない場合は、false を返して終了します。
• 文字列に文字が存在しなくなるまで、2 番目と 3 番目の手順を繰り返します。
• 挿入操作の複雑さは O (n) です。ここで、n はキーのサイズを表します。

3.要素の削除操作

挿入操作のほかに要素を検索します。明らかに、同様に操作を削除するオプションも必要なので、次の手順に従う必要があります。

• 指定された要素が現時点でトライの一部であるかどうかを確認します。
• 要素が見つかった場合は、トライから削除します。
• この計算の複雑さは O(n) です。ここで、n はキーの長さを示します。

Java の Try データ構造の例

以下は Java での Trie データ構造の例です。

コード:

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
}
}

説明:

• 上記の例では、java で trie データ構造を実装しようとしています。ここではまず、ノードを trie データ構造に格納するクラスを作成しました。次に、CHAR_AlPHA_SIZE を使用してアルファベットのサイズを定義しました。次に、クラスのコンストラクターを作成しました。
• 上記のプログラムで示したように、挿入操作 ‘trie_insert’ () と trie データ構造から要素を検索する関数があります。プログラムの最後に、trie データ構造内で挿入および検索する必要があるさまざまな値を指定して、挿入および検索関数を呼び出すだけです。

出力:

結論

上記の記事から、Trie データ構造の基本的な構文を確認し、また Trie データ構造のさまざまな例も確認しました。この記事では、Java で Trie データ構造をいつどのように使用するかを説明しました。

以上がJavaでデータ構造を試すの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。