Haffman编码/译码系统（haffman树的学习与应用）

// 哈夫曼编码/译码系统

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

// 统计字符信息中出现的字符种类数和各字符出现的次数（频率）
typedef struct charNode {
 char c;
 int  n;
}charNode;

charNode charList[27]; // 0号位置存放字符种类个数

void Frequent() {
 for (int i = 0; i < 27; i++) {
  charList[i].n = 0;
 }
 string s;
 cout << "输入报文（#结束）：";
 cin >> s;
 int len = s.length();
 bool flag ;
 for (int i = 0; i < len; i++) {
  flag = false;
  if (s[i] != '#') {
   int p = 1;
   for (; p <= charList[0].n; p++) {
    if (s[i] == charList[p].c) {
     flag = true;
     break;
    }
   }
   if (flag) {
    charList[p].n++;
   }
   else {
    charList[0].n++;
    charList[charList[0].n].c = s[i];
    charList[charList[0].n].n++;
   } 
  }
  else
   break;
 }
}

// 根据字符的种类数和各自出现的次数建立哈夫曼树

typedef struct HaffmanTreeNode {
 int weight;
 int parent, lchild, rchild;
}HaffmanTreeNode,*HaffmanTree;

void Select(HaffmanTree HT, int n, int &s1, int &s2) {
 int i = 0;
 while (HT[i].parent != 0)
  i++;
 s1 = i;
 for (int j = 0; j < n; j++) {
  if (HT[j].parent == 0 && HT[j].weight < HT[s1].weight)
   s1 = j;
 }
 i = 0;
 while ((HT[i].parent != 0) || i == s1)
  i++;
 s2 = i;
 for (int j = 0; j < n; j++) {
  if (HT[j].parent == 0 && HT[j].weight < HT[s2].weight&&j != s1)
   s2 = j;
 }
}

void HuffmanCoding(HaffmanTree &HT,charNode charList[27],vector<string>&HC) {
 int n = charList[0].n; // 叶子节点的个数
 int m = 2 * n - 1; // 总节点个数
 int s1, s2; // 存weight最小的两个节点的索引
 if (n <= 1)
  return;
 HT = (HaffmanTree)malloc(sizeof(HaffmanTreeNode)*m);

 // 创建HaffmanTree 
 HaffmanTree p = HT;
 int i = 1;
 for (; i <= n; i++,p++) {
  p->weight = charList[i].n;
  p->parent = 0;
  p->lchild = 0;
  p->rchild = 0;
 }
 for (; i <= m; i++,p++) {
  p->weight = 0;
  p->parent = 0;
  p->lchild = 0;
  p->rchild = 0;
 }

 for (i = n; i < m; i++) {
  Select(HT, i, s1, s2);
  HT[s1].parent = i;
  HT[s2].parent = i;
  HT[i].lchild = s1;
  HT[i].rchild = s2;
  HT[i].weight = HT[s1].weight + HT[s2].weight;
 }
 
 // 从叶子到根逆向遍历HuffmanTree，完成每个字符的编码
 string tmp = "";

 for (int i = 0; i < n; i++) {
  for (int p = i, q = HT[i].parent; q != 0; p = q, q = HT[q].parent) {
   if (p == HT[q].lchild)
    tmp = tmp + '0';
   else
    tmp = tmp + '1';
  }
  HC[i] = tmp;
  tmp = "";
 }
}

// 从根往下搜索进行解码操作
void HaffmanDecoding(HaffmanTree &HT, vector<string>&HC, int n) {
 int p = 2 * n - 1 -1 ; // p指向根节点
 for (auto it = HC.begin(); it != HC.end(); it++) {
  string tmp((*it).rbegin(), (*it).rend());
  int i = 0;
  while (p != 0 && tmp[i] != '') {
   if (tmp[i] == '0')
    p = HT[p].lchild;
   else
    p = HT[p].rchild;
   // 叶子节点
   if (HT[p].lchild == 0 && HT[p].rchild == 0) {
    cout << (*it) << ":" << charList[p + 1].c << endl;
    p = 2 * n - 1 - 1;
   }
   i++;
  }
 }
}

int main() {
 Frequent();
 cout << "length:" << charList[0].n << endl;
 for (int i = 1; i <= charList[0].n; i++) {
  cout << charList[i].c << "," << charList[i].n << endl;
 }
 HaffmanTree HT;
 vector<string> HC(charList[0].n);
 HuffmanCoding(HT, charList, HC);

 cout << endl << "**************HaffmanCoding:*********" << endl;
 for (int i = 0; i < charList[0].n; i++) {
  cout << charList[i + 1].c << ":" << HC[i] << endl;
 }

 cout << endl << "**************HaffmanDeoding:*********" << endl;
 HaffmanDecoding(HT, HC, charList[0].n);

 system("pause");
 return 0;

}