基于哈夫曼树的数据压缩算法

http://img3.mukewang.com/5a015d8a0001535b08960512.jpg

http://img3.mukewang.com/5a015d8b0001aecf09760516.jpg


#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;


#define MAXN 1000


typedef struct {
 int weight;
 int parent, lchild, rchild;
}HTNode, *HuffmanTree;


typedef char **HuffmanCode;



void Count(char str[], int count[])
{


 for (int i = 1; i <= 26; i++)
 {
  count[i] = 0;
 }
 for (int i = 0; i <strlen(str); i++)
 {
  count[str[i] - 'a' + 1]++;
 }
}


void Select(HuffmanTree &HT, int n, int &a, int &b)
{
 unsigned int m1, m2;
 m1 = m2 = 32767;
 for (int i = 1; i <= n; i++)
 {
  if (HT[i].parent == 0 && HT[i].weight < m1)
  {
   m2 = m1;
   b = a;
   m1 = HT[i].weight;
   a = i;
  }
  else
   if (HT[i].parent == 0 && HT[i].weight < m2)
   {
    m2 = HT[i].weight;
    b = i;
   }
 }


}


void CreatHuffmanTree(HuffmanTree &HT, int n, int count[])
{
 if (n <= 1) return;
 int m;
 m = 2 * n - 1;
 HT = new HTNode[m + 1];
 for (int i = 1; i <= m; i++)
 {
  HT[i].parent = 0;
  HT[i].lchild = 0;
  HT[i].rchild = 0;
 }
 int j;
 for (int i = 1,j=1; i <= n,j<=26; j++) {
  if (count[j] > 0)
  {
   HT[i].weight = count[j];
   i++;
  }
 
 }
 int s1, s2;
 for (int i = n + 1; i <= m; i++)
 {
  Select(HT, i - 1, 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;
 }
}


void CreatHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n)
{
 char *cd;
 HC = new char*[n + 1];
 cd = new char[n];
 cd[n - 1] = '\0';
 int start = 0;
 int c, f;
 for (int i = 1; i <= n; i++)
 {
  start = n - 1;
  c = i;
  f = HT[i].parent;
  while (f != 0)
  {
   start--;
   if (HT[f].lchild == c)
   {
    cd[start] = '0';
   }
   else
   {
    cd[start] = '1';
   }
    c = f;
    f = HT[f].parent;
   
  }
  HC[i] = new char[n - start];
  strcpy(HC[i], &cd[start]);


 }
 delete cd;


}


int main() {


 char str[MAXN];
 int count[50];
 int n;


 while (cin >> str&&*str != '0')
 {
  n = 0;
  Count(str, count);
  for (int i = 97; i<123; i++)
  {
   if (count[i - 96] > 0)
   {
    n++;
    printf("%c:%d ", i, count[i - 96]);


   }
  }
  cout << endl;
  HuffmanTree HT;
  CreatHuffmanTree(HT, n, count);
  for (int i = 1; i <= 2 * n - 1; i++)
  {
   cout << i << " " << HT[i].weight << " " << HT[i].parent << " " << HT[i].lchild << " " << HT[i].rchild << endl;
  }


  HuffmanCode HC;
  CreatHuffmanCode(HT, HC, n);
  int j;
  for (int i = 1; i<n; i++)
  {
   printf("%c:%s ", i, HC[i]);  //输出编码结果
  }
  cout << endl;


  for (int i = 0; i<strlen(str); i++)
  {
   cout << HC[str[i] - 'a' + 1];
  }
  cout << endl;


  for (int i = 0; i<strlen(str); i++)
   cout << str[i];
  cout << endl;
 }
 return 0;
}

用aabb这样开头的就可以过 eeeeffg就不行

哪个大神帮我看看哪里需要改

晴书
浏览 2789回答 0
0回答
打开App,查看更多内容
随时随地看视频慕课网APP