哈弗曼編碼程序說明書

1、學(xué)號(hào):哈弗碼編碼程序說明書一、問題定義 1二、可行性分析2三、概要設(shè)計(jì)3四、詳細(xì)設(shè)計(jì)及源碼4五、測(cè)試結(jié)果 15六、使用手冊(cè)16一、問題定義目前，進(jìn)行快速遠(yuǎn)距離通信的主要手段之一是電報(bào)，即將需傳送的文字轉(zhuǎn)換為由二進(jìn)制的字符組成的字符串。例如，假設(shè)需傳送的電文為'ABCCDA它只有 4 種字符，只需兩個(gè)字符的串便可分辨。假設(shè)A、 B、 C、 D 的編碼分別00、01、 10 和 11，則上述7個(gè)字符的電文便為00010010101100 ，總長(zhǎng)為14位，對(duì)方接收時(shí)，可按二位一分進(jìn)行譯碼。在傳送電文時(shí)希望總長(zhǎng)盡可能的短，如果對(duì)每個(gè)字符設(shè)計(jì)長(zhǎng)度不等的編碼，且讓電文中出現(xiàn)次數(shù)較多的字符采用盡可能

2、短的編碼，則傳送電文的總長(zhǎng)便可減少。若要設(shè)計(jì)長(zhǎng)短不等的編碼，則必須是任一個(gè)字符的編碼都不是另一個(gè)字符的編碼的前綴，這種編碼稱為前綴編碼。假設(shè)有n個(gè)權(quán)值w1 , w2,，wn,試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi ，則其中帶權(quán)路徑長(zhǎng)度最小的二叉樹稱作最優(yōu)二叉樹或哈夫曼樹。設(shè)計(jì)電文總長(zhǎng)最短的二進(jìn)制前綴編碼即為以n 中字符出現(xiàn)的頻率作權(quán)，設(shè)計(jì)一棵哈夫曼樹的問題，由此得到二進(jìn)制前綴編碼便稱為哈夫曼編碼。哈夫曼編碼是廣泛應(yīng)用數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼算法使用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用0， 1 串表示各字符的最優(yōu)表達(dá)方式。關(guān)鍵

3、字：哈弗曼編碼字符 權(quán)值 二叉樹二、可行性分析哈夫曼算法如下：1 構(gòu)造哈弗曼樹結(jié)點(diǎn)結(jié)構(gòu)如下：typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode;2 根據(jù)輸入的字符串（或輸入的字符及對(duì)應(yīng)權(quán)值）結(jié)合相關(guān)算法得出各字符（或葉子結(jié)點(diǎn)）的權(quán)值。3 .根據(jù)得到的n個(gè)權(quán)值w1 , w2 , ,wn構(gòu)成n棵二叉樹的集合F=HT1 , HT2,HTn,其中每棵二叉樹Ti中只有一個(gè)帶權(quán)為 wi 的根結(jié)點(diǎn)，其左右子樹均空。4 在F 中選取兩棵

4、根結(jié)點(diǎn)的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為兩個(gè)小權(quán)值結(jié)點(diǎn)的權(quán)值之和，兩個(gè)小權(quán)值結(jié)點(diǎn)則為新節(jié)點(diǎn)的左右孩子。5 在F 中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F 中。6 重復(fù)4 和5，直到F 中只含一棵樹為止。這棵樹便是哈夫曼樹。應(yīng)用貪心算法原理可知，通過此方法得到哈夫曼編碼能夠使電文總長(zhǎng)最短。三、概要設(shè)計(jì)哈弗曼編碼有兩種方式，第一種是已知字符及其相應(yīng)權(quán)值，然后對(duì)字符編 碼，第二種方式是對(duì)輸入的字符串進(jìn)行處理，得出其中具有的的字符，并求出 相應(yīng)權(quán)值，然后再誰字符串編碼。程序主框架如下：主窗體編碼譯碼窗體二四、詳細(xì)設(shè)計(jì)及源碼1 .利用VC+6.0的AppWiz

5、ard建立一個(gè) MFC工程，新工程名稱為 HuffmanCod0在Stepl中選擇“ Dialog based”選項(xiàng)，其他按照默認(rèn)設(shè)置。選 擇“Finish "。AppWizard將會(huì)自動(dòng)建立一個(gè)作為應(yīng)用程序主窗口的對(duì)話框模板 IDD_HUFFMANCODE_DIA LOG 對(duì)應(yīng)的對(duì)話框類 CHufffmanCodeDlg。2 .利用Insert Resource對(duì)話框?yàn)閼?yīng)用程序添加位圖和圖標(biāo)。選擇Insert->Resource ,打開 Insert Resource 對(duì)話框，在 Resource Type 中選擇 “Bitmap”選項(xiàng)，單擊Import按鈕，打開Import

