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

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計</b></p><p><b>　　---哈夫曼樹編碼</b></p><p><b>　　哈夫曼樹編碼</b></p><p><b>　　一、實現(xiàn)功能</b></p><p>　　給出一串字符，根據(jù)每個字

2、符出現(xiàn)的頻數(shù)進行編碼，將文字轉(zhuǎn)化為二進制的字符組成的字符串，即加密。加密過程根據(jù)頻數(shù)生成哈夫曼樹，然后進行遍歷，得到二進制編碼。</p><p>　　二、 哈夫曼算法敘述</p><p>　?。?）.根據(jù)給定的n個權(quán)值{w1,w2,…,wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn}，其中每棵二叉樹Ti中只有一個帶權(quán)值為Wi的根結(jié)點，其左右子樹均為空。</p><

3、p>　?。?）.在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和 </p><p>　?。?）.在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。</p><p>　　（4）.重復(fù)（2）和（3），直到F中只含一棵二叉樹為止，即哈夫曼樹。</p><p>　　三、根據(jù)書上算法介紹進行代碼

4、編寫（VC++編寫）</p><p>　　1、哈夫曼樹的建立、初始化和遍歷</p><p>　　void CHFMDlg::CrtHuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w,int n)</p><p><b>　　{</b></p><p&g

5、t;　　int m,i,s1,s2;</p><p><b>　　m=2*n-1; </b></p><p>　　HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); </p><p>　　for(i=1; i<=n; ++i) //1--n號存放葉子結(jié)點，初始化 </p><p&

6、gt;<b>　　{</b></p><p>　　HT[i].weight=*w;</p><p>　　HT[i].LChild=0; </p><p>　　HT[i].parent=0; </p><p>　　HT[i].RChild=0; </p><p><b>　　} </

7、b></p><p>　　for(i=n+1; i<=m; i++)</p><p><b>　　{</b></p><p>　　HT[i].weight=0; </p><p>　　HT[i].LChild=0;</p><p>　　HT[i].parent=0; </p>

8、;<p>　　HT[i].RChild=0; </p><p><b>　　}</b></p><p>　　//非葉子結(jié)點初始化</p><p>　　for(i=n+1; i<=m; i++) //創(chuàng)建非葉子結(jié)點，建哈夫曼樹</p><p><b>　　{ </b></p&

9、gt;<p>　　Select(HT,i-1,&s1,&s2);</p><p>　　HT[s1].parent=i; </p><p>　　HT[s2].parent=i; </p><p>　　HT[i].LChild=s1;</p><p>　　HT[i].RChild=s2;</p><

10、;p>　　HT[i].weight=HT[s1].weight+HT[s2].weight; </p><p><b>　　}</b></p><p>　　char *cd; </p><p>　　int j,start,p; </p><p>　　unsigned int c; </p><p

11、>　　HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); //分配n個編碼的頭指針</p><p>　　cd=(char *)malloc(n*sizeof(char)); //分配求當前編碼的工作空間 </p><p>　　cd[n-1]='\0'; </p><p>　　//從右向左逐位存放編碼

12、，首先存放編碼結(jié)束符 </p><p>　　for(j=1; j<=n; j++) //求n個葉子結(jié)點對應(yīng)的哈夫曼編碼 </p><p><b>　　{ </b></p><p>　　start=n-1; //初始化編碼起始指針 </p><p>　　for(c=j,p=HT[j].parent; p!=0

13、;c=p,p=HT[p].parent) </p><p>　　//從葉子到根結(jié)點遍歷求編碼 </p><p>　　if( HT[p].LChild==c) </p><p>　　cd[--start]='0'; //左分支標0</p><p><b>　　else </b></p>&

14、lt;p>　　cd[--start]='1'; //右分支標1 </p><p>　　HC[j]=(char *)malloc((n-start)*sizeof(char)); </p><p>　　//為第i個編碼分配空間 </p><p>　　strcpy(HC[j],&cd[start]);</p><p&

15、gt;<b>　　}</b></p><p>　　free(cd); </p><p><b>　　}</b></p><p><b>　　2、</b></p><p>　　void CHFMDlg::Select(HuffmanTree HT, int n, int *s1,

16、 int *s2)</p><p>　　//在HT[1]~HT[i-1]的范圍內(nèi)選擇兩個parent為0 </p><p>　　//且weight最小的結(jié)點，其序號分別賦值給s1、s2</p><p><b>　　{</b></p><p>　　int i,min; </p><p>　　for(

17、i=1; i<=n; i++) </p><p><b>　　{ </b></p><p>　　if(HT[i].parent==0) </p><p>　　{ min=i; break; } </p><p><b>　　}</b></p><p>　　for(i=1

18、; i<=n; i++)</p><p><b>　　{</b></p><p>　　if(HT[i].parent==0) </p><p><b>　　{ </b></p><p>　　if(HT[i].weight<HT[min].weight) </p><p

19、><b>　　min=i; </b></p><p><b>　　} </b></p><p><b>　　}</b></p><p><b>　　*s1=min; </b></p><p>　　for(i=1; i<=n; i++) <

