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

admin2019-08-01  37

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

选项

答案在Trie树上查找给定值KEY的过程如下:沿和给定值相应的指针向下,直至叶子结点,若叶子中的关键字和KEY相等,则查找成功;若分支结点中和给定值相应的指针为空,或叶子结点中的关键字和给定值不等,则查找不成功。 typedef enum{LEAF,BRANCH}NodeKind; //结点种类{叶子,分支} typedef struct TrieNode{ 2NodeKind kind; 2union{strnct{KeyType K;Record *infoptr}If; //Dr子结点 22struct{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/YNCi777K
0

最新回复(0)