哈夫曼編碼譯碼器數(shù)據(jù)結(jié)構(gòu)C語言(共9頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上一、需求分析目前，進(jìn)行快速遠(yuǎn)距離通信的主要手段是電報，即將需傳送的文字轉(zhuǎn)化成由二級制的字符組成的字符串。例如，假設(shè)需傳送的電文為“ABACCDA”，它只有4種字符，只需兩個字符的串，便可以分辨。假設(shè)A、B、C、D、的編碼分別為00,01,10和11，則上述7個字符的電文便為“100”，總長14位，對方接受時，可按二位一分進(jìn)行譯碼。當(dāng)然，在傳送電文時，希望總長盡可能地短。如果對每個字符設(shè)計長度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能短的編碼，則傳送電文的總長便可減少。如果設(shè)計A、B、C、D的編碼分別為0,00,1,01，則上述7個字符的電文可轉(zhuǎn)換成總長為9的字

2、符串“”。但是，這樣的電文無法翻譯，例如傳送過去的字符串中前4個字符的字串“0000”就可以有很多種譯法，或是“AAAA”或者“BB”，或者“ABA”等。因此，若要設(shè)計長短不等的編碼，則必須是任一字符的編碼都不是另一個字符的編碼的前綴，這種編碼稱作前綴編碼。然而，如何進(jìn)行前綴編碼就是利用哈夫曼樹來做，也就有了現(xiàn)在的哈夫曼編碼和譯碼。二、概要設(shè)計利用哈夫曼樹編/譯碼（一）、建立哈夫曼樹（二）、對哈夫曼樹進(jìn)行編碼（三）、輸出對應(yīng)字符的編碼（四）、譯碼過程主要代碼實現(xiàn)：struct code/結(jié)構(gòu)體的定義char a;int w;int parent;int lchild;int rchild;vo

3、id creation(code *p,int n,int m);/建立哈夫曼樹void coding(code *p,int n);/編碼void display(code *p,int n,int m);/輸出函數(shù)void translate(char *hc,code *p,int n);/譯碼三、 詳細(xì)設(shè)計10序號：7653124（1） 、建立哈夫曼樹ab*c*d*字符：*c646dbaab*c*10634321權(quán)值：33333ab*122112圖3-2圖3-3圖3-1從葉子到根逆向求編碼（2） 、對哈夫曼樹進(jìn)行編碼主要代碼實現(xiàn)：for(c=i,f=pi.parent;f!=0;c=f

4、,f=pf.parent)1ab*c*d*if(pf.lchild=c)/左孩子編碼為010cd-start=0;01else/右孩子編碼為1圖3-4cd-start=1;（3） 、輸出對應(yīng)字符的碼字符編碼a110b111c10d表3-10（4） 、譯碼過程主要代碼實現(xiàn)：if(strcmp(a,hci)=0)/比較兩個字符串是否相等，相等則輸出0for(c=2*n-1,j=0;aj!=0;j+)/從根出發(fā)，按字符0或1確定找左孩子或右孩子從跟到葉子順向求字符if(aj=0)/左孩子ab*c*d*10c=pc.lchild;10else10c=pc.rchild;/右孩子圖3-5四、 調(diào)試分析（

5、一）、數(shù)字的輸入判斷圖4-1（二）、字母的輸入判斷圖4-2（三）、程序是否繼續(xù)進(jìn)行的判斷圖4-3五、 用戶手冊（1） 、首先根據(jù)提示輸入初始化數(shù)據(jù)，提示輸入一個數(shù)字，請輸入一個數(shù)a，0a9999；提示輸入一個字母，則請輸入一個字母（az)或者(AZ)中的一個字符；請勿在輸入一個數(shù)字后再輸入一個字符，或者在輸入一個字符后再輸入一個數(shù)字。（2） 在某一界面結(jié)束后，會有“請按回車?yán)^續(xù)下面操作”提示，請按提示進(jìn)行操作，如輸入其他數(shù)字則無效，知道輸入回車符界面才會跳轉(zhuǎn)。（3） 對界面的操作可以自行選擇，在詢問是否譯碼的時候，請按要求進(jìn)行選擇，在一次譯碼結(jié)束后會詢問是否繼續(xù)譯碼，如需要則輸入y或者Y，輸入

6、其他字符則退出程序。六、測試結(jié)果圖6-1（一）、初始化（二）、建立哈夫曼樹圖6-2（三）、哈夫曼編碼圖6-3（四）、哈夫曼譯碼圖6-4（五）、錯誤判定圖6-5附錄：源代碼：#include#include#include#includestruct code/結(jié)構(gòu)體的定義char a;int w;int parent;int lchild;int rchild;void creation(code *p,int n,int m);/建立哈夫曼樹void coding(code *p,int n);/編碼void translate(char *hc,code *p,int n);/譯碼void

