大数据结构哈夫曼实验C语言

1、实用标准文案用哈夫曼编码实现文件压缩实验报告课程名称数据结构 B实验学期2012至 2013学年第一学期学生所在系部计算机学院年级2011专业班级信管 B11-2学生姓名学号任课教师兰芸实验成绩精彩文档实用标准文案一、实验题目：用哈夫曼编码实现文件压缩二、实验目的：1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握 Huffman 树的概念及构造方法。4、掌握二叉树的存储结构及遍历算法。5、利用 Huffman 树及 Huffman 编码，掌握实现文件压缩的一般原理。三、实验设备与环境：微型计算机、 Windows 系列操作系统、 Visual C+6.0 软件四、实验内容：输入

2、一些字符， 即赫夫曼树结点的权值， 创建 Haffman 树，再将各字符对应的哈夫曼编码写入文件中。五、概要设计：（ 1）构造 Hufffman 树 Hufffman 算法（ 2） Huffman 编码：数据通信用的二进制编码编码：根据字符出现频率构造 Huffman 树，然后将树中结点引向其左孩子的分支标“ 0”，引向其右孩子的分支标“ 1”；每个字符的编码即为从根到每个叶子的路径上得到的 0、 1 序列。（ 3）二叉树的存储结构 typedef struct node datatype data;struct node *lchild,*rchild;BinTree;六、详细设计：1、构造

3、 Huffman 树步骤：、根据给定的n 个权值 w1,w2,wn，构造 n 棵只有根结点的二叉树，令起权值为 wj 。、在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。、在森林中删除这两棵树，同时将新得到的二叉树加入森林中。、重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。2、利用 Select 函数选出权值最小的两个结点。3、利用 CreatHT 函数构的建赫夫曼树先将所有的叶子结点的父结点和左右孩子结点均赋值为 0，并将输入的权值依次赋给叶子结点的 weight 域。从树的最底部开始循环 Select函数共 n-1 次

4、，将最小权的结点赋给中间结点的左孩子，将次小权的结点赋给中间结点的右孩子。精彩文档实用标准文案4、从叶子到根逆向求每个字符的赫夫曼编码，开辟字符串空间，从叶子结点开始逆向寻找每个中间结点的左右孩子，开辟字符空间为左孩子赋值为字符 0，为右孩子赋值为字符 1，运用 strcpy 函数将所得字符依次从右到左连接于所开辟的字符串空间，所得字符串即为赫夫曼编码。#include <stdio.h>#include <string.h>#include <stdlib.h>#include <conio.h>#include <time.h>s

5、truct nodelong weight;/ 权值unsigned char ch;/字符int parent,lchild,rchild;char code256;/编码的位数最多为256 位int CodeLength;/编码长度hfmnode512;void compress();/主函数void main()int choice;printf(" 欢迎使用赫夫曼编码压缩文件！请选择 1 or 2：n"); printf("1. 压缩文件 n");printf("2. 退出！ n");scanf("%d",

6、&choice);if(choice=1)compress();else if(choice=2)return;else printf("输入错误！ ");/压缩函数void compress()int i,j;char infile20,outfile20;FILE*ifp,*ofp;unsigned char c;/long FileLength,filelength=0;int n,m;/ 叶子数和结点数int s1,s2; /权值最小的两个结点的标号char codes256;long sumlength=0;精彩文档实用标准文案float rate,spe

7、ed;int count=0;clock_t start1, start2,finish1,finish2;doubleduration1,duration2;void encode(struct node *nodep,int n);/编码函数int select(struct node *nodep,int pose);/用于建哈弗曼树中选择权值最小的结点的函数printf(" 请输入要压缩的文件名 :");scanf("%s",infile);ifp=fopen(infile,"rb");if(ifp=NULL)printf(&

8、quot; 文件名输入错误，文件不存在!n");return;printf(" 请输入目标文件名 :");scanf("%s",outfile);ofp=fopen(outfile,"wb");if(ofp=NULL)printf(" 文件名输入错误，文件不存在!n");return;start1=clock() ;/开始计时 1/统计文件中字符的种类以及各类字符的个数/先用字符的 ASCII 码值代替结点下标FileLength=0;while(!feof(ifp)fread(&c,1,1,if

9、p);hfmnodec.weight+;FileLength+;FileLength-; / 文件中最后一个字符的个数会多统计一次，所以要减一 hfmnodec.weight-;/再将 ASCII 转换为字符存入到结点的ch 成员里，同时给双亲、孩子赋初值 -1n=0;for(i=0;i<256;i+)if(hfmnodei.weight!=0)hfmnodei.ch=(unsigned char)i;精彩文档实用标准文案n+;/叶子数hfmnodei.lchild=hfmnodei.rchild=hfmnodei.parent=-1;m=2*n-1;/ 哈弗曼树结点总数j=0;for(

10、i=0;i<256;i+)/ 去掉权值为 0 的结点if(hfmnodei.weight!=0)hfmnodej=hfmnodei;j+;for(i=n;i<m;i+)/ 初始化根结点hfmnodei.lchild=hfmnodei.rchild=-1;hfmnodei.parent=-1;/建立哈弗曼树for(i=n;i<m;i+)s1=select(hfmnode,i-1);hfmnodei.lchild=s1;hfmnodes1.parent=i;s2=select(hfmnode,i-1);hfmnodei.rchild=s2;hfmnodes2.parent=i;h

