Huffman编码

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stack>
using namespace std;
typedef struct node{             //哈夫曼树
 int weight;
 char data;
 int parent, lchild, rchild;
}HTree, *pHTree;

typedef struct n{
 char bit[10];
}HCode, *pHCode;

void Select(pHTree HT, int n, int *s1, int *s2)
{
 int i;
 for (i = 0; i < n && HT[i].parent!=-1; i++);
 *s1 = i;

 for (i = 0; i < n; i++)
  if (HT[i].weight < HT[*s1].weight && HT[i].parent == -1)
   *s1 = i;

 for (i = 0; i < n; i++)
  if (HT[i].parent == -1 && *s1 != i)
   break;
 *s2 = i;

 for (i = 0; i < n; i++)
  if (HT[i].parent == -1 && *s1 != i && HT[i].weight<HT[*s2].weight)
   *s2 = i;
 
 
}
void Creat(pHTree &HT,pHCode &HC,int n)
{
 int i;
 int m = 2 * n - 1;
 int s1=0, s2=1;
 HT = (pHTree)malloc((m)*sizeof(HTree));        //数据内存空间

 for (i = 0; i < m; i++)         //初始化哈夫曼树组
 {
  HT[i].weight = -1;
  HT[i].data = ‘#‘;
  HT[i].parent = -1;
  HT[i].lchild = -1;
  HT[i].rchild = -1;
 }
 fflush(stdin);

 printf("输入%d个数据:\n", n);         //输入数据
 for (i = 0; i < n; i++){
  scanf("%c", &HT[i].data);
  getchar();
 }

 printf("输入数据的权:\n");           //输入权重
 for (i = 0; i < n; i++)
 {
  scanf("%d", &HT[i].weight);
  getchar();
 }

 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;
 }

}
void Code(pHTree &HT, pHCode &HC, int n)
{
 stack<char>s;

 HC = (pHCode)malloc(n*sizeof(HCode));
 int p,j=0,k=0,c=0;
 int i;
 for (i = 0; i < n; i++)
 {
  for (k = i, p = HT[k].parent;p!=-1; k=p,p = HT[p].parent)
  {
   if (k == HT[p].lchild)
    s.push(‘0‘);
   else
    s.push(‘1‘);
  }
 
  while (!s.empty())
  {
   HC[i].bit[j] = s.top();
   s.pop();
   j++;
  }
  HC[i].bit[j] = ‘\0‘;
  j = 0;
 }
 
}
int main()
{
 int num;
 pHTree  HT=NULL;
 pHCode HC=NULL;
 FILE *fp;
 printf("Please input num:");
 scanf("%d", &num);

 Creat(HT, HC, num);

 Code(HT, HC, num);
    fp=fopen("D:\\2.txt","a");
 for (int i = 0; i < num; i++)
 {
    fputc(HT[i].data,fp);
        fprintf(fp,"%s\n",HC[i].bit);
  printf("%c-----%s\n", HT[i].data,HC[i].bit);
 }
 
 
 system("pause");
 return 0;
}

Huffman编码

原文：http://www.cnblogs.com/da-peng/p/4975612.html