哈弗曼编码程序说明书

1、学号:哈弗码编码程序说明书一、问题定义 1二、可行性分析2三、概要设计3四、详细设计及源码4五、测试结果 15六、使用手册16一、问题定义目前，进行快速远距离通信的主要手段之一是电报，即将需传送的文字转换为由二进制的字符组成的字符串。例如，假设需传送的电文为'ABCCDA它只有 4 种字符，只需两个字符的串便可分辨。假设A、 B、 C、 D 的编码分别00、01、 10 和 11，则上述7个字符的电文便为00010010101100 ，总长为14位，对方接收时，可按二位一分进行译码。在传送电文时希望总长尽可能的短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能

2、短的编码，则传送电文的总长便可减少。若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。假设有n个权值w1 , w2,，wn,试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi ，则其中带权路径长度最小的二叉树称作最优二叉树或哈夫曼树。设计电文总长最短的二进制前缀编码即为以n 中字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到二进制前缀编码便称为哈夫曼编码。哈夫曼编码是广泛应用数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用0， 1 串表示各字符的最优表达方式。关键

3、字：哈弗曼编码字符 权值 二叉树二、可行性分析哈夫曼算法如下：1 构造哈弗曼树结点结构如下：typedef structunsigned int weight;unsigned int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode;2 根据输入的字符串（或输入的字符及对应权值）结合相关算法得出各字符（或叶子结点）的权值。3 .根据得到的n个权值w1 , w2 , ,wn构成n棵二叉树的集合F=HT1 , HT2,HTn,其中每棵二叉树Ti中只有一个带权为 wi 的根结点，其左右子树均空。4 在F 中选取两棵

4、根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为两个小权值结点的权值之和，两个小权值结点则为新节点的左右孩子。5 在F 中删除这两棵树，同时将新得到的二叉树加入F 中。6 重复4 和5，直到F 中只含一棵树为止。这棵树便是哈夫曼树。应用贪心算法原理可知，通过此方法得到哈夫曼编码能够使电文总长最短。三、概要设计哈弗曼编码有两种方式，第一种是已知字符及其相应权值，然后对字符编 码，第二种方式是对输入的字符串进行处理，得出其中具有的的字符，并求出 相应权值，然后再谁字符串编码。程序主框架如下：主窗体编码译码窗体二四、详细设计及源码1 .利用VC+6.0的AppWiz

5、ard建立一个 MFC工程，新工程名称为 HuffmanCod0在Stepl中选择“ Dialog based”选项，其他按照默认设置。选 择“Finish "。AppWizard将会自动建立一个作为应用程序主窗口的对话框模板 IDD_HUFFMANCODE_DIA LOG 对应的对话框类 CHufffmanCodeDlg。2 .利用Insert Resource对话框为应用程序添加位图和图标。选择Insert->Resource ,打开 Insert Resource 对话框，在 Resource Type 中选择 “Bitmap”选项，单击Import按钮，打开Import

6、 Resource对话框，浏览并选 择要添加的bmp文件，单击Import按钮。依次将需要用到的位图和图标添加进 去。3.设计IDD_HUFFMANCODE_DIALOGf模板，删除该模板上除Cancel按 钮外的所有控件并根据要求和如下表而容，向对话框模板中加入控件。控件类型ID标题其他属性静态图片IDC_STATICType列表框选择Bitmap静态图片IDC_STATICType列表框选择Bitmap选中命令按钮IDC_VALUE字符权值输入编码/译 码选中 Default button命令按钮IDC_TEXT文本输入编码/译码选中 Default button命令按钮IDCANCEL退

7、出选中 Default button如下图:4.插入新对话框如图所示，并添加相关控件，关联成员变量:成员变量如下表:控件ID变量类型变量名IDC_CHARCStringm_strCharIDC_CVALUEintm_strValueIDC_EDIT_CONTENT1CStringm_strContent1IDC_EDIT_OUTPUT1CStringm_strOutput1IDC_LIST_BOX1CListBoxm_listBox1IDC_LIST_BOX2CListBoxm_listBox2添加消息处理函数:对象ID消息消息处理函数IDC_ADDBN_CLICKEDOnAdd （默认名）I

8、DC_OKBN_CLICKEDOnOk（默认名）IDC_MAKECODE1BN_CLICKEDOnMakecode1 （默认名）IDC_TRANSLATECODE1BN_CLICKEDOnTranslatecode1（默认名）编写消息处理函数: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）/ 编码函数，用于调用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);“添加”命令按钮函数：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;“确定码值”命令按钮函数：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);“编码>>”命令按钮函数：void CTestCodeDlg:OnMakecode1()UpdateData();int nIndex=m_listBox2.GetCount();if(!nIndex)Mes

14、sageBox("码值未定！请输入字符及其权值并确定码值！"); return;m_strContent1.TrimLeft();if (m_strContent1.IsEmpty()MessageBox("原文为空，请输入原文！");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);“ <<译码”命令按钮函数void CTestCodeDlg:OnTranslatecode1()UpdateData();int nIndex=m_listBox2.GetCount();if(!nIndex)MessageBox("码值未定！请输入字符及其权值并确定码值！"); return;m_strOutput1

16、.TrimLeft();if (m_strOutput1.IsEmpty()MessageBox（"电文为空，请输入电文！"）;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("有未知编码，请检查输入电文！");m_strContent1.Format("%s",strOutput);UpdateData(false);DialogX成员变量如下表:控件I

18、D变量类型变量名IDC_EDIT_CONTENT2CStringm_strContent2IDC_EDIT_OUTPUT2CStringm_strOutput2IDC_LIST_BOX3CListBoxm_listBox添加消息处理函数:对象ID消息消息处理函数IDC_MAKECODE2BN_CLICKEDOnMakecode2(默认名)IDC_TRANSLATECODE2BN_CLICKEDOnTranslatecode2(默认 名)编写消息处理函数：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);“编码>>”命令按钮函数：void CTestContentDlg:OnMakecode2()UpdateData();m_strContent2.TrimLeft();if (m_strContent2.IsEmpty()MessageBox("原文为空，请输入原文！")； 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对应权值为：”,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(" 对应编码为：");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);“ <<译码”命令按钮函数：void CTestContentDlg:OnTranslatecode2()UpdateDa

26、ta();m_strOutput2.TrimLeft();if (m_strOutput2.IsEmpty()MessageBox("电文为空，请输入电文！"); 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("有未知编码，请检查输入电文！");m_strContent2.Format("%s",strOutput);UpdateData(false);5 为主窗口添加关联对话框的命令按钮消息处理函数：“字符