哈弗曼编码译码(C++实现)

1、 数据结构（C+实现） 实训报告题 目：哈弗曼编码与译码专 业： 信息管理 班 级： 12512201 学 生： 吴昊翀 学 号： 1251220117 指导老师： 黄建灯 目录一、实训要求4二、课题分析和设计41. 基本需求分析42. 对应的结构体或类5三、主要功能界面71.主界面72. 读取文章并对字符编码83. 哈弗曼编码信息94.文章编码10四、 总结12五、附录13一、实训要求n 输入为：一段英文或中文的文章（原文）n 对输入的文章构造哈夫曼树n 生成对应的编码n 输出为：原文所对应的编码（译文）n 根据已经生成的编码表，输入任意的译文可以得到对应的原文二、课题分析和设计1. 基本需

2、求分析 1.在通信过程中，为了提高信道利用率，缩短信息传输时间降低传输成本，需要一编码译码器。 2.此哈弗曼编码译码器应具有编码译码的双向功能，即在发送端通过编码系统对传入的数据进行编码。 3.在接收端将数据译码，将具有两项功能的编码译码器用于双工信道就可满足，双工信道的双向编译功能。 4.输入某段报文是，系统将自己完成编译输出。1. 程序设计流程 (1)文字表述开始进入功能选择界面，包含五种操作：1. 读取文章并对字符编码。 2.哈夫曼编码信息。 3.文章编码。 4.文章译码。 5.退出程序。 （2） 操作 1：给定一篇文章，统计字符出现的概率，并根据概率建立哈弗曼树，并利用哈弗曼树对字符进

3、行哈弗曼编码。 2：显示哈弗曼编码信息，包括字符，字符出现的概率，哈弗曼编码。 3：对文章进行译码，显示译码信息，并保存。 4：对文章进行译码，显示并保存 （3）流程图 程序开始程序主界面哈弗曼编码信息读取文章并对文章编码退出程序文章译码文章编码保存译码显示译码返回主界面返回主界面保存编码显示编码2. 对应的结构体或类（1）定义class Htnote public: char name; /字符名 double weight; /权重 int lchild; /左孩子 int rchild; /右孩子 int parent; /父亲 Htnote() weight = 0; lchild =

4、 -1; parent = -1; rchild = -1; ; （2）定义字符和出现的次数class Name public: int num; /字符出现的次数 char pname; /字符名 double lweight; /权值 Name() num = 0; lweight = 0; ;（3）定义字符种类总数和存储信息class GetName public: char namefmax2; int n; /字符的种类 int sum; /字符的总数 Name lettermax1; /存储字符信息的类的数组 GetName() sum = 0; n = 0; （4） 定义编码类c

5、lass CodeNode/编码类public: char ch; /存储字符 char bitsmax1; /存储编码;class Function public: GetName L; int fn; /定义哈夫曼数组大小 Htnote HuffmanTmax3; /哈夫曼数组 CodeNode Codemax1; /字符编码数组 Function() fn = 0; 三、主要功能界面1.主界面2. 读取文章并对字符编码3. 哈弗曼编码信息4.文章编码5.文章译码4、 总结 为期两个星期的课程设计终于完美落下帷幕，回想起前前后后还是有苦有甜。当拿到课题是感觉还行！结果前几天做程序的代码时一

6、点都不会做，课本也看不懂课程进度可以说是原地踏步！只能怪自己吧！老师讲的有时能听懂有时就听不懂，到头来今天的局面，当时以为自己完成不了任务。过程中甜的是有老师和同学的帮忙，总算圆满完成任务。通过本次实训让我重新学习了算法和数据结构这门课程，也懂得了用代码来建立哈弗曼树，编码译码双向功能! 上机实验，将理论的知识与实际结合起来。增强了自己的动手能力，觉的任何知识都不是轻而易举的学懂，必须花点心思去学，必须要付出努力。以后上课就不能像以前那样，要好好学习这样不辜负老师对我们的心意。最后衷心感谢帮助我完成程序设计的老师和同学表示感谢！五、附录 全部代码：#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; /权重 int lchild; /左孩子 int rchild; /右孩子 int parent; /父亲 Htnote()

8、 weight = 0; lchild = -1; parent = -1; rchild = -1; ;class Name public: int num; /字符出现的次数 char pname; /字符名 double lweight; /权值 Name() num = 0; lweight = 0; ;class GetName public: char namefmax2; int n; /字符的种类 int sum; /字符的总数 Name lettermax1; /存储字符信息的类的数组 GetName() sum = 0; n = 0; void GetWeight()/得到

9、字符的权值 for (int i = 0; i < n; i+) letteri.lweight = (double) letteri.num / sum; /出现的次数除总数得到权值 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(); /得到字符权值 ;class CodeNode/编码类public: char ch; /存储字符 char bitsmax1; /存储编码;class Function public: GetName L; int fn; /定义哈夫曼数组大小 Htnote HuffmanTmax3; /哈夫曼数组 CodeNode Codemax1; /字符编码数组 Function() fn = 0; void CharHuffmanTCoding()/编码功能实现 int i, f, c; char cd1000; /暂时存储编码的数组 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、/将结果存入对应的编码数组中 void OutputHuffmanTCode() cout << "哈夫曼编码：" << endl; cout << "-" << endl; cout << "字符t权值tt哈夫曼编码 " << endl; for (int i = 0; i < L.n; i+)/输出字符，权值，哈夫曼编码 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)/选择最小的两个节点 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)/找出为访问过的最小权值节点 m2 = m1; p2 = p1; m1 = HuffmanTi.weight; p1 = i

16、; else if (HuffmanTi.parent = -1 && HuffmanTi.weight < m2)/找出为访问的权值第二小结点 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; /返回根节点 if (ch = '1')/遇1搜索右子树 if (HuffmanTc.rchild >= 0) c = HuffmanTc.rchild; if (H

22、uffmanTc.rchild = -1)/判断是否到叶子 cout << HuffmanT; /输出字符 c = 2 * L.n - 2; /返回根节点 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