完整word版数据结构课设报告word文档良心出品

1、西安邮电大学（计算机学院）数据结构课程设计报告题目：哈弗曼编/译码器计算机科学与技术专业名称：1505计科级：班常昊生姓名： 04151160 学号（8 位）：指导教师：设计起止时间： 日月年2016122612年日2016月30一. 设计目的1. 训练学生灵括应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程 序求解指定问题。2. 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3. 捉高综合运用所学的理论知识和方法独立分析和解决问题的能力：4. 训练用系统的观点和软件开发般规范进行软件开发，巩固、深化学生的理论知识，捉高编 程水平，并在此过程中培

2、养他们严谨的科学态度和良好的工作作风。二. 设计内容利用哈夫曼编码进行信息通信可以大人提高信道利用率，缩短信息传输时间，降低传输成本。但 是,这耍求在发送端通过个编码系统对待传数据预先编码，在接收端将传来的数据进行译码(复 原)。三. 概要设计1. 建立哈夫曼树：读入文件(*. souce),统计文件中字符出现的频度，并以这些字符的频度作为 权值，建立哈夫曼树。这步需要做字符的统计所以考虑到人量数据的处理，需要考虑时间复杂度带来的影响。所以采 用牺牲定的存储空间的方法，以哈希农的方法完成统计。因为字符的ascii码是0128不重复 的整数，所以采用不散列的简单哈希衣。(例如：对于abcdabb

3、ccc的串的处理遍历字符串， HZArray char i . HZ+)。在完成频数的统计后，下步对整个128的数组中的频数非零的字符按照从小到大的顺序扌II：序。 考虑到稳定/非稳定排序对于本题没有什么影响，而且对于128的排序总数来说各种排序的方法 时间复杂度相对计算机的性能不会和差多少，所以采用简单冒泡排序，而且，每次的扌II：序实际数 量都不会很多，加上flag的优化以后排序效率还是不错的。完成押:序后，根据哈弗曼树的性质，直接依据有序序列建立哈弗曼树。这里没有采用书上的方法， 书上的那个三叉链衣实际上是有缺点的，所以这里采用我自己的算法去建立哈夫曼树，融合了广 义衣的概念，talk

4、is cheap, show me the code,在后面的代码部分会讲清楚的。2. 编码：利用已建立好的哈夫曼树，获得各个字符的哈夫曼编码，并对正文进行编码，中。 (*. code)然后输出编码结果，并存入文件.前而建立哈弗曼树的过程中直接把对应字符的哈夫曼编码存到个用作缓存的数组中，例如 codeArrayEal.code对应的串是0000.这里也用到了简单哈希农的思维，减少了时间复杂度。 然后去获取正文。获取正文有两种方式：自由录入、读取文件。获取到正文以后，直接遍历字串，并连续输出对应字符的哈弗曼编码。例如：puts(codeArraycha讥a, data, code)。并同时把哈

5、夫曼编码strcat到编码总串中，便于保存。然 后将处理完成的总串显示到0、1码的显示区。如果用户输入了保存(*.code)文件的路径，等待用户按下“save the code”就会执行0、1 的位运算数据压缩模块，然后会将压缩后的数据存到指定路径下并显示存储文件成功。3. 译码：利用已建立好的哈夫曼树将文件（*. code）中的代码进行译码，并输出译码结果，并存 入文件（*. decode）中.译码的操作和编码类似，也是两种录入0、1的方式，不同之处只在于译码在读取文件时候需要 先对压缩过的文件执行解压的操作，使之变为0、1的字符串，进-步对建立好的哈夫曼树进行 0左1右的方式去遍历哈弗曼树

6、。由于之前建立的哈弗曼树不同于课本，所以这里的遍历方式也 是不同的，但是原理大同小异。其他的操作也和编码的过程大致和同。4. 利用位操作，实现文件的压缩与解压。（选作）我的想法是：01码如果用char类型的数据去存储的话是很浪费空间的。因为char是占字节 的空间的，意味着存储0、1的信息是存储f 00000000. 00000001 o其实那么多0是不用存储的。 所以用位运算的指定位置0、置1的原理，使得连续字节的位都可以用来直接存储0、K 所以用unsign int来存放0、1的位，这样和当于个无符号的整数可以存储32位0、1信息, 压缩比相当感人。具体的代码会放在下面的代码部分。.1.

7、功能模块图；.2. 各个模块详细的功能描述。输入输出：因为该程序使用了 口界面的交互设计，所以可以支持ipad设备或者在桌面模拟器 的环境中进行触摸、鼠标点击的操作。该部分的代码是用objective-c写的。因为界面的操作 响应是实时的，所以程序运行期间可以重复操作。读写文件：读、写的操作是用C语言的FILE的操作函数完成的。建树模块：对已有序的节点数组建立树并没有按照书上的方法前叶f后非叶/节点，而是直接以各层的叶/节点作为介树的根节点来使用，使用时让左孩了指向左了树的根节点, 右孩了指向自身，最底层的叶（节点的左孩了指向0,右孩/指向白身。（指向0的原冈是：128 个ascii码农示的字

