哈弗曼编码解码器课程设计

1、/课程设计：哈弗曼编码解码器及报告书/vc6测试可以/运行的条件是：“yasuo.txt”, “yima.txt”, “jieya.txt”存在，要压缩的信息已存/在了其他一个文本文档中，然后根据提示输入要压缩的文本文件名，输入的文件名要/加.txt扩展名,如：a.txt。/write by dlnu.ZJY#include <iostream>#include <fstream>#define Max 50#define MAX 10000using namespace std;struct tree/存储统计的频率和字母的char word;int rare;str

2、uct Bianma/存各字母所对应的编码的char word;int codeMax;struct element/哈弗曼树的tree weight;int lchild;int rchild;int parent;int flag;int yezi;/_全局变量element huffTree103;Bianma bianma52;int zijie, wei, yushu;char filename50;/_class HuffmanTreepublic:void open(); /打开要编码文件并统计字母出现的频率函数void creat(); /构造哈弗曼树函数int select(

3、int k); /找权值最小根节点函数void coding(); /编码函数void decoding(); /将编码后信息存入文件函数void original(); /对已压缩文件解压并译码函数void compare(); /压缩函数void yasuoxianshi(); /显示压缩信息void jieyaxianshi(); /显示解压信息void xianshi(); /显示文件压缩比void menu(); /菜单;/_void HuffmanTree:open()/打开文件并统计频率char ch;int i, n, j = 0, flag = 0;for(i = 0; i

4、< 103; i+)/初始化huffTreei.weight.rare = 0;huffTreei.weight.word = 0;huffTreei.yezi = 0;cout<<"请输入您要压缩的文件名："<<endl;cin>>filename;ifstream infile(filename, ios:out);/打开文件if(!infile)flag=1;cerr<<"文件打开失败!"<<endl;exit(1); if(flag = 0)cout<<"压缩

5、中，请等待"<<endl<<endl<<endl;while(infile.get(ch)/统计频率if(ch >= 65 && ch <= 90)/6590i = ch - 65;huffTreei.weight.rare+;huffTreei.yezi = 1;if(ch >= 97 && ch <= 122)/97122n = ch - 71;huffTreen.weight.rare+;huffTreen.yezi = 1;infile.close();/_void HuffmanTr

6、ee:creat()/构造哈弗曼树int i, k, i1, i2, n = 52, j;for(i = 0; i < 2*n-1; i+)/初始化huffTreei.parent = -1;huffTreei.lchild = -1;huffTreei.rchild = -1;huffTreei.flag = 0; for(i = 0; i < 26; i+)/字母赋值huffTreei.weight.word=i+65; for(j = 0; j < 26; j+)/字母赋值huffTreej+26.weight.word = j+97; for(k = n; k <

7、; 2*n-1; k+)/建树 i1 = select(k); i2 = select(k); huffTreek.weight.rare = huffTreei1.weight.rare + huffTreei2.weight.rare; huffTreei1.parent = k; huffTreei2.parent = k; huffTreek.lchild = i1; huffTreek.rchild = i2; /_int HuffmanTree:select(int k)/找出所有根节点中权值最小的根节点int i, n = 52, min, rare = 10000;for(i

8、= 0; i < k; i+) if(huffTreei.weight.rare < rare) && (huffTreei.flag = 0)min = i;rare = huffTreei.weight.rare;huffTreemin.flag = 1; return min;/_void HuffmanTree:coding()/对构造出的哈弗曼树编码int e, a = 0, i, j, n = 52, p, parent;for(i = 0; i < n; i+)/初始化for(j = 0; j < Max; j+)bianmai.codej

