算法设计与分析课程设计报告

1、算法设计与分析课程设计报告压缩软件课程设计书一、问题描述:建立一个文本文件，统计该文件中各字符频 率，对各字符进行Huffman编码，将该文件至 翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。算法分析及思路:对于该问题，我们做如下分析：(1) 首先得构造出哈弗曼树，我们用函数HuffinanTrec(lnt w,int s,int n)设 计；(2) 在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数 Huffmancode(char wen)设计；(3) 实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数 Hiiffmandecode()设计；(4) 其

2、中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一 些必要的标记，我们用函数runhuffman(char wen)ig计；(5) 在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同, 我们用函数compare(char wen)设计;(6) 其中的文件输入我们用到类”fshram.h”中的输入输出流，并在运行的文 件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需 要编码的数据。三、主要解决的设计问题：1. 写一个对txt文件压缩和解压的程序，使用动态编码。2使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也 可以存储所有字符的

3、频度或权值，然后读取时建立Huffman树；3使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一 个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用 一个特殊字符作为结束标记，则其频度为1,需要在建立Huffman树时把它看作 一个独立的字符进行建树。4使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每 当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位 为字节。五、输入和输出说明：K 数据输入：由文件input, txt提供输入需要压缩的内容；

4、2、结果输出：将压缩好的文件内容输出到编码后的文件.txt中，再由编码后的文件txt解压到译码后的文件txt中。六、程序及其注解：1、数据结构设计（即类的设计，包括类的数据成员、函数成员） 类的设计用HuffmanTree.h保存如下：#lnclude<iostream>#include<fstream>using namespace std;const int MaxSize=512;哈夫曼树的结点记录字符在数组中的位置字符出现频率（权值）哈夫曼树各个指针变量存储哈夫曼编码的数组struct elementint str;int weight;int lchild9r

5、child9parent;char bits30;class HuffmanTreeelement hufftreeMaxSize; int mi in;存放哈夫曼树结点的数组结点数public:HuffmanTree(int w9int s,int n);void Select(int njnt & &s2);void Huffmancode(char wen);哈夫曼编码void HuffmandecodeO;哈夫曼译码;/ class Runpublic:将编码后的文件译成原文件统计各字符频率比较逍遥游文件和译码后的文件void huffman(char we

6、n);void runhuffman(char wen); void compare(char wen);/2、算法设计(类的函数成员的具体设计)(1)算法一设计用HuffmanTree.cpp保存如下： #lnclude<iostream>#lnclude,' HuffmanTree.h'1using namespace std;/void HuffmanTree:Select(int n，int &sl,int &s2)sl=-l;s2=-l;for(int i=O;i<=n;l+)if(hiifftreei.parent=-l)if(sl

7、=-l)sl=i;contlnue;if(s2=-l) s2=i;continue; if(hufftreei.weight<hufftreesl.welght) sl=i;else if(hufftreei.weight<hufftrees2.welght) s2=i;/HuffmanTree:HuffmanTree(int w,int s4nt n)num=n;int il,i2;11=12=0;for(int i=0;i<2*num-l;i+)/外部叶子结点数为num个时，内部结点数为n-1, 整个哈夫曼树的需要的结点数为2*num-l.hufftreei.parent

8、=-l;hufftreei.lchlld=-l;hufftreei.rchild=-1;for(int J=0;j<num;J+)hufftreeJ.weight=wJ;hufftreej.str=sj;for(int k=num;k<2*num-l;k+)构建哈夫曼树Select(k-X41J2)； 在hufftree中找权值最小的两个结点II和12 hufftreeil.parent=k;hufftree12.parent=k; hiifftreek.weight=hufftreeil.weight+hufftreei2.weight; hufftreek.lchild=il;

9、hufftreek.rchild=l2;/void HuffmanTree:Huffmancode(char wen)ifstream in(wen);ofstream out(”编码后的文件.txt");int start=MaxSize-l;int cha=0;char cdMaxSize;存放一个编码cd MaxSize- l='0f;for(int i=0;i<num;i+)start=MaxSize-l;int c，f;for(c=i,f=hufftreei.parent;f!=-l;c=f,f=hufftreef.parent)if(hufftreef.lc

10、hlld=c) 置左分支编码 0cd-start=fOf;else cd-start= T;置右分支编码 1strcpy(hufftreei.bits,&cdstart)/将编码存放在相应结点存储哈夫曼 编码的数组中coutvv”字符在数组中的下标及其编码如下：冷输出字符在数组中的位置及其编码for(int k=0;k<num;k+)lf(k%3=0) cout«endl;cout«hufftreek.str«,t:M«hufftreek.bits«,tl;cout«endl«endl;for(char ch;

11、in.get(ch);) 将逍遥游文件中各个字符转变成相应的编码，写 入编码后的文件中if(int)ch<0) cha=(int)ch+256;else cha=(int)ch;for(int J=0;j<num;J+)if(hufftreeJ.str=cha)out«hufftreeJ.bits;cout«M编码成功！ "vvendl;/void HuffmanTree:Huffmandecode()ifstream in(f 编码后的文 #.txtH);ofstream out译码后的文件.txtu);int i=2*num-2;for(char

