数据结构用哈夫曼编码实现文件压缩

1、用哈夫曼编码实现文件压缩实验报告课程名称数据结构B实验学期201至201学年第学期学生所在系部计算机学院年级专业班级学生姓名学号任课教师实验成绩一、实验题目:用哈夫曼编码实现文件压缩二、实验目的1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码，掌握实现文件压缩的一般原理。三、实验设备与环境|：微型计算机、Windows系列操作系统、VisualC+6.0软件四、|实验内容|：根据ascii码文件中各ascii字符出现的频率情况创建Haffman树，再将各字符对应的哈

2、夫曼编码写入文件中，实现文件压缩。五、|概要设计|：（1）构造Hufffman树的方法一Hufffman算法构造Huffman树步骤：根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wj。在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。在森林中删除这两棵树，同时将新得到的二叉树加入森林中。重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。（2）Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码，使电文总长最短编码：根据字符出现频率构造Huffman树，然后将树中结点引向其左孩子的分支

3、标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。（3）解压根据存放在文件中的编码表和文件压缩后的编码，进行一对一的翻译过程。六、|详细设计|：压缩的代码#include#include#include#includetypedefstructunsignedintweight;unsignedintparent,lchild,rchild;HTNode,*HuffmanTree;typedefchar*HuffmanCode;voidSelect(HuffmanTreeHT,intn,int*s1,int*s2)inti;unsignedintt

4、;t=10000;for(i=1;i=n;i+)if(HTi.parent=0&HTi.weightt)t=HTi.weight;*s1=i;t=10000;for(i=1;i=n;i+)if(HTi.parent=0&HTi.weightt&i!=*s1)t=HTi.weight;*s2=i;voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)intm,i,s1,s2;HTNode*p;char*cd;unsignedintc,f;intstart;if(n=1)return;m=2*n-1;HT=(HuffmanTree)m

5、alloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;i=n;+i,+p,+w)(*p).weight=*(w+1);(*p).parent=0;(*p).lchild=0;(*p).rchild=0;for(;i=m;+i,+p)(*p).weight=0;(*p).parent=0;(*p).lchild=0;(*p).rchild=0;for(i=n+1;i=m;+i)Select(HT,i-1,&s1,&s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.we

6、ight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);cdn-1=0;for(i=1;i=n;i+)start=n-1;for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);strcpy(HCi,&cdstart);free(cd);voidmain()int*w;inti,n,m;HuffmanTreeHT=NULL;HuffmanCodeHC=NULL;printf(请输入赫夫曼树的结点个数：”)；scanf(%d,&n);w=(int*)malloc(n+1)*sizeof(int)；m=2*n-1；printf(”请输入结点的权值为:n);for(i=1；i=n；i+)scanf(%d,w+i);printf(赫夫曼编码:n);HuffmanCoding(HT,HC,w,n);for(i=1;i=n;i+)printf(%sn,HCi);七、测试结