哈夫曼編碼與譯碼(附源碼)

1、建立Huffman樹進(jìn)行編碼和譯碼的設(shè)計(jì) 李香蘭 2015548947 哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 1501班摘要：建立一個(gè)簡易的系統(tǒng)，對于給定的一篇英文文章，統(tǒng)計(jì)字符出 現(xiàn)的概率，并根據(jù)概率建立Huffman樹，利用Huffman編碼 對文章進(jìn)行編碼和譯碼。掌握Huffman樹的建立與應(yīng)用，并進(jìn) 一步熟練掌握程序的設(shè)計(jì)流程。關(guān)鍵詞：Huffman樹 Huffman編碼 文章譯碼 文件壓縮 解壓縮1. 引言： 給定一篇文章，統(tǒng)計(jì)字符出現(xiàn)的概率，根據(jù)概率建立哈夫曼樹，并進(jìn)行哈夫曼編碼，進(jìn)而可以利用哈夫曼編碼對文章進(jìn)行編碼與譯碼和文件壓縮、解壓縮等操作。2. 程序設(shè)計(jì)流程 (1)文字表述開

2、始進(jìn)入功能選擇界面，包含五種操作：1.讀取文章并對字符編碼，2.哈夫曼編碼信息，3.文章編碼，4.文章譯碼，5.文件壓縮，6.文件解壓縮，7.退出程序。操作1：給定一篇文章，統(tǒng)計(jì)字符出現(xiàn)的概率，并根據(jù)概率建立Huffman樹，并利用Huffman樹對字符進(jìn)行Huffman編碼。操作2：顯示Huffman編碼信息，包括字符，字符出現(xiàn)的概率，Huffman編碼。操作3：對文章進(jìn)行譯碼，顯示譯碼信息，并保存。操作4：對文章進(jìn)行譯碼，顯示并保存。操作5：對文件進(jìn)行壓縮，每7位二進(jìn)制序列對應(yīng)一個(gè)ASCII碼。操作6：對文件進(jìn)行解壓縮。（2） 流程圖 （3） 程序數(shù)據(jù)要求及功能實(shí)現(xiàn) 主界面1.讀取文件并對

3、字符進(jìn)行編碼2.哈夫曼編碼信息3.文件編碼（1） 顯示文件編碼 （2） 保存文件編碼 4.文件譯碼（1） 顯示文章編碼的譯碼 （2） 保存文章編碼的譯碼 5. 文件壓縮 6. 文件解壓縮附：程序源代碼 /* * File: HUFFMANFUNCTION.h * Author: Administrator * * Created on 2011年12月19日, 下午6:19 */#ifndef HUFFMANFUNCTION_H#defineHUFFMANFUNCTION_H#include <cstdlib>#include<iostream>#include<

4、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 = -1; parent = -1; rchild = -1; ;class Name public: int num; /字符出現(xiàn)

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

