数据结构与程序设计(王丽苹)29multiway.ppt

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

1、5/27/2023,数据结构与程序设计,1,数据结构与程序设计(29)Chapter11 Multiway Trees,王丽苹,5/27/2023,数据结构与程序设计,2,Tries(retrieval):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.Figure 11.7 Trie of words constructed from a,b,c,5/27/20

2、23,数据结构与程序设计,3,5/27/2023,数据结构与程序设计,4,Tries(retrieval):Lexicographic Search Trees特点分析,Tries 经常用于词法的查找。m tries 的第一层表示要查找单词的第一个字母，第二层为要查找单词的第二字母，.m tries 的每一个节点的结构相同，包含m个孩子指针项，一个数据项。m表示在查找单词集合中出现的字母数。,5/27/2023,数据结构与程序设计,5,C+Trie Declarations,Every Record has a Key that is an alphanumeric string.Method

3、 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.E.g.key1:”interesting”key1.key_letter(2)return t,5/27/2023,数据结构与程序设计,6,C+Trie Declarations,function int alphabetic_order(char symbol)returns the alphabetic

4、position of the character symbol,or 27 for nonblank,nonalphabetic characters,or 0 for blank,NONE characters.E.g.alphabetic_order(c)return 3alphabetic_order(5)return 27alphabetic_order()return 0,5/27/2023,数据结构与程序设计,7,TrieTrie_node,#include Record.hconst int num_chars=28;struct Trie_node/data membersR

5、ecord*data;Trie_node*branchnum_chars;/constructorsTrie_node();,5/27/2023,数据结构与程序设计,8,TrieTrie_node,Trie_node*branchnum_chars;,Record*data;,Branch0,Branch27,Branch15,Key：“watermelon”Content:”西瓜：一种非洲藤本植物”,Record*data,Trie_node*branchnum_chars;,5/27/2023,数据结构与程序设计,9,TrieTrie_node,#include Trie_node.hTr

6、ie_node:Trie_node()data=NULL;for(int i=0;inum_chars;i+)branchi=NULL;,5/27/2023,数据结构与程序设计,10,TrieTrie_node-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(int position)const;,5/27/2023,数据结构与程序设计,11,TrieTri

7、e_node-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;,5/27/2023,数据结构与程序设计,12,TrieTrie_node-Record,#include Key.hclass Recordpublic:operator Key()

8、;/implicit conversion from Record to Key.Record(char s=“,string con=“”);char*the_key()const;char key_letter(int position)const;private:char strkey_size;string content;ostream,5/27/2023,数据结构与程序设计,13,TrieTrie_node-Record,#include Record.hRecord:Record(char s,string con)for(int i=0;i=strlen(s);i+)stri=

9、si;content=con;Record:operator Key()Key tmp(str);,5/27/2023,数据结构与程序设计,14,TrieTrie_node-Record,char Record:key_letter(int position)constif(positionstrlen(str)return strposition;else return 0;char*Record:the_key()constreturn(char*)str;ostream,5/27/2023,数据结构与程序设计,15,Trie-declaration,#include Trie_node.

10、henum Error_codenot_present,overflow,underflow,duplicate_error,success;class Trie public:/Add method prototypes here.Error_code insert(const Record,5/27/2023,数据结构与程序设计,16,Trie,#include Trie.hint alphabetic_order(char c)/*Post:The function returns the alphabetic position of character c,or it returns

11、0 if the character is blank.*/if(c=|c=0)return 0;if(a=c,5/27/2023,数据结构与程序设计,17,Trie-search:思考：在图11.7中查找单词cacb的过程。从root向叶子节点搜索，找到单词存放的节点位置，如果中途碰到NULL节点表示该单词不存在。,5/27/2023,数据结构与程序设计,18,Trie-search“cacb”的查找分析,“cacb”，的第一个字母为c，找到根节点的第3个孩子c1。“cacb”，的第二个字母为a，找到c1节点的第1个孩子c2。“cacb”，的第三个字母为c，找到c2节点的第3个孩子c3。“c

12、acb”，的第四个字母为b，找到c3节点的第2个孩子c4。“cacb”读取结束，此时C4的data指针指向单词cacb。,5/27/2023,数据结构与程序设计,19,Trie-search“aabd”的查找分析,“aabd”，的第一个字母为a，找到根节点的第1个孩子c1。“aabd”，的第二个字母为a，找到c1节点的第1个孩子c2。“aabd”，的第三个字母为b，找到c2节点的第2个孩子c3。此时C3为空，查找失败。,5/27/2023,数据结构与程序设计,20,Trie-search,int position=0;Trie_node*location;Step1,location指向根节点

13、。Step2,当location不为空时，并且position小于Key的长度时读取关键字target中第position个字符ch。获取ch的字母位置i。Location指向第i个孩子节点。Position+；重复第二步。Step3，Location为NULL，查找失败。否则 Location的data指针指向record就为要查找的内容。,5/27/2023,数据结构与程序设计,21,Trie-search,Error_code Trie:trie_search(const Key,5/27/2023,数据结构与程序设计,22,Trie-insert:思考：在图11.7中插入单词aabc的

14、过程。从root向叶子节点搜索，找到单词存放的节点位置，并将单词放入该位置。,5/27/2023,数据结构与程序设计,23,Trie-insert“aabc”的插入分析,“aabc”，的第一个字母为a，找到根节点c的第一个孩子c1。“aabc”，的第二个字母为a，找到c1节点的第一个孩子c2。“aabc”，的第三个字母为b，找到c2节点的第二个孩子c3。此时C3为NULL，需要生成一个新的节点C3，同时设置C3为C2的第2个孩子。“aabc”，的第四个字母为c，找到c3节点的第三个孩子c4。此时C4为NULL，需要生成一个新的节点C4，同时设置C4为C3的第3个孩子。“aabc”读取结束，此时

15、C4的data指针指向单词aabc即可。,5/27/2023,数据结构与程序设计,24,Trie-insert,int position=0;Trie_node*location;Step1,location指向根节点，如果根节点不存在，则生成新的根节点。Step2,当location不为空时，并且position小于Key的长度时：读取插入的Record中第position个关键字ch，判断ch的位置i如果Location的第i个孩子节点为NULL，创建新的Tire node节点，该节点为Location的第i个孩子Location指向第i个孩子节点。Position+；重复第二步，直到条件

16、为假。Step3，Location的data部分为空，Location的data指针指向record即可。否则，关键字重复。,5/27/2023,数据结构与程序设计,25,Trie-insert,Error_code Trie:insert(const Record,5/27/2023,数据结构与程序设计,26,Main,#include Trie.hvoid main()Trie dict;dict.insert(Record(a);dict.insert(Record(aa);dict.insert(Record(ab);dict.insert(Record(ac);dict.insert

17、(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);,5/27/2023,数据结构与程序设计,27,Main,dict.insert(Record(caaba);dict.insert(Rec

18、ord(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;,5/27/2023,数据结构与程序设计,28,Result,abaca,5/27/2023,数据结构与程序设计,29,Trie,目录Trie下例程,