1

私は C でトライ順ツリー データ構造をコーディングするのに忙しくしていました。私のプログラムは .txt から一度に 1 文の単語を読み取り、各単語を重複することなくトライに格納します。次に、その文の他のすべての単語を取得し、保存された単語のサブトリーにそれらを保存します。たとえば、「オープンソースに貢献する」という文があるとします。私のコードは次のことを行います...

            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" 

単語をトライとサブトライに挿入することに成功しました。これを徹底的にテストしたので、すべてが意図したとおりに機能することを確信しています。ただし、トライとサブトライをアルファベット順に出力するアルゴリズムがわかりません。

これが私が使用している構造体です

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 です。

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);

}

これが私が理解できないコードです。トライをアルファベット順に出力する予定でしたが、出力が正しくありません。

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) );
        }


}

どんな考えでも大歓迎です!

4

1 に答える 1