資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 Trie 以逆字典序列印字串
簡介
本教程實現了使用 Trie 以逆字典序列印字串的方法。Trie 是一種具有樹形表示的資料結構。它是有序的，並提供了一種有效的字串檢索方法。它像樹形資料結構一樣具有節點和邊。為了解決該任務，初始化一個數組並使用 Trie 以逆字典序排列字串。每個字母都用作樹中的一個節點。重複的陣列元素只打印一次。
演示 1
arr[] = {“hello", "world", "open", "ai", "c++", "programming"”}
輸出
world programming open hello c++ ai
解釋
在上面的輸入陣列中，遍歷陣列以逆序列印所有元素。
演示 2
arr[] = {“life”, “dog”, “is”, “good”}
輸出
life good is dog
解釋
在上面的輸入陣列中，遍歷所有元素以逆序列印。使用 Trie 概念反轉字串並形成樹。
C++ 庫函式
語法
length(): 它是一個字串類庫函式，以位元組形式返回字串的長度。
string_name.length();
vector: 它是 C++ 中的動態陣列，在 <vector> 標頭檔案中定義。它提供了高效的插入和刪除操作。
vector<data_type> vector_name;
push_back(): 它是在 <vector> 標頭檔案中預定義的函式。它將元素插入或推送到向量陣列的末尾。
vector_name.push_back(value);
sort(): 此 C++ 庫函式按升序對陣列或向量進行排序。它採用兩個引數，其中第一個引數是起始點，第二個引數是陣列的結束元素。
sort(first, second);
演算法
初始化一個數組。
使用字串（陣列元素）構建 Trie 資料結構。
使用第一個字串建立最右邊的子樹，使用第二個字串建立最左邊的子樹。這樣，所有字串都可以用來形成一個 Trie。
反轉字串並列印結果。
示例 1
這裡我們實現了一種使用 Trie 以逆字典序列印所有字串的方法。使用字串以先到先服務的順序構建樹。字串的字母構成樹節點。
#include <bits/stdc++.h>
using namespace std;
#define CH 26
#define MAX 100
// structure for trie
struct trieTree {
trieTree* children[CH];
bool endOfString;
};
// Function for trie treeL
trieTree* createTrieNode(){
//creating object
trieTree* t = new trieTree();
t->endOfString = false;
for (int x = 0; x < CH; x++){
// null for all child nodes of trie
t->children[x] = NULL;
}
return t;
}
// recursively inserting string to the trie
void insertStringRecursively(trieTree* it,string s, int l){
if (l < s.length()){
int ind = s[l] - 'a';
if (it->children[ind] == NULL){
// Creating new node of trie
it->children[ind] = createTrieNode();
}
// calling function recursively
insertStringRecursively(it->children[ind], s, l + 1);
} else {
it->endOfString = true;
}
}
// Function to insert the string to trie
void insertString(trieTree* it, string s)
{
//calling function
insertStringRecursively(it, s, 0);
}
// Function To find trie leaf node
bool isTrieLeafNode(trieTree* r){
return r->endOfString != false;
}
// Function for printing the result
void printResult(trieTree* r, char s[], int a){
if (isTrieLeafNode(r)){
//null for empty string
s[a] = '\0';
cout << s << endl;
}
for (int x = CH - 1; x >= 0; x--){
if (r->children[x]){
s[a] = x + 'a';
printResult(r->children[x], s, a + 1);
}
}
}
// function for printing the output
void displaying(trieTree* it){
int a = 0;
char s[MAX];
printResult(it, s, a);
}
// code controller
int main(){
trieTree* r = createTrieNode();
//calling function to insert string to the trie
insertString(r, "this");
insertString(r, "car");
insertString(r, "is");
insertString(r, "expensive");
//calling function to print the output
displaying(r);
return 0;
}
輸出
this is expensive car
示例 2
在此 C++ 實現中，為了以逆序列印字串，我們使用結構來表示 Trie 資料結構的節點。如果節點表示單詞的結尾，則將標誌 isEndWord 設定為 true。使用 createNode 函式建立 Trie 的節點。構建樹後，遍歷所有節點以逆字典序列印字串。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// structure for trie nodes
struct NodeOfTrie{
NodeOfTrie* child[26];
bool isEndWord; // Flag to mark the array end
};
// Creating trie node
NodeOfTrie* createNode(){
NodeOfTrie* newN = new NodeOfTrie;
newN->isEndWord = false;
for (int x = 0; x < 26; x++){
newN->child[x] = nullptr;
}
return newN;
}
// Inserting strings to trie
void insertWord(NodeOfTrie* r, const string& w){
NodeOfTrie* current = r;
// Traversing tree
for (char c : w){
int ind = c - 'a';
// Create a new node if the path doesn't exist
if (current->child[ind] == nullptr){
current->child[ind] = createNode();
}
// Moving next node
current = current->child[ind];
}
// Marking end of the array
current->isEndWord = true;
}
// depth first search function
void depthfirstsearch(NodeOfTrie* r, string currentWord, vector<string>& output){
if (r == nullptr){
return;
}
if (r->isEndWord){
output.push_back(currentWord);
}
for (int x = 25; x >= 0; x--){
if (r->child[x] != nullptr){
depthfirstsearch(r->child[x], currentWord + char(x + 'a'), output);
}
}
}
// Function for print reverse strings
void reverseOrder(vector<string>& arr) {
// Creating trie nodes
NodeOfTrie* r = createNode();
// Inserting array strings to trie
for (const string& word : arr){
insertWord(r, word);
}
// Performing dfs
vector<string> output;
depthfirstsearch(r, "", output);
// Sorting strings in reverse order
sort(output.rbegin(), output.rend());
cout << "Strings in reverse dictionary order:\n";
for (const string& arr : output){
cout << arr << endl;
}
// creating memory space
delete r;
}
int main(){
vector<string> arr = {"hello", "world", "open", "ai", "c++", "programming"};
reverseOrder(arr);
return 0;
}
輸出
Strings in reverse dictionary order: world programming open hello aic ai
結論
我們已經完成了本教程，並解決了使用 Trie 列印逆字典序字串的問題。本教程中使用了 Trie 資料結構，因為它是一種將字串有效地插入樹形結構中的方法。樹的節點表示字串的字母。使用兩種方法實現了該任務，我們首先構建了一個 Trie 樹並迭代了 Trie 樹的節點。然後我們以逆字典序列印字串。在實現該任務之前，我們用一些示例演示了該問題以定義邏輯。
更新於: 2023-08-18
167 次檢視
廣告