哈夫曼编码与译码(附源码).doc

建立Huffman树进行编码和译码的设计 郝萌 1100300423 哈尔滨工业大学计算机科学与技术学院 1003104班摘要：建立一个简易的系统，对于给定的一篇英文文章，统计字符出 现的概率，并根据概率建立Huffman树，利用Huffman编码 对文章进行编码和译码。掌握Huffman树的建立与应用，并进 一步熟练掌握程序的设计流程。关键词：Huffman树 Huffman编码 文章译码 文件压缩 解压缩1. 引言： 给定一篇文章，统计字符出现的概率，根据概率建立哈夫曼树，并进行哈夫曼编码，进而可以利用哈夫曼编码对文章进行编码与译码和文件压缩、解压缩等操作。2. 程序设计流程 (1)文字表述开始进入功能选择界面，包含五种操作：1.读取文章并对字符编码，2.哈夫曼编码信息，3.文章编码，4.文章译码，5.文件压缩，6.文件解压缩，7.退出程序。操作1：给定一篇文章，统计字符出现的概率，并根据概率建立Huffman树，并利用Huffman树对字符进行Huffman编码。操作2：显示Huffman编码信息，包括字符，字符出现的概率，Huffman编码。操作3：对文章进行译码，显示译码信息，并保存。操作4：对文章进行译码，显示并保存。操作5：对文件进行压缩，每7位二进制序列对应一个ASCII码。操作6：对文件进行解压缩。（2） 流程图 （3） 程序数据要求及功能实现 主界面1.读取文件并对字符进行编码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 max2 50#define max3 256using namespace std;class Htnote public: char name; /字符名 double weight; /权重 int lchild; /左孩子 int rchild; /右孩子 int parent; /父亲 Htnote() 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()/得到字符的权值 for (int i = 0; i n; i+) letteri.lweight = (double) letteri.num / sum; /出现的次数除总数得到权值 int ReadLetter() ifstream input; cout 请输入文件名： 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() /读取文件中的所有字符 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(); /得到字符权值 ;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 cdL.n + 1; /暂时存储编码的数组 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); /将结果存入对应的编码数组中 void OutputHuffmanTCode() cout 哈夫曼编码： endl; cout endl; cout 字符t权值tt哈夫曼编码 endl; for (int i = 0; i L.n; i+)/输出字符，权值，哈夫曼编码 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.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; 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; 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(); 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 请输入保存文章编码的文件名： 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 保存完毕！ endl; int OutTransCode() /文章译码操作 ifstream input; char namefmax2; cout 请输入保存文章编码的文件名： namef; input.open(namef); if (input.fail() cout 该文件不存在！ = 0) c = HuffmanTc.lchild; if (HuffmanTc.lchild = -1)/判断是否到叶子 cout = 0) c = HuffmanTc.rchild; if (HuffmanTc.rchild = -1)/判断是否到叶子 cout HuffmanT; /输出字符 c = 2 * L.n - 2; /返回根节点 ch = input.get(); cout endl; input.close(); int SaveTransCode() /保存文章译码 ofstream output; ifstream input; char namefmax2; char namef1max2; cout 请输入文章编码所在的文件名： namef; input.open(namef); if (input.fail() cout 该文件不存在！ endl; return 0; cout 请输入保存文章译码的文件名： 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.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(); CharHuffmanTCoding(); /保存编码 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.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 请输入压缩后的文件名： 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+; 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.txt; cout 请输入待解压缩的文件名： 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; char 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+) 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 请输入解压后的文件名： namef3; File2.open(namef1, ios:in | ios:binary); File1.open(namef3); if (File2.fail() cout 该文件不存在！ endl; return 0; cout 解压后的文件内容为： 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.lchild = -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); 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 namespace std;/* * */int main(int argc, char* argv) Function *a = new Function; while (1) /主界面显示 cout endl endl endl; cout endl; cout 【1】读取文章并对字符编码 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 请选择功能： ; cin ch; switch (ch) case 1:/读取文章并对字符编码 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