数据结构之字典树TrieC语言版本实现

　　#include  #include  #include   /**  * 字典树  *  1、根节点（Root）不包含字符，除根节点外的每一个节点都仅包含一个字符；  *	2、从根节点到某一节点路径上所经过的字符连接起来，即为该节点对应的字符串；  *	3、任意节点的所有子节点所包含的字符都不相同；  *  4、关键词的插入和查找过程的时间复杂度均为 O(key_length)，  * 	5、空间复杂度 O(ALPHABET_SIZE * key_length * N) ，其中 N 是关键词的数量。 **/ #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＂)  // trie node typedef struct trie_node TrieNode; struct trie_node {     int value;     TrieNode* children[ALPHABET_SIZE]; };  // trie ADT typedef struct trie TRIE; struct trie {     TrieNode* root;     int count; };  // Returns new trie node (initialized to NULLs) TrieNode *getNode(void) {     TrieNode *pNode = NULL;      pNode = (TrieNode *)malloc(sizeof(TrieNode));      if (pNode)     {         int i;          pNode->value = 0;          for (i = 0; i < ALPHABET_SIZE; i++)         {             pNode->children[i] = NULL;         }     }      return pNode; }  // Initializes trie (root is dummy node) void initialize(TRIE *pTrie) {     pTrie->root = getNode();     pTrie->count = 0; }  // If not present, inserts key into trie // If the key is prefix of trie node, just marks leaf node void insert(TRIE *pTrie, char key[]) {     int level;     int length = strlen(key);     int index;     TrieNode *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 = pCrawl->children[index];     }      // mark last node as leaf     pCrawl->value = pTrie->count; }  // Returns non zero, if key presents in trie int search(TRIE *pTrie, const char *key) {     int level;     int length = strlen(key);     int index;     TrieNode *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->value); }  // Driver int main() {     // Input keys (use only ＂a＂ through ＂z＂ and lower case)     char keys[][8] = { ＂the＂, ＂a＂, ＂there＂, ＂answer＂, ＂any＂, ＂by＂, ＂bye＂, ＂their＂ };      char output[][32] = { ＂Not present in trie＂, ＂Present in trie＂ };      TRIE trie;     initialize(&trie);      // Construct trie     for (int i = 0; i < ARRAY_SIZE(keys); i++)     {         insert(&trie, keys[i]);     }      // Search for different keys     printf(＂%s --- %s ＂, ＂the＂, output[search(&trie, ＂the＂)]);     printf(＂%s --- %s ＂, ＂these＂, output[search(&trie, ＂these＂)]);     printf(＂%s --- %s ＂, ＂their＂, output[search(&trie, ＂their＂)]);     printf(＂%s --- %s ＂, ＂thaw＂, output[search(&trie, ＂thaw＂)]);      return 0; }
　　运行结果