huffman.cpp

huffman编码

#include "stdio.h"
#include "ctype.h"
#include "stdlib.h"
#include "iostream.h"

typedef struct
{
 unsigned int weight;
 unsigned int parent;
 unsigned int lchild;
 unsigned int rchild;
}HuffmTree;

typedef char **HuffmCode;

typedef struct 
{
 unsigned ch;
 unsigned long fr;
}WD;

void select(HuffmTree *HT, int n, int *s1, int *s2)
{
  int j;
  unsigned long min1,min2;
  min1=65535;
  for(j=1;j<=n;j++)
  {
    if((min1>HT[j].weight)&&(HT[j].parent=0))
		min1=HT[j].weight;
  }

  j=n;

  while((j>0))
  {
    if((min1==HT[j].weight)&&(HT[j].parent==0))
		break;
	else
		j--;
  }

  *s1=j;

  min2=65535;

  for(j=1;j<n;j++)
  {
    if((min2>HT[j].weight)&&(j!=*s1)&&(HT[j].parent==0))
		min2=HT[j].weight;
  }
  
  j=n;

  while((j>0))
  {
   if(j==*s1)
   {
     j--;
	 continue;
   }

   else
	   if((min2==HT[j].weight)&&(HT[j].parent==0))
		   break;
	   else
		   j--;
  }
   *s2=j;
}

void HuffmanCoding(HuffmTree *HT,HuffmCode *HC,WD w[256], int n)
{
  int m,i,j,s1,s2,l,k,start,f,cdlen;
  char *cd;
  if(n<=1)
	  return;
  m=2*n-1;
  HT=(HuffmTree *)malloc((m+1)*sizeof(HuffmTree));
  for(i=1;i<=n;i++)
  {
    HT[i].weight=w[i-1].fr;
	HT[i].parent=0;
	HT[i].lchild=0;
	HT[i].rchild=0;
  }

  for(;i<=m;i++)
  {
    HT[i].weight=0;
	HT[i].lchild=0;
	HT[i].parent=0;
	HT[i].rchild=0;
  }

  for(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 main(void)
{
 
}