数据结构与程序设计

数据结构与程序设计(29)教师：鲍钰ybao@4/21/20231.Chapter11MULTIWAYTREES4/21/20232.Tries:

LexicographicSearchTrees

P531DEFINITIONAtrieofordermiseitheremptyorconsistsofanorderedsequenceofexactlymtriesoforderm.4/21/20233.4/21/20234.C++TrieDeclarationsEveryRecordhasaKeythatisanalphanumericstring.Methodcharkey_letter(intposition)returnsthecharacterinthegivenpositionofthekeyorreturnsaNONE,ifthekeyhaslengthlessthanposition.Auxiliaryfunctionintalphabetic_order(charsymbol)returnsthealphabeticpositionofthecharactersymbol,or27fornonblank,nonalphabeticcharacters,or0forblank,NONEcharacters.4/21/20235.Trie--Key#include"String.h"#include"iostream.h"constintkey_size=10;classKey{ charstr[key_size];public: Key(chars[]); char*the_key()const; charkey_letter(intposition)const;};4/21/20236.Trie--Key#include"Key.h"Key::Key(chars[]){ for(inti=0;i<=strlen(s);i++) str[i]=s[i];}char*Key::the_key()const{ return(char*)str;}charKey::key_letter(intposition)const{ if(position<strlen(str))returnstr[position]; elsereturn'\0';}4/21/20237.Trie--Record#include"Key.h"classRecord{public: operatorKey();//implicitconversionfromRecordtoKey. Record(chars[]=""); char*the_key()const; charkey_letter(intposition)const;private: charstr[key_size];};ostream&operator<<(ostream&output,Record&x);4/21/20238.Trie--Record#include"Record.h"Record::Record(chars[]){ for(inti=0;i<=strlen(s);i++) str[i]=s[i];}Record::operatorKey(){ Keytmp(str);}4/21/20239.Trie--RecordcharRecord::key_letter(intposition)const{ if(position<strlen(str))returnstr[position]; elsereturn'\0';}char*Record::the_key()const{ return(char*)str;}ostream&operator<<(ostream&output,Record&x){ output<<x.the_key(); output<<""; returnoutput;}4/21/202310.Trie—Trie_node#include"Record.h"constintnum_chars=28;structTrie_node{//datamembers Record*data; Trie_node*branch[num_chars];//constructors Trie_node();};4/21/202311.Trie—Trie_node#include"Trie_node.h"Trie_node::Trie_node(){ data=NULL; for(inti=0;i<num_chars;i++) branch[i]=NULL;}4/21/202312.Trie#include"Trie_node.h"enumError_code{not_present,overflow,underflow,duplicate_error,success};classTrie{public://Addmethodprototypeshere. Error_codeinsert(constRecord&new_entry); Error_codetrie_search(constKey&target,Record&x)const; Trie();private://datamembers Trie_node*root;};intalphabetic_order(charc);4/21/202313.Trie#include"Trie.h"intalphabetic_order(charc)/*Post:Thefunctionreturnsthealphabeticpositionofcharacterc,oritreturns0ifthecharacterisblank.*/{ if(c==''||c=='\0')return0; if('a'<=c&&c<='z')returnc-'a'+1; if('A'<=c&&c<='Z')returnc-'A'+1; return27;}Trie::Trie(){ root=NULL;}4/21/202314.TrieError_codeTrie::insert(constRecord&new_entry)/*Post:IftheKeyofnew_entryisalreadyintheTrie,acodeofduplicate_errorisreturned.Otherwise,acodeofsuccessisreturnedandtheRecordnewentryisinsertedintotheTrie.Uses:MethodsofclassesRecordandTrie_node.*/{ Error_coderesult=success; if(root==NULL)root=newTrie_node;//CreateanewemptyTrie. intposition=0;//indexeslettersofnewentry charnext_char; Trie_node*location=root;//movesthroughtheTrie while(location!=NULL&& (next_char=new_entry.key_letter(position))!='\0'){ intnext_position=alphabetic_order(next_char); if(location->branch[next_position]==NULL) location->branch[next_position]=newTrie_node; location=location->branch[next_position]; position++; }//Atthispoint,wehavetestedforallnonblankcharactersofnewentry. if(location->data!=NULL)result=duplicate_error; elselocation->data=newRecord(new_entry); returnresult;}4/21/202315.TrieError_codeTrie::trie_search(constKey&target,Record&x)const/*Post:Ifthesearchissuccessful,acodeofsuccessisreturned,andtheoutputparameterxissetasacopyoftheTrie'srecordthatholdstarget.Otherwise,acodeofnot_presentisreturned.Uses:MethodsofclassKey.*/{ intposition=0; charnext_char; Trie_node*location=root; while(location!=NULL&& (next_char=target.key_letter(position))!='\0'){ //TerminatesearchforaNULLlocationorablankinthetarget. location=location->branch[alphabetic_order(next_char)]; //Movedowntheappropriatebranchofthetrie. position++; //Movetothenextcharacterofthetarget. } if(location!=NULL&&location->data!=NULL){ x=*(location->data); returnsuccess; } else returnnot_present;}4/21/202316.Main#include"Trie.h"voidmain(){ Triedict; 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(Record("bac")); dict.insert(Record("ba")); dict.insert(Record("b"));4/21/202317.Main dict.insert(Record("caaba")); dict.insert(Record("ca")); dict.insert(Record("c")); dict.insert(Record("ca")); dict.insert(Record("cab")