哈夫曼树 上机实验 报告
现在上传,给大家共同分享! #include <stdio.h> #include<stdlib.h> #include<string.h> #include<malloc.h> #include<math.h> #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;i<e;i++) { sum1+=f.weight; *m=fabs(sum-2*sum1)>fabs(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;j<i;j++) { if(FN.ch==FN[j].ch) { printf("Same node!!!\n"); break; } } if(i==j) i++; } for(i=1;i<=n;i++) /*排序*/ { max=i+1; for(j=max;j<=n;j++) max=FN[max].weight<FN[j].weight?j:max; if(FN.weight<FN[max].weight) { w=FN.weight; FN.weight=FN[max].weight; FN[max].weight=w; c=FN.ch; FN.ch=FN[max].ch; FN[max].ch=c; } } for(i=1;i<=n;i++) /*初始化h*/ h=0; EnterQueue(Q,1,n); /*1和n进队*/ while(Q->front->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<stdio.h> #include<stdlib.h> #include<malloc.h> #include<string.h> #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<i;j++) if(ch[j]==ch) { tag=0; break; } if(tag) { (*CW)[++*p].c=ch; (*CW)[*p].weight=1; for(k=i+1;ch[k]!='\0';k++) if(ch==ch[k]) (*CW)[*p].weight++; } } *s=i; } /********创建HuffmanTree********/ void CreateHuffmanTree(Huffman *ht,WeightNode w,int n) { int i,j; int s1,s2; for(i=1;i<=n;i++) { (*ht).weight =w.weight; (*ht).parent=0; (*ht).LChild=0; (*ht).RChild=0; } for(i=n+1;i<=2*n-1;i++) { (*ht).weight=0; (*ht).parent=0; (*ht).LChild=0; (*ht).parent=0; } for(i=n+1;i<=2*n-1;i++) { for(j=1;j<=i-1;j++) if(!(*ht)[j].parent) break; s1=j; /*找到第一个双亲不为零的结点*/ for(;j<=i-1;j++) if(!(*ht)[j].parent) s1=(*ht)[s1].weight>(*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<m;i++) { for(k=1;k<=n;k++) /*从(*weight)[k].c中查找与ch相等的下标K*/ if(ch==weight[k].c) break; (*hc)=(char *)malloc((weight[k].num+1)*sizeof(char)); for(j=0;j<=weight[k].num;j++) (*hc)[j]=h[k][j]; } } /*****解码*****/ void TrsHuffmanTree(Huffman ht,WeightNode w,HuffmanCode hc,int n,int m) { int i=0,j,p; printf("***StringInformation***\n"); while(i<m) { p=2*n-1; for(j=0;hc[j]!='\0';j++) { if(hc[j]=='0') p=ht[p].LChild; else p=ht[p].RChild; } printf("%c",w[p].c); /*打印原信息*/ i++; } } main() { int i,n,m,s1,s2,j; /*n为叶子结点的个数*/ char ch[N],w[N]; /*ch[N]存放输入的字符串*/ Huffman ht; /*二叉数 */ HuffmanCode h,hc; /* h存放叶子结点的编码,hc 存放所有结点的编码*/ WeightNode weight; /*存放叶子结点的信息*/ printf("\t***HuffmanCoding***\n"); printf("please input information :"); gets(ch); /*输入字符串*/ CreateWeight(ch,&m,&weight,&n); /*产生叶子结点信息,m为字符串ch[]的长度*/ printf("***WeightInformation***\n Node "); /*输出叶子结点的字符与权值*/ for(i=1;i<=n;i++) printf("%c ",weight.c); printf("\nWeight "); for(i=1;i<=n;i++) printf("%d ",weight.weight); CreateHuffmanTree(&ht,weight,n); /*产生Huffman树*/ printf("\n***HuffamnTreeInformation***\n"); for(i=1;i<=2*n-1;i++) /*打印Huffman树的信息*/ printf("\t%d %d %d %d\n",i,ht.weight,ht.parent,ht.LChild,ht.RChild); CrtHuffmanNodeCode(ht,ch,&h,&weight,m,n); /*叶子结点的编码*/ printf(" ***NodeCode***\n"); /*打印叶子结点的编码*/ for(i=1;i<=n;i++) { printf("\t%c:",weight.c); printf("%s\n",h); } CrtHuffmanCode(ch,h,&hc,weight,n,m); /*所有字符的编码*/ printf("***StringCode***\n"); /*打印字符串的编码*/ for(i=0;i<m;i++) printf("%s",hc); system("pause"); TrsHuffmanTree(ht,weight,hc,n,m); /*解码*/ system("pause"); } Matlab 中简易实现Huffman编译码: n=input('Please input the total number: '); hf=zeros(2*n-1,5); hq=[]; for ki=1:n hf(ki,1)=ki; hf(ki,2)=input('Please input the frequency: '); hq=[hq,hf(ki,2)]; end for ki=n+1:2*n-1 hf(ki,1)=ki; mhq1=min(hq); m=size(hq); m=m(:,2); k=1; while k<=m%del min1 if hq(:,k)==mhq1 hq=[hq(:,1:(k-1)) hq(:,(k+1):m)]; m=m-1; break else k=k+1; end end k=1; while hf(k,2)~=mhq1|hf(k,5)==1%find min1 location k=k+1; end hf(k,5)=1; k1=k; mhq2=min(hq); k=1; while k<=m%del min2 if hq(:,k)==mhq2 hq=[hq(:,1:(k-1)) hq(:,(k+1):m)]; m=m-1; break else k=k+1; end end k=1; while hf(k,2)~=mhq2|hf(k,5)==1%find min2 location k=k+1; end hf(k,5)=1; k2=k; hf(ki,2)=mhq1+mhq2; hf(ki,3)=k1; hf(ki,4)=k2; hq=[hq hf(ki,2)]; end clc choose=input('Please choose what you want:\n1: Encoding\n2: Decoding\n3:.Exit\n'); while choose==1|choose==2 if choose==1 a=input('Please input the letter you want to Encoding: '); k=1; while hf(k,2)~=a k=k+1; if k>=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); r end choose=input('Please choose what you want:\n1: Encoding\n2: Decoding\n3:.Exit\n'); clc end if choose~=1&choose~=2 clc; end
- 1
- 粉丝: 7
- 资源: 2
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助