// bo9-6.cpp 動態查找表(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->bh.ptr[i]) // 第i個結點不空
         if(T->bh.ptr[i]->kind==BRANCH) // 是子樹
           DestroyDSTable(T->bh.ptr[i]);
         else // 是葉子
         {
           free(T->bh.ptr[i]);
           T->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->bh.ptr[ord(K.ch[i])],++i);
   // 對K的每個字符逐個查找,*p為分支結點,ord()求字符在字母表中序號
   if(p&&p->kind==LEAF&&p->lf.K.num==K.num&&EQ(p->lf.K.ch,K.ch)) // 查找成功
     return p->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->bh.ptr[i]=NULL;
     p=T->bh.ptr[ord(K.ch[0])]=(TrieTree)malloc(sizeof(TrieNode));
     p->kind=LEAF;
     p->lf.K=K;
     p->lf.infoptr=r;
   }
   else // 非空樹
   {
     for(p=T,i=0;p&&p->kind==BRANCH&&i<K.num;++i)
     {
       q=p;
       p=p->bh.ptr[ord(K.ch[i])];
     }
     i--;
     if(p&&p->kind==LEAF&&p->lf.K.num==K.num&&EQ(p->lf.K.ch,K.ch)) // T中存在該關鍵字
       return;
     else // T中不存在該關鍵字,插入之
     {
       if(!p) // 分支空
       {
         p=q->bh.ptr[ord(K.ch[i])]=(TrieTree)malloc(sizeof(TrieNode));
         p->kind=LEAF;
         p->lf.K=K;
         p->lf.infoptr=r;
       }
       else if(p->kind==LEAF) // 有不完全相同的葉子
       {
         K1=p->lf.K;
         do
	 {
           ap=q->bh.ptr[ord(K.ch[i])]=(TrieTree)malloc(sizeof(TrieNode));
           ap->kind=BRANCH;
           for(j=0;j<LENGTH;j++) // 指針量賦初值NULL
             ap->bh.ptr[j]=NULL;
           q=ap;
           i++;
         }while(ord(K.ch[i])==ord(K1.ch[i]));
         q->bh.ptr[ord(K1.ch[i])]=p;
         p=q->bh.ptr[ord(K.ch[i])]=(TrieTree)malloc(sizeof(TrieNode));
         p->kind=LEAF;
         p->lf.K=K;
         p->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->bh.ptr[i];
       if(p&&p->kind==LEAF)
         Vi(p->lf.infoptr);
       else if(p&&p->kind==BRANCH)
         TraverseDSTable(p,Vi);
     }
   }
 }