1、建立Huffman樹進(jìn)行編碼和譯碼的設(shè)計(jì) 郝萌 1100300423 哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 1003104班摘要：建立一個(gè)簡(jiǎn)易的系統(tǒng)，對(duì)于給定的一篇英文文章，統(tǒng)計(jì)字符出 現(xiàn)的概率，并根據(jù)概率建立Huffman樹，利用Huffman編碼 對(duì)文章進(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)而可以利用哈夫曼編碼對(duì)文章2. 程序設(shè)計(jì)流程 (1)文字表

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

3、并對(duì)字符進(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 #include#include#include#define max1 150#define m

4、ax2 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)的次數(shù) char pname; /字符名 double lweight; /權(quán)值 Name() num = 0; l

5、weight = 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)的次數(shù)除總數(shù)得到權(quán)值 int ReadLetter() ifstream input; cout 請(qǐng)輸入文件名： namef;

6、input.open(namef); /打開文件 if (input.fail() cout 該文件不存在！ endl; return 0; 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+;

7、lettern.pname = ch; lettern.num+; sum+; sum-; input.close(); GetWeight(); /得到字符權(quán)值 ;class CodeNode/編碼類public: char ch; /存儲(chǔ)字符 char bitsmax1; /存儲(chǔ)編碼;class Function public: GetName L; int fn; /定義哈夫曼數(shù)組大小 Htnote HuffmanTmax3; /哈夫曼數(shù)組 CodeNode Codemax1; /字符編碼數(shù)組 Function() fn = 0; void CharHuffmanTCoding()/編碼

8、功能實(shí)現(xiàn) int i, f, c; char cdL.n + 1; /暫時(shí)存儲(chǔ)編碼的數(shù)組 int start; /編碼讀取起始位置 cdL.n = 0; for (i = 0; i = 0) if (HuffmanTf.lchild = c)/如果為左孩子，為0 cd-start = 0; else/如果為右孩子，為1 cd-start = 1; c = f; strcpy(Codei.bits, &cdstart); /將結(jié)果存入對(duì)應(yīng)的編碼數(shù)組中 void OutputHuffmanTCode() cout 哈夫曼編碼： endl; cout endl; cout 字符t權(quán)值tt哈夫曼編碼

9、endl; for (int i = 0; i L.n; i+)/輸出字符，權(quán)值，哈夫曼編碼 cout endl; cout HuffmanT 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; HuffmanTi.weight = L.letteri.lweigh

10、t; void SelectMin(int m, int &p1, int &p2)/選擇最小的兩個(gè)節(jié)點(diǎn) 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é)點(diǎn) m2 = m1; p2 = p1; m1 = HuffmanTi.weight; p1 = i; else if (HuffmanTi.parent = -1 & HuffmanTi.weight m2)/找出為訪問的權(quán)值

