《数据结构与程序设计》由会员分享，可在线阅读，更多相关《数据结构与程序设计（20页珍藏版）》请在金锄头文库上搜索。
1、9/6/2024数据结构与程序设计 教师：鲍钰1数据结构与程序设计(29)教师：鲍钰9/6/2024数据结构与程序设计 教师：鲍钰2Chapter 11MULTIWAY TREES9/6/2024数据结构与程序设计 教师：鲍钰3Tries:Lexicographic Search TreesP531DEFINITION A trie of order m is either empty or consists of an ordered sequence of exactly m tries of order m.9/6/2024数据结构与程序设计 教师：鲍钰49/6/2024数据结构与程序设
2、计 教师：鲍钰5C+ Trie DeclarationsEvery Record has a Key that is an alphanumeric string.Method char key_letter(int position) returns the character in the given position of the key or returns a NONE, if the key has length less than position.Auxiliary function int alphabetic_order(char symbol) returns the a
3、lphabetic position of the character symbol, or 27 for nonblank, nonalphabetic characters, or 0 for blank, NONE characters.9/6/2024数据结构与程序设计 教师：鲍钰6Trie-Key#include String.h#include iostream.hconst int key_size = 10;class Key char strkey_size;public:Key (char s);char * the_key( ) const;char key_letter
4、(int position) const;9/6/2024数据结构与程序设计 教师：鲍钰7Trie-Key#include Key.hKey:Key(char s)for(int i=0; i=strlen(s); i+)stri=si;char * Key:the_key() constreturn (char *)str;char Key:key_letter (int position) constif(positionstrlen(str) return strposition;else return 0;9/6/2024数据结构与程序设计 教师：鲍钰8Trie-Record#incl
5、ude Key.hclass Recordpublic:operator Key( ); / implicit conversion from Record to Key .Record(char s=);char * the_key() const;char key_letter(int position) const;private:char strkey_size;ostream & operator (ostream &output, Record &x);9/6/2024数据结构与程序设计 教师：鲍钰9Trie-Record#include Record.hRecord:Record
6、(char s)for(int i=0; i=strlen(s); i+)stri=si;Record:operator Key( )Key tmp(str);9/6/2024数据结构与程序设计 教师：鲍钰10Trie-Recordchar Record:key_letter(int position) constif(positionstrlen(str) return strposition;else return 0;char * Record:the_key() constreturn (char *)str;ostream & operator (ostream &output, R
7、ecord &x)outputx.the_key();output ;return output;9/6/2024数据结构与程序设计 教师：鲍钰11TrieTrie_node#include Record.hconst int num_chars = 28;struct Trie_node / data membersRecord * data;Trie_node * branchnum_chars;/ constructorsTrie_node( );9/6/2024数据结构与程序设计 教师：鲍钰12TrieTrie_node#include Trie_node.hTrie_node:Tri
8、e_node() data = NULL;for(int i=0; inum_chars; i+)branchi = NULL;9/6/2024数据结构与程序设计 教师：鲍钰13Trie#include Trie_node.henum Error_codenot_present, overflow, underflow, duplicate_error, success;class Trie public: / Add method prototypes here.Error_code insert(const Record &new_entry);Error_code trie_search
9、(const Key &target, Record &x) const;Trie();private: / data membersTrie_node *root;int alphabetic_order(char c);9/6/2024数据结构与程序设计 教师：鲍钰14Trie#include Trie.hint alphabetic_order(char c)/* Post: The function returns the alphabetic position of character c , or it returns 0 if the character is blank. */
10、if (c = | c = 0) return 0;if (a = c & c = z) return c - a + 1;if (A = c & c branchnext_position = NULL)location-branchnext_position = new Trie_node;location = location-branchnext_position;position+; / At this point, we have tested for all nonblank characters of new entry .if (location-data != NULL)
11、result = duplicate_error;else location-data = new Record(new_entry);return result;9/6/2024数据结构与程序设计 教师：鲍钰16TrieError_code Trie : trie_search(const Key &target, Record &x) const/* Post: If the search is successful, a code of success is returned, and the outputparameter x is set as a copy of the Trie
12、s record that holdstarget . Otherwise,a code of not_present is returned.Uses: Methods of classKey . */int position = 0;char next_char;Trie_node *location = root;while (location != NULL &(next_char = target.key_letter(position) != 0) / Terminate search for a NULL location or a blank in the target.loc
13、ation = location-branchalphabetic_order(next_char);/ Move down the appropriate branch of the trie.position+;/ Move to the next character of the target. if (location != NULL & location-data != NULL) x = *(location-data);return success; elsereturn not_present; 9/6/2024数据结构与程序设计 教师：鲍钰17Main#include Tri
14、e.hvoid main()Trie dict;dict.insert(Record(a);dict.insert(Record(aa);dict.insert(Record(ab);dict.insert(Record(ac);dict.insert(Record(aba);dict.insert(Record(abc);dict.insert(Record(abba);dict.insert(Record(abaca); dict.insert(Record(baba);dict.insert(Record(baa);dict.insert(Record(bab);dict.insert(
15、Record(bac);dict.insert(Record(ba);dict.insert(Record(b);9/6/2024数据结构与程序设计 教师：鲍钰18Maindict.insert(Record(caaba);dict.insert(Record(ca);dict.insert(Record(c);dict.insert(Record(ca);dict.insert(Record(cab);dict.insert(Record(caba);Record tmp=;dict.trie_search(Key(abaca), tmp);couttmp;tmp=;dict.trie_search(Key(abac), tmp);couttmp;tmp=;dict.trie_search(Key(bag), tmp);couttmp;9/6/2024数据结构与程序设计 教师：鲍钰19Resultabaca9/6/2024数据结构与程序设计 教师：鲍钰20Trie目录目录Trie下例程下例程
