基于哈夫曼编码的通信系统的设计与实现.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.