数据结构与程序设计.ppt

数据结构与程序设计(29)
教师:鲍钰
******@.
11/14/2017
1
数据结构与程序设计教师:鲍钰
Chapter 11
MULTIWAY TREES
11/14/2017
2
数据结构与程序设计教师:鲍钰
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.
11/14/2017
3
数据结构与程序设计教师:鲍钰
11/14/2017
4
数据结构与程序设计教师:鲍钰
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(char symbol) returns the alphabetic position of the character symbol, or 27 for nonblank, nonalphabetic characters, or 0 for blank, NONE characters.
11/14/2017
5
数据结构与程序设计教师:鲍钰
Trie--Key
#include ""
#include ""
const int key_size = 10;
class Key {
char str[key_size];
public:
Key (char s[]);
char * the_key( ) const;
char key_letter(int position) const;
};
11/14/2017
6
数据结构与程序设计教师:鲍钰
Trie--Key
#include ""
Key::Key(char s[]){
for(int i=0; i<=strlen(s); i++)
str[i]=s[i];
}
char * Key::the_key() const{
return (char *)str;
}
char Key::key_letter (int position) const{
if(position<strlen(str)) return str[position];
else return '\0';
}
11/14/2017
7
数据结构与程序设计教师:鲍钰
Trie--Record
#include ""
class Record{
public:
operator Key( ); // implicit conversion from Record to Key .
Record(char s[]="");
char * the_key() const;
char key_letter(int position) const;
private:
char str[key_size];
};
ostream & operator << (ostream &output, Record &x);
11/14/2017
8
数据结构与程序设计教师:鲍钰
Trie--Record
#include ""
Record::Record(char s[]){
for(int i=0; i<=strlen(s); i++)
str[i]=s[i];
}
Record::operator Key( ){
Key tmp(str);
}
11/14/2017
9
数据结构与程序设计教师:鲍钰
Trie--Record
char Record::key_letter(int position) const{
if(position<strlen(str)) return str[position];
else return '\0';
}
char * Record::the_key() const{
return (