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

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

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;void crea

3、tion(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,f=pf.p

4、arent)1ab*c*d*if(pf.lchild=c)/左孩子編碼為'0'10cd-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=

5、9;0')/左孩子ab*c*d*10c=pc.lchild;10else10c=pc.rchild;/右孩子圖3-5四、 調(diào)試分析（一）、數(shù)字的輸入判斷圖4-1（二）、字母的輸入判斷圖4-2（三）、程序是否繼續(xù)進(jìn)行的判斷圖4-3五、 用戶手冊（1） 、首先根據(jù)提示輸入初始化數(shù)據(jù)，提示輸入一個數(shù)字，請輸入一個數(shù)a，0<a<9999；提示輸入一個字母，則請輸入一個字母（az)或者(AZ)中的一個字符；請勿在輸入一個數(shù)字后再輸入一個字符，或者在輸入一個字符后再輸入一個數(shù)字。（2） 在某一界面結(jié)束后，會有“請按回車?yán)^續(xù)下面操作”提示，請按提示進(jìn)行操作，如輸入其他數(shù)字則無效，知道輸入

6、回車符界面才會跳轉(zhuǎn)。（3） 對界面的操作可以自行選擇，在詢問是否譯碼的時候，請按要求進(jìn)行選擇，在一次譯碼結(jié)束后會詢問是否繼續(xù)譯碼，如需要則輸入y或者Y，輸入其他字符則退出程序。六、測試結(jié)果圖6-1（一）、初始化（二）、建立哈夫曼樹圖6-2（三）、哈夫曼編碼圖6-3（四）、哈夫曼譯碼圖6-4（五）、錯誤判定圖6-5附錄：源代碼：#include<stdio.h>#include<string.h>#include<stdlib.h>#include<malloc.h>struct code/結(jié)構(gòu)體的定義char a;int w;int parent

7、;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 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",&

8、n)!=1|n<0|n>9999)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;i<=n;i+)/對1n的數(shù)進(jìn)行初始化printf("輸入編碼中的字符(請輸入一個字母):n");fflush(stdin);scanf("%c",&hti.a);while(!(hti.a>'a'|hti.a<'

9、;z'|hti.a>'A'|hti.a<'Z')printf("重新輸入：n");fflush(stdin);scanf("%c",&hti.a);/清空輸入緩沖區(qū)，往往是確保不影響后面數(shù)據(jù)的讀取printf("輸入字符的權(quán)值(請輸入一個數(shù)字):n");while(scanf("%d",&hti.w)!=1|hti.w<0|hti.w>9999)printf("重新輸入：n");fflush(stdin);/清空輸入

10、緩沖區(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,m);printf("請按回車進(jìn)入哈夫曼樹對應(yīng)界面n");getchar();getchar();system("cls");display(ht,n,m);printf("請按回車進(jìn)入編碼對應(yīng)界面n&q

11、uot;);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<=m;j+)if(htj.parent=0&&htj.w!=0)/條件(htj.w!=0)是因為n2n-1的權(quán)值初始值為0if(h

12、tj.w<t1)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.w<t2)t2=htj.w;m2=j;htm2.parent=i;/第二個值的雙親為htihti.rchild=m2;/hi的的左孩子是最小值的序號hti.w=t1+t2;/hi的權(quán)值是找

13、到的兩個值的權(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.parent)/從葉子到根逆向求編碼if(pf.lchild=

14、c)/左孩子編碼為'0'cd-start='0'else/右孩子編碼為'1'cd-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;

15、i<=n;i+)printf("n%c%sn",pi.a,hci);printf("是否進(jìn)行譯碼操作，是則譯碼，否則退出程序！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(

16、"%s",a);/回車之后會自動生成'0'for(i=1;i<=n;i+)if(strcmp(a,hci)=0)/比較兩個字符串是否相等，相等則輸出0for(c=2*n-1,j=0;aj!='0'j+)/從根出發(fā)，按字符'0'或'1'確定找左孩子或右孩子if(aj='0')/左孩子c=pc.lchild;elsec=pc.rchild;/右孩子printf("字符是：n");printf("%cn",pc.a);break;if(i>n)pri

17、ntf("編碼不存在對應(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)這門課程有了更深一步