基于哈夫曼编码的通信系统的设计与实现.doc

河北工业大学
《数据结构》课程实验
实验报告
题目:基于哈夫曼编码的通信系统的设计与实现
专业:计算机科学与技术
班级：计1301班
姓名：张路浩刘禄源刘磊波李浩川邹博睿王超
完成日期：2015—1—13
一、试验内容
1）初始化处理：建立通信系统
（1)建立有100句中文的信息集合，每个句子称为一条信息。
（2)输入编码参数：
①从终端输入编码字符集大小n，字符编码长度m(设n为4，m为8)；
②从终端输入编码字符（设为A,B,C,D）;
(3）生成每条信息的字符编码,构造字符编码集合；
（4）计算每个字符在字符编码集合中出现的概率；
(5)根据字符概率构造哈夫曼树,求出每个字符的二进制编码。
2）发送端信息编码
(1）用户从信息集合中选择一条信息，找到该信息对应的字符编码；
(2）根据该信息的字符编码，哈夫曼树求出的每个字符的二进制编码，构造出该信息的二进制编码，记录该二进制编码。(由于是软件模拟，没有发送设备，发送端的编码工作完成）。
3)接受端信息译码
（1）根据得到的信息的二进制编码,利用哈夫曼树求出的每个字符的二进制编码，还原出信息的字符编码；
(2）根据信息的字符编码,找到对应的信息。
5、实现提示
（1）本试验涉及到通讯学科的编码理论和信息学科的数据压缩技术。
（2）根据参数生成的通信系统的所有信息的有效存储问题.
（3)信息字符编码可参考随机数的方式生成,且要求保持唯一性
二、试验目的
（1）掌握二叉树的存储结构及其相关操作。
（2）掌握构造哈夫曼树的基本思想，及其编码/译码过程.
三、流程图
开始
定义汉字信息
stringmessage[10]

通过随机数函数对汉字信息用字符集进行编码psw[i]
设置随机数种子
srand(time(NULL));
定义字符集大小n

输入字符集内容
HT.HFMTree[i].word
输入n

统计汉字信息字符编码中各字符出现的频度HT.HFMTree[k].weight

用字符集对信息进行字符编码voidCreatCode(HCodeType&HT,intn)

输入编码长度p

i<2n-1

Y
指针初始化
HT.HFMTree[i].parent=-1;
HT.HFMTree[i].rchild=-1; HT.HFMTree[i].lchild=-1;
逐个非叶结点构造
根据各字符构的频度构造哈夫曼树
CreatHFMTree(HT,n)

N

将各信息的字符编码进行哈弗曼树编码
寻找具有最小、次小值的根建树
哈夫曼编码
CreatHFMCode(HT,HFMCode,n);

链接父节点和兄弟结点，i++

父指针为空

Y
输出文字信息和对应的哈夫曼编码

Y
原来的最小变为次小，记下新的最小值
比原来最小的还要小

记下新的次小值
比原来的次小还小
N
结束

四、源程序代码
#include<iostream>
#include〈cstdlib〉
#include〈ctime〉
＃include〈string>
usingnamespacestd;
constintn=4;//叶子节点个数
constintMAXVALUE=9999；
intm，p；//编码参数
stringl;
intsize;
//构造哈夫曼树结点
typedefstruct｛
intweight;//权值
intparent;//父节点
intlchild；//左子树
intrchild；//右子树
charword;//编码字符
｝HNodeType；
//构造哈夫曼编码数组
typedefstruct｛
HNodeTypeHFMTree［2＊n-1]；//结点数
intbit［n］；
intstart;
｝HCodeType；
HCodeTypeHT；
HCodeTypeHFMCode[n］；
stringmessage[10]={
｛"人之初”｝,｛"性本善”}，｛"性相近”｝，
{"习相远"},｛”苟不教”｝，｛”性乃迁”｝，{”教之道"｝，｛”贵以专”｝，
｛”昔孟母”｝,{”择邻处”}｝;
stringpsw[10]；//存储编码
//对信息进行编码
voidCreatCode（HCodeType＆HT,intn）
｛
inti，j，k；
charch;//存储编码的字符集
//权重初始化
for(i=0;i〈2*n—1;i++）{
HT.HFMTree[i］.weight=0;
}
cout<〈”请输入编码字符集的大小：m=”；
cin〉〉m；
cout〈〈”请输入编码长度大小:p=”；
cin〉〉p；
cout〈〈"请输入编码字符：”〈〈endl；
for(i=0；i〈m；i++)｛
cin〉>HT。HFMTree[i］。wo