數(shù)據(jù)結(jié)構(gòu)與算法——電文的編碼和譯碼

1、電文的編碼和譯碼1. 問題描述 從鍵盤接受一串電文字符，輸出對應(yīng)的哈夫曼編碼；同時能翻譯由哈夫曼編碼生成的代碼串，輸出對應(yīng)的電文字符串。2. 設(shè)計要求(1) 構(gòu)造一棵哈夫曼樹。(2) 實現(xiàn)哈夫曼編碼，并用哈夫曼編碼生成的代碼進(jìn)行譯碼。(3) 程序中字符和權(quán)值是可變的，實現(xiàn)程序的靈活性。3. 數(shù)據(jù)結(jié)構(gòu) 本課程設(shè)計采用結(jié)構(gòu)體數(shù)組作為數(shù)據(jù)結(jié)構(gòu)，來儲存哈夫曼樹及其編碼。4. 分析與實現(xiàn) 在電報通信中，電文是以二進(jìn)制代碼傳送的。在發(fā)送時，需要將電文中的字符轉(zhuǎn)換成二進(jìn)制代碼串，即編碼；在接收時，要將收到的二進(jìn)制代碼串轉(zhuǎn)化成對應(yīng)的字符序列，即譯碼。字符被使用的頻率是非均勻的。在傳送電文時，要想使電文總長盡可

2、能短，就需要讓使用頻率高的字符編碼長度盡可能短。因此，若對某字符集進(jìn)行不定長編碼設(shè)計，則要求任一一個字符編碼都不能使其他字符編碼的前綴，這種編碼稱作前綴編碼。 由哈弗曼樹求得的編碼是最優(yōu)前綴碼，也稱哈夫曼編碼。給出字符集和各個字符的概率分布，構(gòu)造哈弗曼樹，將哈夫曼樹中每個分支結(jié)點的左分支標(biāo)0，右分支標(biāo)1，從根到每個葉子的路徑上的標(biāo)號連起來就是給葉子所代表字符的編碼。(1) 構(gòu)造哈夫曼樹 根據(jù)哈弗曼算法，若已知n個葉結(jié)點，則構(gòu)造的哈弗曼樹有2n-1個結(jié)點。 第一步：先輸入字符集中的n個字符（葉結(jié)點）和表示其概率分布的權(quán)值，儲存在ht（HuffNode型）數(shù)組的前n個數(shù)組元素中。然后將2n-1個結(jié)

3、點的雙親和孩子結(jié)點均置為0。 第二步：在所有的結(jié)點中，選取雙親為零且具有最小權(quán)值m1和次小權(quán)值m2的兩個結(jié)點，用p1和p2指示這兩個結(jié)點在數(shù)組中的位置。將根為htp1和htp2的兩棵樹合并，使其成為新結(jié)點hti的左右孩子，hti的權(quán)值為最小權(quán)值m1和次小權(quán)值m2之和；htp1和htp2的雙親指向i。共進(jìn)行n-1次合并，產(chǎn)生n-1個結(jié)點，依次放入ht數(shù)組中數(shù)組下標(biāo)從n+1到2n-1。這樣就構(gòu)成了一棵哈夫曼樹。(2) 編碼 基本思想是：從哈弗曼樹的葉結(jié)點hti (1in)出發(fā)，通過雙親parent找到其雙親htf，通過htf的域left和right，可知hti是htf的左分支還是右分支，若是左分支

4、，生成的代碼0；若是右分支，生成代碼1。代碼存放在數(shù)組cd的下標(biāo)start中，然后把htf作為出發(fā)點，重復(fù)上述過程，直到找到根為止。顯然這樣生成的代碼序列與要求的編碼次序相反，為了得到正確的代碼，把最先生成的代碼存放在數(shù)組的第n個（雖然各個字符的編碼長度不一，但都不會超過n個）位置處，再次生成的代碼存放在數(shù)組的第n-1個位置處，以此類推。用變量start來指示編碼在數(shù)組cd中的起始位置，start的初始值為n，生成一個代碼后，start的值就減1。(3) 譯碼 基本思想是：首先輸入二進(jìn)制代碼串，存放在數(shù)組ch中，以#為結(jié)束標(biāo)志；接下來，將代碼與編碼表比較，如果為0，轉(zhuǎn)向左子樹，如果為1，轉(zhuǎn)向右

