哈弗曼编码实现无损压缩实验报告

南京理工大学多媒体技术基础实验报告南京理工大学多媒体技术基础实验报告 院系 自动化院系 自动化 学号 学号 姓名 王江鹏姓名 王江鹏 哈弗曼编码实现无损压缩实验报告哈弗曼编码实现无损压缩实验报告 院系 自动化院系 自动化 学号 学号 姓名 王江鹏姓名 王江鹏 指导老师 何新指导老师 何新 一 一 实验内容实验内容 通过C 编程实现 要求 1 字符串的输入是手工输入的 2 通过程序实现编码 最终在屏幕上显示编码结果 例如 如果选用 huffman 编码 则要 显示字符串的编码以及平均码长 二 二 源代码源代码 include include define MAXVALUE define MAXLEAF 256 define MAXNODE MAXLEAF 2 1 char a 0 int qq 0 coun 0 qq 是统计文本中有多少个不同的字符 coun 是统计文本中有多少个字符 float avlen 0 FILE f f fopen D hafuman1 text r 建立文本函数 void creat save int i 0 printf please input text n gets a while a i NULL i coun 南京理工大学多媒体技术基础实验报告南京理工大学多媒体技术基础实验报告 院系 自动化院系 自动化 学号 学号 姓名 王江鹏姓名 王江鹏 printf coun d coun 统计字符频率函数 int s 256 0 s 0 到 s 255 分别对应字母的 ASCII 码由 0 到 255 的统计个数 void count int i 0 f 0 char m while i coun 不能用 cout a 进行输出会将 a 的指针移动 m 0 for int j 0 a i m j m s m i printf n for i 0 i 256 i printf 3d s i while f 255 if s f 0 qq f printf nqq d n qq 构造 Huffman 树 3 typedef struct int weight int parent int lchild int rchild char num HNodeType HNodeType HuffNode MAXNODE MAXNODE 代表所有结点的个数 int n 叶子结点个数 void HuffmanTree 南京理工大学多媒体技术基础实验报告南京理工大学多媒体技术基础实验报告 院系 自动化院系 自动化 学号 学号 姓名 王江鹏姓名 王江鹏 int i j m1 m2 x1 x2 n qq 叶子结点的个数 for i 0 i MAXNODE i HuffNode i weight 0 HuffNode i parent 1 HuffNode i lchild 1 HuffNode i rchild 1 HuffNode i num 1 cout 请分别输入各个叶子结点的权值 endl j 0 for i 0 i 256 i if s i 0 HuffNode j weight s i HuffNode j num i j for i 0 i n 1 i 构造哈弗曼树 m1 m2 MAXVALUE x1 x2 0 for j 0 j n i j 选取最小和次小的两个权值 其中 n i 中的 i 代表已经多加了 i 个非叶子结点 if HuffNode j parent 1 x2 x1 m1 HuffNode j weight x1 j else if HuffNode j parent 1 x2 j 将第找出的俩棵子树合并为一棵新子树 HuffNode x1 parent n i HuffNode x2 parent n i 南京理工大学多媒体技术基础实验报告南京理工大学多媒体技术基础实验报告 院系 自动化院系 自动化 学号 学号 姓名 王江鹏姓名 王江鹏 HuffNode n i weight HuffNode x1 weight HuffNode x2 weight HuffNode n i lchild x1 HuffNode n i rchild x2 Huffman 编码算法 4 define MAXBIT 200 typedef struct int bit MAXBIT int start HCodeType HCodeType HuffCode MAXLEAF cd void HaffmanCode int i j c p HuffmanTree 建立哈弗曼树 for i 0 i qq i 求每个叶子结点的编码 int load 0 cd start qq 1 c i p HuffNode c parent while p 1 if HuffNode p lchild c cd bit cd start 0 else cd bit cd start 1 cd start c p p HuffNode c parent printf n c 频率为 d 编码为 HuffNode i num s HuffNode i num for j cd start 1 j qq j 将编码的叶子结点赋给编码数组保存 load 求叶子节点路径长 HuffCode i bit j cd bit j printf d cd bit j avlen load s HuffNode i num HuffCode i start cd start 南京理工大学多媒体技术基础实验报告南京理工大学多媒体技术基础实验报告 院系 自动化院系 自动化 学号 学号 姓名 王江鹏姓名 王江鹏 printf avlen av