哈夫曼树与文件解压压缩C言代码

1.问题描述哈弗曼树的编码与译码—功能：实现对任何类型文件的压缩与解码—输入：源文件，压缩文件—输出：解码正确性判定，统计压缩率、编码与解码速度—要求：使用边编码边统计符号概率的方法（自适应Huffman编码）和事先统计概率的方法（静态Huffman编码）2.1程序清单程序书签：1.main函数2.压缩函数3.select函数4.encode函数5.解压函数#includestdio.h#includestring.h#includestdlib.h#includeconio.h#includetime.hstructnode{longweight;//权值unsignedcharch;//字符intparent,lchild,rchild;charcode[256];//编码的位数最多为256位intCodeLength;//编码长度}hfmnode[512];voidcompress();voiduncompress();//主函数voidmain(){intchoice;printf(请选择1~3：\n);printf(1.压缩文件\n);printf(2.解压文件\n);printf(3.退出！\n);scanf(%d,&choice);if(choice==1)compress();elseif(choice==2)uncompress();elseif(choice==3)return;elseprintf(输入错误！);}//压缩函数voidcompress(){inti,j;charinfile[20],outfile[20];FILE*ifp,*ofp;unsignedcharc;//longFileLength,filelength=0;intn,m;//叶子数和结点数ints1,s2;//权值最小的两个结点的标号charcodes[256];longsumlength=0;floatrate,speed;intcount=0;clock_tstart1,start2,finish1,finish2;doubleduration1,duration2;voidencode(structnode*nodep,intn);//编码函数intselect(structnode*nodep,intpose);//用于建哈弗曼树中选择权值最小的结点的函数printf(请输入要压缩的文件名:);scanf(%s,infile);ifp=fopen(infile,rb);if(ifp==NULL){printf(文件名输入错误，文件不存在!\n);return;}printf(请输入目标文件名:);scanf(%s,outfile);ofp=fopen(outfile,wb);if(ofp==NULL){printf(文件名输入错误，文件不存在!\n);return;}start1=clock();//开始计时1//统计文件中字符的种类以及各类字符的个数//先用字符的ASCII码值代替结点下标FileLength=0;while(!feof(ifp)){fread(&c,1,1,ifp);hfmnode[c].weight++;FileLength++;}FileLength--;//文件中最后一个字符的个数会多统计一次，所以要减一hfmnode[c].weight--;//再将ASCII转换为字符存入到结点的ch成员里，同时给双亲、孩子赋初值-1n=0;for(i=0;i256;i++)if(hfmnode[i].weight!=0){hfmnode[i].ch=(unsignedchar)i;n++;//叶子数hfmnode[i].lchild=hfmnode[i].rchild=hfmnode[i].parent=-1;}m=2*n-1;//哈弗曼树结点总数j=0;for(i=0;i256;i++)//去掉权值为0的结点if(hfmnode[i].weight!=0){hfmnode[j]=hfmnode[i];j++;}for(i=n;im;i++)//初始化根结点{hfmnode[i].lchild=hfmnode[i].rchild=-1;hfmnode[i].parent=-1;}//建立哈弗曼树for(i=n;im;i++){s1=select(hfmnode,i-1);hfmnode[i].lchild=s1;hfmnode[s1].parent=i;s2=select(hfmnode,i-1);hfmnode[i].rchild=s2;hfmnode[s2].parent=i;hfmnode[i].weight=hfmnode[s1].weight+hfmnode[s2].weight;}//编码encode(hfmnode,n);finish1=clock();duration1=(double)(finish1-start1)/CLOCKS_PER_SEC;/*printf(哈弗曼树编码用时为：%fseconds\n,duration1);*/printf(编码完成，是否查看编码信息:yorn?\n);c=getch();if(c=='y'){printf(\n);printf(叶子数为%d,结点数为%d\n,n,m);for(i=0;in;i++)printf(%d号叶子结点的权值为：%ld,双亲为：%d,左右孩子：%d,编码为：%s\n,i,hfmnode[i].weight,hfmnode[i].parent,hfmnode[i].lchild,hfmnode[i].code);}start2=clock();//开始计时2fseek(ifp,0,SEEK_SET);//将ifp指针移到文件开头位置fwrite(&FileLength,4,1,ofp);//将FileLength写入目标文件的前4个字节的位置fseek(ofp,8,SEEK_SET);//再将目标文件指针ofp移到距文件开头8个字节位置codes[0]=0;//将编码信息写入目标文件while(!feof(ifp)){fread(&c,1,1,ifp);filelength++;for(i=0;in;i++)if(c==hfmnode[i].ch)break;//ch必须也为unsigned型strcat(codes,hfmnode[i].code);while(strlen(codes)=8){for(i=0;i8;i++)//将codes的前8位01代码表示的字符存入c{if(codes[i]=='1')c=(c1)|1;elsec=c1;}fwrite(&c,1,1,ofp);//将新的字符写入目标文件sumlength++;strcpy(codes,codes+8);//更新codes的值}if(filelength==FileLength)break;}//再将剩余的不足8位的01代码补全8位，继续写入if(strlen(codes)0){strcat(codes,00000000);for(i=0;i8;i++){if(codes[i]=='1')c=(c1)|1;elsec=c1;}fwrite(&c,1,1,ofp);sumlength++;}sumlength+=8;printf(编码区总长为：%ld个字节\n,sumlength-8);//将sumlength和n的值写入目标文件，为的是方便解压fseek(ofp,4,SEEK_SET);fwrite(&sumlength,4,1,ofp);//把sumlength写进目标文件的第5-8个字节里fseek(ofp,sumlength,SEEK_SET);fwrite(&n,4,1,ofp);//把叶子数n写进编码段后面的4个字节的位置//为方便解压，把编码信息存入n后面的位置//存储方式为：n*（字符值（1个字节）+该字符的01编码的位数（1个字节）+编码（字节数不确定，用count来计算总值））for(i=0;in;i++){fwrite(&(hfmnode[i].ch),1,1,ofp);c=hfmnode[i].CodeLength;//编码最长为256位，因此只需用一个字节存储fwrite(&c,1,1,ofp);//写入字符的编码if(hfmnode[i].CodeLength%8!=0)for(j=hfmnode[i].CodeLength%8;j8;j++)//把编码不足8位的在低位补0,赋值给C，再把C写入strcat(hfmnode[i].code,0);while(hfmnode[i].code[0]!=0)//开始存入编码，每8位二进制数存入一个字节{c=0;for(j=0;j8;j++){if(hfmnode[i].code[j]=='1')c=(c1)|1;elsec=c1;}strcpy(hfmnode[i].code,hfmnode[i].code+8);//编码前移8位，继续存入编码count++;//编码占的字节数的总值fwrite(&c,1,1,ofp);}}printf(\n);finish2=clock();duration2=(double)(finish2-start2)/CLOCKS_PER_SEC;/*printf(写入目标文件用时为：%fseconds\n,duration2);*/printf(压缩用时为：%fseconds\n,duration1+duration2);speed=(float)FileLength/(duration1+duration2)/1000;printf(\n压缩速率为：%5.2fKB/S\n,speed);printf(\n);printf(源文件长度为：%ld个字节\n,FileLength);sumlength=sumlength+4+n*2+count;//计算压缩后文件的长度printf(压缩后文件长度为：%ld个字节\n,sumlength);rate=(float)sumlength/(float)FileLength;printf(压缩率(百分比)为：%4.2f%%%\n,rate*100);fclose(ifp);fclose(ofp);return;}//返回书签//建立哈弗曼树中用于选择最小权值结点的函数intselect(structnode*nodep,intpose){inti;ints1;longmin=2147483647;//s初值为long型的最大值for(i=0;i=pose;i++){if(nodep[i].parent!=-1)continue;if(nodep[i].weightmin){min=nodep[i].weight;s1=i;}}returns1;}//返回书签//哈弗曼编码函数voidencode(structnode*nodep,intn){//从叶子向根求每个字符的哈弗曼编码intstart;inti,f,c;charcodes[256];codes[n-1]='\0';//编码结束符for(i=0;in;i++)//逐个字符求哈弗曼编码{start=n-1;for(c=i,f=nodep[i].parent;f!=-1;c=f,f=nodep[f].parent){start--;if(nodep[f].lchild==c)codes[start]='0';elsecodes[start]='1';}strcpy(nodep[i].code,&codes[start]);nodep[i].CodeLength=strlen(nodep[i].code);}}//返回书签//解压函数voiduncompress()//解压文件{clock_tstart,finish;doubleduration;FILE*ifp,*ofp