《哈夫曼压缩软件 数据结构课程设计二》由会员分享，可在线阅读，更多相关《哈夫曼压缩软件 数据结构课程设计二（16页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法数据结构与算法 实验报告 题目二：压缩软件设计（哈夫曼编码技术）题目二：压缩软件设计（哈夫曼编码技术） 班级：班级：14 信科二班 姓名姓名：沈靖雯 学号学号：2014326601094 二一六年一月 题目二：压缩软件设计（哈夫曼编码技术应用）题目二：压缩软件设计（哈夫曼编码技术应用） 【实验目的】【实验目的】 哈夫曼编码是一种变长编码法（又称“熵编码法” ） ，用于数据的无损压缩是 指用一张特殊的编码表对源字符进行编码。 根据每一个源字符出现的估算概率建 立编码表（出现频率高的字符使用短编码，低的使用长的，使编码后字符串平均 期望长度降低，达到无损压缩目的） ，同时保持编码唯一
2、可解性。本实验要求使 用哈夫曼编码技术实现压缩软件设计。 【基本要求基本要求】 （准备一个文件（可以是.txt 文件） ，统计文件中各字符出现频率，进行 Huffman 编码，将文件翻译成 Huffman 编码文件，然后将编码文件写成字符存入 文件实现压缩,最后再将文件翻译成源文件。 【信息材料信息材料】 哈夫曼树是哈夫曼算法的理论描述工具，也称最优二叉树，是一种加权路径 长度最短的二叉树。N 个叶子结点的哈夫曼树共有 2N-1 个结点，这个性质将运 用于使用数组结构存储哈夫曼树，从根结点开始，左子结点分配 0，右子结点分 配 1，沿树根到各结点得到哈夫曼编码，所有被编码字符作为叶子结点出现而
3、每 个叶子结点路径独立，保障每个编码都不会是其余码前缀，又称“哈夫曼无重复 前缀编码” 。 哈夫曼树也应用于译码过程，译码过程中逐一扫描码文，从哈夫曼的根结点 开始，将扫描得到的二进制位串中的相邻位与哈夫曼树上的 0，1 匹配。 【问题实现问题实现】 （1）数据数据结构类结构类 typedef struct int weight;/权值 int parent,lchild,rchild; HTNode,*HuffmanTree;/动态分配数组存储哈夫曼树 typedef char* *HuffmanCode;/动态分配数组存储哈夫曼编码 （2 2）所用到的所用到的函数函数： /*所用到的函数*
4、/ void txtprint();/读取文件并输出 void Select(HuffmanTree /选择 n 个节点中权值最小的两个结点 void HuffmanCoding(HuffmanTree /哈夫曼编码函数， 生成编码表 void printcode(HuffmanTree /输出编码表 void Codding(HuffmanTree /文件编码 void ZipCode();/文件压缩 void DecompCode();/文件解压 void Translate(HuffmanTree /解压文件译码 int main();/主函数 （3 3）主要函数及思路主要函数及思路：
5、1 1） . .哈夫曼编码哈夫曼编码 voidvoid HuffmanCoding(HuffmanTreeHuffmanCoding(HuffmanTree /结点数 FILE *fp; fp= fopen( “C:UsersAshmoreDesktop哈夫曼a.txt“, “r“);/读文件 char k,ch; int num29;/频数，0 号单元未用，1-26 字母，27-28 逗句号,29 空格 for(i=0;iweight=numi; p-parent=p-rchild=p-lchild=0; for(;iweight=p-parent=p-rchild=p-lchild=0;
6、随后开始建哈夫曼树，其中 Select()函数作用为选取 parent=0 且权值 最小的两个结点，Select()函数具体代码见附件； for(i=n+1;i=0)i-) if(ki=0) fputc(0,fp2); else fputc(1,fp2); for(i=0;i #include #include #include #define OVERFLOW -2 #define EQ(a,b) (!strcmp(a),(b) int Length=0;/全局变量，记录 acode.txt（编码文件）总长度，初始值置 0 typedef struct int weight;/权值 int
7、parent,lchild,rchild; HTNode,*HuffmanTree;/动态分配数组存储哈夫曼树 typedef char* *HuffmanCode;/动态分配数组存储哈夫曼编码 void txtprint();/读取文件并输出 void Select(HuffmanTree /选择 n 个节点中权值最小的两个结点 void HuffmanCoding(HuffmanTree /哈夫曼编码函数， 生成编码表 void printcode(HuffmanTree /输出编码表 void Codding(HuffmanTree /文件编码 void Translate(Huffma
8、nTree /文件译码 void ZipCode();/文件压缩 void DecompCode();/文件解压 /选择 n 个节点中权值最小的两个结点 void Select(HuffmanTree for(i=1;iweight=numi; p-parent=p-rchild=p-lchild=0; for(;iweight=p-parent=p-rchild=p-lchild=0; for(i=n+1;i=0)i-) if(ki=0) fputc(0,fp2); else fputc(1,fp2); for(i=0;i7;i+) ki=0; j=-1; fclose(fp);fclose
9、(fp2); printf(“解压成功！解压文件存储在 Decompcode.txt！n“); void Translate(HuffmanTree fp= fopen( “C:UsersAshmoreDesktop哈夫曼Decompcode.txt“, “r“);/读文件 fp2= fopen( “C:UsersAshmoreDesktop哈夫曼translate.txt“, “w“);/写文件 char ch; char *c,*cc; int j=0,t,i,len=0; int flag=0;/标记 cc=(char*)malloc(20*sizeof(char); c=(char*)
10、malloc(20*sizeof(char); while(lenLength) flag=1; i=0; while(i3) ch=fgetc(fp);ci=ch;i+;len+; ci=0; strcpy(cc, while(flag=1) if(EQ(cc,HC29) fputc( ,fp2);flag=0; else if(EQ(cc,HC27) fputc(,fp2);flag=0; else if(EQ(cc,HC28) fputc(.,fp2);flag=0; else for(t=0;t26;t+) if(EQ(cc,HCt+1) fputc(a+t,fp2);flag=0;
11、else /未找到对应前缀编码，继续读取字符入数组 ch=fgetc(fp);ci=ch;i+;len+;ci=0; strcpy(cc, fclose(fp); fclose(fp2); printf(“译码成功！编码文件存储在 translate.txt！n“); int main() HuffmanTree HT; HuffmanCode HC; int n=29,a; printf(“-哈夫曼压缩软件设计-nn“); printf(“ 1).建编码表n“); printf(“ 2).编码n“); printf(“ 3).压缩n“); printf(“ 4).解压并译码n“); printf(“ 5).查看 txt 文件n“); printf(“ 0).退出n“); while(scanf(“%d“,printcode(HT,HC,n); break; case 2:Codding(HT,HC); break; case 3:ZipCode(); break; case 4:DecompCode();Translate(HT,HC);break; case 5:txtprint();break; default: printf(“谢谢使用!n“);exit(OVERFLOW); return 0;
