哈夫曼编码c++实现

#include <iostream>
#include <string>
#include <vector>
#include<algorithm>
using namespace std;
class Huffman
{
public:
 char elementChar;//节点元素
 int weight;//权重
 char s;//哈夫曼编码
 Huffman* parent;//父节点
 Huffman* leftChild;//左孩子
 Huffman* rightChild;//右孩子
public:
 Huffman();
 Huffman(char a, int weight);
 bool operator < (const Huffman &m)const { return weight < m.weight;}
};
Huffman::Huffman()
{
 this->s = ' ';
 this->elementChar = '*';//非叶子节点
 this->parent = this->leftChild = this->rightChild = NULL;
}
Huffman::Huffman(char a, int weight):elementChar(a),weight(weight)
{
 this->s = ' ';
 this->elementChar = '*';//非叶子节点
 this->parent = this->leftChild = this->rightChild = NULL;
}

//递归输出哈夫曼值
void huffmanCode(Huffman & h)
{
 if(h.leftChild == NULL && h.rightChild == NULL)
 {
  //如果是叶子节点，输出器哈夫曼编码
  string s;
  Huffman temp = h;
  while(temp.parent != NULL)
  {
   s = temp.s + s;
   temp = *temp.parent;
  }
  cout << h.elementChar << "的哈夫曼编码是：" << s << endl;
  return;
 }
 //左孩子
 huffmanCode(*h.leftChild);
 //右孩子 
 huffmanCode(*h.rightChild);
}
int main()
{
 string huffmanStr;
 cout << "请输入一串字符序列：" << endl;
 cin >> huffmanStr;
 //得到字符串信息
 int i=0,j,n,m[100],h,k=0;
 char cha[100];
 n = huffmanStr.length();
 cout << "字符串总共有字符" << n << "个" << endl;
 for(int i = 0; i < n; i++)
 {
  j = 0; h = 0;
  while(huffmanStr[i] != huffmanStr[j])
   j++;
  if(j == i)
  {
   cha[k] = huffmanStr[i];
   cout << "字符" << cha[k] << "出现";
  }
  //如果j !=i 则略过此次循环
  else
   continue;

  for(j = i; j < n; j++)
  {
   if(huffmanStr[i] == huffmanStr[j])
    h++;
  }
  cout << h << "次" << endl;
  m[k] = h;
  k++;
 }
 //哈夫曼编码
 Huffman huffmanTemp;
 vector < Huffman > huffmanQueue;
 //初始化队列
 for(int i = 0; i < k; i++)
 {
  huffmanTemp.elementChar = cha[i];
  huffmanTemp.weight = m[i];
  huffmanQueue.push_back(huffmanTemp);
 } 
 //得到哈夫曼树所有节点
 int huffmanQueue_index = 0;
 sort(huffmanQueue.begin(), huffmanQueue.end());
 while(huffmanQueue.size() < 2 * k - 1)
 {
  //合成最小两个节点的父节点
  huffmanTemp.weight = huffmanQueue[huffmanQueue_index].weight + huffmanQueue[huffmanQueue_index + 1].weight;
  huffmanQueue[huffmanQueue_index].s = '0';
  huffmanQueue[huffmanQueue_index + 1].s = '1';
  huffmanTemp.elementChar = '*';
  //将父节点加入队列
  huffmanQueue.push_back(huffmanTemp);
  sort(huffmanQueue.begin(), huffmanQueue.end());
  huffmanQueue_index += 2;
 }
 //把所有节点构造成哈夫曼树
 int step = 0;//步长
 while(step + 2 < 2 * k)
 {
  for(int j = step + 1; j <= huffmanQueue.size(); j++)
  {
   if(huffmanQueue[j].elementChar == '*' && huffmanQueue[j].leftChild == NULL && (huffmanQueue[j].weight == huffmanQueue[step].weight + huffmanQueue[step+1].weight))
   {
    huffmanQueue[j].leftChild = &huffmanQueue[step];
    huffmanQueue[j].rightChild = &huffmanQueue[step+1];
    huffmanQueue[step].parent = huffmanQueue[step+1].parent = &huffmanQueue[j];
    break;
   }
  }
  step += 2;
 }
 //cout << huffmanQueue.size() << endl;
 //序列最后一个元素，即哈弗曼树最顶端的节点
 huffmanTemp = huffmanQueue.back();
 huffmanCode(huffmanTemp);
 return 0;
}