首页 > 试题广场 >

请用类 C 或用类 PASCAL 语言编写算法:键树,又称数

[问答题]
请用类 C 或用类 PASCAL 语言编写算法:键树,又称数字查找树。它是一棵度为 >=2 的树,树中的每个结点中不是包含一个或几个关键字,而是只含有组成关键字的符号。编写一个在键( TIRE )树 T 上查找关键字等于给定值 KEY 的记录的算法。若查找成功,返回指向该记录的指针;否则返回空指针。
解析:

[题目分析] Trie树上查找给定值KEY的过程如下:沿和给定值相应的指针向下,直至叶子结点,若叶子中的关键字和KEY相等,则查找成功;若分枝结点中和给定值相应的指针为空,或叶子结点中的关键字和给定值不等,则查找不成功。

     typedef enum{LEAF,BRANCH}NodeKind;//结点种类{叶子,分枝}     typedef struct TrieNode
        {NodeKind  kind;         union {struct{KeyType  K;Record *infoptr} lf;   //叶子结点                struct{TrieNode *ptr[27];int  num} bh;    //分枝结点                };         }TrieNode,*TrieTree;//键树类型Record  *SearchTrie(TrieTree  T,KeyType KEY)   //在Trie树T中查找关键字等于K 的记录。  {for(P=T,i=0;                           //对KEY的每个字符逐个查找        P && P->kind==BRANCH &&  i<K.num;    //*P为分枝结点        P=P->bh.ptr[ord(KEY.ch[i])],++i);//ord求字符在字母表中的序号  if(P && P->kind==LEAF && P->lf.K==KEY )return   P->lf.infoptr;//查找成功  else  return   null; }//结束SearchTrie

发表于 2017-05-16 02:24:53 回复(0)