• 實現(xiàn)了一個C語言寫的簡單字典樹，節(jié)點之間跳轉(zhuǎn)央串，用鏈表實現(xiàn)
• 節(jié)點定義

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

• 插入節(jié)點

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é)點

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

        }
    }
}

• 測試代碼

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;

}

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