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

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

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

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

5、子樹，直到葉結點結束，此時輸出葉結點的數據域，即所對應的字符；繼續譯碼，直到代碼串結束。5. 源代碼#include#include#include#define MAXSIZE 50typedef char DataType;typedef struct /哈夫曼樹結點的結構DataType data; /數據用字符表示int weight; /權值int parent; /雙親int lchild,rchild; /左右孩子 HuffNode;typedef struct /哈夫曼編碼的存儲結構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個字符及其權重分別為（用空格分隔）：n,i);scanf(%c %d,&hti.data,&hti.weight);for(i=1;i=2*n-1;i+) /對數組初始化hti.parent=hti.lchild=hti.rchild=0;for(i=n+1;i=2*n-1;i+)m1=m2=32767; /令m1、m2為整數最大值p1=p2=1;for(j=1;ji;j+) /找出

7、parent為0且權值最小的兩個結點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為新結點的左孩子hti.rchild=p2; /p2為新結點的右孩子hti.weight=m1+m2; /新結點的權值為最小權值和次小權值的和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+) /對所有結點循環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; /規定左樹代碼為0elsed.cd-d.start=1; /規定右樹代碼為1hcdi=d;printf(輸出哈夫曼編碼：n);for(i=1;i=n;i+)printf(%c ,hti.data); /先輸出結點for(j=hcdi.start;j=n;j+) /在輸出其對應編碼printf(%c,

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