哈夫曼樹(shù)課程設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) -哈夫曼樹(shù)編碼 哈夫曼樹(shù)編碼一、實(shí)現(xiàn)功能 給出一串字符，根據(jù)每個(gè)字符出現(xiàn)的頻數(shù)進(jìn)行編碼，將文字轉(zhuǎn)化為二進(jìn)制的字符組成的字符串，即加密。加密過(guò)程根據(jù)頻數(shù)生成哈夫曼樹(shù)，然后進(jìn)行遍歷，得到二進(jìn)制編碼。二、 哈夫曼算法敘述（1）.根據(jù)給定的n個(gè)權(quán)值w1,w2,wn構(gòu)成n棵二叉樹(shù)的集合F=T1,T2,Tn，其中每棵二叉樹(shù)Ti中只有一個(gè)帶權(quán)值為Wi的根結(jié)點(diǎn)，其左右子樹(shù)均為空。（2）.在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，且置新的二叉樹(shù)的根結(jié)點(diǎn)的權(quán)值為其左右子樹(shù)上根結(jié)點(diǎn)的權(quán)值之和 （3）.在F中刪除這兩棵樹(shù)，同時(shí)將新得到的二叉樹(shù)加入F中。（4）.重復(fù)（2）和（3

2、），直到F中只含一棵二叉樹(shù)為止，即哈夫曼樹(shù)。三、根據(jù)書上算法介紹進(jìn)行代碼編寫（VC+編寫）1、哈夫曼樹(shù)的建立、初始化和遍歷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號(hào)存放葉子結(jié)點(diǎn)，初始化 HTi.weight=*w;HTi.LChild=0; HTi.parent=0; HTi.RC

3、hild=0; for(i=n+1; i<=m; i+)HTi.weight=0; HTi.LChild=0;HTi.parent=0; HTi.RChild=0; /非葉子結(jié)點(diǎn)初始化for(i=n+1; i<=m; i+) /創(chuàng)建非葉子結(jié)點(diǎn)，建哈夫曼樹(shù) 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;

4、HC=(HuffmanCode)malloc(n+1)*sizeof(char *); /分配n個(gè)編碼的頭指針cd=(char *)malloc(n*sizeof(char); /分配求當(dāng)前編碼的工作空間 cdn-1='0' /從右向左逐位存放編碼，首先存放編碼結(jié)束符 for(j=1; j<=n; j+) /求n個(gè)葉子結(jié)點(diǎn)對(duì)應(yīng)的哈夫曼編碼 start=n-1; /初始化編碼起始指針 for(c=j,p=HTj.parent; p!=0;c=p,p=HTp.parent) /從葉子到根結(jié)點(diǎn)遍歷求編碼 if( HTp.LChild=c) cd-start='0'

5、; /左分支標(biāo)0else cd-start='1' /右分支標(biāo)1 HCj=(char *)malloc(n-start)*sizeof(char); /為第i個(gè)編碼分配空間 strcpy(HCj,&cdstart);free(cd); 2、void CHFMDlg:Select(HuffmanTree HT, int n, int *s1, int *s2)/在HT1HTi-1的范圍內(nèi)選擇兩個(gè)parent為0 /且weight最小的結(jié)點(diǎn)，其序號(hào)分別賦值給s1、s2 int i,min; for(i=1; i<=n; i+) if(HTi.parent=0) min

6、=i; break; for(i=1; i<=n; i+)if(HTi.parent=0) if(HTi.weight<HTmin.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.weight<HTmin.weight) min=i; *s2=min; 四、 在MFC中進(jìn)行代碼編譯添加列表框顯示每個(gè)字符的編碼界

7、面如下：CHFMDlg對(duì)話框void CHFMDlg:SetCtrlStyle(HWND hWnd, DWORD dwNewStyle)/設(shè)置列表控件風(fēng)格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()

8、/初始化列表控件CDialog:OnInitDialog();SetCtrlStyle(m_ListCtrl.m_hWnd,LVS_REPORT);CString strHeader2="字符","編碼"int nWidth2=80,100;for (int nCol=0;nCol<2;nCol+)m_ListCtrl.InsertColumn(nCol,strHeadernCol,LVCFMT_LEFT,nWidthnCol);return TRUE; void CHFMDlg:OnOK()/編譯按鈕 / TODO: Add extra vali

9、dation hereUpdateData();CString strContent,str,strValue;strContent=m_strContent;/獲取編輯框中的字符串并賦/strContentint size=strContent.GetLength();/獲得字符串長(zhǎng)度str=strContent.GetAt(0);for (int i=0;i<size;i+)/將不同的字符存入str中int m=0;for (int j=0;j<str.GetLength();j+)if (strContent.GetAt(i)=str.GetAt(j)m+;if (m=0)

10、str=str+strContent.GetAt(i); int n=str.GetLength();int *strnum=new int(n);for (int k=0;k<n;k+)/計(jì)算str中字符出現(xiàn)的次數(shù)，即權(quán)值，存/入strnum數(shù)組中int num=0;for (int j=0;j<size;j+)if (strContent.GetAt(j)=str.GetAt(k)num+;strnumk=num;HuffmanTree HT;HuffmanCode HC;CrtHuffmanCoding(HT,HC,strnum,n);CString strShow=&quo

11、t;" for (int m=0;m<size;m+) for (int t=0;t<n;t+)if(strContent.GetAt(m)=str.GetAt(t)strShow=strShow+"*"+HCt+1; SetDlgItemText(IDC_EDIT2,strShow);for (int x=0;x<n;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