哈弗曼編碼譯碼(C++實(shí)現(xiàn)).docx

1、數(shù)據(jù)結(jié)構(gòu)（ C+實(shí)現(xiàn)）實(shí)訓(xùn)報(bào)告題目：哈弗曼編碼與譯碼專業(yè)：信息管理班級：學(xué)生：吳昊翀學(xué)號： 1251220117指導(dǎo)老師：黃建燈1/16目錄一、實(shí)訓(xùn)要求3二、課題分析和設(shè)計(jì)31.基本需求分析32.對應(yīng)的結(jié)構(gòu)體或類4三、主要功能界面61. 主界面62.讀取文章并對字符編碼73.哈弗曼編碼信息74. 文章編碼8四、總結(jié)10五、附錄102/16一、實(shí)訓(xùn)要求輸入為：一段英文或中文的文章（原文）對輸入的文章構(gòu)造哈夫曼樹生成對應(yīng)的編碼輸出為：原文所對應(yīng)的編碼（譯文）根據(jù)已經(jīng)生成的編碼表，輸入任意的譯文可以得到對應(yīng)的原文二、課題分析和設(shè)計(jì)1. 基本需求分析1.在通信過程中，為了提高信道利用率，縮短信息傳輸時

2、間降低傳輸成本，需要一編碼譯碼器。2.此哈弗曼編碼譯碼器應(yīng)具有編碼譯碼的雙向功能，即在發(fā)送端通過編碼系統(tǒng)對傳入的數(shù)據(jù)進(jìn)行編碼。3.在接收端將數(shù)據(jù)譯碼，將具有兩項(xiàng)功能的編碼譯碼器用于雙工信道就可滿足，雙工信道的雙向編譯功能。4.輸入某段報(bào)文是，系統(tǒng)將自己完成編譯輸出。1.程序設(shè)計(jì)流程(1)文字表述開始進(jìn)入功能選擇界面，包含五種操作：1.讀取文章并對字符編碼。2.哈夫曼編碼信息。3.文章編碼。4.文章譯碼。5.退出程序。（2） 操作1：給定一篇文章，統(tǒng)計(jì)字符出現(xiàn)的概率，并根據(jù)概率建立哈弗曼樹，并利用哈弗曼樹對字符進(jìn)行哈弗曼編碼。2：顯示哈弗曼編碼信息，包括字符，字符出現(xiàn)的概率，哈弗曼編碼。3：對文

3、章進(jìn)行譯碼，顯示譯碼信息，并保存。4：對文章進(jìn)行譯碼，顯示并保存（3）流程圖程序開始3/16程序主界面讀取文章并對哈弗曼編碼文章編碼文章譯碼退出程序文章編碼信息顯 示 編保 存 編返 回 主顯示保 存 譯返回主界譯碼碼碼界面碼面2. 對應(yīng)的結(jié)構(gòu)體或類（ 1）定義class Htnote public:char name; /字符名double weight; / 權(quán)重int lchild; / 左孩子int rchild; / 右孩子int parent; / 父親Htnote() weight = 0;lchild = -1;parent = -1;rchild = -1;（2）定義字符和出

4、現(xiàn)的次數(shù)class Name public:int num; / 字符出現(xiàn)的次數(shù)char pname; /字符名double lweight; / 權(quán)值4/16Name() num = 0;lweight = 0;（3）定義字符種類總數(shù)和存儲信息class GetName public:char namefmax2;int n; / 字符的種類int sum; / 字符的總數(shù)Name lettermax1; / 存儲字符信息的類的數(shù)組GetName() sum = 0;n = 0;（4）定義編碼類class CodeNode/編碼類public:char ch; /存儲字符char bitsm

