• 實(shí)現(xiàn)了一個(gè)C語(yǔ)言寫(xiě)的簡(jiǎn)單字典樹(shù)，節(jié)點(diǎn)之間跳轉(zhuǎn)，用鏈表實(shí)現(xiàn)
• 節(jié)點(diǎn)定義

typedef struct _tire_node
{
   struct _tire_node *word[MAX_ASCII_VALUE];
   int value;
}TireNode;

• 插入節(jié)點(diǎn)

void InsertNode(TireNode *node, char * key, int value)
{
    int i = 0;
    for ( i = 0; i < strlen(key); i++)
    {
        if (node->word[key[i]] == NULL)
        {
            node->word[key[i]] = (TireNode *)malloc(sizeof(TireNode));
            nodecount++;
        }

        if (i == strlen(key) - 1)
        {
            node->word[key[i]]->value = value;
        }

        node = node->word[key[i]];
    }
}

• 查找節(jié)點(diǎn)

int SearchNode(TireNode *node, char *key)
{
    int i = 0;;
    for (i = 0 ; i < strlen(key); i++)
    {
        if (node == NULL)
        {
            return 0;
        }

        if (node->word[key[i]] == NULL)
        {
            return 0;
        }
        else
        {
            if (node->word[key[i]]->value > 0)
            {
                return  node->word[key[i]]->value;
            }
            else
            {
                node = node->word[key[i]];
            }

        }
    }
}

• 測(cè)試代碼

int main()
{
    int i = 0;                            
    char *httphead[] = {                                                                                                                 
          "Uri=",          
          "Host=",         
          "Referer=",   
          "User-Agent=",
          "Pragma=",       
          "x-online-host=",
          "X-Requested-With=",
          "c_version=", 
          "X-Umeng-Sdk=",
          "Client-Agent=",
          "appname=",   
          "DPUName=",   
          "actionlocation=",
          "Cookie=",       
          "http.useragent="
     };

     TireNode *root = (TireNode *)malloc(sizeof(TireNode));
    memset(root, 0, sizeof(TireNode));

    TireNode *node = root;
    for (i = 0; i < 15; i++)
    {
        InsertNode(node, httphead[i], i +  1);
    }


    for(i = 14; i >= 0; i--)
    {
        int ret = 0;
        node = root;
        ret = SearchNode(root,httphead[i]);
        if (ret > 0)
        {
            printf("%d\n", ret);
        }
    }
    printf("nodenum is %u, size is :%u KB\n", nodecount, nodecount * sizeof(TireNode)/1024);

    return 0;

}

• 實(shí)現(xiàn)的很粗糙， 單純的字典樹(shù)，節(jié)點(diǎn)消耗了太多了內(nèi)存，不適于實(shí)際應(yīng)用，后面會(huì)接著給出字典樹(shù)的壓縮版本，前綴樹(shù)，后綴樹(shù)，檢索樹(shù)等