哈弗曼压缩软件(数据结构试验报告附源程序)

1、数据结构课程设计报告题 目： 基于哈夫曼编码的压缩软件 系部名称：计算机专业名称：软件工程班 级：0802学号：XXXXXX学生姓名 ：稻草人指导教师：XXXXX时间：2010 XX-2010 YY一、 课程设计目的 通过运用哈夫曼树的知识编写该压缩与解压软件，能使学生将所学的理论知识应用起来，有效地运用到解决实际问题中去，提高学生的自身的编程能力，从而达到学以致用的目的。二、课程设计内容 1应用系统分析，建立该系统的功能模块框图及界面的组织和设计； 2分析系统中的各个函数及它们之间的关系； 3根据问题描述，设计系统的结构体及各个函数； 4设计哈弗曼树的构造算法和哈弗曼编码算法； 5

2、完成设计的系统各个应用模块； 6将各个模块整合进行功能测试。三、需求分析哈弗曼压缩软件1.需求分析目的为明确软件需求、安排项目规划与进度、组织软件开发与测试，供设计人员、开发人员参考。2.项目开发计划时间开发内容6月22日读取文本文件，并统计文件中字母个数6月23日建立huffman树对文件，进行huffman编码6月24日压缩6月25日解压缩3.任务目标能比较完善的对txt文件进行压缩和解压缩。4.数据字典名称：字符频率别名：weight描述：读取文本文件，并统计文件中字母个数定义：字符频率 = 字符 + 数量名称：结点别名：HTNode描述：建立huffman树的叶子和非叶子结点定义：结点

3、 = 数量 + 字符 + 双亲结点 + 左孩子结点 + 右孩子结点位置：编码文件5. 功能划分n 压缩 n 解压缩四、概要设计哈弗曼压缩软件1 建立哈夫曼树。根据哈夫曼编码技术，可以将已经给出的字母的使用频率建立一个哈夫曼树，即以二叉树的形式将英文字母和空格存储。 2 编码。利用二叉树的遍历知识，左孩子用“0”表示，右孩子用“1”表示，将输入的一组英文句子进行编码。 3测试和输出。程序要求的测试的英文句子是：“knowledge is power”，输出每一个字母然后给出相应的哈夫曼编码。本程序输入字母以“#”结束。 4译码。本程序要求对已编码的数字能够给以反编码

4、。 .函数调用示意图Main( )Compression( )Decompression( )Clock ( )Initfromfile( )Htcreat( )Hccreat ( )Convertfile( )Decompressionfile( )Clock ( )Exit( )六、调试情况，设计技巧及体会1测试结论u 能较好地进行压缩和解压u 不足的是对最后所补的0未处理，解压会多出几个字符。2. 设计技巧本软件可对字母、汉字可以实现共同压缩，压缩率在50%以上，压缩后对哈夫曼树进行保存，以便后面解压，对叶子结点只保存其字符、左孩子、右孩子，对非叶子结点保存左孩子和右孩子。解压时从根结点

5、开始，利用哈夫曼树进行解压，遇到0，找左孩子，遇到1找右孩子，到叶子结点时，输出字符。3心得体会： 通过这次课题实验的程序实践，我实在获益匪浅！数据结构是上个学期开展的一门学科，学习好这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。同时，学习这门学科也是艰辛的，因为它比较难懂，这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中领悟。这次的程序设计对我来说无疑是一个具大的考验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。因为开始时基础不是很好，过程中遇到了不少的阻碍，编写程序的进度也比较慢。虽然如此，但是通过自己的努力与老师的指导，我对这

6、次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的基础下写出了本次实验的核心算法，并使其能够正常的运行。这一个多月的设计工作，让我体会到了作为一个编程人员的艰难，一个算法到具体实现，再到应用层面的开发是需要有一段较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程人员还要花很多的时间去完善它，其中包含的心酸，外人是不会明白的。非常感谢在背后一直给我指导的老师和同学，他们的支持和鼓励让我在遇到挫折时能够站起来战胜它，也让我走到了今天这一步，完成了实验的设计。今后，我会更加努力的学习专业知识，提高自我的能力。七、参考文献c语言程序设计谭浩强主编八、附录：源代码#

