数据结构
网络
关系数据库管理系统
操作系统
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 次查看
广告