20、/p><p><b>　　{ </b></p><p>　　if(HT[i].parent==0 && i!=(*s1))</p><p>　　{ min=i; break; }</p><p><b>　　} </b></p><p>　　for(i=1; i&

21、lt;=n; i++)</p><p><b>　　{</b></p><p>　　if(ht[i].parent==0 && i!=(*s1))</p><p><b>　　{</b></p><p>　　if(HT[i].weight<HT[min].weight) <

22、;/p><p><b>　　min=i;</b></p><p><b>　　}</b></p><p><b>　　} </b></p><p><b>　　*s2=min; </b></p><p><b>　　}<

23、/b></p><p>　　四、 在MFC中進行代碼編譯</p><p>　　添加列表框顯示每個字符的編碼</p><p>　　界面如下：CHFMDlg對話框</p><p>　　void CHFMDlg::SetCtrlStyle(HWND hWnd, DWORD dwNewStyle)</p><p>　　/

24、/設(shè)置列表控件風(fēng)格</p><p><b>　　{</b></p><p>　　DWORD dwOldStyle;</p><p>　　dwOldStyle=GetWindowLong(hWnd,GWL_STYLE);</p><p>　　if ((dwOldStyle&LVS_TYPEMASK)!=dwNew

25、Style)</p><p><b>　　{</b></p><p>　　dwOldStyle&=~LVS_TYPEMASK;</p><p>　　dwNewStyle|=dwOldStyle;</p><p>　　SetWindowLong(hWnd,GWL_STYLE,dwNewStyle);</p&g

26、t;<p><b>　　}</b></p><p><b>　　}</b></p><p>　　BOOL CHFMDlg::OnInitDialog()//初始化列表控件</p><p><b>　　{</b></p><p>　　CDialog::OnInitD

27、ialog();</p><p><b>　　……………</b></p><p>　　SetCtrlStyle(m_ListCtrl.m_hWnd,LVS_REPORT);</p><p>　　CString strHeader[2]={"字符","編碼"};</p><p>　　

28、int nWidth[2]={80,100};</p><p>　　for (int nCol=0;nCol<2;nCol++)</p><p><b>　　{</b></p><p>　　m_ListCtrl.InsertColumn(nCol,strHeader[nCol],LVCFMT_LEFT,nWidth[nCol]);<

29、/p><p><b>　　}</b></p><p>　　return TRUE; </p><p><b>　　}</b></p><p>　　void CHFMDlg::OnOK()//編譯按鈕 </p><p><b>　　{</b></p&g

30、t;<p>　　// TODO: Add extra validation here</p><p>　　UpdateData();</p><p>　　CString strContent,str,strValue;</p><p>　　strContent=m_strContent;//獲取編輯框中的字符串并賦//strContent</p&

31、gt;<p>　　int size=strContent.GetLength();//獲得字符串長度</p><p>　　str=strContent.GetAt(0);</p><p>　　for (int i=0;i<size;i++)//將不同的字符存入str中</p><p><b>　　{</b></p>

32、;<p><b>　　int m=0;</b></p><p>　　for (int j=0;j<str.GetLength();j++)</p><p>　　if (strContent.GetAt(i)==str.GetAt(j))</p><p><b>　　m++;</b></p>

33、<p>　　if (m==0) str=str+strContent.GetAt(i);</p><p><b>　　}</b></p><p>　　int n=str.GetLength();</p><p>　　int *strnum=new int(n);</p><p>　　for (int k=0

34、;k<n;k++)//計算str中字符出現(xiàn)的次數(shù)，即權(quán)值，存//入strnum數(shù)組中</p><p><b>　　{</b></p><p>　　int num=0;</p><p>　　for (int j=0;j<size;j++)</p><p>　　if (strContent.GetAt(j)==s

35、tr.GetAt(k))</p><p><b>　　num++;</b></p><p>　　strnum[k]=num;</p><p><b>　　}</b></p><p>　　HuffmanTree HT;</p><p>　　HuffmanCode HC;<

36、/p><p>　　CrtHuffmanCoding(HT,HC,strnum,n);</p><p>　　CString strShow="";</p><p>　　for (int m=0;m<size;m++)</p><p><b>　　{</b></p><p>　

37、　for (int t=0;t<n;t++)</p><p>　　if(strContent.GetAt(m)==str.GetAt(t))</p><p>　　strShow=strShow+"*"+HC[t+1];</p><p><b>　　}</b></p><p>　　SetDlgIt

38、emText(IDC_EDIT2,strShow);</p><p>　　for (int x=0;x<n;x++)</p><p><b>　　{</b></p><p>　　CString s=str.GetAt(x);</p><p>　　Int nIndex=m_ListCtrl.InsertItem(m

39、_ListCtrl.GetItemCount(),s);</p><p>　　m_ListCtrl.SetItemText(nIndex,1,HC[nIndex+1]);</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　void CHFMDlg::

40、SetCtrlStyle(HWND hWnd, DWORD dwNewStyle)</p><p><b>　　{</b></p><p>　　DWORD dwOldStyle;</p><p>　　dwOldStyle=GetWindowLong(hWnd,GWL_STYLE);</p><p>　　if ((dwO

41、ldStyle&LVS_TYPEMASK)!=dwNewStyle)</p><p><b>　　{</b></p><p>　　dwOldStyle&=~LVS_TYPEMASK;</p><p>　　dwNewStyle|=dwOldStyle;</p><p>　　SetWindowLong(hWn