按字母顺序打印尝试的算法 [英] algorithm to print trie alphabetically

问题描述

我一直忙于尝试用 C 编写一个 trie 有序树数据结构.我的程序一次一个地从 .txt 中读取一个句子中的单词，然后将每个单词存储在一个 trie 中，没有重复.然后它抓取该句子中的所有其他单词并将它们存储在存储的单词的子树中.例如，如果我们有以下句子:为开源做出贡献."我的代码执行以下操作...

I've been busy trying to code a trie ordered tree data structure in C. My program reads in words in a sentence one at a time from a .txt, then it stores each word in a trie without duplicates. It then grabs all other words in that sentence and stores them in a subtrie of the word that was stored. For example if we had the following sentence: "contribute to open source. " My code does the following...

            root
  ab'c'defghijklmn'o'pqr's''t'uvwxyz
    'o'           'p'   'o''o'-subtrie-> "contribute", "open", "source"
    'n'           'e'   'u'
    't'           'n'   'r'
    'r'                 'c'-subtrie->"contribute", "to", "open", 
    'i'                     
    'b'
    'u'
    't'
    'e'-subtrie-> "to", "open", "source" 

我已经成功地将单词插入到 trie 和 subtries 中.我已经对此进行了彻底的测试，所以我非常有信心一切都按照预期的方式工作.但是，我似乎无法弄清楚按字母顺序打印 trie 和 subtrie 的算法.

I have successfully been able to insert words into the trie and also the subtries. I have thoroughly tested this so I am pretty confident everything works the way it was intended to. However, i cant seem to figure out the algorithem to print the trie and subtrie alphabetically.

这是我正在使用的结构

typedef struct TrieNode
{
     // number of times this string occurs in the corpus
 int count;

// 26 TrieNode pointers, one for each letter of the alphabet
struct TrieNode *children[26];

// the co-occurrence subtrie for this string
struct TrieNode *subtrie;
} TrieNode;

这是我编写的用于插入尝试的函数.参数是特里树的根，我要插入的单词的字符数组，我要插入的单词的大小，最初 z = -1.

here is the function i wrote to insert tries. The parameters are the root of the trie, a char array of the word i want to insert, size of the word i am inserting, z = -1 initially.

TrieNode *trieInsert(TrieNode *root, char *wordArray, int sizeOfWord, int z){

    z++;
    int x1, j, index; 
    char c1 = wordArray[z];     

    //INSERT char second level 
    // do alphaNum conversions and check uper or lower case for lev1Char
    x1 = char2Num(c1);
        if(x1 >26 ){
        printf("ERRRRRRRRRRRRRRRRRRrr:line475");
    return root;
    }

    //base case
    if( sizeOfWord == z ) 
    return root; 

    //check to see if we already inserted this 
    if( root->children[x1] == NULL ){ 

    //we insert second letter 
    root->children[x1] = malloc(sizeof(struct TrieNode) );
            root->children[x1]->subtrie = NULL;
    root->children[x1]->count = 0;  
    //set children of newly malloced to null 
    for(j = 0; j < 27; j++)
        root->children[x1]->children[j] = NULL;

    }

    //increment word count on last char of word 
    if((sizeOfWord - 1) == z) 
    root->children[x1]->count++;    

    return trieInsert(root->children[x1], wordArray, sizeOfWord, z);

}

这是我无法弄清楚的代码.它是按字母顺序打印特里树，但是，它的输出不正确.

Here is the code i cant figure out. It was to print the trie alphabetically, however, it's output is incorrect.

void printTrieAlefBet( TrieNode *root ){

    int i; 

    if( root->subtrie != NULL){
        printf(" (%d)", root->count);
        return;  
    }


    for( i = 0; i < 27; i++)
        if( root->children[i] != NULL){
            printTrieAlefBet(root->children[i]);
            printf("%c", num2Char(i, 0) );
        }


}

任何想法将不胜感激！

推荐答案

开始工作.这是代码.
特别感谢 Sean Szumlanski 教授！

Got it to work. Here's the code.
Special thanks to prof Sean Szumlanski!

// Helper function called by `printTrie()`.
void printTrieHelper(TrieNode *root, char *buffer, int k)
{
    int i;
    if (root == NULL)
        return;

    if (root->count > 0)
        printf("%s (%d)\n", buffer, root->count);

    buffer[k + 1] = '\0';

    for (i = 0; i < 26; i++)
    {
        buffer[k] = 'a' + (i - 1);

        printTrieHelper(root->children[i], buffer, k + 1);
    }

    buffer[k] = '\0';
}

// If printing a subtrie, the second parameter should be 1; otherwise, 0.
void printTrie(TrieNode *root, int useSubtrieFormatting)
{
    char buffer[1026];

    if (useSubtrieFormatting)
    {
        strcpy(buffer, "- ");
        printTrieHelper(root, buffer, 2);
    }

    else
    {
        strcpy(buffer, 'and');
        printTrieHelper(root, buffer, 0);
    }
}

这篇关于按字母顺序打印尝试的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！