《数据结构的课设》由会员分享，可在线阅读，更多相关《数据结构的课设（24页珍藏版）》请在金锄头文库上搜索。
1、目录第 1 章 问题描述假设某文档只包含26 个英文字母，应用哈夫曼算法对该文档进行压缩和解 压缩操作，使得该文档占用较少的存储空间。一个较大的文件经过压缩后，产生了另外的一个较小容量的文件，我们就叫他是这些文 件较大容量的（可能一个或一个以上的文件）的压缩文件。而压缩此文件的过程称为文件压 缩。要使用这些经过压缩的文件，您就必须将这些经过压缩的文件还原成可以处理或执行的 文件格式。目前网络上有两种常见的压缩格式：一种是zip,另一种是EXE。其中zip的压缩文件 可以通过Winzip这套解压缩工具进行解压，而EXE文件内含解压缩程序，因此会比zip略 大一些。若想充分考虑到文件容量的大小，其
2、实zip是一个较佳的选择。而我们这个程序则 可以将您选择的文件压缩成您需要的任意的格式。第 2 章 基本要求1）假设文档内容从键盘输入；2）设计哈夫曼算法的存储结构；3）设计哈夫曼编码和解码算法；4）分析时间复杂度和空间复杂度。第3章概要设计3.1数据结构的设计对于给定的文档，首先通过扫描确定文档中出现了哪些英文字母以及出现的次数，以出 现的次数作为叶子结点的权值构造哈夫曼树，获得个字符的哈夫曼编码；然后在扫描一次文 档将其进行哈夫曼压缩编码，将文本文档换为二进制编码输出；最后将二进制流进行解码, 并与原文档进行对照，以验证算法的正确性。图3-1哈夫曼编码树字符频率编码A3511B2500C1
3、501D15101E10110图3-2字符编码3.2 算法的设计利用 Huffman 编码树求得最佳的编码方案。根据哈夫曼算法，建立哈夫曼树时，可以将哈夫曼树定义为一个结构型的一维数组HuffTree,保存哈夫曼树中各结点的信息，每个结点包括：权值、左孩子、右孩子、双亲， 如图6所示。由于哈夫曼树中共有2n-1个结点，并且进行n-1次合并操作，所以该数组的 长度为 2n-1。weightlchildrchildparent图3-1哈夫曼树的结点结构构造哈夫曼树的伪代码如下：1.数组huffTree初始化，所有元素结点的双亲、左右孩子都置为-1；2. 数组huffTree的前n个元素的权值置给定
4、权值wn；3. 进行 n-1 次合并3.1在二叉树集合中选取两个权值最小的根结点，其下标分别为i1, i2；3.2将二叉树订、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字符串与no
7、deri.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.1在调试程序的
8、过程中遇到的问题及解决方法 在最开始的时候，会出现很多的错误，在小组成员的共同努力下最后得到运 行，但是还有很多的缺点，经过多次的修改，才真正的完成了本次的课程设计。 5.2测试数据及测试结果第一组测试数据：源文件：l.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 #include #include #include #include using namespace std;struct nodeunsigned char b; long weight; int parent,lch,rch; char bits256;/记录字符/权重/定义双亲，左孩子，右孩子/存放哈夫曼编码的数组noder512,tmp;/头部一要定设置至少512 个,因为结点最多可达256,所有结点数最多可达 511unsigned cha
10、r ctobi(char a)/*将数组的前八位转成二进制形式比特位*/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)/记录压缩前文lon
11、g flength=0;中字符频度件长度long clength=8;/编码从偏移量 8 记录，统计压缩后编码长度加 8int leaf;int point;unsigned char temp;/定义叶子结点/定义总结点/定义 unsigned char 类型，暂存文件中字符的中间变量/*1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1*rI-*/ / I /* 文 件*1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1*
12、*1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* / Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx /for(int i=0;i256;i+)noderi.weight=0;/初始化权重noderi.b=(unsigned char)i;/初始化字符ifstream infile(inf
13、ilename,ios:in|ios:binary);while(infile.peek()!=EOF)infile.read(char *)&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;n
14、oderj+1=tmp;for(i=0;i256;i+)if(noderi.weight=0) break;leaf=i;/取得哈夫曼树中叶子结点数point=2*leaf-1;/取得哈夫曼树中总结点数目/ Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx频度建树*1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* *1* / Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx Tx
