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

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

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

3、oidcreation(code*p,intn,intm);建立哈夫曼樹voidcoding(code*p,intn);/編碼voiddisplay(code*p,intn,intm);/輸出函數(shù)voidtranslate(char*hc,code*p,intn);譯碼三、詳細設(shè)計(一)、建立哈夫曼樹序號：1234567字符:，ab-d二，二權(quán)值：12343610(二)、對哈夫曼樹進行編碼主要代碼實現(xiàn)：for(c=i,f=pi.parent;f!=0;c=f,f=pf.parent)if(pf.lchild=c)左孩子編碼為0cd-start=0;else右孩子編碼為1cd-start=1;從

4、葉子到根逆向求編碼(三)、輸出對應(yīng)字符的碼11字符編碼a110b111c10d0表3-1比較兩個字符串是否相等，相等則輸出0/從根出發(fā)，按字符0或1確定找左孩子或右孩子從跟到葉子順向求字符(四)、譯碼過程主要代碼實現(xiàn)：if(strcmp(a,hci)=0)for(c=2*n-1,j=0;aj!=0;j+)if(aj=0)左孩子c=pc.lchild;elsec=pc.rchild;右孩子四、調(diào)試分析（一）、數(shù)字的輸入判斷圖4-1（二）、字母的輸入判斷圖4-23.strat。r桌面huffdbukhu褊大于目的藪字.輸入多個數(shù)字則按第一個數(shù)字運行）品褊*111111111和輸入;蛋新輸入；q輸入

5、編碼中的字符請輸入一個字母工I選定*CzDnfremr-ntxandSettinarXAdaimxtrntarKhirffBainYDfthnhuff-停貨的數(shù)量;日相入一個大于6晌數(shù)字，輸入多個數(shù)字則按第一個數(shù)字運行右人編眄中的字也謂粕入一個字母11新輸入rH，新輸入；“輸卻卷人字符的杈假請輸入一個數(shù)將=二； 法文 : YDoEiusmt a Jin.rl et 11Adia i nuti r a.t or XllF huf f iMiXDrbugX tiuf f .（三）、程序是否繼續(xù)進行的判斷圖4-3五、用戶手冊然駐舞管1飄鵬著腮出程序!請輸入編網(wǎng);ntr字符是上土者繼續(xù)輸人?是（輸入豉

6、首0否t其他）JiPressanjkeytocontinue（一）、首先根據(jù)提示輸入初始化數(shù)據(jù)，提示輸入一個數(shù)字，請輸入一個數(shù)a,0a9999;提示輸入一個字母，則請車入一個字母（az）或者（AZ）中的一個字符；請勿在輸入一個數(shù)字后再輸入一個字符，或者在輸入一個字符后再輸入一個數(shù)字。（二）在某一界面結(jié)束后，會有“請按回車繼續(xù)下面操作”提示，請按提示進行操作，如輸入其他數(shù)字則無效，知道輸入回車符界面才會跳轉(zhuǎn)。（三）對界面的操作可以自行選擇，在詢問是否譯碼的時候，請按要求進行選擇，在一次譯碼結(jié)束后會詢問是否繼續(xù)譯碼，如需要則輸入y或者Y,輸入其他字符則退出程序。六、測試結(jié)果（一）、初始化法定*C;

7、SDocunentsandSettInffsXAdainistralor3dhuffBanADebucXhiifCb.I子付網(wǎng)數(shù)量：（wfeA一個大于Q的數(shù)字.輸入多個數(shù)字則按第一個數(shù)字運行輸入編附中的字符請輸入一個字母,二輸入字符的根值請輸入一個數(shù)字“1輸入編碼中的字符請輸入一個字母jk輸入字符的權(quán)值請輸入一個數(shù)字4入編刊中的字符d請輸入一個字母K曲入字符的板廓請輸入一個數(shù)字八露入編陰中的字符，請輸入一個字母TdL輸入字符的極值請輸入一個數(shù)字力1請按回軍進入編碼時應(yīng)界面圖6-1（二）、建立哈夫曼樹序號 碼值權(quán)值雙親左孩子右孩子1a15002b25&Q3c36ee4d4?R5*36i2& *6

