哈夫曼树编码
写一个哈夫曼的编码,还没写完,不会调试,只把语法错误改了,其他的不会,那位高人帮忙给找一下错误,拜托了!
123.rar
(1.69 KB)
//赫夫曼编码器
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OVERFLOW 2
#define OK 1
#define ERROR 0
#define SIZE 27
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define CODEDNUM 8
typedef char elemtype;
typedef struct bitnode{
int weight,weighth;
int parent, lchild,rchild;
}htnode,*huffmantree;
typedef char * *huffmancode;
typedef struct Ncode{
int chn[SIZE];
char cha[SIZE];
}Ncode;
Ncode count(Ncode G){
int n=0,i=0,j,temp;
char ch,mid,c='a';
FILE *fp;
for(n=0;n<=26;n++) G.chn[n]=0;
if((fp=fopen("123.txt","r"))!=NULL) {
printf("根据所给文件,字符使用频率情况如下:\n");
while((ch=fgetc(fp))!=EOF){
if(ch>='a'&&ch<='z'){
n=ch-'a';
G.chn[n]++;
i++;
}
}
printf("\n------------------------------------------\n");
}
for(n=0,ch='a';n<26;n++,ch++) printf("%c=%d次\n",ch,G.chn[n]);
printf("其中字符总数为%d\n",i);
fclose(fp);
//对权值进行排序
for(i=0;i<26;i++) G.cha[i]=c++;
for(i=0;i<26;i++){
for(j=i+1;j<26;j++){
if(G.chn[i]<G.chn[j]){
temp=G.chn[j];G.chn[j]=G.chn[i];G.chn[i]=temp;
mid=G.cha[j];G.cha[j]=G.cha[i];G.cha[i]=mid;
}
}
}
printf("根据权值排序得:\n");
for(i=0;i<26;i++){
printf("%c ",G.cha[i]);
printf("%d ",G.chn[i]);
}
return G;
}
//选择未使用的权值最小的两个量
void select(huffmantree HT,int k,int &s1,int &s2){
int i,j,n,m[2],v[2];
for(n=0,i=CODEDNUM;i>0&&n<2;i--){
if(HT[i].parent!=0) m[n]=i;n++;
}
for(j=CODEDNUM+1,n=0;j<=k;j++){
if(HT[j].parent!=0) v[n]=j; n++;
}
i=m[0];j=m[1];n=v[0];k=v[1];
if(HT[j].weight<HT[n].weight) s1=i,s2=j;
else if(HT[i].weight<HT[n].weight) s1=i,s2=n;
else if(HT[i].weight<HT[k].weight) s1=n,s2=i;
else s1=n,s2=k;
}
void huffmancoding(huffmantree &HT,huffmancode &HC,Ncode G,int n){
int m,i,j,v,s1,s2,cdlen=0;
char *cd;
huffmantree p;
printf("进来了吗?");
if(n<=1) return;
m=2*n-1;
HT=(huffmantree)malloc((m+1)*sizeof(htnode));
for(p=HT++,i=1,j=0;i<=n;++i,++p,++j) {
p->weight =G.chn[j];
p->weighth=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(;i<=m;++i,++p){
p->weight =G.chn[j];
p->weighth=0;
p->parent=0;
p->lchild=0;
p->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;
}
//无栈非递归遍历哈夫曼树,求哈夫曼编码
v=m;
HC=(huffmancode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char ));
printf("%d",v);
while(v){
if(HT[v].weighth==0){
HT[v].weighth=1;
if(HT[v].lchild != 0) {v=HT[v].lchild; cd[cdlen++]='0';}
else if(HT[v].rchild==0){
i=HT[v].weight;
HC[v]=(char *)malloc((cdlen+1)*sizeof(char));
cd[cdlen]='\0';
strcpy(HC[v],cd);
printf("%d %s",i,*HC[v]);
}
}
else if(HT[v].weighth==1){
HT[v].weighth=2;
if(HT[v].rchild!=0){v=HT[v].lchild; cd[cdlen++]='1';}
}
else{
HT[v].weighth=0;v=HT[v].parent;--cdlen;
}
}
}
int main(){
Ncode R;
huffmantree htree;
huffmancode hcode;
R=count(R);
huffmancoding(htree,hcode,R,CODEDNUM);
return 0;
}