哈夫曼文件压缩实验报告.doc

《哈夫曼文件压缩实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、......数据结构实验报告三——哈夫曼文件压缩实验题目：哈夫曼文件压缩实验目标：输入一个有10k单词的英文文档。输出压缩后的二进制文件，并计算压缩比。数据结构：栈和哈夫曼树。1.定义栈（）typedefstruct{char*elem;intstacksize;inttop;}STACK;2.定义哈夫曼树（）typedefstruct{intweight;intleft,right;intparent;}HTNode;需要的操作有：1.初始化栈（Initstack）voidInitstack(STACK*

2、s){s->elem=(char*)malloc(sizeof(int)*1000);s->stacksize=1000;s->top=-1;.专业.专注.......}2.压栈（push）voidpush(STACK*s,inte){s->elem[++s->top]=e;}3.弹栈（pop）voidpop(STACK*s,int*e){if(s->top!=-1)*e=s->elem[s->top--];}4.构造哈夫曼树（Inithuffman）voidInithuffman(intwset[n],i

3、ntk,HuffTreeHT[]){//构造哈夫曼树inti,m;ints1,s2;m=k*2-1;for(i=0;iweight=(iparent=-1;HT[i]->left=HT[i]->right=-1;}for(i=k;i

4、);//在HT[1...i-1]中选择parent为0且weight为最小的两个结点，其下标分别为s1和s2HT[i]->left=s1;HT[i]->right=s2;HT[i]->weight=HT[s1]->weight+HT[s2]->weight;HT[s1]->parent=HT[s2]->parent=i;}}其中用到另一个基本操作：找到哈夫曼树中最小和次小的结点（select）5.找到哈夫曼树中最小和次小的结点（select）voidselect(HuffTreeHT[255],inta,i

5、nti,int*p,int*q){intj=0,k=0,*HT1,temp;HT1=(int*)malloc(sizeof(int)*(i-1));//存放权值for(j=0;jparent==-1){HT1[k]=HT[j]->weight;//把没有parent的结点的权值放在HT1中k++;}//printf("%4d%4d%4d%4d%4d",HT[j]->parent,HT[j]->left,HT[j]->right,HT[j]->weight,HT1[k-

6、1]);}.专业.专注.......j=0;while(j<2){//找到权值最小和第二小的结点for(k=j;k<(i-(i-a)*2);k++){if(HT1[j]>HT1[k]){temp=HT1[k];HT1[k]=HT1[j];HT1[j]=temp;}}j++;}k=0;for(j=0;jparent==-1)if(HT[j]->weight==HT1[0]&&k<1){//将最小的权值赋到*p中*p=j;k++;}j++;}for(j=0;j

7、j]->parent==-1).专业.专注.......if(j!=*p)if(HT[j]->weight==HT1[1]&&k<2){//将第二小的权值赋到*q中*q=j;k++;}j++;//printf("%4d%4d%4d%4d",HT[i]->parent,HT[i]->left,HT[i]->right,HT[i]->weight);}}6.根据哈夫曼树得到各字符对应的哈夫曼编码（Huffman）voidHuffman(HuffTreeHT[2*n-1],intk,charstr[][20]

8、){inti,j,e,t1=0,t2=0;charc;STACKst;for(i=0;iright==-1&&HT[i]->left==-1){//找一个叶子结点Initstack(&st);HT[i]->right=HT[i]->left==-2;j=i;//记录其下标while(HT[j]->parent!=-1){if(HT[HT[j]->parent]->right==