數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告(HuffMan編碼器)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告題目：HuffMan編碼器目 錄一問題描述二基本要求(需求分析)三概要設(shè)計(設(shè)計思想、實現(xiàn)方法、模塊設(shè)計)四詳細設(shè)計(數(shù)據(jù)結(jié)構(gòu)設(shè)計、算法設(shè)計、算法分析)五測試數(shù)據(jù)及測試結(jié)果六課程設(shè)計小結(jié)(心得體會、存在問題、改進措施)一 問題描述利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。二 基本要求(需求分析)一

2、個完整的系統(tǒng)應(yīng)具有以下功能：（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼

3、文件寫入文件CodePrin中。（5）T：印哈夫曼樹（Tree printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。測試數(shù)據(jù)用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。字符 空格 A B C D E F G H I J K L M頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z頻度 57 63 15 1 48 51

4、80 23 8 18 1 16 1實現(xiàn)提示（1） 編碼結(jié)果以文本方式存儲在文件CodeFile中。（2） 用戶界面可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。（3） 在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。三 概要設(shè)計(設(shè)計思想、實現(xiàn)方法、模塊設(shè)計)哈夫曼編碼是一種效率比較高的變長無失真信源編碼方法，它的平均碼長最短，因此是最佳編碼。我采用二進制哈夫曼編碼。1 設(shè)計

5、思想a、 原理：構(gòu)造一個碼樹。b、 編碼步驟： (1) 將信源符號按概率從大到小的順序排列，為方便起見，令p(x1)p(x2)p(xn) 。 (2) 對概率最小的兩個信源符號求其概率之和，同時給兩個符號分別賦予碼元“0”和“1”。將“概率之和”當作一個新符號的概率，與剩下符號的概率一起，形成一個縮減信源，結(jié)果得到一個只包含（n1）個信源符號的新信源，稱為信源的第一次縮減信源,用S1表示。 (3) 將縮減信源S1的符號仍按概率從大到小的順序排列，重復步驟2，得到只含（n2）個符號的縮減信源S2。 (4) 重復上述步驟，直至縮減信源只剩下兩個符號為止，此時所剩兩個符號的概率之和必為1。 (5) 按

6、上述步驟實際上構(gòu)造了一個碼樹，從樹根到端點經(jīng)過的樹枝即為碼字。2 實現(xiàn)方法第一， 哈夫曼編碼實際上構(gòu)造了一個碼樹，碼樹從最上層的端點開始構(gòu)造，直到樹根束，最后得到一個橫放的碼樹，因此，編出的碼是即時碼。第二， 哈夫曼編碼采用概率匹配方法來決定各碼字的碼長，概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，從而使平均碼長最小。第三， 每次對概率最小的兩個符號求概率之和形成縮減信源時，就構(gòu)造出兩個樹枝，由于給兩個樹枝賦碼元時是任意的，因此編出的碼字并不惟一。3 模塊設(shè)計1進入的操作界面：（圖一）2輸入字符串，及編碼結(jié)果（圖二）3統(tǒng)計不同字符數(shù)及帶權(quán)路徑長度（圖三）4各字符編碼明細（圖四）四詳細設(shè)計(

7、數(shù)據(jù)結(jié)構(gòu)設(shè)計、算法設(shè)計、算法分析)（一） 數(shù)據(jù)結(jié)構(gòu)設(shè)計1) 結(jié)點類型：/huffcode.cpptypedef struct HaffmanTreeNode char ch, code15; int weight; int parent, lchild, rchild; HTNode, *HaTree;typedef struct HTNode arrMAX_NODE; int total; HTree;2) 基本操作：int statistic_char(char *text, HTree *t);int create_htree(HTree *t);void coding(HTree *t

8、, int head_i, char *code);void print_htree_ldr(HTree *t, int head_i, int deep, int* path);void code_string(char *text, HTree *t,char *codes);（二）算法設(shè)計在哈夫曼編碼過程中，對縮減信源符號按概率由大到小的順序重新排列時，應(yīng)使合并后的新符號盡可能排在靠前的位置，這樣可使合并后的新符號重復編碼次數(shù)減少，使短碼得到充分利用。（三）算法分析(1) 有效的信源編碼可取得較好的冗余壓縮效果。(2) 有效的信源編碼可使輸出碼元概率均勻化。4 測試數(shù)據(jù)及測試結(jié)果1輸入簡