7、 display(code *p,int n,int m);/輸出函數(shù)/主函數(shù)void main()int i,n,m;code *ht;printf(字符的數(shù)量:n(請輸入一個大于0的數(shù)字,輸入多個數(shù)字則按第一個數(shù)字運行)n);while(scanf(%d,&n)!=1|n9999)printf(重新輸入：n);fflush(stdin);m=2*n-1;/哈夫曼樹中沒有度為1的結(jié)點，故含有m=2n-1個結(jié)點ht=(code*)malloc(m+1)*sizeof(code);/動態(tài)申請內(nèi)存for(i=1;ia|hti.aA|hti.aZ)printf(重新輸入：n);fflush(stdi

8、n);scanf(%c,&hti.a);/清空輸入緩沖區(qū)，往往是確保不影響后面數(shù)據(jù)的讀取printf(輸入字符的權(quán)值(請輸入一個數(shù)字):n);while(scanf(%d,&hti.w)!=1|hti.w9999)printf(重新輸入：n);fflush(stdin);/清空輸入緩沖區(qū)，往往是確保不影響后面數(shù)據(jù)的讀取hti.lchild=0;hti.rchild=0;hti.parent=0;for(i=n+1;i=m;i+)/對n+12n-1的數(shù)進(jìn)行初始化hti.a=*;hti.w=0;hti.lchild=0;hti.rchild=0;hti.parent=0;creation(ht,n

9、,m);printf(請按回車進(jìn)入哈夫曼樹對應(yīng)界面n);getchar();getchar();system(cls);display(ht,n,m);printf(請按回車進(jìn)入編碼對應(yīng)界面n);getchar();system(cls);coding(ht,n);getchar();void creation(code *ht,int n,int m)int i,j,m1,m2,t1,t2;for(i=n+1;i=m;i+)j=1;/找到第一個最小值（雙親不為0）while(htj.parent!=0)/找到表中第一個沒有雙親的結(jié)點j+;t1=htj.w;m1=j;for(j=m1+1;j=

10、m;j+)if(htj.parent=0&htj.w!=0)/條件(htj.w!=0)是因為n2n-1的權(quán)值初始值為0if(htj.wt1)t1=htj.w;m1=j;htm1.parent=i;/第一個值的雙親為htihti.lchild=m1;/hi的的左孩子是最小值的序號j=1;/剩余中找到第二個最小值（雙親不為0）while(htj.parent!=0)j+;t2=htj.w;m2=j;for(j=m2+1;j=m;j+)if(htj.parent=0&htj.w!=0)if(htj.wt2)t2=htj.w;m2=j;htm2.parent=i;/第二個值的雙親為htihti.rch

11、ild=m2;/hi的的左孩子是最小值的序號hti.w=t1+t2;/hi的權(quán)值是找到的兩個值的權(quán)值之和void coding(code *p,int n)int i,c,f;char *hc;/指針的指針char *cd;char ch;int start;hc=(char*)malloc(n+1)*sizeof(char *);/分配n個字符編碼的頭指針向量cd=(char*)malloc(n*sizeof(char);/分配求編碼的工作空間cdn-1=0;/編碼結(jié)束符for(i=1;i=n;i+)start=n-1;for(c=i,f=pi.parent;f!=0;c=f,f=pf.pa

12、rent)/從葉子到根逆向求編碼if(pf.lchild=c)/左孩子編碼為0cd-start=0;else/右孩子編碼為1cd-start=1;hci=(char*)malloc(n-start)*sizeof(char);/為第i個字符編碼分配空間strcpy(hci,&cdstart);/從cd復(fù)制編碼（串）到hc,&是取地址符，即取首地址，從start位置到0的編碼為止。free(cd);/釋放工作空間printf(n輸出編碼后的結(jié)果：n);printf(符號數(shù)碼n);for(i=1;i=n;i+)printf(n%c%sn,pi.a,hci);printf(是否進(jìn)行譯碼操作，是則譯碼

13、，否則退出程序！n是（輸入y/Y）否（輸入其他字符）n);scanf(%d,&ch);if(ch=y|ch=Y)translate(hc,p,n);elseexit(0);void translate(char *hc,code *p,int n)char a10,ch;int i,j,c;doprintf(nnn請輸入編碼：n);scanf(%s,a);/回車之后會自動生成0for(i=1;in)printf(編碼不存在對應(yīng)的字符！n);printf(是否繼續(xù)輸入?是（輸入y或者Y）否(其他）n);fflush(stdin);scanf(%c,&ch);while(ch=y|ch=Y);void display(code *p,int n,int m)int i;printf(n序號碼值權(quán)值雙親左孩子右孩子n);for(i=1;i=m;i+)printf(%d%c%d%d%d%dn,i,pi.a,pi.w,pi.parent,pi.lchild,pi.rchild);設(shè)計體會通過這個課程設(shè)計，讓我對數(shù)據(jù)結(jié)構(gòu)這門課程有了更深一步的了解，對以后的深造奠定了基礎(chǔ)。本次課程設(shè)計的課題是：哈夫曼編碼