数据结构的课设.doc

《数据结构的课设.doc》由会员分享，可在线阅读，更多相关《数据结构的课设.doc（25页珍藏版）》请在三一办公上搜索。

1、精选优质文档-倾情为你奉上目录第1章 问题描述假设某文档只包含26个英文字母，应用哈夫曼算法对该文档进行压缩和解压缩操作，使得该文档占用较少的存储空间。一个较大的文件经过压缩后，产生了另外的一个较小容量的文件，我们就叫他是这些文件较大容量的（可能一个或一个以上的文件）的压缩文件。而压缩此文件的过程称为文件压缩。要使用这些经过压缩的文件，您就必须将这些经过压缩的文件还原成可以处理或执行的文件格式。目前网络上有两种常见的压缩格式：一种是zip，另一种是EXE。其中zip的压缩文件可以通过Winzip这套解压缩工具进行解压，而EXE文件内含解压缩程序，因此会比zip略大一些。若想充分考虑到文件容量的

2、大小，其实zip是一个较佳的选择。而我们这个程序则可以将您选择的文件压缩成您需要的任意的格式。 第2章 基本要求（1）假设文档内容从键盘输入；（2）设计哈夫曼算法的存储结构；（3）设计哈夫曼编码和解码算法；（4）分析时间复杂度和空间复杂度。第3章 概要设计3.1数据结构的设计对于给定的文档，首先通过扫描确定文档中出现了哪些英文字母以及出现的次数，以出现的次数作为叶子结点的权值构造哈夫曼树，获得个字符的哈夫曼编码；然后在扫描一次文档将其进行哈夫曼压缩编码，将文本文档换为二进制编码输出；最后将二进制流进行解码，并与原文档进行对照，以验证算法的正确性。图3-1哈夫曼编码树字符频率编码A3511B25

3、00C1501D15101E10110图3-2 字符编码3.2算法的设计利用Huffman编码树求得最佳的编码方案。根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree，保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲，如图6所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的长度为2n-1。weight lchild rchild parent 图3-1 哈夫曼树的结点结构 构造哈夫曼树的伪代码如下：1. 数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1； 2. 数组huffTree的前n个元

4、素的权值置给定权值wn； 3. 进行n-1次合并 3.1 在二叉树集合中选取两个权值最小的根结点，其下标分别为i1, i2； 3.2 将二叉树i1、i2合并为一棵新的二叉树k； 在哈夫曼树中，设左分支为0，右分支为1，从根结点出发，遍历整棵哈夫曼树，求得各个叶子结点所表示字符的哈夫曼编码。3.3抽象数据类型的设计ADT TreeData树是由一个根结点和若干棵子树构成，树中结点具有相同数据类型及层次关系OperationInitTree前置条件：树不存在输入：无功能：初始化一棵树输出：无后置条件：构造一棵树DestroyTree前置条件：树已存在输入：无功能：销毁一棵树输出：无后置条件：释放该

5、树占用的存储空间PreOrder前置条件：树已存在输入：无功能：前序遍历树输出：树的前序遍历序列后置条件：树保持不变PostOrder前置条件：树已存在输入：无功能：后序遍历树输出：树的后序遍历序列后置条件：树保持不变LeverOrder前置条件：树已存在输入：无功能：层序遍历树输出：树的层序遍历序列后置条件：树保持不变第4章 详细设计4.1设计抽象数据类型对应的C+类定义4.2设计每个成员函数1）二进制转化字符函数 函数名：unsigned char ctobi(char a) 操作结果：将数组的前八位转成二进制形式比特位 2）寻找字符的编码串函数 函数名：char *code(unsign

6、ed char temp,int leaf) 操作结果：寻找对应字符的编码串，并返回 3）文件压缩函数 函数名：void compress(char *infilename,char *outfilename) 操作结果：丢文件进行压缩 4）字符转换二进制函数 函数名：void ctobi(unsigned char a,char code) 操作结果：字符转为二进制形式存入8位数组5）匹配函数 函数名：int strcmp1(char buf,struct node node,int n,unsigned char &c) 操作结果：将buf字符串与noderi.bits中匹配，成功后对应的

