数据结构课设报告 哈弗曼编译码器.doc

西 安 邮 电 大 学 （计算机学院）数据结构课程设计报告题 目： 哈弗曼编/译码器 专业名称： 计算机科学与技术班 级： 计科1505 学生姓名： 常昊学号（8位）： 04151160指导教师：设计起止时间： 2016年12月26日2016年12月30日一. 设计目的1. 训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；4. 训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。二. 设计内容利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。三概要设计1. 建立哈夫曼树：读入文件(*.souce)，统计文件中字符出现的频度，并以这些字符的频度作为权值，建立哈夫曼树。这一步需要做字符的统计所以考虑到大量数据的处理，需要考虑时间复杂度带来的影响。所以采用牺牲一定的存储空间的方法，以哈希表的方法完成统计。因为字符的ascll码是0128不重复的整数，所以采用不散列的简单哈希表。（例如：对于abcdabbccc的串的处理遍历字符串，HZArraychari.HZ+）。在完成频数的统计后，下一步对整个128的数组中的频数非零的字符按照从小到大的顺序排序。考虑到稳定/非稳定排序对于本题没有什么影响，而且对于128的排序总数来说各种排序的方法时间复杂度相对计算机的性能不会相差多少，所以采用简单冒泡排序，而且，每次的排序实际数量都不会很多，加上flag的优化以后排序效率还是不错的。完成排序后，根据哈弗曼树的性质，直接依据有序序列建立哈弗曼树。这里没有采用书上的方法，书上的那个三叉链表实际上是有缺点的，所以这里采用我自己的算法去建立哈夫曼树，融合了广义表的概念，talk is cheap，show me the code，在后面的代码部分会讲清楚的。2. 编码：利用已建立好的哈夫曼树，获得各个字符的哈夫曼编码，并对正文进行编码，然后输出编码结果，并存入文件(*.code)中。前面建立哈弗曼树的过程中直接把对应字符的哈夫曼编码存到一个用作缓存的数组中，例如codeArraya.code对应的串是0000，这里也用到了简单哈希表的思维，减少了时间复杂度。然后去获取正文。获取正文有两种方式：自由录入、读取文件。获取到正文以后，直接遍历字串，并连续输出对应字符的哈弗曼编码。例如：puts（codeArraychara.data.code）。并同时把哈夫曼编码strcat到编码总串中，便于保存。然后将处理完成的总串显示到0、1码的显示区。如果用户输入了保存（*.code）文件的路径，等待用户按下“save the code”就会执行0、1的位运算数据压缩模块，然后会将压缩后的数据存到指定路径下并显示存储文件成功。3. 译码：利用已建立好的哈夫曼树将文件(*.code)中的代码进行译码，并输出译码结果，并存入文件(*.decode)中。译码的操作和编码类似，也是两种录入0、1的方式，不同之处只在于译码在读取文件时候需要先对压缩过的文件执行解压的操作，使之变为0、1的字符串，进一步对建立好的哈夫曼树进行0左1右的方式去遍历哈弗曼树。由于之前建立的哈弗曼树不同于课本，所以这里的遍历方式也是不同的，但是原理大同小异。其他的操作也和编码的过程大致相同。4. 利用位操作，实现文件的压缩与解压。（选作）我的想法是：01码如果用char类型的数据去存储的话是很浪费空间的。因为char是占一字节的空间的，意味着存储0、1的信息是存储了00000000、00000001。其实那么多0是不用存储的。所以用位运算的指定位置0、置1的原理，使得连续字节的位都可以用来直接存储0、1。所以用unsign int来存放0、1的位，这样相当于一个无符号的整数可以存储32位0、1信息，压缩比相当感人。具体的代码会放在下面的代码部分。1功能模块图；2各个模块详细的功能描述。输入输出：因为该程序使用了UI界面的交互设计，所以可以支持ipad设备或者在桌面模拟器的环境中进行触摸、鼠标点击的操作。该部分的代码是用objectivec写的。因为界面的操作响应是实时的，所以程序运行期间可以重复操作。读写文件：读、写的操作是用C语言的FILE的操作函数完成的。建树模块：对已有序的节点数组建立树并没有按照书上的方法前叶子后非叶子节点，而是直接以各层的叶子节点作为子树的根节点来使用，使用时让左孩子指向左子树的根节点，右孩子指向自身，最底层的叶子节点的左孩子指向0，右孩子指向自身。（指向0的原因是：128个ascll码表示的字符一定有的是不能直接从键盘上输入的，所以排序完成后前面的0一定不会是有效值），从而解决了数组的大小的2n+1的问题，这时候只要大小为128的数组即可完成统计、建树。编码模块：逐个扫描字符，然后根据已经建立起来的码值数组直接转换文本为码值。其中码值数组可以在哈夫曼树的建立过程中直接完成。解码模块：解码实际上是一个对哈夫曼树的指定路径遍历。因为哈夫曼编码是前缀码，所以直接根据遍历树的情况去解码。因为待解码的是一个0、1的字符串，所以可以从前到后去依照0遍历左子树1右子树的原则去遍历建立好的哈夫曼树。但是因为哈夫曼树的结构差异，这里遍历的时候判断叶子节点的方式不同于传统的。压缩/解压模块：压缩减压模块采用的位运算较为简单。通过判断0、1串的信息采用位置数的思维去实现，因为是以unsign的变量作为存储的单元，所以每个unsign变量可以存储32位1、0信息。所以采用了unsign的数组，这样数组越大，存储的量就越大（32*N位）。解压模块原理相同，不过不同的是要逐步确定unsign数组里的数的指定位是0还是1，同样运算也比较简单。四详细设计initgetHZaddSouceFile1功能函数的调用关系图buildaddToBeDecodeFileaddToBeCodeFilebuildthecachecodeTo01decodeToMassagesaveCodeFilesaveDeCodeFile带符号的为随用户操作调用的入口函数。编码文件输出编码输入文本/文本文件2各功能函数的数据流程图编码/译码文本文件输出文本输入编码/编码文件3重点设计及编码void getHZ()/统计频数 int i=0,j; HZarray temp; for(i=0;i100;i+) if(!ai) break; else if(ai!=n) j=ai; bj.HZ+; for(i=0;i128;i+)/简单排序 for(j=i;jbj.HZ) temp=bi; bi=bj; bj=temp; void build()/二叉树建立 int i=0,j=0,now=1; while(bnow.HZ=0) now+; i=j=now; now+=1; while(bnow.HZ=0&now128) if(bi.sum!=0&bj.sum!=0) if(bi.sum=bj.sum) bnow.sum=bi.sum+bnow.HZ; bnow.right=now; bnow.left=i; i=now; else bnow.sum=bj.sum+bnow.HZ; bnow.right=now; bnow.left=j; j=now; else j=now+1; if(bnow-2.HZ=0) bnow.sum=bi.HZ+bnow.HZ; bnow.left=i; bnow.right=now; i=now; now=i+1;j=now+1; if(bi.sum=bj.HZ) bnow.sum=bi.sum+bnow.HZ; bnow.left=i; bnow.right=now; i=now; else bj.sum=bnow.HZ+bj.HZ; bj.left=now; bj.right=j; now=j; now+; root.sum=bi.sum+bj.sum; root.left=i; root.right=j; return ;-(void)decodeToMassage/解码 if (_pathOfFile.text isEqualToString:) _ForNow setText:please load the souce file first.; return; NSMutableString*temp=NSMutableString allocinitWithString:_toBeDecode.text; /temp appendString:NSString stringWithFormat:%c,temp NSMutableString *tmpCode=NSMutableString allocinit; HZarray p=root; for (NSInteger i=0; itemp.length; i+) if(temp characterAtIndex:i=0) p=bp.left; if(p.left=0) tmpCode appendString:NSString stringWithFormat:%c,p.data; p=root; continue; else if (p.sum=root.sum) p=broot.right; else tmpCode appendString:NSString stringWithFormat:%c,p.data; p=root; continue; _ForNow setText:decoded successfully.; _toBeCode setText:tmpCode; tmpCode setString:;-(void)codeTo01/编码 if (_pathOfFile.text isEqualToString:) _ForNow setText:please load the souce file first.; return; NSString *temp=NSString allocinit; temp=_toBeCode.text; char tmp; NSMutableString *tempCode=NSMutableString allocinit; /NSLog(%,temp); for (NSInteger i=0; itemp.length; i+) tmp=temp characterAtIndex:i; /printf(%c %sn,tmp,theCodetmp.code); if(strlen(theCodetmp.code)1) _ForNow setText: NSString stringWithFormat:warning! %c is not in souce file.,tmp; return; tempCode appendString: NSString stringWithUTF8String:theCode(int)tmp.code; /NSLog(%,tempCode); _toBeDecode setText:NSString stringWithString:tempCode ; _ForNow setText:coded successfully.; tempCode setString:;/此段为位运算的压缩过程unsigned int s10=0,temp2=2147483648; char a500=0; /char b100=0; int i=0,n; int flag; strcpy(a, file); flag=1; for(n=0;(n10)&(istrlen(a);n+,flag=0) for(;i1) break; else flag=1; if(ai=1) sn=(temp2(i%32); /此段为解压缩的过程unsigned int s10=0,k,temp=2147483648; char a100=0; char b100=0; int i=0,n;int flag;k=s0; i=0; flag=1; for(n=0;(n10)&(istrlen(a);n+,flag=0) for(;i1) break; else flag=1; if(sn(i%32) bi=0; else bi=1; /printf(n%udn,sn); puts(b); return ;五测试数据及运行结果1正常测试数据和运行结果正确解码正确编码成功创建错误后缀文件依然保存2异常测试数据及运行结果未输入文件名依然提示正确保存六调试情况，设计技巧及体会调试情况：主要是在位运算的调试过程出现了很多未知情况，通过断点调试逐渐排除了故障。在树的操作过程中因为自己写了一种新的树的结构