Trie 的构建和搜索 (Insert and Search)

今天药忘吃喽~ 2022-10-28 00:46 70阅读 0赞

# **Trie 的构建和搜索 (Insert and Search)** #

//============================================================================
    // Name        : Yongqiang Cheng
    // Author      : Yongqiang Cheng
    // Version     : Version 1.0.0
    // Copyright   : Copyright (c) 2019 Yongqiang Cheng
    // Description : Hello World in C++, Ansi-style
    //============================================================================
    
    #ifndef _CRT_SECURE_NO_WARNINGS
    #define _CRT_SECURE_NO_WARNINGS
    #endif
    
    #include <stdio.h>
    
    // C++ implementation of search and insert operations on Trie 
    #define NULL 0
    
    const int MAX_TNODE_NUM = 10009;
    const int ALPHABET_SIZE = 26;
    
    // Converts key current character into index.
    // Only 'a' through 'z' and lower case.
    #define CHAR_TO_INDEX(ch) ((int)ch - (int)'a') 
    
    // Trie node 
    typedef struct TRIENODE
    {
    	struct TRIENODE *children[ALPHABET_SIZE];
    
    	// EndOfWord is 1 if the node represents end of a word 
    	int end_of_word;
    } TrieNode;
    
    TrieNode tnode_array[MAX_TNODE_NUM];
    int tnode_array_idx = 0;  // init()
    
    int init_node(TrieNode *tnode)
    {
    	int ret = 1;
    
    	tnode->end_of_word = 0;
    	for (int i = 0; i < ALPHABET_SIZE; ++i) {
    		tnode->children[i] = NULL;
    	}
    
    	return ret;
    }
    
    int init()
    {
    	int ret = 1;
    
    	tnode_array_idx = 0;
    
    	return ret;
    }
    
    // If not present, inserts key into trie.
    // If the key is prefix of trie node, just marks leaf node.
    void insert_tnode(TrieNode *head, const char *key)
    {
    	TrieNode *ptr_tnode = head;
    
    	int index;
    	int i = 0;
    	while (key[i] != NULL)
    	{
    		index = CHAR_TO_INDEX(key[i]);
    
    		if (NULL == (ptr_tnode->children)[index])
    		{
    			TrieNode *tnode = &(tnode_array[tnode_array_idx]);
    			++tnode_array_idx;
    			init_node(tnode);
    
    			(ptr_tnode->children)[index] = tnode;
    		}
    
    		ptr_tnode = (ptr_tnode->children)[index];
    		++i;
    	}
    
    	// Mark last node as leaf.
    	ptr_tnode->end_of_word = 1;
    }
    
    // Returns true if key presents in trie, else false. 
    int search_tnode(TrieNode *head, const char *key)
    {
    	TrieNode *ptr_tnode = head;
    
    	int i = 0;
    	int index;
    	while (key[i] != NULL)
    	{
    		index = CHAR_TO_INDEX(key[i]);
    
    		if (NULL == (ptr_tnode->children)[index])
    		{
    			return 0;
    		}
    
    		ptr_tnode = (ptr_tnode->children)[index];
    		++i;
    	}
    
    	return ((ptr_tnode != NULL) && (ptr_tnode->end_of_word));
    }
    
    int main()
    {
    	// Input keys (use only 'a' through 'z' and lower case)
    	const char keys[][9] = { "yong", "qiang", "cheng", "forever", "strong" };
    	const char output[][32] = { "Not present in trie.", "Present in trie." };
    
    	const int keys_size = sizeof(keys);
    	const int key0_size = sizeof(keys[0]);
    	const int key4_size = sizeof(keys[4]);
    
    	printf("keys_size = %d.\n", keys_size);
    	printf("key0_size = %d.\n", key0_size);
    	printf("key4_size = %d.\n", key4_size);
    
    	init();
    
    	TrieNode *tnode_head = &(tnode_array[tnode_array_idx]);
    	++tnode_array_idx;
    	init_node(tnode_head);
    
    	// Construct trie.
    	for (int i = 0; i < (keys_size / key0_size); i++)
    	{
    		insert_tnode(tnode_head, keys[i]);
    	}
    
    	int search_result = 0;
    	search_result = search_tnode(tnode_head, "cheng");
    	printf("%s --- %s\n", "cheng", output[search_result]);
    
    	search_result = search_tnode(tnode_head, "che");
    	printf("%s --- %s\n", "che", output[search_result]);
    
    	search_result = search_tnode(tnode_head, "yong");
    	printf("%s --- %s\n", "yong", output[search_result]);
    
    	search_result = search_tnode(tnode_head, "yongq");
    	printf("%s --- %s\n", "yongq", output[search_result]);
    
    	search_result = search_tnode(tnode_head, "qiang");
    	printf("%s --- %s\n", "qiang", output[search_result]);
    
    	search_result = search_tnode(tnode_head, "ang");
    	printf("%s --- %s\n", "ang", output[search_result]);
    
    	return 0;
    }

keys_size = 45.
    key0_size = 9.
    key4_size = 9.
    cheng --- Present in trie.
    che --- Not present in trie.
    yong --- Present in trie.
    yongq --- Not present in trie.
    qiang --- Present in trie.
    ang --- Not present in trie.
    请按任意键继续. . .

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]

## References ##

[https://www.geeksforgeeks.org/trie-insert-and-search/][https_www.geeksforgeeks.org_trie-insert-and-search]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5neXExMTY_size_16_color_FFFFFF_t_70_pic_center]: /images/20221024/9ac49d59f8844487bcf696b2a41b0cc1.png
[https_www.geeksforgeeks.org_trie-insert-and-search]: https://www.geeksforgeeks.org/trie-insert-and-search/