8、符定有的是不能直接从键盘上输入的，所以排序完成后前而的0 定不会 是有效值）,从而解决了数组的人小的2n+l的问题，这时候只要人小为128的数组即可完成统计、 建树。编码模块：逐个扫描字符，然后根据已经建立起来的码值数组直接转换文本为码值。其中码值 数组可以在哈夫曼树的建立过程中直接完成。解码模块：解码实际上是个对哈夫曼树的指定路径遍历。因为哈夫曼编码是前缀码，所以直 接根据遍历树的情况去解码。因为待解码的是个0、1的字符串，所以可以从前到后去依照0 遍历左了树1右了树的原则去遍历建立好的哈夫曼树。但是因为哈夫曼树的结构差异，这里遍历 的时候判断叶子节点的方式不同于传统的。压缩/解压模块：压缩

9、减压模块采用的位运算较为简单。通过判断0、1串的信息采用位置数的 思维去实现，因为是以unsign的变量作为存储的单元，所以每个unsign变量可以存储32位1、 0信息。所以采用了 unsign的数组，这样数组越大，存储的量就越大（32*N位）。解压模块原理相同，不过不同的是要逐步确定unsign数组里的数的指定位是0还是1,同样运 算也比较简单。四. 详细设计1. 功能函数的调用关系图addSouceFile getHZ initbuildbuildthecache addToBeDecodeaddToBeCodecodeToOldecodeToMassagesaveDeCodeFiles

10、aveCodeFile带符号的为随用户操作调用的入口函数。.2 各功能函数的数据流程图文本文件输入文本/编码/译码输入编码/编码文 件成功创建输出编码编码文件正确编码文本文件输出文本重点设计及编码3统计频数void getHZ ()/ int i=0,j;HZarray temp;for(i=0;i100;i+)if (!ail)break;elseif (ai != n)J=ai；bEjl.HZ 卄；简单排序for (i=0; i128; i+) /for (j=i ;jbj.HZ)temp=bi;bi=bj;bj=temp;void build()/二叉树建立int i=0, j=0, n

11、ow=l:while (bnow. HZ=0) now+;i=j=now;now+=l;while (bnowj. HZ=0&now 128)if (bi sum!=0&bj. sum!=0)if (bLiZ sum=bj sum)b now. sum=b i sum+b now. HZ; b now. r i ght=now; bnow left二i;i=now;elsebnow. sum=b j sum+bnow HZ; b now. r i ght=now; bnow left=j;j=now; elsej=now+l;辻(bnow-2. HZ=O) b now. sum=b i HZ+

12、b now. HZ; bnow left=i;bnow. right=now;i=now;now二i+1;j=now+l;if (bi sum=bj.HZ)b now sum=b i sum+b now. HZ;bnow left=i;bnow right=now;i=now;elsebj sum=bnow. HZ+bj HZ;bj left二now;bj. right二j;now=j;now+;root sum=bLi_. sum+bj sum;root left二i;root right=j;return ;- (void) decodeToMassage/解码if (E_pathOfFi

13、le.text isEqualToString:) _ForNow setText:please load the souce file first; return;NSMutableString*temp=NSMutableStringalloc initWithString:_toBeDecode text;/tempappendString:NSStringstringWithFormat:temp.NSMutableString *tmpCode=NSMutableString allocj init;HZarray p=root;for (NSInteger i二0; itemp l

14、ength; i+) if (temp characterAtIndex:i=，0)P=bp left;if (p. left=0)tmpCode appendString:NSString stringWithFormat:p. data!;p=root;continue;elseif (p. sum二二root sum) p=broot right:elseappendString:NSStringtmpCodestringWithFormat:p. data!;p=root;continue;_ForNow setText:decoded successfully.;_toBeCode

15、setText:tmpCode:tmpCode setString:-(void) codeToOl/编码if (E_pathOfFile.text isEqualToString:) _ForNow setText:please load the souce file first; return;NSString *temp=NSString allocZ init;temp二_toBeCode text;char tmp;NSMutableString *tempCode=NSMutableString allocinit; /NSLogtemp);for (NSInteger i二0;

16、itemp length; i+) tmp=temp characterAtIndex:ij;/printf(%c %sn, tmp, theCodeEtmp_ code);if (strlen (theCodetmp code) 1) _ForNow setText: NSString stringWithFormat:warning! %cis not in souce filereturn;tempCodeappendString:NSStringstringWithUTF8String:theCode(int)tmp code;/NSLogtempCode);_toBeDecode s

17、etText: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=l;for(n=0;(n10)&(istrlen(a);n+, flag=0)for (;il)break; elseflag=l;辻(ai=l)sn (t

18、emp2 (i2);/此段为解压缩的过程unsigned int s10二0, k, temp二2147483648;char a100 = ，0;char b100 = ，0;int i=0, n;int flag;k二s0;i 二0;flag=l;for (n=0; (n10)&(il)break; elseflag=l;if (sn(sn厂(temp(i2) bi=J O;else/printf (%udn, sn);puts(b);return ;五. 测试数据及运行结果1.正常测试数据和运行结果正确解码果结运行据常2.异测试数及错谋后缀文件依然保住未输入文件名依然捉示正确保存.六. 调试情况，设计技巧及体会调试情况：主要是在位运算的调试过程出现了很多未知情况，通过断点调试逐渐拙除了故障。在树的操作过程中因为自己写了 种新的树的结构，所以也用了比较