数据结构与程序设计.ppt

《数据结构与程序设计.ppt》由会员分享，可在线阅读，更多相关《数据结构与程序设计.ppt（20页珍藏版）》请在三一办公上搜索。

1、9/11/2023,数据结构与程序设计 教师：鲍钰,1,数据结构与程序设计(29),教师：鲍钰,9/11/2023,数据结构与程序设计 教师：鲍钰,2,Chapter 11,MULTIWAY TREES,9/11/2023,数据结构与程序设计 教师：鲍钰,3,Tries:Lexicographic Search TreesP531,DEFINITION A trie of order m is either empty or consists of an ordered sequence of exactly m tries of order m.,9/11/2023,数据结构与程序设计 教师

2、：鲍钰,4,9/11/2023,数据结构与程序设计 教师：鲍钰,5,C+Trie Declarations,Every 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(ch

3、ar symbol)returns the alphabetic position of the character symbol,or 27 for nonblank,nonalphabetic characters,or 0 for blank,NONE characters.,9/11/2023,数据结构与程序设计 教师：鲍钰,6,Trie-Key,#include String.h#include iostream.hconst int key_size=10;class Key char strkey_size;public:Key(char s);char*the_key()con

4、st;char key_letter(int position)const;,9/11/2023,数据结构与程序设计 教师：鲍钰,7,Trie-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/11/2023,数据结构与程序设计 教师：鲍钰,

5、8,Trie-Record,#include 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,9/11/2023,数据结构与程序设计 教师：鲍钰,9,Trie-Record,#include Record.hRecord:Record(char s)for(int i=0;i=st

6、rlen(s);i+)stri=si;Record:operator Key()Key tmp(str);,9/11/2023,数据结构与程序设计 教师：鲍钰,10,Trie-Record,char Record:key_letter(int position)constif(positionstrlen(str)return strposition;else return 0;char*Record:the_key()constreturn(char*)str;ostream,9/11/2023,数据结构与程序设计 教师：鲍钰,11,TrieTrie_node,#include Record

7、.hconst int num_chars=28;struct Trie_node/data membersRecord*data;Trie_node*branchnum_chars;/constructorsTrie_node();,9/11/2023,数据结构与程序设计 教师：鲍钰,12,TrieTrie_node,#include Trie_node.hTrie_node:Trie_node()data=NULL;for(int i=0;inum_chars;i+)branchi=NULL;,9/11/2023,数据结构与程序设计 教师：鲍钰,13,Trie,#include Trie_

8、node.henum Error_codenot_present,overflow,underflow,duplicate_error,success;class Trie public:/Add method prototypes here.Error_code insert(const Record,9/11/2023,数据结构与程序设计 教师：鲍钰,14,Trie,#include Trie.hint alphabetic_order(char c)/*Post:The function returns the alphabetic position of character c,or

9、it returns 0 if the character is blank.*/if(c=|c=0)return 0;if(a=c,9/11/2023,数据结构与程序设计 教师：鲍钰,15,Trie,Error_code Trie:insert(const Record,9/11/2023,数据结构与程序设计 教师：鲍钰,16,Trie,Error_code Trie:trie_search(const Key,9/11/2023,数据结构与程序设计 教师：鲍钰,17,Main,#include Trie.hvoid main()Trie dict;dict.insert(Record(a)

10、;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

11、(Record(b);,9/11/2023,数据结构与程序设计 教师：鲍钰,18,Main,dict.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/11/2023,数据结构与程序设计 教师：鲍钰,19,Result,abaca,9/11/2023,数据结构与程序设计 教师：鲍钰,20,Trie,目录Trie下例程,