哈夫曼樹課程設計

1、<p><b>　　數據結構課程設計</b></p><p><b>　　---哈夫曼樹編碼</b></p><p><b>　　哈夫曼樹編碼</b></p><p><b>　　一、實現功能</b></p><p>　　給出一串字符，根據每個字

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

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

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號存放葉子結點，初始化 </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>　　//非葉子結點初始化</p><p>　　for(i=n+1; i<=m; i++) //創(chuàng)建非葉子結點，建哈夫曼樹</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、，首先存放編碼結束符 </p><p>　　for(j=1; j<=n; j++) //求n個葉子結點對應的哈夫曼編碼 </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>　　//從葉子到根結點遍歷求編碼 </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]的范圍內選擇兩個parent為0 </p><p>　　//且weight最小的結點，其序號分別賦值給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、/設置列表控件風格</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中字符出現的次數，即權值，存//入strnum數組中</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