用哈夫曼树算法设计对文件文件的压缩和解压缩的实验程序解析

我在做综合实验,
基本要求： （1）文件名的输入可以从命令行给出或程序界面给出； （2）压缩和解压选择也可以从命令行给出或程序界面给出； （3）给出压缩后的指标：压缩率=压缩后的文件大小/压缩前的文件大小

自己找的一个程序,不是很懂,望请哪位C语言高手帮忙给些注解,越详细越好.
程序如下:http://wenwen.sogou.com/z/q711809331.htm
由于程序太长,我使用了链接.谢谢!

我想请大家直接在程序旁注解，尽量详细点！万分感谢----

楼主可以去看看最优二叉树的编码问题。
1、哈夫曼编码
在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5。然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。
为使不等长编码为前缀编码，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。
哈夫曼静态编码：它对需要编码的数据进行两遍扫描：第一遍统计原数据中各字符出现的频率，利用得到的频率值创建哈夫曼树，并必须把树的信息保存起来，即把字符0-255(2^8=256)的频率值以2-4BYTES的长度顺序存储起来，（用4Bytes的长度存储频率值，频率值的表示范围为0--2^32-1，这已足够表示大文件中字符出现的频率了）以便解压时创建同样的哈夫曼树进行解压；第二遍则根据第一遍扫描得到的哈夫曼树进行编码，并把编码后得到的码字存储起来。
哈夫曼动态编码：动态哈夫曼编码使用一棵动态变化的哈夫曼树，对第t+1个字符的编码是根据原始数据中前t个字符得到的哈夫曼树来进行的，编码和解码使用相同的初始哈夫曼树，每处理完一个字符，编码和解码使用相同的方法修改哈夫曼树，所以没有必要为解码而保存哈夫曼树的信息。编码和解码一个字符所需的时间与该字符的编码长度成正比，所以动态哈夫曼编码可实时进行。[3]
2、哈夫曼译码
在通信中，若将字符用哈夫曼编码形式发送出去，对方接收到编码后，将编码还原成字符的过程，称为哈夫曼译码。[4]

