实验七哈夫曼编码实验

实验七 哈夫曼编码哈夫曼编码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) /统计字母频率，获得权值char 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.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(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.实验结果5.实验