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

1、實(shí)驗(yàn)七哈夫曼編碼哈夫曼編碼1. 問(wèn)題描述設(shè)某編碼系統(tǒng)共有n個(gè)字符，使用頻率分別為 1,2, ,wn ，設(shè)計(jì)一個(gè)不等長(zhǎng)的編ww碼方案，使得該編碼系統(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;int

2、 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+=count

3、;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)i4=i3,

4、i3=i;else if(hi.weight<hi4.weight)i4=i;void HuffmanTree(element *huffTree,int n)/ 哈夫曼樹(shù)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;huffTree

5、i2.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.lchild=-1 &

6、& 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.weight=wj)st

7、rcpy(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'elsek=huffTk.rchild;b1g+=&#

8、39;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;HuffmanTree(huf

9、fTree,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<<" 輸入編碼 :"gets(