哈弗曼树的文件压和解压实验报告(C语言).doc

Lab05 树结构的应用 学号： 姓名： 实验时间：2011.5.24 1.问题描述 哈弗曼树的编码与译码 — 功能：实现对任何类型文件的压缩与解码 — 输入：源文件，压缩文件 — 输出：解码正确性判定，统计压缩率、编码与解码速度 — 要求： 使用边编码边统计符号概率的方法（自适应Huffman编码） 和事先统计概率的方法（静态Huffman编码） 。 2.1程序清单 程序书签： main函数 压缩函数 select函数 encode函数 解压函数 #include stdio.h #include string.h #include stdlib.h #include conio.h #include time.h struct node{ long weight; //权值 unsigned char ch;//字符 int parent,lchild,rchild; char code[256];//编码的位数最多为256位 int CodeLength;//编码长度 }hfmnode[512]; void compress(); void uncompress(); //主函数 void main() { int choice; printf(请选择1~3：\n); printf(1.压缩文件\n); printf(2.解压文件\n); printf(3.退出！\n); scanf(%d,choice); if(choice==1)compress(); else if(choice==2)uncompress(); else if(choice==3)return; else printf(输入错误！); } //压缩函数 void compress() { int i,j; char infile[20],outfile[20]; FILE *ifp,*ofp; unsigned char c;// long FileLength,filelength=0; int n,m;//叶子数和结点数 int s1,s2; //权值最小的两个结点的标号 char codes[256]; long sumlength=0; float rate,speed; int count=0; clock_t start1, start2,finish1,finish2; double duration1,duration2; void encode(struct node *nodep,int n);//编码函数 int select(struct node *nodep,int pose);//用于建哈弗曼树中选择权值最小的结点的函数 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成员里，同时给双亲、孩子赋初值-1 n=0; for(i=0;i256;i++) if(hfmnode[i].weight!=0) { hfmnode[i].ch=(unsigned char)i; n++;//叶子数 hfm