我一直在尝试通过博客工作实现特里数据结构插入的C ++实现,其中有些事情我无法理解http://theoryofprogramming.com/2015/01/16/trie-tree -执行/
#define ALPHABETS 26
#define CASE 'a'
#define MAX_WORD_SIZE 25
using namespace std;
struct Node
{
struct Node * parent;
struct Node * children[ALPHABETS];
vector<int> occurrences;
};
// Inserts a word 'text' into the Trie Tree
// 'trieTree' and marks it's occurence as 'index'.
void InsertWord(struct Node * trieTree, char word[], int index)
{
struct Node * traverse = trieTree;
while (*word != '\0') { // Until there is something to process
if (traverse->children[*word - CASE] == NULL) {
// There is no node in 'trieTree' corresponding to this alphabet
// Allocate using calloc(), so that components are initialised
traverse->children[*word - CASE] = (struct Node *) calloc(1, sizeof(struct Node));
traverse->children[*word - CASE]->parent = traverse; // Assigning parent
}
traverse = traverse->children[*word - CASE];
++word; // The next alphabet
}
traverse->occurrences.push_back(index); // Mark the occurence of the word
}
// Prints the 'trieTree' in a Pre-Order or a DFS manner
// which automatically results in a Lexicographical Order
void LexicographicalPrint(struct Node * trieTree, vector<char> word)
{
int i;
bool noChild = true;
if (trieTree->occurrences.size() != 0) {
// Condition trie_tree->occurrences.size() != 0,
// is a neccessary and sufficient condition to
// tell if a node is associated with a word or not
vector<char>::iterator charItr = word.begin();
while (charItr != word.end()) {
printf("%c", *charItr);
++charItr;
}
printf(" -> @ index -> ");
vector<int>::iterator counter = trieTree->occurrences.begin();
// This is to print the occurences of the word
while (counter != trieTree->occurrences.end()) {
printf("%d, ", *counter);
++counter;
}
printf("\n");
}
for (i = 0; i < ALPHABETS; ++i) {
if (trieTree->children[i] != NULL) {
noChild = false;
word.push_back(CASE + i); // Select a child
// and explore everything associated with the cild
LexicographicalPrint(trieTree->children[i], word);
word.pop_back();
// Remove the alphabet as we dealt
// everything associated with it
}
}
word.pop_back();
}
int main()
{
int n, i;
vector<char> printUtil; // Utility variable to print tree
// Creating the Trie Tree using calloc
// so that the components are initialised
struct Node * trieTree = (struct Node *) calloc(1, sizeof(struct Node));
char word[MAX_WORD_SIZE];
printf("Enter the number of words-\n");
scanf("%d", &n);
for (i = 1; i <= n; ++i) {
scanf("%s", word);
InsertWord(trieTree, word, i);
}
printf("\n"); // Just to make the output more readable
LexicographicalPrint(trieTree, printUtil);
return 0;
}
我无法理解此语句的insertword
作用:
if (traverse->children[*word - CASE] == NULL)
同样,当我们在main函数中将所有元素初始化为1时,如何将其设置为null?
该函数InsertWord()
动态地将一个新单词添加到该Trie中,并且在此过程中,只要该单词的前缀与该Trie中已添加的另一个单词的前缀不匹配,就会创建新节点。
这正是您的生产线正在测试的内容。从我所看到的,traverse
是一个指向单词前缀的当前节点的指针。*word
是前缀后面单词中的下一个字符。如果与k
该单词的当前前缀相对应的节点没有一个子节点(指针为NULL
),且其标签与下一个字符相对应,则意味着我们必须k+1
为该单词的下一个前缀分配新的节点。
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句