poj 3630 Phone List (字典樹 +靜態字典樹）

poj 3630 Phone List (字典樹 +靜態字典樹）

Description

Given a list of phone numbers, determine if it is consistent in the sense that no number is the prefix of another. Let's say the phone catalogue listed these numbers:

In this case, it's not possible to call Bob, because the central would direct your call to the emergency line as soon as you had dialled the first three digits of Bob's phone number. So this list would not be consistent.

Input

The first line of input gives a single integer, 1 ≤ t ≤ 40, the number of test cases. Each test case starts with n, the number of phone numbers, on a separate line, 1 ≤ n ≤ 10000. Then follows n lines with one unique phone number on each line. A phone number is a sequence of at most ten digits.

Output

For each test case, output "YES" if the list is consistent, or "NO" otherwise.

Sample Input

2
3
911
97625999
91125426
5
113
12340
123440
12345
98346

Sample Output

NO
YES

Source

字典樹的一道經典題；話說做了這麼多到字典樹了，對字典樹的思路應該還算比較清晰了，開始看到這道題，我的思路還是先建立字典樹，在末尾加標志，判斷字典樹中間是否有標志，後來做著發現這種思路做不下去了；後來就換了種思路；這道題有兩種情況，第一種是，先輸入比較長的字符串，再輸入較短的字符串，如果是這種情況，那麼在這個過程中如果沒有新節點說明較短的字符串就是長的字符串的一個前綴；第二種情況，先輸入的是比較短的字符串，在輸入較長的字符串，如果在這種情況下，讀取到了較短字符串的結束標志，說明較短的字符串是較長字符串的一個前綴，其他的情況說明就不是公共前綴；

這道題在很多oj上都有，在hduoj 和 nyoj上直接用字典樹就可以水過，在poj上用的是靜態數組才可以過，用malloc分配的空間比較耗時；

下面是直接用字典樹水過的代碼；

#include 
#include 
#include 
typedef struct node //節點的結構體
{
    int count;//計數，標志結束
    struct node * next[10];
}node;
node * newnode() //創建新節點
{
    node *q;
    q=(node*)malloc(sizeof(node));
    q->count=0;
    for(int i=0;i<10;i++)
        q->next[i]=NULL;
    return q;
}
int build(node *T,char *s) //建立字典樹
{
   node *q;
   q=T;
   int i,k,tag,len;
   len=strlen(s);
   for(tag=i=0;inext[k]==NULL)
       {
           q->next[k]=newnode();
           tag=1;  // 產生了新節點
       }
       q=q->next[k];
       if(q->count) //遇到了結束的節點
             return 0;
   }
   q->count=1; //標記結束的節點
   if(!tag)  return 0;
   return 1;
}
int del(node *p)  //釋放字典樹空間，否則占用空間太大
{
    if(p==NULL) return 0;
    for(int i=0;i<10;i++)
        if(p->next[i]) del(p->next[i]);
       free(p);
    return 0;
}
int main()
{
    //freopen("1.txt","r",stdin);
    node *T;
    int n,m,flag;
    char s[12];
    scanf("%d",&n);
    while(n--)
    {
        T=(node *)malloc(sizeof(node));//分配頭節點
        T->count=0;
        for(int i=0;i<10;i++)
        T->next[i]=NULL;
        flag=1;
        scanf("%d",&m);
        for(int i=0;i開始用字典樹寫的時候我犯了一個很不應該的錯誤，我把頭節點放在循環的外面，然後我提交總是wa，找了好久錯誤也沒有找到，而且這樣寫導致我把del函數放在那個位置也出現了異常錯誤，後來，才明白過來，這道題是一組數據就相當於要建立一個字典樹；這種錯誤不應該犯的！

下面是用靜態數組寫的，第一次用靜態數組寫字典樹，參考了別人的代碼；
#include 
#include 
#include 
typedef struct node //節點的結構體
{
    bool end;//結束的標志
    int  a[10];
}node;
node phonelist[100000];
int x;
int flag;
void Init()
{
    flag=1;//標志
    x=0; //初始位置；
    for(int i=0;i<100000;i++)
    {
        phonelist[i].end=false;
        for(int j=0;j<10;j++)
            phonelist[i].a[j]=-1;
    }
}
int build(char *s) //建立字典樹
{
    int k,now=0,tag=0;// 初始位置
    int len=strlen(s);
    for(int i=0;i

總體的思路都是一樣的，只不過寫的方式不一樣而已，這裡我也犯了一個錯誤，我開始把結構體中的數組定義成了字符型了，我也找了好久錯誤都沒找到,浪費了好久的時間，要減少犯這種低級錯誤，算法最重要的還是思想！鍛煉自己的思維能力！！
這道題還可以用另一種方法做的，直接用快排將它們排序，進行比較；
下面的代碼是別人寫的，可以參考參考；
#include
#include
#include
#include
using namespace std;
char phone[10000][11];
int cmp(const void* a,const void* b)
{
    return strcmp((char*)a,(char*)b);
}

int main(void)
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int i,n;
        bool flag=false;
        scanf("%d",&n);
        for(i=0;i