11、第二小結(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()/顯示

12、文章編碼 /文章編碼操作 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 endl; input.close(); int SaveArticleCode()/保存文章編碼 ofstream output; ifst

13、ream input; char namef1max2; input.open(L.namef); if (input.fail() cout 該文件不存在！ endl; return 0; cout 請(qǐng)輸入保存文章編碼的文件名： 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.bit

14、sj); input.close(); output.close(); cout 保存完畢！ endl; int OutTransCode() /文章譯碼操作 ifstream input; char namefmax2; cout 請(qǐng)輸入保存文章編碼的文件名： namef; input.open(namef); if (input.fail() cout 該文件不存在！ = 0) c = HuffmanTc.lchild; if (HuffmanTc.lchild = -1)/判斷是否到葉子 cout = 0) c = HuffmanTc.rchild; if (HuffmanTc.rchi

15、ld = -1)/判斷是否到葉子 cout HuffmanT; /輸出字符 c = 2 * L.n - 2; /返回根節(jié)點(diǎn) ch = input.get(); cout endl; input.close(); int SaveTransCode() /保存文章譯碼 ofstream output; ifstream input; char namefmax2; char namef1max2; cout 請(qǐng)輸入文章編碼所在的文件名： namef; input.open(namef); if (input.fail() cout 該文件不存在！ endl; return 0; co

16、ut 請(qǐng)輸入保存文章譯碼的文件名： 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 = 2 * L.n - 2; if (ch = 1) if (HuffmanTc.rchild = 0) c = HuffmanTc.r

17、child; if (HuffmanTc.rchild = -1) output.put(HuffmanT); c = 2 * L.n - 2; ch = input.get(); input.close(); output.close(); cout 保存完畢！ endl; int FileCompression() /文件壓縮功能 CreatHT(); CharHuffmanTCoding(); /保存編碼 ofstream output; ifstream input; char namef1 = temp.txt; input.open(L.namef); if (inpu

18、t.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.ch = ch) for (int j = 0; j strlen(Codei.bits); j+) output.put(Codei.bitsj); input.close(); output.close(); /壓縮文件 ofstream File1; ifstream File2; char namef2m

19、ax2; cout 請(qǐng)輸入壓縮后的文件名： namef2; File1.open(namef2); File2.open(namef1); if (File2.fail() cout 該文件不存在！ 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+;

20、 if (i = 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 namef2max2; char namef1 = temp.t

21、xt; cout 請(qǐng)輸入待解壓縮的文件名： 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(reinterpret_cast (&ch), sizeof (ch); char sh; char th = ch; input.read(reinterpret_cast (&ch), sizeof (ch); int count; c

22、har num; char t = 0; char p = 1; while (!input.eof() sh = th; th = ch; input.read(reinterpret_cast (&ch), sizeof (ch); count = sh; if (ch != EOF) for (int i = 0; i 7; i+) num = count % 2 + 0; output.write(reinterpret_cast (&num), sizeof (num); count = count / 2; if (ch = EOF) for (int i = 0; i 7; i+

23、) num = count % 2 + 0; output.write(reinterpret_cast (&num), sizeof (num); count = count / 2; if (count = 0) break; for (int i = 0; i th - 0; i+) output.write(reinterpret_cast (&t), sizeof (t); output.close(); input.close(); /解壓文件 fstream File1; fstream File2; char namef3max2; cout 請(qǐng)輸入解壓后的文件名： namef

24、3; 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 (&ch), sizeof (ch); int c = 2 * L.n - 2; while (!File2.eof() if (ch = 0) if (HuffmanTc.lchild = 0) c = HuffmanTc.lchild; if (HuffmanTc.lchil

25、d = -1) cout HuffmanT; File1.write(reinterpret_cast (&HuffmanT), sizeof (HuffmanT); c = 2 * L.n - 2; if (ch = 1) if (HuffmanTc.rchild = 0) c = HuffmanTc.rchild; if (HuffmanTc.rchild = -1) cout HuffmanT; File1.write(reinterpret_cast (&HuffmanT), sizeof (HuffmanT);

26、c = 2 * L.n - 2; File2.read(reinterpret_cast (&ch), sizeof (ch); cout endl; File2.close(); File1.close(); remove(namef1); cout 解壓完畢！ endl; ;#endif/* HUFFMANFUNCTION_H */=/* * File: main.cpp * Author: Administrator * * Created on 2011年12月13日, 上午9:09 */#include #include HUFFMANFUNCTION.husing namespac

27、e std;/* * */int main(int argc, char* argv) Function *a = new Function; while (1) /主界面顯示 cout endl endl endl; cout endl; cout 【1】讀取文章并對(duì)字符編碼 endl; cout 【2】哈夫曼編碼信息 endl; cout 【3】文章編碼 endl; cout 【4】文章譯碼 endl; cout 【5】壓縮文件 endl; cout 【6】解壓縮文件 endl; cout 【7】退出程序 endl; cout = endl endl; char ch; cout 請(qǐng)選擇功

28、能： ; cin ch; switch (ch) case 1:/讀取文章并對(duì)字符編碼 delete a; a = new Function; system(cls); a-CreatHT(); a-CharHuffmanTCoding(); cout 操作完畢！ OutputHuffmanTCode(); system(pause); system(cls); break; case 3:/文章編碼 system(cls); while (1) cout endl; cout 1.顯示文章編碼 endl; cout 2.保存文章編碼 endl; cout 3.返回上一界面 endl; char ch1; co