数据结构实验报告 huffman编码和解码算法.pdfVIP

（规格为A4纸或A3纸折叠）

佛山科学技术学院（用四号宋体）

实验报告（用小二号黑体）

课程名称数据结构实验

实验项目用Huffman树进行编码和解码算法

专业班级姓名学号

指导教师成绩日期

（用小四号宋体）

一、目的和要求

1、通过本实验，熟悉二叉树、Huffman树的基本概念，掌握二叉树的存储结构及各种

算法。

2、熟悉用Huffman树进行电文的加密与解密算法。

二、实验原理

Huffman树是一种特殊的二叉树，其叶结点的编码是一种前缀码，同时，通过统计字符

的频度，能够达到编码电文的最小化。

三、实验步骤

1、统计电文中字符的出现频率。

2.用统计频率建立Hffman树。

3．生成前缀码；

4．建立huffman树的解码算法．

5．用随机输入的电文完成编码与解码过程。

四、源程序

#includestdio.h

#includestdlib.h

#includestring.h

#defineMAX100

structHTNode

{

chara;

intweight;

intparent,lchild,rchild;

}*HT;//动态分配数组存储赫夫曼树

char**HC;

intn=0,m=0;

char*write()//存储输入的电文

{

char*p,*q;

请输入电文(结束输入请按enter）：

p=(char*)malloc(MAX*sizeof(char));//申请存储输入的电文的空间

if(!p)exit(0);

q=p;

while(*q!=

)

{//******录入电文，每录入一个字符同时给电文长度计数器n加一*******

//*****************遇到换行符时结束录入***************

n=n+1;

if(n=MAX)//判断已申请的空间是否足够录入，不足则追加空间

{

p=(char*)realloc(q,(MAX+10)*sizeof(char));

if(!p)exit(0);

}

q++;

}

return(p);

}

voidweight(char*p)//求电文中各字符的概率，并将该概率当作各字符的权值

{

char*q,*q1,temp;

structHTNode*q2;

inti,j,t;

q1=q=(char*)malloc(n*sizeof(char));

for(;*p!=

;p++,q1++)*q1=*p;//将电文存放到q1指向的空间中

q1=q;

for(i=0;in-1;i++)

{//*****对电文中的字符进行排序，使得相同的字符地址连续，方便统计*****

t=i;

for(j=i+1;jn;j++)

if(*(q1+t)*(q1+j))t=j;

temp=*(q1+i);

*(q1+i)=*(q1+t);

*(q1+t)=temp;

}

temp=*q1;//标记当前为何种字符

m=1;

for(i=1;in;i++)//统计电文中出现过不同的字符的个数

{

q1++;

if(temp!=*q1)

{

m++;//字符种类计数器加一