数据结构的课设

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

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

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

4、2. 数组huffTree的前n个元素的权值置给定权值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）寻找字符的编码串函数 函数名

6、：char *code(unsigned 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字符串

7、与noderi.bits中匹配，成功后对应的字符由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

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

9、件夹中会解压出24.txt文件，因为在进行解压之前已经创建了24.txt文件5.3程序清单及运行结果5.3.1程序清单#include <iostream>#include <fstream>#include <string>#include <cmath>#include <iomanip>using namespace std;struct nodeunsigned char b; /记录字符long weight; /权重int parent,lch,rch; /定义双亲，左孩子，右孩子char bits256; /存放哈夫曼编

10、码的数组noder512,tmp; /头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511unsigned char ctobi(char a) /*将数组的前八位转成二进制形式比特位*/unsigned char c=0;for(int i=0;i<8;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;i<leaf;i+) if(temp=noderi

11、.b) return noderi.bits;return NULL;void compress(char *infilename,char *outfilename)long flength=0; /记录压缩前文件长度long clength=8; /编码从偏移量8记录，统计压缩后编码长度加8int leaf; /定义叶子结点int point; /定义总结点unsigned char temp; /定义unsigned char类型，暂存文件中字符的中间变量/*文件中字符频度*/for(int i=0;i<256;i+) noderi.weight=0; /初始化权重 noderi.

12、b=(unsigned char)i; /初始化字符ifstream infile(infilename,ios:in|ios:binary);while(infile.peek()!=EOF) infile.read(char *)&temp,sizeof(unsigned char); /读入一个字符 nodertemp.weight+; /统计对应结点字符权重 flength+; /统计文件长度infile.close(); /关闭文件for(i=0;i<256-1;i+) /对结点进行冒泡排序,权重大的放在上面，编码时效率高 for(int j=0;j<256-1-

13、i;j+) if(noderj.weight<noderj+1.weight) tmp=noderj; noderj=noderj+1; noderj+1=tmp; for(i=0;i<256;i+) if(noderi.weight=0) break;leaf=i; /取得哈夫曼树中叶子结点数point=2*leaf-1; /取得哈夫曼树中总结点数目/*根据频度建树*/long min; /尽量用long，如果文件过大，这里建树可能不是最优树了int s1,s2;for(i=leaf;i<point;i+) min=; for(int j=0;j<i;j+) /挑权重

14、最小的一个 if(noderj.parent=0&&noderj.weight<min) min=noderj.weight; s1=j; noders1.parent=i; /填写第一个叶子结点信息 min=; for(j=0;j<i;j+) /挑权重最小的第二个 if(noderj.parent=0&&noderj.weight<min) min=noderj.weight; s2=j; noders2.parent=i; noderi.weight=noders1.weight+noders2.weight; /填写父结点信息 noder

15、i.lch=s1; noderi.rch=s2;/*根据哈夫曼树编码*/char tmp256; /定义临时变量，暂存编码tmp255='0' /添加结束标志int start;int c; /记录当前叶结点下标int f; /存储父结点的下标for(i=0;i<leaf;i+) start=255; /另开始等于数组最后位 for(c=i,f=noderi.parent;f!=0;c=f,f=noderf.parent) /对叶结点进行编码 if(noderf.lch=c) tmp-start='0' else tmp-start='1'

16、 strcpy(noderi.bits,&tmpstart);/*对文件进行编码，写入新文件(核心)*/infile.open(infilename,ios:in|ios:binary); /打开待压缩的文件infile.clear();infile.seekg(0);ofstream outfile(outfilename,ios:out|ios:binary); /打开压缩后将生成的文件outfile.write(char *)&flength,sizeof(long); /写入原文件长度char buf513="0" /初始化编码缓冲区outfile.

17、seekp(8); /指针定向偏移量8while(infile.peek()!=EOF) infile.read(char *)&temp,sizeof(unsigned char); /读入字符 strcat(buf,code(temp,leaf); /检索出字符对应编码，连到buf中 while(strlen(buf)>=8) /当buf中字符长度大于8时，一直处理写入，直至小于8 temp=ctobi(buf); /上面临时变量已经完成使命，可以赋新值了 outfile.write(char *)&temp,sizeof(unsigned char); /转成二进制

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

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

20、i<leaf;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=noderi.weight/8; else bytelen=noderi.weight

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

22、h;i+) cout<<noderi.bits<<endl; /此循环结束后就完成了编码对照表的写入/compressvoid ctobi(unsigned char a,char code) /*字符转为二进制形式存入8位数组*/ int n=9;for(int i=0;i<n;i+) codei='0' /整个字符串初始化coden-1='0' /添加结束标志n=n-2;int c=(int)a;while(c>0) coden-=c%2+'0' c=c/2;int strcmp1(char buf,str

23、uct node node,int n,unsigned char &c) /将buf字符串与noderi.bits中匹配，成功后对应的字符由c带回for(int i=0;i<n;i+)if(strcmp(buf,nodei.bits)=0) c=nodei.b; return 1;return 0;void strcpy1(char buf,char a,int j) /将字符串a中长度为j的部分复制到buf数组中for(int i=0;i<j;i+)bufi=ai;bufi='0'void uncompress(char *infilename,char

24、 *outfilename)long flength; /定义原文件长度，从压缩后文件前四字节获取值long clength; /获取编码长度后的第一偏移量,从压缩文件第五字节开始获取值int n; /叶子结点数，从编码尾端开始获取string str; /读取编码到字符串,好进行统一解码char code9; /将字符转为二进制数组形式暂存unsigned char temp; /读取字符存放此临时变量long readlen=0; /记录已经读取的长度(读文件解码时用)long writelen=0; /记录已经写入的字节long clen; /临时变量，读取字符编码对照表时使用/*读入必

25、要的数据*/void ctobi(unsigned char a,char code); /需要调用的函数的声明ifstream infile(infilename,ios:binary);if(!infile) cerr<<"文件打开失败"<<endl; return;infile.read(char *)&flength,sizeof(long); /读入原始文件长度，用于解码时判断infile.read(char *)&clength,sizeof(long); /读入叶子结点起始位置infile.seekg(clength);

26、infile.read(char *)&n,sizeof(int); /读入叶子结点数/*读入编码对照表，放入noderi.bits数组中*/infile.seekg(clength+4); /文件指针定位到字符编码对照表的起始for(int i=0;i<n;i+) /逐个读入叶子结点数，将编码进行读入 infile.read(char *)&noderi.b,sizeof(unsigned char); /读入字符 infile.read(char *)&noderi.weight,sizeof(unsigned char); /读入编码长度 clen=(int

27、)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;j<clen;j+) /连接编码,使之存入noderi.bits中 infile.read(char *)&temp,1); ctobi(temp,code); strcat(noderi.bits,code); /将转换过来的编码进行连接 int bitlen=strlen(noderi.bits

28、); if(0!=diff) noderi.bitsbitlen-8+diff='0'/for(int i=0;i<n;i+)/*对读入的编码对照表进行排序，长度短的排在前面*/for(i=0;i<n;i+) for(int j=0;j<n-i-1;j+) if(noderj.weight>noderj+1.weight) tmp=noderj; noderj=noderj+1; noderj+1=tmp; /*将编码读入内容，进行解码工作*/readlen=0;writelen=0;ofstream outfile(outfilename,ios:bi

29、nary|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) /读满缓冲区 infile.read(char *)&temp,sizeof(temp)

