Trie树和查找n个词条的次数最多，指针最多

Question

所以我有这段代码，我必须把它写成主题--找出出现次数最多的n个单词，我对此有一个大致的想法，并以空集顺序函数编写它，但我对指针有一些麻烦。

无论如何，我的想法是，我有两个数组，一个用于单词，另一个用于整数，因此来自字char数组的index [i]将有x次出现，其中x与index [i]一起存储在整数数组中。

我的问题是，我不知道如何爬下这棵树，这样我就不会在递归的情况下搞砸任何事情，我只是不知道结构的指针，我不知道我应该在这个函数参数中具体放些什么:(请帮帮忙

编辑:我忘记添加代码了，呵呵，https://gist.github.com/anonymous/a20e459e2214629d3839

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0])

// Alphabet size (# of symbols)
#define ALPHABET_SIZE (26)
// Converts key current character into index
// use only 'a' through 'z' and lower case
#define CHAR_TO_INDEX(C) ((int)C - (int)'A')


char words[]={0};
int counters[1000]={0};

// trie node
typedef struct trie_node trie_node_t;
struct trie_node
{
    int counter;
    char letter;
    trie_node_t *children[ALPHABET_SIZE];
};

// trie ADT
typedef struct trie trie_t;
struct trie
{
    trie_node_t *root;
    int count;
};

// Returns new trie node (initialized to NULLs)
trie_node_t *getNode(void)
{
    trie_node_t *pNode = NULL;

    pNode = (trie_node_t *)malloc(sizeof(trie_node_t));

    if( pNode )
    {
        int i;

        pNode->counter = 0;

        for(i = 0; i < ALPHABET_SIZE; i++)
        {
            pNode->children[i] = NULL;
        }
    }

    return pNode;
}

// Initializes trie (root is dummy node)
void initialize(trie_t *pTrie)
{
    pTrie->root = getNode();
    pTrie->count = 0;
}

int wordnr=0;

void setorder(trie_node_t *pTrie, char word[])
{
    int length = strlen(word);
    char tempword[1000] = {0};


    for(int i=0; i<length; i++)
    {
        tempword[i]=word[i];
    }

    trie_node_t *pCrawl;
    pCrawl = pTrie->root;


    for(int i=0 ; i<26; i++ )
    {
        tempword[length]=pCrawl->letter;
        tempword[length+1]='\0';

        if(pCrawl->counter!=0)
        {
            for(int i=0; i<=length; i++)
                words[wordnr+i]=tempword[i];

            counters[wordnr]=pCrawl->counter;
        }

        else
        {
            pCrawl = pCrawl->children[i];
            setorder(pCrawl, tempword);
        }
    }
}

// If not present, inserts key into trie
// If the key is prefix of trie node, just marks leaf node
void insert(trie_t *pTrie, char key[])
{
    int level;
    int length = strlen(key);
    int index;
    trie_node_t *pCrawl;


    pTrie->count++;
    pCrawl = pTrie->root;

    for( level = 0; level < length; level++ )
    {
        index = CHAR_TO_INDEX(key[level]);
        if( !pCrawl->children[index] )
        {
            pCrawl->children[index] = getNode();
        }
        pCrawl->letter=key[level];
        pCrawl = pCrawl->children[index];
    }

    if(pCrawl->counter!=0)
        pCrawl->counter++;
    else
        pCrawl->counter=1;

    printf("counter slow 3= %d\n", pCrawl->counter);
}

// Returns non zero, if key presents in trie
int search(trie_t *pTrie, char key[])
{
    int level;
    int length = strlen(key);
    int index;
    trie_node_t *pCrawl;

    pCrawl = pTrie->root;

    for( level = 0; level < length; level++ )
    {
        index = CHAR_TO_INDEX(key[level]);

        if( !pCrawl->children[index] )
        {
            return 0;
        }

        pCrawl = pCrawl->children[index];
    }

    return (0 != pCrawl && pCrawl->counter);
}