6、次數(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.pname = ch; letter0.num+; sum+; while (!input.eof()

7、 /讀取文件中的所有字符 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; /存儲(chǔ)字符 char bitsmax1; /存儲(chǔ)編碼;class F

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

9、 = 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 << "哈夫曼編碼：" << endl; cout <<

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

11、ut << 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 &p1, int &p2)/選擇最小的兩個(gè)節(jié)點(diǎn) int i, j

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

13、 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()/顯示文章編碼 /文章編碼操作 ifstream i

14、nput; 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 << endl; input

15、.close(); int 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); char ch; while (

16、!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; cout <

17、< "請輸入保存文章編碼的文件名：" << 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 = Huffma

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

19、; cout << endl; input.close(); int SaveTransCode() /保存文章譯碼 ofstream output; ifstream input; char namefmax2; char namef1max2; cout << "請輸入文章編碼所在的文件名：" << endl; cin >> namef; input.open(namef); if (input.fail() cout << "該文件不存在！" << endl; return 0

20、; cout << "請輸入保存文章譯碼的文件名：" << endl; cin >> namef1; output.open(namef1); char ch; ch = input.get(); int c = 2 * L.n - 2; while (!input.eof() if (ch = '0') if (HuffmanTc.lchild >= 0) c = HuffmanTc.lchild; if (HuffmanTc.lchild = -1) output.put(HuffmanT); c =

21、 2 * L.n - 2; if (ch = '1') if (HuffmanTc.rchild >= 0) c = HuffmanTc.rchild; if (HuffmanTc.rchild = -1) output.put(HuffmanT); c = 2 * L.n - 2; ch = input.get(); input.close(); output.close(); cout << "保存完畢！" << endl; int FileCompression() /文件壓縮功能 CreatHT(); Cha

22、rHuffmanTCoding(); /保存編碼 ofstream output; ifstream input; char namef1 = "temp.txt" input.open(L.namef); if (input.fail() cout << "該文件不存在！" << endl; return 0; output.open(namef1); char ch; while (!input.eof() ch = input.get(); for (int i = 0; i < L.n; i+) if (Codei.

23、ch = ch) for (int j = 0; j < strlen(Codei.bits); j+) output.put(Codei.bitsj); input.close(); output.close(); /壓縮文件 ofstream File1; ifstream File2; char namef2max2; cout << "請輸入壓縮后的文件名：" << endl; cin >> namef2; File1.open(namef2); File2.open(namef1); if (File2.fail() co

24、ut << "該文件不存在！" << endl; return 0; char sh; char th; int i = 0; char j = '0' int count = 0; while (!File2.eof() sh = File2.get(); if (i < 7 && sh != EOF) count = count + (sh - '0') * pow(2, i); if (sh = '0') j+; else j = '0' i+; if (i

25、= 7) th = count; File1.put(th); i = 0; count = 0; if (sh = EOF) th = count; File1.put(th); File1.put(j); i = 0; count = 0; File1.close(); File2.close(); remove(namef1); cout << "文件壓縮完畢！" << endl; int FileDecompression() /文件解壓縮 /保存編碼 fstream output; fstream input; char namef2max

26、2; char namef1 = "temp.txt" cout << "請輸入待解壓縮的文件名：" << endl; cin >> namef2; input.open(namef2, ios:in | ios:binary); output.open(namef1, ios:out | ios:binary); if (input.fail() cout << "該文件不存在！" << endl; return 0; char ch; input.read(reinter

27、pret_cast<char*> (&ch), sizeof (ch); char sh; char th = ch; input.read(reinterpret_cast<char*> (&ch), sizeof (ch); int count; char num; char t = '0' char p = '1' while (!input.eof() sh = th; th = ch; input.read(reinterpret_cast<char*> (&ch), sizeof (ch);

28、 count = sh; if (ch != EOF) for (int i = 0; i < 7; i+) num = count % 2 + '0' output.write(reinterpret_cast<char*> (&num), sizeof (num); count = count / 2; if (ch = EOF) for (int i = 0; i < 7; i+) num = count % 2 + '0' output.write(reinterpret_cast<char*> (&n

29、um), sizeof (num); count = count / 2; if (count = 0) break; for (int i = 0; i < th - '0' i+) output.write(reinterpret_cast<char*> (&t), sizeof (t); output.close(); input.close(); /解壓文件 fstream File1; fstream File2; char namef3max2; cout << "請輸入解壓后的文件名：" <<

30、endl; cin >> namef3; File2.open(namef1, ios:in | ios:binary); File1.open(namef3); if (File2.fail() cout << "該文件不存在！" << endl; return 0; cout << "解壓后的文件內(nèi)容為：" << endl; File2.read(reinterpret_cast<char*> (&ch), sizeof (ch); int c = 2 * L.n - 2

31、; while (!File2.eof() if (ch = '0') if (HuffmanTc.lchild >= 0) c = HuffmanTc.lchild; if (HuffmanTc.lchild = -1) cout << HuffmanT; File1.write(reinterpret_cast<char*> (&HuffmanT), sizeof (HuffmanT); c = 2 * L.n - 2; if (ch = '1') if (HuffmanTc.rchi

32、ld >= 0) c = HuffmanTc.rchild; if (HuffmanTc.rchild = -1) cout << HuffmanT; File1.write(reinterpret_cast<char*> (&HuffmanT), sizeof (HuffmanT); c = 2 * L.n - 2; File2.read(reinterpret_cast<char*> (&ch), sizeof (ch); cout << endl; File2.close(); Fi

33、le1.close(); remove(namef1); cout << "解壓完畢！" << endl; ;#endif/* HUFFMANFUNCTION_H */=/* * File: main.cpp * Author: Administrator * * Created on 2011年12月13日, 上午9:09 */#include <iostream>#include "HUFFMANFUNCTION.h"using namespace std;/* * */int main(int argc, cha

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

35、 【3】文章編碼 " << endl; cout << " 【4】文章譯碼 " << endl; cout << " 【5】壓縮文件 " << endl; cout << " 【6】解壓縮文件 " << endl; cout << " 【7】退出程序 " << endl; cout << "=" << endl << endl; char ch

36、; cout << "=>>請選擇功能： " cin >> ch; switch (ch) case '1':/讀取文章并對字符編碼 delete a; a = new Function; system("cls"); a->CreatHT(); a->CharHuffmanTCoding(); cout << "操作完畢！" << endl; system("pause"); system("cls");

37、break; case '2':/哈夫曼編碼信息 system("cls"); a->OutputHuffmanTCode(); system("pause"); system("cls"); break; case '3':/文章編碼 system("cls"); while (1) cout << endl; cout << "=>>1.顯示文章編碼" << endl; cout << &quo

38、t;=>>2.保存文章編碼" << endl; cout << "=>>3.返回上一界面" << endl; char ch1; cout << endl << "=>>請選擇功能：" 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; case '3':/返回上一界面 break; default: system("cls"); cout << "輸入錯(cuò)誤，請重新輸入