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 yuest at 2009-08-22 11:34:38 on Problem 3630
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define ALPHABET 10
#define STARTLETTER '0'
typedef struct trie
{
    int num;
    int isWord;
    struct trie * next[ALPHABET];
} TRIE;

TRIE staticTrie[100010];
TRIE * pNewTrie;
TRIE * newTrie()
{
    TRIE * t = pNewTrie++;
    t->num = 0;
    t->isWord = 0;
    int i;
    for (i=0; i<ALPHABET; i++)
        t->next[i] = NULL;
    return t;
}

int add(char * word)
{
    int len = strlen(word);
    TRIE * loc = staticTrie;
    int i, n;
    for (i = 0; i < len; i++)
    {
        n = word[i] - STARTLETTER;
        if (n < 0 || n >= ALPHABET)
            return 0;
        if (loc->next[n] == NULL)
            loc->next[n] = newTrie();
        loc = loc->next[n];
        if (i < len-1 && loc->isWord)//如果后面还有数字而到这一位已经是一个电话号码了
            return 0;
    }
    loc->isWord = 1;
    if (i)
        staticTrie->num++;
    if (loc->num > 1)//说明这个单词是其它词的前缀
        return 0;
    return 1;
}

int main()
{
    TRIE * t;
    char s[11];
    int casenum, n;
    int isConsistent;
    scanf("%d", &casenum);
    while(casenum--)
    {
        scanf("%d", &n);
        isConsistent = 1;
        pNewTrie = staticTrie;
        t = newTrie();
        while(n--)
        {
            scanf("%s", s);
            if (isConsistent)
                isConsistent = add(s);
        }
        if (isConsistent)
            printf("YES\n");
        else
            printf("NO\n");
    }

    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