版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、河北工业(gngy)大学数据结构课程(kchng)实验实 验 报 告题目(tm):基于哈夫曼编码的通信系统的设计与实现专业:计算机科学与技术 班级:计1301班 姓名:张路浩 刘禄源 刘磊波 李浩川 邹博睿 王超 完成日期: 2015-1-13 一、试验(shyn)内容1)初始化处理(chl):建立通信系统(1)建立(jinl)有100句中文的信息集合,每个句子称为一条信息。(2)输入编码参数: 从终端输入编码字符集大小n,字符编码长度m(设n为4,m为8); 从终端输入编码字符(设为A,B,C,D);(3)生成每条信息的字符编码,构造字符编码集合;(4)计算每个字符在字符编码集合中出现的概率
2、;(5)根据字符概率构造哈夫曼树,求出每个字符的二进制编码。2)发送端信息编码(1)用户从信息集合中选择一条信息,找到该信息对应的字符编码;(2)根据该信息的字符编码,哈夫曼树求出的每个字符的二进制编码,构造出该信息的二进制编码,记录该二进制编码。(由于是软件模拟,没有发送设备,发送端的编码工作完成)。3)接受端信息译码(1)根据得到的信息的二进制编码,利用哈夫曼树求出的每个字符的二进制编码,还原出信息的字符编码;(2)根据信息的字符编码,找到对应的信息。5、实现提示(1)本试验涉及到通讯学科的编码理论和信息学科的数据压缩技术。(2)根据参数生成的通信系统的所有信息的有效存储问题。(3)信息字
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.HFMTree
4、i.parent = -1;HT.HFMTreei.rchild = -1;HT.HFMTreei.lchild = -1;逐个非叶结点构造根据各字符构的频度构造哈夫曼树CreatHFMTree(HT,n)N将各信息的字符编码进行哈弗曼树编码寻找具有最小、次小值的根建树哈夫曼编码CreatHFMCode(HT,HFMCode,n);链接父节点和兄弟结点,i+父指针为空Y输出文字信息和对应的哈夫曼编码Y原来的最小变为次小,记下新的最小值比原来最小的还要小记下新的次小值比原来的次小还小N结束四、源程序代码(di m)#include#include#include#includeusing nam
5、espace std;const int n=4;/叶子(y zi)节点个数 const int MAXVALUE = 9999;int m,p; /编码(bin m)参数string l;int size;/构造哈夫曼树结点 typedef structint weight;/权值 int parent;/父节点 int lchild;/左子树 int rchild;/右子树char word;/编码字符HNodeType;/构造哈夫曼编码数组typedef structHNodeType HFMTree2*n-1;/结点数 int bitn;int start;HCodeType;HCod
6、eType HT;HCodeType HFMCoden;string message10=人之初,性本善,性相近,习相远,苟不教,性乃迁,教之道,贵以专,昔孟母,择邻处;string psw10;/存储编码/对信息进行编码void CreatCode(HCodeType& HT,int n)int i,j,k;char ch;/存储编码的字符集/权重初始化for(i=0;i2*n-1;i+)HT.HFMTreei.weight=0;coutm;coutp;cout请输入(shr)编码字符:endl;for(i = 0;iHT.HFMTreei.word; /对汉字信息进行编码srand(tim
7、e(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;k0&pswi = pswi-1)i-;elsecoutmessagei: pswiendl;cout各字符出现的频度为:endl;for(i = 0;im;i+)coutHT.HFMTreei.word出现的频度为:HT.HFMTreei.weightendl;/创建哈弗曼树void CreatHFMTree(HCodeType& HT,int n)int i,j
8、;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.
9、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构造(guzo)的哈弗曼树为:n;for(i = 0;i(2*n-1);i+)couti 字符(z f)HT.HFMTreei.word的权重(qun zhn)
10、:HT.HFMTreei.weight 父结点的位置为:HT.HFMTreei.parent 左孩子的位置为:HT.HFMTreei.lchild 右孩子的位置为:HT.HFMTreei.rchildendl;/对字符集编码void CreatHFMCode(HCodeType& HT,HCodeType HFMCode,int n)HCodeType cd;int i,j,c,p;for(i = 0;in;i+)cd.start = n-1;c = i;p = HT.HFMTreei.parent;while(p != -1)if(HT.HFMTreep.lchild = c)cd.bitc
11、d.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各字符(z f)的编码为:endl;for(i = 0;in;i+)cout字符(z f)HT.HFMTreei.word的编码(bin m)为;for(j = 2;jn;j+)coutHFMCodei.bitj;c
12、outendl; int main()cout*endl;cout*欢迎使用基于哈夫曼编码的通信系统*endl;cout*endl;string t10;CreatCode(HT,n);/对信息进行编码CreatHFMTree(HT,n);CreatHFMCode(HT,HFMCode,n);/将信息(xnx)进行转码cout*endl;cout编码(bin m)结果为:endl;for(int i = 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+)coutHF
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 校园午餐食品安全承诺
- 2025届高考英语一轮复习读后续写说课课件
- 建设工程施工合同书-2
- 山东省济南市(2024年-2025年小学四年级语文)统编版摸底考试((上下)学期)试卷及答案
- 甘肃省甘南藏族自治州(2024年-2025年小学四年级语文)人教版综合练习(上学期)试卷及答案
- 甘肃省酒泉市(2024年-2025年小学四年级语文)人教版摸底考试((上下)学期)试卷及答案
- 2022年秋10月自考05679宪法学练习考题含解析
- 2021年上半年全国自考宪法学模拟试题含解析
- 2021年春季自考法学专业本科宪法学试题含解析
- unit 4 课件教学课件
- 思想政治教育专业师范生双导师制实施办法
- 风电场建设项目绿色施工方案
- 绘本《大脚丫跳芭蕾》PPT课件
- 《汉服》PPT课件(完整版)
- 自考00456教育科学研究方法复习要点
- 为中华之崛起而读书设计
- 新起点小学一至六年级英语单词带音标
- 热处理调质工艺守则及操作规程
- 起重机设备技术要求
- 部编版六年级语文上册第三单元同步练习测试题及答案
- PE投资协议条款样本(NVCA中英文对照版)
评论
0/150
提交评论