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

河北工业大学数据结构课程实验实验报告题目:基于哈夫曼编码的通信系统的设计与实现专业:计算机科学与技术班级：计1301班姓名：张路浩刘禄源刘磊波李浩川邹博睿王超完成日期：2015113一、试验内容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）掌握构造哈夫曼树的基本思想，及其编码/译码过程.三、流程图开始定义汉字信息string message10通过随机数函数对汉字信息用字符集进行编码pswi设置随机数种子srand(time(NULL);定义字符集大小n输入字符集内容HT.HFMTreei.word输入n统计汉字信息字符编码中各字符出现的频度HT.HFMTreek.weight用字符集对信息进行字符编码void CreatCode(HCodeType& HT,int n)输入编码长度pi2n-1Y指针初始化HT.HFMTreei.parent = -1;HT.HFMTreei.rchild = -1;HT.HFMTreei.lchild = -1;逐个非叶结点构造根据各字符构的频度构造哈夫曼树CreatHFMTree(HT,n)N将各信息的字符编码进行哈弗曼树编码寻找具有最小、次小值的根建树哈夫曼编码CreatHFMCode(HT,HFMCode,n);链接父节点和兄弟结点，i+父指针为空Y输出文字信息和对应的哈夫曼编码Y原来的最小变为次小，记下新的最小值比原来最小的还要小记下新的次小值比原来的次小还小N结束四、源程序代码#include#includecstdlib#includectimeincludestringusing namespace std;constint n=4;/叶子节点个数 constint MAXVALUE = 9999；intm，p； /编码参数string l;int size;/构造哈夫曼树结点 typedefstructint weight;/权值 int parent;/父节点 intlchild；/左子树 intrchild；/右子树char word;/编码字符HNodeType；/构造哈夫曼编码数组typedefstructHNodeTypeHFMTree2n-1；/结点数 int bitn；int start;HCodeType；HCodeType HT；HCodeTypeHFMCoden；string message10=人之初”,性本善”，性相近”，习相远,”苟不教”，”性乃迁”，”教之道，”贵以专”，”昔孟母”,”择邻处”;string psw10；/存储编码/对信息进行编码void CreatCode（HCodeType HT,int n）inti，j，k；char ch;/存储编码的字符集/权重初始化for(i=0;i2*n1;i+）HT.HFMTreei.weight=0;coutHT。HFMTreei。word； /对汉字信息进行编码srand（time（NULL）；cout”*endl；cout”生成的编码为:”endl;for（i = 0；i10；i+）for(j = 0;jp；j+）ch = HT。HFMTreerand（)m。word；pswi +=ch；for（k = 0；km;k+）if（ch = HT.HFMTreek.word）HT。HFMTreek。weight+；if（i0pswi = pswi1)i-;elsecoutmessagei： pswiendl;cout”各字符出现的频度为:”endl;for(i = 0；im；i+）coutHT。HFMTreei。word”出现的频度为:”HT。HFMTreei。weightendl；/创建哈弗曼树voidCreatHFMTree(HCodeType& HT，int n）inti,j；int m1，x1，m2，x2;for（i = 0；i2*n-1；i+）HT。HFMTreei。parent = -1；HT。HFMTreei。rchild = -1；HT.HFMTreei。lchild = 1;for（i = 0;in-1；i+）x1 = x2 =MAXVALUE;m1 = m2 =0；for(j = 0;jn+i；j+)if(HT。HFMTreej.parent=-1&HT.HFMTreej.weightx1）x2 = x1;m2 = m1;x1 = HT。HFMTreej。weight;m1 = j；else if（HT。HFMTreej.parent=1&HT。HFMTreej。weightx2）x2 = HT.HFMTreej。weight;m2 = j;HT.HFMTreem1.parent=n+i；HT。HFMTreem2。parent=n+i；HT。HFMTreen+i。weight=HT.HFMTreem1。weight+HT.HFMTreem2。weight；HT.HFMTreen+i。lchild=m1；HT。HFMTreen+i。rchild=m2;cout”*”endl;cout构造的哈弗曼树为:n;for（i = 0；i（2*n1）;i+）couti” 字符”HT。HFMTreei.word”的权重:”HT。HFMTreei.weight 父结点的位置为:”HT。HFMTreei.parent 左孩子的位置为：”HT.HFMTreei。lchild” 右孩子的位置为:”HT.HFMTreei。rchildendl；/对字符集编码voidCreatHFMCode（HCodeType HT，HCodeTypeHFMCode,int n)HCodeType cd;inti，j,c，p；for（i = 0;in;i+）cd.start = n1；c = i；p = HT.HFMTreei。parent;while（p ！= 1）if（HT。HFMTreep。lchild = c)cd。bitcd.start = 0；else if（HT。HFMTreep。rchild = c)cd。bitcd。start = 1；cd。start-;c = p；p = HT.HFMTreec.parent;for（j = cd。start+1;jn;j+）HFMCodei。bitj = cd。bitj；HFMCodei.start = cd.start+1；cout”*”endl；cout各字符的编码为：”endl;for（i = 0；in；i+）cout”字符”HT。HFMTreei.word的编码为；for(j = 2;jn;j+）coutHFMCodei。bitj；coutendl； int main（)cout”*”endl；cout”*欢迎使用基于哈夫曼编码的通信系统*endl；cout”*”endl;string t10;CreatCode(HT，n）；/对信息进行编码CreatHFMTree（HT，n)；CreatHFMCode（HT,HFMCode，n)；/将信息进行转码cout”*”endl;cout编码结果为：endl;for(inti = 0；i10;i+）coutmessagei”-；for(int j = 0；jp;j+)for(int k = 0;km；k+)if（pswij = HT。HFMTreek.word)for(int l = 2；ln；l+）coutHFMCodek。bitl；coutendl;return 0；五、调试过程六、结果分析