7、字符由c带回6）文件解压函数 函数名：void uncompress(char *infilename,char *outfilename) 操作结果：丢文件进行解压7）主菜单函数 函数名：void MainMeun() 操作结果：显示主菜单8）文件显示函数 函数名：void show() 操作结果：显示文件内容9）文件显示函数 函数名：void help() 操作结果：显示帮助信息4.3设计主函数主菜单控制函数 函数名：int main() 操作结果：a) 文件压缩 b) 文件解压 c) 显示文件 d) 帮助菜单 e) 退出程序第5章 运行与测试5.1在调试程序的过程中遇到的问题及解决方法在

8、最开始的时候，会出现很多的错误，在小组成员的共同努力下最后得到运行，但是还有很多的缺点，经过多次的修改，才真正的完成了本次的课程设计。5.2测试数据及测试结果第一组测试数据：源文件：1.txt目标文件：1.zip测试结果：在有程序的文件夹中不会解压出1.zip文件，因为在该文件中没有创建1.txt文件，所以无法进行压缩操作第二组测试数据：源文件：23.txt目标文件：24.zip测试结果：在该程序的文件夹中会出现24.zip文件，因为在进行压缩之前创建了23.txt文件第三组测试数据：源文件：24.zip 目标文件：24.txt测试结果：在该程序的文件夹中会解压出24.txt文件，因为在进行解

9、压之前已经创建了24.txt文件5.3程序清单及运行结果5.3.1程序清单#include #include #include #include #include using namespace std;struct nodeunsigned char b; /记录字符long weight; /权重int parent,lch,rch; /定义双亲，左孩子，右孩子char bits256; /存放哈夫曼编码的数组noder512,tmp; /头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511unsigned char ctobi(char a) /*将数组的前八位转

10、成二进制形式比特位*/unsigned char c=0;for(int i=0;i8;i+) if(ai!=0) =c+(int)(ai-0)*pow(2,8-1-i); return c;char *code(unsigned char temp,int leaf) /寻找对应字符的编码串，并返回for(int i=0;ileaf;i+) if(temp=noderi.b) return noderi.bits;return NULL;void compress(char *infilename,char *outfilename)long flength=0; /记录压缩前文件长度lon

11、g clength=8; /编码从偏移量8记录，统计压缩后编码长度加8int leaf; /定义叶子结点int point; /定义总结点unsigned char temp; /定义unsigned char类型，暂存文件中字符的中间变量/*文件中字符频度*/for(int i=0;i256;i+) noderi.weight=0; /初始化权重 noderi.b=(unsigned char)i; /初始化字符ifstream infile(infilename,ios:in|ios:binary);while(infile.peek()!=EOF) infile.read(char *)

12、&temp,sizeof(unsigned char); /读入一个字符 nodertemp.weight+; /统计对应结点字符权重 flength+; /统计文件长度infile.close(); /关闭文件for(i=0;i256-1;i+) /对结点进行冒泡排序,权重大的放在上面，编码时效率高 for(int j=0;j256-1-i;j+) if(noderj.weightnoderj+1.weight) tmp=noderj; noderj=noderj+1; noderj+1=tmp; for(i=0;i256;i+) if(noderi.weight=0) break;leaf

13、=i; /取得哈夫曼树中叶子结点数point=2*leaf-1; /取得哈夫曼树中总结点数目/*根据频度建树*/long min; /尽量用long，如果文件过大，这里建树可能不是最优树了int s1,s2;for(i=leaf;ipoint;i+) min=; for(int j=0;ji;j+) /挑权重最小的一个 if(noderj.parent=0&noderj.weightmin) min=noderj.weight; s1=j; noders1.parent=i; /填写第一个叶子结点信息 min=; for(j=0;ji;j+) /挑权重最小的第二个 if(noderj.pare

14、nt=0&noderj.weightmin) min=noderj.weight; s2=j; noders2.parent=i; noderi.weight=noders1.weight+noders2.weight; /填写父结点信息 noderi.lch=s1; noderi.rch=s2;/*根据哈夫曼树编码*/char tmp256; /定义临时变量，暂存编码tmp255=0; /添加结束标志int start;int c; /记录当前叶结点下标int f; /存储父结点的下标for(i=0;i=8) /当buf中字符长度大于8时，一直处理写入，直至小于8 temp=ctobi(bu

15、f); /上面临时变量已经完成使命，可以赋新值了 outfile.write(char *)&temp,sizeof(unsigned char); /转成二进制写入 clength+; /统计代码结尾偏移加1,用于找到叶子结点位置 strcpy(buf,buf+8); /字符串前移八位 /当此循环结束时，表示buf中已经小于8了，没到文件末尾，读下一个，继续，否则退出 /while 此层循环退出时，表示已到末尾,再判断buf中是否写完，没写完，连满至少8个字符，再写一个字节，就够了if(strlen(buf)0) strcat(buf,); temp=ctobi(buf); /前八位转成二进