5、ax1; / 存儲編碼;class Function public:GetName L;int fn; / 定義哈夫曼數(shù)組大小Htnote HuffmanTmax3; /哈夫曼數(shù)組CodeNode Codemax1; / 字符編碼數(shù)組Function() fn = 0;5/16三、主要功能界面1. 主界面6/162. 讀取文章并對字符編碼3. 哈弗曼編碼信息7/164. 文章編碼8/165. 文章譯碼9/16四、總結(jié)為期兩個星期的課程設(shè)計(jì)終于完美落下帷幕，回想起前前后后還是有苦有甜。當(dāng)拿到課題是感覺還行！ 結(jié)果前幾天做程序的代碼時一點(diǎn)都不會做， 課本也看不懂課程進(jìn)度可以說是原地踏步！ 只能怪自

6、己吧！老師講的有時能聽懂有時就聽不懂，到頭來今天的局面，當(dāng)時以為自己完成不了任務(wù)。過程中甜的是有老師和同學(xué)的幫忙，總算圓滿完成任務(wù)。通過本次實(shí)訓(xùn)讓我重新學(xué)習(xí)了算法和數(shù)據(jù)結(jié)構(gòu)這門課程， 也懂得了用代碼來建立哈弗曼樹， 編碼譯碼雙向功能 !上機(jī)實(shí)驗(yàn)， 將理論的知識與實(shí)際結(jié)合起來。 增強(qiáng)了自己的動手能力， 覺的任何知識都不是輕而易舉的學(xué)懂， 必須花點(diǎn)心思去學(xué)， 必須要付出努力。以后上課就不能像以前那樣，要好好學(xué)習(xí)這樣不辜負(fù)老師對我們的心意。 最后衷心感謝幫助我完成程序設(shè)計(jì)的老師和同學(xué)表示感謝！五、附錄10/16全部代碼：#ifndef HUFFMANFUNCTION_H#defineHUFFMANF

7、UNCTION_H#include <cstdlib>#include<iostream>#include<fstream>#include<math.h>#define max1 150#define max2 50#define max3 256using namespace std;class Htnote public:char name; /字符名double weight; / 權(quán)重int lchild; / 左孩子int rchild; / 右孩子int parent; / 父親Htnote() weight = 0;lchild

