Lab05树结构的应用学号：姓名：实验时间：2011.5.241.问题描述哈弗曼树的编码与译码—功能：实现对任何类型文件的压缩与解码—输入：源文件，压缩文件—输出：解码正确性判定，统计压缩率、编码与解码速度—要求：使用边编码边统计符号概率的方法（自适应Huffman编码）和事先统计概率的方法（静态Huffman编码）。2.1程序清单程序书签：1.main函数2.压缩函数3.select函数4.encode函数5.解压函数#include<stdio.h>#include<string.h>#include<stdlib.h>#include<conio.h>#include<time.h>structnode{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;i<256;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;i<256;i++)//去掉权值为0的结点if(hfmnode[i].weight!=0){hfmnode[j]=hfmnode[i];j++;}for(i=n;i<m;i++)//初始化根结点{hfmnode[i].lchild=hfmnode[i].rchild=-1;hfmnode[i].parent=-1;}//建立哈弗曼树for(i=n;i<m;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;i<n;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;i<n;i++)if(c==hfmnode[i].ch)break;//ch必须也为unsigned型strcat(codes,hfmnode[i].code);while(strlen(codes)>=8){for(i=0;i<8;i++)//将co...