HUFFman和香农编码

HUFFman和香农编码HUFFman和香农编码 #include #include #include //Huffman编码 #define MaxSize 50 typedef struct SHNODE{ float w; //代码概率; char code[MaxSize]; //HUFFMAN代码的编码; int Code[MaxSize]; //香农编码; int m; //码长; float p_sum; /*第i个消息符号累加概率*/ struct SHNODE *next; }HuffCo...

HUFFman和香农编码 #include #include #include //Huffman编码 #define MaxSize 50 typedef struct SHNODE{ float w; //代码概率; char code[MaxSize]; //HUFFMAN代码的编码; int Code[MaxSize]; //香农编码; int m; //码长; float p_sum; /*第i个消息符号累加概率*/ struct SHNODE *next; }HuffCode[MaxSize]; typedef struct HTNode{ float Weight; //权值; int LChild,RChild,Parent; }HuffTree[MaxSize]; //============================================================================== == void HuffmanTree(HuffTree HT,int length,HuffCode hc); //生成Huffman树; void SelectHTNode(HuffTree HT,int n,int *min1,int *min2); //查找最小和次小序号; void HuffmanCode(HuffTree HT,int len,HuffCode hc); //生成Huffman编码; //============================================================================== == //香农编码 float sym_arry[MaxSize]; /*序列的概率*/ //============================================================================== == void pb_scan(int len); /*得到序列概率*/ void pb_sort(int len); /*序列概率排序*/ void valuelist(struct SHNODE *L,int len); /*计算累加概率，码长，码字*/ void codedisp(struct SHNODE *L,int len); //============================================================================== == struct SHNODE *setnull() { struct SHNODE *head; head=(struct SHNODE *)malloc(sizeof(struct SHNODE)); head->next=NULL; return(head); } struct SHNODE *my_creat(float a[],int n) { struct SHNODE *head,*p,*r; int i; head=setnull(); r=head; for(i=0;iw=a[i]; p->next=NULL; r->next=p; r=p; } return(head); } int main(void) { struct SHNODE *head; int len; printf("<<<< Huffman编码和香农编码生成程序 >>>>:-)...\n\n\n\n"); printf("\n输入代码数量："); scanf("%d",&len); system("cls"); printf("代码数量：%2d\n\n",len); printf("输入概率(概率之和应该等于1)：\n"); pb_scan(len); pb_sort(len); head=my_creat(sym_arry,len); valuelist(head,len); codedisp(head,len); return 0; } void pb_scan(int len) { HuffTree HT; //Huffman树; HuffCode HC; //Huffman编码; int i; float j=0,HX=0,sum=0; loop:for(i=1;i <= len;i++) { while(getchar() != '\n') NULL; printf("\nNo.%2d： ",i); scanf("%f",&HC[i].w); sym_arry[i-1]=HC[i].w; sum=sum+HC[i].w; } /*判断序列的概率之和是否等于1，在实现这块模块时，scanf()对float数的缺陷，故只要满足0.991.0001||sum<0.99) { printf("sum=%f,sum must (<0.999= HT[i].Weight) { *min2 = *min1; *min1 = i; } else if(HT[*min2].Weight > HT[i].Weight) *min2 = i; } } } //================================================================================ void HuffmanCode(HuffTree HT,int len,HuffCode hc) //生成Huffman编码; { int i,j,tc,Stack[MaxSize],top = -1; char flag[MaxSize]; struct HTNode th; for(i = 1;i <= len;i++) { top = -1; //栈初始化; j = 0; //hc[i].code串首位置偏移; th = HT[i]; //当前结点th; tc = i; //当前结点标记tc; while(th.Parent != -1) { //当前结点th双亲P入栈,由P的孩子是th,确定flag;确定下次结点标记tc; Stack[++top] = th.Parent; if(HT[th.Parent].LChild == tc) {flag[top] = 'L'; tc = th.Parent;} if(HT[th.Parent].RChild == tc) {flag[top] = 'R'; tc = th.Parent;} th = HT[Stack[top]]; //下一结点; } while(top != -1) { if(flag[top] == 'L') hc[i].code[j++] ='0'; else hc[i].code[j++] ='1'; Stack[top--]; //出栈; } hc[i].code[j] ='\0'; //当前串结束; hc[i].m=j--; } } /*选择法排序*/ void pb_sort(int len) { int i,j,pos; float max; for(i=0;imax) { max=sym_arry[j]; pos=j; } sym_arry[pos]=sym_arry[i]; sym_arry[i]=max; } } void codedisp(struct SHNODE *L,int len) { int i,j; struct SHNODE *p; float hx=0,KL=0; /*hx存放序列的熵的结果，KL存放序列编码后的平均码字的结果 */ p=L->next; printf("================================================================================ \n"); printf("香农编码：\n"); for(i=0;im;j++) printf("%d",p->Code[j]); printf("\n"); hx=(float)(hx-p->w*3.332*log10(p->w)); /*计算消息序列的熵*/ KL=KL+p->m*p->w; /*计算平均码字*/ p=p->next; } printf("信息熵为：\tHX=%3f\n",hx); printf("平均码长为：\tR=%3f\n",KL); printf("编码效率为：\t$=%3f\n",hx/KL); } void valuelist(struct SHNODE *L,int len) { struct SHNODE *head,*p; int j=0; int i; float temp,s; head=L; p=head->next; temp=0; while(jp_sum=temp; temp=temp+p->w; p->m=-3.322*log10(p->w)+1; /*编码，*/ { s=p->p_sum; for(i=0;im;i++) p->Code[i]=0; for(i=0;im;i++) { p->Code[i]=2*s; if(2*s>=1) s=2*s-1; else if(2*s==0) break; else s=2*s; } } j++; p=p->next; } }

                    本文档为【HUFFman和香农编码】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

HUFFman和香农编码

你可能还喜欢