16、制形式 outfile.write(char *)&temp,sizeof(unsigned char); clength+; /统计代码结尾偏移加1,用于找到叶子结点位置outfile.seekp(4);outfile.write(char *)&clength,sizeof(long); /写入文件中将记录叶子结点位置infile.close(); /*将字符编码对照表写入文件*/long bytelen; /记录编码以二进制存储时需要占多少个字节outfile.clear();outfile.seekp(clength); /将文件指针移到编码后面的第一位置，在此处记录叶子结点数outf

17、ile.write(char *)&leaf,sizeof(long); /写入叶子结点数for(i=0;ileaf;i+) outfile.write(char *)&noderi.b,sizeof(unsigned char); /写入字符 noderi.weight=strlen(noderi.bits); /不再设置其他变量,权值这时已无使用价值,可以用相应结点的权值变量记录长度 outfile.write(char *)&noderi.weight,sizeof(unsigned char); /写入长度的ASCII码 if(noderi.weight%8=0) bytelen=no

18、deri.weight/8; else bytelen=noderi.weight/8+1; strcat(noderi.bits,); /在编码后面补0，使其最后凑满8的倍数， /超过无妨，可以用bytelen控制好写入字节的长度 for(int j=0;jbytelen;j+) temp=ctobi(noderi.bits); outfile.write(char *)&temp,sizeof(unsigned char); strcpy(noderi.bits,noderi.bits+8); cout该文件的哈夫曼的编码为:endl; for(i=0;iflength;i+) coutn

19、oderi.bitsendl; /此循环结束后就完成了编码对照表的写入/compressvoid ctobi(unsigned char a,char code) /*字符转为二进制形式存入8位数组*/ int n=9;for(int i=0;i0) coden-=c%2+0; c=c/2;int strcmp1(char buf,struct node node,int n,unsigned char &c) /将buf字符串与noderi.bits中匹配，成功后对应的字符由c带回for(int i=0;in;i+)if(strcmp(buf,nodei.bits)=0) c=nodei.b

20、; return 1;return 0;void strcpy1(char buf,char a,int j) /将字符串a中长度为j的部分复制到buf数组中for(int i=0;ij;i+)bufi=ai;bufi=0;void uncompress(char *infilename,char *outfilename)long flength; /定义原文件长度，从压缩后文件前四字节获取值long clength; /获取编码长度后的第一偏移量,从压缩文件第五字节开始获取值int n; /叶子结点数，从编码尾端开始获取string str; /读取编码到字符串,好进行统一解码char c

21、ode9; /将字符转为二进制数组形式暂存unsigned char temp; /读取字符存放此临时变量long readlen=0; /记录已经读取的长度(读文件解码时用)long writelen=0; /记录已经写入的字节long clen; /临时变量，读取字符编码对照表时使用/*读入必要的数据*/void ctobi(unsigned char a,char code); /需要调用的函数的声明ifstream infile(infilename,ios:binary);if(!infile) cerr文件打开失败endl; return;infile.read(char *)&f

22、length,sizeof(long); /读入原始文件长度，用于解码时判断infile.read(char *)&clength,sizeof(long); /读入叶子结点起始位置infile.seekg(clength);infile.read(char *)&n,sizeof(int); /读入叶子结点数/*读入编码对照表，放入noderi.bits数组中*/infile.seekg(clength+4); /文件指针定位到字符编码对照表的起始for(int i=0;in;i+) /逐个读入叶子结点数，将编码进行读入 infile.read(char *)&noderi.b,sizeof

