




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
數(shù)據(jù)結構與程序設計(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")
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 谷物磨制企業(yè)戰(zhàn)略規(guī)劃與市場定位策略考核試卷
- 藥用提取設備與有效成分分析考核試卷
- 紡織面料鞋的廢舊資源再利用技術考核試卷
- 紙張印刷與印后加工考核試卷
- 羽絨加工企業(yè)工藝優(yōu)化與成本降低實踐考核試卷
- 車輛信息安全與隱私保護技術考核試卷
- 傳染病敗血癥診療與防控要點
- 寵物美容連鎖店品牌加盟、技術培訓與設備租賃合同
- 綠色環(huán)保住宅售后返租投資協(xié)議
- 婚前商標權權屬爭議調解及執(zhí)行協(xié)議
- 計量器具周檢計劃表
- 老年人口腔功能的衰退與對策
- 《公路路基路面現(xiàn)場測試規(guī)程》(3450-2019)
- (完整版)建筑工程技術說專業(yè)、專業(yè)剖析
- A-Rose-For-Emily-William-Faulkner課文、作者、背景講解-(課堂PPT)
- 內分泌科糖尿病“一病一品”
- 起重作業(yè)培訓-指揮手勢-旗語
- 機械原理課程設計搖擺式輸送機設計說明書
- 山西河曲晉神磁窯溝煤業(yè)有限公司煤炭資源開發(fā)利用、地質環(huán)境保護與土地復墾方案
- 重型自卸車貨箱與舉升裝置設計(含CAD圖紙)
- 內蒙古煤礦豎井地質勘察施工技術
評論
0/150
提交評論