/* bo9-6.c 動態查找表(Trie鍵樹)的基本操作 */
 Status InitDSTable(TrieTree *T)
 { /* 操作結果: 構造一個空的Trie鍵樹T */
   *T=NULL;
   return OK;
 }

 void DestroyDSTable(TrieTree *T)
 { /* 初始條件: Trie樹T存在。操作結果: 銷毀Trie樹T */
   int i;
   if(*T) /* 非空樹 */
   {
     for(i=0;i<LENGTH;i++)
       if((*T)->kind==BRANCH&&(*T)->a.bh.ptr[i]) /* 第i個結點不空 */
         if((*T)->a.bh.ptr[i]->kind==BRANCH) /* 是子樹 */
           DestroyDSTable(&(*T)->a.bh.ptr[i]);
         else /* 是葉子 */
         {
           free((*T)->a.bh.ptr[i]);
           (*T)->a.bh.ptr[i]=NULL;
         }
     free(*T); /* 釋放根結點 */
     *T=NULL; /* 空指針賦0 */
   }
 }

 int ord(char c)
 {
   c=toupper(c);
   if(c>='A'&&c<='Z')
     return c-'A'+1; /* 英文字母返回其在字母表中的序號 */
   else
     return 0; /* 其余字符返回0 */
 }

 Record *SearchTrie(TrieTree T,KeysType K)
 { /* 在鍵樹T中查找關鍵字等于K的記錄。算法9.16 */
   TrieTree p;
   int i;
   for(p=T,i=0;p&&p->kind==BRANCH&&i<K.num;p=p->a.bh.ptr[ord(K.ch[i])],++i);
   /* 對K的每個字符逐個查找,*p為分支結點,ord()求字符在字母表中序號 */
   if(p&&p->kind==LEAF&&p->a.lf.K.num==K.num&&EQ(p->a.lf.K.ch,K.ch)) /* 查找成功 */
     return p->a.lf.infoptr;
   else /* 查找不成功 */
     return NULL;
 }

 void InsertTrie(TrieTree *T,Record *r)
 { /* 初始條件: Trie鍵樹T存在，r為待插入的數據元素的指針 */
   /* 操作結果: 若T中不存在其關鍵字等于(*r).key.ch的數據元素， */
   /*           則按關鍵字順序插r到T中 */
   TrieTree p,q,ap;
   int i=0,j;
   KeysType K1,K=r->key;
   if(!*T) /* 空樹 */
   {
     *T=(TrieTree)malloc(sizeof(TrieNode));
     (*T)->kind=BRANCH;
     for(i=0;i<LENGTH;i++) /* 指針量賦初值NULL */
       (*T)->a.bh.ptr[i]=NULL;
     p=(*T)->a.bh.ptr[ord(K.ch[0])]=(TrieTree)malloc(sizeof(TrieNode));
     p->kind=LEAF;
     p->a.lf.K=K;
     p->a.lf.infoptr=r;
   }
   else /* 非空樹 */
   {
     for(p=*T,i=0;p&&p->kind==BRANCH&&i<K.num;++i)
     {
       q=p;
       p=p->a.bh.ptr[ord(K.ch[i])];
     }
     i--;
     if(p&&p->kind==LEAF&&p->a.lf.K.num==K.num&&EQ(p->a.lf.K.ch,K.ch)) /* T中存在該關鍵字 */
       return;
     else /* T中不存在該關鍵字,插入之 */
     {
       if(!p) /* 分支空 */
       {
         p=q->a.bh.ptr[ord(K.ch[i])]=(TrieTree)malloc(sizeof(TrieNode));
         p->kind=LEAF;
         p->a.lf.K=K;
         p->a.lf.infoptr=r;
       }
       else if(p->kind==LEAF) /* 有不完全相同的葉子 */
       {
         K1=p->a.lf.K;
         do
	 {
           ap=q->a.bh.ptr[ord(K.ch[i])]=(TrieTree)malloc(sizeof(TrieNode));
           ap->kind=BRANCH;
           for(j=0;j<LENGTH;j++) /* 指針量賦初值NULL */
             ap->a.bh.ptr[j]=NULL;
           q=ap;
           i++;
         }while(ord(K.ch[i])==ord(K1.ch[i]));
         q->a.bh.ptr[ord(K1.ch[i])]=p;
         p=q->a.bh.ptr[ord(K.ch[i])]=(TrieTree)malloc(sizeof(TrieNode));
         p->kind=LEAF;
         p->a.lf.K=K;
         p->a.lf.infoptr=r;
       }
     }
   }
 }

 void TraverseDSTable(TrieTree T,Status(*Vi)(Record*))
 { /* 初始條件: Trie鍵樹T存在，Vi是對記錄指針操作的應用函數 */
   /* 操作結果: 按關鍵字的順序輸出關鍵字及其對應的記錄 */
   TrieTree p;
   int i;
   if(T)
   {
     for(i=0;i<LENGTH;i++)
     {
       p=T->a.bh.ptr[i];
       if(p&&p->kind==LEAF)
         Vi(p->a.lf.infoptr);
       else if(p&&p->kind==BRANCH)
         TraverseDSTable(p,Vi);
     }
   }
 }