哈弗曼编码程序说明书.doc

哈弗码编码程序说明书 姓名： 班级： 学号： 16目 录一、问题定义1二、可行性分析2三、概要设计3四、详细设计及源码4五、测试结果15六、使用手册16一、问题定义目前，进行快速远距离通信的主要手段之一是电报，即将需传送的文字转换为由二进制的字符组成的字符串。例如，假设需传送的电文为ABCCDA，它只有4种字符，只需两个字符的串便可分辨。假设A、B、C、D的编码分别00、01、10和11，则上述7个字符的电文便为00010010101100，总长为14位，对方接收时，可按二位一分进行译码。在传送电文时希望总长尽可能的短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。若要设计长短不等的编码，则必须是任一个字符的编码都不是另一个字符的编码的前缀，这种编码称为前缀编码。假设有n个权值w1，w2，wn，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度最小的二叉树称作最优二叉树或哈夫曼树。设计电文总长最短的二进制前缀编码即为以n中字符出现的频率作权，设计一棵哈夫曼树的问题，由此得到二进制前缀编码便称为哈夫曼编码。哈夫曼编码是广泛应用数据文件压缩的十分有效的编码方法。其压缩率通常在20%90%之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表达方式。关键字： 哈弗曼编码 字符 权值 二叉树二、可行性分析 哈夫曼算法如下： 1构造哈弗曼树结点结构如下：typedef struct unsigned 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中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为两个小权值结点的权值之和，两个小权值结点则为新节点的左右孩子。5在F中删除这两棵树，同时将新得到的二叉树加入F中。6重复4和5，直到F中只含一棵树为止。这棵树便是哈夫曼树。应用贪心算法原理可知，通过此方法得到哈夫曼编码能够使电文总长最短。三、概要设计哈弗曼编码有两种方式，第一种是已知字符及其相应权值，然后对字符编码，第二种方式是对输入的字符串进行处理，得出其中具有的的字符，并求出相应权值，然后再谁字符串编码。程序主框架如下：输入字符串统计不同字符和各个字符出现次数（作为权值）编码译码调用子过程求哈夫曼编码输出权值和编码 主窗体调用子过程求哈夫曼编码输入字符及相应权值，确定编码编码译码窗体一窗体二四、详细设计及源码1利用VC+6.0的AppWizard建立一个MFC工程，新工程名称为“”HuffmanCode，在Step1中选择“Dialog based”选项，其他按照默认设置。选择“Finish”。AppWizard将会自动建立一个作为应用程序主窗口的对话框模板IDD_HUFFMANCODE_DIALOG，及其对应的对话框类CHufffmanCodeDlg。2利用Insert Resource对话框为应用程序添加位图和图标。选择Insert-Resource，打开Insert Resource对话框，在Resource Type中选择“Bitmap”选项，单击Import按钮，打开Import Resource对话框，浏览并选择要添加的bmp文件，单击Import按钮。依次将需要用到的位图和图标添加进去。3设计IDD_HUFFMANCODE_DIALOG对话框模板，删除该模板上除Cancel按钮外的所有控件并根据要求和如下表的内容，向对话框模板中加入控件。控件类型ID标题其他属性静态图片IDC_STATICType列表框选择Bitmap静态图片IDC_STATICType列表框选择Bitmap选中命令按钮IDC_VALUE字符权值输入编码/译码选中Default button命令按钮IDC_TEXT文本输入编码/译码选中Default button命令按钮IDCANCEL退出选中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（默认名）IDC_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) 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.weight=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=HTj.weight ) min1 = HTj.weight; s1 = j; for(j=1;j=HTj.weight) 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=c) cd-start=0; else cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(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 CTestCodeDlg:OnOk() UpdateData();CString strData;int n=count;HuffmanCoding1(HT,HC,w,n); for(int i=1;i”命令按钮函数：void CTestCodeDlg:OnMakecode1() UpdateData();int nIndex=m_listBox2.GetCount();if(!nIndex)MessageBox(码值未定！请输入字符及其权值并确定码值！);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;icountC;i+)for(j=1;j=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.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;i0)MessageBox(有未知编码，请检查输入电文！);m_strContent1.Format(%s,strOutput);UpdateData(false);成员变量如下表：控件ID变量类型变量名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;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.weight=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=HTj.weight ) min1 = HTj.weight; s1 = j; for(j=1;j=HTj.weight) 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”命令按钮函数：void CTestContentDlg:OnMakecode2() UpdateData();m_strContent2.TrimLeft(); if (m_strContent2.IsEmpty() MessageBox(原文为空，请输入原文！);return; int count=strlen(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;i27;i+) w2i=0; for(i=1;icount;i+)for(int k=0;ki;k+)if(int)stri=(int)code2k) w2k+=1;break;if(k=i)code2j=stri;w2i+=1;j+;s+;CString strContent;strContent.Format(输入的文字中共有字符%d个，对应权值为：,s);m_listBox.AddString(strContent);for (i=0;is;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;is;i+)strContent.Format(%c:%s,code2i,HC2i+1);m_listBox.AddString(strContent); char strOutput500=;for(i=0;icount;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() UpdateData();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=; for (int i=0;i0)M