[UVa] 10815 - Andy's First Dictionary

這題我採用 Trienode的資料結構，直接做字典順序輸出

詳細請參閱 http://en.wikipedia.org/wiki/Trie 

 http://openhome.cc/Gossip/CGossip/

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

char input[300]={'\0'};
char words[6000][300]={'\0'};

//建構Tire字典樹
struct TrieNode{
  TrieNode* l[128]; //128種字元，皆為Trienode型別，以l陣列儲存
  int n; //計算字串出現次數，0則代表沒有這個字
  TrieNode() //Trienode函數
  {
    memset(l, 0, sizeof(TrieNode*) *128); //把l陣列裡的指標都設為0
    n = 0;
  }
}*root = new TrieNode(); //root為第一個TrieNode

//插入字串
void add(char* s)
{
 TrieNode* p = root; //p為指向root節點的指標，
 for (; *s; ++s) // *s= s指向的變數，若尚有字元，則++s
 {   //若l陣列中第s欄位的指標不存在，則新增一節點
  if ( !(p->l[*s]) ) p->l[*s] = new TrieNode();
  p = p->l[*s];
 }
 //p->n++;
 p->n=1; //1代表有此單次，因只要輸出一次，所以p->n設為1即可
}

char w[300+1];   // 300個字的字串
void traversal(TrieNode* p, char* s) //s指標指向w
{
 *s = '\0';  
 for (int i=0; i<(p->n); ++i)
  printf("%s\n",w);

 for (int i=0; i<128; ++i)
  if (p->l[i]) //若l[i]存在有指標
  {
   *s = i; //s指向的變數設為i
   traversal(p->l[i], s+1); //往下一個Trienode節點探詢，s指標往w的下一位前進
  }
}

//釋放記憶體空間
void release(TrieNode* p = root)
{
 for (int i=0; i<26; ++i)
  if (p->l[i])
   release(p->l[i]);
 delete p;
}



int main(){
  freopen("input.txt", "r", stdin);
  //printf("%d\n", sizeof(TrieNode*));
  while(fgets(input, sizeof(input), stdin) ){  /*讀到EOF會自動跳出*/
    //gets(input);
 
 int len=strlen(input); // len = input長度
 for(int i=0;i<len;i++){
   if(!isalpha(input[i])){
     input[i]=' ';   //去除非字母字元
      }
      //大寫換小寫
   if(input[i]>='A'&&input[i]<='Z')input[i]+=32;
    }
 
 char word[300]={'\0'};
 int start_read=0, flag=0;
 for(int i=0;i<len;i++){
   ////該字元為字母且前一個不是字元，或該字元為列首時，start_read=1
   if(isalpha(input[i]) && (!isalpha(input[i-1]) ||i==0) ){ 
     start_read=1;
  flag=0;
   }
   if(start_read==1){ //start_read維持在1時，字元存入word陣列
     word[flag]=input[i];
  flag++;
   }
   if(isalpha(input[i])&&!isalpha(input[i+1])){
     start_read=0;
  flag=0;
  //puts(word);
  add(word); //插入到Trie
  
  //清空陣列
  memset(word,'\0',sizeof(word));
  //for(int j=0;j<300;j++)word[j]='\0';
   }
   
 }
 //puts(input);
 //system("PAUSE");
  }
  
  traversal(root,w);
  
  release(root);
  return 0;
}