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

《哈夫曼編碼與譯碼(附源碼)》由會(huì)員分享，可在線閱讀，更多相關(guān)《哈夫曼編碼與譯碼(附源碼)（23頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-----傾情為你奉上 建立Huffman樹進(jìn)行編碼和譯碼的設(shè)計(jì) 郝萌 哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 班 摘要：建立一個(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ì)

2、字符出現(xiàn)的概率，根據(jù)概率建立哈夫曼樹，并進(jìn)行哈夫曼編碼，進(jìn)而可以利用哈夫曼編碼對(duì)文章進(jìn)行編碼與譯碼和文件壓縮、解壓縮等操作。 2. 程序設(shè)計(jì)流程 (1)文字表述 開始進(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)行譯碼

3、，顯示并保存。操作5：對(duì)文件進(jìn)行壓縮，每7位二進(jìn)制序列對(duì)應(yīng)一個(gè)ASCII碼。操作6：對(duì)文件進(jìn)行解壓縮。 （2） 流程圖 （3） 程序數(shù)據(jù)要求及功能實(shí)現(xiàn) 主界面 1.讀取文件并對(duì)字符進(jìn)行編碼 2.哈夫曼編碼信息 3.文件編碼 （1） 顯示文件編碼 （2） 保存文件編碼 4.文件譯碼 （1） 顯示文章編碼的譯碼 （2） 保存文章編碼的譯碼 5. 文件壓縮 6. 文

4、件解壓縮 附：程序源代碼 /* * File: HUFFMANFUNCTION.h * Author: Administrator * * Created on 2011年12月19日, 下午6:19 */ #ifndef HUFFMANFUNCTION_H #define HUFFMANFUNCTION_H #include #include #include #include #define max1 150 #define max2 50 #de

5、fine max3 256 using 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; } }; cla

6、ss Name { public: int num; //字符出現(xiàn)的次數(shù) char pname; //字符名 double lweight; //權(quán)值 Name() { num = 0; lweight = 0; } }; class GetName { public: char namef[max2]; int n; //字符的種類 int sum; //字符的總數(shù) Name letter[max1]; //存儲(chǔ)字符信息的類的數(shù)組 Get

7、Name() { sum = 0; n = 0; } void GetWeight()//得到字符的權(quán)值 { for (int i = 0; i < n; i++) { letter[i].lweight = (double) letter[i].num / sum; //出現(xiàn)的次數(shù)除總數(shù)得到權(quán)值 } } int ReadLetter() { ifstream input; cout << "請(qǐng)輸入文件名

8、： " << endl; cin >> namef; input.open(namef); //打開文件 if (input.fail()) { cout << "該文件不存在！" << endl; return 0; } char ch; ch = input.get(); letter[0].pname = ch; letter[0].num++; sum++;

9、 while (!input.eof()) {//讀取文件中的所有字符 int tag = 0; ch = input.get(); for (int i = 0; i < n + 1; i++) { if (letter[i].pname == ch) { letter[i].num++; sum++; tag = 1; }

10、 } if (tag == 0) { n++; letter[n].pname = ch; letter[n].num++; sum++; } } sum--; input.close(); GetWeight(); //得到字符權(quán)值 } }; class CodeNode//編碼類 { p

11、ublic: char ch; //存儲(chǔ)字符 char bits[max1]; //存儲(chǔ)編碼 }; class Function { public: GetName L; int fn; //定義哈夫曼數(shù)組大小 Htnote HuffmanT[max3]; //哈夫曼數(shù)組 CodeNode Code[max1]; //字符編碼數(shù)組 Function() { fn = 0; } void CharHuffmanTCoding()//編碼功能實(shí)現(xiàn) {

12、 int i, f, c; char cd[L.n + 1]; //暫時(shí)存儲(chǔ)編碼的數(shù)組 int start; //編碼讀取起始位置 cd[L.n] = '\0'; for (i = 0; i < L.n; i++) { Code[i].ch = HuffmanT[i].name; //字符信息 start = L.n; //起始位置 c = i; while ((f = HuffmanT[c].parent) >=

