Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

简单的字典树操作!

Posted by 1214011013 at 2014-09-27 14:49:27 on Problem 2503
#include <iostream>
#include <stdio.h>
#include <string>
#include <map>
#include <string.h>
using namespace std;


//字典树

struct Trie
{
    Trie * next[26];
    char text[15];
    int flag;
    Trie()
    {
        for(int i = 0; i < 26; i++)
        {
            next[i] = NULL;
            flag = 0;
            memset(text,0,sizeof(text));
        }
    }
};
Trie *root;
void Insert(char msg[],char text[])
{
    //printf("%s %s\n",msg,text);
    Trie *cur = root;
    int k;
    int i = 0;
    while(msg[i])
    {
        k = msg[i] - 'a';
        if(cur->next[k] == NULL)
            cur->next[k] = new Trie();
        cur = cur->next[k];
        i++;
    }
    cur->flag = 0;
    strcpy(cur->text,text);
}
void search_Trie(char msg[])
{
    Trie * cur = root;
    int k;
    int i = 0;
    while(msg[i])
    {
        k = msg[i] - 'a';
        if(cur->next[k] == NULL)
        {
            printf("eh\n");
            return;
        }
        cur = cur->next[k];
        i++;
    }
    if(cur->flag == 0)
    printf("%s\n",cur->text);
    else
    printf("eh\n");
}
void Delete(Trie *root)
{
    for(int i = 0; i < 26; i++)
    if(root->next[i] != NULL)
        Delete(root->next[i]);
    delete root;
}

int main()
{
    char msg[30];
    char eng[15];
    char fore[15];
    int i,j,k;
    root = new Trie();
    while(gets(msg) && strlen(msg) != 0)
    {
        memset(fore,0,sizeof(fore));
        memset(eng,0,sizeof(eng));
        for(i=0;;i++)
        {
            if(msg[i] == ' ')
                break;
        }
        msg[i] = '\0';
        strcat(eng,msg);
        strcpy(fore,&msg[i+1]);
        Insert(fore,eng);
    }
    while(scanf("%s",fore) != EOF)
    {
        search_Trie(fore);
    }
    Delete(root);
    return 0;
}



Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator