哈夫曼编译码器课程设计报告

数据结构数据结构 课程设计报告课程设计报告 题目 哈夫曼编 译码器 专业 计算机科学与技术 对口 班级 13 3 姓名 陈霞 指导教师 彭飞 成绩 计算机学院计算机学院 20152015 年年 1111 月月 1212 日日 学号学号1508 2015 2016 学年学年 第第 1 学期学期 计算机学院 数据结构 课程设计报告 1 目录目录 1设计内容及要求 3 1 1 内容 3 1 2 要求 3 2概要设计 4 2 1 抽象数据类型定义 4 2 2 模块划分 4 3设计过程及代码 5 3 1 设计过程 5 3 2 代码 7 4设计结果与分析 10 5参考文献 12 计算机学院 数据结构 课程设计报告 1 1设计内容及要求设计内容及要求 1 11 1 内容内容 利用哈夫曼编码进行信息通信可以大大提高信道利用率 缩短信息传输时间 降低传输成本 但是 这要求在发送端通过一个编码系统对待传数据预先编码 在 接收端将传来的数据进行译码 复原 对于双工信道 即可以双向传输信息的信 道 每端都需要一个完整的编 译码系统 试为这样的信息收发站写一个哈夫曼编 译码系统 1 21 2 要求要求 一个完整的系统应具有以下功能 1 I 初始化 Initialization 从终端读入字符集大小 n 以及 n 个字符和 n 个权值 建立哈夫曼树 并将它存于文件 hfmTree 中 2 E 编码 Encoding 利用已建好的哈夫曼树 如不在内存 则从文件 htmTree 中读入 对文件 ToBeTran 中的正文进行编码 然后将结果存入文件 CodeFile 中 3 D 译码 Decoding 利用已建好的哈夫曼树将文件 CodeFile 中的代码 进行译码 结果存入文件 TextFile 中 4 P 印代码文件 Print 将文件 CodeFile 以紧凑格式显示在终端上 每 行 50 个代码 同时将此字符形式的编码写入文件 CodePrint 中 5 T 印哈夫曼树 Tree Printing 将已在内存中的哈夫曼树以直观的方 式 树或凹入表形式 显示在终端上 同时将此字符形式的哈夫曼树写入文件 TreePrint 中 测试数据 1 数据一 已知某系统在通信联络中只可能出现 8 种字符 其概率分别为 0 05 0 29 0 07 0 08 0 14 0 23 0 03 0 11 以此设计哈夫曼编码 利用此数据对程序 进行 调试 2 用下表给出的字符集和频度的实际统计数据建立哈夫曼树 并实现以下报 文的编码和译码 THIS PROGRAM IS MY FAVORITE 字符 ABCDEFGHIJKLM 频度 1866413223210321154757153220 字符 NOPQRSTUVWXYZ 频度 5763151485180238181161 计算机学院 数据结构 课程设计报告 1 2概要设计概要设计 2 12 1抽象数据类型定义抽象数据类型定义 ADT Stack 数据对象 D ai ai ElemSet i 1 2 n n 0 数据关系 若 D 为空集 则称为空树 若 D 仅为一个数据元素 则 R 为空集 否则 R H H 是如下的二元关 系 1 再 D 中存在唯一的称为根的数据元素 root 它在关系 H 下无前驱 2 若 D root 空集 则存在一个划分 D1 D2 Dm m 0 3 对应于 D root 的划分 H root X1 有唯一的一个划分 H1 H2 Hm m 0 基本操作 InitTree 结点权值 int weight 权重 int parent 双亲结点 int lchild 左孩子 int rchild 右孩子 HTNode HTNode ht 30 2 求哈夫曼编码类型 typedef struct char cd 30 存放当前结点的哈弗曼编码 int start cd start cd n 存放哈弗曼码 HCode HCode hcd 30 计算机学院 数据结构 课程设计报告 1 2 主要模块的算法描述 计算机学院 数据结构 课程设计报告 1 开始 Int I i n Scanf d I 0 I n Hc start n c i F 1 multiplex Hc start I 主函数流程图 图 3 1 1 哈弗曼编码算法流程图 图 3 1 2 计算机学院 数据结构 课程设计报告 1 3 23 2代码代码 include define n 27 叶子数目 define m 2 n 1 结点总数 define maxval 10000 0 define maxsize 100 哈夫曼编码的最大位数 typedef struct char ch float weight int lchild rchild parent hufmtree typedef struct char bits n 位串 int start 编码在位串中的起始位置 char ch 字符 codetype void huffman hufmtree tree 建立哈夫曼树 void huffmancode codetype code hufmtree tree 根据哈夫曼树求出哈夫曼编码 void decode hufmtree tree 依次读入字符 根据哈夫曼树译码 int main printf 哈夫曼编码 n printf 总共有 d 个字符 n n hufmtree tree m codetype code n int i j 循环变量 huffman tree 建立哈夫曼树 huffmancode code tree 根据哈夫曼树求出哈夫曼编码 printf 输出每个字符的哈夫曼编码 n for i 0 i n i printf c code i ch for j code i start j n j printf c code i bits j printf n printf 读入字符 并进行译码 n decode tree 依次读入电文 根据哈夫曼树译码 void huffman hufmtree tree 建立哈夫曼树 计算机学院 数据结构 课程设计报告 1 int i j p1 p2 p1 p2 分别记住每次合并时权值最小和次小的两个根结点的下标 float small1 small2 f char c for i 0 i m i 初始化 tree i parent 0 tree i lchild 1 tree i rchild 1 tree i weight 0 0 printf 依次读入前 d 个结点的字符及权值 中间用空格隔开 n n for i 0 i n i 读入前 n 个结点的字符及权值 printf 输入第 d 个字符为和权值 i 1 scanf c f getchar tree i ch c tree i weight f for i n i m i 进行 n 1 次合并 产生 n 1 个新结点 p1 0 p2 0 small1 maxval small2 maxval maxval 是 float 类型的最大值 for j 0 j i j 选出两个权值最小的根结点 if tree j parent 0 if tree j weight small1 small2 small1 改变最小权 次小权及对应的位置 small1 tree j weight p2 p1 p1 j else if tree j weight small2 small2 tree j weight 改变次小权及位置 p2 j tree p1 parent i tree p2 parent i tree i lchild p1 最小权根结点是新结点的左孩子 计算机学院 数据结构 课程设计报告 1 tree i rchild p2 次小权根结点是新结点的右孩子 tree i weight tree p1 weight tree p2 weight huffman void huffmancode codetype code hufmtree tree 根据哈夫曼树求出哈夫曼编码 codetype code 为求出的哈夫曼编码 hufmtree tree 为已知的哈夫曼树 int i c p codetype cd 缓冲变量 for i 0 i n i cd start n cd ch tree i ch c i 从叶结点出发向上回溯 p tree i parent tree p 是 tree i 的双亲 while p 0 cd start if tree p lchild c cd bits cd start 0 tree i 是左子树 生成代码 0 else cd bits cd start 1 tree i 是右子树 生成代码 1 c p p tree p parent code i cd 第 i 1 个字符的编码存入 code i huffmancode void decode hufmtree tree 依次读入字符 根据哈夫曼树译码 int i j 0 char b maxsize char endflag 2 电文结束标志取 2 i m 1 从根结点开始往下搜索 printf 输入发送的编码 以 2 为结束标志 gets b printf 译码后的字符为 while b j 2 if b j 0 i tree i lchild 走向左孩子 else i tree i rchild 走向右孩子 计算机学院 数据结构 课程设计报告 1 if tree i lchild 1 tree i 是叶结点 printf c tree i ch i m 1 回到根结点 j print