V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
bigshot
V2EX  ›  程序员

搜索二叉树应用——简单字典实现

  •  
  •   bigshot · 2018-02-27 19:49:12 +08:00 · 1672 次点击
    这是一个创建于 2459 天前的主题,其中的信息可能已经有所发展或是发生改变。

    搜索二叉树基本概念请看上篇博客 这两个问题都是典型的 K ( key ) V ( value )问题,我们用 KV 算法解决。

    1. 判断一个单词是否拼写正确:假设把所有单词都按照搜索树的性质插入到搜索二叉树中,我们判断一个单词拼写是否正确就是在树中查找该单词是否存在(查找 key 是否存在)。

    结构声明下

    typedef char* KeyType;
    
    typedef struct BSTreeNode 
    {
        struct BSTreeNode *_left;
        struct BSTreeNode *_right;
    
        KeyType _key;
    }BSTreeNode;
    

    插入,查找函数代码如下:

    int BSTreeNodeInsertR(BSTreeNode **tree,KeyType key) //搜索树的插入
    {
        int tmp = 0;
        if(*tree == NULL)
        {
            *tree = BuyTreeNode(key);
            return 0;
        }
        
        tmp  = strcmp((*tree)->_key,key);
        if (tmp>0)
            return BSTreeNodeInsertR(&(*tree)->_left,key);
        else if (tmp<0)
            return BSTreeNodeInsertR(&(*tree)->_right,key);
        else
            return -1;
    }
    
    BSTreeNode *BSTreeNodeFindR(BSTreeNode *tree,KeyType const key) //查找
    {
        int tmp = 0;
        if (!tree)
            return NULL;
        
        tmp = strcmp(tree->_key,key);
        if (tmp > 0)
            return BSTreeNodeFindR(tree->_left,key);
        else if (tmp < 0)
            return BSTreeNodeFindR(tree->_right,key);
        else
            return tree;
    }
    

    测试代码:

    void TestApplication()
    {
        BSTreeNode *tree = NULL;
    
        BSTreeNodeInsertR(&tree,"hello");
        BSTreeNodeInsertR(&tree,"world");
        BSTreeNodeInsertR(&tree,"int");
        BSTreeNodeInsertR(&tree,"char");
        BSTreeNodeInsertR(&tree,"float");
        BSTreeNodeInsertR(&tree,"double");
    
        printf("%s \n", BSTreeNodeFindR(tree,"char")->_key);
        printf("%s \n", BSTreeNodeFindR(tree,"double")->_key);
        printf("%s \n", BSTreeNodeFindR(tree,"int")->_key);
        printf("%s \n", BSTreeNodeFindR(tree,"float")->_key);
        printf("%s \n", BSTreeNodeFindR(tree,"hello")->_key);
        printf("%s \n", BSTreeNodeFindR(tree,"world")->_key);
        printf("%p \n", BSTreeNodeFindR(tree,"chars"));
        printf("%p \n", BSTreeNodeFindR(tree,"str"));
    }
    

    测试结果: 检查单词是否拼写正确 2. 请模拟实现一个简单的字典(简单的中英文字典)

    结构构建

    typedef char* KeyType;
    typedef int ValueType;
    
    
    typedef struct BSTreeNode 
    {
        struct BSTreeNode *_left;
        struct BSTreeNode *_right;
    
        KeyType _key;
        ValueType _count;
    }BSTreeNode;
    

    查找函数与上面相同,插入函数有所改变。

    int BSTreeNodeInsertR(BSTreeNode **tree,KeyType key, ValueType value) //搜索树的插入
    {
        int tmp = 0;
        if(*tree == NULL)
        {
            *tree = BuyTreeNode(key,value);
            return 0;
        }
        
        tmp  = strcmp((*tree)->_key,key);
        if (tmp>0)
            return BSTreeNodeInsertR(&(*tree)->_left,key,value);
        else if (tmp<0)
            return BSTreeNodeInsertR(&(*tree)->_right,key,value);
        else
            return -1;
    }
    

    测试代码:

    void test()
    {
    	BSTreeNode *tree = NULL;
        BSTreeNodeInsertR(&tree,"hello","你好");
        BSTreeNodeInsertR(&tree,"world","世界");
        BSTreeNodeInsertR(&tree,"char","字符");
        BSTreeNodeInsertR(&tree,"int","整形");
        BSTreeNodeInsertR(&tree,"float","浮点型");
    
        printf("%s \n", BSTreeNodeFindR(tree,"char")->_value);
        printf("%s \n", BSTreeNodeFindR(tree,"int")->_value);
        printf("%s \n", BSTreeNodeFindR(tree,"float")->_value);
        printf("%s \n", BSTreeNodeFindR(tree,"hello")->_value);
        printf("%s \n", BSTreeNodeFindR(tree,"world")->_value);
        printf("%p \n", BSTreeNodeFindR(tree,"double"));
    }
    

    测试结果 中英文字典

    构建测试案例尽量构建全面,防止特殊情况被忽略。

    目前尚无回复
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5696 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 06:27 · PVG 14:27 · LAX 22:27 · JFK 01:27
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.