哈夫曼编码与译码 数据结构实验Word格式.docx
《哈夫曼编码与译码 数据结构实验Word格式.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码与译码 数据结构实验Word格式.docx（14页珍藏版）》请在冰点文库上搜索。
#include<
string.h>
ctype.h>
malloc.h>
//malloc（）
limits.h>
//INT,MAX
stdio.h>
//EOF,NULL
stdlib.h>
//atoi（）
io.h>
//eof（）
math.h>
//floor（）,ceil（）,abs（）
process.h>
//exit（）
iostream.h>
//cout,cin
//函数结果状态代码
#defineTRUE1
#defineFALSE0
#defineOK1
#defineERROR0
#defineINFEASIBLE-1
//OVERFLOW在math.h中已定义为3
typedefintStatus;
typedefintBoolean;
//布尔类型
main.cpp:
#include"
head.h"
typedefstruct
{
unsignedintweight;
unsignedintparent,lchild,rchild;
}HTNode,*HuffmanTree;
/*动态分配数组存储赫夫曼树*/
typedefchar**HuffmanCode;
/*动态分配数组存储赫夫曼编码表*/
/*求赫夫曼编码。
实现算法6.12的程序*/
intmin1（HuffmanTree&
t,inti）
{/*函数voidselect（）调用*/
intj,flag;
unsignedintk=UINT_MAX;
/*取k为不小于可能的值*/
for（j=1;
j<
=i;
j++）
if（t[j].weight<
k&
&
t[j].parent==0）
k=t[j].weight,flag=j;
t[flag].parent=1;
returnflag;
}
voidSelect（HuffmanTree&
t,inti,int&
s1,int&
s2）
{/*s1为最小的两个值对应结点权值小的那个*/
intj;
s1=min1（t,i）;
s2=min1（t,i）;
if（t[s1].weight>
t[s2].weight）
{
j=s1;
s1=s2;
s2=j;
}
voidHuffmanCoding（HuffmanTree&
HT,HuffmanCode&
HC,int*w,intn）/*算法6.12*/
{/*w存放n个字符的权值（均>
0）,构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC*/
intm,i,s1,s2,start;
unsignedc,f;
HuffmanTreep;
char*cd;
if（n<
=1）
return;
m=2*n-1;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;
/*0号单元未用*/
for（p=HT+1,i=1;
i<
=n;
++i,++p,++w）
p->
weight=*w;
parent=0;
lchild=0;
rchild=0;
for（;
=m;
++i,++p）
weight=0;
for（i=n+1;
++i）/*建赫夫曼树*/
{/*在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2*/
Select（HT,i-1,s1,s2）;
HT[s1].parent=HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
/*从叶子到根逆向求每个字符的赫夫曼编码*/
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;
/*分配n个字符编码的头指针向量（[0]不用）*/
cd=（char*）malloc（n*sizeof（char））;
/*分配求编码的工作空间*/
cd[n-1]='
\0'
;
/*编码结束符*/
for（i=1;
i++）
{/*逐个字符求赫夫曼编码*/
start=n-1;
/*编码结束符位置*/
for（c=i,f=HT[i].parent;
f!
=0;
c=f,f=HT[f].parent）
/*从叶子到根逆向求编码*/
if（HT[f].lchild==c）
cd[--start]='
0'
else
1'
HC[i]=（char*）malloc（（n-start）*sizeof（char））;
/*为第i个字符编码分配空间*/
strcpy（HC[i],&
cd[start]）;
/*从cd复制编码（串）到HC*/
free（cd）;
/*释放工作空间*/
voidmain（）
intn;
HuffmanTreeHT;
HuffmanCodeHC;
do
{
cout<
<
"
请输入权值的个数（n>
1）:
n="
cin>
>
n;
}while（n<
=1）;
int*w=（int*）malloc（n*sizeof（int））;
cout<
请依次输入"
n<
个权值（整型）:
endl;
for（inti=0;
=n-1;
*（w+i）;
HuffmanCoding（HT,HC,w,n）;
赫夫曼编码为:
*（w+i-1）<
\t:
"
HC[i]<
运行结果：
赫夫曼树的形状为：
2.选做内容
哈夫曼译码
在前面必做内容的基础上，实现哈弗曼译码算法，对给定的一组编码（要求从终端输入），译出其对应的报文部分。
源代码：
#definemaxsize100//哈夫曼编码的最大位数
charch;
HC,char*ch,int*w,intn）/*算法6.12修改*/
++i,++p,++w,++ch）
ch=*ch;
ch='
voidHuffmanDecoding（HuffmanTree&
HT,intn）//依次读入电文，根据哈夫曼树译码
inti,j=0,k=0,flag=0;
charc[maxsize]="
\0"
charb[maxsize];
charendflag='
2'
//电文结束标志取2
i=2*n-1;
//从根结点开始往下搜索
printf（"
请输入译码（以'
为结束标志）:
）;
gets（b）;
while（b[j]!
='
）
if（b[j]=='
i=HT[i].lchild;
//走向左孩子
elseif（b[j]=='
i=HT[i].rchild;
//走向右孩子
else
{
cout<
输入译码有错."
flag=1;
break;
}
if（HT[i].lchild==0）//HT[k]是叶结点
c[k++]=HT[i].ch;
c[k]='
i=2*n-1;
j++;
if（HT[i].lchild!
=0&
i!
=2*n-1&
b[j]=='
）//译码读完，但尚未到叶子结点
elseif（flag==0）
printf（"
译码对应的报文为:
puts（c）;
char*c=（char*）malloc（n*sizeof（char））;
个字符及相应的权值（中间用空格隔开）:
输入第%d个字符和权值:
i+1）;
scanf（"
%c%d"
c+i,w+i）;
getchar（）;
HuffmanCoding（HT,HC,c,w,n）;
*（c+i-1）<
\n下面进行赫夫曼译码---->
HuffmanDecoding（HT,n）;
//依次读入电文，根据哈夫曼树译码
下面为译码输入错误的情况：
【小结或讨论】
通过本次实验，掌握了Huffman树的概念、特点和存储结构；
并且掌握了Huffman树的构造方法；
还学会了运用Huffman树解决编码问题。
能够用Huffman树实现编码和译码的功能。
必做内容里，用每个字符对应的权值代替了该字符，因为在定义Huffman树的存储结构时，没有添加存储字符的数据域。
这一点在选作内容里做了修改，可以在创建Huffman树的时候将权值连同字符一起输入。
在译码过程中，可能面对输入的译码有错的情况，这时候要添加程序段判断是何种出错类型，并作出相应处理操作。
比如有可能只输入了某个字符编码的前几位，这时候不能从Huffman树根结点访问到叶子结点，输入有错。
还有一种情况，就是输入的译码前面的部分是正确的，但是后面出错了，这时候整个译码是错误的，不用将前面正确的报文输出，所以程序中定义了一个char型数组用来存放翻译过的译文，如果译文结束了都没有出错，就将该数组里面的内容输出，否则不输出。
这里，在向char型数组里存放报文的时候，每存入一个就将该报文的下一个存储位置置为’\0’，以保证最后输出的全是译码对应的报文。
程序中是以字符’2’作为结束标记的，也可以以其他字符作为结束标记。
升级会员 