第四次上机作业.docx
《第四次上机作业.docx》由会员分享，可在线阅读，更多相关《第四次上机作业.docx（15页珍藏版）》请在冰点文库上搜索。
第四次上机作业
第四次上机作业
——huffman编码和解码
姓名：
黄涛
班级：
070921
学号：
07092002
指导老师：
唐厚俭
上机时间：
2010年10月22号
一、摘要
一、实验目的
1、理解Huffman二叉树的概念
2、学会使用Huffman编码对数据进行无损压缩的原理
二、试验方法
1、通过对huffman编码和解码的编程，利用指针、数组等进行编写程序代码，并运行结果。
2、深入了解函数的嵌入、递归等方面的运用。
二、内容
一、问题重述
Huffman编码是一种常用的压缩编码方法，其基本原理是频繁使用的数据用较短的代码代替，较少使用的数据用较长的代码代替，每个数据的代码各不同。
这些代码都是二进制的，且码长是可变的，其实现主要通过借助huffman数即最优二叉树，是一类带权径最短的树。
二、问题分析
对于读入一ASCII文件，首先进行打开操作，当然，必须判断能否打开，打开后统计文档中字符出现的频度，并根据频度对每个字符生成Huffman编码，这些编码各不相同，要记录每个字符对应的huffman编码，计算出其总编码的长度，利用其概率算法计算编码效率。
对已编的bhuffman编码进行解码，其解码后生成huffman树，并将其输出、打印。
最后要对原始数据、每个字符对应的Huffman编码以及原文档的Huffman编码进行打出处理。
三、流程图
4、函数说明
1、输入文件，printf（"请输入你要打开的文件名:
"）通过if（（fp=fopen（name,"rt"））==NULL）判断能否打开，打不开进行存档失败，打开进行下一步操作。
2、对文件进行huffman编码，首先通过利用typedefstructnode进行函数声明，{
intweight;
structnode*lchild,*rchild,*parent;
structnode*next;
}HuffmanNode,*HuffmanTree;定义编码函数：
HuffmanNode、HuffmanTree，利用数组逐项进行编码，并且没行对应唯一的编码，对其字符在编码过程中，找出最小的字符利用指针编码，记录其码号，利用for语句依次进行下去，输出编码函数，完成函数编码，
3、对已编码完的文件进行解码操作；首先开程序开始时，对解码函数进行声明：
typedefstruct
{
charch;
charcode[N];
}CodeNode;；并保存。
然后接入huffman编码文件，分成HuffmanTreeHT,CodeNodeHC[],charstr[]三部分，分别进行数据的输入、输出、存储。
从零开始记录首个被解码字符，累加进行下去，最后输出其解码后的数据。
五、结论
通过领用一系列的函数将输入的文件进行huffman编码，解码，完成其要求，正确的解决了huffman编码、解码问题，并运行出了结果。
六、遇到的问题及解决方法
在编程过程中，起初靠里直接输入文件，但其能否打开并不知道，少了步判定，后加入判定，成功输入文件，对文件进行编码，感觉繁琐，故利用for语句，依次编码，同样也对编码文件进行了解码，总的说来，主要问题出现在后面的huffman树形式的输出以及解码后对解码数据的输出问题。
后通过多次调试将其解决，对函数的运用也得到熟悉。
七、程序代码
#include
#include
#include
#defineM1000
#defineN128
typedefstructnode
{
intweight;
structnode*lchild,*rchild,*parent;
structnode*next;
}HuffmanNode,*HuffmanTree;
typedefstruct
{
charch;
charcode[N];
}CodeNode;
intn;
voidOpen（chars[]）
{
FILE*fp;
charname[10];
inti=0;
printf（"请输入你要打开的文件名:
"）;
gets（name）;
if（（fp=fopen（name,"rt"））==NULL）
{
printf（"打开文件失败!
\n"）;
exit
（1）;
}
s[i++]=fgetc（fp）;
while（s[i-1]!
=EOF）
s[i++]=fgetc（fp）;
s[i]='\0';
printf（"读取到的字符：
\n"）;
puts（s）;
fclose（fp）;
}
voidSave（chars[]）
{
FILE*fp;
charname[10];
printf（"请输入你要保存的文件名：
"）;
gets（name）;
if（（fp=fopen（name,"wt"））==NULL）
{
printf（"保存文件失败!
\n"）;
exit
（1）;
}
fputs（s,fp）;
fclose（fp）;
}
voidSearchStr（chars[],charstr[],intcount[]）
{
inti,j,k=0;
for（i=0;icount[i]=0;
for（i=0;s[i];i++）
{
for（j=0;j{
if（str[j]==s[i]）
{
count[j]++;
break;
}
}
if（j==k）
{
str[k]=s[i];
count[k]++;
k++;
}
}
str[k-1]='\0';
n=k-1;
}
voidSelectMin（HuffmanTreeHT,intk,HuffmanTree*HT1,HuffmanTree*HT2）
{
inti,min;
HuffmanTreep;
min=3128;
for（p=HT,i=0;inext）
{
if（p->weightparent==NULL）
{
min=p->weight;
*HT1=p;
}
}
min=3128;
for（p=HT,i=0;inext）
{
if（p->weightparent==NULL&&p!
=*HT1）
{
min=p->weight;
*HT2=p;
}
}}
voidCreatHuffmanTree（HuffmanTree*HT,intcount[]）
{
inti;
HuffmanTreep,HT1,HT2;
p=*HT=（HuffmanTree）malloc（sizeof（HuffmanNode））;
p->next=p->lchild=p->rchild=p->parent=NULL;
for（i=0;i<2*n-1;i++）
{
p->next=（HuffmanTree）malloc（sizeof（HuffmanNode））;
p=p->next;
p->next=p->lchild=p->rchild=p->parent=NULL;
}
for（p=*HT,i=0;i{
p->weight=count[i];
p=p->next;
}
for（i=n;i<2*n-1;i++）
{
SelectMin（*HT,i,&HT1,&HT2）;
HT1->parent=HT2->parent=p;
p->lchild=HT1;
p->rchild=HT2;
p->weight=HT1->weight+HT2->weight;
p=p->next;
}
free（p）;
}
voidCodeHuffman（HuffmanTreeHT,CodeNodeHC[],charstr[]）
{
inti,j,k,x;
charch;
HuffmanTreep,q=HT;
for（i=0;iHC[i].ch=str[i];
for（i=0;i{
j=0;
x=0;
for（p=q;p->parent;p=p->parent）
{
if（p==p->parent->lchild）
HC[i].code[j++]='0';
else
HC[i].code[j++]='1';
}
HC[i].code[j]='\0';
k=j/2;
while（j>k）//编码反转
{
ch=HC[i].code[j-1];
HC[i].code[j-1]=HC[i].code[x];
HC[i].code[x]=ch;
j--;
x++;
}
q=q->next;
}
}
voidToltalCoding（CodeNodeHC[],chars[],charcode[]）
{
inti,j;
code[0]='\0';
for（i=0;s[i];i++）
{
for（j=0;j{
if（s[i]==HC[j].ch）
strcpy（code+strlen（code）,HC[j].code）;
}
}
}
voidDecoding（HuffmanTreeHT,charcode[],charstr[],charss[]）
{
inti,j,k=0;
HuffmanTreep,q,root;
for（root=HT;root->parent;root=root->parent）;
for（i=0,p=root;code[i];i++）
{
if（code[i]=='0'）
p=p->lchild;
else
p=p->rchild;
if（p->lchild==NULL&&p->rchild==NULL）
{
for（j=0,q=HT;q!
=p;q=q->next,j++）;
ss[k++]=str[j];
.
p=root;
}
}
ss[k]='\0';
printf（"解码结果:
\n"）;
puts（ss）;
}
voidmain（void）
{
inti=0;
//charxuanzhe;
chars[M],ss[M];//定义字符串数组，s[]存放将要编码的字符串，ss[]存解码后的字符串
charstr[N];//存放输入的字符串中n个不同的字符
intcount[N];//存放n个不同字符对应的在原字符串中出现的次数
charcode[M];//存放最终编码完成后的编码
//charchoice;
HuffmanTreeHT;//定义一个哈夫曼树的链表
CodeNodeHC[N];
Open（s）;
SearchStr（s,str,count）;
CreatHuffmanTree（&HT,count）;
CodeHuffman（HT,HC,str）;for（i=0;iprintf（"字符:
%c\t权值:
%d\t编码:
%s\n",str[i],count[i],HC[i].code）;
ToltalCoding（HC,s,code）;
Decoding（HT,code,str,ss）;
free（HT）;
}
升级会员 