23、(unsigned char); /读入字符 infile.read(char *)&noderi.weight,sizeof(unsigned char); /读入编码长度 clen=(int)noderi.weight; int diff=clen%8; if(0=clen%8) /计算需要读取多少个字节 clen=clen/8; else clen=clen/8+1; noderi.bits0=0; /初始化，方便后面进行连接 for(int j=0;jclen;j+) /连接编码,使之存入noderi.bits中 infile.read(char *)&temp,1); ctobi(t

24、emp,code); strcat(noderi.bits,code); /将转换过来的编码进行连接 int bitlen=strlen(noderi.bits); if(0!=diff) noderi.bitsbitlen-8+diff=0;/for(int i=0;in;i+)/*对读入的编码对照表进行排序，长度短的排在前面*/for(i=0;in;i+) for(int j=0;jnoderj+1.weight) tmp=noderj; noderj=noderj+1; noderj+1=tmp; /*将编码读入内容，进行解码工作*/readlen=0;writelen=0;ofstre

25、am outfile(outfilename,ios:binary|ios:out); /打开编码后文件if(!outfile) cerr输出文件打开失败endl; return;char buf513=0; /读入编码缓冲区char buf1257=0;infile.seekg(8); /* 读取编码，解压连入缓冲区 */while(1) while(readlen(clength-8)&strlen(buf)=256) /处理缓冲区，直到少于256位，再读满它 for(i=0;i=flength) break; /如果写入达到原文件长度，退出 /while if(readlen=(clen

26、gth-8)/*编码长度*/|writelen=flength) break; /如果写入或者读入编码完毕，退出/退出此循环后，还有未解码完成的buf/对buf缓冲的善后处理while(writelenflength) for(i=0;istrlen(buf);i+) strcpy1(buf1,buf,i+1); if(strcmp1(buf1,noder,n,temp)=1) outfile.write(char *)&temp,sizeof(unsigned char); writelen+; strcpy(buf,buf+i+1); break; /forinfile.close();

27、/关闭文件outfile.close();/uncompress()void MainMeun() cout*哈夫曼编码/译码器*endl; coutendl; cout*Q-Quit*endl; cout*H-Help*endl; cout*C-Coding*endl; cout*D-Decoding*endl; cout*L-List Text Document*endl; void show() string contents; char filename200; /coutsfd; cout该文件的内容为：filename; ifstream in(filename,ios:out);

28、 while(!in.eof() incontents; coutcontents; void help()coutendl;cout 哈夫曼编码/译码器 endl;coutendl;cout使用说明:endl;coutendl;cout-1、压缩文件:-endl;coutendl;cout 在源文件中输入您所要压缩的文件!输入地格式为：路径压缩前文件名endl;cout 在目标文件中输入您压缩后将文件保存的地址!输入地格式为：路径压缩后文件名endl;cout 例如:源文件:d123.txt表示您要将D盘中123.txt文件进行压缩endl;cout 目标文件:d:123_new.COD表示

29、你将压缩后的文件保存在D盘123_new.COD文件中endl;coutendl;cout-2、解压文件:-endl;cout 在源文件中输入您所要解压的文件！输入地格式为：路径压缩前文件名endl;cout 在目标文件中输入您解压后将文件保存的地址!输入地格式为：路径压缩后文件名endl;cout 例如:源文件:d:123_new.COD表示你要将D盘中123_new.COD文件解压endl;cout 目标文件:d:123.txt表示您要将解压后的文件保存到D盘123.txt文件中endl;cout3) strcpy(select,cmdline1); strcpy(infilename,cmdline2); strcpy(outfilename,cmdline3);else if(num=1) MainMeun(); coutchoice; switch(choice) case C: coutinfilename; coutoutfilename; compress(infilename,outfilename);break; case D: coutinfilename; coutoutfilename; uncompress(infilename,outfilename);break; case H: help();break;