6、 Resource對(duì)話框，瀏覽并選 擇要添加的bmp文件，單擊Import按鈕。依次將需要用到的位圖和圖標(biāo)添加進(jìn) 去。3.設(shè)計(jì)IDD_HUFFMANCODE_DIALOGf模板，刪除該模板上除Cancel按 鈕外的所有控件并根據(jù)要求和如下表而容，向?qū)υ捒蚰０逯屑尤肟丶?。控件類型ID標(biāo)題其他屬性靜態(tài)圖片IDC_STATICType列表框選擇Bitmap靜態(tài)圖片IDC_STATICType列表框選擇Bitmap選中命令按鈕IDC_VALUE字符權(quán)值輸入編碼/譯 碼選中 Default button命令按鈕IDC_TEXT文本輸入編碼/譯碼選中 Default button命令按鈕IDCANCEL退

7、出選中 Default button如下圖:4.插入新對(duì)話框如圖所示，并添加相關(guān)控件，關(guān)聯(lián)成員變量:成員變量如下表:控件ID變量類型變量名IDC_CHARCStringm_strCharIDC_CVALUEintm_strValueIDC_EDIT_CONTENT1CStringm_strContent1IDC_EDIT_OUTPUT1CStringm_strOutput1IDC_LIST_BOX1CListBoxm_listBox1IDC_LIST_BOX2CListBoxm_listBox2添加消息處理函數(shù):對(duì)象ID消息消息處理函數(shù)IDC_ADDBN_CLICKEDOnAdd （默認(rèn)名）I

8、DC_OKBN_CLICKEDOnOk（默認(rèn)名）IDC_MAKECODE1BN_CLICKEDOnMakecode1 （默認(rèn)名）IDC_TRANSLATECODE1BN_CLICKEDOnTranslatecode1（默認(rèn)名）編寫消息處理函數(shù):char *str;char code27;int w27;HuffmanTree HT;HuffmanCode HC;char c27;int count=0;void HuffmanCoding1（HuffmanTree &HT,HuffmanCode &HC,int *w,int n）/ 編碼函數(shù)，用于調(diào)用if(n<=1) r

9、eturn;int m=2*n-1;int i,start,s1,s2;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);int sum=0;for(i=1;i<=n;+i)HTi.weight=wi;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;sum = sum + HTi.weight;for(i=n+1;i<=m;+i)HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i<=m;+i)unsigned int min1 = su

10、m;unsigned int min2 = sum;for(int j = 1;j<=i - 1;+j)if(HTj.parent =0 && min1>=HTj.weight )min1 = HTj.weight;51 = j;for(j=1;j<=i-1;j+ )if (j!=s1 && HTj.parent=0 && min2>=HTj.weight)min2 = HTj.weight;52 = j;HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi

11、.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);char *cd;cd=new charn;cdn-1='0'for(i=1;i<=n;+i)start=n-1;for(unsignedintc=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c) cd-start='0'else cd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);st