8、= -1;parent = -1;rchild = -1;class Name public:int num; / 字符出現(xiàn)的次數(shù)char pname; /字符名double lweight; / 權(quán)值Name() num = 0;lweight = 0;class GetName public:char namefmax2;int n; / 字符的種類int sum; / 字符的總數(shù)Name lettermax1; / 存儲字符信息的類的數(shù)組GetName() sum = 0;n = 0;void GetWeight()/ 得到字符的權(quán)值11/16for (int i = 0; i <

9、 n; i+) letteri.lweight = (double) letteri.num / sum; /出現(xiàn)的次數(shù)除總數(shù)得到權(quán)值int ReadLetter() ifstream input;cout << " 請輸入文件名：" << endl;cin >> namef;input.open(namef); / 打開文件if (input.fail() cout << " 該文件不存在！" << endl;return 0;char ch;ch = input.get();letter0.

10、pname = ch;letter0.num+;sum+;while (!input.eof() /讀取文件中的所有字符int tag = 0;ch = input.get();for (int i = 0; i < n + 1; i+) if (letteri.pname = ch) letteri.num+;sum+;tag = 1;if (tag = 0) n+;lettern.pname = ch;lettern.num+;sum+;sum-;input.close();GetWeight(); / 得到字符權(quán)值;class CodeNode/編碼類public:char ch;

11、 /存儲字符char bitsmax1; / 存儲編碼;class Function public:GetName L;int fn; / 定義哈夫曼數(shù)組大小Htnote HuffmanTmax3; /哈夫曼數(shù)組CodeNode Codemax1; / 字符編碼數(shù)組12/16Function() fn = 0;void CharHuffmanTCoding()/編碼功能實(shí)現(xiàn)int i, f, c;char cd1000; / 暫時存儲編碼的數(shù)組int start; / 編碼讀取起始位置cdL.n = '0'for (i = 0; i < L.n; i+) Codei.ch

12、 = HuffmanT; /字符信息start = L.n; / 起始位置c = i;while (f = HuffmanTc.parent) >= 0) if (HuffmanTf.lchild = c)/如果為左孩子，為'0'cd-start = '0' else/ 如果為右孩子，為 '1'cd-start = '1'c = f;strcpy(Codei.bits, &cdstart); /將結(jié)果存入對應(yīng)的編碼數(shù)組中void OutputHuffmanTCode() cout << &qu

13、ot; 哈夫曼編碼： " << endl;cout << "-" << endl;cout << " 字符 t 權(quán)值 tt 哈夫曼編碼" << endl;for (int i = 0; i < L.n; i+)/輸出字符，權(quán)值，哈夫曼編碼cout << "-" << endl;cout << HuffmanT << "t" << HuffmanTi.weight <

14、;< "t"cout << Codei.bits;cout << endl;cout << "-" << endl;void InitHT()/ 哈夫曼初始化L.ReadLetter();fn = (L.n)*2 - 1;for (int i = 0; i < fn; i+) if (i < L.n) HuffmanT = L.letteri.pname;HuffmanTi.weight = L.letteri.lweight;void SelectMin(int m, int

15、 &p1, int &p2)/選擇最小的兩個節(jié)點(diǎn)13/16int i, j;double m1, m2;m1 = m2 = 1;p1 = p2 = -1;for (i = 0; i < m; i+) if (HuffmanTi.parent = -1 && HuffmanTi.weight < m1)/找出為訪問過的最小權(quán)值節(jié)點(diǎn)m2 = m1;p2 = p1;m1 = HuffmanTi.weight;p1 = i; else if (HuffmanTi.parent = -1 && HuffmanTi.weight < m2)

16、/找出為訪問的權(quán)值第二小結(jié)點(diǎn)m2 = HuffmanTi.weight;p2 = i;void CreatHT()/ 建立哈夫曼樹int i, p1, p2;InitHT();for (i = L.n; i < fn; i+) SelectMin(i, p1, p2);HuffmanTp1.parent = HuffmanTp2.parent = i;HuffmanTi.lchild = p1;HuffmanTi.rchild = p2;HuffmanTi.weight = HuffmanTp1.weight + HuffmanTp2.weight;int OutArticleCode(

17、)/ 顯示文章編碼/ 文章編碼操作ifstream input;input.open(L.namef);if (input.fail() cout << " 文件不存在！" << endl;return 0;char ch;cout << " 文章編碼如下：" << endl;while (!input.eof() ch = input.get();for (int i = 0; i < L.n; i+) if (Codei.ch = ch)cout << Codei.bits;cout

18、<< endl;input.close();14/16int SaveArticleCode()/ 保存文章編碼ofstream output;ifstream input;char namef1max2;input.open(L.namef);if (input.fail() cout << " 該文件不存在！" << endl;return 0;cout << " 請輸入保存文章編碼的文件名：" << endl;cin >> namef1;output.open(namef1);

19、char ch;while (!input.eof() ch = input.get();for (int i = 0; i < L.n; i+) if (Codei.ch = ch) for (int j = 0; j < strlen(Codei.bits); j+) output.put(Codei.bitsj);input.close();output.close();cout << " 保存完畢！ " << endl;int OutTransCode() / 文章譯碼操作ifstream input;char namefmax2

20、;cout << " 請輸入保存文章編碼的文件名：" << endl;cin >> namef;input.open(namef);if (input.fail() cout << " 該文件不存在！" << endl;return 0;char ch;ch = input.get();int c = 2 * L.n - 2;while (!input.eof() if (ch = '0')/ 遇 0 搜索左子樹if (HuffmanTc.lchild >= 0) c =

21、HuffmanTc.lchild;if (HuffmanTc.lchild = -1)/判斷是否到葉子cout << HuffmanT; /輸出字符c = 2 * L.n - 2; / 返回根節(jié)點(diǎn)if (ch = '1')/ 遇 1 搜索右子樹15/16if (HuffmanTc.rchild >= 0) c = HuffmanTc.rchild;if (HuffmanTc.rchild = -1)/判斷是否到葉子cout << HuffmanT; /輸出字符c = 2 * L.n - 2; / 返回根節(jié)點(diǎn)ch = input.get();cout << endl;input.close();#endif/* HUF