9、 = -1;bianmai.word = 95;for(i = 0; i < 2*n-1; i+)/根据建好的哈弗曼树对各字母编码，从叶子结点往上查，左1右0，将编好的码存入bianma中 if(huffTreei.flag != 2) && (huffTreei.yezi = 1)e = Max - 1;huffTreei.flag = 2;bianmaa.word = huffTreei.weight.word;p = i;while(huffTreep.parent != -1)parent = huffTreep.parent;if(huffTreeparent.

10、lchild = p)bianmaa.codee = 0;e-;else if(huffTreeparent.rchild = p)bianmaa.codee = 1;e-;p = huffTreep.parent;/原来是这里的问题，以前parent两次赋值让每次编码都又往上跳了一级，所有编出的码有重复的a+;/_void HuffmanTree:decoding()/将原文件重新编码后将编码后的存入文件int i, j, n = 52;char ch;ifstream file(filename, ios:out);if(!file)cerr<<"文件打开失败!&qu

11、ot;<<endl;exit(1);ofstream infile("bianma.txt", ios:in|ios:out|ios:trunc);/打开文件if(!infile)cerr<<"文件打开失败!"<<endl;exit(1);while(file.get(ch)/将编码后的信息存入bianma.txt文件for(i = 0; i < n; i+)if(ch = bianmai.word)for(j = 0; j < Max; j+)if(bianmai.codej != -1)infile &

12、lt;< bianmai.codej;file.close();infile.close();/_void HuffmanTree:compare()/压缩文件char ch, a, yasuo10008 = 95, b100000 = 0;int n = 0, i = 0, j, k = 0, l = 0;ifstream infile("bianma.txt", ios:out);/打开文件if(!infile)cerr<<"文件打开失败!"<<endl;exit(1);ofstream outfile("ya

13、suo.txt", ios:binary|ios:trunc);/打开文件if(!outfile)cerr<<"open error!" <<endl;abort();while(infile.get(ch)/统计0，1个数bi = ch;i+;wei = i;zijie = wei / 8;yushu = wei % 8;if(yushu != 0)zijie+;for(i = 0; i < zijie; i+)/将编码后的信息每八个倒着存入yaosuo数组for(j = 7; j >= 0; j-)yasuoij = bk+

14、;for(i = 0; i < zijie; i+)/压缩已编码的原文件，八个编码合为一个字节存入二进制文件a = 0;for(j = 0; j < 8; j+)if(yasuoij != 95)if(yasuoij = '0' | yasuoij = '1')if(yasuoij = '1')a = (a << 1) | 1;else if(yasuoij = '0')a = a << 1;outfile.write(char *)&a, sizeof(a);infile.close(

15、);outfile.close();/_void HuffmanTree:original()/对已压缩文件解压并译码int i = 0, n = 52, p = 102, q = 102, k, j, f = 0, m = 0;char a, b, c, d, jieya100000;ifstream infile("yasuo.txt", ios:binary);/打开文件if(!infile)cerr<<"文件打开失败!"<<endl;abort();ofstream infile1("jieya.txt"

16、;, ios:in|ios:out|ios:trunc);/打开文件if(!infile1)cerr<<"文件打开失败!"<<endl;exit(1);for(k = 0; k < zijie; k+)/解压压缩了的二进制文件infile.read(char*)&a, sizeof(a);for(j = 0; j < 8; j+)if(m >= wei)break;b = a;c = (b >> 1) << 1);/先右移再左移将最右端的位变为0d = (a - c) + '0'/得出

17、最右端的二进制位a = a >> 1; if(d = '0')jieyaf+ = '0'/将解压后的信息先存入jieya数组else if(d = '1')jieyaf+ = '1'/将解压后的信息先存入jieya数组m+;for(int z = 0; z < wei + 1; z+)/译码，从树的根结点开始判断，左1右0，直到找到叶子结点if(jieyaz = '0')i = huffTreep.lchild;p = huffTreep.lchild;if(huffTreei.weight.wo

18、rd != 0)infile1 << huffTreei.weight.word;p = q;else if(jieyaz = '1')i = huffTreep.rchild;p = huffTreep.rchild;if(huffTreei.weight.word != 0)infile1 << huffTreei.weight.word;p = q;infile.close();infile1.close();/_void HuffmanTree:yasuoxianshi()/显示压缩的信息char ch;int i, j, n = 52, k =

19、 0;ifstream infile(filename, ios:out);/打开文件if(!infile)cerr<<"文件打开失败!"<<endl;exit(1);cout<<"原文件："<<endl;while(infile.get(ch)/输出原文件cout << ch;cout << endl << endl;infile.close();cout<< "根据哈弗曼树对字母的编码："<<endl;for(i = 0;

20、i < n; i+)/输出各字母对应的编码if(bianmai.word != 95)for(j = 0; j < Max; j+)if(bianmai.codej != -1)cout<< bianmai.codej;/编码cout<<" "<<bianmai.word<<endl;/字母cout<< endl;ifstream infile2("bianma.txt", ios:out);/打开文件if(!infile2)cerr<<"文件打开失败!&quo

21、t;<<endl;exit(1);cout<<"对原文件编码后的文件："<<endl;while(infile2.get(ch)/输出对原文件编码后的信息cout<< ch;cout<< endl<< endl;cout<< "压缩成功!"<<endl<<endl;cout<< "压缩后的文件名为："<< "yasuo.txt"<< endl<< endl;/_

22、void HuffmanTree:jieyaxianshi()/显示解压的信息char ch;ifstream infile3("jieya.txt", ios:out);/打开文件if(!infile3)cerr<<"文件打开失败!"<<endl;exit(1);cout<<"解压成功!"<<endl<<endl;cout<<"解压后的文件名为: "<<"jieya.txt"<<endl<&l

23、t;endl;cout<<"解压并译码后的文件："<<endl;while(infile3.get(ch)/输出解压后的信息cout << ch;cout<<endl<<endl;/_void HuffmanTree:xianshi()/显示压缩比的信息int k = 0;char ch;ifstream infile4(filename, ios:out);/打开文件if(!infile4)cerr<<"文件打开失败!"<<endl;exit(1);while(infi

24、le4.get(ch)/统计原文件字母个数k+;cout<<"本次文件的压缩比为："<<endl;cout<<"原文件"<<" "<<"压缩后的文件"<<endl;cout<<" "<< k <<" "<<":"<<" "<<zijie<<endl<<endl;if(k

25、> zijie)/判断压缩前后文件的大小看压缩是否成功cout<<"压缩成功!"<<endl<<endl;cout<<"压缩率为： "<<(double)zijie/(double)k)*100<<"%"<<endl<<endl;elsecout<<"压缩失败!"<<endl<<endl;/_void HuffmanTree:menu()/主菜单cout<<"

26、; 欢迎使用哈弗曼编码器 & 译码器"<<endl;cout<<"<<->>"<<endl;cout<<" 请选择您需要的操作："<<endl;cout<<" "<<endl; cout<<" "<<endl;cout<<" 1.压缩文件 "<<endl;cout<<" 2.解压文件 "<

27、;<endl;cout<<" 3.显示压缩比 "<<endl;cout<<" 4.退出 "<<endl;cout<<" "<<endl;cout<<" "<<endl<<endl; /_int main()HuffmanTree tree;int choose;while(1)tree.menu();cin>>choose;cout<<endl;switch(choose)cas

28、e 1:/压缩文件 tree.open();tree.creat();tree.coding();tree.decoding();pare();tree.yasuoxianshi();system("pause");system("cls");break;case 2:/解压文件tree.original();tree.jieyaxianshi();system("pause");system("cls");break;case 3:/显示压缩比 tree.xianshi();system("pause&

29、quot;);system("cls");break;case 4:/退出cout<<"谢谢使用!"<<endl;exit(0);default: cout<<"输入错误，请重新输入!"<<endl;system("pause");system("cls");break;return 0;题目：设计Huffman 编码器与解码器（*）1、问题描述12需求分析23概要设计2（1）抽象数据类型：2（2）主程序流程：2（3）模块调用关系:34详细设计4（

30、1）实现概要设计的数据类型：4（2）主程序以及其它模块的算法描述：4主函数具体代码：4（3） 其它模块的算法描述5创建哈弗曼树函数：6挑选权值最小的根节点函数：6据建好的哈弗曼树编码函数：7压缩文件主要代码：8解压文件主要代码：8译码主要代码：95、编码与调试分析91.编码与调试过程中遇到的问题及解决办法：92.待解决问题：106、使用说明117、测试结果11（1）压缩文件结果：11（2）解压文件结果：12（3）显示压缩比结果：138、自学知识139、课程设计心得体会13参考书：141、问题描述利用哈夫曼编码进行信息通讯可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发

31、送端通过一个编码系统对待传输数据预先编码；在接受端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。基本要求：根据某字符文件统计字符出现频度，构造Huffman 树，编制Huffman编码，并将给定字符文件编码，生成编码文件；再将给定编码文件解码，生成字符文件。（要求按二进制位表示编码）提高要求：改进Huffman编码，产生两种以上的编码方案，对同一组测试数据，用不同的编码方案编码，从文件长度、算法复杂度等方面进行比较。测试数据：英文文档文件或中文文档文件。考核要求：（1） 对原文件编码后，保存

32、到新建文件中，将原文件与新文件比较，如果新文件长度大于原文件，则编码失败，成绩不及格。如果达到题目的基本要求，成绩为良好。（2） 达到提高要求，成绩可以为优秀。2需求分析软件的基本功能：根据某字符文件生成新的压缩后的二进制编码文件；再将给定编码文件解码，生成原来的字符文件。输入 / 输出形式：用户可以通过控制台，根据提示输入。输入：按提示输入，有错误过滤性能。输出：统一输出信息，不用选择。测试数据要求：将需要压缩的字符信息存在一个文本文件中后根据提示打开此文件进行压缩，文本文件中的信息内容为大小写字母。3概要设计（1）抽象数据类型： 结构体数组：element huffTree103;Bian

33、ma bianma52;（2）主程序流程：开 始“1”“2”“3”“4”文件名输出各压缩信息输出各解压信息输出压缩比退出其他结束（3）模块调用关系:void open(); /打开要编码文件并统计字母出现的频率数void creat(); /构造哈弗曼树函数int select(int k); /找出权值最小根结点函数void coding(); /编码函数void decoding(); /将原文件重新编码后将编码后的存入文件void original(); /对已压缩文件解压并译码void compare(); /压缩文件void yasuoxianshi(); /显示压缩信息void j

34、ieyaxianshi(); /显示解压信息void xianshi(); /显示文件压缩比void menu(); /菜单其函数调用关系如下：main()Open()Compare()Coding()Yasuoxianshi()Creat()Jieyaxianshi（）Decoding()Xianshi()Original()Select(int)Menu()4详细设计（1）实现概要设计的数据类型：struct tree/存储统计的频率和字母的char word;int rare;struct Bianma/存各字母所对应的编码的char word;int codeMax;struct el

35、ement/哈弗曼树的tree weight;int lchild;int rchild;int parent;int flag;int yezi;（2）主程序以及其它模块的算法描述：主函数具体代码：主函数调用实现各个函数功能。（3） 其它模块的算法描述创建哈弗曼树函数：此函数根据各个字母的权值建立哈弗曼树，其中select(int)是从还未挑选过的根结点中挑出权值最小的根结点的函数，挑出两个权值最小根结点后将她们的权值相加，存到第k个结点中，并把k赋为它们的父母，把i1，i2赋为k的左右还在，然后继续循环，直至找完所有结点。挑选权值最小的根节点函数：此函数为找出权值最小的根结点函数，先将ra

36、re赋了一个不可能被超过的值，再将它和huffTree中的第一个结点的rare比较，如果比热热小，则它们交换，像这样循环下去，最后挑出的权值最小的根结点，再找过的结点标志一下，防止重复。据建好的哈弗曼树编码函数：此函数是根据已建好的哈弗曼树编码，每次找到树中的根结点，将其做个标志，从根结点网上查，如果此结点是父母的左孩子，在数组中存入0，如果此结点是父母的右孩子，在数组中存入1，直到它的父母值为-1为止，一直循环，直至把所有的根结点找完。压缩文件主要代码：此函数为将编好码的内容压缩为二进制文件。如果遇到1则将a左移加1，如果遇到0则左移不加1，因为运用位操作左移后系统自动在最右位补0，这样0就存入了其中，如果左移一位再加1则1就存入了其中，这样每八位循环就可以将原来的内