Trie树; 模拟了一个简单的输入法;

2019-04-14 21:49发布生成海报

站内文章 / 模拟电子

9517 0

#include <iostream>
using namespace std;

//Trie Node structure
struct TrieNode
{
    bool isStr;
    char word[20]; //模拟拼音输入法
    TrieNode* next[26];
    TrieNode()
    {
        isStr=false;
        memset(next,0,sizeof(next));
    }
};

//Initiate Trie
void initiate(TrieNode *&root)
{
    root=new TrieNode();
}

//Insert TrieNode
void insertNode(const char *str,TrieNode *root,const char *cn)
{
    TrieNode *location=root;
    while((*str)!='/0')
    {
        if(location->next[(*str)-'a']==NULL)
        {
            TrieNode *p=new TrieNode();
            location->next[(*str)-'a']=p;
        }
        location=location->next[(*str)-'a'];
        ++str;
    }
    location->isStr=true;
    strcpy(location->word,cn);
}

//Search TrieNode
bool searchNode(const char *str,TrieNode *root)
{
    TrieNode *location=root;
    while((*str)!='/0'&&location!=NULL)
    {
        location=location->next[(*str)-'a'];
        ++str;
    }
    if((location!=NULL)&&(location->isStr))
    {
        cout<<location->word<<endl;
        return true;
    }
    else
    {
        cout<<"没有存储这个字符"<<endl;
        return false;
    }
}

//打印词库
void printTrie(TrieNode *root,char str[])
{
    if(root->isStr==true)
    {
        cout<<str<<","<<root->word<<endl;
    }
    for(int i=0;i<26;++i)
    {
        if(root->next[i]!=0)
        {
            char temp[20];
            char c[2];
            strcpy(temp,str);
            sprintf(c,"%c",i+'a');
            strcat(str,c);
            printTrie(root->next[i],str);
            strcpy(str,temp);
        }
    }
}

//销毁Trie
void destroy(TrieNode *root)
{
    for(int i=0;i<26;++i)
    {
        if(root->next[i]!=0)
        {
            destroy(root->next[i]);
        }
    }
    delete root;
}

//删除单词
void deleteStr(const char *str,TrieNode *root)
{
    //首先找到单词存储的结点,取消标记,删除对应汉字，看该结点的26个next是否全为null
    //如果不是，那么操作结束
    //如果是，那么删除这个结点，将上一个存有单词的结点与该结点之间的结点全部删除即可
    // 所以，要求在深搜的过程中，记录存有单词的preNode结点
    TrieNode *location=root;
    TrieNode *pre=0;
    int preNum;
    while((*str)!='/0'&&location!=NULL)
    {
        pre=location;
        preNum=(*str)-'a';
        location=location->next[(*str)-'a'];
        ++str;
    }
    if((location!=NULL)&&(location->isStr))
    {
        int i;
        for(i=0;i<26;++i)
        {
            if(location->next[i]!=NULL)
            {
                break;
            }
        }
        if(i!=26)
        {
            location->isStr=false;
            return;
        }
        else
        {
            delete location;
            pre->next[preNum]=NULL;
        }
    }
    else
    {
        cout<<"没有存储这个字符"<<endl;
    }
}

int main()
{
    TrieNode *root;
    initiate(root);
    int n=0;
    cout<<"输入词库，按如下格式：/n"<<
    "liang 梁/n"<<"现在开始录入词库,输入0结束录入！"<<endl;
    char pinYin[20]="1";
    char hanZi[20]="1";
    cin>>pinYin;
    cin>>hanZi;
    while((*pinYin)!='0')
    {
        insertNode(pinYin,root,hanZi);
        ++n;
        cin>>pinYin;
        cin>>hanZi;
    }
    cout<<"下面可以测试输入法了!您被允许输入"<<n<<"次拼音,拼音间空格间隔,可以开始了!"<<endl;
    char search[20];
    for(int i=0;i<n;++i)
    {
        cin>>search;
        searchNode(search,root);
    }
    cout<<endl;
    char toPrint[20];
    printTrie(root,toPrint);
    deleteStr("liang",root);
    deleteStr("dong",root);
    cout<<endl;
    printTrie(root,toPrint);
    destroy(root);
    return 0;
}

以下说明是转载的: l Trie原理 Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 l Trie性质好多人说trie的根节点不包含任何字符信息，我所习惯的trie根节点却是包含信息的，而且认为这样也方便，下面说一下它的性质 (基于本文所讨论的简单trie树) 1. 字符的种数决定每个节点的出度，即branch数组(空间换时间思想) 2. branch数组的下标代表字符相对于a的相对位置 3. 采用标记的方法确定是否为字符串。 4. 插入、查找的复杂度均为O(len),len为字符串长度

Trie树; 模拟了一个简单的输入法;

Ta的文章更多 >>

热门文章

Trie树; 模拟了一个简单的输入法;

Ta的文章 更多 >>

热门文章

举报内容

检举类型

检举原因

检举说明(必填)

打开微信“扫一扫”，打开网页后点击屏幕右上角分享按钮

Ta的文章更多 >>