数据结构课设报告.docx

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