极客笔记C++ 使用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树的节点。然后我们按照倒序字典顺序打印了字符串。在实现任务之前，我们通过一些示例展示了问题并定义了逻辑。