#include<stdio.h> #include<string.h> #include<stdlib.h> #include<conio.h> structhead { unsignedcharb; longcount; longparent,lch,rch; charbits[256]; } header[512],tmp; voidcompress() { charfilename[255],outputfile[255],buf[512]; unsignedcharc; longi,j,m,n,f; longmin1,pt1,flength; file*ifp,*ofp; printf("sourcefilename:"); gets(filename); ifp=fopen(filename,"rb"); if(ifp==null) { printf("sourcefileopenerror!\n"); return; } printf("destinationfilename:"); gets(outputfile); ofp=fopen(outputfile,"wb"); if(ofp==null) { printf("destinationfileopenerror!\n"); return; } flength=0; while(!feof(ifp)) { fread(&c,1,1,ifp); header[c].count++; flength++; } flength--; header[c].count--; for(i=0;i<512;i++) { if(header[i].count!=0)header[i].b=(unsignedchar)i; elseheader[i].b=0; header[i].parent=-1; header[i].lch=header[i].rch=-1; } for(i=0;i<256;i++) { for(j=i+1;j<256;j++) { if(header[i].count<header[j].count) { tmp=header[i]; header[i]=header[j]; header[j]=tmp; } } } for(i=0;i<256;i++)if(header[i].count==0)break; n=i; m=2*n-1; for(i=n;i<m;i++) { min1=999999999; for(j=0;j<i;j++) { if(header[j].parent!=-1)continue; if(min1>header[j].count) { pt1=j; min1=header[j].count; continue; } } header[i].count=header[pt1].count; header[pt1].parent=i; header[i].lch=pt1; min1=999999999; for(j=0;j<i;j++) { if(header[j].parent!=-1)continue; if(min1>header[j].count) { pt1=j; min1=header[j].count; continue; } } header[i].count+=header[pt1].count; header[i].rch=pt1; header[pt1].parent=i; } for(i=0;i<n;i++) { f=i; header[i].bits[0]=0; while(header[f].parent!=-1) { j=f; f=header[f].parent; if(header[f].lch==j) { j=strlen(header[i].bits); memmove(header[i].bits+1,header[i].bits,j+1); header[i].bits[0]='0'; } else { j=strlen(header[i].bits); memmove(header[i].bits+1,header[i].bits,j+1); header[i].bits[0]='1'; } } } fseek(ifp,0,seek_set); fwrite(&flength,sizeof(int),1,ofp); fseek(ofp,8,seek_set); buf[0]=0; f=0; pt1=8; while(!feof(ifp)) { c=fgetc(ifp); f++; for(i=0;i<n;i++) { if(c==header[i].b)break; } strcat(buf,header[i].bits); j=strlen(buf); c=0; while(j>=8) { for(i=0;i<8;i++) { if(buf[i]=='1')c=(c<<1)|1; elsec=c<<1; } fwrite(&c,1,1,ofp); pt1++; strcpy(buf,buf+8); j=strlen(buf); } if(f==flength)break; } if(j>0) { strcat(buf,"00000000"); for(i=0;i<8;i++) { if(buf[i]=='1')c=(c<<1)|1; elsec=c<<1; } fwrite(&c,1,1,ofp); pt1++; } fseek(ofp,4,seek_set); fwrite(&pt1,sizeof(long),1,ofp); fseek(ofp,pt1,seek_set); fwrite(&n,sizeof(long),1,ofp); for(i=0;i<n;i++) { fwrite(&(header[i].b),1,1,ofp); c=strlen(header[i].bits); fwrite(&c,1,1,ofp); j=strlen(header[i].bits); if(j%8!=0) { for(f=j%8;f<8;f++) strcat(header[i].bits,"0"); } while(header[i].bits[0]!=0) { c=0; for(j=0;j<8;j++) { if(header[i].bits[j]=='1')c=(c<<1)|1; elsec=c<<1; } strcpy(header[i].bits,header[i].bits+8); fwrite(&c,1,1,ofp); } } fclose(ifp); fclose(ofp); printf("compresssuccessfully!\n"); return; } voiduncompress() { charfilename[255],outputfile[255],buf[255],bx[255]; unsignedcharc; longi,j,m,n,f,p,l; longflength; file*ifp,*ofp; printf("sourcefilename:"); gets(filename); ifp=fopen(filename,"rb"); if(ifp==null) { printf("sourcefileopenerror!\n"); return; } printf("destinationfilename:"); gets(outputfile); ofp=fopen(outputfile,"wb"); if(ofp==null) { printf("destinationfileopenerror!\n"); return; } fread(&flength,sizeof(long),1,ifp); fread(&f,sizeof(long),1,ifp); fseek(ifp,f,seek_set); fread(&n,sizeof(long),1,ifp); for(i=0;i<n;i++) { fread(&header[i].b,1,1,ifp); fread(&c,1,1,ifp); p=(long)c; header[i].count=p; header[i].bits[0]=0; if(p%8>0)m=p/8+1; elsem=p/8; for(j=0;j<m;j++) { fread(&c,1,1,ifp); f=c; itoa(f,buf,2); f=strlen(buf); for(l=8;l>f;l--) { strcat(header[i].bits,"0"); } strcat(header[i].bits,buf); } header[i].bits[p]=0; } for(i=0;i<n;i++) { for(j=i+1;j<n;j++) { if(strlen(header[i].bits)>strlen(header[j].bits)) { tmp=header[i]; header[i]=header[j]; header[j]=tmp; } } } p=strlen(header[n-1].bits); fseek(ifp,8,seek_set); m=0; bx[0]=0; while(1) { while(strlen(bx)<(unsignedint)p) { fread(&c,1,1,ifp); f=c; itoa(f,buf,2); f=strlen(buf); for(l=8;l>f;l--) { strcat(bx,"0"); } strcat(bx,buf); } for(i=0;i<n;i++) { if(memcmp(header[i].bits,bx,header[i].count)==0)break; } strcpy(bx,bx+header[i].count); c=header[i].b; fwrite(&c,1,1,ofp); m++; if(m==flength)break; } fclose(ifp); fclose(ofp); printf("uncompresssuccessfully!\n"); return; } intmain() { intc; printf("1--compressfile\n"); printf("2--uncompressfile\n"); printf("select1or2:"); c=getch(); printf("%c\n",c); if(c=='1')compress(); elseif(c=='2')uncompress(); return0; }

如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！

点此我要举报以上问答信息