哈夫曼压缩软件数据结构课程设计二.pdfVIP

数据结构与算法 实验报告 题目二：压缩软件设计 （哈夫曼编码技术） 班级：14信科二班 姓名：沈靖雯 学号：2014326601094 二〇一六年一月 题目二：压缩软件设计 （哈夫曼编码技术应用） 【实验目的】 哈夫曼编码是一种变长编码法 （又称 “熵编码法”），用于数据的无损压缩是 指用一张特殊的编码表对源字符进行编码。根据每一个源字符出现的估算概率建 立编码表 （出现频率高的字符使用短编码，低的使用长的，使编码后字符串平均 期望长度降低，达到无损压缩目的），同时保持编码唯一可解性。本实验要求使 用哈夫曼编码技术实现压缩软件设计。 【基本要求】 （准备一个文件 （可以是.txt文件），统计文件中各字符出现频率，进行 Huffman编码，将文件翻译成Huffman编码文件，然后将编码文件写成字符存入 文件实现压缩,最后再将文件翻译成源文件。 【信息材料】 哈夫曼树是哈夫曼算法的理论描述工具，也称最优二叉树，是一种加权路径 长度最短的二叉树。N个叶子结点的哈夫曼树共有2N-1个结点，这个性质将运 用于使用数组结构存储哈夫曼树，从根结点开始，左子结点分配0，右子结点分 配1，沿树根到各结点得到哈夫曼编码，所有被编码字符作为叶子结点出现而每 个叶子结点路径独立，保障每个编码都不会是其余码前缀，又称“哈夫曼无重复 前缀编码”。 哈夫曼树也应用于译码过程，译码过程中逐一扫描码文，从哈夫曼的根结点 开始，将扫描得到的二进制位串中的相邻位与哈夫曼树上的0，1匹配。 【问题实现】 （1）数据结构类 typedef struct{ int weight; //权值 int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char* *HuffmanCode;//动态分配数组存储哈夫曼编码 （2）所用到的函数： /*所用到的函数*/ void txtprint();//读取文件并输出 选择 个节点中权值最小的两个结点 void Select(HuffmanTree HT,int n,int s1,int s2); // n void HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int n);//哈夫曼编码函数，生成编码表 void printcode(HuffmanTree HT,HuffmanCode HC,int n);//输出编码表 void Codding(HuffmanTree HT,HuffmanCode HC);//文件编码 void ZipCode();//文件压缩 void DecompCode();//文件解压 void Translate(HuffmanTree HT,HuffmanCode HC);//解压文件译码 int main();//主函数 （3）主要函数及思路： 1）.哈夫曼编码void HuffmanCoding(HuffmanTreeHT,HuffmanCode HC,int n)； （函数完整代码见附件，此处只取重要部分） 该函数首先实现对a.txt待编码文件字符频数统计，根据统计所得各字 符频数初始化叶子结点权值，叶子结点即a.txt文件中出现的所有字符，其 中包括26个英文字母 （频数统计不区分大小写）、空格符、句号和逗号；随 后初始化非叶子结点权值0；此部分代码如下，用到读文件操作： m=2*n-1; //结点数 FILE *fp; fp= fopen( C:\\Users\\Ashmore\\Desktop\\哈夫曼\\a.txt, r);//读文件 char k,ch; int num[29];//频数，0 号单元未用，1-26 字母，27-28 逗句号,29 空格 fo