欢迎来到三一文库! | 帮助中心 三一文库31doc.com 一个上传文档投稿赚钱的网站
三一文库
全部分类
  • 幼儿/小学教育>
  • 中学教育>
  • 高等教育>
  • 研究生考试>
  • 外语学习>
  • 资格/认证考试>
  • 论文>
  • IT计算机>
  • 法律/法学>
  • 建筑/环境>
  • 通信/电子>
  • 医学/心理学>
  • ImageVerifierCode 换一换
    首页 三一文库 > 资源分类 > DOC文档下载
    分享到微信 分享到微博 分享到QQ空间

    哈夫曼编译码系统实验报告.doc

    • 资源ID:52126       资源大小:149.50KB        全文页数:14页
    • 资源格式: DOC        下载积分:5
    快捷下载 游客一键下载
    账号登录下载
    微信登录下载
    三方登录下载: 微信开放平台登录 QQ登录 微博登录
    二维码
    微信扫一扫登录
    下载资源需要5
    邮箱/手机:
    温馨提示:
    快捷下载时,用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)。
    如填写123,账号就是123,密码也是123。
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    哈夫曼编译码系统实验报告.doc

    1、数学与计算机学院 数据结构 实验报告年级 大二 学号* 姓名 * 成绩 专业 电气信息类(计算机) 实验地点 主楼402 指导教师 实验项目 实验日期 2010年11月20日 一、实验目的和要求通过对简单哈夫曼编/译码系统的设计与实现来熟练掌握树型结构在实际问题中的应用。此实验可以作为综合实验,阶段性实验时可以选择其中的几个功能来设计和实现。二、 问题描述利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码(复原)。对于双工信道(即可以双向传输信息的信道),每端都需要一个完整的编/译码

    2、系统。试为这样的信息收发编写一个哈夫曼码的编/译码系统。三、 数据结构设计1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时,设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息,根据二叉树的性质可知,具有n个叶子结点的哈夫曼树共有2n-1个结点,所以数组HuffNode的大小设置为2n-1;描述结点的数据类型为:struct HNodeTypechar data; /结点字符int weight;/结点权值int parent;int lchild;int rchild;int level;2、求哈夫曼树编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。

    3、求哈夫曼编码,实质上就是在已建立的哈夫曼树中,从叶子结点开始,沿结点的双亲链域回退到根结点,每回退一步,就走过了哈夫曼树的一个分支,从而得到一位哈夫曼码值,由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列,因此先得到的分支代码为所求编码为所求编码的低位码,后得到的分支代码为所求编码的高位码,所以设计如下数据类型:struct HCodeTypeint bitMAXBIT;int start;3、文件hfmtree.txt、code、text。四、 功能设计 (1)接收原始数据:从终端读入字符集大小n,以及n个字符和n个权值,建立哈夫曼树,并将它存于文件hf

    4、mtree.dat中。(2)编码:利用已建好的哈夫曼树(如不在内存,则从文件hfmtree.dat中读入),对文件中的正文进行编码,然后将结果存入文件code中。(3)译码:利用已建好的哈夫曼树将文件code中的代码进行译码,结果存入文件text中。(4)打印编码规则:即字符与编码的一一对应关系。(5)打印哈夫曼树:将已在内存中的哈夫曼树以直观的方式显示在终端上。五、 测试数据(1) 利用教科书中的数据调试程序。 令叶子结点个数n为4,权值集合为1 3 5 7,字符集合为A B C D,并有如下对应关系,A1,B3,C5,D7,调用初始化功能模块可以正确接收这些数据。调用建立哈夫曼树的功能模块

    5、构造静态链表HuffNode的存储。调用建立哈夫曼编码规则的功能模块,在屏幕上显示如下对应关系:A1,B3,C5,D7。调用哈夫曼编码的功能模块,在屏幕上输入“ABCD”后,显示编码:调用译码的功能模块,输入代码串“111110100”后,屏幕上显示译码结果:100101110ABCD调用打印哈夫曼树的功能模块。在屏幕上显示哈夫曼树(用凹入法表示)。打印编码规则:(2)用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下报文的编码和译码:“THIS PROGRAM IS MY FAVORITE”。字符ABCDEFGHIJKLM频度18664132232103211547571532

    6、20字符NOPQRSTUVWXYZ频度5763151485180238181161调用建立哈夫曼树的功能模块,构造静态链表HuffNode的存储。调用建立哈夫曼编码规则的功能模块: 调用哈夫曼编码的功能模块:调用译码的功能模块:调用打印哈夫曼树的功能模块。在屏幕上显示哈夫曼树(用凹入法表示)。 打印编码规则:六、 程序代码/ HUFF.cpp : 定义控制台应用程序的入口点。/#include stdafx.h#include#include#includeusing namespace std;const int MAXBIT=100;const int MAXVALUE=2000;cons

    7、t int MAXNODE=100;struct HNodeTypechar data;int weight;int parent;int lchild;int rchild;int level;struct HCodeTypeint bitMAXBIT;int start;static int n;static HNodeType *HuffNode;static HCodeType *HuffCode;/字符和权值的输入及建立哈夫曼树模块*HNodeType *huffmanTree()cout请输入字符总数:n;HuffNode=new HNodeType2*n-1;int i,j;in

    8、t m1,m2,x1,x2;/初始化for(i=0;i2*n-1;i+) HuffNodei.level=1;HuffNodei.data=0;HuffNodei.weight=0;HuffNodei.parent=-1;HuffNodei.lchild=-1;HuffNodei.rchild=-1;/输入字符及权值cout请输入字符(可以识别空格,两个非空格字符之间请不要再加空格):endl;cout形如:(a bc),( abb c)endl;char c;flushall();for(i=0;in;i+)cin.get(c);HuffNodei.data=c;cout字符对应的叶子结点的

    9、权值:endl;for(i=0;iHuffNodei.weight;/建立哈夫曼树for(i=0;in-1;i+)m1=m2=MAXVALUE;x1=x2=0;for(j=0;jn+i;j+)if(HuffNodej.parent=-1&HuffNodej.weightm1)m2=m1;x2=x1;m1=HuffNodej.weight;x1=j;elseif(HuffNodej.parent=-1&HuffNodej.weightm2)m2=HuffNodej.weight; x2=j; HuffNodex1.level=n-i;HuffNodex2.level=n-i;/结点在哈夫曼树的层

    10、次HuffNodex1.parent=n+i;HuffNodex2.parent=n+i;HuffNoden+i.weight=HuffNodex1.weight+HuffNodex2.weight;HuffNoden+i.lchild=x1;HuffNoden+i.rchild=x2;/输出哈夫曼树cout已成功建立哈夫曼树!endl;for(i=0;i2*n-1;i+)coutHuffNodei.weightt;coutHuffNodei.lchildt;coutHuffNodei.rchildt;coutHuffNodei.parentt;coutHuffNodei.levelt;cou

    11、tendl;/把哈夫曼树写入文件ofstream outFile;out(hfmtree.txt,ios:out);for(i=0;i2*n-1;i+)outFileHuffNodei.datat;outFileHuffNodei.weightt;outFileHuffNodei.lchildt;outFileHuffNodei.rchildt;outFileHuffNodei.parentt;outFileendl;out(); cout已成功建立哈夫曼树并存入文件hfmtree.txt!endl;return HuffNode;/建立哈夫曼编码规则模块*void huffmanCode()

    12、HuffCode=new HCodeTypen;HCodeType cd;int i,j,c,p;/建立编码规则for(i=0;in;i+)cd.start=MAXBIT-1;c=i;p=HuffNodec.parent;while(p!=-1)if(HuffNodep.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=HuffNodec.parent;for(j=cd.start+1;jMAXBIT;j+)HuffCodei.bitj=cd.bitj;HuffCodei.start=cd.start;/输出编码规则c

    13、out已成功建立以下编码规则并存入code文件中!endl;for(i=0;in;i+)coutHuffNodei.data-;for(j=HuffCodei.start+1;jMAXBIT;j+)coutHuffCodei.bitj;coutendl;/将编码规则写入文件ofstream outFile(code,ios:out);for(i=0;in;i+)outFileHuffNodei.data-;for(j=HuffCodei.start+1;jMAXBIT;j+)outFileHuffCodei.bitj;outFileendl;out();/哈夫曼编码模块*void coding

    14、)cout请输入要编码的字符串:endl;string s;flushall();getline(cin,s);couts对应的编码为:endl;for(int i=0;is.length();i+)for(int j=0;jn;j+)if(si=HuffNodej.data)for(int k=HuffCodej.start+1;kMAXBIT;k+)coutHuffCodej.bitk;elsecout您输入的编码不正确!endl;coutendl;/哈夫曼译码模块*void deCoding()string code;cout请输入要译码的编码序列:code;coutcode编码后的结

    15、果(已存入txt文件)为:endl;int next,root;for(int i=0;i2*n-1;i+)if(HuffNodei.parent=-1)root=i;ofstream outFile(txt,ios:out); for(int i=0;icode.length();i+)next=root;while(HuffNodenext.lchild!=-1&HuffNodenext.rchild!=-1)if(codei=0)next=HuffNodenext.lchild;i+;elsenext=HuffNodenext.rchild;i+;coutHuffNodenext.dat

    16、a;outFileHuffNodenext.data;i-;coutendl;out();/打印哈夫曼树模块*void printHuffTree()/凹入法打印哈夫曼树for(int i=0;in;i+)for(int j=0;j2*n-1;j+)if(HuffNodej.level=i+1)for(int k=0;kHuffNodej.level;k+)cout ;for(int k=0;k60-HuffNodej.level-i;k+)cout*;cout(HuffNodej.weight);if(jn)coutHuffNodej.data;coutendl; /输出编码规则模块*voi

    17、d printPrinciple()for(int i=0;in;i+)coutHuffNodei.data-;for(int j=HuffCodei.start+1;jMAXBIT;j+)coutHuffCodei.bitj;coutendl;/显示菜单函数*void menu()cout请选择功能:endl;cout菜单:-输入字符和频度,建立哈夫曼树endl;cout 2-建立哈夫曼编码规则endl;cout 3-实现哈夫曼编码endl;cout 4-实现哈夫曼译码endl;cout 5-打印哈夫曼树endl;cout 6-打印编码规则endl;cout 0-退出程序endl;int _

    18、tmain(int argc, _TCHAR* argv)cout*欢迎使用*endl;cout输入字符和权值,建立哈夫曼树:key;switch(key)case 1:huffmanTree();break;case 2:huffmanCode();break;case 3:coding();break;case 4:deCoding();break;case 5:printHuffTree();break;case 6:printPrinciple();break;case 0:break;default:cout输入错误!请正确选择功能:key;while(key!=0);return 0;14 / 14文档可自由编辑打印


    注意事项

    本文(哈夫曼编译码系统实验报告.doc)为本站会员(田海滨)主动上传,三一文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一文库(点击联系客服),我们立即给予删除!




    宁ICP备18001539号-1

    三一文库
    收起
    展开