logo

TechCodeview

Amazonas

Datenstruktur testen | Einfügen und Suchen

Datenstruktur testen | Einfügen und Suchen

Der Versuchen Sie es mit der Datenstruktur ist eine baumartige Datenstruktur, die zum Speichern eines dynamischen Satzes von Zeichenfolgen verwendet wird. Es wird häufig für effiziente Zwecke verwendet Abruf Und Lagerung von Schlüsseln in einem großen Datensatz. Die Struktur unterstützt Vorgänge wie Einfügen , suchen , Und Streichung von Schlüsseln, was es zu einem wertvollen Werkzeug in Bereichen wie Informatik und Informationsbeschaffung macht. In diesem Artikel werden wir es untersuchen Einfügen und Suchen Operation in der Trie-Datenstruktur.

Versuchen Sie es mit der Datenstruktur

Versuchen Sie es mit der Datenstruktur

Inhaltsverzeichnis

Nachfolgend finden Sie die Umsetzung des oben genannten Ansatzes:

C++ 
#include  using namespace std; struct TrieNode {  // pointer array for child nodes of each node  TrieNode* childNode[26];  // Used for indicating ending of string  bool wordEnd;  TrieNode()  {  // constructor  // initialize the wordEnd variable with false  // initialize every index of childNode array with  // NULL  wordEnd = false;  for (int i = 0; i  < 26; i++) {  childNode[i] = NULL;  }  } }; void insert_key(TrieNode* root, string& key) {  // Initialize the currentNode pointer  // with the root node  TrieNode* currentNode = root;  // Iterate across the length of the string  for (auto c : key) {  // Check if the node exist for the current  // character in the Trie.  if (currentNode->childNode[c - 'a'] == NULL) { // Wenn der Knoten für das aktuelle Zeichen nicht existiert // dann einen neuen Knoten erstellen TrieNode* newNode = new TrieNode();  // Behalten Sie die Referenz für den neu erstellten // Knoten bei.  currentNode->childNode[c - 'a'] = newNode;  } // Verschieben Sie nun den aktuellen Knotenzeiger auf den neu // erstellten Knoten.  currentNode = currentNode->childNode[c - 'a'];  } // Erhöhe den WordEndCount für den letzten // CurrentNode-Zeiger. Dies impliziert, dass es eine Zeichenfolge gibt, die bei // currentNode endet.  currentNode->wordEnd = 1; } bool search_key(TrieNode* root, string& key) { // Initialisiere den currentNode-Zeiger // mit dem Wurzelknoten TrieNode* currentNode = root;  // Iteriere über die Länge der Zeichenfolge for (auto c : key) { // Überprüfe, ob der Knoten für das aktuelle // Zeichen im Trie vorhanden ist.  if (currentNode->childNode[c - 'a'] == NULL) { // Das gegebene Wort existiert nicht in Trie return false;  } // Verschiebe den currentNode-Zeiger auf den bereits // vorhandenen Knoten für das aktuelle Zeichen.  currentNode = currentNode->childNode[c - 'a'];  } return (currentNode->wordEnd == true); } // Treibercode int main() { // Einen Wurzelknoten für den Trie erstellen TrieNode* root = new TrieNode();  // Speichert die Zeichenfolgen, die wir in den // Trie-Vektor einfügen möchten inputStrings = { 'and', 'ant', 'do', 'geek', 'dad', 'ball' };  // Anzahl der Einfügeoperationen im Trie int n = inputStrings.size();  für (int i = 0; i < n; i++) {  insert_key(root, inputStrings[i]);  }  // Stores the strings that we want to search in the Trie  vector searchQueryStrings = { 'do', 'geek', 'bat' };  // Anzahl der Suchvorgänge im Trie int searchQueries = searchQueryStrings.size();  für (int i = 0; i < searchQueries; i++) {  cout  < < 'Query String: '  < < searchQueryStrings[i]   < < '
';  if (search_key(root, searchQueryStrings[i])) {  // the queryString is present in the Trie  cout  < < 'The query string is present in the '  'Trie
';  }  else {  // the queryString is not present in the Trie  cout  < < 'The query string is not present in '  'the Trie
';  }  }  return 0; }
Java 
class TrieNode {  TrieNode[] childNode;  boolean wordEnd;  TrieNode()  {  childNode = new TrieNode[26];  wordEnd = false;  } } class Trie {  TrieNode root;  Trie() { root = new TrieNode(); }  // Function to insert a key into the Trie  void insert(String key)  {  TrieNode currentNode = root;  for (int i = 0; i  < key.length(); i++) {  int index = key.charAt(i) - 'a';  if (currentNode.childNode[index] == null) {  currentNode.childNode[index]  = new TrieNode();  }  currentNode = currentNode.childNode[index];  }  currentNode.wordEnd = true;  }  // Function to search for a key in the Trie  boolean search(String key)  {  TrieNode currentNode = root;  for (int i = 0; i  < key.length(); i++) {  int index = key.charAt(i) - 'a';  if (currentNode.childNode[index] == null) {  return false;  }  currentNode = currentNode.childNode[index];  }  return currentNode.wordEnd;  } } public class Main {  public static void main(String[] args)  {  Trie trie = new Trie();  String[] inputStrings  = { 'and', 'ant', 'do', 'geek', 'dad', 'ball' };  // Insert each string into the Trie  for (String str : inputStrings) {  trie.insert(str);  }  String[] searchQueryStrings  = { 'do', 'geek', 'bat' };  // Search for each string and print whether it is  // found in the Trie  for (String query : searchQueryStrings) {  System.out.println('Query String: ' + query);  if (trie.search(query)) {  System.out.println(  'The query string is present in the Trie');  }  else {  System.out.println(  'The query string is not present in the Trie');  }  }  } }
Python 
class TrieNode: def __init__(self): self.childNode = [None] * 26 self.wordEnd = False class Trie: def __init__(self): self.root = TrieNode() # Function to insert a key into the Trie def insert(self, key): currentNode = self.root for char in key: index = ord(char) - ord('a') if not currentNode.childNode[index]: currentNode.childNode[index] = TrieNode() currentNode = currentNode.childNode[index] currentNode.wordEnd = True # Function to search for a key in the Trie def search(self, key): currentNode = self.root for char in key: index = ord(char) - ord('a') if not currentNode.childNode[index]: return False currentNode = currentNode.childNode[index] return currentNode.wordEnd if __name__ == '__main__': trie = Trie() inputStrings = ['and', 'ant', 'do', 'geek', 'dad', 'ball'] # Insert each string into the Trie for word in inputStrings: trie.insert(word) searchQueryStrings = ['do', 'geek', 'bat'] # Search for each string and print whether it is found in the Trie for query in searchQueryStrings: print('Query String:', query) if trie.search(query): print('The query string is present in the Trie') else: print('The query string is not present in the Trie')
JavaScript 
class TrieNode {  constructor() {  // Initialize the childNode array with 26 nulls  this.childNode = Array(26).fill(null);  // Initialize wordEnd to the false indicating that no word ends here yet  this.wordEnd = false;  } } class Trie {  constructor() {  // Initialize the root node of the Trie  this.root = new TrieNode();  }  // Function to insert a key into the Trie  insert(key) {  // Start from the root node  let currentNode = this.root;  for (let i = 0; i  < key.length; i++) {  const index = key.charCodeAt(i) - 'a'.charCodeAt(0);  if (currentNode.childNode[index] === null) {  currentNode.childNode[index] = new TrieNode();  }  // Move to the next node in the Trie  currentNode = currentNode.childNode[index];  }  // Mark the end of the word  currentNode.wordEnd = true;  }  // Function to search for a key in the Trie  search(key) {  // Start from the root node  let currentNode = this.root;  // Iterate through each character in the key  for (let i = 0; i  < key.length; i++) {  const index = key.charCodeAt(i) - 'a'.charCodeAt(0);  if (currentNode.childNode[index] === null) {  return false;  }  // Move to the next node in the Trie  currentNode = currentNode.childNode[index];  }  // Return true if the end of the word is marked otherwise false  return currentNode.wordEnd;  } } // Driver code const trie = new Trie(); const inputStrings = ['and', 'ant', 'do', 'geek', 'dad', 'ball']; // Insert each string into the Trie inputStrings.forEach((str) =>trie.insert(str)); const searchQueryStrings = ['do', 'geek', 'bat']; // Nach jeder Zeichenfolge suchen und ausgeben, ob sie im Trie gefunden wird searchQueryStrings.forEach((query) => { console.log(`Query String: ${query}`); if (trie.search(query)) { console.log('Die Abfragezeichenfolge ist im Trie vorhanden'); else { console.log('Die Abfragezeichenfolge ist im Trie nicht vorhanden' });

Ausgabe 
Query String: do The query string is present in the Trie Query String: geek The query string is present in the Trie Query String: bat The query string is not present in the Trie

Versuchen Sie es mit Löschen
  • Inhalte von Trie werden angezeigt
  • Autovervollständigungsfunktion mit Trie
  • Mustersuche mithilfe eines Versuchs aller Suffixe

    • Übungsprobleme:

    • Minimaler Wortumbruch
    • Eindeutige Zeilen in einer binären Matrix
    • Anzahl unterschiedlicher Teilzeichenfolgen
    • Wort-Boggle
    • Sortieren eines Arrays von Zeichenfolgen (oder Wörtern) mithilfe von Trie


    Aktie

    Das Könnte Ihnen Gefallen

    Log4J-Protokollierungsstufen

    Log4J-Protokollierungsstufen

    National Merit Finalist – So gewinnen Sie das Stipendium

    National Merit Finalist – So gewinnen Sie das Stipendium

    Top Artikel

    Kategorie

    Blog Java-Konvertierung Mathe Java-Sammlungen Unterschiede Java-String

    Interessante Artikel