哈弗曼压缩软件数据结构试验报告附源程序.docx
《哈弗曼压缩软件数据结构试验报告附源程序.docx》由会员分享，可在线阅读，更多相关《哈弗曼压缩软件数据结构试验报告附源程序.docx（22页珍藏版）》请在冰点文库上搜索。
哈弗曼压缩软件数据结构试验报告附源程序
数据结构课程设计报告
题目：
基于哈夫曼编码的压缩软件
系部名称
：
计算机
专业名称
：
软件工程
班级
：
0802
学号
：
XXXXXX
学生姓名
：
稻草人
指导教师
：
XXXXX
时间
：
2010XX--2010YY
一、 课程设计目的
通过运用哈夫曼树的知识编写该压缩与解压软件，能使学生将所学
的理论知识应用起来，有效地运用到解决实际问题中去，提高学生的自
身的编程能力，从而达到学以致用的目的。
二、课程设计内容
1．应用系统分析，建立该系统的功能模块框图及界面的组织和设计；
2．分析系统中的各个函数及它们之间的关系；
3．根据问题描述，设计系统的结构体及各个函数；
4．设计哈弗曼树的构造算法和哈弗曼编码算法；
5．完成设计的系统各个应用模块；
6．将各个模块整合进行功能测试。
三、需求分析
哈弗曼压缩软件
1.需求分析目的
为明确软件需求、安排项目规划与进度、组织软件开发与测试，供设计人员、开发人员参考。
2.项目开发计划
时间
开发内容
6月22日
读取文本文件，并统计文件中字母个数
6月23日
建立huffman树对文件，进行huffman编码
6月24日
压缩
6月25日
解压缩
3.任务目标
能比较完善的对txt文件进行压缩和解压缩。
4.数据字典
名称：
字符频率
别名：
weight
描述：
读取文本文件，并统计文件中字母个数
定义：
字符频率=字符+数量
名称：
结点
别名：
HTNode
描述：
建立huffman树的叶子和非叶子结点
定义：
结点=数量+字符+双亲结点+左孩子结点+右孩子结点
位置：
编码文件
5.功能划分
⏹压缩
⏹解压缩
四、概要设计
哈弗曼压缩软件
1建立哈夫曼树。
根据哈夫曼编码技术，可以将已经给出的字母的使用频率建立一个哈夫曼树，即以二叉树的形式将英文字母和空格存储。
2编码。
利用二叉树的遍历知识，左孩子用“0”表示，右孩子用“1”表示，将输入的一组英文句子进行编码。
3测试和输出。
程序要求的测试的英文句子是：
“knowledgeispower”，输出每一个字母然后给出相应的哈夫曼编码。
本程序输入字母以“#”结束。
4译码。
本程序要求对已编码的数字能够给以反编码。
.函数调用示意图
六、调试情况，设计技巧及体会
1．测试结论
◆能较好地进行压缩和解压
◆不足的是对最后所补的0未处理，解压会多出几个字符。
2.设计技巧
本软件可对字母、汉字可以实现共同压缩，压缩率在50%以上，压缩后对哈夫曼树进行保存，以便后面解压，对叶子结点只保存其字符、左孩子、右孩子，对非叶子结点保存左孩子和右孩子。
解压时从根结点开始，利用哈夫曼树进行解压，遇到0，找左孩子，遇到1找右孩子，到叶子结点时，输出字符。
3．心得体会：
通过这次课题实验的程序实践，我实在获益匪浅！
数据结构是上个学期开展的一门学科，学习好这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。
同时，学习这门学科也是艰辛的，因为它比较难懂，这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中领悟。
这次的程序设计对我来说无疑是一个具大的考验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。
因为开始时基础不是很好，过程中遇到了不少的阻碍，编写程序的进度也比较慢。
虽然如此，但是通过自己的努力与老师的指导，我对这次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的基础下写出了本次实验的核心算法，并使其能够正常的运行。
这一个多月的设计工作，让我体会到了作为一个编程人员的艰难，一个算法到具体实现，再到应用层面的开发是需要有一段较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程人员还要花很多的时间去完善它，其中包含的心酸，外人是不会明白的。
非常感谢在背后一直给我指导的老师和同学，他们的支持和鼓励让我在遇到挫折时能够站起来战胜它，也让我走到了今天这一步，完成了实验的设计。
今后，我会更加努力的学习专业知识，提高自我的能力。
七、参考文献
《c语言程序设计》谭浩强主编
八、附录：
源代码
#include
#include
#include
#include
#include
typedefstructword
{
charword[3];
unsignedlongtimes;
structword*next;
}word,*word_list;
typedefstructTnode
{
unsignedlongweight;
charword[3];
longparent,lchild,rchild;
}Tnode,HuffTree;
HuffTreeht[5000];
char*hc[5000];
intn=0;
voidstat（word_listhead,char*filename）
{
FILE*fp;
charch[3];
intflag=0;
word*p,*q,*s;
fp=fopen（filename,"rt"）;
if（fp==NULL）
printf（"\n无法打开要压缩的文件,或该文件不存在!
"）;
p=head;
while（（ch[0]=fgetc（fp））!
=EOF）
{
if（ch[0]<0||ch[0]>254）
{
ch[1]=fgetc（fp）;
ch[2]='\0';
}
elsech[1]='\0';
if（ch[0]==10）strcpy（ch,"-n"）;
if（ch[0]==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;
++n;
}
flag=0;
}
p->next=NULL;
fclose（fp）;
return;
}
voidprotect1（char*filename）
{
FILE*fp2;
charch[26]="编码：
";
inti;
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%ld\n",ht[i].word,ht[i].parent,ht[i].lchild,ht[i].rchild）;
}
fclose（fp2）;
return;
}
voidout（char*filename）
{
FILE*fp2;
charch[26]="编码：
";
inti;
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%ld\n",ht[i].word,&ht[i].parent,&ht[i].lchild,&ht[i].rchild）;
n=i;
}
fclose（fp2）;
return;
}
voidsort（）
{
inti,j;
unsignedlongmin;
charch[3];
for（i=1;ifor（j=i+1;j<=n;j++）
{
if（ht[i].weight>ht[j].weight）
{
min=ht[j].weight;
ht[j].weight=ht[i].weight;
ht[i].weight=min;
strcpy（ch,ht[i].word）;
strcpy（ht[i].word,ht[j].word）;
strcpy（ht[j].word,ch）;
}
}
return;
}
voidselect（intt,int*s1,int*s2）
{
inti;
unsignedlongmin1,min2;
min1=min2=4294967295;
*s1=*s2=0;
for（i=1;i<=n;i++）
{
if（ht[i].parent==0）
{
if（（ht[i].parent==0）&&（ht[i+1].parent==0）&&i+1<=n）
{
min1=ht[i].weight;
*s1=i;
min2=ht[i+1].weight;
*s2=i+1;
break;
}
else
{
min1=ht[i].weight;
*s1=i;
break;
}
}
}
for（i=n+1;i<=t;i++）
{
if（ht[i].weight{
min2=min1;
*s2=*s1;
min1=ht[i].weight;
*s1=i;
continue;
}
elseif（ht[i].weight{
min2=ht[i].weight;
*s2=i;
}
}
return;
}
voidctrHuffTree（word*head）
{
inti,m,s1,s2;
word*p;
for（i=1,p=head->next;i<=n&&p!
=NULL;i++,p=p->next）
{
ht[i].weight=p->times;
strcpy（ht[i].word,p->word）;
ht[i].parent=ht[i].rchild=ht[i].lchild=0;
}
m=2*n-1;
for（i=n+1;i<=m;i++）
{
ht[i].parent=ht[i].rchild=ht[i].lchild=ht[i].weight=0;
}
sort（）;
for（i=n+1;i<=m;i++）
{
select（i-1,&s1,&s2）;
strcpy（ht[i].word,"无"）;
ht[i].weight=ht[s1].weight+ht[s2].weight;
ht[s2].parent=ht[s1].parent=i;
ht[i].lchild=s2;ht[i].rchild=s1;
}
return;
}
voidctrHuffmancode（）
{
char*cd;
intc,p,start,i;
cd=（char*）malloc（（n+1）*sizeof（char））;
cd[n]='\0';
for（i=1;i<=n;i++）
{
start=n;
c=i;p=ht[i].parent;
while（p!
=0）
{
--start;
if（ht[p].lchild==c）
cd[start]='0';
elseif（ht[p].rchild==c）
cd[start]='1';
c=p;p=ht[p].parent;
}
hc[i]=（char*）malloc（（n-start）*（sizeof（char）））;
strcpy（hc[i],&cd[start]）;
}
free（cd）;
return;
}
voidcompress（char*filename,char*filename1）
{
FILE*fp1,*fp2;
intt,i=0,j=0,sum=0;
charch[3],tr[8];
unsignedcharc;
fp1=fopen（filename,"rt"）;
if（fp1==NULL）
{
printf（"\n无法打开%s文件,或该文件不存在!
",filename）;
exit（0）;
}
fp2=fopen（filename1,"wb"）;
if（fp2==NULL）
{
printf（"\n无法创建%s文件!
",filename1）;
exit（0）;
}
system（"cls"）;
printf（"\n\n\n\n\n\n\n\n压缩中，请稍候..."）;
while（（ch[0]=fgetc（fp1））!
=EOF）
{
if（ch[0]<0||ch[0]>254）
{
ch[1]=fgetc（fp1）;
ch[2]='\0';
}
else
ch[1]='\0';
for（t=1;t<=n;t++）
{
if（ch[0]==10&&ch[1]=='\0'）strcpy（ch,"-n"）;
if（ch[0]==32&&ch[1]=='\0'）strcpy（ch,"-t"）;
if（!
strcmp（ht[t].word,ch））
{
while（j<=7）
{
for（;*（hc[t]+i）!
='\0';i++,j++）
{
tr[j]=*（hc[t]+i）;
if（j==7）
{
sum=（tr[7]-48）*1+（tr[6]-48）*2+（tr[5]-48）*4+（tr[4]-48）*8+（tr[3]-48）*16+（tr[2]-48）*32+（tr[1]-48）*64+（tr[0]-48）*128;
c=（unsignedchar）sum;
fputc（c,fp2）;
j=0;
i++;
break;
}
}
if（*（hc[t]+i）=='\0'）
{
i=0;
t=n+1;
break;
}
}
}
}
}
if（j<=7&&j!
=0）
{
for（;j<=7;j++）
{tr[j]=48;
if（j==7）
{
sum=（tr[7]-48）*1+（tr[6]-48）*2+（tr[5]-48）*4+（tr[4]-48）*8+（tr[3]-48）*16+（tr[2]-48）*32+（tr[1]-48）*64+（tr[0]-48）*128;
c=（unsignedchar）sum;
fputc（c,fp2）;
break;
}
}
}
fclose（fp1）;
fclose（fp2）;
system（"cls"）;
printf（"\n\n\n\n\n\n\n\n压缩完成!
（按任意键返回）\n"）;
getch（）;
return;
}
voidre_compress（char*filename1,char*filename2）
{
intm[8],i=0,j=0,flag=1;
HuffTreep;
charch,cha='\t';
unsignedcharc;
FILE*fp1,*fp2;
p=ht[n];
fp1=fopen（filename1,"rb"）;
if（fp1==NULL）
{
printf（"\n无法打开压缩文件%s,或该文件不存在!
",filename1）;
exit（0）;
}
fp2=fopen（filename2,"wt"）;
if（fp2==NULL）
{
printf（"\n无法创建%s文件!
",filename2）;
exit（0）;
}
system（"cls"）;
printf（"\n\n\n\n\n\n\n\n解压中，请稍候..."）;
ch=fgetc（fp1）;
c=（unsignedchar）ch;
while（!
feof（fp1））
{
while（flag!
=0）
{
for（i=7;i>=0;i--）
{
m[i]=c%2;
flag=c=c/2;
if（i==0||c==0）
{
break;
}
}
if（（unsignedchar）ch<128&&（c==0）&&（i!
=0））
{
for（i=--i;i>=0;i--）
{
m[i]=0;
if（i==0）break;
}
}
for（j=i;j<=7;j++）
{
if（m[j]==0）p=ht[p.lchild];
elseif（m[j]==1）p=ht[p.rchild];
if（p.lchild==0&&p.rchild==0）
{
if（strcmp（p.word,"-n"）==0）
{
fputc（'\n',fp2）;
}
elseif（strcmp（p.word,"-t"）==0）
{
fputc（'',fp2）;
}
elseif（strcmp（p.word,"-n"）!
=0&&strcmp（p.word,"-t"）!
=0）
{
fprintf（fp2,"%s",p.word）;
}
p=ht[n];
}
}
}
ch=fgetc（fp1）;
c=（unsignedchar）ch;
flag=1;
}
fclose（fp1）;
fclose（fp2）;
system（"cls"）;
printf（"\n\n\n\n\n\n\n\n解压完成!
（按任意键返回）\n"）;
getch（）;
return;
}
main（）
{
charfilename[20],filename1[20],filename2[20];
word_listhead;
charchoise;
head=（word*）malloc（sizeof（word））;
head->next=NULL;
while
（1）
{
system（"cls"）;
printf（"\n\n\n\n\n************************************"）;
printf（"\n\n请选择您要执行的操作:
\n\n1.压缩文件\n\n2.解压文件\n\n3.退出\n"）;
printf（"\n\n************************************"）;
flushall（）;
choise=getch（）;
switch（choise）
{
case'1':
{
system（"cls"）;
printf（"\n\n\n\n\n\n\n\n请输入要压缩的文件名:
"）;
flushall（）;
scanf（"%s",filename）;
printf（"\n\n请输入压缩后的文件名:
"）;
flushall（）;
scanf（"%s",filename1）;
stat（head,filename）;
ctrHuffTree（head）;
ctrHuffmancode（）;
protect1（filename1）;
compress（filename,filename1）;
break;
}
case'2':
{
system（"cls"）;
printf（"\n\n\n\n\n请输入要解压的文件名:
"）;
flushall（）;
scanf（"%s",filename1）;
printf（"\n请输入解压后的文件名:
"）;
flushall（）;
scanf（"%s",filename2）;
out（filename1）;
re_compress（filename1,filename2）;
break;
}
case'3':
{
exit
（1）;
printf（"\n\n"）;
}
default:
{
system（"cls"）;
printf（"\n您的选择有误!
"）;
break;
}
}
}
printf（
升级会员 