// Driver
int main()
{
    // Input keys (use only 'a' through 'z' and lower case)
    char keys[][15] = {"THE", "THE", "BYE", "A", "THERE", "ANSWER", "ANSWER", "BBUWNTSMFK", "THE", "THEIR", "ANSWER", "THE", "LOL", "OMG", "WTF"};
    trie_t trie;

    char output[][20] = {"Not present in trie", "Present in trie"};

    initialize(&trie);

    // Construct trie
    for(int i = 0; i < ARRAY_SIZE(keys); i++)
    {
        insert(&trie, keys[i]);
    }

    char word[1000] = {0};
    setorder(&trie, word);

    // Search for different keys
    printf("%s --- %s\n", "THE", output[search(&trie, "THE")] );
    printf("%s --- %s\n", "THESE", output[search(&trie, "THESE")] );
    printf("%s --- %s\n", "THEIR", output[search(&trie, "THEIR")] );
    printf("%s --- %s\n", "THAW", output[search(&trie, "THAW")] );

    return 0;
}

Answer 1

我认为您的代码中有一些概念错误。基本的trie插入工作，但计数出现的情况是错误的。

首先，这里介绍的代码没有编译，因为您在trie_t和trie_node_t中混合了setorder。当您想要引用整个结构时使用trie_t，在引用该结构中的节点及其子节点(和孙辈等)时使用tire_node_t。节点。当您爬行trie时，跟踪trie_node_t节点，从trie_t的root开始。

然后，当插入节点时，在分配计数器时不需要区分零和非零的情况，只是

pCrawl->counter++;

就行了。(如果你想一想的话，你会发现递增的零会产生1，所以你只是抓住了一个所谓的特例，不需要特别处理。)你的代码没有错，只是不必要的复杂。)

好的，继续走着，然后报告单词的出现。我不太清楚在setorder中发生了什么，但同样，它看起来很复杂。去掉辅助数组counters。我认为那个数组的簿记会使你的程序分段错误。您还可以去掉letter字段的trie_node_t。您需要的所有信息都在trie节点本身及其连接中。特别是，letter是由从父节点到达此节点的路径提供的。children[0]的意思是A，children[23]的意思是X。

尝试是一种树，树最好用递归向下爬行。因此，让我们编写一个setorder的递归变体

#define INDEX_TO_CHAR(IX) ('A' + IX)

void setorder_rec(trie_node_t *pCrawl, char *str, int n)
{
    if (pCrawl == NULL) return;

    if (pCrawl->counter) {
        printf("%.*s: %d\n", n, str, pCrawl->counter);
    }

    for (int i = 0; i < ALPHABET_SIZE; i++) {
        str[n] = INDEX_TO_CHAR(i);
        setorder_rec(pCrawl->children[i], str, n + 1);
    }
}

和一个前端函数，它将定义一个临时数组并在根节点开始递归：

void setorder(trie_t *pTrie)
{
    char tempword[40] = {0};

    setorder_rec(pTrie->root, tempword, 0);
}

递归函数沿着节点遍历，将适当的字母添加到字符串中，并在找到单词时打印计数。trie的当前级别等于当前字符串长度，并且都等于当前递归深度，即函数调用自己多少次。

插入和搜索的不同之处在于，在这里，我们没有一条单一的线性路径通过一个单词给出的trie，也就是字母序列，但是我们必须遍历所有现有的子节点。

在非递归函数中，我们必须走第一条路径，重新跟踪到所有分支点，再向下走一点，等等。控制所有的爬行将是非常乏味的。在递归函数中，爬行对应于对setorder_rec的调用，爬行返回对应于来自setorder_rec的返回。

请注意，我已经创建了第二个宏，与CHAR_TO_INDEX相反。在搜索trie时，我们需要从一个字符中知道索引。当我们以非条件的方式行走所有的分支时，我们需要能够从子索引中重建一个单词的字符。

如果您不想只打印计数，而是希望创建一个数组，则可以使用全局索引，如您的示例所示。但是你必须把单词本身和计数一起存储，也许是在第二个数组中，也许是在一个特殊的结构中。

最后一点:您的程序没有避免计算错误的指数。如果添加的单词不是大写字母、行CAN'T或LOS ANGELES，则会出现访问冲突。