9、短英文字符串：（圖五）2輸入數(shù)字英文混合串：（圖六）3混合串： （圖七） 4輸入復雜無規(guī)則長串：（圖八）六課程設(shè)計小結(jié)(心得體會、存在問題、改進措施)本次程序設(shè)計使我不僅深化理解了教學內(nèi)容，進一步提高靈活運用數(shù)據(jù)結(jié)構(gòu)、算法和程序設(shè)計技術(shù)的能力，而且在總體分析、總體結(jié)構(gòu)設(shè)計、算法設(shè)計、程序設(shè)計、上機操作及程序調(diào)試等基本技能方面受到了綜合訓練。本次實驗我選擇Huffman編譯碼器的課題。幫助我深入研究樹的各種存儲結(jié)構(gòu)的特性及其應(yīng)用。由于課程設(shè)計著眼于原理與應(yīng)用的結(jié)合，使我學會把書本上和課堂上學到的知識用于解決實際問題，從而培養(yǎng)了一部分計算機軟件工作所需要的動手能力。我通過對Huffman編譯碼原理

10、的學習，再通過分析、設(shè)計、編碼、調(diào)試等各環(huán)節(jié)，實現(xiàn)了Huffman編譯碼器的數(shù)據(jù)實現(xiàn)和界面實現(xiàn)。在Huffman編譯碼器數(shù)據(jù)結(jié)構(gòu)的算法設(shè)計中我同時用到了多種技術(shù)和方法，如算法設(shè)計的構(gòu)思方法，算法的編碼，遞歸技術(shù)，與二叉樹和樹相關(guān)的技術(shù)等。從而幫助我深入學習研究了樹的各種存儲結(jié)構(gòu)的特性及其應(yīng)用。為了實現(xiàn)界面友好的要求，我決定采用MFC的界面操作，所以必須以C+為基本語言，但是由于學習數(shù)據(jù)結(jié)構(gòu)課程是基于PASCAL，實驗數(shù)據(jù)結(jié)構(gòu)部分設(shè)計遇到一些語法沖突。但是通過課程實踐學習，我又開始熟悉C+的編程環(huán)境，從而實現(xiàn)了在不同語言上數(shù)據(jù)結(jié)構(gòu)思想的統(tǒng)一。此次課程設(shè)計并沒有劃定具體題目，包括算法需求都由我們度

11、量，思路開闊。我始終和同學探討并獨立研究新的功能的實現(xiàn)。通過嘗試來學習，通過實踐去理解。當然，通過多天來的上機實踐，我獲取了一些心得：一充分準備。由于課題寬泛，很多同學去網(wǎng)上下了界面優(yōu)良的源程序。相對而言在DOS下編程的我開始時很焦急，不知如何實現(xiàn)界面友好。準備充分是很重要的，為了實現(xiàn)MFC，我重新學習了C+語言。二冷靜，耐心投入。集中精力地編程，不被外界影響，使自己的思路始終連貫不被打斷。對待每一個錯誤，都要仔細分析，太過焦急，不僅不能及時的改正錯誤，還對后面的編程造成影響。三要有一種堅持不懈的毅力，不管自己的程序多么復雜，多么冗長，要堅持不懈的去完成。冷靜思考。四要對自己有信心，出錯是必然

