中财网庶女也有春天txt顾瑾瑄:哈弗曼编码
来源：百度文库 编辑：中财网 时间：2024/04/23 15:48:05
哈夫曼编码(Huffman Coding)是一种编码方式，哈夫曼编码是可变字长编码(VLC)的一种。uffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长 度最短的码字，有时称之为最佳编码，一般就叫作Huffman编码。 #include #include #include #include #define M 10 typedef struct Fano_Node { char ch; float weight; }FanoNode[M]; typedef struct node { int start; int end; struct node *next; }LinkQueueNode; typedef struct { LinkQueueNode *front; LinkQueueNode *rear; }LinkQueue; void EnterQueue(LinkQueue *q,int s,int e) { LinkQueueNode *NewNode; NewNode=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); if(NewNode!=NULL) { NewNode->start=s; NewNode->end=e; NewNode->next=NULL; q->rear->next=NewNode; q->rear=NewNode; } else printf("Error!"); } //***按权分组***// void Divide(FanoNode f,int s,int *m,int e) { int i; float sum,sum1; sum=0; for(i=s;i<=e;i++) sum+=f.weight; *m=s; sum1=0; for(i=s;ifabs(sum-2*sum1-2*f.weight)?(i+1):*m; if(*m==i) break; } } main() { int i,j,n,max,m,h[M]; int sta,mid,end; float w; char c,fc[M][M]; FanoNode FN; LinkQueueNode *p; LinkQueue *Q; //***初始化队Q***// Q->front=(LinkQueueNode *)malloc(sizeof(LinkQueueNode)); Q->rear=Q->front; Q->front->next=NULL; printf("\t***FanoCoding***\n"); printf("Please input the number of node:"); /*输入信息*/ scanf("%d",&n); i=1; while(i<=n) { printf("%d weight and node:",i); scanf("%f %c",&FN.weight,&FN.ch); for(j=1;jfront->next!=NULL) { p=Q->front->next; /*出队*/ Q->front->next=p->next; if(p==Q->rear) Q->rear=Q->front; sta=p->start; end=p->end; free(p); Divide(FN,sta,&m,end); /*按权分组*/ for(i=sta;i<=m;i++) { fc[h]='0'; h++; } if(sta!=m) EnterQueue(Q,sta,m); else fc[sta][h[sta]]='\0'; for(i=m+1;i<=end;i++) { fc[h]='1'; h++; } if(m==sta&&(m+1)==end) //如果分组后首元素的下标与中间元素的相等， { //并且和最后元素的下标相差为1，则编码码字字符串结束 fc[m][h[m]]='\0'; fc[end][h[end]]='\0'; } else EnterQueue(Q,m+1,end); } for(i=1;i<=n;i++) /*打印编码信息*/ { printf("%c:",FN.ch); printf("%s\n",fc); } system("pause"); } #include #include #include #include #define N 100 #define M 2*N-1 typedef char * HuffmanCode[2*M]; typedef struct { char weight; int parent; int LChild; int RChild; }HTNode,Huffman[M+1]; typedef struct Node { int weight; /*叶子结点的权值*/ char c; /*叶子结点*/ int num; /*叶子结点的二进制码的长度*/ }WNode,WeightNode[N]; /***产生叶子结点的字符和权值***/ void CreateWeight(char ch[],int *s,WeightNode *CW,int *p) { int i,j,k; int tag; *p=0; for(i=0;ch!='\0';i++) { tag=1; for(j=0;j(*ht)[j].weight?j:s1; (*ht)[s1].parent=i; (*ht).LChild=s1; for(j=1;j<=i-1;j++) if(!(*ht)[j].parent) break; s2=j; /*找到第一个双亲不为零的结点*/ for(;j<=i-1;j++) if(!(*ht)[j].parent) s2=(*ht)[s2].weight>(*ht)[j].weight?j:s2; (*ht)[s2].parent=i; (*ht).RChild=s2; (*ht).weight=(*ht)[s1].weight+(*ht)[s2].weight; } } /***********叶子结点的编码***********/ void CrtHuffmanNodeCode(Huffman ht,char ch[],HuffmanCode *h,WeightNode *weight,int m,int n) { int i,j,k,c,p,start; char *cd; cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\0'; for(i=1;i<=n;i++) { start=n-1; c=i; p=ht.parent; while(p) { start--; if(ht[p].LChild==c) cd[start]='0'; else cd[start]='1'; c=p; p=ht[p].parent; } (*weight).num=n-start; (*h)=(char *)malloc((n-start)*sizeof(char)); p=-1; strcpy((*h),&cd[start]); } system("pause"); } /*********所有字符的编码*********/ void CrtHuffmanCode(char ch[],HuffmanCode h,HuffmanCode *hc,WeightNode weight,int n,int m) { int i,j,k; for(i=0;i=n display('Error! You did not input this number.'); break end end if k>=n break end r=[]; while hf(k,5)==1 kc=n+1; while hf(kc,3)~=k&hf(kc,4)~=k kc=kc+1; end if hf(kc,3)==k r=[0 r]; else r=[1 r]; end k=kc; end r else a=input('Please input the metrix you want to Decoding: '); sa=size(a); sa=sa(:,2); k=2*n-1; while sa~=0 if a(:,1)==0 k=hf(k,3); else k=hf(k,4); end a=a(:,2:sa); sa=sa-1; if k==0 display('Error! The metrix you entered is a wrong one.'); break end end if k==0 break end r=hf(k,2); end choose=input('Please choose what you want:\n1: Encoding\n2: Decoding\n3:.Exit\n'); clc; end if choose~=1&choose~=2 clc; end