11、fmnodei.weight=hfmnodes1.weight+hfmnodes2.weight;/编码encode(hfmnode,n);finish1=clock();duration1=(double)(finish1- start1) / CLOCKS_PER_SEC;printf(" 编码完成，是否查看编码信息: y or n?n");c=getch();if(c='y')start2=clock() ;/开始计时 2fseek(ifp,0,SEEK_SET);/将 ifp 指针移到文件开头位置fwrite(&FileLength,4,1,

12、ofp);/ 将 FileLength 写入目标文件的前4 个字节的位置fseek(ofp,8,SEEK_SET);/再将目标文件指针ofp 移到距文件开头 8 个字节位精彩文档实用标准文案置codes0=0;/将编码信息写入目标文件while(!feof(ifp)fread(&c,1,1,ifp);filelength+;for(i=0;i<n;i+)if(c=hfmnodei.ch) break; /ch 必须也为 unsigned 型 strcat(codes,hfmnodei.code); while(strlen(codes)>=8)for(i=0;i<8;

13、i+)/ 将 codes的前 8 位 01 代码表示的字符存入cif(codesi='1')c=(c<<1)|1;else c=c<<1;fwrite(&c,1,1,ofp); / 将新的字符写入目标文件sumlength+;strcpy(codes,codes+8);/更新 codes的值if(filelength=FileLength) break;/再将剩余的不足 8 位的 01 代码补全 8 位，继续写入 if(strlen(codes)>0)strcat(codes,"00000000");for(i=0;i&

14、lt;8;i+)if(codesi='1')c=(c<<1)|1;else c=c<<1;fwrite(&c,1,1,ofp);sumlength+;sumlength+=8;printf(" 编码区总长为： %ld 个字节 n",sumlength-8);/将 sumlength和 n 的值写入目标文件，为的是方便解压 fseek(ofp,4,SEEK_SET);fwrite(&sumlength,4,1,ofp);/ 把 sumlength 写进目标文件的第5-8 个字节精彩文档实用标准文案里fseek(ofp,s

15、umlength,SEEK_SET);fwrite(&n,4,1,ofp);/ 把叶子数 n 写进编码段后面的4 个字节的位置/为方便解压，把编码信息存入n 后面的位置/存储方式为： n*（字符值（1 个字节） +该字符的 01 编码的位数（1 个字节）+编码（字节数不确定，用count 来计算总值）for(i=0;i<n;i+)fwrite(&(hfmnodei.ch),1,1,ofp);c=hfmnodei.CodeLength;/编码最长为 256 位，因此只需用一个字节存储fwrite(&c,1,1,ofp);/写入字符的编码if(hfmnodei.Cod

16、eLength%8!=0)for(j=hfmnodei.CodeLength%8;j<8;j+)/ 把编码不足8 位的在低位补 0,赋值给 C，再把 C 写入strcat(hfmnodei.code,"0");while(hfmnodei.code0!=0)/ 开始存入编码，每 8 位二进制数存入一个字节c=0;for(j=0;j<8;j+)if(hfmnodei.codej='1')c=(c<<1)|1;else c=c<<1;strcpy(hfmnodei.code,hfmnodei.code+8);/编码前移 8 位

17、，继续存入编码count+; /编码占的字节数的总值fwrite(&c,1,1,ofp);printf("n");finish2=clock();duration2=(double)(finish2- start2) / CLOCKS_PER_SEC;printf( " 压缩用时为： %f secondsn", duration1+duration2); speed=(float)FileLength/(duration1+duration2)/1000; printf("n 压缩速率为： %5.2f KB/Sn",speed

18、);printf("n");printf(" 源文件长度为： %ld 个字节 n",FileLength); sumlength=sumlength+4+n*2+count; /计算压缩后文件的长度 printf(" 压缩后文件长度为： %ld 个字节 n",sumlength);精彩文档实用标准文案rate=(float)sumlength/(float)FileLength;printf(" 压缩率 (百分比 )为： %4.2f%n",rate*100);fclose(ifp);fclose(ofp);retu

19、rn;/建立哈弗曼树中用于选择最小权值结点的函数int select(struct node *nodep,int pose)int i;int s1;long min=2147483647;/s初值为 long 型的最大值for(i=0;i<=pose;i+)if(nodepi.parent!=-1)continue;if(nodepi.weight<min)min=nodepi.weight;s1=i;return s1;/哈弗曼编码函数void encode(struct node *nodep,int n)/从叶子向根求每个字符的哈弗曼编码 int start;int i,f,c;char codes256; codesn-1='0' / 编码结束符 for(i=0;i<n;i+) / 逐个字符求哈弗曼编码start=n-1; for(c=i,f=nodepi.parent;f!=-1;c=f,