哈呼曼编译器设计说明书.doc

实践教学实践教学 兰州理工大学兰州理工大学 计算机与通信学院 2007 年春季学期 算法与数据结构算法与数据结构课程设计课程设计 题 目 哈夫曼编译码器设计 专业班级 05 计算机科学与技术 3 班 姓 名 徐玉霞 学 号 05240317 指导教师 李 睿 成成 绩 绩 目目 录录 摘摘 要要 2 前前 言言 3 正正 文文 4 1 采用类C语言定义相关的数据类型 4 2 各模块的伪码算法 4 3 函数的调用关系图 7 4 调试分析 7 5 测试结果 8 6 源程序 带注释 10 参考参考文文献献 18 致致 谢谢 19 附件附件 部分源程序部分源程序代代码码 20 摘摘 要要 该设计是对输入的一串电文字符实现哈夫曼编码 再对哈夫曼编码生成的代 码串进行译码 输出电文字符串 在该设计中把数据压缩过程称为编码 解压缩 的过程称为译码 此程序中建立了哈夫曼树 并利用建好的哈夫曼树对文件中的 正文进行编码 对文件中的代码进行译码 显示输出等功能 关关键键词词 哈夫曼树 哈夫曼编码 哈夫曼译码 前前 言言 哈夫曼编码的应用很广泛 利用哈夫曼树求地的二进制编码称为哈夫 曼编码 哈夫曼树中从根到每个叶子都有一条路径 对路径上的各分支约定 指 向左子树的分支表示 0 码 指向右子树的分支表示 1 码 取每条路径 上的 0 或 1 的序列作为对应的编码 这就是哈夫曼编码 我们在对一 些问题进行求解时 会发现有些问题很难找到规律 或者根本无规律可寻 对于 这样的问题 可以利用计算机运算速度快的特点 先搜索查找 所有可能出现 的情况 再根据题目条件从所有可能的情况中 删除那些不符合 条件的解 由哈夫曼算法的定义可知 初始森林中共有n 棵只含有根结点的二叉树 算法的的第二步是 算法的的第二步是 将当前森林中的两棵根结点权值最小的 二叉树 合并成一棵新的二叉树 每合并一次 森林中就减少一棵树 产生 一个新结点 则要进行n 1 次合并 所以共产生n 1 个新结点 由此可知 最终求得的哈夫曼树中一共有2n 1 个结点 其中 n 个结点是初始森林中 的 n 个孤立结点 并且哈夫曼树中没有度数为1 的分支的结点 采用哈夫曼编码方案 即应用哈夫曼树构造使电文的编码总长最短的编码方 案 正文正文 1 采用类 采用类 C 语言定义相关的数据类型语言定义相关的数据类型 1 哈夫曼树的存储结构定义为 typedef struct 字符集的元素结构 char data int weight 权值 elemtype typedef struct 哈夫曼树的元素结构 char data int flag int weight 权值 int parent lchild rchild 左右孩子及双亲指针 htnode huffmantree 动态分配数组存储哈夫曼树 typedef char HuffmanCode 动态分配数组存储哈夫曼编码表 2 哈夫曼树的存储结构描述 include include include define n 27 字符集的容量 define MAXVALUE 1000 权值的最大值 define MAXNODE 35 哈夫曼树最多节点数 define MAXD 100 2 各模块的伪码算法 各模块的伪码算法 1 构造哈夫曼树的算法 void ChuffmanTree HuffmanTree HT Huffmancode Hc int cnt char str 构造哈夫曼树 HT cnt 中存放每类字符在电文中出项的频率 str 中存放电文中不同类 的字符 int i s1 s2 for i 1 i 2 num 1 i HT i lchild 0 HT i rchild 0 HT i parent 0 HTweight 0 for i 1 i 2 num i 输入 num 个结点的权值 HT i weight cnt i for i num 1 i 2 num 1 i 在 HT 1 i 1 中选择 parent 为 0 且权值最小的两个结点 selext Ht i 1 s1 s2 HT s1 parent i HT s2 parent i Ht i lchild s HT i rchild s2 HT i weight HT s1 weight HT s2 weight for i 0 i num i 输入字符集中字符 HC i ch str i i 1 while i num printf 字符 2 求哈夫曼编码 huffmancode 算法 HuffmanCode huffmancode huffmantree ht char cd int c i f start HuffmanCode HC HC HuffmanCode malloc n 1 sizeof char 分配 n 个字符编码的头指针向量 cd char malloc n sizeof char 分配求编码的工作区间 cd n 1 0 编码结束符标志 for i 1 i n i 逐个字符求哈夫曼编码 start n 1 编码结束位置 for c i f ht i parent f 0 c f f ht f parent 从叶子到根逆向求编码 if ht f lchild c cd start 0 else cd start 1 HC i char malloc n start sizeof char 为第 i 个字符编码分配空间 strcpy HC i 从 cd 复制编码 串 到 HC for i 1 i n i puts HC i free cd 释放工作空间 return HC 3 求测试数据的编码 encoding 算法 void encoding huffmantree ht char hc 根据哈夫曼树 HT 求哈夫曼编码表 HC int i j k char sstring MAXNODE clrscr flushall printf input huffmancode n eg this is programma is my favorite n gets sstring for i 0 i strlen sstring i for j 1 j n j if sstring i ht j data k j break 4 哈夫曼译码算法 void decoding huffmantree ht 代码文件的译码 char a MAXD int m i clrscr scanf s a m 2 n 1 for i 0 a i 0 i if a i 0 m ht m lchild else m ht m rchild if m n printf c ht m data m 2 n 1 3 函数调用关系图 函数调用关系图 4 调试分析 调试分析 a 调试中遇到的问题及对问题的解决方法 在对源程序进行调试时 当输入字符后 应正确判断所输入的字符是否满足程序的 需求 且保正所输入字符后所输出语句功能唯一 则在源程序中加入了一条 while 判断 语句 若 while 判断语句中表达式成立 就重新获取一个字符 然后对 while 语句进 行重新判断 直到 while 判断语句中表达式不成立 就执行 switch 语句中于其输入字 符相对应的 case 语句 其程序语句如下 while ch r 选取功能 switch ch case r readdata w break 初始化 readdata 读取数据 case c ht createhuff w break 建立哈夫曼树 createhuff case e hc huffmancode ht encoding ht hc break 求字符集的哈夫曼编码 huffmancode 和求测试数据的编码 encoding case d decoding ht break 译码 decoding case q return 程序结束 返回 b 算法的时间复杂度和空间复杂度 时间复杂度 建立哈夫曼树 O n 对文件中正文进行编码 O n2 对文件中的代码进行译码 O n 5 测试结果测试结果 对下列给出的字符集和频度的实际统计数据建立哈夫曼树 并实现以下报文的编码和 译码 THIS PROGRAM IS MY FAVORITE 字符 空格 A B C D E F G H I J K L M 频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 频度 57 63 15 1 48 51 80 23 8 18 1 16 1 输入 r 后 输入 c 后 输入 e 后 6 源程序 带注释 源程序 带注释 include include include define n 27 字符集的容量 define MAXVALUE 1000 权值的最大值 define MAXNODE 35 哈夫曼树最多节点数 define MAXD 100 typedef struct 字符集的元素结构 char data int weight elemtype typedef struct 哈夫曼树的元素结构 char data int flag int weight 权值 int parent lchild rchild 左右孩子及双亲节点 htnode huffmantree 动态分配数组存储哈夫曼树 typedef char HuffmanCode 动态分配数组存储哈夫曼编码表 void readdata elemtype w huffmantree createhuff elemtype w char huffmancode huffmantree ht void encoding huffmantree ht char hc void decoding huffmantree ht 初始化 readdata 读取数据 void readdata elemtype w int i w 0 data w 0 weight 186 w 1 data a w 1 weight 64 w 2 data b w 2 weight 13 w 3 data c w 3 weight 22 w 4 data d w 4 weight 32 w 5 data e w 5 weight 103 w 6 data f w 6 weight 21 w 7 data g w 7 weight 15 w 8 data h w 8 weight 47 w 9 data i w 9 weight 57 w 10 data j w 10 weight 1 w 11 data k w 11 weight 5 w 12 data l w 12 weight 32 w 13 data m w 13 weight 20 w 14 data n w 14 weight 57 w 15 data o w 15 weight 63 w 16 data p w 16 weight 15 w 17 data q w 17 weight 1 w 18 data r w 18 weight 48 w 19 data s w 19 weight 51 w 20 data t w 20 weight 80 w 21 data u w 21 weight 23 w 22 data v w 22 weight 8 w 23 data w w 23 weight 18 w 24 data x w 24 weight 1 w 25 data y w 25 weight 16 w 26 data z w 26 weight 1 for i 0 i 27 i printf c w i data printf d t w i weight return huffmantree createhuff elemtype w int i j x1 x2 int m1 m2 m huffmantree HT p m 2 n 1 HT huffmantree malloc m 1 sizeof htnode 0 号单元未用 p HT p for i 1 i m i p w 初始化 HT if idata w data p weight w weight else p data 0 p weight 0 p parent 0 p lchild 0 p rchild 0 p flag 0 for i 1 i n i 该循坏开始构造哈夫曼树 m1 m2 MAXVALUE x1 x2 0 p HT for j 1 j n 1 i j if p j weight m1 x2 x1 m1 p j weight x1 j else if p j weight m2 x2 j p x1 parent n i p x2 parent n i p x1 flag 1 p x2 flag 1 p n i weight p x1 weight p x2 weight p n i lchild x1 p n i rchild x2 clrscr for i 1 i m i printf d c d 3d 3d 3d 3d n i p i data p i flag p i weight p i parent p i lchil d p i rchild if i 15 0 getch clrscr return HT HuffmanCode huffmancode huffmantree ht char cd int c i f start HuffmanCode HC 从叶子到根逆向求哈夫曼编码 HC HuffmanCode malloc n 1 sizeof char 分配 n 个字符的头指针向量 cd char malloc n sizeof char 分配求编码的工作区间 cd n 1 0 编码结束符 for i 1 i n i 逐个字符求哈夫曼编码 start n 1 编码结束符位置 for c i f ht i parent f 0 c f f ht f parent 从 叶子到根逆向求编码 if ht f lchild c cd start 0 else cd start 1 HC i char malloc n start sizeof char 为第 i 个字符编码分配空间 strcpy HC i 从 cd 复制编码串到 HC for i 1 i n i puts HC i free cd 释放工作区间 return HC void encoding huffmantree ht char hc int i j k char sstring MAXNODE clrscr flushall printf input huffmancode n eg this is programma is my favorite n gets sstring for i 0 i strlen sstring i for j 1 j n j if sstring i ht j data k j break if kMAXNODE printf there isn t NO d char n i continue printf c tweight 3d t s n ht k data ht k weight hc k void decoding huffmantree ht char a MAXD int m i clrscr scanf s a m 2 n 1 for i 0 a i 0 i if a i 0 m ht m