数据结构实验报告哈夫曼树.docx
- 文档编号:17787627
- 上传时间:2023-08-03
- 格式:DOCX
- 页数:13
- 大小:29.36KB
数据结构实验报告哈夫曼树.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 =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; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 实验 报告 哈夫曼树