實(shí)驗(yàn)七哈夫曼編碼實(shí)驗(yàn)

1、實(shí)驗(yàn)七 哈夫曼編碼哈夫曼編碼1. 問題描述設(shè)某編碼系統(tǒng)共有n個(gè)字符，使用頻率分別為w1, w2, , wn，設(shè)計(jì)一個(gè)不等長的編碼方案，使得該編碼系統(tǒng)的空間效率最好。2. 基本要求 設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)； 設(shè)計(jì)編碼算法； 分析時(shí)間復(fù)雜度和空間復(fù)雜度。3. 編碼#include<iostream>#include<string.h>using namespace std;const int Size=10,Size1=50; struct elementint weight;int lchild,rchild,parent;char sSize;int wSize,w1Size;i

2、nt getW(char T1) /統(tǒng)計(jì)字母頻率，獲得權(quán)值char TSize1;strcpy(T,T1);char c;int count,k=0;for(int i=0;Ti!='0'i+)count=0;if(Ti>='a'&&T1<='z') c=Ti;sk=c;sk+1='0'if(c!='0')for(int j=0;Tj!='0'j+)if(Tj=c)count+; Tj='$'if(c!='0')w1k=count; wk+

3、=count;c='0'return k;void Select(element h,int &i3,int &i4)/獲得哈夫曼數(shù)組中權(quán)值最小的兩個(gè)下標(biāo)int c;i3=-1;i4=-1;for(int i=0;i3=-1;i+)if(hi.parent=-1)i3=i;for(i;i4=-1;i+)if(hi.parent=-1)i4=i;if(hi3.weight>hi4.weight) c=i3;i3=i4;i4=c;for(i;hi.weight>0;i+)if(hi.parent=-1)if(hi.weight<hi3.weight

4、)i4=i3,i3=i;else if(hi.weight<hi4.weight)i4=i;void HuffmanTree(element *huffTree,int n)/哈夫曼樹int i1,i2;for(int i=0;i<2*n-1;i+)huffTreei.parent=-1; huffTreei.lchild=-1; huffTreei.rchild=-1;for(i=0;i<n;i+)huffTreei.weight=wi;for(int k=n;k<2*n-1;k+)Select(huffTree,i1,i2);huffTreei1.parent=k;

5、huffTreei2.parent=k; huffTreek.weight=huffTreei1.weight+huffTreei2.weight; huffTreek.lchild=i1; huffTreek.rchild=i2;struct codetypechar bitsSize;char ch;codetype codeSize;void bm(element h,int m)/記錄路徑編碼char bSize;b0='0' int s1Size,cd;int top=-1,i=0,k;while(m!=-1|top!=-1)while(m!=-1)if(hm.lch

6、ild=-1 && hm.rchild=-1)/記錄路徑編碼'0'，'1'的算法，用到parent回溯。cd=0;for(int j=hm.parent;j!=-1;j=hj.parent)cd+;bcd='0'k=m;for(j=hk.parent;j!=-1;j=hj.parent)if(hj.lchild=k) b-cd='0'else b-cd='1'k=j;for(j=0;sj>='a'&&sj<='z'j+)if(hm.weig

7、ht=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.rch

8、ild;b1g+='1'b1g='0'if(huffTk.lchild=-1 && huffTk.rchild=-1)for(int j=0;j<n;j+)if(strcmp(b1,codej.bits)=0) cout<<codej.ch; break;k=2*n-2;g=0;cout<<endl;void main()char TSize1,tSize1;int n;cout<<"輸入字符串："gets(T);n=getW(T);element huffTreeSize1; Huf

9、fmanTree(huffTree,n);cout<<"編碼："<<endl;bm(huffTree,2*n-2);for(int i=0;i<n;i+) cout<<codei.ch<<":"<<codei.bits<<endl;for(i=0;Ti!='0'i+)for(int j=0;j<n;j+)if(Ti=codej.ch)cout<<codej.bits;cout<<endl;cout<<"輸入編碼:"ge