题目描述：
已知有一自字符数组MB[]={'d','g','e','r','a','o'},现有字符数组str[]={"dog","dear","ear","geo"},实现对str中的字符串按MB字符数组提供的规则排序输出，输出样式应为dear dog geo ear 。
分析：这道题最佳的解法应该采用Trie数，Trie树又称字典树，它可以用来实现对字符串的快速匹配。它的基本思想是以空间换时间，匹配一个字符串只需O(n)。这道题看似不是字典序排序，但是思想是一样的，可以实现一个方法，对于字符变量m,找出m在MB中的位置 k，即可改变成用字典排序。
代码如下：
#include<iostream>
#include<string.h>
using namespace std;
class Node
{
public:
enum{NUM=6};
static char MB[NUM];
int count;
Node* char_arr[NUM];
char* curr_arr;
Node();
static int retdiji(char a);
};
class Trie
{
public:
Node* root;
Trie();
void insert(char* str);
void output(Node* node,char** str,int& count);
};
int main()
{
char** str=new char*[4];
str[0]="dog";
str[1]="dear";
str[2]="ear";
str[3]="geo";
Trie T;
for(int i=0;i<4;i++)
{
T.insert(str[i]);
}
int count=0;
T.output(T.root,str,count);
for(int i=0;i<count;i++)
{
cout<<str[i]<<endl;
}
return 0;
}
char Node::MB[]={'d','g','e','r','a','o'};
int Node::retdiji(char a)
{
for(int i=0;i<NUM;i++)
{
if(a==MB[i])
return i;
}
cout<<"Not a ileanum!"<<endl;
return -1;
}
Node::Node()
{
count=0;
curr_arr=new char[100];
curr_arr[0]=' ';
for(int i=0;i<NUM;i++)
{
char_arr[i]=0;
}
}
Trie::Trie()
{
root=new Node();
}
void Trie::insert(char* str)
{
if(str==0)
return;
Node* parent=root;
int i=0;
while(str[i]!=' ')
{
int k=Node::retdiji(str[i]);
if(parent->char_arr[k]==0)
{
parent->char_arr[k]=new Node();
strcat(parent->char_arr[k]->curr_arr,parent->curr_arr);
char newc[2];
newc[0]=str[i]; newc[1]=' ';
strcat(parent->char_arr[k]->curr_arr,newc);
}
parent=parent->char_arr[k];
i++;
}
parent->count++;
}
void Trie::output(Node* node,char** str,int& count)
{
if(node!=0)
{
for(int i=0;i<node->count;i++)
{
str[count++]=node->curr_arr;
}
for(int i=0;i<Node::NUM;i++)
{
output(node->char_arr[i],str,count);
}
}
}
1 #include<iostream> 2 #include<string.h> 3 using namespace std; 4 5 class Node 6 { 7 public: 8 enum{NUM=6}; 9 static char MB[NUM]; 10 int count; 11 Node* char_arr[NUM]; 12 char* curr_arr; 13 Node(); 14 static int retdiji(char a); 15 }; 16 17 class Trie 18 { 19 public: 20 Node* root; 21 Trie(); 22 void insert(char* str); 23 void output(Node* node,char** str,int& count); 24 }; 25 int main() 26 { 27 char** str=new char*[4]; 28 str[0]="dog"; 29 str[1]="dear"; 30 str[2]="ear"; 31 str[3]="geo"; 32 Trie T; 33 for(int i=0;i<4;i++) 34 { 35 T.insert(str[i]); 36 } 37 int count=0; 38 T.output(T.root,str,count); 39 for(int i=0;i<count;i++) 40 { 41 cout<<str[i]<<endl; 42 } 43 return 0; 44 } 45 46 char Node::MB[]={'d','g','e','r','a','o'}; 47 int Node::retdiji(char a) 48 { 49 for(int i=0;i<NUM;i++) 50 { 51 if(a==MB[i]) 52 return i; 53 } 54 cout<<"Not a ileanum!"<<endl; 55 return -1; 56 } 57 Node::Node() 58 { 59 count=0; 60 curr_arr=new char[100]; 61 curr_arr[0]=' '; 62 for(int i=0;i<NUM;i++) 63 { 64 char_arr[i]=0; 65 } 66 } 67 68 Trie::Trie() 69 { 70 root=new Node(); 71 } 72 73 void Trie::insert(char* str) 74 { 75 if(str==0) 76 return; 77 Node* parent=root; 78 int i=0; 79 while(str[i]!=' ') 80 { 81 int k=Node::retdiji(str[i]); 82 if(parent->char_arr[k]==0) 83 { 84 parent->char_arr[k]=new Node(); 85 strcat(parent->char_arr[k]->curr_arr,parent->curr_arr); 86 char newc[2]; 87 newc[0]=str[i]; newc[1]=' '; 88 strcat(parent->char_arr[k]->curr_arr,newc); 89 } 90 parent=parent->char_arr[k]; 91 i++; 92 } 93 parent->count++; 94 } 95 96 void Trie::output(Node* node,char** str,int& count) 97 { 98 if(node!=0) 99 { 100 for(int i=0;i<node->count;i++) 101 { 102 str[count++]=node->curr_arr; 103 } 104 for(int i=0;i<Node::NUM;i++) 105 { 106 output(node->char_arr[i],str,count); 107 } 108 } 109 }
部分代码参考：http://www.cnblogs.com/shuaiwhu/archive/2012/05/05/2484676.html