#include<cstdio>
#include<cstring>
#define N 13
bool flag;

char a[N], b[N],c[N];
typedef struct node {
    char pre[N];
    char s[N];
    node *left;
    node *right;
} BST;

BST *creat_tree(BST *p, char* str1, char* str2) {
    if (p == NULL) {
        p = new BST();
        strcpy(p->pre, str1);
        strcpy(p->s, str2);
        p->left = NULL;
        p->right = NULL;
    } else {
        if (strcmp(str2, p->s) > 0) {
            p->right = creat_tree(p->right, str1, str2);
        } else {
            p->left = creat_tree(p->left, str1, str2);
        }
    }
	return p;
}

void print(BST *p, char *a) {
    if (p) {
        
        if (strcmp(p->s, a) == 0)
        {
            flag = true;
            printf("%s\n", p->pre);
            return;
        }
        else
            if (strcmp(p->s, a) > 0)
            print(p->left, a);
        else
            print(p->right, a);
    }
}

int main() {
    
    BST *root = NULL;
    while (gets(a)) {
        if(strcmp(a,"")==0)
            break;
        int i;
        for(i = 0;a[i]!=' ';i++)
            c[i] = a[i];
        i++;
        c[i] = '\0';
        int t = i;
        for(;i<strlen(a);i++)
            b[i-t] = a[i];
        b[i - t] = '\0';
        //printf("%s\n%s\n",c,b);
        root = creat_tree(root, c, b);
    }
    while (scanf("%s", a) != EOF) {
        flag = false;
        print(root, a);
        if(!flag)
            printf("eh\n");
    }
}

• 刚刚又用trie树做了一次。。。。400多MS，是不是我用指针比较慢呢，求个好的trie树算法。。。。。 (0) lgq1205 2009-08-20 02:04:14
  • 晚上用hash 235MS。。。。。好像有些大牛说有更快的hash。。。求教！～～～ (0) lgq1205 2009-08-20 10:52:44