首页 > 代码库 > huffuman编码
huffuman编码
#include "stdafx.h" #include <iostream> using namespace std; typedef struct { int w; int p,l,r; }HNode,*HTree; typedef char** HCode; void select(HTree ht,int n,int& s1,int& s2) { int min[2]={1000,1000}; for(int i=1;i<=n;i++) { if(ht[i].p==0) { if(ht[i].w<min[0]) { min[1]=min[0]; s2=s1; min[0]=ht[i].w; s1=i; } else if(ht[i].w<min[1]) { min[1]=ht[i].w; s2=i; } else {} } } } void HuffumanCoding(HCode& code,int *w,int n) { int m=2*n-1; HTree ht=(HTree)malloc((m+1)*sizeof(HNode)); memset(ht,0,(m+1)*sizeof(HNode)); for(int i=1;i<=n;i++) { ht[i].w=*(w+i-1); } for(int i=n+1;i<=m;i++) { int s1,s2; select(ht,i-1,s1,s2); ht[i].w=ht[s1].w+ht[s2].w; ht[i].l=s1; ht[i].r=s2; ht[s1].p=i; ht[s2].p=i; } code=(HCode)malloc((n+1)*sizeof(char*)); char* cd=(char*)malloc((n+1)*sizeof(char)); for(int i=1;i<=n;i++) { int cnt=0; int child=i; int p=ht[i].p; while(p!=0) { if(child==ht[p].l) { cd[cnt++]='0'; } else { cd[cnt++]='1'; } child=p; p=ht[p].p; } code[i]=(char*)malloc((cnt+1)*sizeof(char)); code[i][cnt]='\0'; for(int j=cnt-1;j>=0;j--) { code[i][cnt-1-j]=cd[j]; } } free(cd); free(ht); return; } void showCode(char* ch,HCode code,int n) { for(int i=1;i<=n;i++) { cout<<ch[i-1]<<":"; cout<<code[i]<<endl; } } int main(void) { char ch[]="12345678"; int w[]={5,29,7,8,14,23,3,11}; HCode hc; HuffumanCoding(hc,w,8); showCode(ch,hc,8); system("pause"); return 0; }
#include "stdafx.h" #include <iostream> using namespace std; typedef struct { int w; int p,l,r; }HNode,*HTree; typedef char** HCode; void select(HTree ht,int n,int& s1,int& s2) { int min[2]={1000,1000}; for(int i=1;i<=n;i++) { if(ht[i].p==0) { if(ht[i].w<min[0]) { min[1]=min[0]; s2=s1; min[0]=ht[i].w; s1=i; } else if(ht[i].w<min[1]) { min[1]=ht[i].w; s2=i; } else {} } } } void HuffumanCoding(HCode& code,int *w,int n) { int m=2*n-1; HTree ht=(HTree)malloc((m+1)*sizeof(HNode)); memset(ht,0,(m+1)*sizeof(HNode)); for(int i=1;i<=n;i++) { ht[i].w=*(w+i-1); } for(int i=n+1;i<=m;i++) { int s1,s2; select(ht,i-1,s1,s2); ht[i].w=ht[s1].w+ht[s2].w; ht[i].l=s1; ht[i].r=s2; ht[s1].p=i; ht[s2].p=i; } code=(HCode)malloc((n+1)*sizeof(char*)); char* cd=(char*)malloc((n+1)*sizeof(char)); char*pcd=cd; int cdlen=0; for(int i=1;i<=m;i++) { ht[i].w=0; } int p=m; while(p) { if(ht[p].w==0) { ht[p].w=1; if(ht[p].l!=0) { *pcd++='0'; cdlen++; p=ht[p].l; } else if(ht[p].r==0) { *pcd='\0'; code[p]=(char*)malloc((cdlen+1)*sizeof(char)); strcpy(code[p],cd); } else {} } else if(ht[p].w==1) { ht[p].w=2; if(ht[p].r!=0) { *pcd++='1'; cdlen++; p=ht[p].r; } } else { ht[p].w=0; p=ht[p].p; pcd--; cdlen--; } } free(cd); free(ht); return; } void showCode(char* ch,HCode code,int n) { for(int i=1;i<=n;i++) { cout<<ch[i-1]<<":"; cout<<code[i]<<endl; } } int main(void) { char ch[]="12345678"; int w[]={5,29,7,8,14,23,3,11}; HCode hc; HuffumanCoding(hc,w,8); showCode(ch,hc,8); system("pause"); return 0; }
huffuman编码
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。