数据结构大作业.docx

上传人:p** 文档编号:387152 上传时间:2023-08-06 格式:DOCX 页数:13 大小:150.31KB
下载 相关 举报
数据结构大作业.docx_第1页
第1页 / 共13页
数据结构大作业.docx_第2页
第2页 / 共13页
数据结构大作业.docx_第3页
第3页 / 共13页
数据结构大作业.docx_第4页
第4页 / 共13页
数据结构大作业.docx_第5页
第5页 / 共13页
数据结构大作业.docx_第6页
第6页 / 共13页
数据结构大作业.docx_第7页
第7页 / 共13页
数据结构大作业.docx_第8页
第8页 / 共13页
数据结构大作业.docx_第9页
第9页 / 共13页
数据结构大作业.docx_第10页
第10页 / 共13页
亲,该文档总共13页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述

《数据结构大作业.docx》由会员分享,可在线阅读,更多相关《数据结构大作业.docx(13页珍藏版)》请在第壹文秘上搜索。

1、预习分 操作分 报告分 总成绩指导老师实验学号姓名实验名称哈夫曼编码器设计班级实验日期一实验报告具体内容普通应包括:一、实验目的和要求;二、实验原理;三、主要仪器设备(软件);四、实验内容及实验数据记录;五、实验数据处理与分析;六、问题与建议一、实验目的和要求:哈夫曼(HLlffman)树与哈夫曼码1 .输入一个文本,统计各字符浮现的频度,输出结果;2 .使用二叉链表或者三叉链表作存储结构,构造哈夫曼(HUffman)树;3 .确定和输出各字符的哈夫曼码;4 .输入一个由O和1组成的代码序列,翻译并输出与之对应的文本;要求:一个完整的系统应具有以下功能:(1)初始化:从终端读入一段英文字符,统

2、计每一个字符浮现的频率,建立赫夫曼树,并将该树存入某文件;(2)编码:利用建好的赫夫曼树对各字符进行编码,用列表的形式显示在屏幕上,并将编码结果存入另一文件中;(3)解码:利用保存的赫夫曼编码,对任意输入的0,1序列能正确解码二、实验思路:对输入的一串字符串,用循环进行浮现频率的统计,浮现频率即为节点的权值。为了方便将叶子节点数定义成为全局变量。创建哈夫曼树时,先给哈夫曼树创建一个节点,挨次对叶子节点和非叶子节点进行初始化。将全部的叶子节点中最小权值的两个节点的权值进行相加即为非叶子节点。进行哈夫曼编码时,从叶子节点到根节点进行编码。而进行解码时,是从根节点到叶子节点,向左为0向右为K由于书上

3、有相关代码,一部份代码直接借用。三、实验代码:#defineMAX50typedefstructintweight;intparent,lchild,rchild;HTNode,*HuffmanTree;typedefchar*HuffmanCode;intn;叶子结点数charaMAX;接受字符串的数组voidselect(HuffmaTree*ht,inti,int*s1,int*s2)(intj=1;for(j=1;j=i;j+)if(*ht)0.parent=O)(*s1=j;break;for(j=1;j=i;j+)(if(j=*s1)continue;else(计(*ht)jpar

4、ent=0)*s2=j;break;)for(j=1;jK(*ht)j.weight(*ht)*s1.weight&(*ht)0.parent=O&(*ht)*s1.weight!=(*ht)*s2.weight)*s1=j;for(j=1;j=i;j+)(if(j=*s1)continue;else(if(*ht)0weight(*ht)*s2.weight&(*ht)0parent=O)*s2=j;)voidCreattree(HuffmanTree*ht,HuffmanCode*hc,int*w)intm,i,s1,s2;m=2*n-1;*ht=(HuffmanTree)malloc(m

5、+1)*sizeof(HTNode);for(i=1;i=n;i+)数组HUffnOdeU初始化(*ht)i.weight=wi;(*ht)i.parent=O;(*ht)i.lchild=O;(*ht)i.rchild=O;)for(i=n+1;i=m;i+)(*ht)i.weight=O;(*ht)i.parent=O;(*ht)i.lchild=O;(*ht)i.rchild=O;)for(i=n+1;i=m;i+)建立非叶子结点,Huffmantree(select(ht,i-1,&s1,&s2);(*ht)s1.parent=1;(*ht)s2.parent=!;if(*ht)s1.

6、weight(*ht)s2.weight)(*ht)i.lchild=s1;(*ht)i.rchild=s2;else(*ht)i.Ichild=s1;(*ht)i.rchild=s2;(*ht)i.weight=(*ht)s1.weight+(*ht)s2.weight;voidcharge(int*w)i11ti,j,k=1;for(k=1;k=n;k+)wk=1;k=1;if(ai=T)continue;if(ai=aj)(wk+;aO=T;)的频数为k+;)voidcreatnode(HuffmaTree*ht,HuffmanCode*hc)(char*cd;inti,start,c,

7、p;*hc=(HuffmaCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);编码for(i=1;i=n;i+)(start=n-1;for(c=i,p=*ht)i.parent;p!=0;c=p,p=*ht)p.parent)if(*ht)p.lchild=c)cd-start=,O;elsecd-start=1;(*hc)i=(char*)malloc(n-start)*sizeof(char);strcpy(*hc)i,&cdstart);)free(cd);voidtranslate(HuffmaTree*ht,

8、int*w)intp;charsMAX;intm,k,i;m=0;请输入一串01代码p=2*n-1;对应的字符为(if(si=,O)p=(*ht)p.lchild;if(si=,1)p=(*ht)p.rchild;if(*ht)p.lchild=O&(*ht)p.rchild=O)(for(k=1;wk!=(*ht)p.weightjk+)m=m+wk;)四、实验数据put in the namber of the leafs: WSDebug78xeI O12 3 4SinIt打为为为为 1数数数数 JQ k S LuI K*hr(i.pineiitcdtart卜U;cd(t)-r:CbtMwentM)iTcbaEmU。i*tframed):Translate的函数流程图:数据结构实验题目:哈夫曼(HUffman树)与哈夫曼码学院:专业:学号:学生姓名:指导教师:S期:

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > IT计算机 > 数据结构与算法

copyright@ 2008-2023 1wenmi网站版权所有

经营许可证编号:宁ICP备2022001189号-1

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。第壹文秘仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知第壹文秘网,我们立即给予删除!