數(shù)據(jù)結構與程序設計(29)

Chapter11MultiwayTrees王麗蘋lipingwang@4/21/20231.Tries(retrieval):

LexicographicSearchTrees

P531DEFINITIONAtrieofordermiseitheremptyorconsistsofanorderedsequenceofexactlymtriesoforderm.Figure11.7Trieofwordsconstructedfroma,b,c4/21/20232.4/21/20233.Tries(retrieval):

LexicographicSearchTrees

特點分析Tries經(jīng)常用于詞法的查找。mtries的第一層表示要查找單詞的第一個字母，第二層為要查找單詞的第二字母，……..mtries的每一個節(jié)點的結構相同，包含m個孩子指針項，一個數(shù)據(jù)項。m表示在查找單詞集合中出現(xiàn)的字母數(shù)。4/21/20234.C++TrieDeclarationsEveryRecordhasaKeythatisanalphanumericstring.Methodcharkey_letter(intposition)returnsthecharacterinthegivenpositionofthekeyorreturnsaNONE,ifthekeyhaslengthlessthanposition.E.g.key1:”interesting”key1.key_letter(2)return‘t’4/21/20235.C++TrieDeclarationsfunctionintalphabetic_order(charsymbol)returnsthealphabeticpositionofthecharactersymbol,or27fornonblank,nonalphabeticcharacters,or0forblank,NONEcharacters.E.g.alphabetic_order(‘c’)return3alphabetic_order(‘5’)return27alphabetic_order(‘’)return04/21/20236.Trie—Trie_node#include"Record.h"constintnum_chars=28;structTrie_node{//datamembers Record*data; Trie_node*branch[num_chars];//constructors Trie_node();};4/21/20237.Trie—Trie_nodeTrie_node*Trie_node*…Trie_node*…Trie_node*Record*dataTrie_node*branch[num_chars];Record*data;Branch[0]Branch[27]Branch[15]Key：“watermelon”Content:”西瓜：一種非洲藤本植物”Record*dataTrie_node*branch[num_chars];4/21/20238.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/20239.Trie—Trie_node--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/202310.Trie—Trie_node--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/202311.Trie—Trie_node--Record#include"Key.h"classRecord{public: operatorKey();//implicitconversionfromRecordtoKey. Record(chars[]="“,stringcon=“”); char*the_key()const; charkey_letter(intposition)const;private: charstr[key_size];stringcontent;};ostream&operator<<(ostream&output,Record&x);4/21/202312.Trie—Trie_node--Record#include"Record.h"Record::Record(chars[],stringcon){ for(inti=0;i<=strlen(s);i++) str[i]=s[i];content=con;}Record::operatorKey(){ Keytmp(str);}4/21/202313.Trie—Trie_node--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/202314.Trie-declaration#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/202315.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/202316.Trie-search:思考：在圖11.7中查找單詞cacb的過程。

從root向葉子節(jié)點搜索，找到單詞存放的節(jié)點位置，如果中途碰到NULL節(jié)點表示該單詞不存在。4/21/202317.Trie-search“cacb”的查找分析“cacb”，的第一個字母為c，找到根節(jié)點的第3個孩子c1。“cacb”，的第二個字母為a，找到c1節(jié)點的第1個孩子c2?！癱acb”，的第三個字母為c，找到c2節(jié)點的第3個孩子c3?！癱acb”，的第四個字母為b，找到c3節(jié)點的第2個孩子c4。“cacb”讀取結束，此時C4的data指針指向單詞cacb。4/21/202318.Trie-search“aabd”的查找分析“aabd”，的第一個字母為a，找到根節(jié)點的第1個孩子c1?！癮abd”，的第二個字母為a，找到c1節(jié)點的第1個孩子c2?！癮abd”，的第三個字母為b，找到c2節(jié)點的第2個孩子c3。此時C3為空，查找失敗。4/21/202319.Trie-searchintposition=0;Trie_node*location;Step1,location指向根節(jié)點。Step2,當location不為空時，并且position小于Key的長度時讀取關鍵字target中第position個字符ch。獲取ch的字母位置i。Location指向第i個孩子節(jié)點。Position++；重復第二步。Step3，Location為NULL，查找失敗。否則Location的data指針指向record就為要查找的內(nèi)容。4/21/202320.Trie-searchError_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/202321.Trie-insert:思考：在圖11.7中插入單詞aabc的過程。

從root向葉子節(jié)點搜索，找到單詞存放的節(jié)點位置，并將單詞放入該位置。4/21/202322.Trie-insert“aabc”的插入分析“aabc”，的第一個字母為a，找到根節(jié)點c的第一個孩子c1?！癮abc”，的第二個字母為a，找到c1節(jié)點的第一個孩子c2?！癮abc”，的第三個字母為b，找到c2節(jié)點的第二個孩子c3。此時C3為NULL，需要生成一個新的節(jié)點C3，同時設置C3為C2的第2個孩子?！癮abc”，的第四個字母為c，找到c3節(jié)點的第三個孩子c4。此時C4為NULL，需要生成一個新的節(jié)點C4，同時設置C4為C3的第3個孩子?！癮abc”讀取結束，此時C4的data指針指向單詞aabc即可。4/21/202323.Trie-insertintposition=0;Trie_node*location;Step1,location指向根節(jié)點，如果根節(jié)點不存在，則生成新的根節(jié)點。Step2,當location不為空時，并且position小于Key的長度時：讀取插入的Record中第position個關鍵字ch，判斷ch的位置i如果Location的第i個孩子節(jié)點為NULL，創(chuàng)建新的Tirenode節(jié)點，該節(jié)點為Location的第i個孩子Location指向第i個孩子節(jié)點。Position++；重復第二步，直到條件為假。Step3，Location的data部分為空，Location的data指針指向record即可。否則，關鍵字重復。4/21/202324.Trie-insertError_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/202325.Main#include"Trie.h"voidmain(){ Triedict; dict.insert(Record("a")); dict.insert(Rec