13、0) { if (HuffmanT[f].lchild == c)//如果為左孩子，為‘0’ { cd[--start] = '0'; } else//如果為右孩子，為‘1’ { cd[--start] = '1'; } c = f; } strcpy(Cod

14、e[i].bits, &cd[start]); //將結(jié)果存入對(duì)應(yīng)的編碼數(shù)組中 } } void OutputHuffmanTCode() { cout << "哈夫曼編碼：" << endl; cout << "——————————————————————" << endl; cout << "字符\t權(quán)值\t\t哈夫曼編碼 " << endl; for (int i = 0; i < L.n; i++)//輸出字符，權(quán)值，哈夫曼編碼 {

15、 cout << "——————————————————————" << endl; cout << HuffmanT[i].name << "\t" << HuffmanT[i].weight << "\t"; cout << Code[i].bits; cout << endl; } cout << "——————————————————————" << endl; } void InitHT()//哈夫曼初始化 { L.R

16、eadLetter(); fn = (L.n)*2 - 1; for (int i = 0; i < fn; i++) { if (i < L.n) { HuffmanT[i].name = L.letter[i].pname; HuffmanT[i].weight = L.letter[i].lweight; } } } void SelectMin(int m, int &p1, int &p2

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

18、 m1 = HuffmanT[i].weight; p1 = i; } else if (HuffmanT[i].parent == -1 && HuffmanT[i].weight < m2)//找出為訪問的權(quán)值第二小結(jié)點(diǎn) { m2 = HuffmanT[i].weight; p2 = i; } } } void CreatHT()//建立哈夫曼樹

19、 { int i, p1, p2; InitHT(); for (i = L.n; i < fn; i++) { SelectMin(i, p1, p2); HuffmanT[p1].parent = HuffmanT[p2].parent = i; HuffmanT[i].lchild = p1; HuffmanT[i].rchild = p2; HuffmanT[i].weight = Huffma

20、nT[p1].weight + HuffmanT[p2].weight; } } int OutArticleCode()//顯示文章編碼 {//文章編碼操作 ifstream input; input.open(L.namef); if (input.fail()) { cout << "文件不存在！" << endl; return 0; } char ch; cout << "文

21、章編碼如下：" << endl; while (!input.eof()) { ch = input.get(); for (int i = 0; i < L.n; i++) { if (Code[i].ch == ch) cout << Code[i].bits; } } cout << endl; input.close(); } int Sa

22、veArticleCode()//保存文章編碼 { ofstream output; ifstream input; char namef1[max2]; input.open(L.namef); if (input.fail()) { cout << "該文件不存在！" << endl; return 0; } cout << "請(qǐng)輸入保存文章編碼的文件名：" << endl; cin >

23、> namef1; output.open(namef1); char ch; while (!input.eof()) { ch = input.get(); for (int i = 0; i < L.n; i++) { if (Code[i].ch == ch) { for (int j = 0; j < strlen(Code[i].bits); j++) {

24、 output.put(Code[i].bits[j]); } } } } input.close(); output.close(); cout << "保存完畢！" << endl; } int OutTransCode() {//文章譯碼操作 ifstream input; char namef[max2]; cout << "請(qǐng)輸入保存

25、文章編碼的文件名：" << 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

26、 == '0')//遇0搜索左子樹 { if (HuffmanT[c].lchild >= 0) { c = HuffmanT[c].lchild; } if (HuffmanT[c].lchild == -1)//判斷是否到葉子 { cout << HuffmanT[c].name; //輸出字符 c = 2

27、 * L.n - 2; //返回根節(jié)點(diǎn) } } if (ch == '1')//遇1搜索右子樹 { if (HuffmanT[c].rchild >= 0) { c = HuffmanT[c].rchild; } if (HuffmanT[c].rchild == -1)//判斷是否到葉子 {

