sout

-1-

福建农林大学计算机与信息学院

（程序设计类课程）

实验报告

课程名称：数据结构

姓名：邓建国

系：计算机与信息学院

专业：网络工程

年级：09级

学号：091154050

指导教师：黄思先

职称：副教授

-2-

福建农林大学计算机与信息学院实验报告

系：计算机与信息专业：网络工程年级：09级

姓名：邓建国学号：091154050实验室号：_计算机号：

实验二哈夫曼树及哈夫曼编码译码的实现

一、实验目的和要求

1，掌握树及二叉树的基本概念

2，熟悉二叉树的运算和应用

3，理解哈夫曼树的概念及哈夫曼编码译码的实现

二、实验内容和原理

实验内容：

输入一个电文字符串，构造出哈夫曼树并实现该字符串的二进制输出，并统计该字

符串中的字符总数目及二进制编码的总长度。

实验原理：

哈夫曼树是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二

叉树。本实验中，要输入电文字符以及它的权值，用Hunffman算法构建哈夫曼树。定

义一个存储哈夫曼编码结果的二维数组。为使每一个字符编码都不是另一个字符编码的

前缀，规定哈夫曼树中左分枝以“0”编码，右分枝以“1”编码。

三、实验环境

硬件环境：

多媒体实验室

学生用微机

局域网环境

软件环境:

Windowsxpprofessional

TurboC/C++forwindows

四、算法描述及实验步骤

1，算法描述

-3-

-4-

-5-

-6-

ht[0][1][2][3][4][5][6][7]

w

lch

rch

parent

3，4，2，10为叶子权值。

ch

code

starstarstarstar

2，算法描述及实验步骤

在TurboC/C++forwindows新建名为huffman.c的c程序项目，然后进行编译调试，若编译

○3○4○2○105919

326

154

565767

abcd

3231

011000101

-7-

链接都通过，则运行程序，得出正确结果。正确的程序代码如下所示：

#include"stdio.h"

#include"conio.h"

#include"string.h"

#defineN010

typedefstructnode1

{intw,lch,rch,parent;

}HFT[2*N0-1+1];//哈夫曼树结点的数据类型

HFTht;

structnode2

{charch;

intstart;

intcode[N0];

}hc[N0+1];//字符的哈夫曼编码信息的数据类型

intn,m;

voidlect(intt,int*s1,int*s2)//选择一个权值最小和次小的结点作为叶子结点

{intw1=32767,w2=w1,i;

for(i=1;i<=t;i++)

if(ht[i].parent==0)//先找出前面2个无双亲（即未合并的）结点的位置

if(ht[i].w

{w2=w1;

*s2=*s1;

w1=ht[i].w;

*s1=i;//s1指向最小的数

}elif(ht[i].w

{w2=ht[i].w;

*s2=i;//s2指向次小的数

}

}

voidcreat_ht_hc()//建立哈夫曼树的函数

{ints1,s2,i,child,parent;

freopen("","r",stdin);//读取文件信息，文件名为

freopen("","w",stdout);//写入文件信息，文件名为

scanf("%d",&n);//输入叶子个数n

m=2*n-1;//总结点数m为2*n-1

-8-

for(i=1;i<=n;i++)//分别输入叶子字符以及它的权值

{

scanf("n%c%d",&hc[i].ch,&ht[i].w);

}

for(i=n+1;i<=m;i++)//建树

{lect(i-1,&s1,&s2);//调用lect()函数

ht[i].w=ht[s1].w+ht[s2].w;

ht[i].lch=s1;//ht[i]左孩子指向最小的数

ht[i].rch=s2;//ht[i]右孩子指向次小的数

ht[s1].parent=ht[s2].parent=i;

}

for(i=1;i<=n;i++)//生成哈夫曼编码的函数

{child=i;//从叶子开始

parent=ht[child].parent;

while(child!=m)//查找直到哈夫曼树根结点的路径

{if(child==ht[parent].lch)

hc[i].code[hc[i].start]=0;//左分枝编码为0

el

hc[i].code[hc[i].start]=1;//右分枝编码为1

hc[i].start++;//校正编码的指针位置

child=parent;

parent=ht[child].parent;

}

}

}

voidshowtree(introot,inttab)//哈夫曼树的显示

{if(root)//从根开始，如果根结点不为空

{inti;

for(i=1;i<=tab;i++)printf("");//输出空格

printf("%d",ht[root].w);//输出根结点权值

if(ht[root].lch==0)//如果左孩子为0

printf("(%c)",hc[root].ch);//输出根字符

printf("n");

showtree(ht[root].lch,tab+3);//沿左链下降

showtree(ht[root].rch,tab+3);//沿右链下降

}

}

-9-

voidshowcode()//显示哈夫曼编码

{inti,j;

for(i=1;i<=n;i++)

{printf("%c:",hc[i].ch);//输出结点字符

for(j=hc[i].start-1;j>=0;j--)//依次输出结点的编码

printf("%d",hc[i].code[j]);

printf("n");

}

}

voidchar2bit(charSin[],charSout[])//加密,把字符转化为编码

{inti,j,k,p=0;

i=0;

while(Sin[i])

{for(j=1;j<=n;j++)

if(Sin[i]==hc[j].ch)

{for(k=hc[j].start-1;k>=0;k--)

Sout[p++]=hc[j].code[k]+48;/*Soutl里面存储的是字符，code存储的是数字，字符0,1,

2….9的ASCII是48，49….57*/

break;

}

i++;

}

Sout[p]='0';

}

voidbit2char(charSin[],charSout[])//解密把哈夫曼编码转化为字符

{inti=0,k=m,p=0;

while(Sin[i])

{if(ht[k].lch==0)//如果结点左孩子为0

{Sout[p++]=hc[k].ch;//把字符存入Sout里

k=m;

}

el//否则结点左孩子不为0

{if(Sin[i]=='0')//如果Sim[i]是字符0

k=ht[k].lch;//沿左链下降

-10-

elk=ht[k].rch;//否则沿右链下降

i++;

}

}

Sout[p++]=hc[k].ch;//把字符存入Sout里

Sout[p]=0;

}

main()

{charSin[2*N0+1],Sout[2*N0+1];//定义两个字符数组

clrscr();//清屏

creat_ht_hc();//调用creat_ht_hc()创建哈夫曼树

showtree(m,1);//调用showtree(m,1)显示哈夫曼树

showcode();调用showcode()显示哈夫曼编码

gets(Sin);gets(Sin);

char2bit(Sin,Sout);//加密，把字符转化为编码

puts(Sout);//输出

gets(Sin);

bit2char(Sin,Sout);//解密，把编码转化为字符

puts(Sout);//输出

}

五、调试过程

调试过程前面建树过程没错，当输入caabd，和11进行加密和解密却错了，

错误如下：

-11-

经排除在主函数用gets(Sin);输入字符串是少写了一个gets(Sin);改正如上程序的主函数第7行,

改正之后运行正确.

六、实验结果

最后的运行结果如下：

-12-

七、总结

通过实验，使我对树的结构有了新的认识。在今后学习数据结构的过程中有很大的帮助，也在

编程的过程中掌握了更多编程上的技巧,如使用文件进行输入输出。

参考文献:

[1]宁正元，王秀丽——算法与数据结构清华大学出版社2006

[2]严蔚敏吴伟民——数据结构（C语言版）清华大学出版社2006

[3]宁正元，王秀丽——算法与数据结构习题精解和实验指导清华大学2007