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

西安邮电大学（计算机学院）数据结构课程设计报告题目：哈弗曼编/译码器专业名称：计算机科学与技术班级：计科1505学生姓名：常昊学号（8位）：04151160指导教师：设计起止时间：2016年12月26日—2016年12月30日设计目的训练学生灵活应用所学数据结构知识，独立完成问题分析，结合数据结构理论知识，编写程序求解指定问题。初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的工作作风。设计内容利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。三．概要设计建立哈夫曼树：读入文件(*.souce)，统计文件中字符出现的频度，并以这些字符的频度作为权值，建立哈夫曼树。这一步需要做字符的统计所以考虑到大量数据的处理，需要考虑时间复杂度带来的影响。所以采用牺牲一定的存储空间的方法，以哈希表的方法完成统计。因为字符的ascll码是0~128不重复的整数，所以采用不散列的简单哈希表。（例如：对于abcdabbccc的串的处理——遍历字符串，HZArray[char[i]].HZ++）。在完成频数的统计后，下一步对整个128的数组中的频数非零的字符按照从小到大的顺序排序。考虑到稳定/非稳定排序对于本题没有什么影响，而且对于128的排序总数来说各种排序的方法时间复杂度相对计算机的性能不会相差多少，所以采用简单冒泡排序，而且，每次的排序实际数量都不会很多，加上flag的优化以后排序效率还是不错的。完成排序后，根据哈弗曼树的性质，直接依据有序序列建立哈弗曼树。这里没有采用书上的方法，书上的那个三叉链表实际上是有缺点的，所以这里采用我自己的算法去建立哈夫曼树，融合了广义表的概念，talkischeap，showmethecode，在后面的代码部分会讲清楚的。编码：利用已建立好的哈夫曼树，获得各个字符的哈夫曼编码，并对正文进行编码，然后输出编码结果，并存入文件(*.code)中。前面建立哈弗曼树的过程中直接把对应字符的哈夫曼编码存到一个用作缓存的数组中，例如codeArray[a].code对应的串是0000，这里也用到了简单哈希表的思维，减少了时间复杂度。然后去获取正文。获取正文有两种方式：自由录入、读取文件。获取到正文以后，直接遍历字串，并连续输出对应字符的哈弗曼编码。例如：puts（codeArray[char[a].data].code）。并同时把哈夫曼编码strcat到编码总串中，便于保存。然后将处理完成的总串显示到0、1码的显示区。如果用户输入了保存（*.code）文件的路径，等待用户按下“savethecode”就会执行0、1的位运算数据压缩模块，然后会将压缩后的数据存到指定路径下并显示存储文件成功。译码：利用已建立好的哈夫曼树将文件(*.code)中的代码进行译码，并输出译码结果，并存入文件(*.decode)中。译码的操作和编码类似，也是两种录入0、1的方式，不同之处只在于译码在读取文件时候需要先对压缩过的文件执行解压的操作，使之变为0、1的字符串，进一步对建立好的哈夫曼树进行0左1右的方式去遍历哈弗曼树。由于之前建立的哈弗曼树不同于课本，所以这里的遍历方式也是不同的，但是原理大同小异。其他的操作也和编码的过程大致相同。利用位操作，实现文件的压缩与解压。（选作）我的想法是：01码如果用char类型的数据去存储的话是很浪费空间的。因为char是占一字节的空间的，意味着存储0、1的信息是存储了00000000、00000001。其实那么多0是不用存储的。所以用位运算的指定位置0、置1的原理，使得连续字节的位都可以用来直接存储0、1。所以用unsignint来存放0、1的位，这样相当于一个无符号的整数可以存储32位0、1信息，压缩比相当感人。具体的代码会放在下面的代码部分。1．功能模块图；2．各个模块详细的功能描述。输入输出：因为该程序使用了UI界面的交互设计，所以可以支持ipad设备或者在桌面模拟器的环境中进行触摸、鼠标点击的操作。该部分的代码是用objective—c写的。因为界面的操作响应是实时的，所以程序运行期间可以重复操作。读写文件：读、写的操作是用C语言的FILE的操作函数完成的。建树模块：对已有序的节点数组建立树并没有按照书上的方法前叶子后非叶子节点，而是直接以各层的叶子节点作为子树的根节点来使用，使用时让左孩子指向左子树的根节点，右孩子指向自身，最底层的叶子节点的左孩子指向0，右孩子指向自身