5、子樹，直到葉結(jié)點結(jié)束，此時輸出葉結(jié)點的數(shù)據(jù)域，即所對應(yīng)的字符；繼續(xù)譯碼，直到代碼串結(jié)束。5. 源代碼#include#include#include#define MAXSIZE 50typedef char DataType;typedef struct /哈夫曼樹結(jié)點的結(jié)構(gòu)DataType data; /數(shù)據(jù)用字符表示int weight; /權(quán)值int parent; /雙親int lchild,rchild; /左右孩子 HuffNode;typedef struct /哈夫曼編碼的存儲結(jié)構(gòu)DataType cdMAXSIZE; /存放編碼位串int start; /編碼的起始位置 H

6、uffCode;void HuffmanCreate(HuffNode *ht,int n)int i,j,p1,p2,m1,m2;for(i=1;i=n;i+)getchar(); /接收回車printf(第%d個字符及其權(quán)重分別為（用空格分隔）：n,i);scanf(%c %d,&hti.data,&hti.weight);for(i=1;i=2*n-1;i+) /對數(shù)組初始化hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i=2*n-1;i+)m1=m2=32767; /令m1、m2為整數(shù)最大值p1=p2=1;for(j=1;ji;j+) /找出

7、parent為0且權(quán)值最小的兩個結(jié)點if(htj.parent=0)if(htj.weightm1)m2=m1;p2=p1;m1=htj.weight;p1=j;else if(htj.weightm2)m2=htj.weight;p2=j;hti.lchild=p1; /p1為新結(jié)點的左孩子hti.rchild=p2; /p2為新結(jié)點的右孩子hti.weight=m1+m2; /新結(jié)點的權(quán)值為最小權(quán)值和次小權(quán)值的和htp1.parent=i;htp2.parent=i;printf(哈夫曼樹已成功建立！n);void Encoding(HuffNode *ht,HuffCode *hcd,i

8、nt n)HuffCode d;int i,j,f;for(i=1;i=n;i+) /對所有結(jié)點循環(huán)d.start=n+1; /起始位置f=hti.parent; /雙親的位置for(j=i;f!=0;j=f,f=htj.parent)if(htf.lchild=j)d.cd-d.start=0; /規(guī)定左樹代碼為0elsed.cd-d.start=1; /規(guī)定右樹代碼為1hcdi=d;printf(輸出哈夫曼編碼：n);for(i=1;i=n;i+)printf(%c ,hti.data); /先輸出結(jié)點for(j=hcdi.start;j=n;j+) /在輸出其對應(yīng)編碼printf(%c,

9、hcdi.cdj);printf(n);void Decoding(HuffNode *ht,int n)DataType c,ch200; /c接收輸入電文，ch儲存int i,temp,f;printf(請輸入電文，以“#”為結(jié)束標(biāo)志：n);c=getchar();i=0;while(c!=#)i+; /ch數(shù)組下標(biāo)后移chi=c; /將單個字符依次存入ch字符串中c=getchar();temp=i; /標(biāo)記數(shù)組存儲末位位置i=1;printf(輸出哈弗曼譯碼：n);while(i=temp)f=2*n-1; /每次都從根節(jié)點開始查找while(htf.lchild!=0)if(chi=0)f=htf.lchild;if(chi=1)f=htf.rchild;i+;printf(%c,htf.data);printf(n);void main()int n,select;HuffNode htMAXSIZE*2; /定義存放哈夫曼樹的數(shù)組HuffCode hcdMAXSIZE; /定義存放編碼的數(shù)組while(1)printf(1-建立哈夫曼樹n);printf(2-編碼n);printf(3-譯碼n);printf(4-退出系統(tǒng)n);printf(請輸入您所要實現(xiàn)的功能：);scanf(%d,&select);