键树(Trie),又称数字查找树,它是一棵度大于等于2的树,树中的每个结点中不是包含一个或几个关键字,而是只含有组成关键字的符号。请用类C语言或类PAscAL语言编写一个在键树T上查找关键字等于给定值KEY的记录的算法。若查找成功,返回指向该记录的指针;否

admin2019-08-01  37

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

选项

答案在Trie树上查找给定值KEY的过程如下:沿和给定值相应的指针向下,直至叶子结点,若叶子中的关键字和KEY相等,则查找成功;若分支结点中和给定值相应的指针为空,或叶子结点中的关键字和给定值不等,则查找不成功。 typedef enulTl{LEAF,BRANCH}NodeKind; //结点种类{叶子,分支} typedef struet TrieNode{ NodeKind kind; union{struet{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&&ibh.ptr[ord(KEY.ch[i])],++i); //ord求字符在字母表中的序号 if(P&&P一>kind==LEAF&&P一>lf.K==KEY)return P一>If.infoptr; //查找成功 else return null; }

解析
转载请注明原文地址:https://kaotiyun.com/show/ytCi777K
0

最新回复(0)