-树-哈夫曼编解码的实现-实验内容与要求.docx

数据结构实验报告评分满分10分学号：2015111840 姓名：陈周擎 专业：计算机科学与技术知识范畴：树 完成日期：2017年05月12日实验题目：Huffman编解码的实现实验内容及要求：从字符文件读取若干个大写英文字符(英文字符种类数m建议为6至8种，如:m=6，则英文字符可取A-F)，统计m种英文字符的出现频度，构造Huffman二叉树，对所有英文字符进行Huffman编码，将编码后的比特流用byte型（或char型）数组实现存储。在屏幕上输出该比特流的压缩率，然后利用该数组和Huffman二叉树进行译码，将译码后的字符序列输出到另一个字符文件。提示：(1) 输入与输出字符文件每10个字符一行； (2) 输入文件中的不可显示字符（如：回车、换行符）不进行统计和编码； (3) 压缩率=平均编码长度/log2m。实验目的：掌握Huffman二叉树及Huffman编、译码。数据结构设计简要描述：本实验采用数组以及静态链表方式存储。码树结点的结构体：typedef struct int parent,； /双亲下标int lchild； /左儿子下标int rchild; /右儿子下标 double w; /结点权值 HF_BTNode;Huffman码树及码表：typedef struct int n; /实际符号数 char sN; /符号表 double weightN; /符号权重表 char codeNN+1; /编码表 HF_BTNode hf2 * N - 1; /码树 double rate; /压缩率HFT；算法设计简要描述：本实验中核心算法包括构造Huffman二叉树并编码算法、解码算法。构造Huffman二叉树并编码：hf0.n-1为码树的叶子结点。构造Huffman树的过程共需要进行n-1趟两个子树的合并，每趟合并后，生成的新的子树的根结点按照下标增量次序加入。解码算法：设接收二进制序列用字符串表示，从根结点出发，1表示向左，0表示向右深入，直到到达某个叶子结点时，输出叶子结点对应的符号；重复此过程，直到接收序列全部译出。输入/输出设计简要描述：本实验中分别有一次输入和两次输出。输入：英文字符种类数m。输出：译码的字符序列输出到另一个文件中；在屏幕上输出Huffman编码的压缩率。编程语言说明：1.编程软件，Code Blocks 16.0；2.代码均用C+语言实现；3.输入输出采用C+语言的cout和cin函数；4.程序注释采用C/C+规范；5.动态存储分配采用C+的new和delete操作符实现主要函数说明：void insert(char ch) /插入字符int found(char ch) /查找字符void creat() /构造霍夫曼二叉树void coding() /生成各种字符编码void cal() /计算压缩率void coding(char *sour, HFT &hft) /字符串进行霍夫曼编码void decoding(char *dsou, HFT &hft) /字符串解码程序测试简要报告：（1） 测试实例1输入：请输入m：4输出：压缩率为 0.875运行界面：结论：程序输出结果与期望输出结果相符。（2） 测试实例2输入：请输入m：10输出：压缩率为 0.872987运行界面：结论：程序输出结果与期望输出结果相符。（3） 测试实例3输入：请输入m：6输出：压缩率为 0.976803运行界面：结论：程序输出结果与期望输出结果相符。源程序代码：#include #include #include #include#include #define N 256 /最多字符种类#define MAXL 10000 /最长文件长度using namespace std;typedef struct int parent, lchild, rchild; double w; HF_BTNode;char receMAXL; /编码结果char sMAXL; /源字符串（编码源）int byte_num; /编码总位数typedef struct int n; /实际符号数 char sN; /符号表 double weightN; /符号权重表 char codeNN+1; /编码表 HF_BTNode hf2 * N - 1; /码树 double rate; /压缩率void insert(char ch) /插入字符ch for (int i = 0; i n; i+) if (si = ch) weighti+; return; sn = ch; weightn+; n+;int found(char ch) /查找ch字符 for (int i = 0; i n; i+) if (ch = si) return i; return -1; void creat() /构造霍夫曼二叉树 int m = 2 * n - 1; for (int i = 0; i m; i+) hfi.parent = hfi.lchild = hfi.rchild = -1; for (int i = 0; i n; i+) hfi.w = weighti; for (int i = n; i m; i+) int j1, j2; for (j1 = 0; j1 i; j1+) if (hfj1.parent = -1) break; for (int j = j1 + 1; j i; j+) if (hfj.parent = -1 & hfj.w hfj1.w) j1 = j; hfj1.parent = i; hfi.lchild = j1; for (j2 = 0; j2 i; j2+) if (hfj2.parent = -1) break; for (int j = j2 + 1; j i; j+) if (hfj.parent = -1 & hfj.w hfj2.w) j2 = j; hfj2.parent = i; hfi.rchild = j2; hfi.w = hfj1.w + hfj2.w; void coding() /生成各种字符编码 for (int i = 0; i n; i+) int j = i; char *p = codei; while (hfj.parent != -1) int child = j; j = hfj.parent; if (hfj.lchild = child) *p+ = 1; else *p+ = 0; *p = 0; char *q = codei; p-; while (q p) char ch = *q; *q = *p; *p = ch; q+; p-; void cal() /计算压缩率 double len = 0; for (int i = 0; i n; i+) len += strlen(codei)*weighti; rate = len / log(n) * log(2); HFT;void coding(char *sour, HFT &hft) /对sour字符串进行霍夫曼编码 byte_num = 0; int len = strlen(sour); for (int i = 0; i len; i+) int ind = hft.found(souri); if (ind = -1) continue; char *p = hft.codeind; int l = strlen(p); for (int j = 0; j l; j+) int x = byte_num / 8; int y = byte_num % 8; if (pj = 0) recex &= (1 y); else recex |= (1 y); byte_num+; void decoding(char *dsou, HFT &hft) /对dsou字符串解码 int x, y, cnt = 0; FILE *fp; fp=fopen(file_result.txt,w); for (int i = 0; i = hft.n & i byte_num) x = i / 8; y = i % 8; if (dsoux & (1 y) k = hft.hfk.lchild; else k = hft.hfk.rchild; i+; if (k hft.n) cnt+; fputc(hft.sk, fp); if (cnt % 10 = 0) fputc(n, fp); HFT hufft;int main() FILE *fp; int ch, slen = 0; fp=fopen(file_data.txt, r); while (ch = fgetc(fp) != EOF & slen MAXL) if (ch != & ch != n) hufft.insert(ch); sslen+ = ch; sslen