7、include<stdio.h>#include<stdlib.h>#include<malloc.h>#include<string.h>#include<io.h>typedef struct word char word3; unsigned long times; struct word *next; word,*word_list;typedef struct Tnode unsigned long weight; char word3; long parent,lchild,rchild; Tnode,HuffTree;H

8、uffTree ht5000;char *hc5000;int n=0;void stat(word_list head,char *filename) FILE *fp; char ch3; int flag=0; word *p,*q,*s; fp=fopen(filename,"rt"); if(fp=NULL) printf("n无法打开要压缩的文件,或该文件不存在!"); p=head; while(ch0=fgetc(fp)!=EOF)if(ch0<0|ch0>254) ch1=fgetc(fp); ch2='0'

9、else ch1='0'if(ch0=10) strcpy(ch,"-n"); if(ch0=32) strcpy(ch,"-t");for(q=head->next;q!=NULL;q=q->next)if(!strcmp(q->word,ch) (q->times)+; flag=1; break;if(flag=0)s=(word *)malloc(sizeof(word);strcpy(s->word,ch);s->times=1;p->next=s;p=s;p->next=NULL

10、;+n;flag=0; p->next=NULL; fclose(fp);return;void protect1(char *filename) FILE *fp2;char ch26="编码："int i;strcat(ch,filename);fp2=fopen(ch,"wt");if(fp2=NULL) printf("n编码文件无法创建!");exit(1); for(i=1;i<=2*n-1;i+)fprintf(fp2,"%s %ld %ld %ldn",hti.word,hti.pare

11、nt,hti.lchild,hti.rchild); fclose(fp2); return;void out(char *filename) FILE *fp2;char ch26="编码："int i;strcat(ch,filename);fp2=fopen(ch,"rt");if(fp2=NULL) printf("n编码文件无法打开!");exit(1); for(i=1;!feof(fp2);i+) fscanf(fp2,"%s %ld %ld %ldn",hti.word,&hti.paren

12、t,&hti.lchild,&hti.rchild);n=i; fclose(fp2); return;void sort()int i,j; unsigned long min;char ch3;for(i=1;i<n;i+)for(j=i+1;j<=n;j+) if(hti.weight>htj.weight)min=htj.weight;htj.weight=hti.weight;hti.weight=min;strcpy(ch,hti.word);strcpy(hti.word,htj.word);strcpy(htj.word,ch);return;

13、void select(int t,int *s1,int *s2)int i;unsigned long min1,min2;min1=min2=4294967295;*s1=*s2=0;for(i=1;i<=n;i+) if(hti.parent=0) if(hti.parent=0)&&(hti+1.parent=0)&&i+1<=n)min1=hti.weight;*s1=i;min2=hti+1.weight;*s2=i+1;break;else min1=hti.weight;*s1=i;break; for(i=n+1;i<=t;

14、i+)if(hti.weight<min1&&hti.parent=0)min2=min1;*s2=*s1;min1=hti.weight;*s1=i;continue;else if(hti.weight<min2&&hti.parent=0)min2=hti.weight;*s2=i;return;void ctrHuffTree(word *head) int i,m,s1,s2; word *p; for(i=1,p=head->next;i<=n&&p!=NULL;i+,p=p->next) hti.wei

15、ght=p->times;strcpy(hti.word,p->word);hti.parent=hti.rchild=hti.lchild=0; m=2*n-1; for(i=n+1;i<=m;i+) hti.parent=hti.rchild=hti.lchild=hti.weight=0; sort(); for(i=n+1;i<=m;i+) select(i-1,&s1,&s2); strcpy(hti.word,"无"); hti.weight=hts1.weight+hts2.weight; hts2.parent=hts

16、1.parent=i; hti.lchild=s2; hti.rchild=s1; return;void ctrHuffmancode() char *cd;int c,p,start,i;cd=(char *)malloc(n+1)*sizeof(char);cdn='0'for(i=1;i<=n;i+) start=n;c=i; p=hti.parent;while(p!=0) -start;if(htp.lchild=c)cdstart='0'else if(htp.rchild=c)cdstart='1'c=p; p=htp.pa

17、rent;hci=(char *)malloc(n-start)*(sizeof(char);strcpy(hci,&cdstart);free(cd);return;void compress(char *filename,char *filename1)FILE *fp1,*fp2;int t,i=0,j=0,sum=0;char ch3, tr8;unsigned char c;fp1=fopen(filename,"rt");if(fp1=NULL) printf("n无法打开 %s 文件,或该文件不存在!",filename);exit

18、(0);fp2=fopen(filename1,"wb");if(fp2=NULL) printf("n无法创建 %s 文件!",filename1);exit(0);system("cls");printf("nnnnnnnn 压缩中，请稍候.");while(ch0=fgetc(fp1)!=EOF)if(ch0<0|ch0>254) ch1=fgetc(fp1); ch2='0' else ch1='0'for(t=1;t<=n;t+) if(ch0=10&am

19、p;&ch1='0') strcpy(ch,"-n"); if(ch0=32&&ch1='0') strcpy(ch,"-t"); if(!strcmp(htt.word,ch) while(j<=7)for(;*(hct+i)!='0'i+,j+)trj=*(hct+i);if(j=7)sum=(tr7-48)*1+(tr6-48)*2+(tr5-48)*4+(tr4-48)*8+(tr3-48)*16+(tr2-48)*32+(tr1-48)*64+(tr0-48)*128

20、;c=(unsigned char)sum;fputc(c,fp2);j=0;i+;break;if(*(hct+i)='0')i=0;t=n+1;break;if(j<=7&&j!=0)for(;j<=7;j+)trj=48;if(j=7)sum=(tr7-48)*1+(tr6-48)*2+(tr5-48)*4+(tr4-48)*8+(tr3-48)*16+(tr2-48)*32+(tr1-48)*64+(tr0-48)*128;c=(unsigned char)sum; fputc(c,fp2);break;fclose(fp1);fclose(

21、fp2);system("cls");printf("nnnnnnnn 压缩完成!(按任意键返回)n");getch();return;void re_compress(char *filename1,char *filename2)int m8,i=0,j=0,flag=1;HuffTree p; char ch,cha='t'unsigned char c;FILE *fp1,*fp2;p=htn;fp1=fopen(filename1,"rb");if(fp1=NULL) printf("n无法打开压缩

22、文件 %s,或该文件不存在!",filename1);exit(0);fp2=fopen(filename2,"wt");if(fp2=NULL) printf("n无法创建 %s 文件!",filename2);exit(0);system("cls");printf("nnnnnnnn 解压中，请稍候.");ch=fgetc(fp1);c=(unsigned char)ch;while(!feof(fp1) while(flag!=0) for(i=7;i>=0;i-)mi=c%2;flag=c

23、=c/2;if(i=0|c=0) break;if(unsigned char)ch<128&&(c=0)&&(i!=0) for(i=-i;i>=0;i-) mi=0; if(i=0) break; for(j=i;j<=7;j+) if(mj=0) p=htp.lchild;else if(mj=1) p=htp.rchild;if(p.lchild=0&&p.rchild=0) if(strcmp(p.word,"-n")=0) fputc('n',fp2);elseif(strcmp(

24、p.word,"-t")=0) fputc(' ',fp2); else if(strcmp(p.word,"-n")!=0&&strcmp(p.word,"-t")!=0) fprintf(fp2,"%s",p.word); p=htn; ch=fgetc(fp1); c=(unsigned char)ch;flag=1;fclose(fp1);fclose(fp2);system("cls");printf("nnnnnnnn 解压完成!(按任意键返回)n");getch();return;main() char filename20,filename120,filename220; word_list head; char choise; head=(word *)malloc(sizeof(word); head->next=NULL;while(1)system("cls");printf("nnnnn *");printf("nn 请选择您要执行的操作:nn