12、b;in»b;)if(b=,O,)i=hufftreei.lchild;else i=hufftreei.rchild;if(hiifftreei.lchlld=-1)out«(char)hufftreei.str;i=2*num-2;cout«fl译码成功! ,f«endl;/(2)算法二设计用HuffmanRun.cpp保存如下：#lnclude<iostream>#lnclude,' HuffmanTree.h'1using namespace std;/void Run:runhuffman(char wen)ifst

13、ream in(wen);int wMaxSlze;int weightMaxSize;存放各个字符的频率int strMaxSize;存放逍遥游文件中各个字符在数组w中的位置(下标)Int 1=0;int n=0;int cha=0;for(int J=O;j<MaxSize;J+)wj=0；庐从文件逍遥游中依次读入字符，根据字符的ASCII码值将字符存入str 数组的相应位置而weighty数组的相应位置则记录该字符出现的频率紗for(char ch;in.get(ch);)lf(lnt)ch<0) cha=(int)ch+256;中文的 ASCII 码值为负数，加上 256使

14、其可以存放在数组中else cha=(int)ch;wcha+;for(int k=0;k<MaxSize;k+)if(wk!=0)strn=k;weight n=wk;n+;coutvv"字符在数组中的下标及其权值如下：”；输出字符在数组中的位置 及其权值for(int p=0;p<n;p+)if(p%6=0)cout«endl;cout«strp«t,:t,«weightp«,tt;cout«endl«endl;HuffmanTree h(weight,str,n); 构造哈夫曼树h.Huffman

15、code(wen);利用哈夫曼树进行编码及译码h.HuffmandecodeO;void Run:huffman(char wen)ifstream in(wen);int weightMaxSize;存放各个字符的频率int strMaxSize;存放逍遥游文件中各个字符在数组w中的位置(下标)int n=0;HuffmanTree h(weight,str,n); 构造哈夫曼树h.Huffniandecode();void Run:compare(char wen)ifstream ina(wen);ifstream inc("译码后的文件.txt");char str

16、inga 100000;int 1=0;int flag=0;char stringc 100000;intJ=O;for(char cha;ina»cha;)将文件逍遥游的内容读入数组stringastringai=cha;i+；stringai='Ot;for(char chc;inc»chc;)将译码后的文件内容读入数组stringedstringcj=chc;H+;stringcJ=,O,;/*比较文件逍遥游和译码后的文件内容，若相同则说明编码正确，若不同, 则说明编码错误*/for(int k=O;stringak!=,0'&&st

17、ringck!='0;k+) if(stringak!=stringck) flag=0;if(stringak=tOt&&strlngck=,O,) flag=l;else flag=0;lf(flag=O)coutvv“逍遥游文件与译码后的文件不相同，编码错误！ “vvendl;elsecout«*谴遥游文件与译码后的文件相同，编码正确！ "vvendl;(3)实现算法设计的主程序用HaffmanMain.cpp保存如下：#lnclude<iostream>#includeHHiiffmanTree.hHusing namespace

18、 std;void main()char wenjian20;int t=l;while(l)if(t=l)cout«*请输入要编码的文件名：“；cin»wenjian;Run manager; manager.runhuffman(wenjian); pare(wenjian); elsecoutvv “请输入要译码的文件名：“；cin»wenjian;Run manager; manager.huffman(wenjian); coutvv"请继续选择需要执行的功能：“vvendl; coutvv“请问您是需要编码文件还是译码文件？ “vvmdl;

19、cout«M如果是要编码文件，那么请输入1； H«endl; cout«M如果是要译码文件，那么请输入0。H«endl; dn»t;七、程序运行结果及分析:E：kgS-i+3yia计耸可卷习耳衣设计与力折深程斟(胡伟l(HlS6LQgfcuqHaffmanMain.gxe<161 ；1163；7182:2183:2192:2199：1206:2207:1224:2228:2238:1247:2请输入要编码的文 字符在数组中的下标及其权值如下:172:3178；1184:2187:3200:2201 ：1208:3210:4229:3231 :2250:1名