哈夫曼树课程设计.doc

数据结构课程设计 -哈夫曼树编码 哈夫曼树编码一、实现功能 给出一串字符，根据每个字符出现的频数进行编码，将文字转化为二进制的字符组成的字符串，即加密。加密过程根据频数生成哈夫曼树，然后进行遍历，得到二进制编码。二、 哈夫曼算法叙述（1）.根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn，其中每棵二叉树Ti中只有一个带权值为Wi的根结点，其左右子树均为空。（2）.在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和 （3）.在F中删除这两棵树，同时将新得到的二叉树加入F中。（4）.重复（2）和（3），直到F中只含一棵二叉树为止，即哈夫曼树。三、根据书上算法介绍进行代码编写（VC+编写）1、哈夫曼树的建立、初始化和遍历void CHFMDlg:CrtHuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w,int n) int m,i,s1,s2;m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(i=1; i=n; +i) /1-n号存放叶子结点，初始化 HTi.weight=*w;HTi.LChild=0; HTi.parent=0; HTi.RChild=0; for(i=n+1; i=m; i+)HTi.weight=0; HTi.LChild=0;HTi.parent=0; HTi.RChild=0; /非叶子结点初始化for(i=n+1; i=m; i+) /创建非叶子结点，建哈夫曼树 Select(HT,i-1,&s1,&s2);HTs1.parent=i; HTs2.parent=i; HTi.LChild=s1;HTi.RChild=s2;HTi.weight=HTs1.weight+HTs2.weight; char *cd; int j,start,p; unsigned int c; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); /分配n个编码的头指针cd=(char *)malloc(n*sizeof(char); /分配求当前编码的工作空间 cdn-1=0; /从右向左逐位存放编码，首先存放编码结束符 for(j=1; j=n; j+) /求n个叶子结点对应的哈夫曼编码 start=n-1; /初始化编码起始指针 for(c=j,p=HTj.parent; p!=0;c=p,p=HTp.parent) /从叶子到根结点遍历求编码 if( HTp.LChild=c) cd-start=0; /左分支标0else cd-start=1; /右分支标1 HCj=(char *)malloc(n-start)*sizeof(char); /为第i个编码分配空间 strcpy(HCj,&cdstart);free(cd); 2、void CHFMDlg:Select(HuffmanTree HT, int n, int *s1, int *s2)/在HT1HTi-1的范围内选择两个parent为0 /且weight最小的结点，其序号分别赋值给s1、s2 int i,min; for(i=1; i=n; i+) if(HTi.parent=0) min=i; break; for(i=1; i=n; i+)if(HTi.parent=0) if(HTi.weightHTmin.weight) min=i; *s1=min; for(i=1; i=n; i+) if(HTi.parent=0 & i!=(*s1) min=i; break; for(i=1; i=n; i+)if(hti.parent=0 & i!=(*s1)if(HTi.weightHTmin.weight) min=i; *s2=min; 四、 在MFC中进行代码编译添加列表框显示每个字符的编码界面如下：CHFMDlg对话框void CHFMDlg:SetCtrlStyle(HWND hWnd, DWORD dwNewStyle)/设置列表控件风格DWORD dwOldStyle;dwOldStyle=GetWindowLong(hWnd,GWL_STYLE);if (dwOldStyle&LVS_TYPEMASK)!=dwNewStyle)dwOldStyle&=LVS_TYPEMASK;dwNewStyle|=dwOldStyle;SetWindowLong(hWnd,GWL_STYLE,dwNewStyle);BOOL CHFMDlg:OnInitDialog()/初始化列表控件CDialog:OnInitDialog();SetCtrlStyle(m_ListCtrl.m_hWnd,LVS_REPORT);CString strHeader2=字符,编码;int nWidth2=80,100;for (int nCol=0;nCol2;nCol+)m_ListCtrl.InsertColumn(nCol,strHeadernCol,LVCFMT_LEFT,nWidthnCol);return TRUE; void CHFMDlg:OnOK()/编译按钮 / TODO: Add extra validation hereUpdateData();CString strContent,str,strValue;strContent=m_strContent;/获取编辑框中的字符串并赋/strContentint size=strContent.GetLength();/获得字符串长度str=strContent.GetAt(0);for (int i=0;isize;i+)/将不同的字符存入str中int m=0;for (int j=0;jstr.GetLength();j+)if (strContent.GetAt(i)=str.GetAt(j)m+;if (m=0) str=str+strContent.GetAt(i); int n=str.GetLength();int *strnum=new int(n);for (int k=0;kn;k+)/计算str中字符出现的次数，即权值，存/入strnum数组中int num=0;for (int j=0;jsize;j+)if (strContent.GetAt(j)=str.GetAt(k)num+;strnumk=num;HuffmanTree HT;HuffmanCode HC;CrtHuffmanCoding(HT,HC,strnum,n);CString strShow=; for (int m=0;msize;m+) for (int t=0;tn;t+)if(strContent.GetAt(m)=str.GetAt(t)strShow=strShow+*+HCt+1; SetDlgItemText(IDC_EDIT2,strShow);for (int x=0;xn;x+) CString s=str.GetAt(x);Int nIndex=m_ListCtrl.InsertItem(m_ListCtrl.GetItemCount(),s);m_ListCtrl.SetItemText(nIndex,1,HCnIndex+1);void CHFMDlg:SetCtrlStyle(HWND hWnd, DWORD dwNewStyle)DWORD dwOldStyle;dwOldStyle=G