huffman2.cpp

来自「本代码用于对数据进行哈夫曼编码」· C++ 代码 · 共 129 行

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<ctype.h>
#include<string>
#define swap(x,y,t) ((t)=(x),(x)=(y),(y)=(t))
#define N 26
char string[N]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
int num[N];
typedef struct
{
int weight;
int parent,lchild,rchild;
}HTnode,*hafumantree;
typedef char **hufumanode;
hafumantree HT;
hufumanode HC;
int small(int x)/*求最小权值*/
{
int i=0,flag,k=32767;
for(i=0;i<=x;i++)
if(HT[i].weight<k&&HT[i].parent==0)
{
k=HT[i].weight;
flag=i;
}
HT[flag].parent=1;
return flag;
}
void select(int i,int *s1,int *s2)/*选择s1,s2,为最小的两个权值(s1<s2)*/
{
int temp;
*s1=small(i);
*s2=small(i);
if(*s1>*s2)
swap(*s1,*s2,temp);
}
void hufumancoding(int *w,int n)/*编译码*/
{
int m,i,s1,s2,f,c,start;
hafumantree p;
char *code;
m=2*n-1;
HT=(HTnode *)malloc(m*sizeof(HTnode));
if(!HT)
{
printf("\noverflow!");
exit(0);
}
p=HT;
for(i=0;i<n;i++,p++)
{
(*p).weight=w[i];
(*p).parent=0;
(*p).lchild=0;
(*p).rchild=0;
}
for(;i<m;i++,p++)
(*p).parent=0;
for(i=n;i<m;i++)
{
select(i-1,&s1,&s2);
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
HT[s1].parent=HT[s2].parent=i;
}
HC=(hufumanode)malloc(n*sizeof(char *));/*开始译码*/
code=(char *)malloc((n+1)*sizeof(char));
code[n]='\0';
for(i=0;i<n;i++)
{
start=n;
c=i;
for(f=HT[c].parent;f!=0;c=f,f=HT[c].parent)
if(HT[f].lchild==c)
code[--start]='0';
else
code[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char));
strcpy(HC[i],&code[start]);
printf("%c:",string[i]);
puts(HC[i]);
printf("\n");
}
free(code);/*释放工作空间*/
}
void tongji()/*统计文件中字符出现的次数*/
{
FILE *fp;
int i,count;
char ch,m;
if((fp=fopen("d:\\wenjian.txt","r"))==NULL)
{
printf("cannot open this file.\n");
exit(0);
}
for(i=0;i<N;i++)
{
  count=0;
    ch=string[i];
   while((m=fgetc(fp))!=EOF)
    {
       if(isalpha(m))
        {
         if(m==ch||m==ch-32)
              count++;
         }
    }
  num[i]=count;
  fp=fopen("d:\\wenjian.txt","r");
}
printf("\nthe alphals merge's times:\n");
for(i=0;i<N;i++)
{
printf("\n %c:",string[i]);
printf("%d",num[i]);
}
}
void  main()
{
int *w,i=0;//,n;
//clrscr();
tongji();
w=(int *)malloc(N*sizeof(int));
for(;i<N;i++)
w[i]=num[i];
hufumancoding(w,N);
}