12、rcpy(HCi,&cdstart);delete(cd);“添加”命令按鈕函數(shù)：void CTestCodeDlg:OnAdd()count+;UpdateData();m_strChar.TrimLeft();CString strData;strData.Format("%s:%d",m_strChar,m_strValue);m_listBox1.AddString(strData);wcount=m_strValue;strcpy(c,m_strChar.Mid(0,1);codecount=c0;“確定碼值”命令按鈕函數(shù)：void CTestCodeDl

13、g:OnOk()UpdateData();CString strData;int n=count;HuffmanCoding1(HT,HC,w,n);for(int i=1;i<=n;i+)strData.Format("%c:%s",codei,HCi);m_listBox2.AddString(strData);UpdateData(false);“編碼>>”命令按鈕函數(shù)：void CTestCodeDlg:OnMakecode1()UpdateData();int nIndex=m_listBox2.GetCount();if(!nIndex)Mes

14、sageBox("碼值未定！請(qǐng)輸入字符及其權(quán)值并確定碼值！"); return;m_strContent1.TrimLeft();if (m_strContent1.IsEmpty()MessageBox("原文為空，請(qǐng)輸入原文！");return;int countC=strlen(m_strContent1);str=new charcountC+1;str+;strcpy(str,m_strContent1);int i,j;char strOutput500=""for(i=0;i<countC;i+)for(j=1;j

15、<=count;j+)if(int)stri=(int)codej)strcat(strOutput,HCj);m_strOutput1.Format("%s",strOutput);UpdateData(false);“ <<譯碼”命令按鈕函數(shù)void CTestCodeDlg:OnTranslatecode1()UpdateData();int nIndex=m_listBox2.GetCount();if(!nIndex)MessageBox("碼值未定！請(qǐng)輸入字符及其權(quán)值并確定碼值！"); return;m_strOutput1

16、.TrimLeft();if (m_strOutput1.IsEmpty()MessageBox（"電文為空，請(qǐng)輸入電文！"）;return;int countC=strlen(m_strOutput1);str=new charcountC+1;strcpy(str,m_strOutput1);int sum=0,j=0,index=2*count-1;char strOutput500=""for (int i=0;i<countC;+i)if(stri='0'&&HTindex.lchild!=0)index=

17、HTindex.lchild;if (stri='1'&&HTindex.rchild!=0)index=HTindex.rchild;if (HTindex.lchild=0)strOutputj=codeindex;j+;index=2*count-1;sum=0;else sum=sum+1;if(sum>0)MessageBox("有未知編碼，請(qǐng)檢查輸入電文！");m_strContent1.Format("%s",strOutput);UpdateData(false);DialogX成員變量如下表:控件I

18、D變量類型變量名IDC_EDIT_CONTENT2CStringm_strContent2IDC_EDIT_OUTPUT2CStringm_strOutput2IDC_LIST_BOX3CListBoxm_listBox添加消息處理函數(shù):對(duì)象ID消息消息處理函數(shù)IDC_MAKECODE2BN_CLICKEDOnMakecode2(默認(rèn)名)IDC_TRANSLATECODE2BN_CLICKEDOnTranslatecode2(默認(rèn) 名)編寫消息處理函數(shù)：int s;HuffmanTree HT2;HuffmanCode HC2;char code227;int w227;char *str1

19、;void HuffmanCoding2(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)if(n<=1) return;int m=2*n-1;int i,start,s1,s2;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);int sum=0;for(i=1;i<=n;+i)HTi.weight=wi;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;sum = sum + HTi.weight;for(i=n+1;i<=m;+i)HTi.weig

20、ht=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for(i=n+1;i<=m;+i)unsigned int min1 = sum;unsigned int min2 = sum;for(int j = 1;j<=i - 1;+j)if(HTj.parent =0 && min1>=HTj.weight ) min1 = HTj.weight;s1 = j;for(j=1;j<=i-1;j+ )if (j!=s1 && HTj.parent=0 && min2>=HTj.wei

21、ght) min2 = HTj.weight;s2 = j;HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);char *cd;cd=new charn;cdn-1='0'for(i=1;i<=n;+i)start=n-1;for(unsigned int c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild

22、=c) cd-start='0'else cd-start='1'HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);delete(cd);“編碼>>”命令按鈕函數(shù)：void CTestContentDlg:OnMakecode2()UpdateData();m_strContent2.TrimLeft();if (m_strContent2.IsEmpty()MessageBox("原文為空，請(qǐng)輸入原文！")； return;int count=str

23、len(m_strContent2);char *str;str=new charcount+1;strcpy(str,m_strContent2);int i,j=1;code20=str0;w20=1;s=1;for(i=1;i<27;i+) w2i=0;for(i=1;i<count;i+)for(int k=0;k<i;k+)if(int)stri=(int)code2k)w2k+=1;break;if(k=i)code2j=stri;w2i+=1;j+;s+;CString strContent;strContent.Format("輸入的文字中共有字符c

24、K對(duì)應(yīng)權(quán)值為：”,s);m_listBox.AddString(strContent);for (i=0;i<s;i+)strContent.Format("%c:%d",code2i,w2i);m_listBox.AddString(strContent);HuffmanCoding2(HT2,HC2,w2,s);strContent.Format(" 對(duì)應(yīng)編碼為：");m_listBox.AddString(strContent);for (i=0;i<s;i+)strContent.Format("%c:%s",co

25、de2i,HC2i+1);m_listBox.AddString(strContent);char strOutput500=""for(i=0;i<count;i+)for(j=1;j<=count;j+)if(int)stri=(int)code2j-1)strcat(strOutput,HC2j);m_strOutput2.Format("%s",strOutput);UpdateData(false);“ <<譯碼”命令按鈕函數(shù)：void CTestContentDlg:OnTranslatecode2()UpdateDa

26、ta();m_strOutput2.TrimLeft();if (m_strOutput2.IsEmpty()MessageBox("電文為空，請(qǐng)輸入電文！"); return;if(m_listBox.GetCount()=0)MessageBox("尚未確定碼值！");return;int countC=strlen(m_strOutput2);str1=new charcountC+1;strcpy(str1,m_strOutput2);int sum=0,j=0,index=2*s-1;char strOutput500=""

27、for (int i=0;i<countC;+i)if(str1i='0'&&HT2index.lchild!=0)index=HT2index.lchild;if (str1i='1'&&HT2index.rchild!=0)index=HT2index.rchild;if (HT2index.lchild=0)strOutputj=code2index-1;j+;index=2*s-1;sum=0;else sum=sum+1;if(sum>0)MessageBox("有未知編碼，請(qǐng)檢查輸入電文！");m_strContent2.Format("%s",strOutput);UpdateData(false);5 為主窗口添加關(guān)聯(lián)對(duì)話框的命令按鈕消息處理函數(shù)：“字符