hdu 1305 还是字典树

#include<cstdio>

#include<iostream>

#include<string>

#include<cstdlib>

#define maxn 2

#include<queue>

using namespace std;

struct Tri

{

    Tri*next[maxn];

    int num;

};

Tri *root;

void buildTri(string ss)//建树的过程是一个动态的过程 动插的过程

{

    Tri *p=root,*q;

    for(int i=;i<ss.size();i++)

    {

        int id=ss[i]-'0';

        if(p->next[id]==NULL)

        {

            q=(Tri*)malloc(sizeof(Tri));

            q->num=;

            for(int j=;j<maxn;j++) q->next[j]=NULL;

            p->next[id]=q;

            p=p->next[id];

        }

        else p=p->next[id],p->num++;

    }

    p->num=-;// 作为结束的标志

}

int findTri(string ss)

{

    Tri *p=root,*q;

    for(int i=;i<ss.size();i++)

    {

        int id=ss[i]-'0';

        p=p->next[id];

        if(p==NULL) return;

        if(p->num==-) return -;

    }

    return -;

}

void del(Tri *root)

{

    Tri *zz=root;

    if(zz==NULL) return;

    for(int i=;i<maxn;i++)

    {

        if(zz->next[i]!=NULL) del(zz->next[i]);

    }

    free(zz);

}

int main()

{

    int Case=;

    string ss;

    queue<string> fuck;

    while(cin>>ss)

    {

        if(ss=="9")

        {

            int flag=;

            root=(Tri *)malloc(sizeof(Tri));

            for(int i=;i<maxn;i++) root->next[i]=NULL;

            root->num=;

            while(!fuck.empty())

            {

                string temp;

                temp=fuck.front();

                fuck.pop();

                if(findTri(temp)==-)

                {

                    flag=;

                    break;

                }

                buildTri(temp);

            }

            if(flag) printf("Set %d is immediately decodable\n",++Case);

            else printf("Set %d is not immediately decodable\n",++Case);

            del(root);

            continue;

        }

        fuck.push(ss);

    }

    return;

}
巴特西

hdu 1305 还是字典树

最新文章

热门文章
