武漢理工大學(xué)《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)說明書 哈夫曼編碼 1．問題分析與

1、哈夫曼編碼1問題分析與任務(wù)定義1.1 需求分析.1 用哈夫曼編碼進(jìn)行通信可以大大提高通信利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)射端通過一個(gè)編碼系統(tǒng)對(duì)待傳輸?shù)臄?shù)據(jù)預(yù)先編碼，在接受端將傳來的數(shù)據(jù)進(jìn)行譯碼(復(fù)原)。對(duì)于雙工信息道(既可以雙向傳輸信息的通道)，每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編譯/碼系統(tǒng)。.2 本演示程序中，用戶可以輸入鍵盤中的任意字符，長(zhǎng)度為任意長(zhǎng)，字符輸入順序不限，且允許出現(xiàn)重碼。.3 演示程序以用戶與計(jì)算機(jī)的對(duì)話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令，相應(yīng)的輸入數(shù)據(jù)（可慮去

2、輸入中的非法字符）和運(yùn)算結(jié)果顯示在其后。.4 在本系統(tǒng)中，用戶可以對(duì)任意長(zhǎng)的字符串可進(jìn)行編碼/譯碼。1.2 設(shè)計(jì)基本要求： 一個(gè)完整的系統(tǒng)應(yīng)該包括以下功能： 初始化（initalization）. 從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值,建立哈夫曼樹, 中. 編碼(Encoding)。利用已建立好的哈夫曼樹（如不在內(nèi)存，則從文件中讀入），對(duì)文件中的正文進(jìn)行編碼,然后將結(jié)果代碼存(傳輸)到文件codeFile中. 譯碼(Decoding)。利用已建好的哈夫曼樹,對(duì)傳輸?shù)竭_(dá)的CodeFile中的數(shù)據(jù)代碼進(jìn)行譯碼,將譯碼結(jié)果存入文件TextFile中. 印文件代碼(Print)。將文件Cod

3、eFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。.5 印哈夫曼樹(TreePrinting)。將已在內(nèi)存中的哈夫曼樹以直觀的方式(樹或凹入表的形式)顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。 任務(wù)定義 1.3.1 程序執(zhí)行的命令包括：1）初始化 2）編碼 3）譯碼 4）印代碼文件 5）印哈夫曼樹 6）退出 1.3.2 測(cè)試數(shù)據(jù): 1) 利用教科書例6-2中的數(shù)據(jù)調(diào)試程序。2)用程序文件夾中的text.txt文件進(jìn)行測(cè)試,并把得到的哈夫曼編碼寫入codefile.txt文件中。2數(shù)據(jù)類型和系統(tǒng)設(shè)計(jì) 2.1邏輯設(shè)計(jì)

4、 為實(shí)現(xiàn)上述程序，須將程序分模塊設(shè)計(jì)，具體設(shè)計(jì)為四個(gè)模塊：分別是二叉樹節(jié)點(diǎn)模塊，二叉樹實(shí)現(xiàn)的模塊，哈夫曼樹的實(shí)現(xiàn)模塊及測(cè)試模塊。各模塊的抽象數(shù)據(jù)類型如下： 二叉樹節(jié)點(diǎn)模塊： 本模塊中主要定義二叉樹節(jié)點(diǎn)的類型，包括：.1樹的節(jié)點(diǎn)值 m_data.2指向左孩子節(jié)點(diǎn)的指針 left_child.3指向右孩子節(jié)點(diǎn)的指針 right_child 二叉樹實(shí)現(xiàn)的模塊 本模塊中主要根據(jù)二叉樹的節(jié)點(diǎn)，來建立一系列的操作，即:.1 初始化一棵二叉樹 BinaryTree_T(void);.2二叉樹的賦值BinaryTree_T<T>& operator=(const BinaryTree_T&

5、lt;T>& bt).3 二叉樹的遍歷 void PreOrder(void); .4 二叉樹的清空 void Clear(void);.5 二叉樹的訪問 void Visit(const TreeNode_T<T>*ptr) 哈夫曼樹的實(shí)現(xiàn)模塊 本模塊中根據(jù)二叉樹來建立哈夫曼樹，主要包括： .1 哈夫曼樹的初始化 HfmTree_T(void) .2 哈夫曼樹的創(chuàng)建 void CreatHfmTree(void); .3 哈夫曼樹的創(chuàng)建 HfmTree_T<W>& operator=(const HfmTree_T<W> &r

6、hs); .4 文件譯碼 void Code(char *&code);； .5 文件的解碼 void GenerateCode(BinaryTree_T<int> &P); 主測(cè)試模塊 int main() HfmTree_T<int>hfmTree;hfmTree.CreatHfmTree(); hfmTree.GenerateCode(); hfmTree.DeCode(); return 0; 2.2 詳細(xì)設(shè)計(jì) 本部分內(nèi)容主要包括對(duì)模塊的抽象，及將其抽象出一般的定義，各模塊的抽象數(shù)據(jù)類型如下： 抽象數(shù)據(jù)類型TreeNode_h 用以實(shí)現(xiàn)二叉樹的節(jié)