8、7357-1004G請按回車進入編碼對應(yīng)界面圖6-2（三）、哈夫曼編碼困tingsXAdaini.Hra.torXJXhuffBanXDBbuEhuf-fM.-.-IE箕一i出翼胡后的結(jié)果:哥號數(shù)碼nat.111圖6-3國C；:Dociucntsand.SettingsAdB.iiiisHtrat請輸入編碼,（四）、哈夫曼譯碼請輸入編徜：LLQ圖6-4字符是：營者繼續(xù)輸.人?是（輸入屈著0否其他）（五）、錯誤判定常輸入編弱ry或胡）否（其他）圖6-5mi編碼不存在對應(yīng)的是否繼續(xù)輸入?是附錄：源代碼：#include#include#include#includestructcode結(jié)構(gòu)體的定義

9、chara;intw;intparent;intIchild;intrchild;voidcreation(code*p,intn,intm);建立哈夫曼樹voidcoding(code*p,intn);/編碼voidtranslate(char*hc,code*p,intn);/譯碼voiddisplay(code*p,intn,intm);/輸出函數(shù)/主函數(shù)voidmain()inti,n,m;code*ht;printf(字符的數(shù)量：n(請輸入一個大于0的數(shù)字，輸入多個數(shù)字則按第一個數(shù)字運行)n);while(scanf(%d,&n)!=1|n9999)printf(重新輸入：n);ff

10、lush(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(stdin);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ù)的讀取h

11、ti.lchild=0;hti.rchild=0;hti.parent=0;for(i=n+1;i=m;i+)/對n+12n-1的數(shù)進行初始化hti.a=*;hti.w=0;hti.lchild=0;hti.rchild=0;hti.parent=0;creation(ht,n,m);printf(請按回車進入哈夫曼樹對應(yīng)界面n);getchar();getchar();system(cls);display(ht,n,m);printf(請按回車進入編碼對應(yīng)界面n);getchar();system(cls);coding(ht,n);getchar();voidcreation(code*

12、ht,intn,intm)inti,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=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(ht

13、j.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;hti.rchild=m2;hti.w=t1+t2;voidcoding(code*p,intn)inti,c,f;char*hc;第二個值的雙親為hti/hi的的左孩子是最小值的序號/hi的權(quán)值是找到的兩個值的權(quán)值之和指針的指針char*cd;charch;intstart;hc=(char*)malloc(n+1)*sizeof(char*);cd=(char*)mall

14、oc(n*sizeof(char);cdn-1=0;for(i=1;i=n;i+)分配n個字符編碼的頭指針向量分配求編碼的工作空間編碼結(jié)束符否則退出程序!n是（輸入y/Y ）否（輸入其他字符）n）start=n-1;for(c=i,f=pi.parent;f!=0;c=f,f=pf.parent)if(pf.lchild=c)cd-start=0;elsecd-start=1;hci=(char*)malloc(n-start)*sizeof(char);strcpy(hci,&cdstart);首地址，從start位置到0的編碼為止。free(cd);printf(n輸出編碼后的結(jié)果：n);

15、printf(符號數(shù)碼n);for(i=1;i=n;i+)printf(n%c%sn,pi.a,hci);printf(是否進行譯碼操作，是則譯碼，scanf(%d,&ch);if(ch=y|ch=Y)translate(hc,p,n);else從葉子到根逆向求編碼左孩子編碼為0右孩子編碼為1為第i個字符編碼分配空間從cd復(fù)制編碼（串）到hc,&是取地址符，即取釋放工作空間exit(0);voidtranslate(char*hc,code*p,intn)chara10,ch;inti,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);voiddisplay(code*p,intn,intm)inti;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)