28、 cout << HuffmanT[c].name; //輸出字符 c = 2 * L.n - 2; //返回根節(jié)點(diǎn) } } ch = input.get(); } cout << endl; input.close(); } int SaveTransCode() {//保存文章譯碼 ofstream output; ifstr

29、eam input; char namef[max2]; char namef1[max2]; cout << "請(qǐng)輸入文章編碼所在的文件名：" << endl; cin >> namef; input.open(namef); if (input.fail()) { cout << "該文件不存在！" << endl; return 0; } cout << "請(qǐng)輸入保存文章譯碼的文件名：" <<

30、endl; cin >> namef1; output.open(namef1); char ch; ch = input.get(); int c = 2 * L.n - 2; while (!input.eof()) { if (ch == '0') { if (HuffmanT[c].lchild >= 0) { c = HuffmanT[c].lchild;

31、 } if (HuffmanT[c].lchild == -1) { output.put(HuffmanT[c].name); c = 2 * L.n - 2; } } if (ch == '1') { if (HuffmanT[c].rchild >= 0) { c = HuffmanT[c].rchi

32、ld; } if (HuffmanT[c].rchild == -1) { output.put(HuffmanT[c].name); c = 2 * L.n - 2; } } ch = input.get(); } input.close(); output.close(); cout

33、<< "保存完畢！" << endl; } int FileCompression() {//文件壓縮功能 CreatHT(); CharHuffmanTCoding(); //保存編碼 ofstream output; ifstream input; char namef1[] = {"temp.txt"}; input.open(L.namef); if (input.fail()) { cout

34、<< "該文件不存在！" << endl; return 0; } output.open(namef1); char ch; while (!input.eof()) { ch = input.get(); for (int i = 0; i < L.n; i++) { if (Code[i].ch == ch) { for (int j = 0; j < strlen

35、(Code[i].bits); j++) { output.put(Code[i].bits[j]); } } } } input.close(); output.close(); //壓縮文件 ofstream File1; ifstream File2; char namef2[max2]; cou

36、t << "請(qǐng)輸入壓縮后的文件名：" << endl; cin >> namef2; File1.open(namef2); File2.open(namef1); if (File2.fail()) { cout << "該文件不存在！" << endl; return 0; } char sh; char th; int i = 0; char j = '0';

37、 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';

38、 } i++; } if (i == 7) { th = count; File1.put(th); i = 0; count = 0; } if (sh == EOF) { th = count; File1.put(th);

39、 File1.put(j); i = 0; count = 0; } } File1.close(); File2.close(); remove(namef1); cout << "文件壓縮完畢！" << endl; } int FileDecompression() {//文件解壓縮 //保存編碼 fstream output;

40、 fstream input; char namef2[max2]; char namef1[] = {"temp.txt"}; cout << "請(qǐng)輸入待解壓縮的文件名：" << endl; cin >> namef2; input.open(namef2, ios::in | ios::binary); output.open(namef1, ios::out | ios::binary); if (input.fail()) {

41、 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; char num;

42、 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++) {

43、 num = count % 2 + '0'; output.write(reinterpret_cast (&num), sizeof (num)); count = count / 2; } } if (ch == EOF) { for (int i = 0; i < 7; i++) { num = count % 2 +

44、'0'; output.write(reinterpret_cast (&num), sizeof (num)); count = count / 2; if (count == 0) { break; } } for (int i = 0; i < th - '0'; i++) {

45、 output.write(reinterpret_cast (&t), sizeof (t)); } } } output.close(); input.close(); //解壓文件 fstream File1; fstream File2; char namef3[max2]; cout << "請(qǐng)輸入解壓后的文件名：" << endl;

46、 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 (&ch), sizeof