7、點(diǎn)，其定義如下： Template<class T> Class TreeNode_T Private:T m_data;/樹的節(jié)點(diǎn)值TreeNode_T<T> *left_child;/指向左孩子節(jié)點(diǎn)的指針 TreeNode_T<T> *right_child;/指向右孩子節(jié)點(diǎn)的指針Public:/成員函數(shù) TreeNode_T(const T &data,TreeNode_T<T> *lchild=NULL, TreeNode_T<T> *rchild=NULL);T Data(void)const; TreeNode_T

8、<T>*& LeftChild(void); TreeNode_T<T>*& RightChild(void); .2 抽象數(shù)據(jù)類型BinaryTree_h用以實(shí)現(xiàn)二叉樹的操作，其定義如下：template<class T>class BinaryTree_T Public:BinaryTree_T(void); BinaryTree_T(const T &element); BinaryTree_T(const BinaryTree_T<T> &bt);BinaryTree_T(void);/賦值 BinaryT

9、ree_T<T>& operator=(const BinaryTree_T<T>& bt); TreeNode_T<T>* CopyBinaryTree(TreeNode_T<T>*ptr); /構(gòu)造二叉樹 Void MakeTree(constT&data,BinaryTree_T<T>&lhs, BinaryTree_T<T>&rhs); /前置條件:當(dāng)前樹為空 lhs rhs 不等 /后置條件:lhs rhs 為空/拆開二叉樹 Void BreakTree(T&dat

10、a,BinaryTree_T<T>&lhs, BinaryTree_T<T>&rhs);/前置條件:當(dāng)前樹非空,rhs lhs為空,且不等/后置條件:當(dāng)前樹指空 void PreOrder(void);/前序 void InOrder(void);/中序void PostOrder(void);/后序/清空 void Clear(void); /訪問節(jié)點(diǎn)void Visit(const TreeNode_T<T>*ptr);/得到樹的根結(jié)點(diǎn) TreeNode_T<T>* GetTreeNode(void);protected: /

11、樹的保護(hù)成員只想二叉樹節(jié)點(diǎn)的指針 TreeNode_T<T>* m_root;private:/樹的遍歷的私有成員函數(shù) void PreOrder(TreeNode_T<T>*ptr); void InOrder(TreeNode_T<T>*ptrvoid PostOrder(TreeNode_T<T>*ptr);void Clear(TreeNode_T<T>*ptr);.3 抽象數(shù)據(jù)類型HfmTree_h用以實(shí)現(xiàn)哈夫曼樹的操作，其定義如下： template<class W>class HfmTree_Tpublic:

12、 /幾種構(gòu)造函數(shù) HfmTree_T(void); HfmTree_T(const BinaryTree_T<int> &rhs); HfmTree_T(const HfmTree_T<W> &rhs); /析構(gòu)函數(shù)HfmTree_T(void); bool operator>(const HfmTree_T<W> &rhs)const; bool operator=(const HfmTree_T<W> &rhs)const; bool operator<(const HfmTree_T<W&g

13、t; &rhs)const; HfmTree_T<W>& operator=(const HfmTree_T<W> &rhs); /創(chuàng)建Hfm樹 void CreatHfmTree(void); operator W()const;/重載()運(yùn)算符 以得到勸值 /void ShowTree(void); /記錄頻率 void GetWeight(char c); /譯碼 void Code(char *&code);； int GetNumber(int x); int GetNumber(char c); void GenerateCo

14、de(void); void DeCode(void);private: void GenerateCode(BinaryTree_T<int> &P);void GenerateCode(TreeNode_T<int> *ptr,char *c,char *&code,int &count,int k,int lev); BinaryTree_T<int>m_tree; /哈夫曼樹的權(quán)值W m_weight;3調(diào)試報(bào)告 由于文件text.txt的內(nèi)容較多，結(jié)果造成程序運(yùn)的較慢，并造成部分的字母沒有被編碼。導(dǎo)致程序調(diào)試時(shí)間花費(fèi)較多，且

15、最后并沒很好的解決。 3.2 本程序有些代碼重復(fù)出現(xiàn)，從而減少了空間的利用率和增加了程序的雜亂性，特別是文件操作方面，如果可能的話，可以把文件的讀入讀出分別寫成一個(gè)函數(shù)，將會(huì)大大增強(qiáng)程序的可讀性。 3.3 算法的時(shí)空分析：此程序中使用了大量的指針，且是動(dòng)態(tài)申請(qǐng)，釋放內(nèi)存的，有效的利用了系統(tǒng)的空間，使程序執(zhí)行起來更高效。 3.4 本程序采用數(shù)據(jù)抽象的程序設(shè)計(jì)方法，將程序分為四個(gè)模塊，使得設(shè)計(jì)時(shí)思路清晰，實(shí)現(xiàn)時(shí)調(diào)試順利完成，各個(gè)模塊具有較好的可重用性，確實(shí)做到了一次良好的程序設(shè)計(jì)訓(xùn)練。 3.5 程序運(yùn)行結(jié)果如下： 在text.txt文檔中輸入要編碼的文件，結(jié)果程序順利把該文件中包含的字符編碼，并進(jìn)行了解碼，結(jié)果如下：4經(jīng)驗(yàn)和體會(huì)、通過實(shí)驗(yàn)更好的掌握了哈夫曼樹，并對(duì)哈夫曼樹有了深一步的了解、掌握了用get