算法导论83(b)习题解答(trie树)

CLRS 8-3(b) :

        给定一个字符串数组，其中不同的串包含的字符数可能不同，但所有串中总的字符个数为n。说明如何在O(n)时间内对该数组进行排序。

算法思想：

1.在这里用空间来换取时间，因而采用trie树，即字典树，顾名思义，像一本字典一样。

2.将每个字符串插入到trie树中，到达特定的结尾节点时，在这个节点上进行标记，如插入"afb"，第一个字母为a，沿着a往下，然后第二个字母为f，沿着f往下，第三个为b，沿着b往下，由于字符串最后一个字符为'\0'，因而结束，不再往下了，然后在这个节点上标记afb.count++，即其个数增加1.

3.通过前序遍历此树，即可得到字符串从小到大的顺序。

#include <iostream>
#include <string>
using namespace std;

#define NUM 26

class Node
{
public:
      int count; //记录该处字符串个数
  Node* char_arr[NUM];  //分支
  char* current_str;   //记录到达此处的路径上的所有字母组成的字符串
  Node();
};

class Trie
{
public:
  Node* root;
  Trie();

      void insert(char* str);
      void output(Node*&node, char** str, int& count);
};

//程序未考虑delete动态内存
int main()
{
      char** str =newchar*[12];
  str[0] ="zbdfasd";
  str[1] ="zbcfd";
  str[2] ="zbcdfdasfasf";
  str[3] ="abcdaf";
  str[4] ="defdasfa";
  str[5] ="fedfasfd";
  str[6] ="dfdfsa";
  str[7] ="dadfd";
  str[8] ="dfdfasf";
  str[9] ="abcfdfa";
  str[10] ="fbcdfd";
  str[11] ="abcdaf";

      //建立trie树
  Trie* trie =new Trie();
      for(int i =0; i <12; i++)
  trie->insert(str[i]);

      int count =0;
  trie->output(trie->root, str, count);

      for(int i =0; i <12; i++)
    cout<<str[i]<<endl;

      return 0;
}

Node::Node()
{
  count =0;
      for(int i =0; i < NUM; i++)
    char_arr[i] = NULL;
  current_str = new char[100];
  current_str[0] = '\0';
}

Trie::Trie()
{
  root = new Node();
}

void Trie::insert(char* str)
{
      int i =0;
  Node* parent = root;

      //将str[i]插入到trie树中
  while(str[i] !='\0')
  {
            //如果包含str[i]的分支存在，则新建此分支
    if(parent->char_arr[str[i] -'a'] == NULL)
    {
      parent->char_arr[str[i] -'a'] =new Node();
                  //将父节点中的字符串添加到当前节点的字符串中
      strcat(parent->char_arr[str[i] -'a']->current_str, parent->current_str);

                  char str_tmp[2];
      str_tmp[0] = str[i];
      str_tmp[1] ='\0';

                  //将str[i]添加到当前节点的字符串中
      strcat(parent->char_arr[str[i] -'a']->current_str, str_tmp);

      parent = parent->char_arr[str[i] -'a'];
    }
            else
    {
      parent = parent->char_arr[str[i] -'a'];
    }
    i++;
  }
  parent->count++;
}

//采用前序遍历
void Trie::output(Node*&node, char** str, int& count)
{
      if(node != NULL)
  {
            if(node->count !=0)
    {
                  for(int i =0; i < node->count; i++)
      str[count++] = node->current_str;
    }
            for(int i =0; i < NUM; i++)
    {
      output(node->char_arr[i], str, count);
    }
  }
}