欢迎来到天天文库
浏览记录
ID:48971091
大小:231.50 KB
页数:11页
时间:2020-02-26
《哈夫曼文件压缩实验报告.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、数据结构实验报告三——哈夫曼文件压缩实验题目:哈夫曼文件压缩实验目标:输入一个有10k单词的英文文档。输出压缩后的二进制文件,并计算压缩比。数据结构:栈和哈夫曼树。1.定义栈()typedefstruct{char*elem;intstacksize;inttop;}STACK;2.定义哈夫曼树()typedefstruct{intweight;intleft,right;intparent;}HTNode;需要的操作有:1.初始化栈(Initstack)voidInitstack(STACK*s){s->el
2、em=(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],intk,HuffTreeHT[]){//构造哈
3、夫曼树inti,m;ints1,s2;m=k*2-1;for(i=0;iweight=(iparent=-1;HT[i]->left=HT[i]->right=-1;}for(i=k;i4、两个结点,其下标分别为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,inti,int*p,int*q){intj=0,k=0,*HT1,temp;HT5、1=(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-1]);}j=0;while(j<2){//找到权值最小和第二小的结点for(k=j6、;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;jparent==-1)if(j!=*p)if(HT[j]->weight==HT1[1]&&k<2){//7、将第二小的权值赋到*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]){inti,j,e,t1=0,t2=0;charc;STACKst;for(i=0;iright==-1&8、&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==j)//找到一个叶子结点,如果他是其parent结点的右结点,就将此边记为1push(&st,'1');elsepu
4、两个结点,其下标分别为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,inti,int*p,int*q){intj=0,k=0,*HT1,temp;HT
5、1=(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-1]);}j=0;while(j<2){//找到权值最小和第二小的结点for(k=j
6、;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;jparent==-1)if(j!=*p)if(HT[j]->weight==HT1[1]&&k<2){//
7、将第二小的权值赋到*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]){inti,j,e,t1=0,t2=0;charc;STACKst;for(i=0;iright==-1&
8、&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==j)//找到一个叶子结点,如果他是其parent结点的右结点,就将此边记为1push(&st,'1');elsepu
此文档下载收益归作者所有