哈夫曼编码解码实验报告.doc

哈夫曼编码解码实验实验要求掌握二叉树的相关概念掌握构造哈夫曼树,进行哈夫曼编码。对编码内容通过哈夫曼树进行解码。实验内容通过二叉树构造哈夫曼树,并用哈夫曼树对读取的txt文件进行哈夫曼编码。编码完成后通过哈夫曼树进行解码。#include<>#include<>#defineMAX100//定义哈夫曼树的存储结构typedefstruct{ chardata; intweight; intparent; intlch; intrch;}HuffNode;//定义哈夫曼编码的存储结构typedefstruct{ charbit[MAX]; intstart;}HuffCode;HuffNodeht[2*MAX];HuffCodehcd[MAX];intCoun[127]={0};intn;chars1[200000];chartext[5000];//构造哈夫曼树voidHuffmanTree(){ inti,j,k,left,right,min1,min2; //printf("输入叶子的节点数:"); //scanf("%d",&n); printf("字符数量=%d\n",n); for(i=1;i<=2*n-1;i++) { ht[i].parent=ht[i].lch=ht[i].rch=0; } j=0; for(i=1;i<=n;i++) { /*getchar(); printf("输入第%d个叶子节点的值:",i); scanf("%c",&ht[i].data); printf("输入该节点的权值:"); scanf("%d",&ht[i].weight); */ for(;j<127;j++) { if(Coun[j]!=0) { ht[i].data=j; //printf("%c",ht[i].data); ht[i].weight=Coun[j]; //printf("%d",ht[i].weight); break; } } j++; } printf("\n"); for(i=1;i<=n;i++) { printf("%c",ht[i].data); } printf("\n"); for(i=n+1;i<=2*n-1;i++) {//在前n个结点中选取权值最小的两个结点构成一颗二叉树 min1=min2=10000;//为min1和min2设置一个比所有权值都大的值 left=right=0; for(k=1;k<=i-1;k++) { if(ht[k].parent==0)//若是根结点//令min1和min2为最小的两个权值,left和right为权值最小的两个结点位置 if(ht[k].weight<min1) { min2=min1; right=left; min1=ht[k].weight; left=k; } elseif(ht[k].weight<min2) { min2=ht[k].weight; right=k; } } ht[left].parent=i; ht[right].parent=i; ht[i].weight=ht[left].weight+ht[right].weight; ht[i].lch=left; ht[i].rch=right; }}//构造哈夫曼编码voidHuffmanCode(){ inti,c,k,f; HuffCodecd; for(i=1;i<=n;i++) { =n; c=i; f=ht[i].parent; while(f!=0) { if(ht[f].lch==c) []='0'; else []='1'; --; c=f; f=ht[f].parent; } hcd[i]=cd; } printf("输出哈夫曼编码:\n"); for(i=1;i<=n;i++) { printf("%c:",ht[i].data); for(k=hcd[i].start+1;k<=n;k++) printf("%c",hcd[i].bit[k]); printf("\n"); }}//对字母进行编码voidCode()//将字符与相应的哈夫曼编码进行匹配,输出编码结果{ inti=0,j,k,h=0; while(text[i]!='\0') { for(j=1;j<=n;j++) { if(text[i]==ht[j].data) { for(k=hcd[j].start+1;k<=n;k++) { s1[h]=hcd[j].bit[k]; h++; } break; } } i++; } //printf("编码\n");