数据结构实验报告哈夫曼树.docx
《数据结构实验报告哈夫曼树.docx》由会员分享，可在线阅读，更多相关《数据结构实验报告哈夫曼树.docx（13页珍藏版）》请在冰点文库上搜索。
数据结构实验报告哈夫曼树
数据结构实验报告
实验题目：
Huffman编码与解码
姓名：
学号：
院系：
实验名称：
Huffman编码与解码实验
问题描述：
本实验需要以菜单形式完成以下功能：
1.输入电文串
2.统计电文串中各个字符及其出现的次数
3.构造哈弗曼树
4.进行哈弗曼编码
5.将电文翻译成比特流并打印出来
6.将比特流还原成电文
数据结构的描述：
逻辑结构：
本实验可用二叉树实现，其逻辑结构为一对二的形式，即一个结点对应两个结点。
在实验过程中我们也应用到了栈的概念。
存储结构：
使用结构体来对数据进行存储：
typedefstruct
{
intweight;
intparent,lc,rc;
}HTNode,*HuffmanTree;
typedefstructLNode
{
char*elem;
intstacksize;
inttop;
}SqStack;
在main函数里面定义一个哈弗曼树并实现上述各种功能。
程序结构的描述：
本次实验一共构造了10个函数：
1.voidHuffTree（HuffmanTree&HT,intn[],intmun）;
此函数根据给定的mun个权值构建哈弗曼树，n[]用于存放num个权值。
2.voidSelect（HuffmanTree&HT,intn,inti,int&s1,int&s2）;
此函数用于在HT[1,i-1]中选择parent为0且weight为最小的两个结点，其下标分别为s1,s2.
3.voidHuffmanCoding（HuffmanTreeHT,char**&HC,intn）;
此函数从哈弗曼树HT上求得n个叶子结点的哈弗曼编码并存入数组HC中。
4.voidCoding（HuffmanTreeHT,char**HC,introot,SqStack&S）；
此函数用于哈弗曼编码，先序遍历哈弗曼树HT，求得每个叶子结点的编码字符串，存入数组HC，S为一个顺序栈，用来记录遍历路径，root是哈弗曼数组HT中根结点的位置下标。
5.voidInitStack（SqStack&S）;
此函数用于初始化一个栈。
6.voidPop（SqStack&S,chare）;
此函数为出栈操作。
7.voidPush（SqStack&S,chare）;
此函数为进栈操作。
8.intStackLength（SqStackS）;
此函数用于求栈长，返回一个int型的值。
9.intFind（chara,chars[],intnum）;
此函数用于查找字符a在电文串中的位置。
10.intRecover（HuffmanTreeHT,char**HC,charstring[],chara[],charb[],intn）;
此函数用于将比特流还原成电文。
调试分析：
输入任意一个字符串，如输入welcometoustc:
运行结果如下：
按照提示输入任意一个或多个哈弗曼编码，如输入11111110101：
结果正确。
若输入一个11111：
结果正确。
实验完成！
实验体会和收获：
本次实验提高了对哈弗曼树的认识，同时加深了对二叉树的理解，在栈的运用上更加熟练，对数组的应用也有了提高。
源代码：
#include
#include
#include
#include
typedefstruct
{
intweight;
intparent,lc,rc;
}HTNode,*HuffmanTree;
typedefstructLNode
{
char*elem;
intstacksize;
inttop;
}SqStack;
#definesize20
voidHuffTree（HuffmanTree&HT,intn[],intmun）;
voidSelect（HuffmanTree&HT,intn,inti,int&s1,int&s2）;
voidHuffmanCoding（HuffmanTreeHT,char**&HC,intn）;
voidCoding（HuffmanTreeHT,char**HC,introot,SqStack&S）;
voidInitStack（SqStack&S）;
voidPop（SqStack&S,chare）;
voidPush（SqStack&S,chare）;
intStackLength（SqStackS）;
intFind（chara,chars[],intnum）;
intRecover（HuffmanTreeHT,char**HC,charstring[],chara[],charb[],intn）;
intmain（）
{
inti=0,n[size]={0},j=0,k=1,num=0;
charstring[size]={0},m[size]={0},a[size]={0},b[size]={0};
char**HC;
HuffmanTreeHT;
printf（"请输入电文串:
\n"）;
scanf（"%s",string）;
strcpy（m,string）;
while（string[j]）
{
if（string[j]!
='#'）a[k]=string[j];
i=j;
while（string[i]）
{
if（string[i]==a[k]）
{
string[i]='#';
n[k]++;
}
i++;
}
if（n[k]!
=0）
{
printf（"该电文中字符%c出现次数为%d\n",a[k],n[k]）;
num++;
k++;
}
j++;
}
printf（"哈弗曼树:
\n"）;
HuffTree（HT,n,num）;
for（i=1;i<=2*num-1;i++）printf（"%d\t%d\t%d\t%d\n",HT[i].weight,HT[i].parent,HT[i].lc,HT[i].rc）;
printf（"哈弗曼编码:
\n"）;
HuffmanCoding（HT,HC,num）;
for（i=1;i<=num;i++）
{
printf（"%c:
%s\n",a[i],HC[i]）;
}
printf（"\n该电文的哈弗曼编码为:
\n"）;
i=0;
while（string[i]）
printf（"%s",HC[Find（m[i++],a,num）]）;
printf（"\n请输入哈弗曼编码：
\n"）;
scanf（"%s",string）;
if（Recover（HT,HC,string,a,b,num））printf（"%s\n",b）;
elseprintf（"代码有误!
\n"）;
system（"pause"）;
return0;
}
voidHuffTree（HuffmanTree&HT,intn[],intnum）
{
inti,m,s1,s2;
m=2*num-1;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
for（i=1;i<=m;i++）
{
HT[i].weight=i<=num?
n[i]:
0;
HT[i].lc=HT[i].rc=HT[i].parent=0;
}
for（i=num+1;i<=m;i++）
{
Select（HT,num,i,s1,s2）;
HT[i].lc=s1;
HT[i].rc=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
HT[s1].parent=HT[s2].parent=i;
}
}
voidSelect（HuffmanTree&HT,intn,inti,int&s1,int&s2）
{
intk,t;
s1=s2=-1;
k=1;
while（s1==-1）
{
if（HT[k].parent==0）
s1=k;
k++;
}
k=1;
while（s2==-1||s2==s1）
{
if（HT[k].parent==0）
s2=k;
k++;
}
if（HT[s2].weight{
t=s2;s2=s1;s1=t;
}
for（k=1;k{
if（HT[k].parent==0）
{
if（HT[k].weight=s1&&k!
=s2）
{
s2=s1;
s1=k;
}
elseif（HT[k].weight=HT[s1].weight&&k!
=s1&&k!
=s2）s2=k;
}
}
}
voidHuffmanCoding（HuffmanTreeHT,char**&HC,intn）
{
SqStackS;
InitStack（S）;
HC=（char**）malloc（（n+1）*sizeof（char*））;
Coding（HT,HC,2*n-1,S）;
}
voidCoding（HuffmanTreeHT,char**HC,introot,SqStack&S）
{
if（root!
=0）
{
if（HT[root].lc==0）
{
Push（S,'\0'）;
HC[root]=（char*）malloc（（StackLength（S）））;
strcpy（HC[root],S.elem）;
Pop（S,'\0'）;
}
Push（S,'0'）;
Coding（HT,HC,HT[root].lc,S）;
Pop（S,'\0'）;
Push（S,'1'）;
Coding（HT,HC,HT[root].rc,S）;
Pop（S,'\0'）;
}
}
voidInitStack（SqStack&S）
{
S.elem=（char*）malloc（size*sizeof（char））;
S.stacksize=size;
S.top=-1;
}
voidPush（SqStack&S,chare）
{
S.elem[++S.top]=e;
}
voidPop（SqStack&S,chare）
{
if（S.top==-1）return;
e=S.elem[S.top--];
return;
}
intStackLength（SqStackS）
{
if（S.top==-1）return（0）;
return（S.top）;
}
intFind（chara,chars[],intnum）
{
inti;
for（i=1;i<=num;i++）
if（a==s[i]）returni;
return0;
}
intRecover（HuffmanTreeHT,char**HC,charstring[],chara[],charb[],intn）
{
inti=0,j=0,k,m=0,t=0,h=0;
chars[size];
k=2*n-1;
while（string[i]）
{
if（!
HT[k].lc&&!
HT[k].rc）
{
if（string[i]=='0'）{s[j]='\0';k=2*n-1;t=1;j=0;}
if（string[i]=='1'）
{
s[j]='\0';
k=2*n-1;
t=1;
j=0;
}
for（h=1;h<=n;h++）
if（!
strcmp（HC[h],s））
b[m++]=a[h];
}
else
{
if（string[i]=='0'）{k=HT[k].lc;s[j++]='0';}
if（string[i]=='1'）
{
k=HT[k].rc;
s[j]='1';
j++;
}
t=0;
}
if（!
t）
i++;
}
if（!
HT[k].lc&&!
HT[k].rc）
{
if（string[i-1]=='0'）{s[j]='\0';k=2*n-1;j=0;}
if（string[i-1]=='1'）
{
s[j]='\0';
k=2*n-1;
t=1;
j=0;
}
for（h=1;h<=n;h++）
if（!
strcmp（HC[h],s））
b[m++]=a[h];
}
b[m]='\0';
if（k==2*n-1）return1;
elsereturn0;
}
升级会员 