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

算法设计与分析课程设计2019-1-15压缩软件课程设计书1、 问题描述：建立一个文本文件，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件至翻译成Huffman编码文件，再将Huffman编码文件翻译成原文件。 2、 算法分析及思路：对于该问题，我们做如下分析：（1） 首先得构造出哈弗曼树，我们用函数HuffmanTree(int w,int s,int n)设计；（2） 在构建哈弗曼树的基础上，进一步实现哈弗曼编码问题，我们用函数Huffmancode(char wen)设计；（3） 实现哈弗曼编码后再进一步实现哈弗曼译码问题，我们用函数Huffmandecode()设计；（4） 其中编码问题中，得进一步统计出各个字符在文件中的频率，并进行一些必要的标记，我们用函数runhuffman(char wen)设计；（5） 在译码过程中，还有必要的一步是比较原文件与译码后的文件是否相同，我们用函数compare(char wen)设计；（6） 其中的文件输入我们用到类”fstream.h”中的输入输出流，并在运行的文件夹中建立一个文件名为逍遥游的文本文件，且在逍遥游文件中输入需要编码的数据。3、 主要解决的设计问题：1.写一个对txt文件压缩和解压的程序，使用动态编码。2.使用Huffman编码压缩和解压时，Huffman树的存储可以直接存储树结构，也可以存储所有字符的频度或权值，然后读取时建立Huffman树；3.使用Huffman编码压缩和解压时，注意定义压缩码的结束标记，可以使用一个特殊的字符作为结束标记，也可以在压缩码之前存储其比特长度；如果使用一个特殊字符作为结束标记，则其频度为1，需要在建立Huffman树时把它看作一个独立的字符进行建树。4.使用Huffman编码压缩和解压时，在一个缓冲区里面收集压缩码比特流，每当收集的比特数满8时，可以把这8比特通过位操作合并成一个字节写入文件（当然也可以收集满一定数目的字节后再写入文件）。写入文件的最小信息单位为字节。四、程序设计的流程图：统计字符，得出统计出的字符的权值n根据权值进行建立哈弗曼树输出哈弗曼树生成二进制文件主函数编码输出编码压缩编码解码解压生成新的文本文档退出建立哈弗曼树输出哈弗曼树根据哈弗曼树编码根据哈弗曼树解码对二进制文件进行解压生成文本文档输出编码对编码进行压缩生成二进制文件五、输入和输出说明：1、数据输入：由文件input.txt提供输入需要压缩的内容；2、结果输出：将压缩好的文件内容输出到编码后的文件.txt中，再由编码后的文件.txt解压到译码后的文件.txt中。6、 程序及其注解：1、数据结构设计（即类的设计，包括类的数据成员、函数成员）类的设计用HuffmanTree.h保存如下:#include#includeusing namespace std;const int MaxSize=512;/-struct element /哈夫曼树的结点int str; /记录字符在数组中的位置int weight; /字符出现频率（权值）int lchild,rchild,parent; /哈夫曼树各个指针变量char bits30; /存储哈夫曼编码的数组;/-class HuffmanTreeelement hufftreeMaxSize; /存放哈夫曼树结点的数组int num; /结点数public:HuffmanTree(int w,int s,int n);void Select(int n,int &s1,int &s2);void Huffmancode(char wen); /哈夫曼编码 void Huffmandecode(); /哈夫曼译码;/-class Runpublic:void huffman(char wen);/将编码后的文件译成原文件void runhuffman(char wen); /统计各字符频率void compare(char wen); /比较逍遥游文件和译码后的文件;/- 2、算法设计（类的函数成员的具体设计）（1）算法一设计用HuffmanTree.cpp保存如下：#include#includeHuffmanTree.husing namespace std;/-void HuffmanTree:Select(int n,int &s1,int &s2)s1=-1;s2=-1;for(int i=0;i=n;i+)if(hufftreei.parent=-1) if(s1=-1) s1=i;continue; if(s2=-1) s2=i;continue; if(hufftreei.weighthufftrees1.weight)s1=i; else if(hufftreei.weighthufftrees2.weight)s2=i;/-HuffmanTree:HuffmanTree(int w,int s,int n) num=n;int i1,i2;i1=i2=0;for(int i=0;i2*num-1;i+)/外部叶子结点数为num个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*num-1.hufftreei.parent=-1;hufftreei.lchild=-1;hufftreei.rchild=-1;for(int j=0;jnum;j+)hufftreej.weight=wj;hufftreej.str=sj;for(int k=num;k2*num-1;k+) /构建哈夫曼树Select(k-1,i1,i2); /在hufftree中找权值最小的两个结点i1和i2 hufftreei1.parent=k;hufftreei2.parent=k;hufftreek.weight=hufftreei1.weight+hufftreei2.weight;hufftreek.lchild=i1;hufftreek.rchild=i2;/-void HuffmanTree:Huffmancode(char wen)ifstream in(wen);ofstream out(编码后的文件.txt);int start=MaxSize-1;int cha=0;char cdMaxSize; /存放一个编码cdMaxSize-1=0;for(int i=0;inum;i+) start=MaxSize-1;int c,f;for(c=i,f=hufftreei.parent;f!=-1;c=f,f=hufftreef.parent)if(hufftreef.lchild=c) /置左分支编码0cd-start=0;else cd-start=1; /置右分支编码1strcpy(hufftreei.bits,&cdstart);/将编码存放在相应结点存储哈夫曼编码的数组中cout字符在数组中的下标及其编码如下：; /输出字符在数组中的位置及其编码for(int k=0;knum;k+)if(k%3=0) coutendl;couthufftreek.str:hufftreek.bitst;coutendlendl; for(char ch;in.get(ch);) /将逍遥游文件中各个字符转变成相应的编码，写入编码后的文件中if(int)ch0) cha=(int)ch+256;else cha=(int)ch;for(int j=0;jnum;j+)if(hufftreej.str=cha)outhufftreej.bits;cout编码成功！b;) if(b=0)i=hufftreei.lchild;else i=hufftreei.rchild;if(hufftreei.lchild=-1)out(char)hufftreei.str;i=2*num-2;cout译码成功！endl;/-（2）算法二设计用HuffmanRun.cpp保存如下：#include#includeHuffmanTree.husing namespace std;/-void Run:runhuffman(char wen)ifstream in(wen);int wMaxSize;int weightMaxSize; /存放各个字符的频率int strMaxSize; /存放逍遥游文件中各个字符在数组w中的位置(下标)int i=0;int n=0;int cha=0;for(int j=0;jMaxSize;j+)wj=0;/*从文件逍遥游中依次读入字符，根据字符的ASCII码值将字符存入str数组的相应位置 而weight数组的相应位置则记录该字符出现的频率*/for(char ch;in.get(ch);) if(int)ch0) cha=(int)ch+256; /中文的ASCII码值为负数，加上256使其可以存放在数组中else cha=(int)ch;wcha+;for(int k=0;kMaxSize;k+)if(wk!=0)strn=k;weightn=wk;n+;cout字符在数组中的下标及其权值如下：; /输出字符在数组中的位置及其权值for(int p=0;pn;p+)if(p%6=0)coutendl;coutstrp:weightpt;coutendlcha;) /将文件逍遥游的内容读入数组stringastringai=cha;i+;stringai=0;for(char chc;incchc;) /将译码后的文件内容读入数组stringcstringcj=chc;j+;stringcj=0;/*比较文件逍遥游和译码后的文件内容，若相同则说明编码正确，若不同， 则说明编码错误*/for(int k=0;stringak!=0&stringck!=0;k+) if(stringak!=stringck) flag=0;if(stringak=0&stringck=0) flag=1;else flag=0; if(flag=0)cout逍遥游文件与译码后的文件不相同，编码错误！endl;elsecout逍遥游文件与译码后的文件相同，编码正确！endl;/-（3）实现算法设计的主程序用HaffmanMain.cpp保存如下：#include#includeHuffmanTree.husing namespace std;void main()char wenjian20;int t=1;while(1)if(t=1)coutwenjian;Run manager;manager.runhuffman(wenjian);pare(wenjian);elsecoutwenjian;Run manager;manager.huffman(wenjian);cout请继续选择需要执行的功能：endl;cout请问您