哈夫曼编码解码实验报告

哈夫曼编码解码实验实验要求掌握二叉树的相关概念掌握构造哈夫曼树，进行哈夫曼编码。对编码内容通过哈夫曼树进行解码。实验内容通过二叉树构造哈夫曼树，并用哈夫曼树对读取的txt文件进行哈夫曼编码。编码完成后通过哈夫曼树进行解码。#include<stdio.h>#include<string.h>#defineMAX100//定义哈夫曼树的存储结构typedefstruct{chardata;intweight;intparent;intlch;intrch;}HuffNode;//定义哈夫曼编码的存储结构typedefstruct{charbit[MAX];intstart;}HuffCode;HuffNodeht[2*MAX];HuffCodehcd[MAX];intCoun[127]={0};intn;chars1[200000];chartext[5000];//构造哈夫曼树voidHuffmanTree(){inti,j,k,left,right,min1,min2;//printf("输入叶子的节点数：");//scanf("%d",&n);printf("字符数量=%d\n",n);for(i=1;i<=2*n-1;i++){ht[i].parent=ht[i].lch=ht[i].rch=0;}j=0;for(i=1;i<=n;i++){/*getchar();printf("输入第%d个叶子节点的值：",i);scanf("%c",&ht[i].data);printf("输入该节点的权值：");scanf("%d",&ht[i].weight);*/for(;j<127;j++){if(Coun[j]!=0){ht[i].data=j;//printf("%c",ht[i].data);ht[i].weight=Coun[j];//printf("%d",ht[i].weight);break;}}j++;}printf("\n");for(i=1;i<=n;i++){printf("%c",ht[i].data);}printf("\n");for(i=n+1;i<=2*n-1;i++){//在前n个结点中选取权值最小的两个结点构成一颗二叉树min1=min2=10000;//为min1和min2设置一个比所有权值都大的值left=right=0;for(k=1;k<=i-1;k++){if(ht[k].parent==0)//假设是根结点//令min1和min2为最小的两个权值，left和right为权值最小的两个结点位置if(ht[k].weight<min1){min2=min1;right=left;min1=ht[k].weight;left=k;}elseif(ht[k].weight<min2){min2=ht[k].weight;right=k;}}ht[left].parent=i;ht[right].parent=i;ht[i].weight=ht[left].weight+ht[right].weight;ht[i].lch=left;ht[i].rch=right;}}//构造哈夫曼编码voidHuffmanCode(){inti,c,k,f;HuffCodecd;for(i=1;i<=n;i++){cd.start=n;c=i;f=ht[i].parent;while(f!=0){if(ht[f].lch==c)cd.bit[cd.start]='0';elsecd.bit[cd.start]='1';cd.start--;c=f;f=ht[f].parent;}hcd[i]=cd;}printf("输出哈夫曼编码：\n");for(i=1;i<=n;i++){printf("%c:",ht[i].data);for(k=hcd[i].start+1;k<=n;k++)printf("%c",hcd[i].bit[k]);printf("\n");}}//对字母进行编码voidCode()//将字符与相应的哈夫曼编码进行匹配，输出编码结果{inti=0,j,k,h=0;while(text[i]!='\0'){for(j=1;j<=n;j++){if(text[i]==ht[j].data){for(k=hcd[j].start+1;k<=n;k++){s1[h]=hcd[j].bit[k];h++;}break;}}i++;}//printf("编码\n");//puts(s1);//printf("\n");}//解码voidHuffmanDecode(){printf("解码\n");intlen,i,f;charC;//charS[MAXCODE];//scanf("%s",S);//使用gets()直接跳过len=strlen(s1);printf("s1:%d\n",len);f=2*n-1;for(i=0;i<len;i++){if(s1[i]=='0'){f=ht[f].lch;if(ht[f].lch==0&&ht[f].rch==0){C=ht[f].data;printf("%c",C);f=2*n-1;}}elseif(s1[i]=='1'){f=ht[f].rch;if(ht[f].lch==0&&ht[f].rch==0){C=ht[f].data;printf("%c",C);f=2*n-1;}}}printf("\n");}//统计字母个数及其权值voidCount(){inti,j,m;n=0;i=0;//printf("请仅输入小写字母\n");//例程本省存在一个BUG，只输入一个字母不能进行编码〔并未解决〕//scanf("%s",s);while(text[i]!='\0')//使用ASCII码表进行统计{m=text[i];//printf("%d\n",m);Coun[m]++;i++;}for(j=0;j<127;j++){if(Coun[j]!=0)n++;}}//markCodevoidmain(){intl=0;FILE*fp;fp=fopen("text.txt","r");if(fp==NULL){printf("文件翻开失败\n");while(1);}while(!feof(fp)){text[l]=fgetc(fp);l++;}printf("输入文本\n");printf("%s\n",text);fclose(fp);Count();HuffmanTree()