12、的?！皩覒?zhàn)屢敗，屢敗屢戰(zhàn)”，不怕受挫的心理承受能力和從零開始的決心是走向成功的必要條件。五學會與別人學習討論，但不依賴別人，可以通過借鑒思路從而創(chuàng)新，但決不照搬別人的東西。通過查找資料，我發(fā)現(xiàn)我們做Huffman編碼和解碼時，一般都要在內(nèi)存通過指針生成Huffman樹，這是一個比較費時間、費空間的過程。實際上，真正的Huffman編碼程序經(jīng)常使用其他更快的數(shù)據(jù)結(jié)構(gòu)來完成樹的生成，如散列等。所以我的課題有待繼續(xù)學習研究。用戶手冊/使用說明 （圖九）1在此處輸入要編碼的字符串，點擊進行編碼。2再次輸入時再點擊可成功使用，不會受之前結(jié)果影響。附錄(源程序清單)/huffcode.cpp/C編寫的源代

13、碼，原來含有writef()以及printf(),但由于最終用MFC界面實現(xiàn)，故刪去，只作為一/些功能子函數(shù)被MFC的對話框類調(diào)用。/另外，對于類型申明等已包含于頭文件。#include "stdafx.h"#include "huffcode.h"/* 統(tǒng)計字符出現(xiàn)的頻率 */int statistic_char(char *text, HTree *t) int i, j; int text_len = strlen(text); t->total = 0; for (i=0; i<text_len; i+) for (j=0; j<

14、;t->total; j+) if (t->arrj.ch = texti) t->arrj.weight +; break; if (j=t->total) t->arrt->total.ch = texti; t->arrt->total.weight = 1; t->total +; return t->total;int create_htree(HTree *t) int i; int total_node = t->total * 2 - 1;int min1, min2; /* 權(quán)最小的兩個結(jié)點 */ int mi

15、n1_i, min2_i; /* 權(quán)最小結(jié)點對應(yīng)的編號 */ int leaves = t->total; for (i=0; i<leaves; i+) t->arri.parent = -1; t->arri.rchild = -1; t->arri.lchild = -1; while (t->total < total_node) min1 = min2 = MAX_WEIGHT; for (i=0; i<t->total; i+) /* 對每一個結(jié)點 */ if (t->arri.parent = -1 /* 結(jié)點沒有被合并

16、 */ && t->arri.weight < min2) /* 結(jié)點的權(quán)比最小權(quán)小 */ if (t->arri.weight < min1) /* 如果它比最小的結(jié)點還小 */ min2_i = min1_i; min2 = min1; min1_i = i; min1 = t->arri.weight; else min2_i = i; min2 = t->arri.weight; t->arrt->total.weight = min1 + min2; t->arrt->total.parent = -1; t

17、->arrmin1_i.parent = t->total; t->arrmin2_i.parent = t->total; t->arrt->total.ch = ' ' t->total +; return 0;/* 對哈夫曼樹進行編碼 */void coding(HTree *t, int head_i, char *code) if ( head_i = -1) return; if (t->arrhead_i.lchild = -1 && t->arrhead_i.rchild = -1) strc

18、py(t->arrhead_i.code, code);/ else int len = strlen(code); strcat(code, "0"); coding(t, t->arrhead_i.lchild, code); codelen = '1' coding(t, t->arrhead_i.rchild, code); codelen = '0' /* 對字符進行編碼 */void code_string(char *text, HTree *t,char *codes) int i, j, text_len

19、= strlen(text); int n = 0; for (i=0; i<text_len; i+) char ch = texti; for (j=0; j<t->total; j+) if (ch = t->arrj.ch) strcat(codes, t->arrj.code); break; / DlgString.cpp /作為執(zhí)行文件，通過MFC的可視化界面實現(xiàn)HuffMan編譯碼器#include "stdafx.h"#include "iostream.h"#include "string.h&

20、quot;#include "math.h"#include "HUFFMANTREE.h"#include "DlgString.h"#include "huffcode.h"#ifdef _DEBUG#define new DEBUG_NEW#undef THIS_FILEstatic char THIS_FILE = _FILE_;#endifCDlgString:CDlgString(CWnd* pParent /*=NULL*/): CDialog(CDlgString:IDD, pParent)/AFX