30、; ctobi(temp,code); /将字节转为数组 strcat(buf,code); readlen+; /while while(strlen(buf)>=256) /处理缓冲区，直到少于256位，再读满它 for(i=0;i<strlen(buf);i+) strcpy1(buf1,buf,i+1); /逐渐增多取，放入buf1，进行匹配 if(strcmp1(buf1,noder,n,temp)=1) outfile.write(char *)&temp,sizeof(unsigned char); writelen+; strcpy(buf,buf+i+1)

31、; /缓冲区前移 break; /for if(writelen>=flength) break; /如果写入达到原文件长度，退出 /while if(readlen>=(clength-8)/*编码长度*/|writelen>=flength) break; /如果写入或者读入编码完毕，退出/退出此循环后，还有未解码完成的buf/对buf缓冲的善后处理while(writelen<flength) for(i=0;i<strlen(buf);i+) strcpy1(buf1,buf,i+1); if(strcmp1(buf1,noder,n,temp)=1) o

32、utfile.write(char *)&temp,sizeof(unsigned char); writelen+; strcpy(buf,buf+i+1); break; /forinfile.close(); /关闭文件outfile.close();/uncompress()void MainMeun() cout<<"*哈夫曼编码/译码器*"<<endl; cout<<endl; cout<<"*Q-Quit*"<<endl; cout<<"*H-Help

33、*"<<endl; cout<<"*C-Coding*"<<endl; cout<<"*D-Decoding*"<<endl; cout<<"*L-List Text Document*"<<endl; void show() string contents; char filename200; /cout<<"sfd" cout<<"该文件的内容为："<<endl;

34、 cin>>filename; ifstream in(filename,ios:out); while(!in.eof() in>>contents; cout<<contents; void help()cout<<endl;cout<<" 哈夫曼编码/译码器 "<<endl;cout<<endl;cout<<"使用说明:"<<endl;cout<<endl;cout<<"-1、压缩文件:-"<

35、<endl;cout<<endl;cout<<" 在源文件中输入您所要压缩的文件!输入地格式为：路径压缩前文件名"<<endl;cout<<" 在目标文件中输入您压缩后将文件保存的地址!输入地格式为：路径压缩后文件名"<<endl;cout<<" 例如:源文件:d123.txt表示您要将D盘中123.txt文件进行压缩"<<endl;cout<<" 目标文件:d:123_new.COD表示你将压缩后的文件保存在D盘123_n

36、ew.COD文件中"<<endl;cout<<endl;cout<<"-2、解压文件:-"<<endl;cout<<" 在源文件中输入您所要解压的文件！输入地格式为：路径压缩前文件名"<<endl;cout<<" 在目标文件中输入您解压后将文件保存的地址!输入地格式为：路径压缩后文件名"<<endl;cout<<" 例如:源文件:d:123_new.COD表示你要将D盘中123_new.COD文件解压&quo

37、t;<<endl;cout<<" 目标文件:d:123.txt表示您要将解压后的文件保存到D盘123.txt文件中"<<endl;cout<<endl;int main(int num,char *cmdline) char infilename256,outfilename256,select255; char choice; if(num>3) strcpy(select,cmdline1); strcpy(infilename,cmdline2); strcpy(outfilename,cmdline3);else if(num=1) MainMeun(); cout<<"请输入您的选项(Q/H/C/D):" cin>>choice; switch(