哈弗曼編碼譯碼(C++實現(xiàn))

1、 數(shù)據(jù)結(jié)構(gòu)（C+實現(xiàn)） 實訓(xùn)報告題 目：哈弗曼編碼與譯碼專 業(yè)： 信息管理 班 級： 12512201 學(xué) 生： 吳昊翀 學(xué) 號： 1251220117 指導(dǎo)老師： 黃建燈 目錄一、實訓(xùn)要求4二、課題分析和設(shè)計41. 基本需求分析42. 對應(yīng)的結(jié)構(gòu)體或類5三、主要功能界面71.主界面72. 讀取文章并對字符編碼83. 哈弗曼編碼信息94.文章編碼10四、 總結(jié)12五、附錄13一、實訓(xùn)要求n 輸入為：一段英文或中文的文章（原文）n 對輸入的文章構(gòu)造哈夫曼樹n 生成對應(yīng)的編碼n 輸出為：原文所對應(yīng)的編碼（譯文）n 根據(jù)已經(jīng)生成的編碼表，輸入任意的譯文可以得到對應(yīng)的原文二、課題分析和設(shè)計1. 基本需

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

3、行哈弗曼編碼。 2：顯示哈弗曼編碼信息，包括字符，字符出現(xiàn)的概率，哈弗曼編碼。 3：對文章進(jìn)行譯碼，顯示譯碼信息，并保存。 4：對文章進(jìn)行譯碼，顯示并保存 （3）流程圖 程序開始程序主界面哈弗曼編碼信息讀取文章并對文章編碼退出程序文章譯碼文章編碼保存譯碼顯示譯碼返回主界面返回主界面保存編碼顯示編碼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 =

4、 -1; parent = -1; rchild = -1; ; （2）定義字符和出現(xiàn)的次數(shù)class Name public: int num; /字符出現(xiàn)的次數(shù) char pname; /字符名 double lweight; /權(quán)值 Name() 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） 定義編碼類c

5、lass CodeNode/編碼類public: char ch; /存儲字符 char bitsmax1; /存儲編碼;class Function public: GetName L; int fn; /定義哈夫曼數(shù)組大小 Htnote HuffmanTmax3; /哈夫曼數(shù)組 CodeNode Codemax1; /字符編碼數(shù)組 Function() fn = 0; 三、主要功能界面1.主界面2. 讀取文章并對字符編碼3. 哈弗曼編碼信息4.文章編碼5.文章譯碼4、 總結(jié) 為期兩個星期的課程設(shè)計終于完美落下帷幕，回想起前前后后還是有苦有甜。當(dāng)拿到課題是感覺還行！結(jié)果前幾天做程序的代碼時一

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

7、_H#defineHUFFMANFUNCTION_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()

8、 weight = 0; lchild = -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()/得到

9、字符的權(quán)值 for (int i = 0; i < 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;

10、char ch; ch = input.get(); letter0.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(); GetWe

11、ight(); /得到字符權(quán)值 ;class CodeNode/編碼類public: char ch; /存儲字符 char bitsmax1; /存儲編碼;class Function public: GetName L; int fn; /定義哈夫曼數(shù)組大小 Htnote HuffmanTmax3; /哈夫曼數(shù)組 CodeNode Codemax1; /字符編碼數(shù)組 Function() fn = 0; void CharHuffmanTCoding()/編碼功能實現(xiàn) int i, f, c; char cd1000; /暫時存儲編碼的數(shù)組 int start; /編碼讀取起始位置 cdL

12、.n = '0' for (i = 0; i < L.n; i+) Codei.ch = 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);

13、/將結(jié)果存入對應(yīng)的編碼數(shù)組中 void OutputHuffmanTCode() cout << "哈夫曼編碼：" << endl; cout << "-" << endl; cout << "字符t權(quán)值tt哈夫曼編碼 " << endl; for (int i = 0; i < L.n; i+)/輸出字符，權(quán)值，哈夫曼編碼 cout << "-" << endl; cout << HuffmanTi.

14、name << "t" << HuffmanTi.weight << "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

15、; HuffmanTi.weight = L.letteri.lweight; void SelectMin(int m, int &p1, int &p2)/選擇最小的兩個節(jié)點 int 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é)點 m2 = m1; p2 = p1; m1 = HuffmanTi.weight; p1 = i

16、; else if (HuffmanTi.parent = -1 && HuffmanTi.weight < m2)/找出為訪問的權(quán)值第二小結(jié)點 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

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

18、(); for (int i = 0; i < L.n; i+) if (Codei.ch = ch) cout << Codei.bits; cout << endl; input.close(); int SaveArticleCode()/保存文章編碼 ofstream output; ifstream input; char namef1max2; input.open(L.namef); if (input.fail() cout << "該文件不存在！" << endl; return 0; cout <

19、;< "請輸入保存文章編碼的文件名：" << endl; cin >> namef1; output.open(namef1); 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 <

20、< "保存完畢！" << endl; int OutTransCode() /文章譯碼操作 ifstream input; char namefmax2; cout << "請輸入保存文章編碼的文件名：" << endl; cin >> namef; input.open(namef); if (input.fail() cout << "該文件不存在！" << endl; return 0; char ch; ch = input.get(); int c

21、 = 2 * L.n - 2; while (!input.eof() if (ch = '0')/遇0搜索左子樹 if (HuffmanTc.lchild >= 0) c = HuffmanTc.lchild; if (HuffmanTc.lchild = -1)/判斷是否到葉子 cout << HuffmanT; /輸出字符 c = 2 * L.n - 2; /返回根節(jié)點 if (ch = '1')/遇1搜索右子樹 if (HuffmanTc.rchild >= 0) c = HuffmanTc.rchild; if (H

22、uffmanTc.rchild = -1)/判斷是否到葉子 cout << HuffmanT; /輸出字符 c = 2 * L.n - 2; /返回根節(jié)點 ch = input.get(); cout << endl; input.close(); ;#endif/* HUFFMANFUNCTION_H */#include <iostream>#include "HUFFMANFUNCTION.h"using namespace std;int main(int argc, char* argv) Function *a =

23、 new Function; while (1) /主界面顯示 cout << endl << endl << endl; cout << "<<=功 能 選 擇=>>" << endl; cout << " 【1】讀取文章并對字符編碼 " << endl; cout << " 【2】哈夫曼編碼信息 " << endl; cout << " 【3】文章編碼 " <&l

24、t; endl; cout << " 【4】文章譯碼 " << endl; cout << " 【5】退出程序 " << endl; cout << "=" << endl << endl; char ch; cout << "=>>請選擇功能： " cin >> ch; switch (ch) case '1':/讀取文章并對字符編碼 delete a; a = new Func

25、tion; system("cls"); a->CreatHT(); a->CharHuffmanTCoding(); cout << "操作完畢！" << endl; system("pause"); system("cls"); break; case '2':/哈夫曼編碼信息 system("cls"); a->OutputHuffmanTCode(); system("pause"); system("

26、;cls"); break; case '3':/文章編碼 system("cls"); while (1) cout << endl; cout << "=>>1.顯示文章編碼" << endl; cout << "=>>2.保存文章編碼" << endl; cout << "=>>3.返回上一界面" << endl; char ch1; cout << e

27、ndl << "=>>請選擇功能：" cin >> ch1; switch (ch1) case '1':/顯示文章編碼 system("cls"); a->OutArticleCode(); system("pause"); system("cls"); continue; case '2':/保存文章編碼 system("cls"); a->SaveArticleCode(); system("pause"); system("cls"); continue