字典树-trie

时间：2010-10-27 来源：superbin

描述：将火星文翻译成英文。

反思：好久以前做的，现在又拿来写了个字典树，递归比非递归确实慢，一个小错误导致wa数次。

代码

#include <stdio.h>
#include <string.h>
#include <ctype.h>

struct Node {
    Node *t[26];
    char mar[13];
    Node () {
        for (int i=0; i<26; i++)
            t[i] = NULL;
        mar[0] = '\0'; //key '\0' 写成了 '/0'
    }
};

Node *head;

void build(Node *p, char *c1, char *c2) {
    if (*c1 == '\0') {
        strcpy(p->mar, c2);
        return;
    }
    int k = *c1-'a';
    if (p->t[k] == NULL) {
        p->t[k] = new Node;
    }
    build(p->t[k], c1+1, c2);
}

void find(Node *p, char *c1, char *c2) {
    if (*c1 == '\0') {
        if (p->mar[0] != '\0')
            strcpy(c2, p->mar);
        return;
    }
    int k = *c1-'a';
    if (p->t[k] != NULL) {
        find(p->t[k], c1+1, c2);
    }
}

int main()
{
    char c1[20], c2[20], c[3010];
//    freopen("datain", "r", stdin);
//    freopen("dataout", "w", stdout);
    while (scanf("%s", c1) != EOF) {
        head = new Node;
        while (scanf("%s", c1)) {

            if (strcmp(c1,"END") == 0) break;
            scanf("%s", c2);

            build(head, c2, c1);
        }
        scanf("%s%*c", c1);
        while (gets(c)) {
            if (strcmp(c, "END") == 0) break;
            int len = strlen(c);
            for (int i=0; i<len; ) {
                int j = 0;
                while (i<len && isalpha(c[i])) {
                    c1[j++] = c[i++];
                }
                if (j>0) {
                    c1[j] = '\0';
                    c2[0] = '\0';
                    find(head, c1, c2);
                    if (c2[0] != '\0') {
                        printf("%s", c2);
                    }else {
                        printf("%s", c1);
                    }
                }else {
                    printf("%c", c[i]);
                    i++;
                }
            }
            printf("\n");
        }
    }
    return 0;
}