实验七哈夫曼编码实验

1、实验七 哈夫曼编码哈夫曼编码1. 问题描述设某编码系统共有n个字符，使用频率分别为w1, w2, , wn，设计一个不等长的编码方案，使得该编码系统的空间效率最好。2. 基本要求 设计数据结构； 设计编码算法； 分析时间复杂度和空间复杂度。3. 编码#include#includeusing namespace std;const int size=10,size1=50; struct elementint weight;int lchild,rchild,parent;char ssize;int wsize,w1size;int getw(char t1) /统计字母频率，获得权值cha

2、r tsize1;strcpy(t,t1);char c;int count,k=0;for(int i=0;ti!=0;i+)count=0;if(ti=a&t1hi4.weight) c=i3;i3=i4;i4=c;for(i;hi.weight0;i+)if(hi.parent=-1)if(hi.weighthi3.weight)i4=i3,i3=i;else if(hi.weighthi4.weight)i4=i;void huffmantree(element *hufftree,int n)/哈夫曼树int i1,i2;for(int i=0;i2*n-1;i+)hufftreei

3、.parent=-1; hufftreei.lchild=-1; hufftreei.rchild=-1;for(i=0;in;i+)hufftreei.weight=wi;for(int k=n;k=a&sj=z;j+)if(hm.weight=wj) strcpy(codei.bits,b);codei+.ch=sj;wj=-1;break;s1+top=m;m=hm.lchild;if(top!=-1)m=s1top-;m=hm.rchild;void jm(element hufft,int n,char t1)char b1size;b10=0;int k=2*n-2,g=0;for

4、(int i=0;t1i!=0;i+)if(t1i=0) k=hufftk.lchild;b1g+=0;b1g=0;else k=hufftk.rchild;b1g+=1;b1g=0;if(hufftk.lchild=-1 & hufftk.rchild=-1)for(int j=0;jn;j+)if(strcmp(b1,codej.bits)=0) coutcodej.ch; break;k=2*n-2;g=0;coutendl;void main()char tsize1,tsize1;int n;cout输入字符串：;gets(t);n=getw(t);element hufftreesize1; huffmantree(hufftree,n);cout编码：endl;bm(hufftree,2*n-2);for(int i=0;in;i+) coutcodei.ch:codei.bitsendl;for(i=0;ti!=0;i+)for(int j=0;jn;j+)if(ti=codej.ch)coutcodej.bits;coutendl;cout输入编码:;gets(t); cout解码：endl;jm(hufftree,n,t);4.实