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

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

2、，這樣的電文無(wú)法翻譯，例如傳送過(guò)去的字符串中前4個(gè)字符的字串“0000”就可以有很多種譯法，或是“AAAA”或者“BB”，或者“ABA”等。因此，若要設(shè)計(jì)長(zhǎng)短不等的編碼，則必須是任一字符的編碼都不是另一個(gè)字符的編碼的前綴，這種編碼稱(chēng)作前綴編碼。然而，如何進(jìn)行前綴編碼就是利用哈夫曼樹(shù)來(lái)做，也就有了現(xiàn)在的哈夫曼編碼和譯碼。二、概要設(shè)計(jì)利用哈夫曼樹(shù)編/譯碼（一）、建立哈夫曼樹(shù)（二）、對(duì)哈夫曼樹(shù)進(jìn)行編碼（三）、輸出對(duì)應(yīng)字符的編碼（四）、譯碼過(guò)程主要代碼實(shí)現(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);/建立哈夫曼樹(shù)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è)計(jì)10序號(hào)：7653124（1） 、建立哈夫曼樹(shù)ab*c*d*字符：*c646dbaab*c*10634321權(quán)值：33333ab*122112圖3-2圖3-3圖3-1從葉子到根逆向求編碼（2） 、對(duì)哈夫曼樹(shù)進(jìn)行編碼主要代碼實(shí)現(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） 、輸出對(duì)應(yīng)字符的碼字符編碼a110b111c10d表3-10（4） 、譯碼過(guò)程主要代碼實(shí)現(xiàn)：if(strcmp(a,hci)=0)/比較兩個(gè)字符串是否相等，相等則輸出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五、 用戶(hù)手冊(cè)（1） 、首先根據(jù)提示輸入初始化數(shù)據(jù)，提示輸入一個(gè)數(shù)字，請(qǐng)輸入一個(gè)數(shù)a，0<a<9999；提示輸入一個(gè)字母，則請(qǐng)輸入一個(gè)字母（az)或者(AZ)中的一個(gè)字符；請(qǐng)勿在輸入一個(gè)數(shù)字后再輸入一個(gè)字符，或者在輸入一個(gè)字符后再輸入一個(gè)數(shù)字。（2） 在某一界面結(jié)束后，會(huì)有“請(qǐng)按回車(chē)?yán)^續(xù)下面操作”提示，請(qǐng)按提示進(jìn)行操作，如輸入其他數(shù)字則無(wú)效，知道輸入

6、回車(chē)符界面才會(huì)跳轉(zhuǎn)。（3） 對(duì)界面的操作可以自行選擇，在詢(xún)問(wèn)是否譯碼的時(shí)候，請(qǐng)按要求進(jìn)行選擇，在一次譯碼結(jié)束后會(huì)詢(xún)問(wèn)是否繼續(xù)譯碼，如需要?jiǎng)t輸入y或者Y，輸入其他字符則退出程序。六、測(cè)試結(jié)果圖6-1（一）、初始化（二）、建立哈夫曼樹(shù)圖6-2（三）、哈夫曼編碼圖6-3（四）、哈夫曼譯碼圖6-4（五）、錯(cuò)誤判定圖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);/建立哈夫曼樹(shù)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(請(qǐng)輸入一個(gè)大于0的數(shù)字,輸入多個(gè)數(shù)字則按第一個(gè)數(shù)字運(yùn)行)n");while(scanf("%d",&

8、n)!=1|n<0|n>9999)printf("重新輸入：n");fflush(stdin);m=2*n-1;/哈夫曼樹(shù)中沒(méi)有度為1的結(jié)點(diǎn)，故含有m=2n-1個(gè)結(jié)點(diǎn)ht=(code*)malloc(m+1)*sizeof(code);/動(dòng)態(tài)申請(qǐng)內(nèi)存for(i=1;i<=n;i+)/對(duì)1n的數(shù)進(jìn)行初始化printf("輸入編碼中的字符(請(qǐng)輸入一個(gè)字母):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)值(請(qǐng)輸入一個(gè)數(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+)/對(duì)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("請(qǐng)按回車(chē)進(jìn)入哈夫曼樹(shù)對(duì)應(yīng)界面n");getchar();getchar();system("cls");display(ht,n,m);printf("請(qǐng)按回車(chē)進(jìn)入編碼對(duì)應(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;/找到第一個(gè)最小值（雙親不為0）while(htj.parent!=0)/找到表中第一個(gè)沒(méi)有雙親的結(jié)點(diǎn)j+;t1=htj.w;m1=j;for(j=m1+1;j<=m;j+)if(htj.parent=0&&htj.w!=0)/條件(htj.w!=0)是因?yàn)閚2n-1的權(quán)值初始值為0if(h

12、tj.w<t1)t1=htj.w;m1=j;htm1.parent=i;/第一個(gè)值的雙親為htihti.lchild=m1;/hi的的左孩子是最小值的序號(hào)j=1;/剩余中找到第二個(gè)最小值（雙親不為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;/第二個(gè)值的雙親為htihti.rchild=m2;/hi的的左孩子是最小值的序號(hào)hti.w=t1+t2;/hi的權(quán)值是找

13、到的兩個(gè)值的權(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個(gè)字符編碼的頭指針向量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個(gè)字符編碼分配空間strcpy(hci,&cdstart);/從cd復(fù)制編碼（串）到hc,&是取地址符，即取首地址，從start位置到'0'的編碼為止。free(cd);/釋放工作空間printf("n輸出編碼后的結(jié)果：n");printf("符號(hào)數(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請(qǐng)輸入編碼：n");scanf(

16、"%s",a);/回車(chē)之后會(huì)自動(dòng)生成'0'for(i=1;i<=n;i+)if(strcmp(a,hci)=0)/比較兩個(gè)字符串是否相等，相等則輸出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("編碼不存在對(duì)應(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序號(hào)碼值權(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è)計(jì)體會(huì)通過(guò)這個(gè)課程設(shè)計(jì)，讓我對(duì)數(shù)據(jù)結(jié)構(gòu)這門(mén)課程有了更深一步