数据结构的课设

目录第1章问题描述假设某文档只包含26个英文字母，应用哈夫曼算法对该文档进行压缩和解压缩操作，使得该文档占用较少的存储空间。一个较大的文件经过压缩后，产生了另外的一个较小容量的文件，我们就叫他是这些文件较大容量的（可能一个或一个以上的文件）的压缩文件。而压缩此文件的过程称为文件压缩。要使用这些经过压缩的文件，您就必须将这些经过压缩的文件还原成可以处理或执行的文件格式。目前网络上有两种常见的压缩格式：一种是zip，另一种是EXE。其中zip的压缩文件可以通过Winzip这套解压缩工具进行解压，而EXE文件内含解压缩程序，因此会比zip略大一些。若想充分考虑到文件容量的大小，其实zip是一个较佳的选择。而我们这个程序则可以将您选择的文件压缩成您需要的任意的格式。第2章基本要求（1）假设文档内容从键盘输入；（2）设计哈夫曼算法的存储结构；（3）设计哈夫曼编码和解码算法；（4）分析时间复杂度和空间复杂度。第3章概要设计3.1数据结构的设计对于给定的文档，首先通过扫描确定文档中出现了哪些英文字母以及出现的次数，以出现的次数作为叶子结点的权值构造哈夫曼树，获得个字符的哈夫曼编码；然后在扫描一次文档将其进行哈夫曼压缩编码，将文本文档换为二进制编码输出；最后将二进制流进行解码，并与原文档进行对照，以验证算法的正确性。图3-1哈夫曼编码树字符频率编码A3511B2500C1501D15101E10110图3-2字符编码3.2算法的设计利用Huffman编码树求得最佳的编码方案。根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图6所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。构造哈夫曼树的伪代码如下：1.数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1；2.数组huffTree的前n个元素的权值置给定权值w[n]；3.进行n-1次合并3.1在二叉树集合中选取两个权值最小的根结点，其下标分别为i1,i2；3.2将二叉树i1、i2合并为一棵新的二叉树k；在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。3.3抽象数据类型的设计ADTTreeData树是由一个根结点和若干棵子树构成，树中结点具有相同数据类型及层次关系OperationInitTree前置条件：树不存在输入：无功能：初始化一棵树输出：无后置条件：构造一棵树DestroyTree前置条件：树已存在输入：无功能：销毁一棵树输出：无weightlchildrchildparent图3-1哈夫曼树的结点结构后置条件：释放该树占用的存储空间PreOrder前置条件：树已存在输入：无功能：前序遍历树输出：树的前序遍历序列后置条件：树保持不变PostOrder前置条件：树已存在输入：无功能：后序遍历树输出：树的后序遍历序列后置条件：树保持不变LeverOrder前置条件：树已存在输入：无功能：层序遍历树输出：树的层序遍历序列后置条件：树保持不变第4章详细设计4.1设计抽象数据类型对应的C++类定义4.2设计每个成员函数1）二进制转化字符函数函数名：unsignedcharctobi(chara[])操作结果：将数组的前八位转成二进制形式比特位2）寻找字符的编码串函数函数名：char*code(unsignedchartemp,intleaf)操作结果：寻找对应字符的编码串，并返回3）文件压缩函数函数名：voidcompress(char*infilename,char*outfilename)操作结果：丢文件进行压缩4）字符转换二进制函数函数名：voidctobi(unsignedchara,charcode[])操作结果：字符转为二进制形式存入8位数组5）匹配函数函数名：intstrcmp1(charbuf[],structnodenode[],intn,unsignedchar&c)操作结果：将buf字符串与noder[i].bits[]中匹配，成功后对应的字符由c带回6）文件解压函数函数名：voiduncompress(char*infilename,char*outfilename)操作结果：丢文件进行解压7）主菜单函数函数名：voidMainMeun()操作结果：显示主菜单8）文件显示函数函数名：voidshow()操作结果：显示文件内容9）文件显示函数函数名：voidhelp()操作结果：显示帮助信息4.3设计主函数主菜单控制函数函数名：intmain()操作结果：a)文件压缩b)文件解压c)显示文件d)帮助菜单e)退出程序第5章运行与测试5.1在调试程序的过程中遇到的问题及解决方法在最开始的时候，会出现很多的错误，在小组成员的共同努力下最后得到运行，但是还有很多的缺点，经过多次的修改，才真正的完成了本次的课程设计。5.2测试数据及测试结果第一组测试数据：[源文件]：1.txt[目标文件]：1.zip测试结果：在有程序的文件夹中不会解压出1.zip文件，因为在该文件中没有创建1.txt文件，所以无法进行压缩操作第二组测试数据：[源文件]：23.txt[目标文件]：24.zip测试结果：在该程序的文件夹中会出现24.zip文件，因为在进行压缩之前创建了23.txt文件第三组测试数据：[源文件]：24.zip[目标文件]：24.txt测试结果：在该程序的文件夹中会解压出24.txt文件，因为在进行解压之前已经创建了24.txt文件5.3程序清单及运行结果5.3.1程序清单#includeiostream#includefstream#includestring#includecmath#includeiomanipusingnamespacestd;structnode{unsignedcharb;//记录字符longweight;//权重intparent,lch,rch;//定义双亲，左孩子，右孩子charbits[256];//存放哈夫曼编码的数组}noder[512],tmp;//头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511unsignedcharctobi(chara[])/*将数组的前八位转成二进制形式比特位*/{unsignedcharc=0;for(inti=0;i8;i++)if(a[i]!=0){=c+(int)(a[i]-'0')*pow(2,8-1-i);}returnc;}char*code(unsignedchartemp,intleaf)//寻找对应字符的编码串，并返回{for(inti=0;ileaf;i++)if(temp==noder[i].b)returnnoder[i].bits;returnNULL;}voidcompress(char*infilename,char*outfilename){longflength=0;//记录压缩前文件长度longclength=8;//编码从偏移量8记录，统计压缩后编码长度加8intleaf;//定义叶子结点intpoint;//定义总结点unsignedchartemp;//定义unsignedchar类型，暂存文件中字符的中间变量/*********************************文件中字符频度************************************/for(inti=0;i256;i++){noder[i].weight=0;//初始化权重noder[i].b=(unsignedchar)i;//初始化字符}ifstreaminfile(infilename,ios::in|ios::binary);while(infile.peek()!=EOF){infile.read((char*)&temp,sizeof(unsignedchar));//读入一个字符noder[temp].weight++;//统计对应结点字符权重flength++;//统计文件长度}infile.close();//关闭文件for(i=0;i256-1;i++)//对结点进行冒泡排序,权重大的放在上面，编码时效率高for(intj=0;j256-1-i;j++)if(noder[j].weightnoder[j+1].weight){tmp=noder[j];noder[j]=noder[j+1];noder[j+1]=tmp;}for(i=0;i256;i++)if(noder[i].weight==0)break;leaf=i;//取得哈夫曼树中叶子结点数point=2*leaf-1;//取得哈夫曼树中总结点数目/**********************************根据频度建树*************************************/longmin;//尽量用long，如果文件过大，这里建树可能不是最优树了ints1,s2;for(i=leaf;ipoint;i++){min=999999999;for(intj=0;ji;j++)//挑权重最小的一个if(noder[j].parent==0&&noder[j].weightmin){min=noder[j].weight;s1=j;}noder[s1].parent=i;//填写第一个叶子结点信息min=999999999;for(j=0;ji;j++)//挑权重最小的第二个if(noder[j].parent==0&&noder[j].weightmin){min=noder[j].weight;s2=j;}noder[s2].parent=i;noder[i].weight=noder[s1].weight+noder[s2].weight;//填写父结点信息noder[i].lch=s1;noder[i].rch=s2;}/*********************************根据哈夫曼树编码**********************************/chartmp[256];//定义临时变量，暂存编码tmp[255]='\0';//添加结束标志intstart;intc;//记录当前叶结点下标intf;//存储父结点的下标for(i=0;ileaf;i++){start=255;//另开始等于数组最后位for(c=i,f=noder[i].parent;f!=0;c=f,f=noder[f].parent)//对叶结点进行编码if(noder[f].lch==c)tmp[--start]='0';elsetmp[--start]='1';strcpy(noder[i].bits,&tmp[start]);}/************************************对文件进行编码，写入新文件(核心)*********************************/infile.open(infilename,ios::in|ios::binary);//打开待压缩的文件infile.clear();infile.seekg(0);ofstreamoutfile(outfilename,ios::out|ios::binary);//打开压缩后将生成的文件outfile.write((char*)&flength,sizeof(long));//写入原文件长度charbuf[513]=\0;//初始化编码缓冲区outfile.seekp(8);//指针定向偏移量8while(infile.peek()!=EOF){infile.read((char*)&temp,sizeof(unsignedchar));//读入字符strcat(