小弟现在做毕业设计，用C语言做基于霍夫曼算法的文件压缩。要求是从一篇文章中读取每个字符，然后统计字符个数，再根据字符个数建造霍夫曼树，并编成0，1代码。源程序如下，请各位高手指点以下，因为我的程序执行后的结果有错误。words.txt文件在附件中。请大家快快帮忙啊，小弟现在非常着急，谢谢各位了！
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <malloc.h>
#include <conio.h>
/*#define N 26*/
typedef struct
{
unsigned int weight;
unsigned int parent,lchild,rchild;
} HTNode,*HuffmanTree;
typedef char **HuffmanCode;
typedef struct {
unsigned int s1;
unsigned int s2;
} MinCode;
void Error(char *message);
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n);
MinCode Select(HuffmanTree HT,unsigned int n);
void Error(char *message)
{
clrscr();
fprintf(stderr,"Error:%s\n",message);
exit(1);
}
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,unsigned int *w,unsigned int n)
{
unsigned int i,s1=0,s2=0;
HuffmanTree p;
char *cd;
unsigned int f,c,start,m;
MinCode min;
if(n<=1) Error("Code too small!");
m=2*n-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(p=HT,i=0;i<=n;i++,p++,w++)/************i<=n**************/
{
p->weight=*w;
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+1;i<=m;i++)/************************/
{
min=Select(HT,i-1);
s1=min.s1;
s2=min.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;
}
printf("HT List:\n");
printf("Number\t\tweight\t\tparent\t\tlchild\t\trchild\n");
for(i=0;i<=m;i++)/*************0->1*************************************/
printf("%d\t\t%d\t\t%d\t\t%d\t\t%d\n",
i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char *));
cd[n-1]='\0';
for(i=0;i<=n;i++)/*******!!!1---n***********************/
{
start=n-1;/*************************************/
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
HC[i]=(char *)malloc((n-start)*sizeof(char *));
strcpy(HC[i],&cd[start]);
}
free(cd);
return HC;
}
MinCode Select(HuffmanTree HT,unsigned int n)
{
unsigned int min,secmin;
unsigned int temp;
unsigned int i,s1,s2,tempi;
MinCode code;
s1=1;s2=1;
for(i=0;i<=n;i++)/*****!!!!***1---n*************/
if(HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
break;
}
tempi=i++;
for(;i<=n;i++)/*************************************/
if(HT[i].weight<min&&HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
}
for(i=tempi;i<=n;i++)/********************************/
if(HT[i].parent==0&&i!=s1)
{
secmin=HT[i].weight;
s2=i;
break;
}
for(i=1;i<=n;i++)/***********************************/
if(HT[i].weight<secmin&&i!=s1&&HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
if(s1>s2)
{
temp=s1;
s1=s2;
s2=temp;
}
code.s1=s1;
code.s2=s2;
return code;
}
main()
{
HuffmanTree HT=NULL;
HuffmanCode HC=NULL;
unsigned int num[26];
unsigned int n=26;
char ch;
char zifu[800];
int i;
char c;
FILE *fp;
clrscr();
if((fp=fopen("words.txt","r"))==NULL)
{
printf("open file error!--words.txt\n");
exit(0);
}
if((ch=fgetc(fp))==EOF)
{
printf("\nempty file!");
}
zifu[0]=ch;
if((ch!=EOF)&&(ch>='A'&&ch<='Z')||(ch>='a'&&ch<='z'))
{
for(i=1;i<800;i++)
{
ch=fgetc(fp);
zifu[i]=ch;
}
}
for(i=0;i<800;i++)
{
if(zifu[i]!='\0')
printf("%c",zifu[i]);
}
printf("\n");
fclose(fp);
printf("press anykey,go on...");
getchar();
printf("\n");
for(i=0;i<n;i++)/*******************/
{
num[i]=0;
}
for(i=0;(c = zifu[i])!='\0';i++)
{
if (tolower(c) =='a')
{
num[0]=num[0]+1;
}
if (tolower(c)=='b')
{
num[1]=num[1]+1;
}
if (tolower(c) =='c')
{
num[2]=num[2]+1;
}
if (tolower(c)=='d' )
{
num[3]=num[3]+1;
}
if (tolower(c) =='e')
{
num[4]=num[4]+1;
}
if (tolower(c) =='f')
{
num[5]=num[5]+1;
}
if (tolower(c) =='g')
{
num[6]=num[6]+1;
}
if (tolower(c) =='h')
{
num[7]=num[7]+1;
}
if (tolower(c) =='i')
{
num[8]=num[8]+1;
}
if (tolower(c) =='j')
{
num[9]=num[9]+1;
}
if (tolower(c) =='k')
{
num[10]=num[10]+1;
}
if (tolower(c) =='l')
{
num[11]=num[11]+1;
}
if (tolower(c) =='m')
{
num[12]=num[12]+1;
}
if (tolower(c) =='n')
{
num[13]=num[13]+1;
}
if (tolower(c) =='o')
{
num[14]=num[14]+1;
}
if (tolower(c) =='p')
{
num[15]=num[15]+1;
}
if (tolower(c) =='q')
{
num[16]=num[16]+1;
}
if (tolower(c) =='r')
{
num[17]=num[17]+1;
}
if (tolower(c) =='s')
{
num[18]=num[18]+1;
}
if (tolower(c) =='t')
{
num[19]=num[19]+1;
}
if (tolower(c) =='u')
{
num[20]=num[20]+1;
}
if (tolower(c) =='v')
{
num[21]=num[21]+1;
}
if (tolower(c) =='w')
{
num[22]=num[22]+1;
}
if (tolower(c) =='x')
{
num[23]=num[23]+1;
}
if (tolower(c) =='y')
{
num[24]=num[24]+1;
}
if (tolower(c) =='z')
{
num[25]=num[25]+1;
}
}
for(i=0;i<n;i++)/****************************/
{
printf("number of %c is:%2d",97+i,num[i]);
printf("\n");
}
printf("\n");
printf("press anykey,go on...");
getchar();
printf("\n");
HC=HuffmanCoding(HT,HC,num,n);/************************/
printf("\n");
printf("press anykey,go on...");
getchar();
printf("\n");
printf("HuffmanCode:\n");
printf("Number\t\tWeight\t\tCode\n");
for(i=0;i<n;i++)/******************/
printf("%d\t\t%d\t\t%s\n",i,num[i],HC[i]);
/*clrscr();*/
HC=NULL;
return 0;
}
igyXYFjF.txt