47、 (ch)); int c = 2 * L.n - 2; while (!File2.eof()) { if (ch == '0') { if (HuffmanT[c].lchild >= 0) { c = HuffmanT[c].lchild; } if (HuffmanT[c].lchild == -1) { cout << HuffmanT[c

48、].name; File1.write(reinterpret_cast (&HuffmanT[c].name), sizeof (HuffmanT[c].name)); c = 2 * L.n - 2; } } if (ch == '1') { if (HuffmanT[c].rchild >= 0) { c = HuffmanT[c]

49、.rchild; } if (HuffmanT[c].rchild == -1) { cout << HuffmanT[c].name; File1.write(reinterpret_cast (&HuffmanT[c].name), sizeof (HuffmanT[c].name)); c = 2 * L.n - 2; }

50、} File2.read(reinterpret_cast (&ch), sizeof (ch)); } cout << endl; File2.close(); File1.close(); remove(namef1); cout << "解壓完畢！" << endl; } }; #endif /* HUFFMANFUNCTION_H */ ======================================

51、================================ /* * File: main.cpp * Author: Administrator * * Created on 2011年12月13日, 上午9:09 */ #include #include "HUFFMANFUNCTION.h" using namespace std; /* * */ int main(int argc, char** argv) { Function *a = new Function; while (

52、1) {//主界面顯示 cout << endl << endl << endl; cout << "<<==================功 能 選 擇===============>>" << endl; cout << " 【1】讀取文章并對(duì)字符編碼 " << endl; cout << " 【2】哈夫曼編碼信息 " << endl; cout << "

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

54、ut << "=========================================================" << endl << endl; char ch; cout << "====>>請(qǐng)選擇功能： "; cin >> ch; switch (ch) { case '1'://讀取文章并對(duì)字符編碼 { delete a; a = new Function; syst

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

56、Code(); system("pause"); system("cls"); break; } case '3'://文章編碼 { system("cls"); while (1) { cout << endl; cout << "========>>1.顯示文章編碼" << endl;

57、 cout << "========>>2.保存文章編碼" << endl; cout << "========>>3.返回上一界面" << endl; char ch1; cout << endl << "===>>請(qǐng)選擇功能："; cin >> ch1; switch (ch1) { case '1'://顯示文章編碼

58、{ system("cls"); a->OutArticleCode(); system("pause"); system("cls"); continue; } case '2'://保存文章編碼 { system("cls");

59、 a->SaveArticleCode(); system("pause"); system("cls"); continue; } case '3'://返回上一界面 { break; } default:

60、 { system("cls"); cout << "輸入錯(cuò)誤，請(qǐng)重新輸入！" << endl; continue; } } system("cls"); break; } break; } case '4'://文章譯碼

61、 { system("cls"); while (1) { cout << endl; cout << "========>>1.顯示文章編碼的譯碼" << endl; cout << "========>>2.保存文章編碼的譯碼" << endl; cout << "========>>3.返回上一界面" << endl; char ch1;

62、 cout << endl << "===>>請(qǐng)選擇功能："; cin >> ch1; switch (ch1) { case '1'://顯示文章編碼的譯碼 { system("cls"); a->OutTransCode(); system("pause");

63、 system("cls"); continue; } case '2'://保存文章編碼的譯碼 { system("cls"); a->SaveTransCode(); system("pause"); system("cls");

64、 continue; } case '3'://返回上一界面 { break; } default: { system("cls"); cout << "輸入錯(cuò)誤，請(qǐng)重新輸入！" << endl; conti

65、nue; } } system("cls"); break; } break; } case '5': { delete a; a = new Function; system("cls"); a->FileCompression();

66、 system("pause"); system("cls"); continue; } case '6': { system("cls"); a->FileDecompression(); system("pause"); system("cls"); continue; } case '7': { return 0; } default: { system("cls"); cout << "功能選擇錯(cuò)誤，請(qǐng)重新輸入！" << endl; break; } } } return 0