21、_DATA_INIT(CDlgString)m_inStr = _T("");m_outstr = _T("");m_wpl = _T("");m_number = _T("");/AFX_DATA_INITvoid CDlgString:DoDataExchange(CDataExchange* pDX)CDialog:DoDataExchange(pDX);/AFX_DATA_MAP(CDlgString)DDX_Control(pDX, IDC_LIST1, m_chars);DDX_Text(pDX, ID

22、C_EDIT_STR, m_inStr);DDX_Text(pDX, IDC_STATIC_OUT, m_outstr);DDX_Text(pDX, IDC_STATIC_WPL, m_wpl);DDX_Text(pDX, IDC_STATIC_NUM, m_number);/AFX_DATA_MAPBEGIN_MESSAGE_MAP(CDlgString, CDialog)/AFX_MSG_MAP(CDlgString)ON_NOTIFY(NM_CLICK, IDC_LIST1, OnClickList1)/AFX_MSG_MAPEND_MESSAGE_MAP()/ CDlgString m

23、essage handlersvoid CDlgString:OnOK() UpdateData(true);/ TODO: Add extra validation herem_chars.DeleteAllItems();CBrush brush(RGB(225,30,100);CClientDC dc(this);dc.FillRect(CRect(630,10,1050,280),&brush);/ 清屏 int i,ci,n,nn,wpl,len; int x,y,h; HTree t; m_outstr= _T(""); int path16=0; ch

24、ar code128 = "" char codes128 = ""CString str; char text128; strcpy(text,m_inStr); n=statistic_char(text, &t);/n用于存儲葉子個數(shù) h=(int)(log(n)/log(2)+1); create_htree(&t);/建樹 coding(&t, t.total-1, code);/編碼 UpdateData(TRUE); wpl=0;for(ci=1;ci<=n;ci+) CClientDC *pdc = new

25、CClientDC(this);CPen pen;pen.CreatePen(PS_SOLID,1,RGB(225,250,250);CPen *oldpen =(CPen *)pdc->SelectObject(&pen);/建筆 x=800;y=20;/ 原始坐標設(shè)定pdc->MoveTo(x,y);/每次路徑都從同一源點開始str.Format(_T("%c"),t.arrci-1.ch);/*對n個葉子的明細輸入列表*/nn=m_chars.InsertItem(m_chars.GetItemCount(),str); str.Format(_T

26、("%s"),t.arrci-1.code);m_chars.SetItemText(nn,1,str);str.Format(_T("%d"),t.arrci-1.weight);m_chars.SetItemText(nn,2,str); len=strlen(t.arrci-1.code);str.Format(_T("%d"),len);m_chars.SetItemText(nn,3,str);wpl+=t.arrci-1.weight*len; for(i=0;i<len;i+)/*對n個葉子的編碼路徑畫圖，此處循環(huán)

27、完成一個葉子的路徑*/y=y+50;if(t.arrci-1.codei='0') /向左x=x-8*(h-i+1);pdc->LineTo(x,y);pdc->MoveTo(x,y); if(i=len-1)str.Format(_T("%c"),t.arrci-1.ch);pdc->TextOut(x,y+10,str);else if(t.arrci-1.codei='1')/向右x=x+8*(h-i+1); pdc->LineTo(x,y);pdc->MoveTo(x,y);if(i=len-1)str.

28、Format(_T("%c"),t.arrci-1.ch);pdc->TextOut(x,y+10,str); str.Format(_T("%d"),wpl);m_wpl=str;/在對話框上顯示最短帶權(quán)路徑str.Format(_T("%d"),n);m_number=str;/在對話框上顯示不同的編碼字符總數(shù)UpdateData(false);code_string(text, &t,codes);str.Format(_T("%s"),codes);m_outstr=str;/在對話框上輸出對應(yīng)于輸入字符串的編碼結(jié)果UpdateData(false); v