第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告(HuffMan編碼器)
《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計報告
題目：HuffMan編碼器
數(shù)據(jù)結(jié)構(gòu)設(shè)計報告
計科0403
041106308
雷娜
目 錄
一．問題描述
二．基本要求(需求分析)
三．?概要設(shè)計(設(shè)計思想、實(shí)現(xiàn)方法、模塊設(shè)計)
四．?詳細(xì)設(shè)計(數(shù)據(jù)結(jié)構(gòu)設(shè)計、算法設(shè)計、算法分析)
五．測試數(shù)據(jù)及測試結(jié)果
六．課程設(shè)計小結(jié)(心得體會、存在問題、改進(jìn)措施)
一． 問題描述
利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。
第 1 頁
數(shù)據(jù)結(jié)構(gòu)設(shè)計報告
計科0403
041106308
雷娜
但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。二． 基本要求(需求分析)
一個完整的系統(tǒng)應(yīng)具有以下功能：
（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。
（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。
（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。
（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。
（5）T：印哈夫曼樹（Tree printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。[測試數(shù)據(jù)] 用下表給出的字符集和頻度的實(shí)際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。
字符 空格 A
B
C
D
E
F
G
H
I
J
K
L
M 頻度 186
13 22 32 103 21 15 47 57 1
20 字符 N
O
P
Q
R
S
T
U
V
W
X
Y
Z 頻度 57
15 1
51 80 23 8 1 1[實(shí)現(xiàn)提示]
（1）編碼結(jié)果以文本方式存儲在文件CodeFile中。
（2）用戶界面可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示退出運(yùn)行Quit。請用戶鍵入一個選擇功能符。此功能執(zhí)行完畢后再顯示此菜單，直至某次用戶選擇了“Q”為止。
（3）在程序的一次執(zhí)行過程中，第一次執(zhí)行I，D或C命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。
三． 概要設(shè)計(設(shè)計思想、實(shí)現(xiàn)方法、模塊設(shè)計)哈夫曼編碼是一種效率比較高的變長無失真信源編碼方法，它的平均碼長
第 2 頁
數(shù)據(jù)結(jié)構(gòu)設(shè)計報告
計科0403
041106308
雷娜
最短，因此是最佳編碼。我采用二進(jìn)制哈夫曼編碼。
1． 設(shè)計思想
a、原理：構(gòu)造一個碼樹。
b、編碼步驟：
(1)將信源符號按概率從大到小的順序排列，為方便起見，令p(x1)≥p(x2)≥?≥p(xn)。
(2)對概率最小的兩個信源符號求其概率之和，同時給兩個符號分別賦予碼元“0 ”和“1”。將“概率之和”當(dāng)作一個新符號的概率，與剩下符號的概率一起，形成一個縮減信源，結(jié)果得到一個只包含（n－1）個信源符號的新信源，稱為信源的第一次縮減信源,用S1表示。
(3)將縮減信源S1的符號仍按概率從大到小的順序排列，重復(fù)步驟2，得到只含（n－2）個符號的縮減信源S2。
(4)重復(fù)上述步驟，直至縮減信源只剩下兩個符號為止，此時所剩兩個符號的概率之和必為1。
(5)按上述步驟實(shí)際上構(gòu)造了一個碼樹，從樹根到端點(diǎn)經(jīng)過的樹枝即為碼字。
2． 實(shí)現(xiàn)方法
第一，哈夫曼編碼實(shí)際上構(gòu)造了一個碼樹，碼樹從最上層的端點(diǎn)開始構(gòu)造，直到樹根束，最后得到一個橫放的碼樹，因此，編出的碼是即時碼。
第二，哈夫曼編碼采用概率匹配方法來決定各碼字的碼長，概率大的符號對應(yīng)于短碼，概率小的符號對應(yīng)于長碼，從而使平均碼長最小。
第三，每次對概率最小的兩個符號求概率之和形成縮減信源時，就構(gòu)造出兩個樹枝，由于給兩個樹枝賦碼元時是任意的，因此編出的碼字并不惟一。
3． 模塊設(shè)計
第 3 頁
數(shù)據(jù)結(jié)構(gòu)設(shè)計報告
計科0403
041106308
雷娜
1．進(jìn)入的操作界面：
（圖一）
2．輸入字符串，及編碼結(jié)果
（圖二）
3．統(tǒng)計不同字符數(shù)及帶權(quán)路徑長度
（圖三）
4．各字符編碼明細(xì)
第 4 頁
數(shù)據(jù)結(jié)構(gòu)設(shè)計報告
計科0403
041106308
雷娜
（圖四）
四．詳細(xì)設(shè)計(數(shù)據(jù)結(jié)構(gòu)設(shè)計、算法設(shè)計、算法分析)
（一）數(shù)據(jù)結(jié)構(gòu)設(shè)計
1)結(jié)點(diǎn)類型：
//huffcode.cpp
typedef struct HaffmanTreeNode {
char ch, code[15];
int weight;
int parent, lchild, rchild;} HTNode, *HaTree;
typedef struct { HTNode arr[MAX_NODE];
int total;} HTree;
2)基本操作：
第 5 頁
數(shù)據(jù)結(jié)構(gòu)設(shè)計報告
計科0403
041106308
雷娜
int statistic_char(char *text, HTree *t);int create_htree(HTree *t);void coding(HTree *t, 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)使合并后的新符號盡可能排在靠前的位置，這樣可使合并后的新符號重復(fù)編碼次數(shù)減少，使短碼得到充分利用。
（三）算法分析
(1)有效的信源編碼可取得較好的冗余壓縮效果。(2)有效的信源編碼可使輸出碼元概率均勻化。
4． 測試數(shù)據(jù)及測試結(jié)果
1．輸入簡短英文字符串：
（圖五）
2．輸入數(shù)字英文混合串：
第 6 頁
數(shù)據(jù)結(jié)構(gòu)設(shè)計報告
計科0403
041106308
雷娜
（圖六）
3．混合串：
（圖七）
4．輸入復(fù)雜無規(guī)則長串：
（圖八）
第 7 頁
數(shù)據(jù)結(jié)構(gòu)設(shè)計報告
計科0403
041106308
雷娜
六．課程設(shè)計小結(jié)(心得體會、存在問題、改進(jìn)措施)
本次程序設(shè)計使我不僅深化理解了教學(xué)內(nèi)容，進(jìn)一步提高靈活運(yùn)用數(shù)據(jù)結(jié)構(gòu)、算法和程序設(shè)計技術(shù)的能力，而且在總體分析、總體結(jié)構(gòu)設(shè)計、算法設(shè)計、程序設(shè)計、上機(jī)操作及程序調(diào)試等基本技能方面受到了綜合訓(xùn)練。
本次實(shí)驗我選擇Huffman編譯碼器的課題。幫助我深入研究樹的各種存儲結(jié)構(gòu)的特性及其應(yīng)用。由于課程設(shè)計著眼于原理與應(yīng)用的結(jié)合，使我學(xué)會把書本上和課堂上學(xué)到的知識用于解決實(shí)際問題，從而培養(yǎng)了一部分計算機(jī)軟件工作所需要的動手能力。
我通過對Huffman編譯碼原理的學(xué)習(xí)，再通過分析、設(shè)計、編碼、調(diào)試等各環(huán)節(jié)，實(shí)現(xiàn)了Huffman編譯碼器的數(shù)據(jù)實(shí)現(xiàn)和界面實(shí)現(xiàn)。在Huffman編譯碼器數(shù)據(jù)結(jié)構(gòu)的算法設(shè)計中我同時用到了多種技術(shù)和方法，如算法設(shè)計的構(gòu)思方法，算法的編碼，遞歸技術(shù)，與二叉樹和樹相關(guān)的技術(shù)等。從而幫助我深入學(xué)習(xí)研究了樹的各種存儲結(jié)構(gòu)的特性及其應(yīng)用。
為了實(shí)現(xiàn)界面友好的要求，我決定采用MFC的界面操作，所以必須以C++為基本語言，但是由于學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)課程是基于PASCAL，實(shí)驗數(shù)據(jù)結(jié)構(gòu)部分設(shè)計遇到一些語法沖突。但是通過課程實(shí)踐學(xué)習(xí)，我又開始熟悉C++的編程環(huán)境，從而實(shí)現(xiàn)了在不同語言上數(shù)據(jù)結(jié)構(gòu)思想的統(tǒng)一。
此次課程設(shè)計并沒有劃定具體題目，包括算法需求都由我們度量，思路開闊。我始終和同學(xué)探討并獨(dú)立研究新的功能的實(shí)現(xiàn)。通過嘗試來學(xué)習(xí)，通過實(shí)踐去理解。
當(dāng)然，通過多天來的上機(jī)實(shí)踐，我獲取了一些心得：
一．充分準(zhǔn)備。由于課題寬泛，很多同學(xué)去網(wǎng)上下了界面優(yōu)良的源程序。相對而言在DOS下編程的我開始時很焦急，不知如何實(shí)現(xiàn)界面友好。準(zhǔn)備充分是很重要的，為了實(shí)現(xiàn)MFC，我重新學(xué)習(xí)了C++語言。
二．冷靜，耐心投入。集中精力地編程，不被外界影響，使自己的思路始終連貫不被打斷。對待每一個錯誤，都要仔細(xì)分析，太過焦急，不僅不能及時的改正錯誤，還對后面的編程造成影響。
三．要有一種堅持不懈的毅力，不管自己的程序多么復(fù)雜，多么冗長，要堅持不懈的去完成。冷靜思考。
四．要對自己有信心，出錯是必然的。“屢戰(zhàn)屢敗，屢敗屢戰(zhàn)”，不怕受挫的心理承受能力和從零開始的決心是走向成功的必要條件。
五．學(xué)會與別人學(xué)習(xí)討論，但不依賴別人，可以通過借鑒思路從而創(chuàng)新，但決不照搬別人的東西。
第 8 頁
數(shù)據(jù)結(jié)構(gòu)設(shè)計報告
計科0403
041106308
雷娜
通過查找資料，我發(fā)現(xiàn)我們做Huffman編碼和解碼時，一般都要在內(nèi)存通過指針生成Huffman樹，這是一個比較費(fèi)時間、費(fèi)空間的過程。實(shí)際上，真正的Huffman編碼程序經(jīng)常使用其他更快的數(shù)據(jù)結(jié)構(gòu)來完成樹的生成，如散列等。所以我的課題有待繼續(xù)學(xué)習(xí)研究。
?用戶手冊/使用說明
（圖九）
1．在此處輸入要編碼的字符串，點(diǎn)擊進(jìn)行編碼。
2．再次輸入時再點(diǎn)擊可成功使用，不會受之前結(jié)果影響。
?附錄(源程序清單)//huffcode.cpp //C編寫的源代碼，原來含有writef()以及printf(),但由于最終用MFC界面實(shí)現(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 for(j=0;j if(t->arr[j].ch == text[i]) { 第 9 頁 數(shù)據(jù)結(jié)構(gòu)設(shè)計報告 計科0403 041106308 雷娜 t->arr[j].weight ++; break; } if(j==t->total){ t->arr[t->total].ch = text[i]; t->arr[t->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é)點(diǎn) */ int min1_i, min2_i;/* 權(quán)最小結(jié)點(diǎn)對應(yīng)的編號 */ int leaves = t->total; for(i=0;i t->arr[i].parent =-1; t->arr[i].rchild =-1; t->arr[i].lchild =-1; } while(t->total < total_node){ min1 = min2 = MAX_WEIGHT; for(i=0;i 對每一個結(jié)點(diǎn) */ if(t->arr[i].parent ==-1 /* 結(jié)點(diǎn)沒有被合并 */ && t->arr[i].weight < min2){ /* 結(jié)點(diǎn)的權(quán)比最小權(quán)小 */ if(t->arr[i].weight < min1){ /* 如果它比最小的結(jié)點(diǎn)還小 */ min2_i = min1_i;min2 = min1; min1_i = i; min1 = t->arr[i].weight; } else { min2_i = i; min2 = t->arr[i].weight; } } } t->arr[t->total].weight = min1 + min2; t->arr[t->total].parent =-1; t->arr[min1_i].parent = t->total; t->arr[min2_i].parent = t->total; t->arr[t->total].ch = ' '; 第10 頁 數(shù)據(jù)結(jié)構(gòu)設(shè)計報告 計科0403 041106308 雷娜 t->total ++; } return 0;} /* 對哈夫曼樹進(jìn)行編碼 */ void coding(HTree *t, int head_i, char *code){ if(head_i ==-1)return; if(t->arr[head_i].lchild ==-1 && t->arr[head_i].rchild ==-1){ strcpy(t->arr[head_i].code, code);/ } else { int len = strlen(code); strcat(code, “0”); coding(t, t->arr[head_i].lchild, code); code[len] = '1'; coding(t, t->arr[head_i].rchild, code); code[len] = '